データベースライブラリであるTkrzwの初版をリリースした。Kyoto Cabinetの正式な後継製品である。本家のサイトはここである。設計目標の通り、高速かつ堅牢で多目的に使える実装になったと思っている。私の下手な英文を読ませるのも忍びないので、ここに概要を書いておこう。
ダウンロードとインストール
このディレクトリにソースファイルのパッケージが置いてあるので、ダウンロードする。あとは典型的なインストール手順を踏襲すればよい。
$ tar zxvf tkrzw-0.9.1.tar.gz $ cd tkrzw-0.9.1 $ ./configure $ make $ make check $ sudo make install
自分の環境でもテストをしたいという人は以下のコマンドを実行してもよいし、しなくてもよい。テストケースはGoogle Testを使って書かれているので、予めそれをインストールしておくこと。
$ make test $ make testrun
C++のAPIについてはこの文書に詳述してある。典型的なアプリケーションプログラムは以下のようなコードになるだろう。
#include "tkrzw_dbm_hash.h"
int main(int argc, char** argv) {
tkrzw::HashDBM dbm;
dbm.Open("casket.tkh", true).OrDie();
dbm.Set("hello", "world").OrDie();
std::cout << dbm.GetSimple("hello") << std::endl;
dbm.Close().OrDie();
return 0;
}ビルドは以下のようなコマンドで行う。GCC 11以上（まだ出てない）ならデフォルトがC++17になるので -std=c++17 というオプションは省略してもOKだが、それまでは必要。
$ g++ -std=c++17 -I/usr/local/include \ -O2 -Wall helloworld.cc \ -L/usr/local/lib -ltkrzw -lstdc++ -lpthread
データ構造
設計と実装に関する一連の連載で述べたように、DBMとはキーと値からなるレコードの集合をファイルに保存する機能を提供するライブラリである。検索条件に該当するキーを持つレコードを線形時間よりも高速に見つけることができる。そのためのアルゴリズムは数多くあるが、中でも典型的に使われるハッシュ表とB+木とスキップリストを今回は実装した。おまけでオンメモリの実装も提供する。以下のクラスがある。
- HashDBM: ファイル上のハッシュテーブル
- TreeDBM: ファイル上のB+木
- SkipDBM: ファイル上のスキップリスト
- TinyDBM: メモリ上のハッシュテーブル
- BabyDBM: メモリ上のB+木
- CacheDBM: メモリ上のLRU削除キャッシュ
- StdHashDBM: メモリ上のハッシュテーブル
- StdTreeDBM: メモリ上の赤黒木
まず、ファイル上の実装とメモリ上の実装を分けて考察しよう。ファイル上の実装はレコードのデータがファイルに記録された状態で運用されるため、メモリ使用量が少なく、データベースオブジェクトの起動と終了にかかる時間はほぼゼロである。しかし、毎回の操作でファイルに対する入出力が発生するために、遅くなる。一方、メモリ上の実装ではメモリ使用量が大きくなる。起動時に全レコードをファイルから読み込んで終了時に全データを書き込む機能を持つのでデータの永続化は一応可能だが、その場合は起動と終了に時間がかかる。
次に、順序つきの実装と順序なしの実装に分けて考察しよう。順序つきとは、レコードがキーの順序（辞書順）で並べられているかのように振る舞うものだ。それによって、「100以上200未満」といった範囲検索や、「"app"で始まる（="app"以上"apq"未満）」といった前方一致検索ができる。順序なしだとキーの完全一致による検索しかできない。順序なしの代表であるハッシュテーブルは、検索の計算量がO(1)であり、検索処理にかかる時間がレコードの数によらず一定である。上で挙げたその他のアルゴリズムは全て順序つきのデータ構造を実現するものだが、検索の時間計算量はO(log N)であり、つまり検索処理にレコード数の対数に比例する時間がかかる。
仕様を単純化して無駄を徹底的に省いた実装をすることで個々の検索や更新の操作の性能を上げているのがDBMの特徴である。さらに、実装者の腕の見せ所として、スレッド並列性をいかに上げるかというのがある。複数のスレッドが同時にデータベースの操作を行なった際にも、データの一貫性を損なうことなく、できるだけ並列に処理を行って、スループット（一定時間に処理できる量）を最大化するのだ。一貫性を保つためにはミューテクス（mutual exclusion＝相互排他制御）が必要になるが、その粒度をいかに細かくするかが肝要である。ハッシュテーブルではレコード単位のミューテクスを実現し、B+木ではページ単位のミューテクスを実現している。
以上のことを表にまとめるとこんな感じになる。
| クラス | ストレージ | アルゴリズム | 順序 | 計算量 | 更新方法 | ミューテクス |
| HashDBM | File | Hash table | No | O(1) | Online | Record RW-lock |
| TreeDBM | File | B+ tree | Yes | O(log N) | Online | Page RW-lock |
| SkipDBM | File | Skip list | Yes | O(log N) | Batch | Whole RW-lock |
| TinyDBM | RAM | Hash table | No | O(1) | Online | Record RW-lock |
| BabyDBM | RAM | B+ tree | Yes | O(log N) | Online | Page RW-lock |
| CacheDBM | RAM | Hash table | No | O(1) | Online | Slot RW-lock |
| StdHashDBM | RAM | Hash table | No | O(1) | Online | Whole RW-lock |
| StdTreeDBM | RAM | Red-black tree | Yes | O(log N) | Online | Whole RW-lock |
古式ゆかしいDBMの特徴を引き継いでいるのがHashDBMだ。ファイルの先頭にあるハッシュテーブルからファイル内の様々な場所にリンクを張ることで、O(1)という最善の計算量で検索処理を実現する。ミューテクスもレコード単位であり、並列性も最高だ。追記モードを実装してクラッシュしても絶対に壊れないようにできたり、スレッドをブロックせずにDBの再構築ができたりといった、実運用で嬉しい機能も備えている。順序なしのファイルデータベースが欲しいならこれで決まり。これと全く同じアルゴリズムをオンメモリで実装したのがTinyDBMだ。省メモリかつ並列動作を可能とする、順序なし連想配列の実装である。さらに、LRUレコードの自動削除機能を備えたCacheDBMも提供される。
リレーショナルデータベースのインデックスでよく使われるB+木をファイル上で実装したのがTreeDBMだ。検索処理の計算量は O(log N) だ。B+木の各ノードをHashDBMのレコードとして保存することで永続化を実現している。追記モードや再構築の機能もHashDBMから引き継いでいる。また、キャッシュ機構を工夫することで、毎回のレコード操作でページ全体のファイル入出力が発生する欠点を緩和している。ミューテクスはページ単位で実現していて、並列性もそこそこある。順序ありのファイルデータベースとしてはこれがまず検討されるだろう。これと同じアルゴリズムをオンメモリで実装したのがBabyDBMだ。省メモリかつ並列動作を可能とする順序あり連想配列の実装である。
ソート済みのレコード群にスキップリストを付与して二分探索できるようにしたのがSkipDBMだ。検索処理の計算量は O(log N) だ。この構造は分散コンピューティングの現場でよく使われるが、各社がSSTable（Sorted String Table）と呼ぶ構造はまさにこれだ。構築時に全てのレコードをソートする必要があるのでオンライン更新ができない欠点があるが、いったん構築してしまえばファイルの空間効率も検索処理の時間効率も良いので便利に扱える。マージソートを使うことで実メモリより大きい規模のデータベースも構築できる。順序つきのデータベースでスケーラビリティを追求したい場合はこれが検討されるだろう。
StdHashDBMとStdTreeDBMは、それぞれstd::unordered_mapとstd::mapをラップした実装であり、TinyDBMとBabyDBMの性能を引き立たせるための噛ませ犬だ。std::unordered_mapとstd::mapはスレッドセーフではないのでテーブル全体のRWロックで保護せざるを得ないし、個々のレコードがstd::stringクラスを内包するので空間効率が最適ではない。しかし、それらは標準実装なので、テスト時の信頼できる比較対象として活躍する。
性能テスト
能書きはいいから、性能はどうなんだと。まずは100万レコードを保存して検索して削除する処理のベンチマークテストをしてみよう。レコードのキーは「00000000」から「00999999」までの8バイトの連番の文字列として生成する。レコードの値はキーと同じ8バイトの文字列とする。
| class | Set | Get | Remove | memory usage | file size |
| HashDBM | 1,426,925 QPS | 1,734,473 QPS | 1,207,978 QPS | 28.4 MB | 26.8 MB |
| TreeDBM | 1,506,575 QPS | 1,612,324 QPS | 1,418,317 QPS | 67.9 MB | 17.8 MB |
| SkipDBM | 1,144,860 QPS | 394,145 QPS | 1,211,729 QPS | 64.8 MB | 19.3 MB |
| TinyDBM | 2,506,691 QPS | 2,929,785 QPS | 2,744,441 QPS | 54.7 MB | n/a |
| BabyDBM | 2,080,122 QPS | 2,331,687 QPS | 2,084,949 QPS | 61.1 MB | n/a |
| CacheDBM | 2,505,286 QPS | 3,115,558 QPS | 2,858,990 QPS | 73.7 MB | n/a |
| StdHashDBM | 2,012,894 QPS | 2,920,263 QPS | 2,661,896 QPS | 99.1 MB | n/a |
| StdTreeDBM | 1,331,320 QPS | 2,957,670 QPS | 2,751,585 QPS | 104.5 MB | n/a |
どれも100万QPSとか200万QPSとか出ていて凄い。100万レコードの保存が1秒以内に終わるということだ。ファイルデータベースとオンメモリデータベースを比べるとさすがにオンメモリが勝つが、ファイルの方も比肩する性能を出せている。さて、並列性のある実装では、スレッド数を増やせばもっとスループットが上がることが期待される。今度は10スレッドを使って同じことをさせてみよう。
| class | Set | Get | Remove | memory usage | file size |
| HashDBM | 2,064,218 QPS | 4,011,795 QPS | 2,048,902 QPS | 28.7 MB | 26.8 MB |
| TreeDBM | 837,329 QPS | 2,271,298 QPS | 695,477 QPS | 63.8 MB | 19.0 MB |
| SkipDBM | 762,903 QPS | 1,520,528 QPS | 886,466 QPS | 80.8 MB | 19.3 MB |
| TinyDBM | 5,058,370 QPS | 8,370,093 QPS | 6,611,346 QPS | 54.8 MB | n/a |
| BabyDBM | 1,136,897 QPS | 7,395,522 QPS | 1,213,289 QPS | 50.5 MB | n/a |
| CacheDBM | 5,238,041 QPS | 7,387,499 QPS | 7,382,310 QPS | 74.0 MB | n/a |
| StdHashDBM | 804,870 QPS | 8,667,923 QPS | 1,131,562 QPS | 99.3 MB | n/a |
| StdTreeDBM | 387,786 QPS | 8,069,927 QPS | 1,128,146 QPS | 106.6 MB | n/a |
予想通り、ミューテクスの粒度が細かい実装は並列化によってスループットが上がるが、ミューテクスの粒度が大きい実装はスループットが変わらないかむしろ下がる。HashDBMの更新スループットが200万QPS、検索スループットが400万QPSに到達しているのはなかなかの快挙ではないだろうか。
たった100万件程度のテストでは足りない。今度は1億件でやってみよう。キーは「00000000」から「99999999」の間でランダムに割り振ることにする。ツリー系のアルゴリズムはシーケンシャルアクセスの性能が異常に高まる傾向になるので、平均的な実力を知るにはランダムなキーを使った方が良い。
| class | Set | Get | Remove | memory usage | file size |
| HashDBM | 1,269,066 QPS | 1,528,441 QPS | 1,302,638 QPS | 1787.6 MB | 1828.2 MB |
| TreeDBM | 179,108 QPS | 129,585 QPS | 310,956 QPS | 3903.3 MB | 1596.8 MB |
| SkipDBM | 432,946 QPS | 204,870 QPS | 843,037 QPS | 3036.5 MB | 1225.7 MB |
| TinyDBM | 2,267,644 QPS | 2,576,552 QPS | 2,690,487 QPS | 3573.0 MB | n/a |
| BabyDBM | 490,861 QPS | 493,863 QPS | 489,624 QPS | 2963.1 MB | n/a |
| CacheDBM | 2,263,022 QPS | 2,257,323 QPS | 2,745,666 QPS | 4999.2 MB | n/a |
| StdHashDBM | 1,691,914 QPS | 2,131,297 QPS | 2,315,516 QPS | 6409.0 MB | n/a |
| StdTreeDBM | 463,928 QPS | 516,673 QPS | 505,744 QPS | 6593.6 MB | n/a |
ハッシュ系の実装は規模が大きくなっても理論通りO(1)の性能が出せていて素晴らしい。ツリー系の実装が規模の対数に比例して遅くなるのもこれで確認できた。TreeDBMの性能の落ち込みが激しいのは、ライブラリ内のキャッシュにデータが載りきらなくなってファイル入出力の頻度が増えたからだ。この規模から先はSkipDBMの方が高性能になってくる。あと、TinyDBMとBabyDBMのメモリ使用量がStdHashDBMやStdTreeDBMより半分くらいになっていることにも注目されたい。
同じ1億件の条件を10スレッドでやってみよう。大規模サービスのバックエンドとしてデータベースサーバを動かした場合の傾向を占うにはよい条件だと思う。
| class | Set | Get | Remove | memory usage | file size |
| HashDBM | 2,134,418 QPS | 3,729,010 QPS | 2,631,454 QPS | 1787.6 MB | 1828.2 MB |
| TreeDBM | 183,013 QPS | 486,047 QPS | 315,559 QPS | 4062.7 MB | 1602.7 MB |
| SkipDBM | 380,683 QPS | 1,325,381 QPS | 742,633 QPS | 3036.4 MB | 1225.7 MB |
| TinyDBM | 7,376,532 QPS | 8,314,453 QPS | 7,596,498 QPS | 3573.0 MB | n/a |
| BabyDBM | 687,414 QPS | 3,481,460 QPS | 655,081 QPS | 2960.3 MB | n/a |
| CacheDBM | 6,871,719 QPS | 7,358,504 QPS | 8,325,958 QPS | 4999.5 MB | n/a |
| StdHashDBM | 711,054 QPS | 10,794,019 QPS | 1,334,017 QPS | 6409.6 MB | n/a |
| StdTreeDBM | 103,929 QPS | 3,944,576 QPS | 121,817 QPS | 6595.6 MB | n/a |
HashDBMのスループットは100万件の時とほぼ同じで、検索400万QPSくらいと更新200万QPSくらいを示した。TinyDBMの検索800万QPSくらいと更新700万QPSくらいというのは圧巻だが、HashDBMがその半分くらい出ているというのが今回の肝だ。それに比べると、TreeDBMは検索48万QPSと更新18万QPSしか出せないので、だいぶ劣る。ファイル上のB+木操作にはページ単位の入出力が伴うので仕方がない。
ということで、やたら高速なデータベースが欲しい場合には、HashDBMを使うと良い。順序つきデータベースが欲しい場合には、TreeDBMかSkipDBMを検討することになる。オンライン更新が必要なら前者、そうでなければ後者を使うことになるだろう。メモリに乗る規模であればTinyDBMかBabyDBMを使うと良い。
性能に関する留意点
上記の1億件の性能テストの規模では、たかだが2GBのデータベースファイルを作るだけだ。その規模だと、ファイル全体がファイルシステムのキャッシュに乗る。したがって、ファイルの読み書きを行なっているとはいえ、実際にはファイルシステムが管理するメモリの内容を更新しているに過ぎないので、やたら高速なのだ。DBMに性能上の利点があるのは実メモリに乗る規模までだ。
それを超えた規模の性能にこそ興味があるという人もいるだろう。ただ、そうなると、ほとんどストレージデバイスの性能テストをやっているようなものになる。ここで、ファイルシステムやライブラリ内部のキャッシュが全くないという状況を想定してみよう。ハッシュデータベースの検索においては、ハッシュテーブルを読むのに1ページの読み込みを必要とし、レコードを読むのに1ページの読み込みを必要とするので、合計2ページの読み込みが必要となる。実際には、ファイルの先頭に集めてあるハッシュテーブルの領域にはmlockというシステムコールでメモリロックがかけられてキャッシュが強制されるので、典型的にはレコードの実データのための1ページだけを読むことになる。アプリケーション側で1バイト読もうが100バイト読もうが、ファイルシステムが読み込むのは4096バイトのページ単位になる。ストレージデバイスはそれに応じてブロック単位で読み取りを行う。そして、かかる時間のほとんどはストレージデバイスが使うことになる。データ転送にも時間がかかるが、ランダムアクセスでハードディスクのヘッドが動いてシークタイムが発生するのも痛い。
ツリーデータベースの検索においては、 B+木の高さに応じた、典型的には4つくらいのノードを読み込むことになる。各ノードはハッシュデータベースのレコードなので、その読み込みもページ単位で行う。つまり4ページの読み取りが必要であり、ここでもかかる時間のほとんどはストレージデバイスが使うことになる。全体のレコード数をNとするとlog N個のレコードの読み取りと比較を要するのが順序つきデータ構造の宿命だが、ページ単位の操作の回数はほぼ定数であるというのがB木やB+木の素晴らしいところだ。それでもなお、キャッシュが全く効かないと想定した場合には、1レコードの読み取りに対して4回以上のシークと1万バイトを超えるデータ転送が必要となる。もちろん実際にはキャッシュが効くので少しはマシになるのだが、複数ページの読み取りが必要であるという点は変わらない。
操作するページの数はアルゴリズムによって決まるのであって、コードを最適化することでこの構造を変えることはできない。つまり誰が実装したって、DBMだろうがRDBMSだろうが、同じような数のページを読み書きすることになる。そしてページを読み書きする速度はハードウェアの性能に依存する。ソフトウェア層の最適化など、ハードウェアの性能差の前では塵に等しい。よって、DBMの良さを生かすには、データベースファイルのサイズが実メモリに収まる規模であることが望ましい。それに収まらない場合には、複数のマシンを使った分散処理を検討すべきだ。マシンをたくさん持っていない場合でも、分散処理と同じ考え方で分割した部分問題を逐次処理する時間分散の手法を検討したい。
そうはいっても、単体のマシンでできるだけ大きいデータベースを構築したいという人もいるだろう。そういう場合は、まずはストレージデバイスにはハードディスクではなくSSDを使うべきだ。RAMほどではないが、SSDはハードディスクより桁違いに早い。ストレージデバイスやファイルシステムの実装が並列処理に対応している場合、大規模データベースにおいてもDBMライブラリの並列処理性能が生かされ、スループットが最大化される。
並列性能とかはどうでもよいユースケースでは、すなわちシーケンシャルなバッチ処理においては、できることならSkipDBMを使うべきだ。スケーラビリティの観点では、ほぼシーケンシャルアクセスのみでデータベースを構築できるSkipDBMが最強である。それが無理ならば、つまりオンライン更新が必要ならば、追記更新モードのHashDBMを使うと良い。追記更新モードでもほぼシーケンシャルアクセスのみでデータベースを構築できるので、空間効率は悪いが、スケーラビリティは高い。オンライン更新もレコードの順序も必要なのであれば、TreeDBMを使う以外に選択肢はない。
大規模なデータのテストは、下層のハードウェアの性能に律速され、またアクセスパターンによって大きく左右されるので、実環境と実データ（を模したダミーデータ）と実アプリケーション（を模したテストドライバ）を使って行うべきである。
セカンダリインデックス
key-valueよりも複雑な構造を表現したい場合には、その構造をシリアライズした文字列をvalueに入れればよい。主キー以外で検索したい場合にはTreeDBMやBabyDBMを使ったセカンダリインデックスを実現するクラスを使うとよい。セカンダリインデックスは検索キーと主キーのペアの順序集合であるが、それをTreeDBMでファイル上に実現したFileIndexというクラスと、BabyDBMでメモリ上に実現したMemIndexというクラスと、std::mapでメモリ上に実現したStdIndexというクラスが提供される。
FileIndexとMemIndexとStdIndexのそれぞれに対して1億件の挿入と検索と削除を行う性能テストをやってみた。10スレッドで並列に操作する。
| class | Add | Check | Remove | Memory Usage |
| FileIndex | 61,779 QPS | 216,758 QPS | 63,744 QPS | 7202.7 MB |
| MemIndex | 455,743 QPS | 2,428,402 QPS | 392,666 QPS | 6144.4 MB |
| StdIndex<int64_t, int64_t> | 158,152 QPS | 4,935,703 QPS | 142,164 QPS | 5962.8 MB |
| StdIndex<int64_t, string> | 128,086 QPS | 4,528,615 QPS | 128,206 QPS | 7453.0 MB |
| StdIndex<string, int64_t> | 114,269 QPS | 3,768,720 QPS | 110,755 QPS | 7452.9 MB |
| StdIndex<string, string> | 105,488 QPS | 3,477,022 QPS | 101,512 QPS | 10433.1 MB |
| StdIndexStr | 98,652 QPS | 2,798,903 QPS | 96,561 QPS | 10422.1 MB |
HashDBMが更新200万QPSであることを考えると、セカンダリインデックスの性能は1桁や2桁も劣ることになるので、ミスマッチであるとも言える。とはいえ、HashDBMが早すぎるのであって、45万QPSで更新できるMemIndexも悪くはない。ファイル上のメインデータベースとオンメモリのセカンダリインデックスという組み合わせはそれなりに実用的だと思う。
マルチスレッド環境においてセカンダリインデックスとメインデータベースの整合性を保証するために、メインデータベースの更新時にコールバック関数を呼び出してセカンダリインデックスの更新を行うためのProcessというメソッドがある。このProcessメソッドはCompare-and-Swapとかアトミックな数値のインクリメントとかいった並列化の技法の基盤となる。
多相化とシャーディングのアダプタ
全てのDBM派生クラスを同じクラスとして扱うために、PolyDBMというクラスも用意されている。そのOpenメソッドに渡すパラメータによって内部で使われるクラスを切り替えたり、チューニングパラメータを設定したりすることができる。こんな感じで使う。
# ".tkh" なのでHashDBMが開かれる。
PolyDBM dbm;
dbm.Open("casket.tkh, true);
# 以後、使い方は全て同じ。
dbm.Set("Japan", "Tokyo");
std::cout << dbm.GetSimple("Japan") << std::endl;
dbm.Close();現時点でJavaとPythonとRubyのインターフェイスも提供しているが、それはこのPolyDBMのラッパーである。このアダプタクラスを介して、各種のDBM派生クラスのほぼ全ての機能を使うことができる。詳しいことは以前の記事を参照されたい。
さらに、複数のPolyDBMを内部に持ってシャーディングを行うShardDBMというクラスも提供される。これを使うと、全ての種類のデータベースをシャーディングすることができ、並列処理性能を劇的に向上させることができる。シャーディングをすると、HashDBMのスループットはSetは500万QPS以上、Getは600万QPS以上にも達する。詳しいことは前回の記事を参照されたい。Java等からもこの機能は利用できる。
その他のユーティリティ
おまけのユーティリティとして、Searchという関数群が提供されている。これはDBMの全てのレコードを探索して、条件が一致するキーのリストを取得するものだ。前方一致、中間一致、後方一致、正規表現に加えて、編集距離による曖昧検索も使える。順序つきデータベースに対する前方一致だけは順序を使った高速なアクセスを行うが、それ以外の条件では全探索が必要となるので遅い。とはいえコードの保守という意味では簡潔に書けるので利点がある。JavaやPythonやRubyからこの機能を呼び出す際には言語間の相互データ変換が一度に終わるので、性能上の利点もある。
同じヘッダファイルにはDBMの中身をTSVテキストやバイナリレコードリストとしてエクスポートしたりそれらをインポートする機能もある。データ移行の作業には便利だろう。キーだけをテキストとしてエクスポートする機能には別の用途もある。エクスポートしたキーのリストに対して上述した汎用検索機能を適用することができ、それはデータベース全体を読み込むよりも効率が良い。やっていることはfgrepやegrepやagrepと同じなのだが、これもやはり一撃で書けるのは大きな利点だ。この機能はJavaやPythonやRubyからも呼び出せる。
文字列の基本的な操作を行うユーティリティ関数群も提供されている。これらはDBMの機能と直接の関係はないのだが、関連するアプリケーションを書いたりテストを書いたりする際に自分で欲しくなりそうな機能が網羅してある。文字列のsplitとかjoinとか、文字列と数値の相互変換とか、UTF-8とUCS-32の変換とか、Java/Python/Rubyだと標準であるような機能でもC++だと自分で書かなければならないことがよくあるが、その作業を楽にしたい。
DBMの下層で使われるファイルを抽象化した実装もなかなか使える。これらを使うとスレッドセーフかつ並列なファイル入出力を簡単に実現できる。ここだけがOS依存の実装になっていて、UNIX系以外に移植する場合にはここにだけ注力すれば済むように企図している。一時ファイルの作成やディレクトリの再起的な削除などの便利機能も提供されている。
ハッシュデータベースを実装する際に必要なハッシュロックのユーティリティとか、ツリーデータベースを実装する際に必要な順序つきハッシュテーブルや二層LRUキャッシュといったコンテナとかも再利用可能なクラスとしてライブラリに収録している。
総じて、普通はもっと高水準な言語で実装するような面倒くさげな処理をC++の層でも実装しやすいように頑張っている。DBMの瞬発力を活かすために、その他のボトルネックを排除せねばならないことがあるからだ。そもそも私が15年以上前にDBMを作り始めたのは全文検索エンジンのストレージを作る必要があったからだが、このTkrzwを使ってもそれが簡単にできるようになっている。
ライセンスと開発体制
TkrzwはApacheライセンス2に基づいて公開されるオープンソースソフトウェアである。OSSで食っていくという夢は捨ててサラリーマンになったので、LGPL+商用ライセンスであるKyoto Cabinetとはうって変わって大人しい。というか、大人の事情で私は著作者であっても著作権者ではないという事態になっている。しかし、どのような状況下でもオープンな開発が続けられることを保証するのがOSS準拠のライセンスの最大の役割であり、誰が権利者であるかは些末な問題とも言える。法的なゴタゴタが起こる可能性を最小化して皆が平穏かつ生産的に暮らすには、この着地点が合理的であろう。
GitHubでリポジトリを公開しているので、最新の状況を知るにはそちらを参照いただきたい。GitHub上のコードは開発版という位置づけである。安定版はソースパッケージのディレクトリに置いてあるものなので、試すならまずそちらを利用いただきたい。
Kyoto Cabinetでは機能を増やしすぎたという反省があるので、Tkrzwではライブラリ本体の機能はあまり増やさない方針である。しかし、移植性は最大化したいと思っているので、その辺りはぜひ皆様の協力をいただきたいところだ。SolarisとかFreeBSDとかMac OS XとかのUNIX系は現状で動くはずだが、Linuxでしかテストしていないので、configureやMakefileの不備があるかもしれない。Win32系もそのうちサポートしたい。コミットするにはこちらの手順に基づいてCLAなる同意書にサインしなくちゃならないのでちょっと面倒だけども。
まとめ
DBMは、各種の情報処理の基盤となるデータ構造であるkey-valueの連想配列をファイル上で実現するライブラリである。仕様が単純な分、やたら高速に動作するのが特徴である。ファイルがファイルシステムのキャッシュに乗っている状態では、オンメモリの連想配列に匹敵するようなスループットが出せる。それ以上の規模の場合でも、計算量とストレージの性能に応じた最善のスループットが出る。典型的なユースケースとして、辞書検索とかユーザアカウントの管理といったことが挙げられるだろうが、それだけに留まらない多種多様のユースケースが考えられる。機械学習とかバイオインフォマティクスの現場でも使えるだろう。ルータに組み込んでテーブルを管理するのにも使えるだろう。セカンダリインデックスを駆使してRDB風に使うこともできる。
ユースケースに合わせたクラスを選択することが重要だ。ファイル上とメモリ上、順序なしと順序あり、そしてオンライン更新の有無というのが判断基準になる。機能的な必要性を満たすクラスの中で、最も性能特性の良いものを選ぶとよい。Tkrzwは単なるDBMではなく、DBMの集合なのだ。
TkrzwはC++言語のライブラリだが、JavaとPythonとRubyのインターフェイスも提供している。それらの言語から使うと言語間のオーバーヘッドに律速されるので100万QPSとかは出ないが、それでも十分に高速に動作する。連想配列の一種として考えると、JavaのHashMapやTreeMap、PythonのDictやOrderedDict、RubyのHashに比べて空間効率が格段に良いであろうTinyDBMやBabyDBMを使うだけでも便利だと思う。もちろんデータをファイル上で永続化できるHashDBMやTreeDBMが使えるのも便利だ。
ともかく、ちょっと遊んでみていただきたい。質問等があれがここにコメントを書いてくれてもいいし、hirarin@gmail.com にメールを送ってくれてもいい。もしあればバグ報告などもいただけると嬉しいし、こんなことに使ったよとか報告いただけると後学のためになる。
