パスワードを忘れた? アカウント作成
569869 journal

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

日記 by Oliver

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を使うのだがなぁ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Yappo (5920) on 2005年05月30日 19時12分 (#743342) 日記
    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で実装されてない事でしょうか。
    • アドバイスありがとうございます。sync_threshold_charsをデフォルトの10倍である100万にしたところ、index作成にかかる時間がほぼリニアに8分の1になりました。数が増えてくると、どんどん時間が延びるのは変わらないのですが、前のアリエナイ時間ではなく、なんとか初期作成だけ我慢して、がんばって一晩回すことができそうな時間になりました。あとで、更新したベンチマーク結果の日記を書きます。

      index時間削減のために一定数のエントリごとにローカルなDBをつくって、rast_merger_tを使ってしまうと、結局、文書数に対してO(n)な検索性能になってしまうので、激しく躊躇します。かなりのオーバーヘッドがありますし、index管理の複雑度も劇的にアップするので、index作成時間の短縮よりも、統合不可な複数のリモートDBを扱う場面こそがrast_merger_tの活躍の場ですね。
      親コメント
      • 上のコメントを書きつつ、数十万エントリをindexする作業を実施してたんですが、一定のエントリ数を越えるとindex作成のスピードがガタっと落ちる感じです。sync_threshold_charsが100万でだいたい8万エントリを越えたあたりから、syncにかかる時間(?)が急激に延びた印象です。現在10万エントリ弱で320MBのメモリを食べていて、indexのサイズが433MBです。もしかして、indexの物理サイズが絡んでいるのかもしれません。詳しくは検証しませんが、とりあえず手元のテストDBに入ってる16万の日記エントリのindexを終わらせてみます。
        親コメント
  • by Anonymous Coward on 2005年05月29日 17時28分 (#742885)
    N-gramは再現率において分かち書きよりも有利ですが、精度はむしろ下がります。ですから、「Rastは再現率が高い」と言うべきです。
typodupeerror

私はプログラマです。1040 formに私の職業としてそう書いています -- Ken Thompson

読み込み中...