データベースライブラリTkrzwは追記型データベースをサポートしているが、それを応用したら転置インデックスの作成が効率的に行えるのか、考えてみた。
転置インデックスのおさらい
いわゆるDBMとかkey-valueストレージとか呼ばれる方式のストレージシステムでは、任意のキーに任意の値を紐づけて保存することができる。それを用いて、単語に対してそれが出現する文書のIDのリストを保存したものが転置インデックスである。転置インデックスを作るにあたっては、検索対象となる全文書をスキャンしながら、出現した単語をキーにしたレコードに文書IDを追記していくことになる。
IDが1の文書を読んでいる時にaという単語があったなら、"a"というキーに"1"という値を持たせたレコードを記録する。実際には値は何らかのバイナリ表現にするだろう。その後にIDが2の文書を読んでいる時にaという単語があったなら、"a"というキーに"1,2"という値を記録することになる。それをやるには、キー"a"の既存のレコードを読み込んで、古い値に末尾に"2"を追加したバイナリ表現を作り、それを記録する。この操作をRMW（Read-Modify-Write）と呼ぶこともある。この処理は計算量がO(N^2)になってしまうので、スケールしない。
オンメモリのバッファを使うと、これを軽減できる。メモリ上の連想配列を使って、各レコードの末尾に文書IDを足していくのだ。Tkrzwのオンメモリデータベースクラス（TinyDBMとBabyDBM）にはAppendというメソッドがあり、それを効率的に行ってくれる。値のメモリのサイズが一定を超えるとメモリ確保を倍々のサイズでやるので、N回のAppendの償却計算量はO(N)になる。
メモリ容量には制限があるので、オンメモリのバッファはいつかファイルに書き出すフラッシュ処理を行わねばならない。その際にHashDBMのAppendを使えば簡単だが、単一のファイルにAppendを繰り返すフラッシュ処理の回数Nに対してO(N^2)になってしまい、根本的な解決にならない。よって、フラッシュ処理毎にファイルを分けるのが普通だ。その際に、HashDBMではなくSkipDBMを使うとよい。いわゆるSSTableと同じくスキップリストであるSkipDBMは、ヒープ配列を使ってマージ処理を効率的に行ってくれる。空のデータベースにMergeSkipDatabaseというメソッドを繰り返し呼べばいいだけだ。マージ処理はコマンドライン一発でもできる。
検索エンジンと呼ばれるほとんどのシステムは、だいたい上記の戦略を踏襲しているだろう。単体マシンで動くオープンソースのものでも、大企業の地球規模のものでも、MapしてSortしてReduceしたデータをkey-valueストレージに記録しているという点で同じだ。検索エンジンだけではなく、そこそこの規模のデータ処理をするならこの方法を身につけておいて損はない。自前のKindle用英和辞書を作るのにも使っていたりする。
HashDBMの追記モード
転置インデックスはMapReduce的なバッファリングをした上でソートされた結果をスキップリストに保存することで構築するのが最善であるという答えはもう出ていて、それ以上に効率的な方法はない。とはいえ、スキップリストの部分を追記型のハッシュデータベースに替えるという代替案もある。
HashDBMを追記モードで作成すると、レコードの更新操作ログが全てデータベースに追記され、その個々のキーの最新ログの結果を値として提示することでデータベースとして機能させる。つまり、キー"a"の値を"1,2,3,4"にSetした後に、同じキーの値を"5,6,7"にしたなら、"a:Set:1,2,3,4"みたいなデータと、"a:Set:5,6,7"みたいなデータの両方がファイルに記録される。Getした際には最も後ろにあるものが検索され、最新の値である"5,6,7"が返される。
ここで気づくのは、過去のSetの結果も全て返せば、Appendしているのと同じ結果になるということだ。Appendと違ってSetの計算量はO(1)で済む（呼び出し回数Nに対してO(N)で済む）ので、単一のデータベースだけで転置インデックスの構築ができ、構築だけならめっちゃスケールする。ただし、過去の更新ログのリストを取得するTraceAllHistory的なメソッドの計算量はフラッシュ処理の回数に対してO(N)になってしまうので、構築は効率的だが、検索処理はあんまり効率的ではないシステムになるだろう。
これが嬉しいユースケースはあるだろうか。無理やり考えるなら、検索結果にリアルタイム性が必要で、にもかかわらず最新データをメモリ上ではなくストレージ上に持っていたい場合だろうか。個人のPCのファイル検索システムとか、個人サイトのブログ記事の検索システムとかを想定しよう。文書（記事）が更新された直後には、それが検索対象に加わっていて欲しい。よって、文書が更新される度に転置インデックスを更新したくなるが、過去の文書の量がそれなりにある場合、インデックス全体を更新していたら時間がかかりすぎる。したがって、全部の文書を対象とするインデックスは1日に1回とか1週間に1回とかの頻度で定期的に更新し、それとは別に最新の記事だけを対象にした小さい「ホットインデックス」を管理する。全体を対象にしたインデックスは普通にSkipDBMで作るとして、ホットインデックスは追記モードのHashDBMで作ると楽かもしれない。
ホットインデックスの構築と検索
小さいインデックスは、10分に1回のバッチ処理で更新されることとしよう。前回の更新の後に更新された文書IDのリストはGetNewDocumentIdsという関数が返し、各々の文書に含まれる単語のリストはGetWordListという関数が返してくれるとしよう。それをインデックスに反映するコードは以下のようになる。
// Builds the cache.
tkrzw::BabyDBM cache;
const auto& doc_ids = GetDocIds()
for (const auto& doc_id : doc_ids) {
const auto& words = GetWordList();
for (const auto& word : words) {
cache.Append(word, doc_id, ",").OrDie();
}
}
// Writes the cache content into the database file.
tkrzw::HashDBM dbm;
tkrzw::HashDBM::TuningParameters params;
params.update_mode = tkrzw::HashDBM::UPDATE_APPENDING;
dbm.OpenAdvanced("hot_index.tkh", true, params).OrDie();
auto iter = cache.MakeIterator();
iter->First();
std::string key, value;
while (iter->Get(&key, &value) == tkrzw::Status::SUCCESS) {
dbm.Set(key, value).OrDie();
iter->Next();
}
dbm.Close().OrDie();バッチ内の全ての文書のデータをキャッシュ内で結合してから、それをデータベースに吐き出している。ここで興味深いのは、インデックスをSetメソッドで更新していることだ。Setメソッドは既存の値を上書きしてしまう。しかし、追記モードの場合はこれでいいのだ。
このインデックスを検索する際には、レコードの過去の値も取り出せねばならない。そのための専用のメソッドとして、Traceというメソッドを用意しよう。キーを渡すと、そのキーに対するSetで渡された値のリストを返す。それを使って検索をするコードは以下のようになる。
// Searches the hot database.
tkrzw::HashDBM dbm;
dbm.Open("hot_index.tkh", false).OrDie();
const auto& history = dbm.Trace("foo");
for (const auto& concat_value : history) {
const auto& values = tkrzw::StrSplit(concat_value, ",");
for (const auto& value : values) {
std::cout << value << std::endl;
}
}
dbm.Close().OrDie();
ホットインデックスの実運用
ホットインデックスは、メインインデックスが作成開始されてから現在の間までに更新された文書の情報を蓄積する。検索処理はメインインデックスとホットインデックスの両方に対して行って、結果の和集合をとることでなされる。
実は、もうちょい話は複雑だ。メインインデックスの構築には数時間かかるとする。構築中のメインインデックスは使えないので、構築処理が行われている間は一世代前のインデックスと、それとペアとなる一世代前のホットインデックスがユーザには提供される。インデックス構築中にも文書は更新されるが、その情報は最新のホットインデックスに格納される。ということは、実際の検索処理は、一世代前のメインインデックスと一世代前のホットインデックスと、現世代のホットインデックスの全てを検索して、その結果の和集合をとることでなされる。そうすれば最新の情報が常に検索対象になる。現世代のメインインデックスの構築が完了したら、旧世代のメインインデックスとホットインデックスは消去してよい。
なんか面倒くさそうだが、ちゃんと実装すれば普通に動くだろう。ホットインデックスの検索の時間計算量はバッチ処理の回数Nに対してO(N)であるが、バッチ処理の回数は定数なので、O(1)であるとも言える。10分に1回なら、1日に144回なので、大したことはない。ホットインデックスの更新はめちゃくちゃ速いはずだ。個々のレコードで、ファイルの末尾にデータを書いてハッシュ表を更新するだけだから。つまり、検索処理の頻度はあまり高くないが、更新処理の頻度が高い場合には、この方法が向いている。
個別ファイルという代替案
ホットインデックスを複数のファイルに分けてしまえば、追記モードの特殊な機能を使わないでもいい。10分に1回、ホットインデックスのバッチ処理が始まった時刻の日付をファイル名にして、別々のファイルを作っていけばいい。検索時には、メインインデックスと、その更新処理が始まった以後の全てのホットインデックスを検索して、その結果の和集合をとればいい。
この方法でも検索処理の計算量は同じであり、バッチ処理の回数Nに対してO(N)であり、それは定数なのでO(1)と言い張れる。ただ、実際の計算負荷はより大きくなる。存在しない単語を検索した場合、追記方式では、ハッシュ表を1回引いただけでそれが存在しないことを突き止めて処理が終了する。個別ファイル方式の場合は、個別のファイルのハッシュ表を全て引いて回らねばならない。全てのバッチで出てくるような頻出語を検索した場合、追記方式では、ハッシュ表を1回引いてから、バッチ回数分に分かれた連結リストを辿る。個別ファイル方式では、ハッシュ表を引いてから連結リストを辿るというペアの処理をバッチ回数の分だけ行う。
正直なところ、文書検索システムくらいなら、個別ファイル方式で十分だと思う。何より、わかりやすい。そもそもここで検討しているのはマシン1台でお手軽に検索システムを構築する話であり、検索処理の負荷がべらぼうに高いようなことは想定していない。よって、おそらく追記方式の方が2倍くらい効率的だとは思うけれど、特殊なメソッドを追加してまでやることじゃない気がする。
その他の想定ユースケース
ローカルの文書検索システム以外だと、イベントログの検索とか、それを使ったモニタリングシステムとかにも追記方式のホットインデックスは使えると思う。この話はGitHubのスレで相談されたから考えたのだが、そのユースケースはイベントログの検索に近いものだった。一般化すると、巨大なアドレス空間で個々のアドレスに紐づけられた更新ログを低負荷で記録したい場合にこの手法は便利だ。
唐突だが、昭和生まれなら子供時代に「海戦ゲーム」をやったことがある人も多かろう。方眼紙に規定数の軍艦を書いておいてから、相手の空間の座標を指定して爆撃するのをターン制で繰り返すものだ。指定された座標に艦影が重なっていたら「命中」と報告し、艦影と隣接していたら「水しぶき」などと報告する。似たようなルールの「ネイビーブルー」というゲームボーイソフトもあった。仮にこれを1万行*1万列で1億セルのフィールドで表現するゲームを実装したなら、各セルの現在の状態の記録にハッシュデータベースを使うのは率直な方法だろう。ここで、とある海域の過去の状態を遡って見るという機能を実装したい場合、任意のセルの過去の状態を調べられるのは便利だ。そんなゲームが面白いのかどうかは知らないけど。
一般化すると、スパースなキーのデータベースを管理していて、各レコードの更新履歴が必要で、しかし過去の状態をレコードの内容として累積的に追加したくない場合、追記型データベースのTrace機能は有用なはずだ。とはいえ、その機能はまだ実装していない。要望があれば考えようかと思っていたが、特に強い要望でもなさそうなので、今のところ保留かな。
まとめ
追記型データベースは過去の状態を遡って取り出せるので、個別のレコードの過去の値も知ることができる。現状でその機能を公開するAPIはないのだが、あったらどんな利便性があるのか検討してみた。更新は早いが検索はちょっと遅いという特性になるので、リアルタイム性が必要なイベントログの管理とか、文書検索システムのインデックスの管理とかに使えそうだ。とはいえ、それで嬉しい人が一人でもいるのだろうか。
