「全文検索エンジンgroongaを囲む夕べ #1」参加メモ

参加メモ:http://atnd.org/events/9234

全文検索エンジンgroongaについて

発表者: (有)未来検索ブラジル 末永 匡 a.k.a. グニャラくん

• 全文検索エンジンSenna
  • 2チャンネル検索のために作った
• Sennaの特徴(1)
  • 高速なインデックス更新
    • 参照ロックフリーなデータ構造を採用
    • データ更新時に検索を阻害しない
  • 2chの地震速報板をすぐに検索したい
    • 検索の速報性が重要。Twitterなど
    • TwitterはLuceneを使ってしまってへこんでいる
  • Sennaは全文検索「ライブラリ」
    • 転置インデックスをのみを更新
    • 本文、タイトル、作成者といった文書の情報を持たない
    • 文書情報はMySQLにやらせる
  • Tritonn MySQL + Senna
    • Sennaの利用≒Tritonnの利用
    • SQLを用いて全文検索ができた。全文検索、並び替え、グループ化、これらの組み合わせ
    • SELECT * FROM table1 WHERE MATCH(body) AGAINST('クエリ') AND last_update > '2010/01/31'
  • Tritonnのよいところ
    • MySQLの資産（人的にも物的にも）が使える
    • SQLを用いた柔軟なクエリが書ける
  • Tritonnの悪いところ
    • 更新が遅い！
    • 更新時に、検索スループットが悪い！
  • Tritoonの仕組み
    • MySQLのMyISAMの全文検索を置換
  • MyISAMとテーブルロック
    • 更新時テーブル単位でロックを行うため、更新スループットが低下。更新時の検索を阻害
    • Sennaの特徴と矛盾している
    • TritonnではSennaの設計特性を活かせなかった
• groonga *1
  • groongaの特徴
    • MyISAMに依存しない
    • 単体で動作
  • 文書情報の保存：カラムごとに保存
    • key-valueストアを並列に並べたイメージ
  • ベクターカラム(multiValued)
    • カラムの値として配列を保存できる
  • テーブルカラム
    • カラム値として、他のテーブルの行、もしくはその配列を保存できる
  • groonga単体で全文検索可能
  • プロトコル: HTTP GET, memcachedバイナリ, 独自、MessagePack(未実装)
  • クエリ言語
    • JavaScriptライクな文法
    • 結果はJSON(P)/XML/CSV
  • その他の特徴
    • ドリルダウン（ファセット）
    • ジオサーチ（地理情報検索）
    • サジェスト（検索キーワード候補の提案)
  • ドリルダウン
    • 検索結果を特定のカラムでグループ化。SQLでいうところのGROUP BY
    • ベクターカラムでも可能
  • ジオサーチ
    • ある地点からの距離計算
    • 楕円体としてキチンと計算している
    • 日本測地系／世界測地系両対応
    • インデックスを用いて高速に検索可能
  • サジェスト
    • ユーザの検索クエリログを収集
    • 上記ログを収集し、おすすめのクエリを提案する
    • 今収集するところは自分で作らないといけない。将来的には自動にできるかも。
    • 提案、訂正、補完
  • SQL経由で使いたい
    • groongaストレージエンジン = MySQL + groonga
    • textsearch_groonga = PostgreSQL + groonga
    • あとの発表おたのしみに
  • 複数プロセスでの利用
    • 複数スレッド・プロセスで共有可能。更新時はロックされる
    • MySQLで更新、groongaデーモン経由でHTTPで検索
  • 分散構成
    • 直接のソリューションは現在ない -> アプリケーション側で頑張る
    • Spider/VPエンジンなどと組み合わせればできるのではないかと考えている
  • 使い方 http://groonga.org/docs/
  • 導入事例
    • groongaデーモン 某Webサイトでのアイテム検索
    • groongaライブラリ(Ruby) 某番組情報サイトの検索、buzztter
  • 注意点
    • 64bit専用
    • ファイルディスクリプタMAXあげる
    • カラムごとに１ファイル
    • ネットワークサーバも兼用
    • 可変長カラムの空間効率には改善の余地がある
  • まとめ
    • Sennaの特徴である「高速な更新」を真に実現するために書かれた全文検索エンジンである
    • LGPL2.1 開発者、バグ報告募集中
