軽量なインデックス機構を用いた全文検索ツールの高速化の検討
このエントリは、第6回 Web System Architecture 研究会 (WSA研)の予稿です。
概要
コマンドラインによる全文検索ツールの検索速度は、キャッシュ機構、並列化や効率的なアルゴリズムの導入によって高速化が図られている。一方で、これらのツールは、検索対象の変更や削除への追従を避けるためインデックスの採用を行なっておらず、都度検索対象に対して全探索を行う。
全文検索ツールに対するインデックス機構の課題を整理、解決し、インデックス機構を採用することができれば、検索対象を限定した、より高速な検索が可能になると考えられることから、本稿では、軽量なインデックス機構を用いた全文検索ツールの高速化の検討を行う。
提案手法では、インデックス機構に計算量と情報量の観点で効率的に扱うことのできるブルームフィルタを採用する。 まず全ての検索対象に対してブルームフィルタを作成し、結合・転置した軽量なインデックスを生成する。 次に検索対象へのクエリを行う前にインデックスから候補を取得し、全文検索ツールがこれを検索する。 検索対象の変更や削除への追従に対しては、インデックスを都度再生成する方式を採用するが、生成の高速化により利用者が負担とすることなくこれを行える。
評価では、提案手法を組み合わせることで、全文検索ツールの検索時間が短縮することを確認する。
発表スライド
提案手法のアーキテクチャ、ならびに具体的な実装であるmonochromegane/sifterとこれによる軽量・高速・汎用性についての評価は発表スライドを参照のこと。
まとめ
本研究会では軽量なインデックス機構を用いた全文検索ツールの高速化の検討とその参考実装を評価した。 インデックス機構としてブルームフィルタを用いることで少ないメモリ使用量と問い合わせの高速化が達成でき、インデックス操作のツールに分離することで任意の全文検索ツールとの連携による汎用性を備えることができた。 結果として、評価では全文検索ツールとの組み合わせにおいて大幅な検索時間の短縮を確認した。
一方で、インデックス構築時間の長さを解消することは、利用者にとっての負担の改善の観点から最優先で取り組まなければならない。 ブルームフィルタにおけるハッシュ関数のボトルネックは多く研究されていることから、これを取り込むこと、また、ハッシュ関数の実行回数を減らしながら精度を保つことができるような効率的なトークン化を調べる必要がある。 実装面ではハッシュ関数の結果は再利用できるため、キャッシュ機構の導入も効果があると考える。
今後は問い合わせ自体にオーバーヘッドが発生するようなアーキテクチャとの連携も検討し、Webシステムの分野へ研究を発展させたい。
発表を終えて
今回のWSA研は初のリモート開催で新しい顔ぶれも揃い、6回目ながらに新鮮な気持ちで楽しめた。 自身の発表でも、あまり気負いすぎずに頭の中で温めていたアイディアを形にして議論として発展できればいいなぐらいで臨んだ。 結果的に、まずは発表に向けて形にして評価することで長所短所が明確になり、参加者から新しいアイディアのヒントをもらうことができた。 特に、これまでプラチナサーチャーでの全文検索の高速化は、システムコールやバッファ確保の効率化やタスクの並列化といったプログラミングの実装面でのアプローチがほとんどであったため、アルゴリズムの観点からの取り組むためのとっかかりを色々議論できたと思う。 この分野は先人の知恵が大量にある分野なので、色々勉強しつつプラチナサーチャーの進化系も考えていきたい（研究会終わった後の夜中に考えていた方法がSuffix Trieと同じだと気づいて、巨人の肩に乗るべく、まずは高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)を注文した）
このような普段の研究から少し離れた取り組みであっても、定期的に発表を促されることで形にすることができるのはとても大切で、やりっぱなし学びっぱなしではなく一つの区切りまで考え実装することで次回以降の研究への糧となる。 Webシステムアーキテクチャに関する運用知見を研究的アプローチで前進させること興味がある方は次回開催の参加を検討してみてはいかがでしょうか。
＊次回は9月の後半のようです。
