mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

Tokyo (Cabinet|Tyrant)の新機能

mixi

アロハシャツとショートパンツとビーサンで出勤してスネ毛が美しくないと評判のmikioです。さて今回は、Tokyo Cabinet（TC）とTokyo Tyrant（TT）のそれぞれ最新版でサポートされた新機能についてご紹介します。

固定長データベース

最終ログイン時刻データベースをTTで管理する仕組みについての記事を以前書きましたが、それに対して「各レコードを固定長にすればlseek一発で参照できるよ」という趣旨のご指摘をいただきました。全くその通りで、最終ログイン時刻の値に必要な領域は各ユーザ毎に10バイトもあれば十分ですし、検索キーはユーザID（mixiにおいては1からの連番）なので、それを添字に使えば二次元配列としてデータベースを表現することができます。

ただし、yamazさんも指摘しているように、ログイン時刻データベースのスループット限界はwriteがブロックすることにより訪れるので、データ構造がハッシュ表でも二次元配列でもwriteの回数はほぼ同じことから、性能はそんなに変わらないとも考えられます。むしろ実運用上で問題になったのは、更新ログの記録のためのwriteが重いのと、cron駆動の別プロセスで更新ログを削除した際にファイルシステムが重くなってTTも重くなることでした（いろいろ試したところ、更新ログを小さい単位にしてコマメに消すのがコツらしいです）。したがって、現状では二次元配列にする必要はないのですが、まあ今後もユーザが増えて負荷が増大していくことを考えると、より効率が良い実装を準備しておくのが大人のマナーでしょう。

fixedlength.png

ということで「固定長データベースAPI」なるAPIをTCに追加しました。ハッシュデータベースとほぼ同じインターフェイスだけれども、中身は固定幅の多次元配列をmmapしたものです。実装はものすごく簡単です。キーをstrtollにかけて自然数を取り出して（0以下はエラーにする）、データベース作成時に指定してある各レコードの幅（最大長）にキーのIDを掛けたオフセットを算出し、そこに値を書き込むのです。実際には値の長さのための領域（255バイト以下なら1バイト、65535バイト以下なら2バイト、それ以上なら4バイト）がレコードの幅に足されることになります。

固定長データベースは「キーが連番に近い自然数で値が固定長以下である」という制約がありますが、それに該当するユースケースでは比類ない性能を発揮します。100万件の読み書きを行った以下のベンチマーク結果を見るとその爆速っぷりがおわかりいただけると思います。固定長データベースの読み込みは実に2738万QPSの性能なのです（単なる配列操作なんだから早いのも当たり前ですが）。

tcperformance.png

固定長データベースは並列処理性能も最強です。固定長データベースではレコードの位置を特定する計算において別のレコードの状態を勘案する必要がないので、ロックの粒度を完全にレコード単位にすることができるからです。ただし実装上は、レコードの数だけのmutexを準備するとメモリの無駄なので、ハッシュロックと呼んでいる手法を用います。例えば127個のmutexの配列を作っておいて、キーのハッシュ値に対応する要素をロックするというものです。127個もあれば衝突する可能性は十分低いですし、たとえ衝突したとしてもそのスレッドが一瞬ブロックするだけでスループットの大勢には影響がありません。

なお、TCの抽象データベースAPIにも固定長データベースAPIのラップ機能を持たせたので、自動的にTTからも固定長データベースを使えることになっています。もちろんmemcachedプロトコルでも利用できます。TCのPerl/Ruby/Javaバインディングからも利用できます。

さらに余談ですが、ハッシュやB+木には前方一致するキーの取得を行うfwmkeyという関数がありますが、その使い方が固定長データベースだとちょっと異なります。数には前方一致という概念がないので、前方一致パターンの代わりに区間記法を用います。例えば、10以上20以下は "[10,20]"、10以上20未満は "[10,20)"、10超20未満は "(10,20)"、10超20以下は "(10,20]" と指定します。

値の回転

TTの独自プロトコルにおいて、tcrdbputrttというメソッドが加わりました。これは、既存のレコードの値の後ろにデータを連結するtcrdbputcatメソッドの発展で、連結した結果として値の長さが一定を越えた場合には、前からそれを切り捨てるというものです。例えば、「ABCDEFGH」に「IJK」を連結して制限長8で回転させた場合、「DEFGHIJK」が新しい値になります。

