Tokyo CabinetのBDBを利用して、10年分くらいのわりとでかいシステムのCVSのリポジトリを検索するシステムを書きました。というか、Tokyo Cabinetを使うのと、MapReduceはバッチ処理なんだよ!と言いたいのが目的だったので、手段としてCVSのリポジトリを検索してみた感じ。
Tokyo CabinetのBDBはKey, ValueなんだけどKeyの重複を許してくれるのでKey, Valuesな集合です。しかもKeyをmemcmpみたいなので比較して順序付きの集合にしてくれる、かっこいいストレージです。
どんなデータ構造で作られた集合も、閲覧するにはいっつも線形に辿るので、線形にアクセスできるこれが大好きです。
今回の設計の自分に課した縛りは:
- cvsリポジトリのrcsを分析して、ある単語がaddされたりdeleteされたりしたリビジョンを検索するできるものを作る
- データベースは1ファイル
- 複数のデータベースをマージできる (バッチで小分けにあつめてきて、最後にマージしたい)
- Tokyo Cabinetを使う
一つのファイルで、単語や文書IDの管理も転置インデックスもすべてまかなうので、次のようなKeyにしました。
[クラス, データ].join("\0")
シンボルの文字列から数値への変換は's'で、その逆は'S'というクラスにします。数値は工夫するのがめんどくさかったので36進数(to_s(36))を使いました。文字列から番号への変換はintern()という操作で変換できるようになってます。
key = ['s', 'string'].join("\0"); value =10.to_s(36) key = ['S', 10.to_s(36)].join("\0"); value = "string"
文書情報は'd'、転置インデックスは'w'を用います。keyにいろんな情報を載せちゃいます。ずる。
逆にvalueはなんでも良いので、行内での出現位置を入れたけど使用せず。
key = ['w', 単語, ファイルパス, リビジョン, 'add'|'del'|'log', 行番号.to_s(36)].join("\0")
出てくる文字列はみんなintern()操作で圧縮します。本当は圧縮しない方が便利なんだけど、容量的に妥協してしまいました。
このようなデータ片をrcsを解析しながら単語を見つけてputしていくとインデックスが出来上がり。
ある単語について文書ID順がたくさん並んでいるデータ構造になっているので、andやorを効率よく実装できます。
...
と思ったんだけど、ある2単語のand検索において、それぞれ候補になるインデックスが大量にあるのに、andが成立する(つまり、同じ文書IDを持つ)ケースが非常に少ないとき、はずれのループが多くて時間がかかります。例えば"return"と"include"が同じ行にあるCのプログラムはなかなか見つからないけど、それぞれの候補は多いのです。なんかうまい方法あるのかな。バッチ処理なら時間かけてでも全部探すのもありなんだけど、インタラクティブな検索ではすぐに返事をしたいんだよね。とりあえず、いまは数千回ハズレを引いたらあきらめるようにしておきました。
だれか参考書下さいな!
