ディレクトリデータベースの設計をさらに進めてみる。
性能
前回書いた設計をもとに実装をすすめて、読み書きやカーソルなどの基本的な機能はできてきた。ここで、性能を測ってみよう。もう会社のPCが使えないので家のボロいノートPCでしか性能テストできないのだが、まあ参考にはなるだろう。10万レコードのsetとgetとremoveにかかる時間をファイルハッシュDBとファイルツリーDBとディレクトリDBで比較してみる。キーと値はそれぞれ8バイトである。ディレクトリDBに関してはファイルシステムの性能がものを言うので、ファイルシステムをいくつか試してみた。
| set | get | remove | |
| ファイルハッシュDB | 0.172 | 0.136 | 0.155 |
| ファイルツリーDB | 0.161 | 0.169 | 0.159 |
| ディレクトリDB（EXT2） | 325.814 | 0.943 | 1.860 |
| ディレクトリDB（EXT3） | 13.228 | 1.288 | 4.498 |
| ディレクトリDB（EXT4） | 18.659 | 2.192 | 5.289 |
| ディレクトリDB（XFS） | 587.423 | 18.392 | 508.348 |
| ディレクトリDB（ReiserFS） | 8.909 | 1.474 | 5.819 |
いつもは100万レコードのテストを行うのだが、今回は10万レコードしかやっていない。というのも、ディレクトリDBの書き込みがめちゃくちゃ遅くて100万件は待っていられないからだ。特にEXT2のsetとXFSのset/removeがめちゃくちゃ遅い。getは早いのに。おそらく1個のディレクトリに万単位でファイルを作るのは苦手なんだろう。やはり、ディレクトリDBは、でかいけどそんなに数は多くないようなレコードを手軽に扱う手段だということだ。
他のファイルシステムに比べるとReiserFSは優秀である。たとえ原作者が牢獄にいようと、いいものはいいのだ。ReiserFSであれば、100万件でも、setが106.170秒（9418qps）、getが41.284秒（24222qps）、removeが77.874秒（12841qps）である。万のオーダーのqpsが出るのであれば人気Webサイトでも実用になることが多いだろう。
追記：XFSのnobarrierオプションを試した
XFSはnobarrierオプションをつけてマウントするとかなり高速化するらしいので、同じテストをnobarrierなXFS環境でやってみた（ノートPCをもっと良いものに買い換えたので上記の環境とは違う）。nobarrierをつけるとだいぶ高速化することはわかった。それでもEXT3に比べると大分遅いけども。
| set | get | remove | |
| ディレクトリDB（EXT3） | 3.377 | 0.412 | 3.039 |
| ディレクトリDB（XFS-nobarrier） | 60.462 | 7.863 | 84.787 |
トランザクション
DBM（連想配列）のインターフェイスでファイルシステムが扱えると楽だから嬉しいというのは前回述べたが、KCの場合はトランザクションが使えることも嬉しさのひとつである。つまり、複数レコードに対する一連の操作をアトミックにコミットしたりロールバックしたりできる機能があると、堅牢性を保証する努力をアプリ側でしなくていいから楽で嬉しいということだ。
ACID属性に関する基本戦略としては以下のような感じになろうか。ディレクトリDBの堅牢性に関してはファイルシステムに完全に任せることになるので、それを信用してKC側では特に何の努力もしないことにする。原子性と分離性に関してはロックで守る。レコードロックとトランザクションロックを駆使してゴニョゴニョする仕組みファイルハッシュDBやファイルツリーDBのものをそのまま踏襲する。一貫性に関してはKVSとして以外のことは何も保証せず、アプリ側で気にしてもらう。
DBが壊れないという広義の堅牢性は上述のようにファイルシステム任せなのだが、更新が確定したレコードがきちんと更新された後のデータを保持するという狭義の堅牢性とトランザクションとしての一貫性を確保するには、やはりWAL的なアプローチが不可欠だ。あるレコードのファイルを書いている最中にプロセスが落ちるかもしれないし、複数のレコードを更新するトランザクションで一部のみを更新したところでプロセスが落ちるかもしれない。
結論としては、ディレクトリDBでは、renameシステムコールの原子性をトランザクションのACID属性の根拠とする。ファイルハッシュDBではtruncateシステムコールの原子性を根拠としていたのと比較するとわかりやすいだろう。
トランザクション内での全ての更新操作は、更新前のレコードのファイルを別のディレクトリにrenameで待避することでロールバック可能にする。新規にレコードを作る場合は空のレコードを退避させる。全てのレコードファイルはマジックデータや長さなどのヘッダを持つので空ファイルとは確実に区別できる。で、いざロールバックするという時には、退避ディレクトリの中のレコードファイルは元のディレクトリにrenameし、空ファイルは対応する名前のファイルを元のディレクトリからremoveする。それらを適用すれば確実にトランザクション前の状態に戻るはずだ。レコード数や総レコードサイズなどのメタ情報は元の情報をオンメモリで退避しておいてロールバック時に復元するか、それを行う前に死んだ時には再計算すればよい。退避ディレクトリにファイルがある状態で死んだ場合、次にDBを開いた時にはまず退避ディレクトリの復元から処理を再開するので、アプリ側から次の操作が行われる前にはかならずトランザクション前の状態に戻っていることが保証できる。
コミットしたときには、退避ディレクトリを別名にrenameすることでアトミックに途中状態を破棄する。実際にはrenameしてから、中身を消して、それが終わってから退避ディレクトリ自体も消す。この手順であれば、コミット中にプロセスが死んだとしても、renameの前であれば全てがロールバックされるし、renameの後であれば何もロールバックされない（つまり処理が確定される）ので、ACID属性が保証されるというわけだ。ディスクとファイルシステムが壊れなければの話だが。
ディレクトリツリーDB
ファイルハッシュDBでB+木のページを永続化する実装としてファイルツリーDBがあるわけだが、同じ考え方で、ディレクトリDBでB+木のページを永続化する実装として「ディレクトリツリーDB」というものを考えることもできる。ファイルハッシュDBとディレクトリDBのインターフェイスはほぼ同じなわけだから、既存のファイルツリーDBの実装をちょろっと変えるだけでディレクトリツリーDBが実現できそうだ。テンプレートにしてしまえば同じコードを共有することさえできる。
ディレクトリツリーDBを作るのであれば、圧縮B+木にするために、ディレクトリDBの層で圧縮機能を実装しておきたいところだ。でもそうすると圧縮しているかどうかというメタデータをどこに持たせようかという話にもなり、DBの構造を多少変えることにはなるだろう。
普通のディレクトリDBはsetやgetの度にファイルの開け閉めに伴うopen/closeシステムコールを発生させるわけだが、ディレクトリツリーDBだとそのような非効率性はかなり緩和されるはずだ。setでレコードを各際には同じページのレコードは一括して単一のファイルに書かれるし、getでページキャッシュが効いた場合はファイルの読み出しは発生しない。IOの頻度が下がるということはファイルシステム側の負荷も減る。それでいて、ファイルシステムが本来持っているチャンク管理やデフラグなどの効率化の恩恵を直接的に受けられるので、なかなかいいバランスなんじゃないかな。
まとめ
性能実験してみたところ、ReiserFS上ならディレクトリDBも普通に実用になりそうだ。トランザクションもサポートしているので便利に使えると思う。ディレクトリツリーDBもおもしろそうなので、近いうちに実装と性能検証をしてみる所存。あとZFSとかも試したいなぁ。