2011/12/05

「全文検索エンジンgroongaを囲む夕べ2」 に参加した


イベントのページはこちら
http://atnd.org/events/20446
会場は前回は六本木のgree、今回は渋谷のVOYAGE GROUP(旧ECナビ)。
前回(初回)は一年前のいい肉の日 2011/11/29 も参加したんだけど、
当時子供が生まれたばかりで風呂当番だったので門限があって
途中退出せざるを得ず、もったいないことした。
今年は嫁の了解をもらってフルで参加できた。


全部は理解できていない気がするけど、必死にメモったのでせっかくなので晒す。
「ブログ書くのは自分のため」とdankogai氏も言ってたしネ。
(間違いを見つけた方はお手すきならコメントください。)




■groongaってそもそもなに?

話し手:クリアコード須藤さん

・groongaの利点最大は即時更新
・類似ソリューションのほうが機能の充実している場合が多い

groongaの全体像

groonga
libgroonga
DB API
rroonga
Rubyによる実装
1.3.0リリースしたよ!パチパチ
mroonga
MySQLストレージエンジンとしての実装
1.10リリースしたよ!パチパチ
クエリAPI
goongaコマンド
httpで使えるよ
nroonga
node.jsによる実装
w/ PostgreSQL
ハイブリッドだよ

スライドはgroongaのメーリングリストに資料あり


■groongaのこれまでと今後

話し手:groonga創始者の森さん

これまで

開発経緯
2005年Sennaリリース
2chの検索をするために開発
索引の動的構築
カラムストア機能追加

動的構築とは
検索エンジンとしては当時斜め上

静的構築と動的構築
作業領域の大きさが違う
検索可能な状態を維持しながらかどうか
技術情報「検索エンジンはいかにして動くのか?
類似品注意「検索エンジンはなぜ見つけるのか

カラムストア機能追加
列単位でのデータ格納
集計処理が得意
圧縮効率が高い

現在

最近の動向
静的構築の追加
性能的に有利な静的構築も出来たほうがよい
インデックスの後付
mroongaにALTER TABLE追加
offlineで索引を作るシステム
年末くらいにリリースしたい

行く末

開発したいもの
カラムストアの性能強化
索引の圧縮方法拡充
類似文字列検索
頻出パターン抽出
ストリーム処理機能
スキーマレス化

それらは開発者が決まっていません。開発者募集デス!


質問タイム

Q. nroongaを作った経緯は?
A.もともと持っているhttpサーバーの完成度が低いのでより汎用性の高いnode.jsを採用した実装を作った。


■mroongaの紹介

話し手:斯波さん

mroongaとは

groongaをMySQLで使えるよう実装したもの
全文検索、位置情報検索ができるストレージエンジンとしての実装。
またはほかのストレージエンジンに全文検索機能を追加する実装。

更新が混在しても高速な全文検索が可能
MyISAMの場合は参照ロックする
更新を即時参照することに強い

位置情報検索
更新性能が高い
ただし、位置情報は点のみ、図形は非対応。

ラッパーモード
これまで使用していたストレージエンジンを利用できる。
groongaで使えないNULLを使える


この1年の主な機能追加

auto_incrementの追加
ラッパーモード
マルチカラムインデックス
CREATE/DROP INDEX対応
位置情報検索のINDEX対応
全文検索用パーサーカスタマイズ対応
RENAME/ALTER TABLEに対応
これでやっとRORが使える

この1年のSpider/VPでの主な機能追加

全文検索対応
位置情報検索INDEX対応
shardingしても位置情報検索が可能

今後の予定

MariaDBにバンドルします!オオー
要望の高いものから実装したい。

まとめ

・更新と参照が混在する用途に強い
・Spiderと組み合わせてshardingできる
・RORで使えるよ


■実際のサービスで位置情報検索で利用したレポート

話し手:ぐるなび塩畑さん

歩み

2008年6月~
オープンソース化
ファセット分類
httpによるQuery
緯度経度範囲検索

2010年4月~
実装例
レストラン検索
地図検索
駅検索
GPS検索

緯度経度検索

groongaでは矩形円形で対応
矩形による範囲検索
左上と右下の点を指定して範囲を決める
円形による範囲検索
中心点と半径を指定して範囲を決める
距離を算出する
groongaではメートル単位で可能

距離の計算方法

方形近似
平面地図上にて距離を算出
精度が低い
計算が単純で速い
球面近似
地球儀での距離を算出
ヒュベニ
楕円体上にて距離を算出する
もっとも精度が高い
一般的に計算が遅い

測地系とは

日本測地系・世界測地系 両方を使う
それぞれで400m前後ずれることがある
それぞれ楕円体が違うため精度に差がある