• Q&A
  • Q.分散構成について。Spiderとの連携はどういう構成になるか？
  • A.Spiderの後ろにいるInnoDBをgroongaストレージエンジンに置き換える感じ。
  • Q.インデックスの分散はどうするの？
  • A.分散はSpiderが担当。groongaは分散されていることを意識しない。Spiderがわけたようにインデックスができあがる
  • Q.groonga自体が堅牢でも、ライブラリやOSの問題で異常終了したケースが想定される。その場合、InnoDBのような復旧システムはあるか？
  • A.更新中はいつ落ちても壊れるようになっているｗ ロックフリーな更新のために諦めている。元データは別で持っておくのが良いと思う。
  • Q.バインディングはどの程度？
  • A.作りたいけど手が回ってない。Rubyは結構できがいい。開発者募集中。HTTP経由ならどんな言語からでも簡単に使える
  • Q.データのオンラインバックアップは
  • A.更新してなければcpという素晴らしいコマンドで！ｗ　データのダンプ機能は持っている
  • Q.Sennaでファイルサイズが問題になっているがgroongaはどうか？
  • A.Sennaに比べて文書情報を保存する分ファイルサイズは大きくなる。転置インデックスのサイズはそれほど変わらない。

Ruby/groonga (rroonga/ActiveGroonga/Racknga) について

発表者: (株)クリアコード 須藤功平 (すとうこうへい)さん

• 趣味：フリーソフトウェア開発
  • RSS Parser　（Ruby標準添付)
  • Rabbit プレゼンソフト http://www.cozmixng.org/~rwiki/?cmd=view;name=Rabbit
  • Cutter C言語テストフレームワーク
  • milter manager
• ラングバプロジェクト　語感だけで意味はない
  • http://groonga.rubyforge.org/
  • 使いやすい検索システムを手早く、簡単に
    • 全文検索システム
    • ↑のコンポーネント
    • 独自の全文検索システム開発を支援
• 全文検索システム
  • クローラ
  • テキスト抽出
    • ChupaText
    • RubyバインディングはChupaRuby
  • インデクサ
  • エンジン
    • groonga
    • Rubyバインディング (rroonga)
  • インタフェース
    • RailsサポートActiveGroonga
    • Rackサポート+α:racknga(らくんが)あとで名前変えるかも
  • これらをまとめたものが文書検索ラングバ
• rroongaの紹介
  • groongaのRubyバインディング
  • groongaをライブラリとして使用(groongaクライアント機能はほぼない)
  • Rubyらしく書けることを重視。速さを落とさないように頑張っている
  • 便利な機能を盛り込む（例：スキーマ定義DSL）
• groonga APIレイヤー
  • QL-API: DB操作コマンド、ネットワークアクセス
  • DB-API: データベース、テーブル・カラム・型、手続き(Tokenizeなど)
  • LOW-LEVEL: ハッシュテーブル、パトリシアトライ、配列
  • rroongaのサポートはDB-APIをメインでサポート。QL-APIすこしサポート
• Rubyらしさ重視
  • DSL
  • カラムアクセス：メソッド
  • groonga <-> Ruby型変換
  • クエリ。名前に"mo"を含むユーザを全文検索

 users.select do |record|
   record.name =~ "mo"
 end

• • クエリ重み付け

 record.match(query) do |target|
   # titleにマッチしたらスコア100, descriptionにマッチしたらスコア10
   (target.title * 100) |
     (target.description * 10 ) |
     (target.content)
 end

• • • block内は一回だけ評価されるようにしている
  • rroongaをインストールするとgroongaも自動で入る
• 利用シーン
  • インデクサ。Rubyで加工しながらデータ追加
  • データベースメンテナンス。バッチ処理
  • groongaの挙動確認 irb -r groonga
  • テストデータ作成
• 利用例
  • るりまサーチ: rroonga + Rack
  • http://rurema.clear-code.com/
• ChupaText: 目標
  • 複数の入力形式を１つの操作方法で
  • chpatextコマンド。MIME形式で出力
  • どうしてMIME?
    • メタデータとテキストを扱える
    • メタデータ：ヘッダー（拡張可能）
    • テキスト：本文
    • 複数のファイルを扱える
    • アーカイブ対応
  • 拡張性
    • 入力処理部分をプラグイン化
    • プラグイン追加。Cで共有ライブラリを作るか、Rubyスクリプトを作るか
