Inside Tokyo Cabinet その五
先日、MySQL Conferenceという催しに行ってきました。そこでMySQLの開発者のBrian Aker氏およびMichael Widenius氏と話をする機会があったのですが、やっぱしトップランナー達と議論するのは刺激になるなぁと思ったmikioです（その時の資料）。さて、一連の連載も今回が感動の最終回で、TCの性能上の蘊蓄をお届けいたします。
なぜdynamic hashingを使わないか
Brianさん達とTCの実装についても少し議論したのですが、その際にdynamic hashingをなぜ使わないのかと問われました。その背景として、TCやQDBMではハッシュのバケット数（＝格納するレコード数を予測してその数倍に設定すべき値）をデータベース作成時に指定しなければならないという問題があります。バケット数が大きすぎると空間効率が劣化し、小さすぎると時間効率が劣化するというトレードオフを調整する必要があるということです。
それに対してdynamic hashingは、バケット数を動的かつインクリメンタルに調整できる手法で、NDBM、SDBM、GDBM、BDBでそれぞれ変種が使われています。関連する手法は数多く提案されているのですが、例えば最も典型的なlinear hashingという手法は、バケット配列の使用率がある閾値を越えた段階で、別の領域（典型的にはファイルの末尾）にバケット配列を追加するというものです。元来のバケット配列の要素からリンクされていたレコード群は、ポインタを進めながら少しずつ新しいバケットとの割り当てをやりなおしていって、それが終わった時に元来のバケットと新しいバケットを結合することになります。
兄弟達がdynamic hashingを頑張っているにもかかわらず、QDBMやTCはなぜ古めかしいstatic hashingを使い続け、チェーンを二分探索木にしたくらいで誤魔化しているのでしょう。率直にいえば、面倒く...、いやいや、実装が簡潔になり、高速に動作するからです。結局のところ、dynamic hashingを使ったとしても、（まじめなユースケースでは）最適な性能を出すためには初期値のバケット数を適切に設定することになるし（例えばBDBのset_h_nelem）、初期値を算定する際の予測の誤りは更新性能の劣化となってユーザを悩ませることになります。ということで、どうせレコード数を予測しなきゃならないなら、簡潔で高速な実装の方がいいと判断したものです。
といいつつ何で二分探索木を併用しているのかといえば、レコードあたりたった5バイトのオーバーヘッドで手軽に O(log n) を保証できるからです（木が偏らないための工夫もしてあります）。5バイトが大きいか小さいかはユースケースによるわけですが、B+木や転置インデックスなどの上位構造の基盤としてハッシュデータベースを用いることを想定しているTCの場合、5バイトはかなり小さいと言えるでしょう。また、二分探索木には、バケット容量が十分な場合にも発生しうる衝突のコストを下げるという利点もあります。
なぜページ管理をしないのか
たまにメーリングリストに投げられたり直接メールで箴言されることとして、なぜページ管理をしないのかというのがあります。QDBMやTCではレコードが直接ファイルに書かれてその位置はバケット配列の要素にそのまま記録されますが、NDBM、SDBM、GDBM、BDBでは複数のレコードを格納した「ページ」がファイルに書かれ、バケット配列の要素もページの位置を指し示すように記録されます。レコード毎ではなくページ毎にデータを読み書きするとreadやwriteといった重いシステムコールを呼ぶ回数が減らせるというわけです。ページのサイズをファイルシステムのブロックサイズに合わせるとI/Oの効率が最適化されるのも利点です。
では、QDBMやTCではなぜレコード単位でI/Oを行うのでしょうか。例によって実装を簡潔にして高速化したいという理由もありますが、空間効率を上げたいというのが最大の理由です。各ページに該当するレコードのサイズの合計とページサイズが必ずしも近いとは限らないので、ページサイズが大きすぎると馬鹿にならない無駄が発生してしまいます。逆に、ページサイズを小さくしすぎると、I/Oの効率が悪くなるとともに、ページサイズより大きいレコードがあった場合のワークアラウンドに伴うオーバーヘッドが馬鹿にならなくなります（BDBのset_pagesizeが参考になります）。レコード数の予測ですら面倒くさいのに、ましてや1ページに入るレコードの数やその合計サイズを予測するのなんて勘弁ですよね？
なお、TCが持つアラインメント機能は、ファイルシステムのブロックサイズに近い単位でI/Oを最適化する点でページ管理に近いと言えるかもしれません。ただし、TCのアラインメントは個々のレコードの典型的なサイズを予測すればよいので、ページサイズの設定よりは気楽に行えるはずです。また、複数のレコードをまとめて管理しないことの利点として、ページ内での位置を記録するための空間と時間のオーバーヘッドが節約できるということも挙げられます。B+木や転置インデックスなどの上位層でその層での論理的なレコードをまとめる処理がやられていることを考えると、ハッシュデータベースの層でのページ管理は二度手間とも考えられます。
非同期更新モード
ページ管理をすればreadやwriteの回数を減らして効率化できるということは既に述べましたが、TCでも複数のレコードを一括して書き込むモードがあります。putの対象になったレコードをディスク上でのフォーマットに合わせて直列化して、そのデータをメインメモリ上のバッファに連結していき、バッファのサイズが閾値を越えた時点で一気に書き込みます。writeの回数が抑えられるので高速化する一方で、更新がすぐにファイルに反映されない点で非同期であるというわけです。
バッファ上で直列化されたデータは変更しにくい（不可能ではないが、コストが大きすぎる）ので、ハッシュ値が衝突した際のセパレートチェーンがバッファ上のレコードを通る場合は、バッファがファイルに書き込まれないと新規のレコードを追加できないことになります。そこで、そのようなレコードは遅延用のサブバッファに格納していき、メインのバッファが書き込まれた後に追加することにします。
非同期更新モードがあるのに非同期検索モードはないわけですが、それは仕方ないのです。新規に追加されるレコード群はファイルの末尾に一括して書き込む余地があるのですが、既存のレコードの探索はその対象がファイル全体に散らばってしまうので、まとめてreadすることはできないし、ブロック毎にreadしてキャッシュしておくのもヒット率が低すぎて現実的ではありません（むしろレコード毎のキャッシュの方が効率的）。この観点からも、ハッシュデータベースにページ管理機能をつけるのは避けたくなりますよね。
なお、非同期モードというとLinux 2.6からサポートされたAIO（Asynchronous I/O）を想像されるかもしれませんが、それとは全く関係ありません。AIOはレプリケーションや更新ログの保存にかかる処理を並列化するのには便利ですが、データベースの通常運用で使うにはちょっと面倒すぎました。
フリーブロックプール
削除されたり移動されたりしたレコードの領域はフリーブロックとして再利用されると以前の記事で述べましたが、その管理方法にも結構な工夫が求められます。フリーブロックは位置（ファイル上の先頭からのオフセット）とサイズの構造体ですが、それを管理するフリーブロックプールに求められる機能は以下のものです。
- 新しいフリーブロックを追加する
- これから格納するレコードのサイズより大きい、最適なサイズのフリーブロックを探索する
- データベースファイルが閉じた際に自身を直列化してファイルに記録する
- データベースファイルが開かれた際に自身をファイルから読み出して復元する
上の二つから検討してみましょう。フリーブロックを追加する操作は自明ですが、最適なサイズを割り当てる操作における「最適」とはどんな基準なのでしょうか。勘のよい人は気づいたと思いますが、フリーブロックの割り当てに対する要求はC言語のメモリマネージャが提供するmallocと全く同じものです。フリーブロックの追加がfreeで、追加されるレコードに割り当てる領域を取得するのがmallocに相当します。そこでメモリ管理の手法を参考にして考えます。領域を割り当てる戦略の主なものとしては以下の5つがあります（出典：Tanenbaum先生のMinix本）。なお、フリーブロックプールを探索しても適当なサイズの領域がなかった場合は、隣接したフリーブロックを連結してより大きな領域をつくり出そうとし、それでもダメならファイルのサイズを増やして新しい領域を作ることになります。
- ファーストフィット：先頭から全体を逐次探索して、指定サイズより大きくて最初に見付かったものを選ぶ。
- ネクストフィット：さっき探索を終了した場所から全体を逐次探索して、指定サイズより大きくて最初に見付かったものを選ぶ。
- ベストフィット：先頭から全体を逐次探索して、指定サイズより大きくて最も小さいものを選ぶ。
- ワーストフィット：先頭から全体を逐次探索して、最も大きいものを選ぶ。
- クイックフィット：よく使われるサイズ毎に分けたリストに対して探索を行う。
ファーストフィットやネクストフィットは探索がやや高速になる反面、実際に使われるサイズよりもかなり大きいフリーブロックを割り当てて無駄が生じる可能性が高くなります。ベストフィットは無駄が生じる可能性は低いですが、探索に時間がかかります。さて、ワーストフィットは無駄が多くてしかも遅いやんけと思ったアナタ、私と同類ですね。でもそういうわけではなくて、余った領域をフリーブロックプールに戻すことでベストフィットよりも無駄がなくなるというカラクリなのです。ベストフィットでも余った領域を戻せばいいわけですが、そうすると断片化されて小さすぎる領域ばかりがフリーブロックに溜るのでよろしくないのです。そして最後のクイックフィットは、探索は速いし無駄も少ないのですが、リストが分けられているおかげて隣接したフリーブロックをひとつに連結する操作が遅くなるという弱点があります。要するにどれも一長一短ということです。
TCではフリーブロックプールは配列で実装されています。新しいフリーブロックは配列の末尾に加え、割り当てて削除されたフリーブロックの要素には末尾の要素を補填します。その上で、割り当てのアルゴリズムには以下のような折衷案を採用しました。
- 基本的にはファーストフィットを用いる。
- たまに、フリーブロックを小さい順でソートする。そうするとファーストフィットだけどベストフィット的な具合に近づく。
- 割り当てたフリーブロックが要求されたサイズの2倍以上ならば、余った領域をフリーブロックプールに戻す。
- 要求されたサイズの割り当てに失敗する頻度が増えたら、隣接したフリーブロックを連結する。
フリーブロックプールの時間効率や空間効率はどのようなレコードをどのような順番で格納するかに依存するので、おそらく決定版は存在しないでしょう。したがって、とりあえず私が想定するユースケースであるB+木や転置インデックスのストレージとして良好な結果が出るように調整しています。すなわち、少数の巨大なレコードと多数の小さいレコードが混在し、各レコードは高い頻度と偏った確率でサイズが拡張していくという状況で、時間効率が目に見えて落ちない範囲で空間効率を最大化すべく設計しました。
レコード圧縮
比較的冗長なデータ（特にテキスト）をデータベースに格納することも多いと思います。例えばmixiでは、日記IDをキーとして日記の本文を値とするレコードを格納するような使いかたをするでしょうが、日記の本文のテキストはかなりパターン（記号）の出現頻度に偏りがある冗長なデータです。そのようなデータは圧縮してからデータベースに格納すると空間効率が劇的に改善します。アプリケーション側の責任で圧縮と復元をする運用でももちろんOKなのですが、putする直前に圧縮してgetした直後に復元するのは決まりきっているので、ライブラリ側でサポートしてもバチは当たらないでしょう。
ということで、TCでは二種類の圧縮方式をサポートしています。ひとつはDeflateで、これはzlibを利用して実現しており、LZ77という圧縮アルゴリズムを使ってデータサイズを小さくします。Deflateはテキストでも画像などのバイナリでも大抵の非圧縮データに対してかなりよい圧縮率を実現し、それでいて高速に動作します。
もうひとつはTCBS（Tokyo Cabinet Block Sorting）で、bzip2を参考に私が実装したものです。TCSBは圧縮率も速度もzlibやbzip2に負け負けなのですが、256バイトやそれ未満といった小さいデータに対して効率的であるという特徴があります。BWT→MTFという前処理をしてから圧縮するところはbzip2と同じですが、圧縮にHuffman符号でなくElias Gamma符号を使って辞書分のオーバーヘッドを節約しています。この話をBrianさんにしたら、レコード間で共通した辞書を別の領域に保存すればいいはずで、MySQLではその機能があるとのアドバイスをいただいたのですが、それは今後の研究課題にしておきます。そういえば、Apacheのログを検索可能な状態のままいかに圧縮して保持するかみたいな課題がありますが、圧縮データをDBMに入れて頑張るってのもアリかもですね。
レコード圧縮をわざわざライブラリ内で実現しているもうひとつの理由は、B+木などの上位層における「ページ」をレコードとして保存する際に、冗長なデータを圧縮してからファイルに記録する方が明らかに有利だからです。一般的にデータ圧縮は時間効率を犠牲にして空間効率を稼ぐという位置付けですが、ファイルI/OやネットワークI/Oを伴う場合は、空間効率を高めることでI/Oにかかる時間も減らせるので時間効率もよくなるという、ちょっと不思議で嬉しい事態になります。
壊れにくくする
QDBMにおいては、データベースを開いているアプリケーションが異常終了した場合、もしくはデータベースを適切に閉じずに終了した場合は、データベースが壊れるようにしていました。それらは明白なバグであり、アプリケーションの作者やそれを使うことを選択したユーザに何らかの意識的な対処を求めることが適切であると考えたからです。データベースを修復するユーティリティがQDBMに付属しているのでそれを使って修復作業を行うことはできるのですが、そのコストとリスクは因果応報として受け入れてもらいます。
しかし、上記のような理想主義と「上から目線」では現実の問題に対処できないことを近ごろ感じはじめました。マナーを守らない/守れないユーザやユースケースも結構な割合で存在するのが現実なのです。したがって、TCは、マナーを守らないアプリケーションやそのユーザにも宥和する戦略に転換しました。すなわち、たとえ重要なデータベースを開いているにもかかわらず適切なシグナルハンドラを書いていないアプリケーションがあっても、そしてたとえそのようなアプリケーションをSIGTERMやSIGINTで殺すユーザがいても、あるいはアプリケーションがSIGSEGVを発生させて自滅しても、データベースがなかなか壊れないようにしました。だって、いま挙げたプレーヤは全て私ですから。
前回の記事で挙げた並列性の議論を思い出していただきたいのですが、データベースファイルが壊れる事態は、クリティカルセクション内で処理が停止した場合に発生します。つまり、単一のクリティカルセクション内でファイルの書き込みを複数回にわたって行う際に、最初の書き込みは成功したが最後またはそれ以前の書き込みが失敗した場合には、データベースファイルの状態に不整合が起きることになります。例を挙げてみましょう。
- putで、レコードの実体をwriteしてファイルサイズが増えたのに、そのメタデータをwrite（実際はmmap領域の更新）していない。
- putやoutで、レコードの実体やフリーブロックをwriteしてレコード数が増減したのに、そのメタデータをwrite（実際はmmap領域の更新）していない。
- putやoutで、レコードの実体やフリーブロックをwriteしてバケット配列が変更されたのに、その要素をwrite（実際はmmap領域の更新）していない。
- putやoutで、レコードの実体やフリーブロックをwriteしてチェーンが変更されたのに、その親のヘッダをwriteしていない。
- putやoutで、フリーブロックプールが更新されているのに、それを書き戻していない。
- putやoutで、そもそもwriteの途中で失敗した。
ファイルサイズのメタデータが狂う件については、statで問い合わせて修復すればよいでしょう。レコード数のメタデータが狂う件については、壊れていることは確かですが、格納したレコードの情報が失われているわけではないから許容することにしましょう（最適化の際に再計算すれば修復可能）。バケット配列が更新されない件については、そのレコードのputやoutは無かったことにすればその他の整合性は確保できるでしょう。チェーンの件も同様です。フリーブロックプールの書き戻しができていない件については、フリーブロックプールをなかったことにすることで対処できるでしょう（再利用できないフリーブロックが出るが、まあ気にしない）。最後に挙げた、writeの途中で失敗したケースは判断が難しいのですが、レコード実体やフリーブロックのwriteで起こることがほとんどでしょうから、その場合はバケット配列やチェーンの更新も行われないので、更新が無かったことにすれば整合性が確保できるでしょう。
重要なのは、レコードのエントリポイント（そのレコードに辿り着くポインタ）の更新を、レコードの実体を更新した後に行うということです。エントリポイントの更新は1回のwriteで済むので（バケット配列直下の場合は0回）、途中で失敗する確率は低いし、エントリポイントを更新する前に落ちても不正状態になるのはそのレコードだけで済むからです。もちろん本気で耐障害性を考えるなら更新ログを記録しないといけませんけどね。
ということで、現状では、データベースを閉じないでプログラムが落ちたとしても、大抵の場合でデータベースファイルは壊れないようになっています（非同期更新モードの場合はその限りではありません）。とはいえ、やはり開いたデータベースファイルをきちんと閉じているかどうかを確認して安心したいでしょうから、データベースファイルにフラグを設けています。データベースファイルが書き込みモードで開かれた時にそのフラグは立てられ、正常に閉じられた時にそのフラグは降ろされます。つまり開いたままプロセスが死ぬとフラグが立ったままになるので、次に開いた時にそのフラグを確かめることで意識的な対処が可能になるわけです。
超まとめ
Tokyo Cabinetは時間効率と空間効率がそれなりによくて使いやすいDBMです。CDBには負けるけどそれに近いくらい速く小さく頑健で、そして更新可能なDBMです。今まで述べた工夫の他にも、細かいトリックをたくさん入れて効率を稼いでいます。文章で説明されてもおそらくわかりにくいでしょうから、ご興味のある方はぜひソースをご覧ください（結論）。コアの部分は3000行に満たないくらい小さいので、比較的理解しやすいと思います。何かアドバイスがあればコッソリ教えてくれると嬉しいです。
今後はB+木などの上位層の実装と、更新ログやトランザクションなどの機能強化を行っていきたいと思います。なので、いずれまた連載を再開するかもしれませんし、しないかもしれません。それでは、Happy DBM Hacking!!
