インフルエンザで休んだ影響で仕事が鬼のように溜まって消化不良のmikioです（こんな記事を書いている場合じゃない）。さて今回は、Tokyo Cabinetでリレーショナル風データベースを実現したテーブルデータベース（TCTDB）の実装について説明します。
SQLiteとの違いは？
SQLiteはアプリケーション組み込み型のSQL対応リレーショナルデータベースのライブラリです。TCのテーブルデータベースよりもはるかに高機能で、それでいて性能も大変優れています。いわゆるデスクトップアプリケーションに組み込むデータベースをお探しであれば、TCなんかではなく、断然SQLiteがおすすめです。
一方で、TCなどのDBMは、より単純なデータ操作をより高速に実行できるように設計および実装されています。典型的なユースケースとして、大規模Webサイトのアカウント管理や、データマイニングに伴う集計操作が挙げられます。ということで、そういった特定のユースケースではSQLiteよりも高い性能を示すことがTCTDBには期待されるわけですが、果たしてそうなのか、性能テストをしてみました。
a,b,c,d,eという5つのコラムを持つレコード群を100万件登録したデータベースを作ります。その構築にかかる時間と、それに対する検索にかかる時間を、SQLiteおよびTCTDBのそれぞれで測定してみます。各コラムは以下の条件を設定します。
- a : 文字列型。主キー。”00000001″ 〜 “01000000″ のシーケンシャルな値。
- b : 文字列型。インデックス有り。”00000001″ 〜 “01000000″ のシーケンシャルな値。
- c : 数値型。インデックス有り。”1″ 〜 “1000000″ のランダムな値。
- d : 文字列型。インデックスなし。”00000001″ 〜 “01000000″ のランダムな値。
- e : 数値型。インデックスなし。”1″ 〜 “1000000″ のシーケンシャルな値。
コラムaで主キーのインデックスの性能を計り、コラムbでB+木インデックスのシーケンシャルな更新性能を計り、コラムcでB+木インデックスのランダムな更新性能を計ります。コラムdとコラムeはオマケです。検索はコラムbの完全一致（SQLiteでは「=」、TCTDBではSTREQ）で行います。実際のテストプログラムはこちらです。TCのバージョンは1.4.2で、SQLiteのバージョンは3.4.2です。CPUが4コアXeonでメモリ8GBのマシンで実行したところ、以下の結果になりました。値は10回の試行の平均値（秒）です。
| write time | read time | file size | |
|---|---|---|---|
| SQLite | 45.562 (21948qps) | 47.713 (20958qps) | 92MB | TCTDB | 9.561 (104591qps) | 6.152 (162548qps) | 105MB (70+20+15) |
ということで、あくまでこのテストプログラムに限った話ではありますが、TCTDBはSQLiteの数倍の時間効率になることがわかりました。空間効率については、SQLiteの方が優れていることがわかりました。もちろん、スキーマやアクセスパターンやチューニングを変えればまた違う結果になるので、気になる方はテストプログラムをいじっていろいろ試してみてください。
余談ですが、SQLiteのamalgamationという最適化手法には驚きました。前処理で全部のソースコードを1ファイルに連結してからコンパイラにかけることで、通常のコンパイル単位をまたがった最適化を可能にするらしいのです。そしてそれだけ5〜10%も高速化するとのこと。そりゃいいと思ってTCでも試してみたのですが、B+木のwrite（tcbtest write casket 1000000）で1.3%、B+木のread（tcbtest read casket）で0.8%ほど高速化しました。5%は無理でしたが、それなりに効果はあるみたいですね。
データベースの構造
閑話休題。前回の記事でも述べましたが、TCTDBはTokyo Cabinetのハッシュデータベース（TCHDB）の上に実装され、主キーによってレコードを参照する操作が最も高速になるように仕上げられています。主キー以外のコラムによってレコードを参照する操作は補助的な位置づけで、コラムに対するインデックスはB+木データベース（TCBDB）の外部ファイルとして実装されています。
ハッシュデータベースでテーブルを表現するために、主キーをハッシュのキーとして、各キーに関連づけられた値としてコラムを直列化して記録しています。コラムはTCのユーティリティAPIにおけるマップ（TCMAP）として表現されます。マップの直列化にあたっては、キー（コラム名）と値の各々を直列化したバイト列 [ksiz:vsiz:kbuf:vbuf] をコラムの数だけ並べます。ksizはキーのサイズ、vsizは値のサイズ、kbufはキーの実体、vbufは値の実体です。ksizとvsizは固定長でなくBERエンコード風の可変長で表現することで領域を節約しています。
SQLiteなどのほとんどのリレーショナルデータベースでは、コラム名はデータベースのメタデータとしてのみ保持しますが、TCTDBではコラム名も各レコードに入れています。この方式だと空間効率の点でかなり不利になり、上記のテストでSQLiteよりサイズが大きくなった一因ともなっているわけですが、その反面、予めスキーマを定義する必要がなくなるとともに、レコード毎に異なるスキーマを持たせることが可能となります。この点では、リレーショナルデータベースというよりも、オブジェクトデータベースとかドキュメントデータベースとかいったモデルに近いと言えるかもしれません。
コラムにインデックスを張ると、本体のデータベースの名前に「.idx.xxxx.lex」もしくは「.idx.xxxx.dec」といった接尾辞をつけた名前の外部ファイルが作成されます。「xxxx」の部分はコラム名で、「lex」または「dec」は型が文字列の辞書順（lexical）か10進数の数値順（decimal）かによって決まります。なお、主キーは空文字列のコラムとして扱うことでインデックスを張ることができ、その場合は主キーに対する完全一致以外の演算子を高速化する効果があります。
レコード本体の管理とインデックスの管理はそれぞれTCHDBとTDBDBに任せるとして、レコード本体が更新された時にインデックスも更新するというのが、TCTDB層の仕事の半分と言っていいでしょう（残り半分は後述するクエリの処理です）。インデックスは、コラムの値をキーとして、その値のコラムを含むレコードの主キーを値としたデータベースです。ここでB+木データベースの重複キーを許す性質が生きてくるわけです。で、新規にレコードが追加された際には、そのレコードの各々のコラムに対して該当するインデックスを調べ、あればそれにtcbdbputdupでエントリの追記を行います。同じ理屈で、レコード本体が削除される際には、そのレコードの各々のコラムに対して該当するインデックスを調べ、コラムの値と主キーに対応するエントリを削除します。既存のレコードが更新される際には、先に削除処理を行ってから新規追加を行います。
TCHDBと同じくTCTDBにも圧縮オプションを指定することができます。TCTDBにはTCHDBよりも大きいレコードが格納される傾向にあるので圧縮し甲斐があるでしょうし、インデックスはB+木なのでページ毎の圧縮によって高い圧縮効率が期待できます。その他のチューニングオプションも全てTCHDBから引き継いでいます。また、キャッシュ設定はTCHDBとTCBDBの双方から引き継いでいます。
クエリオプティマイザ
TCTDBが検索クエリを処理する際には、クエリの内容に基づいてどの順番でインデックスを参照するかを判断するクエリオプティマイザが実行されます。オプティマイザといってもそんなに賢いものではなく、TCTDBではものすごく素朴な実装をしていて、以下のロジックになっています。
- クエリに含まれる条件指定の各々を巡回して、計算量が少なくなる条件指定を探す。すなわち、コラム名が一致し、型が一致し、B+木のカーソルジャンプができる条件を探す。
- 1の条件に当てはまれば、そのインデックスを使って、カーソルで探索範囲を限定しつつ、検索を行う。
- カーソル上の各々のレコードにその他の条件指定との合致を選択し、全て真なら採用する。
- 順序指定のコラム名と型がインデックスと同一ならば、採用順の昇順もしくは降順をそのまま結果集合の順序にする。
- 結果集合の要素数が最大取得数指定に達して、順序指定がないか、上記の順序採用が成立していれば、そこで探索を終了する。
- 1の条件に当てはまらなければ、クエリに含まれる条件指定の各々を巡回して、係数が小さくなる条件指定を探す。すなわち、コラム名が一致し、型が一致する条件を探す。
- 3の条件に当てはまれば、そのインデックスを使って先頭から末尾まで訪問しつつ、検索を行う。
- カーソル上の各々のレコードにその他の条件指定との合致を選択し、全て真なら採用する。
- 順序指定のコラム名と型がインデックスと同一ならば、採用順の昇順もしくは降順をそのまま結果集合の順序にする。
- 結果集合の要素数が最大取得数指定に達して、順序指定がないか、上記の順序採用が成立していれば、そこで探索を終了する。
- 3の条件に当てはまらなければ、クエリの順序指定に対してコラム名と型が一致するインデックスを探す。
- 5の条件に当てはまれば、そのインデックスを使って先頭から末尾まで訪問しつつ、検索を行う。
- カーソル上の各々のレコードに全ての条件指定との合致を選択し、全て真なら採用する。
- 結果集合の要素数が最大取得数指定に達すれば、そこで探索を終了する。
- 1,3,5のいずれの条件にもあてはまらなければ、本体のハッシュデータベースを使って先頭から末尾まで訪問しつつ、検索を行う。
- イテレータ上の各々のレコードに全ての条件指定との合致を選択し、全て真なら採用する。
- 結果集合の要素数が最大取得数指定に達して、順序指定がなければ、そこで探索を終了する。
- 順序指定があり、ここまでの手順で順序が決定していない場合、結果集合の並び替えを行う。
- 結果集合の各々の要素に対して順序指定のコラムの値を取り出して、メモリ上でクイックソートする。
- 結果集合の上位から、最大取得数の分だけの主キーを呼び出し側に返す。
一般的には、手順1,3,5をいかに賢くするかがオプティマイザの勝負どころなようですが、TCTDBの実装では、コラム名や型の一致と演算子の種類のみを見てインデックスの採否を決定しています。本来であればインデックスのカーディナリティ度が高いものを優先して採用すべきであり、カーディナリティ度が低すぎるものは採用すべきではありません。例えば、「性別が男（sex STREQ male）の人を若い順（age NUMASC）に取り出す」ことを考えてみましょう。インデックスはsexにもageにも張ってあるとします。もしここでsexのインデックスを採用した場合、値が2種類しかないので効果的に探索範囲を狭めることができません。そしてその手順で全体の半数のレコードを採用してしまい、最後にageでソートする際には、ハッシュデータベースを参照するためのI/O負荷やソートのための使用メモリおよびCPU時間が大変なことになってしまいます。したがって、インデックスごとに統計的な手法でカーディナリティを算出しメタデータとして持っておき、それが高いものから採用する方が賢いのかもしれません。
しかし、なぜそうしていないのかと言うと、面倒だからですね。カーディナリティ度が予めわかったからと言って個々のクエリに対する効果は実際に実行してみなければわからないので、割に合いません（男女の2種類であっても、男が圧倒的に少なければ男という条件にはインデックスを使うべき）。どの条件がどのくらいの該当数になるのかはアプリケーション層（ユーザ層）の知識がないと予測できないので、むしろアプリケーション側から指定できた方がいいんじゃないかと思った次第です。
ということで、クエリオブジェクトに追加（tcqdbqryaddcond）した順番でループを回して各インデックスとの合致をコラム名と型と演算子の種類のみで判定し、最初に合致したものを採用することにしています。アプリケーションプログラマやエンドユーザは、カーディナリティが高そうな（つまり効果的に絞り込めそうな）条件指定から先にクエリオブジェクトに追加することで、だいたい望ましい性能を得ることができます。また、条件指定ではなく順序指定でインデックスを使いたい場合には、全ての条件指定でインデックスを使わないオプション（TDBQCNOIDX）を演算子に付与することで順序指定のインデックスを優先させることができます。先ほどの例がまさにそうで、年齢のインデックスを先に引いて若い順にレコードを参照しつつ、男が最大取得件数分だけ出てきた段階で探索を終了すれば、本体のハッシュデータベースを引く回数は極小で済むし、ソートも必要なくなります（sexとageの複合インデックスを使うのが時間効率としては最高なわけですが、それはまた別の問題）。
アトミックな更新
TCTDBは、主キーを使ったレコードの操作（取得、更新、削除）の他に、任意のコラムをつかった検索ができます。SQL的に考えると、主キーを使ったSELECTとINSERTとDELETEができるのに加えて、任意のコラムを使ったSELECTができるということです。あれ、でも待てよ、任意のコラムを使ったREPLACEとDELETEもできないとまずいんじゃないか。SELECTしてから結果集合の各要素にREPLACEやDELETEを発行すれば同じようなことはできそうだけど、極小のアトミック性を確保するためにわざわざトランザクションを使うのはだるいんじゃないかと。
ということで、クエリを使った検索結果の各々に対して更新または削除の操作をアトミックに行える仕組みが用意してあります。クエリオブジェクトに加えて、結果集合の各々に対するコールバック関数を与えてメソッドを呼び出すことで、任意の更新処理を行うことができます。コールバック関数の戻り値によって、レコードを削除する（TDBQPOUT）か、更新する（TDBQPPUT）か、何もしない（0）かの後処理が実行されます。例えば20歳から29歳までの女子の給料を10000円増やす処理は以下のように実装できます。
int baseup(const void *pkbuf, int pksiz, TCMAP *cols, void *op){
const char *val = tcmapget2(cols, "sal");
if(!val) return 0;
char numbuf[32];
sprintf(numbuf, "%d", atoi(val) + atoi(op));
tcmapput2(cols, "sal", numbuf);
return TDBQPPUT;
}
int foo(void){
...
TDBQRY *qry = tctdbqrynew(tdb);
tctdbqryaddcond(qry, "age", TDBQCNUMBT, "20,29");
tctdbqryaddcond(qry, "sex", TDBQCSTREQ, "female");
tctdbqryproc(qry, baseup, "10000");
tctdbqrydel(qry);
...
}
これで、WHERE句に主キーの完全一致以外を指定したREPLACEやDELETEと同等の操作が行えるようになりました。MySQLのREPLACEとSQLiteのON CONFLICT句の両方のニーズが満たせるはずです。なお、単に該当のレコードを削除するのにいちいちコールバック関数を用意するのは面倒なので、tctdbqrysearchout(qry); だけで消せるようにもしています。
そういえば、参照と削除がアトミックにできるというという特徴は、キューを実現するのにぴったりですよね。キューの処理は以下のように実装するとよいでしょう。コールバック関数の中では、タスクの処理をするのではなく、タスクリストにコラムのデータを入れるだけにするのが重要です。なぜなら、コールバック関数の実行中は他のデータベース操作がブロックされるので、コールバック関数は一瞬で終わりたいからです。
int shifttasks(const void *pkbuf, int pksiz, TCMAP *cols, void *tasks){
// コラムのマップオブジェクトを複製
TCMAP *newcols = tcmapdup(cols);
// プライマリキーをダミーのコラムとして入れる
tcmapput(newcols, "", 0, pkbuf, pksiz);
// タスクリストに入れる
tclistpush(tasks, &newcols, sizeof(newcols));
// 取得したレコードの削除を指示する
return TDBQPOUT;
}
int bar(void){
...
// タスクリストの初期化
TCLIST *tasks = tclistnew();
// クエリ組み立て
TDBQRY *qry = tctdbqrynew(tdb);
tctdbqrysetorder(qry, "seq", TDBQONUMASC); // seqコラムの昇順に
tctdbqrysetmax(qry, 10); // 最大10件を取得
// クエリ実行
tctdbqryproc(qry, shifttasks, tasks);
// タスクの処理
for(int i = 0; i < tclistnum(tasks); i++){
TCMAP *cols = *(TCMAP **)tclistval2(tasks, i);
// コラムを参照しつつ何かする
const char *pkbuf = tcmapget2(cols, "");
printf("the primary key: %s\\n", pkbuf);
// コラムのリソースを破棄する
tcmapdel(cols);
}
// 後始末
tctdbqrydel(qry);
tclistdel(tasks);
...
}
上記ではseqというコラムにタスクの優先順位（格納した時間でOK）を入れていることを前提としていますが、プライマリキーやその他のコラムを使ってもよいでしょう。また、昇順でなく降順で取り出せばスタックとして使えます。
コード内に「ポインタポインタ」が出てきてしまっているので念のため補足しておきます。shifttasks関数の中でtclistpushでリストオブジェクトに入れているのは(TCMAP *)型の変数の領域なので、つまりその領域を指すポインタ(TCMAP **)を引数にしています。同じ理屈で、bar関数の中のtcmapget2では、(TCMAP **)が返されるので、その参照先である(TCMAP *)を先ほど複製したマップのポインタとして利用することができるのです。えーと、複雑ですね。スクリプト言語バインディングを使うともう少し直感的になると思います。
まとめ
Tokyo Cabinetのテーブルデータベースに関して、SQLiteと比較しつつ性能を評価するとともに、内部の実装について説明しました。繰り返しになりますが、プロセス組み込みのリレーショナルデータベースが欲しい場合は相変わらずSQLiteを使うのが便利だし効率的です。一方で、TCTDBは主にクライアント/サーバモデルにおけるサーバ側で使いやすいように作っています。サーバ側だったらMySQLだろと言われそうですが、サーバ側でプロセス組み込み型であるというニッチなニーズもないことはないのと、あとは性能の高さが存在意義なのかなと思います。
TCTDBを作りながら感じたのは、Hyper Estraierのデータベースとものすごく似た構造になってきたということです。これで文字N-gramインデックスをサポートしたら完全に全文検索システムとか文書管理システムになってしまいますね。作者が同じなのだから仕方ないのですが、楽観的なメモリの使い方とか素朴すぎるクエリオプティマイザとか、2年以上経ってもあまり進歩していません。並列性と64ビット環境を意識している点が違うといえば違いますが…。
次回は、いよいよTokyo Tyrantにテーブルデータベースを組み込む話をします。
