Kyoto Cabinet 1.2.0にて、B+木をディレクトリデータベース上で実装したという話。
ディレクトリツリーデータベース
先日リリースしたディレクトリデータベース（DirDB）は個々のレコードを別個のファイルとして単一のディレクトリ内に格納する実装であり、抽象データベースを継承しているので主なインターフェイスはファイルハッシュデータベース（HashDB）と同じである。
ところで、ファイルハッシュデータベースでページ管理を行ってB+木を表現する実装として、ファイルツリーデータベース（TreeDB）というのが従来からある。ということは、ディレクトリデータベースでページ管理を行ってB+木を表現する実装を考えてもよさそうだ。これをディレクトリツリーデータベースと呼ぶ。木というイメージとたくさんファイルがあるというイメージから、ForestDBという識別子にしようか。区別のために、従来のディレクトリデータベースはディレクトリハッシュデータベースと呼ぶことにする。
実装
TreeDBの実装は全てkctreedb.hに書いてある。その場合、クラス定義の中でHashDBという識別子を使っているところをBASEDBとかいう名前で検索置換して、クラスの前にtemplate <class BASEDB>とか書いてあげて、内部クラス識別子にいくつかtypenameを補うだけで、実装をテンプレート化できる。C++素晴らしい。
こうしてできたB+木実装のクラステンプレートをPlantDBと名づける。そんでもって、ファイルツリーデータベースとディレクトリツリーデータベースは今や以下の実装になってしまった。
typedef PlantDB<HashDB> TreeDB; typedef PlantDB<DirDB> ForestDB;
これが意味するところは大きい。連想配列のインターフェイスを持つものはたいがい、それをベースとしたB+木に進化させることができるのだ。実際は連想配列（set/get/remove）以外にもファイル操作（open/close）などのインターフェイスを実装しなきゃならないけども、必要ないならダミーでよい。
DirDBをPlantDBに対応させるにあたっては、HashDBで使っていたバケット数などのチューニングメソッドのダミー実装をつける必要があった。テンプレート特殊化でも対処できただろうが、その辺のリファクタリングは今後の課題としよう。
性能
で、実際にForestDBをビルドして動かしてみたところ、驚くべきことに一発でテストケースをパスした。俺すげー。っつかC++すげー。しかも、性能がなぜかTreeDBを凌駕している。これも驚きだ。ファイル数が増えているっていうのに、なぜ高速化するんだろう。例によってキー8バイト値8バイトのレコード100万件のset/get/removeのテスト結果を以下に示しておく。CPUはCore i7 LM620（2GHz）でメモリは4GBでOSはUbuntu10.04でファイルシステムはEXT3（writeback）。
| write | get | remove | |
| HashDB | 0.747 | 0.765 | 0.675 |
| DirDB | 149.592 | 207.701 | 215.489 |
| TreeDB | 0.727 | 0.909 | 0.828 |
| ForestDB | 0.709 | 0.846 | 0.735 |
ファイルハッシュデータベースとディレクトリハッシュデータベースを比べると、前者の方が200倍くらい早い。なのに、ファイルツリーデータベースとディレクトリツリーデータベースを比べると、後者の方がほんの少し早くなる。なんでだろう。
今回のテストはB+木のシーケンシャルアクセスをしているので、一旦書き込まれたリーフノードは二度とアクセスされることはなく、ファイルツリーデータベースでは、各ページにおいてwriteかreadを1回発行するのみで処理が終わる。ディレクトリツリーデータベースではそれに加えてopenとcloseが1回づつ加わるので遅くなりそうなものだが、その代わりにcloseした後は関連するリソースの優先度を下げるみたいな効率化がなされていたりするのだろうか。わからん。
ファイルツリーデータベースとディレクトリツリーデータベースに関しては1億件のテストもやってみようか。B+木のページサイズは65536にした。
| write | get | remove | |
| TreeDB | 82.625 | 98.071 | 107.854 |
| ForestDB | 105.450 | 100.412 | 112.348 |
今度はファイルツリーデータベースの方が性能が良くなった。上記の表には現れていないが、ディレクトリツリーデータベースの方はデータベースのclose処理に追加で45秒くらいかかっている。謎だ。でも俺としてはファイルデータベース系が勝つ方が嬉しい。なぜならそれがKCのコアだから。
KCの今後
2つのディレクトリDBが加わったことで、KCは今や技のデパートみたいな状態になってきた。これだけ揃えばかなりいろんなユースケースで活躍できるんじゃないだろうか。
| 名前 | 時間計算量 | アルゴリズム | ロック粒度 | 永続性 | 用途 |
| ProtoHashDB | O(1) | ハッシュ表 | 全体 (rwlock) | なし | なし（テスト用） |
| ProtoTreeDB | O(log N) | 赤黒木 | 全体 (rwlock) | なし | オンメモリで順序構造を管理 |
| CacheDB | O(1) | ハッシュ表 | レコード (mutex) | なし | キャッシュ |
| HashDB | O(1) | ハッシュ表 | レコード (rwlock) | あり | 小さいけど多数のメタデータ的情報 |
| TreeDB | O(log N) | B+木 | ページ (rwlock) | あり | 小さいけど多数の順序付きメタデータ的情報 |
| DirDB | 未定義 | 未定義 | レコード (rwlock) | あり | 大きいけど少数のデータ |
| ForestDB | O(log N) | B+木 | ページ (rwlock) | あり | 比較的大きく比較的多数の順序付きデータ |
ディレクトリツリーデータベースの面白い用途としては、やはり転置インデックスが挙げられると思う。転置インデックスはレコードの長さがどんどん伸びていくのが特徴であり、その場合はフラグメンテーションが起きやすいファイルハッシュデータベースでページ管理をするよりは、フラグメンテーションをほとんど起こさないと言われるEXT3等のファイルシステムを直接使ってページ管理をする方が効率的だろう。
なぜNTFSやFATではフラグメンテーションがよく起こるのにEXT系では起こらないのかと言えば、NTFSやFATではファイル群のデータをパーティションの前方に詰めぎみに配置しようとするのに対し、EXT系ではパーティション全体に個々のファイルのデータを分散させて置くかららしい。ファイルの長さを縮めた時にできる小さすぎて利用不能な隙間とか、ファイルの長さを増やそうとした時に後ろに別のファイルがあってそれができないから別の場所に書き直した場合にできる隙間とかが、もともとパーティション内にファイルが散在していればできにくいということらしい。
KCやTCのファイルハッシュデータベースでは、ユーザがパディングサイズを指定することができて、さらにフリーブロックプールとオートデフラグカーソルが隙間を回収していくことで上述のフラグメンテーションを緩和している。ファイルシステムのようにパーティションサイズが決まっていて、「予めこの領域を使い切っていい」という状態であれば、EXT系のように富豪的に領域を使ってフラグメンテーションをさらに緩和することができるだろう。ユーザから「予約データベースサイズ」を前もって教えてもらえれば同じことができるはずなので、今後それも検討してみる。
なお、多相データベースや各種言語バインディングからディレクトリツリーデータベースを呼ぶには、データベース名の拡張子に「.tcf」をつけるか、オプション文字列「#type=tcf」をつけるかすればよい。その他のオプションはファイルツリーデータベースと同じで、「#psiz=65536」とかでページサイズを調整でき、「#opts=c」で圧縮が有効になり、「#zcomp=arc#zkey=aiueo」で暗号化もできちゃう。すぐれもの。
まとめ
ディレクトリハッシュデータベース上にB+木を構築したディレクトリディレクトリツリーデータベースを実装してみたら、性能が思いのほか良くって驚いた。バカっぽい仕組みなようで、結構実用になるんじゃないかなぁ。単一マシンでのスケーラビリティやスループットを最大化させるのは実はこのディレクトリツリーデータベースなのかもしれない。でもそれを最強と認めるのはDBMの存在意義を否定することなので、今後はディレクトリツリーデータベースを倒すべく、ファイルツリーデータベースの改良を考えていきたいと思う。