• ChupaRuby
  • HTTPインタフェース（予定）。テキスト抽出Webサービス
  • gemでインストールできるが、ChupaTextはインストールされない（ChupaTextのインストールは大変）
• ActiveGroonga
  • Rails3 用groongaモデル
  • 実装はrroonga + ActiveModel
  • ActiveGroonga::Base
  • rake groonga:*
  • マイグレーション、バリデーション、リレーション
• racknga
  • いれ場所こまった便利な物をいれている
• Q&A 聴き逃した。。。。

MySQL + groonga (groongaストレージエンジン) について

発表者: 住商情報システム(株) 池田徹郎さん

• groongaストレージエンジンとは
  • Tritonnの後継プロダクト。まだ置き換えるまでの品質まではいってない
  • MySQL 5.1/5.5 pluggable storage engine
• Tritonnのコンセプト
  • MySQLで全文検索を使えるようにする
    • MySQLのビルドインは、半角スペースで文章が区切られる言語圏のみ。日本語、中国語などがだめ
  • MySQLユーザのためのもの
  • 簡単に・シンプルに使えるもの
  • 安定して・安心して使えるもの
  • Tritonnのアーキテクチャ
  • Tritonn patchの規模
    • parser /execution layer 19ファイル、899行のパッチ
    • myisam storage engine 32ファイル、1306行のパッチ
  • MySQLの規模
    • 2393ファイル
    • 160万行 原稿用紙８万枚相当
    • これだけの規模のソースにパッチを当てるのは大変。
  • Tritonnの品質向上スキーム
    • オープンソースuserの使用＆フィードバック
    • MySQL,incのcertification test
  • MyISAM依存による限界
    • MySQLは１プロセス、マルチスレッドモデル
    • MyISAMではtable lock。検索に関しては共有ロック、更新は排他ロック
• groongaストレージエンジンのコンセプト
  • MySQL5.1+で全文検索を使えるようにする
  • MySQLユーザのためのもの + 柔軟性追加
  • 簡単に・シンプルに使えるもの
  • 安定して・安心して使えるもの
  • MyISAMから離脱、＋さらに高速化
• 公開場所 http://mroonga.github.com/ など
  • groongaストレージエンジンではDB-APIをつかって、MySQLのストレージエンジンを実装している
  • MySQL5.1　ソース／バイナリパッケージ配布中。MySQL5.5はソースからのみ
• Tandem構成
  • MySQL with groonga storage engineで作ったファイルを、rroongaや、groonga HTTP Serverから読み書きできる
• 仮想カラム
  • _id
    • groongaにおけるレコードの識別番号。
    • MySQLにはROW_IDの概念が存在しない（内部的にあるのみ）
  • _score
    • 全文検索のヒット時のスコア値
    • インタフェースがイケてない
    • メモリ節約のため
• 従来からのORDER BY LIMIT問題
  • 100万件のレコードから先頭の100件だけ取りたい場合
  • 検索条件とorder byで指定しているものが複合インデックスでマッチすると非常に早く動くが、そうでない場合遅い
  • インデックスでマッチしない場合、ヒットした大量レコードを全部読み込む処理が走る。これが遅い。キャッシュが足りないと他のキャッシュが追い出される
  • データを読んだ上でscore値に用いてソート
  • Row IDをもとにしたランダムアクセス。場合によってはここがほとんどを占める場合もある。
• ORDER BY LIMITの高速化
  • ストレージエンジンからクエリの情報が取れる
  • 全文検索＋スコア取得＋ソート＋LIMIT適用
  • LIMIT指定件数のみレコードの読み取る。ここが高速化されると大幅に早くなる
  • スコアに基づくROWIDソート
  • ROWIDしていによるレコード読み取り(LIMIT 100)
• その他実装済の高速化機能
  • カラムの刈りこみ
  • COUNT高速化
• 大規模分散検索対応
  • Spider Storage Engineとの連携で対応を予定している
• Current Development Status
  • 2010/11/29 ver0.4 alpha released
  • 近々betaになるかも
  • 開発者募集
  • [twitter:ikdttr]まで

