注: 長いです。
日本Ruby会議2010でるりまサーチの作り方について発表しました。
2010-08-30 |
[rk10][29S06] るりまサーチの作り方 - Ruby 1.9でgroonga使って全文検索 (32:59) こんな動画まで風評被 RRMさん!?まずいです RRMさんをすこれ お覚悟を。 すごー buzztterはgrongaを使 rackngaが便利そう 検索: rrooonga HTTPでも出来るー 検索se... |
ステージから見た感じだと立ち見の人もいたようでした。セッションに参加してくれたみなさん、会場を担当してくれたりレポートしてくれたスタッフのみなさん、ありがとうございました。
時間の関係で省略したことも含めてまとめておきます。
資料の中では、まず、るりまサーチについて説明し、その後、全文検索システムとしてのるりまサーチをどう作るのかを説明しています。
るりまサーチはRubyリファレンスマニュアル刷新計画 (通称るりま)の成果物であるRuby本体のリファレンスマニュアルを全文検索するためのWebアプリケーションです。るりまサーチが必要とされていた理由は、既存のリファレンスマニュアル閲覧Webアプリケーションに組み込まれていた検索機能の速度が遅かった*1からです。せっかく有益なリファレンスマニュアルがあっても、目的のエントリにたどりつくのが難しければ、有効に活用することができません。検索機能の面からリファレンスマニュアルの有効活用を支援する全文検索システムがるりまサーチです。
るりまサーチはRubyのリファレンスマニュアルに特化した小さな全文検索システムですが、最近の全文検索システムにとって重要なエッセンスが含まれています。全文検索システムを開発する場合はこれらのエッセンスを含めることを検討してみてください。
まず1つ目はドリルダウンと呼ばれる機能です。Solrなど他の全文検索システムによってはファセットと呼ぶこともあります。ドリルダウンとは、通常の検索結果に加えて、別のパラメータでの絞り込み結果も同時に提供する機能です。スライド中では「Rubyのバージョンで絞り込んだ結果、何件ヒットするか」という情報も表示しています。
この機能で嬉しいことは以下の2点です。
どちらもユーザの使い勝手を向上させるインターフェイスにつながります。ショッピングサイトなどでも使われているインターフェイスですね。
2つ目はURLのパスに絞り込み条件を含めることです。これは、内部ネットワーク用の全文検索システムではなく、インターネット上に公開する全文検索システム向けです。
最近ではURLにUTF-8でエンコードされたページ情報を含めることは一般的になってきました。WikipediaやAmazonでも行っています。Web検索エンジンはURLからも検索用の情報を抽出しているようなので、SEOになると考えられます。
3つ目はキャッシュです。より快適に検索・絞り込みを行うにはできるだけ速いレスポンスが求められます。レスポンスを高速化するためには、以下のような方法があります。
手軽に高速化する場合は後者のキャッシュ機能が便利です。キャッシュをする場合はキャッシュを無効化するタイミングを慎重に検討する必要があります。このタイミングを誤ると、期待した結果が返ってこないという問題が発生します。
キャッシュを無効にするタイミングはアプリケーションに依存します。一般的に、データが変更されるまでは同じキャッシュを利用できます。るりまサーチの場合は1日1回バッチ処理で元データを更新しています。そのため、同じキャッシュを1日使いまわすことができます。これにより高速にレスポンスを返すことができます。
また、キャッシュの効果を高めるためには、処理の内部よりもクライアントに近いところでキャッシュする必要があります。その方がより多くの計算を省略することができるからです。るりまサーチはログインせずに使えるシステムなので、同じ検索リクエストの結果はクライアントに関わらず同一になります。そのため、レスポンスをまるごとキャッシュすることができ、とても高い効果があります。
ログインが必要なシステムの場合は、クライアント毎に変更される部分のみJavaScriptで動的に生成したり、iframeを用いて別HTMLにすることにより、ログインによって変更されない部分ではキャッシュを利用することができます。それが難しい場合はもっと処理の内部でキャッシュをすることになります。この場合はキャッシュの効果が薄くなります。
キャッシュを用いることにより劇的にレスポンス速度を改善することができますが、キャッシュの有効期限とキャッシュする場所についてはよく検討する必要があります。
るりまサーチに含まれている最近の全文検索システムに重要なエッセンスは以下の3つです。
それでは、このようなエッセンスを含む全文検索システムるりまサーチの作り方について説明します。
全文検索システムは以下の5つの要素からなります。
まず、検索対象からクローラーが検索対象とする文書を収集します。次に、それらからインデクサーがテキストやメタ情報を抽出して全文検索エンジンに登録します。全文検索エンジンに登録したデータからユーザが求めるデータを検索して提示するのが検索インターフェイスです。
るりまサーチの場合は以下のようになります。
この中で、るりまサーチの重要な部分である全文検索エンジンgroongaについて説明します。
発表当日に初のメジャーバージョン1.0.0がリリースされたgroongaは、MySQLとの組み合わせで広く利用されているSennaの後継プロジェクトです。Sennaでのよいところを維持しつつ、さらに改良が加えられています。
Sennaは妥協しない転置索引実装と参照ロックしない更新アルゴリズムによるリアルタイム検索の実現が大きな特徴でした。Senna自体はデータストア機能を持たず、MySQLなど外部のデータストアと連携します。MySQLとSennaを連携させるソフトウェアはTritonnと呼ばれ、SQLで高速な全文検索機能を利用できることから広く使われています。しかし、MySQL側のロックモデルのため常に検索可能な状態で更新処理を行うことができません。そのため、せっかくのSennaの参照ロックフリーな更新アルゴリズムの特徴を活かしきれませんでした。
そこで、groongaでは独自のデータストア機能を提供し、外部のシステムによる制限を回避してgroongaの性能を発揮できるようにしました。データストアはドリルダウンを高速に実現できるカラム指向を採用しています。
また、HTTP/memcached/独自プロトコルなどのネットワークプロトコルも実装し、Solrのように検索サーバとして利用することもできるようになっています。
その他にも、より大規模な文書に対してもスケールするような性能改善や、モバイル端末の普及により重要性が増している位置情報データに対応するなど新規機能が含まれています。ただし、これらの改善のためにSennaとの互換性がなくなっています。Sennaの後継としてgroongaと名前を変更した理由はこのためです。
それでは、るりまサーチのケースを例にしてgroongaの使い方を説明します。手順は以下の通りです。
RDBと同じようにgroognaでも、まず、スキーマを定義します。
スキーマはRDBと同じように以下の3つの要素から構成されます。
RDBではさらに索引もでてきますが、groongaでは↑の3つの要素を使って索引を作成するので、RDBより特別な存在ではありません。
スキーマを定義するときは、まず、検索対象がなにかを考えます。そして、その対象がどのくらいの粒度で1エントリになるかを考えます。るりまサーチではリファレンスマニュアルが検索対象で、メソッドやクラスそれぞれが1つのエントリになります。検索対象全体をテーブルとし、エントリをテーブルの各レコードにします。るりまサーチでは検索対象全体を扱う「Entries」テーブルを定義しています。
テーブルには検索結果に表示したい内容と検索時に利用する内容をカラムとして定義します。るりまサーチの場合にはメソッド名やクラス名を格納する「name」カラムやドキュメントを格納する「description」カラムなどを定義しています。
検索対象用のテーブルを定義したら索引を定義します。ここがRDBと異なる部分です。全文検索用の索引では単語と文書を対応させる語彙表が必要になりますが、同じトークナイザー*2を利用している場合は同じ語彙表を共有して省スペース化したり、同じテキストに複数のトークナイザーを適用して検索精度や検索漏れのトレードオフを調整したり、といったRDBよりも細かい制御ができます。
単にヒットしたかどうかではなく、検索結果の重み付けも重要です。有用な検索結果を提供するためには、クエリに適していると思われる結果ほど上位に提示する必要があります。しかし、どのように重み付けをするのが適切かは全文検索システムに大きく依存します。そのため、groongaでは索引毎に重み付けをカスタマイズする機能を提供しています。
るりまサーチではメソッド名やクラス名に完全一致した場合はよりマッチしていると判断するように*3、名前と完全一致だけする語彙表「Names」テーブル*4を定義し、そこに「name」カラムの索引を定義します。検索時にはこの索引にマッチした場合は重み付けを大きくします。
ドキュメント部分(「summary」カラムと「description」カラム)はトークナイザーを設定した全文検索用の語彙表「Terms」テーブルを共有しています。こっちの索引にマッチした場合は重み付けを小さくします。
スキーマはgroongaが提供している組み込みのDDLで定義する方法と、groongaのRubyバインディングであるrroongaが提供するDSLで定義する方法があります。
groongaのDDL:
# 検索対象のテーブル table_create Entries TABLE_HASH_KEY ShortText # 全文検索用の語彙表。トークナイザーとしてN-gramを使用。 table_create Terms TABLE_PAT_KEY ShortText --default_tokenizer TokenBigram # 完全一致検索用の語彙表。トークナイザーはなし。 table_create Names TABLE_HASH_KEY ShortText # 検索対象のデータ格納場所 column_create Entries name COLUMN_SCALAR Names column_create Entries summary COLUMN_SCALAR Text column_create Entries description COLUMN_SCALAR Text # 全文検索用の索引 column_create Terms Entries_summary COLUMN_INDEX Entries summary column_create Terms Entries_description COLUMN_INDEX Entries description # 完全一致検索用の索引 column_create Names Entries_name COLUMN_INDEX Entries name
rroongaのDDL:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
Groonga::Schema.define do |schema| # 完全一致検索用の語彙表。トークナイザーはなし。 schema.create_table("Names", :type => :hash, :key_type => "ShortText") do |table| end # 検索対象のテーブル schema.create_table("Entries", :type => :hash, :key_type => "ShortText") do |table| table.reference("name", "Names") table.text("summary") table.text("description") end # 全文検索用の語彙表。トークナイザーとしてN-gramを使用。 schema.create_table("Terms", :type => :patricia_trie, :key_type => "ShortText", :default_tokenizer => "TokenBigram", :key_normalize => true) do |table| # 全文検索用の索引 table.index("Entries.summary") table.index("Entries.description") end schema.change_table("Names") do |table| # 全文検索用の索引 table.index("Entries.name") end end |
スキーマを定義したらデータを登録します。索引は自動で更新されるため、データ用のカラムにデータを登録するだけで動作します。
データの登録方法はgroongaのloadコマンドを使う方法と、rroongaを使う方法があります。
groongaのloadコマンド:
load --table Entries [ ["_key", "name", "summary", "description"], ["String#sub", "sub", "置換", "1つ置換"], ["String#gsub", "gsub", "置換", "全部置換"] ]
rroonga:
1 2 3 4 5 6 7 8 9 |
entries = Groonga["Entries"] entries.add("String#sub", name: "sub", summary: "置換", description: "1つ置換") entries.add("String#gsub", name: "gsub", summary: "置換", description: "全部置換") |
Rubyで登録データの前処理を行う場合はrroongaを使う方がよいでしょう。Ruby以外で処理を行う場合はデータからJSONを生成し、groongaのloadコマンドを使う方がよいでしょう。るりまサーチはRubyで前処理*5をしているのでrroongaでデータを登録しています。
全文検索する場合は検索対象のカラムを指定する方法と、明示的に利用する索引を指定する方法の2通りあります。カラム単位で重み付けをしたい場合はカラムを指定し、索引単位で重み付けをしたい場合は索引を指定します。両方の指定方法を混ぜ合わせることもできます。
データの検索方法はgroongaのselectコマンドを使う方法と、rroongaを使う方法があります。
groongaのselectコマンド:
# 「description」カラムに「1つが」含まれているエントリを検索 select Entries description "1つ" [[...], [[[...], [..., ["_key", ...], ["name", ...], ["summary", ...], ["description", ...], ...]], [..., "String#sub", "sub", "置換", "1つ置換", ...], ...]] # 「sub」が含まれているエントリを検索。ただし、「name」が # 「sub」だった場合は重みを大きくする。 select Entries "name * 100 | summary | description" "sub" [[...], [[[...], [..., ["_key", ...], ["name", ...], ["summary", ...], ["description", ...], ...]], [..., "String#sub", "sub", "置換", "1つ置換", ...], ...]]
groongaのselectコマンド(HTTP経由):
# 「description」カラムに「1つが」含まれているエントリを検索 % wget -O - 'http://localhost:10041/d/select?table=Entries&match_columns=description&query=1つ' [[...], [[[...], [..., ["_key", ...], ["name", ...], ["summary", ...], ["description", ...], ...]], [..., "String#sub", "sub", "置換", "1つ置換", ...], ...]] # 「sub」が含まれているエントリを検索。ただし、「name」が # 「sub」だった場合は重みを大きくする。 % wget -O - 'http://localhost:10041/d/select?table=Entries&match_columns=name*100|summary|description&query=sub' [[...], [[[...], [..., ["_key", ...], ["name", ...], ["summary", ...], ["description", ...], ...]], [..., "String#sub", "sub", "置換", "1つ置換", ...], ...]]
rroonga:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
entries = Groonga["Entries"] # 「description」カラムに「1つ」が含まれているエントリを検索 result = entries.select do |record| record.description =~ "1つ" end # 「sub」が含まれているエントリを検索。ただし、「name」が # 「sub」だった場合は重みを大きくする。 result = entries.select do |record| target = record.match_target do |match_record| (match_record["name"] * 100) | (match_record["summary"]) | (match_record["description"]) end target =~ "sub" end |
PHPなどRuby以外の言語から利用する場合はgroongaサーバを立てて、HTTP経由で検索するのがよいでしょう。Rubyから利用する場合は、selectコマンドで十分ならselectコマンドを利用、より複雑なことをしたい場合はrroongaを利用するのがよいでしょう。selectコマンドでもドリルダウンはサポートされて入るので、多くの場合はselectコマンドで十分でしょう。
るりまサーチでは、selectコマンドが提供するクエリ書式を利用したくない、rroongaが提供するページネーション機能を利用したい、などの理由でselectコマンドではなくrroongaを使っています。rroongaを利用してドリルダウンを実現する例にもなっています。
るりまサーチを例にして、groongaを用いて全文検索システムを開発する場合の基本的な流れを説明しました。より詳しいことはGitHubのるりまサーチのリポジトリにあるソースコードを見てください。
るりまサーチの検索WebインターフェイスはRuby 1.9とRackの上に構築されています*6。るりまサーチを開発した際に、るりまサーチ以外でも使えそうな部分がでてきたので、rackngaという名前でるりまサーチと別パッケージとして公開しています。
rackngaにはRackのミドルウェアとMuninプラグインが含まれています。MuninのプラグインはPassengerの以下の情報を収集します。
Rackのミドルウェアは1つずつ説明します。
アプリケーション内でエラーが発生した場合にメールでその内容を通知するミドルウェアです。RailsのException NotifierのRack用です。
以下のように利用します。
config.ru:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
require 'racknga' notifier_options = { "host" => 127.0.0.1, "from" => "rurema@example.com", "to" => "developer@example.com", "charset" => "iso-2022-jp", "subject_label" => "[るりまサーチ] ", } notifiers = [Racknga::ExceptionMailNotifier.new(notifier_options)] use Racknga::Middleware::ExceptionNotifier, :notifiers => notifiers # ... run your_application |
できるだけ多くのエラーを検出するためになるべく最初の方でuse
してください。
主にサーバ1台や2台などで処理できる程度の中規模のPassenger環境で利用することを想定したキャッシュミドルウェアです。ヘッダーやボディを含めHTTPのレスポンス全体をgroongaのデータストアにキャッシュします。Passengerでは複数のインスタンスが別プロセスで起動しますが、groongaは複数プロセス間で同一のデータベースを操作することができるため、別のインスタンスがキャッシュした内容を他のインスタンスから参照することができます。以下のように利用します。
config.ru:
1 2 3 4 5 6 7 8 9 10 11 |
require 'racknga' require 'racknga/middleware/cache' # ... # use Rack::Deflater # use Rack::ConditionalGet # ... base_dir = Pathname.new(__FILE__).dirname.cleanpath.realpath cache_database_path = base_dir + "var" + "cache" + "db" use Racknga::Middleware::Cache, :database_path => cache_database_path.to_s run your_application |
他のミドルウェアと組み合わせやすいように、なるべくアプリケーションに近い部分に置くことをよいでしょう。
複数のサーバ間でキャッシュを共有したい場合は別の仕組みを利用することをオススメします。
ネットワーク帯域を節約するためには、レスポンスを圧縮して返すことが有効です。しかし、Internet Explorer 6では問題があることがわかっています。そのため、Internet Explorer 6の場合は常に圧縮しないようにするのがこのミドルウェアです。Rack::Deflater
のラッパーです。以下のように利用します。
config.ru:
1 2 3 4 5 6 7 |
require 'racknga' # ... use Racknga::Middleware::Deflater # use Rack::ConditionalGet # ... run your_application |
Web APIとしてサービスを提供する場合、JSON形式で結果を返すことが多くなっています。クライアント側でWeb APIにアクセスする場合はJSONPを利用することになります。
このミドルウェアはJSONPに対応しておらず単にJSONデータを返すだけのアプリケーションをJSONPに対応させることができます。また、以下のような配置にすることにより、キャッシュを有効にしたままJSONP対応にすることができます。
config.ru:
1 2 3 4 5 6 7 8 9 10 |
require 'racknga' require 'racknga/middleware/cache' use Rack::Middleware::JSONP base_dir = Pathname.new(__FILE__).dirname.cleanpath.realpath cache_database_path = base_dir + "var" + "cache" + "db" use Racknga::Middleware::Cache, :database_path => cache_database_path.to_s run your_application # "Content-Type: application/json"のレスポンスを返す |
現在、るりまサーチはWebサービスを提供していませんが、将来の拡張を念頭においてこのミドルウェアがrackngaに含まれています。
るりまサーチはドリルダウンやキャッシュを利用することにより、快適に目的のドキュメントへ到達できるような工夫をしています。るりまサーチ以外にもリファレンスマニュアルを利用するツールがあるので有効活用しましょう。
ドリルダウンを効果的に利用した高速な全文検索システムにはgroongaが適しています。Rubyとの親和性も高いgroongaで全文検索システムを開発してみてはいかがでしょうか。汎用ユーティリティであるrackngaも一緒に用いることにより開発・運用が改善されるでしょう。
最後にお知らせです。クリアコードではプログラミングが好きな開発者を募集しています。プログラミングが好きな人は検討してみてください。
*1 数十秒以上かかる。
*2 文章から単語を抜き出す処理。
*3 メソッド名で検索することは多いですよね?
*4 実体はトークナイザーなしのハッシュテーブル。
*5 BitClustを使ってメソッド単位にドキュメントを分割するなど。
*6 RailsやSinatraなどは使っていません。