飲み屋に行くとかなりの確率で荷物を忘れて帰るmikioです。さて、今回はここ2ヶ月ほどで急ピッチで開発した軽量データベースライブラリ「Kyoto Cabinet」について紹介します。
開発の動機
以前から軽量データベースライブラリとしてご好評いただいているTokyo Cabinetですが、DBMとして必要十分な機能と性能を備えていてなかなか良いものだと自負しております。ただ、開発を進める中でいくつか不満な点があったのも事実です。端的に言えば、全てC言語で記述して、標準ライブラリ（とzlib/bzip2）以外の機能は全て自作しているので、最適化がしやすい反面、メンテナンスの難易度が高くなってしまっているというのが不満です。
そこで、多少性能が悪くなってもいいから、私自身としてお気楽に開発およびメンテナンスができて、移植性も高いような実装を作ってみようと思い立ったのが昨年10月頃。様々な検討を経てついにC++を採用し、STLを使って楽々にプログラミングしてみようということになりました。
特徴
KCの基本設計はTCのものを踏襲しているので、TCと同じく以下の点が優れています。
- プロセス組み込みなので、ネットワーク通信等のオーバーヘッドがない。
- 静的ハッシュの単純な構造なので高速で並列性も高い。
- データベースファイルが小さく空間効率が高い。
- オンメモリデータベースとファイルデータベースを使い分けられる。
- トランザクションによってACID属性を確保。
- 動的デフラグでデータベースの肥大化を抑止。
- APIが単純で使いやすい。
- 名前がかっこいい。
一方で、KCは実装上の工夫をさらに重ねて、TCに比べて以下の利点を獲得しています。
- さらに空間効率が高い。
- さらに並列性が高い。
- 下層の抽象化による非POSIX環境への対応。
- レコード操作の究極的な抽象化。
- 実装上の細かい改善。
KCの性能はTCに比べてかなり低く、現状では半分以下です。しかし、ユーザランドでの並列性は高いはずなので、OSやハードウェアの並列性が上がれば、並列処理で使った場合の全体のスループットがTCに勝つ日も来るかもしれません。
空間効率が高い
いかなるデータベースにおいても、レコードを管理するためのデータを記憶しておく必要があり、TCやKCではレコードに前置するヘッダとしてそれを表現しています。データベースの空間効率を高めるにはこのヘッダをできるだけ小さくすることが重要です。
TCでは通常モードで14バイト、ラージモードで22バイトのヘッダ領域をレコード毎に必要としていました。通常モードとラージモードの違いはレコードのアドレッシングのために4バイトの領域を使うか8バイトの領域を使うかの違いです。4バイトだと2^32=4GBまでの値を表せ、それにデフォルトアラインメントの16バイトを掛けた64GBまでのデータベースを扱えることになります。8バイトだと2^63=8EBまでのデータベースを扱えます。
今日の一般的な計算機環境を考えると、4バイトアドレッシングは非力すぎる一方、8EBのストレージなんてものも存在していません。そこで、KCではモードを統一して、6バイトアドレッシングを採用しています。6バイトだと2^48=256TBまでの値が扱え、デフォルトアラインメントは8なので、2PBまでのデータベースを扱えることになります。1台のデータベースで扱えるサイズとしては当面はこれで十分でしょう。なお、アラインメントは32768まで上げることができるので、ライブラリとしての最大データベースサイズはTCと同じく8EBまでとなります。
アドレッシングの幅が4バイトから6バイトに上がった分だけ空間効率が悪化するので、それが最小限になるように努力もしています。レコードを識別するためのマジックナンバをサイズ管理用の領域に押し込んだり、後述の二分探索木をバランスさせるためのキーを動的に再計算することで記憶領域をとらないようにしたりして、16バイトまで抑えました。TCの通常モード14バイトに比べると多少増えていますが、ラージモードの22バイトに比べるとかなり減っています。
TCやKCでは静的ハッシュ法によるインデックス（バケット配列）を管理することでレコードの探索を高速化していますが、バケット配列の要素が足りない場合でも著しく遅くならないようにするために、ハッシュ値の衝突管理を二分探索木で行って計算量を抑制しています。とはいえ、単一のマシンでどれだけのレコードを管理できるかはあらかじめ予測できるはずなので、きちんとチューニングすれば二分探索木の機構は不要とも言えます。そこで、きちんとチューニングできる人達のために、「線形モード」も用意しました。二分探索でなく線形リストとして衝突管理を行うことで子供のアドレスの6バイトを節約するのです。つまり、線形モードを使えば、バケット配列のサイズに対してセンシティブな性能特性にはなるけれど、ヘッダのサイズを10バイトにまで減らせるのです。
さらに、KCは使うけどデータベースサイズが32GB以下だと確実に分かっている場合には4バイトのアドレッシングで十分なので、「スモールモード」も用意しました。線形モードとスモールモードを併用するとレコード毎のヘッダは8バイトで済みます。ここまでやればTCに対して優位性を示せるでしょう。
並列性が高い
TCやKCではPthread（POSIXスレッド）パッケージでマルチスレッドの排他制御を行っています。例えばデータベースファイルのサイズというメタデータを更新するためには、mutexでロックをかけて、更新を行って、ロックを解除するという手順を踏んでいます。この構造自体は仕方ないことですが、変数一つを更新するためにmutexのロック/アンロックのオーバーヘッドがかかるのは非効率なので、できればもっと軽量な方法を使いたいところです。
うまいことに、GCCのバージョン4からはi386のアトミック演算機能を呼べる拡張機能がサポートされているので、それを使うことにしました。もちろんIntel系以外のCPUを使った環境やGCC以外のコンパイラでビルドする場合にはそれだとうまくいかないので、その場合はspinlockで該当の変数を保護する代替実装を適用するようにしています。
それ以外にも、並列性に着目してコード全体を見直して、ロックフリーとはいかないまでも、クリティカルセクション内でブロックし得るシステムコールを一切呼ばないというところまでは来ています。
TCと同じく、「pread/pwriteというシステムコールは明示的な内部状態（ファイル位置）を持たないので並列性が高いと言われつつも実際には期待外れな問題」に対処するためにmmapを積極活用しています。KCでは全てのファイルI/Oをmmap経由でやろうとも思ったのですが、諸事情で断念して、結局mmapとpread/pwriteを併用する実装になっています。
非POSIX環境への対応
TCでは最適化のためにモジュール化の原則を崩しまくっていわばモノリシックな構造になっているので、POSIX依存のコードをそうでないOS用に書き換えるのが絶望的に難くなっています。とはいえ、TCは主にWebサービスのバックエンドとして利用することを想定しているので、LinuxやFreeBSDやSolarisで動けば十分だという割り切りの上で設計をしていたので、これは問題ではありませんでした。いわゆる組み込み系やWindows等のデスクトップ環境で動く必要はないということです。
一方、KCは組み込み系やWindowsでも動くようにする予定です。よって、多少オーバーヘッドがあろうとも、処理系依存部分は徹底的にモジュール化して、C++03標準で定義されていないシンボルはハッシュDB本体の実装には一切現れないようにしました。主にファイルI/Oを抽象化するFileクラスとスレッド管理を抽象化Threadクラスがそれを担っています。
Windows版はまだ開発に着手できていませんが、数ヶ月以内にはリリースしたいと思っています。構造を単純化したのでPure Java版も作れるだろうとかDBフォーマットをRFCにできたら格好いいとか妄想は膨らみますが、多分口だけで終わると思います。
レコード操作の抽象化
KCを設計する際に、「KVSとは何だろう」「DBMとは何だろう」とかいう哲学的な部分を考察しました。その結果、KVSとは以下のメソッドを宣言したインターフェイスであるという仮説が導き出されました。
- set : キーと値の組を記憶し、後でgetできるようにする。
- get : キーを指定して、そのキーを伴って直前に記憶された組の値を取得する。
- remove : キーを指定して、そのキーを伴って直前に記憶された組の記憶から消す。
- open : 直前にcloseした際の記憶を復元する。
- close : setやremoveによって更新された論理構造を記憶装置に保存する。
KVSの「Key-Value」はset/get/removeを示し、「Store/Storage」はopen/closeを示す感じでしょうか。そして、DBMとは、上記KVSの実装形態の一つであり、実装として以下の条件を満たすものです。
- ファイル記憶 : 記憶状態をファイルシステム上のファイルに保存する。
- プロセス組み込み : ネットワーク通信を伴わず、関数呼び出しだけの低いオーバーヘッドでメソッドを呼び出せる。
これらはあくまでオレオレ定義にすぎませんが、KCはDBMであり、DBMはKVSなので、KCはKVSだと考えています。まあ、「分散しないものはKVSとは言えない」とか、「ACIDじゃないものはそもそもDBとは言えない」とかいうオレオレ定義をするのも自由なので、TCやKCを実際のところ何と呼ぶのかはユーザの皆様にお任せすることにします。
話を戻して、KVSインターフェイスの一実装であると認識されるKCですが、並列処理を想定した場合、キーと値の組に対する操作はset/get/removeだけでは済まないというのが課題になります。単一スレッドの直列処理の場合、レコードの状態をgetしてから、その内容やそれ以外の状況に応じてそのレコードをsetしたりremoveしたりすれば、キーと値の組に対するいかなる操作も実現することができます。一方で、並列処理の場合、getしてからset/removeするまでの間に別のスレッドがレコードの状態を変更してしまう可能性があるため、何らかの排他制御機能が必要となります。そのためには主に以下の二つの戦略があります。
- lock/unlockメソッドの定義 : 該当のレコードをlockしてから、任意の操作を行って、最後にunlockするのをアプリケーションの責任で行う。
- 各種の操作を全てライブラリ側で定義 : 上記の操作のひとつひとつをライブラリ側で実装する。
前者はライブラリ側の実装が簡素になるとともに、アプリ側で排他制御の有無や粒度を自由に設定できるという利点がある反面、実装が複雑になり、デッドロック等の酷いバグを生み出す原因になります。後者逆の特性で、アプリ側は不自由ながらも簡潔になる反面、ライブラリ側のメンテナンスは非常に大変になります。TCでは後者を採用して、putcatとかaddintとかaddbouleとか多数のメソッドを実装しまくるという苦労を味わっていますが、KCではその苦労を少しでも軽減したいものです。
ここでKVSの定義を再検討してみましょう。レコードに対するいかなる操作も、「特定のレコードの状態を調べて、それに応じて更新操作をしたりしなかったりする、という挙動をアトミックに行う」という風に抽象化できます。例えば、各種操作は以下のような言い換えが可能です。
- set : レコードの状態を調べるが、その状態の如何に関わらず新しい値に書き換えて更新する。
- get : レコードの状態を調べて、レコードがあれば値を返し、元の状態をそのまま残す。
- remove : レコードの状態を調べて、レコードがあれば削除して、なければ何もしない。
- increment : レコードの状態を調べて、レコードがあればそれを数値とみなして、なければ0とみなして、付与の値を足した値をもって、レコードの値を書き換える。
- append : レコードの状態を調べて、レコードがあればその値に、なければ空文字列に、付与の値を後置した値をもって、レコードの値を書き換える。
例えて言うなら、キーに対応するレコードの空間にアプリケーションの実行者を案内して、その値の読み書きを自由にさせるという操作を、その空間に限定してアトミックに行わせるということです。すなわち、KVSの仕様としては、操作の具体的な内容ではなく、アトミック性を保証する範囲が重要であるということになります。その考えに基づいてKVSを定義すると、以下のようになります。
- キーに対応する値の更新履歴を1世代以上記憶することができる。
- openメソッドは記憶のある時点のスナップショットを復元する
- closeメソッドは記憶のその時点のスナップショットを保存する
- キーに対応するレコードの状態の取得と更新をアトミックに行える
- 付与のキーに基づくレコードがある場合、そのレコードの値を渡してコールバック関数を呼ぶ
- 付与のキーに基づくレコードがない場合、何も渡さずコールバック関数を呼ぶ
- 上記のコールバック関数が値を返したなら、その値を元のキーに対応する値として記憶する
具体的なAPI
ここまでの議論で新たに認識したKVSインターフェイスをC++のAPIに落とし込んでみましょう。
class DB {
// レコードの空間を訪問する操作主体のクラス
class Visitor {
public:
// 訪問時、更新が必要ない（no operation）の場合に返す値
static const char* const NOP;
// 訪問時、そのレコードを削除したい場合に返す値
static const char* const REMOVE;
// 仮想デストラクタ
virtual ~Visitor() {}
// 既存のレコードを訪問した場合に呼ばれるコールバック関数
virtual const char* visit_full(const char* kbuf, size_t ksiz,
const char* vbuf, size_t vsiz, size_t* sp) = 0;
// 存在しないレコードを訪問した場合に呼ばれるコールバック関数
virtual const char* visit_empty(const char* kbuf, size_t ksiz, size_t* sp) = 0;
};
// 訪問者を受け入れる
bool accept(const char* kbuf, size_t ksiz, Visitor* visitor, bool writable);
// データベースを開く
bool open(std::string& path, int mode);
// データベースを閉じる
bool close();
};
上記はKyoto Cabinetの実際のインターフェイスです。アプリケーションは、openでデータベースオブジェクトを利用可能にした後、DB::Visitorを実装した任意のクラスを定義して、それをデータベースオブジェクトのacceptメソッドに渡して操作を行い、最後にデータベースオブジェクトを閉じます。データベースから「hoge」というキーに対応する値を検索して表示するアプリケーションは以下のようになります。
DB db;
db.open("casket", DB::OREADER);
class : public DB::Visitor {
virtual const char* visit_full(const char* kbuf, size_t ksiz,
const char* vbuf, size_t vsiz, size_t* sp) {
cout << string(kbuf, ksiz) << " has " string(vbuf, vsiz) << endl;
return NOP;
}
virtual const char* visit_empty(const char* kbuf, size_t ksiz) {
cout << string(kbuf, ksiz) << " is empty" << endl;
return NOP;
}
} visitor;
db.accept("hoge", 4, &visitor, false);
db.close();
毎回Visitorを実装するのは面倒なので、KCの実際のDBクラスには典型的な操作であるset/get/remove/append/incrementをacceptを使って実装したものがビルトインとして組み込まれています。ただ、レコードの操作は必ずacceptを経由するようにしているので、ライブラリ内の実装はとても簡潔で保守しやすくなっています。
詳細についてはKCのチュートリアルとAPI文書をご覧ください。
実装上の細かい改善
KCではハッシュ関数としてMurMur hashを採用しています。TCで採用していた各バイトを37倍して足すハッシュ関数だと、自然言語の単語のようなものをキーにする際にはとても効率がよいのですが、intなどのバイナリ表現をそのままキーにすると衝突率が高まるという弱点があります。TCでは主なユースケースのひとつとしては全文検索の転置インデックスを想定していたのでそれでもよかったのですが、KCではより汎用性を重視して、数値のバイナリでも偏りが出にくいという評判のあるMurMurを採用した次第です。MurMur hashと同じような特性を示すFNV hashも捨てがたいところで、自然言語の単語ではFNVの方がよさげでしたが、やはり数値バイナリでの安定性が上のような気がするMurMurを採用しました。とはいえ、ハッシュ関数はプラグインで入れ替えられるようにする予定です。
TCでは値の圧縮にgzipとbzip2を切り替えて使えるようにしていましたが、bzip2モードを使う人があまり多くない割に、libbz2-devパッケージをインストールしていなくてはまる人が多いので、bzip2は廃止しました。ただし、TCと同じく任意の圧縮関数をプラグインで入れ替えられるようにしているので、bzip2はもちろん、LZOやLZSSやLZMAを使うことも可能です。
特定のハッシュ関数や圧縮関数で作ったデータベースファイルは同じ関数のセットを組み込んだDBオブジェクトで開かないと不整合が起きるわけですが、チェックサム機構を備えることでそういった不整合を事前に検出できるようにもしています。
TCでは全レコードを横断的に参照するために内部イテレータ方式を採用していました。内部イテレータ方式は、データベースの内部にどこまで読んだかという情報を保持するので、アトミック性の確保が容易になり、実装も単純になる反面、同時に一つのイテレータしか使えないという弱点があります。KCでは内部イテレータと外部イテレータの両方をサポートしています。外部イテレータ方式は、どこまで読んだかという情報を保持するカーソルオブジェクトを生成してアプリケーション側で管理するものです。アトミックに全レコードを操作したい場合には内部イテレータを用いて、アトミック性はいらないから複数スレッドで並列にスキャンを行いたい場合には外部イテレータを使うとよいでしょう。
さらに、KCではイテレータによるレコードアクセスもacceptメソッドを経由して行うので、Visitorによる任意のアトミック処理ができ、そしてイテレーション中のレコードの書き換えも簡単に行うことができます。どうせならSTLのstd::map::iteretorと互換にしようともちらっと思いましたが、あまりに面倒なので挫折しました。
まとめ
Kyoto CabinetはTokyo Cabinetの後継の製品で、性能は悪化していますが、機能性と並列性と移植性と保守性は向上しています。まだまだアルファバージョンで、実用に耐える品質とは言い難い状態ですが、そこそこ使える状態まではもっていく所存です。
TCは不要なのかというのがFAQになりそうなのでここで答えておくと、そんなことはありません。おそらく、TCが使える環境ではTCを使い続けるのがよいでしょう。POSIX準拠でない環境（主にWindows）でDBMが欲しい場合にはKCが役立つと思います。そういう意味では、KCはTCの後継というより、QDBMを共通の親とするTCの兄弟と言った方が適切かもしれません。
