Oliverの日記： 全文検索エンジン：Rast

RastはIPAの平成16年度オープンソフトウェア活用基盤整備事業の一環としてRubyを筆頭にいろいろなオープンソースの港であるNaClで開発されている全文検索エンジン。ライセンスはGPL2だ。特徴は：

• n-gram式で高精度
• コマンドラインのツールを含まない純粋なライブラリ
• C、Ruby, Perl, PHPのバインディングが存在
• APIはとてもシンプルで簡単に使える
• バックエンドはBerkley DBM

Slashcode的にはPerlバインディングが存在するのがポイントが高い。が、Berkley DBMがバックエンドということは排他処理の問題で実質的にNFSでindexを共有して複数のフロントエンドサーバーが並列に検索する処理分散の方法が取れないし、複数のサーバーからindexに書き込むというのはもっと危険だ。もし使うなら、Ruby APIでも使って、簡単な常駐型のXML-RPCサーバでも立てる必要アリ

最終的には約1万のストーリー、30万の日記、70万のコメントが検索対象になるので、パフォーマンス的には初期のIndex作成が現実的な時間で作成でき、検索と単エントリの登録とがまあまあの時間(0.5秒いないとか)でできればいい。

ベンチマークとしてはindexerの性能を見るために、日記エントリを1万個づつ登録していき、かかった時間とindexサイズを求め、同じ検索を成長していくindexにたいして発行した。

Rastの場合：

Journals indexing:

10000 entries: 2m39sec
+10000 entries: 7m24sec
========================
20000 entries: 10m06sec (117MB)
+10000 entries: 13m03sec
========================
30000 entries: 23m09sec (163MB)
+10000 entries: 24m12sec
========================
40000 entries: 47m21sec (206MB)
(中断)

Journals search "foo"
10000 entries 0.04sec (17hits)
20000 entries 0.03sec (34hits)
30000 entries 0.07sec-0.12sec (55hits)
40000 entries 0.07sec-0.13sec (75hits)

index成長率も検索時間の悪化も悪くはない感じだが、いかんせindex作成時間がエントリ数増加にともない激しく延びていくので、とてもじゃないが数十万の文書をindexする気になれない。1万のストーリーだけなら、APIのシンプルさからRastを使うのだがなぁ。

indexのチューニング

[Yappo (5920)]

C APIならrast_db_openのsync_threshold_charsの数値を変更することによって
パフォーマンスを上げる事が出来ます。（メモリ食いますが・・・）

Rast.pmなら

my $rast = Rast->open('/db', RAST_DB_RDWR, {sync_threshold_chars => 1000000});

等のように書けます。

他にもrast_merger_tを利用する事を前提としてindexを複数に分けるのも手です。
問題は検索時間が気になるのと、Rast.pmで実装されてない事でしょうか。

Re:indexのチューニング

[Oliver (4)]

アドバイスありがとうございます。sync_threshold_charsをデフォルトの10倍である100万にしたところ、index作成にかかる時間がほぼリニアに8分の1になりました。数が増えてくると、どんどん時間が延びるのは変わらないのですが、前のアリエナイ時間ではなく、なんとか初期作成だけ我慢して、がんばって一晩回すことができそうな時間になりました。あとで、更新したベンチマーク結果の日記を書きます。

index時間削減のために一定数のエントリごとにローカルなDBをつくって、rast_merger_tを使ってしまうと、結局、文書数に対してO(n)な検索性能になってしまうので、激しく躊躇します。かなりのオーバーヘッドがありますし、index管理の複雑度も劇的にアップするので、index作成時間の短縮よりも、統合不可な複数のリモートDBを扱う場面こそがrast_merger_tの活躍の場ですね。

Re:indexのチューニング

[Oliver (4)]

上のコメントを書きつつ、数十万エントリをindexする作業を実施してたんですが、一定のエントリ数を越えるとindex作成のスピードがガタっと落ちる感じです。sync_threshold_charsが100万でだいたい8万エントリを越えたあたりから、syncにかかる時間(?)が急激に延びた印象です。現在10万エントリ弱で320MBのメモリを食べていて、indexのサイズが433MBです。もしかして、indexの物理サイズが絡んでいるのかもしれません。詳しくは検証しませんが、とりあえず手元のテストDBに入ってる16万の日記エントリのindexを終わらせてみます。

N-gramの精度

[Anonymous Coward]

N-gramは再現率において分かち書きよりも有利ですが、精度はむしろ下がります。ですから、「Rastは再現率が高い」と言うべきです。