@m_seki の

I like ruby tooから引っ越し

Tokyo Cabinetを使った検索システムごっこ

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のプログラムはなかなか見つからないけど、それぞれの候補は多いのです。なんかうまい方法あるのかな。バッチ処理なら時間かけてでも全部探すのもありなんだけど、インタラクティブな検索ではすぐに返事をしたいんだよね。とりあえず、いまは数千回ハズレを引いたらあきらめるようにしておきました。

だれか参考書下さいな!