kiyoka.2012_04_23 RSSPLAIN

Related pages: !kiyoka.blog.list kiyoka.2012_04_26 !kiyoka.blog.2012_04
5555555555555555555555555555555555555555555555555555
5

[Sekka][KVS] distributed-trieを使って曖昧文字列検索実装してみた感想

5

 

5

曖昧文字列マッチングのindexをtrieにしたのだが、前よりもモッサリした感じになった。

5

 

5

以前のバージョン 1.0.x では、"Kanji"というクエリに対して、1.6MByte程度のインデックスがKVSから1回で返ってき

5

ていた。

5
 例
5
  MASTER::(ka)    ka ... kanji ... (1.6MByteもある)
5

 

5

今回のtrieを使ったバージョン 1.1.x (開発版) ではtrieのツリーを辿りながら、曖昧文字列マッチングをするという方式に変えた。

5

文字列の流さが10文字であれば、悪くて100回程度のKVSへのリクエストが飛ぶ可能性がある。

5
  例
5
  Master::Index::k     a$
5
  Master::Index::ka    n
5
  Master::Index::kan   j
5
  Master::Index::kanj  i$
5
  .
5
  .
5

 

5

良くなった点

5

登録が軽くなった。

5

ユーザー辞書に新規の語彙を追加した時にも重くならない。

5

read/writeのバランスが良くなった。

5

1.0.xでは辞書登録中は重くて10秒以上レスポンスが返ってこないことも多かったが、1.1.xでは辞書登録の影響はほんとんど無くなった。

5

1.0.xではインデックスの更新に、1.6MByteのwriteが発生することになるので、かなりDISK I/Oに負荷を掛けていたに違いない。

5

1.1.xでは小さいエントリを沢山細切れに書くようになる。writeの合間にreadも可能だ。

5

 

5

悪くなった点

5

変換レスポンスが悪くなった。

5

Tokyo Cabinetを使った時の体感的なレスポンスが悪くなった。

5

sekka-benchmarkコマンドでベンチマークを取ると3倍ほど速くなっているんだけど、それはベンチマークの方法が悪いということで…

5

Redisを使った時はほとんど劣化は無いような気がする。

5

 

5

辞書が大きくなった

5

辞書のリストア用TSVイメージであるSEKKA-JISYO.SMALL.tsvが223Mから381Mに増えた。

5

結果、redis-serverが消費するRAM容量が800MByteから1.4GByteに増えた。

5

redis-serverが消費する容量の増加具合が比例していない気もするが、Redisのkeyのインデックス分なのではないかと推測する。

5

KVSのエントリ数は 3873011件 から 11533536件 に増えた。エントリ数は約3倍だ。

5

 

5

改善案

5

1.0.x は Tokyo Cabinetが使うメモリ容量は64MByteだが、それを256Mや512Mくらいに設定してやれば、もしかしたら良いバランスに落ちつく可能性がある。

5

要はDISKのreadを適度に抑制してやる必要があるわけだ。

5

RedisはDISK I/Oが無いので高速なのは当然だが、メモリが大量にある人向けのオプションだなぁ。

5

自分はRedisを使うけど。

5

 

5

感想

5

なんかローカルにsekka-serverを立てる場合、良くなったのか悪くなったのかわからないなぁ。

5

多分、今回の変更でスケールアウトするようになったのは確実なのでそのあたりも調べてみたい。

5

しかしスケールアウトするといってもぴったりマッチするKVSも無いわけだが… (Redis Clusterか?)

5

うーん、何だか趣味の領域を脱出できてない気がする…

5

 

5

...comment disabled...