ぱぱネット（仮）

_ [開発][Linux] Tokyo Cabinet / Tyrantで遊ぶ(4)

TC/TTの勉強がてら、2chの過去ログ検索システム(1投稿毎)を作るつもりだったのに、 なんかメチャクチャハマっとるぱぱんだです。こんにちは。

とにかく Q-GRAMの登録処理が遅い というのが前回までのあらすじ。 現象面からの洞察や、仕様書に書いてある最適化はやり尽くした感があるので、 もうソースを読むしかない。

_ [開発][Linux] モコモコ穴堀り

手打ちプロファイルにより、*.qgrファイルを更新する関数を調べる。 tctdbput()->tctdbidxputqgram()->tctdbidxsyncicc()と処理を追っていと...

tctdbidxsyncicc()関数内の

for(int i = 0; i < knum; i++){
   ...
   const char *vbuf = tcmapget(cc, kbuf, ksiz, &vsiz); //*T1
   if(vsiz > 0 && !tcbdbputcat(db, kbuf, ksiz, vbuf, vsiz)) //*T2
   tcmapout(cc, kbuf, ksiz); //*T3
 }

で時間の大半を消費していた。どうもQ-GRAMインデックス(を格納するB+木)を ディスクにフラッシュする部分のようだ。上記の関数のそれぞれの実行時間の合計を 洗い出すと、特にtcbdbputcat()の処理時間が多い。手持ちの2chのdatだと 18万件登録する頃には、もう 1投稿処理するのに1秒超えてしまう ....使い物にならない。

DELAY: tctdbput() = 1 . 178601
       t1 = 0 . 10234
       t2 = 1 . 137749
       t3 = 0 . 13995
       t4 = 0 . 0

でも、これが全キーワードの追加時に1秒超えるのではなくて、極々 特定のキーワードのみ のようなんですよ...... なんかピンときた ので、 スクリプトdumpbtree.plを作った。 これはB+木の、各キーワードと、キーワードごとの値の長さ (この場合は転置インデックスのバイナリが入っているのでバイト長)をダンプする。出力を

$ perl dumpbtree.pl test.tct.idx.6.qgr > qgram1
$ sort -n < qgram1 > qgram2
$ tail qgram2

とかするとバイト長のランキングがとれるわけだ。

304128 います
390504 た。
398256 した。
432816 ました
437760 です。
443232 ます。
758688 す。
2399688 。

えー？！句読点や記号を 正規化の段階で省かない のか....んーmikio wareがそんな基本を 忘れるはずがないので、たぶん検索精度か何かの問題でわざと入れてるだろう。

B+木はキーでサーチしたリーフにどんどん値をコンバインできるのだが、 いくらなんでもこれが入ったらまずかろう。今までのリーフ内メンバ数の調整なんて、こいつがメモリキャッシュに入ってきたら全部オジャンじゃん.....しかも書き足したら書き出す必要がある＝ディスクにアクセスする、という悪循環。

尚、「。」を含めた上位100傑を取り除いた全体の分布はこうなる。 横軸が単語ごと、縦軸がバイト長(ソート済み)ね。壮絶に偏るなあ...

別に2ちゃんねるの文章が飛び抜けて特殊なわけではなく、対象文章がちょっと多ければ、いずれ同じ問題にブチ当たると思う。つまり現状のTCのQ-GRAMは、本当に個人ブログの文章のみなど、文字の組み合わせが少ない場合にしか使えないということだね。

まあ、たぶん.....掲示板などの文字の組み合わせが膨大になる場合は Tokyo Distopiaつかえってことだな。 でもこれ、ツンツン過ぎて俺のような素人には辛いぞ！