MroongaとSpiderのコンビネーション（予定）

発表者: 斯波健徳さん

• スコアソートでの全文検索
  • Spider検索エンジンでは、最初の段階ではスコアの高いものがどこにあるかわからない
  • スコアでのソートの場合は、全パーティションに同じSQLが並列実行され、結果が返却される
  • １００件のデータが欲しい場合、例えば３箇所に分散している場合、それぞれから１００件ずつとる
  • そこで得られた３００件をSpider側でソートして返却する
• レンジパーティション条件でのソート
  • order by c1なら、c1が小さいパーティションから検索して、結果が指定した件数に揃った段階で返す
• パーティションの分割条件に沿った絞り込み
  • パーティション条件に沿った絞り込みを行った場合、必要なパーティションだけにアクセスできるので早くなる
• ここで質問。これらはまだ実装できていません。どれぐらいできて欲しいですか？
  • 会場挙手半数以上。頑張りますｗ

• Q&A
  • Q.最初scoreをつくっていなくて、後からつけたい場合は？
  • A.現状alter tableをサポートしていないので、create table時に作るしかない。ゆくゆくは対応予定
  • Q.他のテーブルとJOINした場合など、取得件数がたりなくなるケースなどは？
  • A.まだjoinには対応できていない。エンジン側で高速化ロジックが使えるかどうかを判定して、データが取得できないリスクがある場合は高速化ロジックを使わないなどの対応が考えられる
  • Q.複数カラムにまたがる全文インデックスの対応予定は？
  • A.groonga自体のマルチカラムインデックス対応が行われていない。groonga本体が対応すればgroongaストレージエンジンも対応する予定。
  • Q.NULL値を入れたら0になった
  • A.groongaではサポートできていない。設計時にはNULL値いらない方針だった？MySQLから使うにはあったほうがいいので再検討
  • Q.groongaストレージエンジンで、ベクターカラムのサポート予定は？
  • A.MySQLで持っているデータとのマッピングが難しいので、今のところノーアイデア
  • Q.mroongaという名前は使わないの？
  • A.時々使っている。別名として使ってください。

PostgreSQL + groonga (textsearch_groonga) について

発表者: フォルシア(株) 板垣貴裕さん

発表者資料：http://www.slideshare.net/ItagakiTakahiro/textsearch-groonga-v01

• textsearch_groonga
  • バージョン0.1をリリース
  • PostgreSQL 8.3, 8.4, 9.0, 9.1dev
  • groongaなるべく新しいもの
  • 基本的な検索機能をサポート
• 組み込みのtextsearch
  • textsearch_ja -> 組み込み機能 + Mecab
• 追加インデックス・アクセス・メソッド
  • textsearch_senna -> senna
  • textsearch_groonga -> groonga
    • N-gramのインデックス
• textsearch_ja 固有名詞やカタカナ連語の検索漏れが怖い
• SennaとPostgreSQLはもともとは相性がよかった -> PostgreSQL8.3の機能HOT更新と相性が悪いことが判明
  • Sennaは文書削除時にももとの文書が必要だったため
• PostgreSQLの拡張インタフェース
  • インデックスを拡張可能
  • やれることは限定的だが、拡張は容易。必要なのはハンドラ関数１０個程度
  • トランザクション管理は本体に任せられる
• 使い方
  • インストール
    • ソースからビルド。PGの開発用ヘッダ、ライブラリをインストール。makeで自動的にPGXSが使われる
    • データベースへの登録が必要 psql -f ...
  • インデックス作成
    • create index idx on t bl USING groonga (doc)
  • 検索
    • doc=キーワード - 比較演算子による検索
    • 単語検索 doc %% 'キーワード' - N-gramによる検索
    • doc @@ groonga.query('キーワード', '列と重み')
    • LIMITは悩ましい問題。多めを指定するとかリトライするとか
  • スコアリング
    • 行を識別するシステム列,tableoid, ctidを使って特定の行のスコアを取得
    • 行が更新されていると結果が0になることがある