値の回転は基本的には履歴の管理のような用途のためにあります。典型的なのはmixiの足あとデータベースです。各ユーザのIDをキーにして、そのユーザのページを訪れたユーザのIDを最大60個まで保存するというのが現状の仕様ですが、これはTTで管理することができます。新たにユーザが足あとをつける場合、そのユーザのIDと時刻それぞれ4バイトの整数としてpackした値を、8バイト*60個=480バイトの制限長で回転させればよいのです。制限長があるということは値は固定幅になるので、上述の固定長データベースと組み合わせればかなり効率的に処理が行えると考えられます。実際のところ、MySQLで問題なく管理できている現状の足あとデータベースをわざわざ置き換えるようなことはしないのですが、データマイニングの用途では回転は重宝することと思います。

no replyモード

memcached-1.2.5とCache::Memcached::Fast-0.10で追加されたno replyモードをTTでも実装しました。これは、setやdeleteなどの更新操作の際に、クライアント側にその成否を送信しないようにするものです。大量の更新を行う際にはno replyモードを利用するとパフォーマンスが非常によくなります。クライアントは一切recvすることなしにsendを繰り返すので、MTUが許す限りのリクエストを単一のパケットに詰め込んで送ることができるからです。実際にハッシュデータベースへのsetを100万回繰り返すベンチマークテストをしたところ、約25倍のスループットが出ることがわかりました。TTの独自プロトコルでもtcrdbputnrメソッドを呼ぶことでno replyモードを利用することができます。性能特性もmemcachedプロトコルとほぼ同じです。 

　　　　　　time　　　QPS
default　35.936s　　 27827
noreply　 1.366s　　732064

なお、Cache::Memcached::Fastでは、newメソッドの引数で { servers => [{ address => "localhost:1978", noreply => 1 }] } などとすることでnoreplyモードを指定できますが、その上でさらにsetメソッドをvoidコンテキストで評価しないとno replyモードにならないことに注意してください。つまり、setメソッドの戻り値を評価しようとするとno replyモードでなく通常モードになってしまいます。これに関して個人的な見解を言わせてもらえば、sendのエラーはno replyモードであっても検出すべきなので、コンテキストでモードを切り替えるのはあまり良い設計ではないと思います。

非同期ロギング

最終ログイン時刻データベースのボトルネックに更新ログが関わっていることは既に述べましたが、TTでAIO（Asynchronous I/O）を利用することによってそれを軽減することができます。ttserverを実行する際に -uas オプションをつけるとAIO更新ログモードになります。

更新ログを記録する際には、その対象となる操作の順番とログの順番は、同一のレコードに対しては常に保証されなければなりません。したがって、データベースの更新とログの書き込みは同一のロックで保護する必要があります。また、更新ログは単一のファイルの末尾に追記していくので、普通にwriteやwritevで更新ログを書き込む方法だと、更新ログの書き込み操作はグローバルなロックで保護する必要があります。そうすると、結果的にデータベースの操作がグローバルなロックの中に入っているのと同じことになってしまうのです。

そこで、writeやwritevの代わりにaio_writeを用います。aio_writeは実際にデータがファイルに書き込まれるのをまたずに制御を返し、別スレッドで書き込みを行ってくれます。ここで重要なのは、追記モードで開いたファイルの場合、aio_writeを用いた順番と書き込まれるデータの順番が同じになるのが保証されることです。したがって、データベースの操作とaio_writeをレコード単位のロック（実際は上述のハッシュロック）で保護して実行すれば、各レコードに対する更新操作の順番と更新ログの順番が確実に一致するのです。

固定長データベースに別マシン2台から合計32スレッドでアクセスして、各100万回の書き込みを計3200万回行うテストをしてみたところ、以下のような結果になりました。すごく速くなるわけでもないみたいですが、クライアント数がもっと多い場合にはもっと効果があるかもしれません。 

　　　　　time　　　QPS
default　 469s　　 68230
AIO mode　378s　　 84656

まとめ

TCやTTの最近の追加機能として、固定長データベースとno replyモードと値の回転と非同期ロギングについて紹介しました。かなりマニアックな機能ばかりですが、できるだけコストをかけずに高負荷に耐える仕組みを模索するとこうなりました。こういうad hocな機能追加をいちいちサーバ作者やライブラリ作者がやっているとキリがないので、CouchDBのようにサーバ側でJavaScriptなりのデータ処理言語を動かしたい欲求に駆られますが、そうするとシンプルかつチープに徹するというTTのコンセプトと矛盾してしまうので我慢しています。TTのエンハンスはこれくらいにして別のプロジェクトをまた考えようかな（Mac OS XとFreeBSD対応をやれよという声もちらほらありますが...）。

追伸、TTの独自プロトコルのRuby版クライアントが近々出るそうです。また、TCのErlangバインディングが出たらしいので、そちらもチェックしてみてください。