追記型MVCCで機能するB-treeによるインデックス

Koherent_DB

PerlShellKoherent::DBのインデックスがとりあえず機能するようになりました。

最初実装していた手法が正しく動作しないことに、かなり実装が進んでから気付いたのでずいぶん時間がかかってしまいました。単純なB-treeなら実装が簡単ですが、どうやって追記型MVCCと共存させ、トランザクションをサポートするかに苦労しました。

パフォーマンス

適当にしか計測してないですが、1件当たり80B（内データ部は50B）程度の小さめのデータで試したところ、インデックス付き（PKのみ）の書き込みが5〜6ms/件、100万件からのインデックス検索を用いた読み込みが5〜6ms/件程度でした。CPUがCore 2 Duo 1.8GHz、メモリが2.5GB、SATAのディスクのマシンを用いて計測しました。

今回計測したのはStandaloneモードという、常駐するDBサーバを用いずアクセスの度に設定等を読み込んで動作するモードです。ミューテックスがロックファイルで実現されていたり、1件書き込む度にインデックス情報を読み直したり（他プロセスがインデックスを作成しているかもしれないので）と、大量のディスクアクセスが発生しており、Pure Perlということも考えるとまあこんなもんかなという気がしています。プロファイラ*1で見てもディスクI/O関連のオーバーヘッドが大きいみたいなので、Client/Serverモードではもう少し高速化できると思います。

追記型MVCCインデックス

当初はインデックスのタプルもテーブルのタプル同様xminやxmaxを用いて管理しようと考えていました。しかし、この方法は実装が複雑な上に機能しないことに気付き、数日を無駄にした後にボツになりました。

具体的には次のような方法です。B-treeに1件データを挿入・削除する度に新しいノードを作成し、そのノードには一つ前の過去ノードへのポインタも記述しておきます。あるノードにアクセスするときは最新ノードから順にxmin・xmaxを検証し、現行トランザクションから可視なノードを拾い上げます。ノードは削除されることなく追記されるので、他トランザクションで削除されたけれどもコミットされていないノードを読み取ることもできます。

しかし、よく考えてみるとこの方法は機能しません。追記型MVCCでテーブルがうまく機能するのはデータごとにタプルが独立しているからです。インデックスの場合は、例えば枝数が100ほどあるB-treeを用いると、1件のデータの更新によって100件ものデータがロックされ他トランザクションから更新することができなくなってしまいます。さらに悪いことに、B-treeではノード挿入・削除時にノードが分割・統合されそれが親ノードへと伝播していくケースがあります。もし根ノードまで更新が伝播した場合、1件の更新・削除が他トランザクションからのあらゆるデータの更新・削除（同じく分割・統合が伝播する場合）を妨げる可能性があるということです。これではさすがに使い物になりません。

テーブルの全タプルを格納したB-tree

とはいえ、単純なB-treeでインデックスを実装するわけにはいきません。例えば、データ削除時にインデックスのB-treeからもデータを削除してしまうとコミット前に他トランザクションからもデータが見えなくなってしまいます。PerlShellKoherent::DBはトランザクションの分離レベルとしてSERIALIZABLEのみをサポートするため、このようなDIRTY READを許容するわけにはいきません。また、ロールバックをどう実装するのかという問題もあります。このように、単純なB-treeではトランザクションを扱うことができません。

そこで考えたのが、削除されたものも含めてすべてのテーブルのタプル（へのポインタ）を格納したB-treeを作成するという方法です*2。この方法は非常にシンプルなものです。データ削除時には何も行わず挿入時のみB-treeにデータを格納します。B-treeから検索するときはレンジスキャンを行い、範囲内のタプルの中からそのトランザクションで可視のもののみを拾い上げます。ただし、ノードが分割される際には元のノードを上書きするのではなく新たに2個のノードを追加する必要があります。これは、更新と参照が同時に行われた際にノード分割による参照データの欠如を防ぐための処置です。あるノードのデータは追記されるのみで削除されないため、更新と参照の同時実行が可能になるのです。

今後の予定

Client/Serverモードの実装やPODの作成なども行いたいのですが、とりあえずStandaloneモードだけでも動作するようになったので簡単なサンプルコードとモジュールをダウンロードできる形にして近日中に公開したいと思います。まだ実装しないといけない機能もあるので、目安は1週間程度でしょうか。

まとめ

インデックスの実装が完了し、動作するようになりました。近日中にPerlShellKoherent::DBを公開したいと思います。

インデックスのパフォーマンスを調べるために簡単なベンチマークをとってみたところ、100万件からの検索が平均5〜6ms程度で行えることがわかりました。これは、現在実装できているStandaloneモードでの結果であり、Client/Serverモードではより高速に動作すると思われます。

インデックスの実装に関しては、削除データも含めテーブルの全タプルを格納したB-treeを作成し、タプルの可視性判断はタプルに任せるという手法を用いました。

*1:Devel::NYTProfを使ったのですが、あまりの素晴らしさに感動しました。どこがボトルネックになっているのかをソースコード上で見ることができ、その呼び出し元をたどったり呼び出し元ごとの実行時間を見たりすることもできるので非常に対策を立てやすいです。今回も簡単に動作速度を3倍程度まで向上させることができました。

*2:もしかすると、DBの世界ではこういう手法は常識的なものかもしれませんが。