• textsearch_senna vs textsearch_groonga
  • 利点
    • スコアリングやgrn_expr等の機能を活用できる
    • text型以外に、スカラー型（数値、日時）もサポート
    • マルチカラム・インデックスをサポート
  • 欠点
    • ディスク消費量が多い(文書をDBとgroongaの両方で持つ）
    • (将来対応予定)LIKE演算子をサポートしていない
    • (将来対応予定)インデックスをDROPした際にゴミが残る
  • 類似点
    • クラッシュ・リカバリやアーカイブ・リカバリは未対応
    • PG9.0のレプリケーションに未対応(Slony, pgpoolは可)
• ToDoと今後
  • LIKE演算子のサポート
    • textsearch_sennaで意外に人気の機能。LIKE "%foo%"とかでつくってしまった遅いアプリを後から救う
    • groongaにも機能はあるみたい？
      • UNIGRAM, BIGRAM, TRIGRAMの使い分けは？
      • 英数字も文字単位でインデックスするには？
  • PostgreSQLとの相性の向上
    • 適切なスコアを返すには？
    • DROP INDEXでgroongaデータも削除するには？
      • PostgreSQLハンドラにamdropを追加する？
    • トランザクションログと連携するには？
      • クラッシュリカバリは難しいかも
  • 標準SQLで仕様化されたストレージ・エンジン
    • PostgreSQL9.1に向けて開発中
    • groonga DBを、表として参照可能
    • 行志向のPG表と、列志向のgroonga表の使い分け
  • 標準SQLに含まれているのは参照処理のみ
  • この辺ができたらproongaを勝ち取りたい *2
• まとめ
  • 現在おためし版をリリース中
  • textsearch_sennaの良いところ／悪いところを踏まえて作った
  • SQL/MEDが大本命
• Q&A
  • Q.groongaのデータモデルとRDBMSのデータモデルはあわないので、フル実装は難しい。groongaを最大限に活かすのか、RDBMSの機能を残すのかどちらの方針か？
  • A.Postgresはmulti valueに対応する配列型を持っている。型サポートに関してはPostgresはフルサポート出来る見込み。
  • A.groongaストレージエンジンはMySQLから使えるのがうれしい。MySQLで頑張れるところはできるだけ頑張る。MySQLで頑張れ無いところはTandem構成で頑張る。UDF(User-Defined Function)を使いまくる。UDF動作するタイミングがレコード１件毎なので、その範囲ではいろいろ頑張れる
  • A.なにしてもいいなら、何でもしますよw 要望があれば頑張ります
  • Q.ORDER BY LIMIT, JOINしたときの問題にたいして、groongaからの解決案は？
  • A.Sphinx - MySQLのプロトコルを受け取って、自前で全文検索結果をかえすものがある。そういうことをやればいろいろ頑張れるかも。
  • A.MySQLの場合はJOINのときは各テーブルに分解されて呼ばれる。ただストレージエンジンではもとのSQLが取れるので、頑張ればできるかもしれない。今後の課題として少しずつ制限を解除していきたい
  • A.Postgresの対応は、地理情報検索でN近傍検索ができるようになる見込み。テキスト検索のスコアを、あるスコアからの距離として返すことで、LIMIT処理を一般化できるかも。
  • Q.性能限界は？
  • A.インデックスもデータ量も、容量が重要。１テーブルに30bitレコードしか保存できない

LT 三日で作るGroonga関数

[twitter:hotpepsi]さん

発表者資料：http://www.slideshare.net/firewood/groonga

• filterで呼べる関数を作る
• しょぼいサーバでスループットを上げたい
• 更新中も処理をとめたくない
• 親子関係を持つテーブルから子のテーブルを探したい
• 具体的には商品(1), 在庫・価格(n)
• SQLの場合、JOINしてDISTINCT ? groongaの場合素直にできない
• 親のIDでドリルダウンすれば２度引きで可能
• 子テーブルで検索する
• 重複するキーをfilterで捨てる
• filterで使える関数を自作する
• 自作の関数
  • 引数として親のキーを取る。
  • 格納済かどうかを返す
• 雛形
  • testになるstrlen.cを参照して書く
  • とりあえずproc.cに登録
• 正式なやり方
  • configure.ac
  • autoreconf
  • 大変なので省略
• 手抜き
  • Makefile.in
  • .SUFFIXESに.ccを追加
  • CCLD g++に書き換える
• groonga関数意外と簡単につくれます

*1:Sennaとう名前はSEO的に良くなかった

*2:Pは敵が多いので早めに