日本測地系座標
Yahoo!Japan、Mapion、Mapfanで使われている
世界測地系座標
WGS84を採用
GPSを利用
GoogleMapで使われている

当初パフォーマンスがでなかったが、バージョンアップで9割改善
オオー

■groonga with PostgreSQLの紹介

話し手:フォルシア 奥野さん

PostgreSQLの特徴

拡張性の高さ
インストールはPGXNで。
CPANのようなもので、インストールが今北産業で簡単にできちゃう。

PostgreSQLでgroongaを使う

実装方法は2つ。

1.INDEXで使う
textsearch_groonga
形態素解析は辞書ちゃんと作らないと漏れるし、sennaはお休みなのでこれを作った。
こちらはリリース済み!

2.table groonga_fdw
SQL/MED SQL2003に準拠した実装。
FDW (Foreign Table Wrapper)
こちらはまだ開発中

まとめ

・PostgreSQLは拡張性高いよ
・PostgreSQLではgroongaを2つの方法で使えるよ
・親和性高いよ


■mroongaのベンチマーク

話し手:クリアコード 須藤さん

全文検索

秒数
mroonga -- 3
mroonga+InnoDB -- 6
InnoDB 5.6.3-lab -- 46
MyISAM -- 8

mroonga圧勝!オオー
ただし、InnoDB 5.6.3はまだ開発版なので参考値

位置情報検索

秒数
mroonga -- 1200
mroonga+InnoDB -- 1700
MyISAM -- 1300
(MBRContains + OrderBy)

若干早い。

更新スループット

全文検索・位置情報とも
mroonga単体が圧倒的高速
InnoDBラッパーモードはInnoDBの性能に引きずれられるので遅くなりがち。


参照ロックフリーなので検索負荷に強いよ


■mroongaの制限事項

話し手:斯波さん

mroongaの未サポート機能

・UTF-8以外の文字コード
・COLLATION
・condition pushdown
・点以外の空間情報
・0度またぎの緯度経度
・MySQL5.6から登場する正確な位置比較関数
・ストレージモードでのNULL (ラッパーなら使える)
・トランザクション (ラッパーでもダメ)
mroongaのINDEX更新をロールバックできない
・REPAIR TABLE
ストレージモードの場合はレプリケーションしておくことをお勧め
Spiderなら無停止復旧できる
・Spiderでのparallel searching

さっきも言ったけど要望の強いものから実装する予定。


■grn_dat ダブル配列の話

話し手:未来検索ブラジル 矢田さん

IDと文字列を関連付けるINDEXについて

「grn_pat」
パトリシアトライと呼ばれる
前方一致検索

「grn_hash」
ハッシュ表と呼ばれる
前方一致検索をサポートしない代わりに高速

「grn_dat」
ダブル配列と呼ばれる
前方一致検索をサポートする
更新性能・ファイルサイズは不利
文字列更新ができる

いずれも参照ロックフリー
文字列更新の機能はテーブル情報の管理に使う

「grn_pat」の代替として「grn_dat」を使ってみた

前方一致検索ができる
更新より参照が多い
参照時間を重視する場合

参考記事
「参照ロックフリーなダブル配列」


ベンチマーク

wikipediaのデータを使ってみた
検索
grn_pat より速い
構築時間
grn_dat は遅い
サイズ
grn_dat 一番でかくなる


まとめ

前方一致検索できて参照が早い


今後の開発

頻出する索引語をキャッシュ
偏りがあれば早くできる
構築時間の短縮
改良の余地あり
見る機会の少ないデータの圧縮
marisaなら更新できないし参照も遅いがサイズを小さくできる。


■質疑応答

ベンチマーク結果について

Q.INDEX タイプによる違いはあるのか

A.英語で検索した。
(InnoDB 5.6.3がまだマルチバイト非対応なので平等に比較するために。)
mroonga は n-gram、ほかはデフォルト
(須藤さん)


ぐるなび位置情報検索について

Q.サービス開始後、トラブルがどの程度、どんな理由であったか
A.トラフィクは 20QPS 3台でまわしている。
問題になるような障害はない。
緯度経度検索でバグがあったがスループットでつまったことはない。
(ぐるなび塩畑さん)


Q.3台構成はどうやって実装しているのか
A.httpリクエストをロードバランサで3台に分ける。
データ自体はバックグラウンドで別のアプリで3台に同期する。
(ぐるなび塩畑さん)


データが壊れる

Q.インデックスやストレージのデータの壊れやすさや壊れるタイミングは?
A.カーネルごと落ちると壊れやすい
プロセルが落ちても壊れるかも
運が悪いとロックが残る




その後、懇親会がVOYAGER GROUPの社内バー(!)で開催され、寿司をおいしくいただきました。

0 件のコメント:

コメントを投稿