関口宏司のLuceneブログ

OSS検索ライブラリのLuceneおよびそのサブプロジェクト(Solr/Tika/Mahoutなど)について
Baileyのアーキテクチャ - 今後の超大規模検索インフラの指針
会社を創業した2年半前頃はLuceneを使って数百万件オーダーの文書の全文検索機能を企業システムなどに導入するコンサルティングを行っていた(もちろん、今でも)。

ところが現在は、数千万件やそれを超える1億件、さらには十億件オーダーの文書を検索したいという依頼がある。検索側ではSolr 1.3(出る出るといっていまだ出ていないので、客先にいくたびに肩身が狭い?)がDistributed Searchをサポートするが、大量の文書のインデックスをなるべく短い時間で作成するための並列化や、多数のハードウェアの故障をあらかじめ織り込んだ運用を行うために、だんだんとHadoopが無視できなくなりつつある今日この頃だ。

SolrのMLで紹介されていたBaileyというプロジェクトは、LuceneやHadoopのコミッターのDoug Cutting氏のチェックポイント的な、今後の大規模検索のインフラのあるべき姿を彼なりに示したものであると見た。以下はその「デザイン」を解説したページの翻訳である。

例によって翻訳はいい加減なところがあるので、正確なところは原文をあたっていただきたい。

http://bailey.wiki.sourceforge.net/Architecture



デザイン

1 システム構成と機能

システムはひとつの「マスター」と複数の「ノード」、複数の「クライアント」からなります。

docidハッシュ値空間は「リング」とみなします。各「ノード」はリング上のドキュメントの「レンジ」の「インデックス」をメンテナンスします。「マスター」は各ノードとそれらがインデックスしているレンジのマッピングを管理します。

「ノード」は仮想/論理ノードを参照します。物理「ホスト」は複数のノードをホストします。

システムは以下の操作をサポートします:

  • addDoc(doc), deleteDoc(doc), updateDoc(doc)

  • search(query)



「アプリケーション」はこれらの操作を「クライアント」を通じて行います。クライアントはノードとレンジのマッピング情報を取得するためにマスターと通信します。そしてノードに対し直接addDoc(doc), deleteDoc(doc), updateDoc(doc)したりsearch(query)したりします。

2 パーティショニング

ロードバランシングのために一貫したハッシングを使うこととします。ノードXはリング上の「ポジション」にアサインされます。リング上の「次」のノード/ポジションはX+1です。ノードXのレンジは[X, X+1)です。

これはレンジパーティショニングに似ています。

3 レプリケーション

耐障害性対策のためにレプリケーションを行います。N-wayレプリケーションとはデータをN個のノードに保存/インデクシングすることを意味します。N=3の場合、ノードXのレンジは[X, X+3)です。レンジ[X, X+1)はノードXに加えてノードX-2とノードX-1をサービスします。

4 search(query)

ノードとレンジのマッピングに基づき、クライアントは検索リクエストを複数のノードに送ります。クライアントはリクエストを送る各ノードに検索レンジを指定することで次を行います:
(1)ノードのための検索レンジはそのノードがカバーしているレンジ
(2)検索レンジは統合的にリングをただ一度だけカバーします
(3)リクエストを送るノード数をなるべく少なくします

たとえば、7個のノードで3-wayレプリケーションの場合、検索リクエストはノードXに検索レンジ[X, X+3)で、ノードX+3に検索レンジ[X+3, X+6)で送られます。またノードX+6では検索レンジは[X+6, X+7)ですが、X+7 == Xです。

再検索の待ち時間を避けるための代替案はリングをR回(たとえばR=2)カバーすることです。

5 addDoc(doc)/deleteDoc(doc)/updateDoc(doc)

ドキュメントの追加、削除、更新はアプリケーションが指定したドキュメントのリビジョン番号が付加されるものとします。そうしないとベクタークロックなどのより複雑なオペレーションを行わなければなりません。

各ノードは定期的に(定期的にのみ)ディスクにフラッシュされる軽量なログをメンテナンスします。ログはログエントリのシーケンスです。各ログエントリは<{ADD|DEL}, docid, revision>です。

更新リクエストは複数のノードに送られ、送られた全レンジはドキュメントを含んでいなければなりません。

ノードがリビジョンRのドキュメントの更新リクエストを受け取った場合、リビジョンRがノードに保存/インデクシングされているリボジョンと比較して新しいことを確認します。そしてノードはその新しいリビジョンをメモリに保存およびインデクシングしてログにログエントリを書き込みます。

W-way更新ではその更新が「完了」したとみなせるためには、少なくともW個のノードが更新リクエストを成功させる必要があります。ここでWは1 < W <= Nです。W > 1とは更新オペレーションに耐障害性を持たせることを意味します。

6 一貫性

各ノードはログ伝播ともいわれるレンジのオーバラッピングにおけるノード間でシンクします。しかしほとんどのケースでW+R <= Nなので、システムは結果として一貫性を具備します。

ノードは、更新リクエストのためのリビジョンが現在ノード上に保存/インデクシングされているリビジョンよりも新しいことをチェックしますので、単調な更新一貫性をサポートします。

クライアントの実装はセッションの一貫性をサポートしなければなりません。またread-your-writesと単調なリード一貫性をサポートするといい感じです。

ログ伝播について。ノードXはレンジ[X, X+3)をサービスし、以下の定期シンクを行います:
range [X, X+1) with node X-2
range [X, X+2) with node X-1
range [X+1, X+3) with node X+1
range [X+2, X+3) with node X+2

以下はノードX上のレンジ[X, X+1)の更新がどのようにノードX-2に伝播されるかを説明しています。最後のシンクの間、ノードX上のログエントリEの更新はノードX-2に伝播され、ノードX上の現在のログエントリはFであるとします。

  • ログエントリ(E, F]がシーケンシャルにスキャンされ、レンジ[X, X+1)にあるものがノードX-2に送られます。

  • ノードX-2はノードXから受信したログエントリをチェックします。ログエントリ<{ADD|DEL}, docid, revision>において、もしノードX-2の現在のリビジョンが古い場合は、ノードX-2は当該docidをリクエストリストにプットします。そしてノードX-2はdocidのリクエストリストをノードXに送信します。

  • ノードXはリクエストリスト上のドキュメントの保存コピーをノードX-2に出荷します。

  • ノードXからドキュメントを受信すると、ノードX-2はそれを通常の更新リクエストとして処理します。つまりノードX-2は単調な更新一貫性を確認するためにリビジョンを再度チェックしてログします。



7 ノードの追加/ノードの削除

新しいノードが追加されると、新しいポジションがアサインされます。新しいX'がXとX+1の間のポジションX'にアサインされると仮定しましょう。

隣接ノードが影響を受け以下から:
node X-2 serves range [X-2, X+1)
node X-1 serves range [X-1, X+2)
node X serves range [X, X+3)
以下のようにスイッチします:
node X-2 serves range [X-2, X')
node X-1 serves range [X-1, X+1)
node X serves range [X, X+2)
node X' serves range [X', X+3)

ノードX'は1つ以上の隣接ノードからインデックスファイルをコピーすることによりレンジ[X', X+3)を用意します。そしてノードX'はレンジオーバラッピングにおけるノードのシンクを開始します。

実行中のノー・ライトあるいは更新伝播の喪失を保証するために、2-フェーズコミット風なことが行われます。
| 関口宏司 | 超大規模検索 | 15:00 | comments(0) | trackbacks(0) |
+ Solrによるブログ内検索
+ PROFILE
     12
3456789
10111213141516
17181920212223
24252627282930
<< June 2018 >>
+ LINKS
検索エンジン製品 - 比較のポイント
商用検索エンジンを購入した企業担当者は読まないでください。ショックを受けますから・・・
>>製品比較 10のポイント
+ Lucene&Solrデモ
+ ThinkIT記事
+ RECOMMEND
Apache Solr入門 ―オープンソース全文検索エンジン
Apache Solr入門 ―オープンソース全文検索エンジン (JUGEMレビュー »)
関口 宏司,三部 靖夫,武田 光平,中野 猛,大谷 純
+ RECOMMEND
Lucene in Action
Lucene in Action (JUGEMレビュー »)
Erik Hatcher,Otis Gospodnetic,Mike McCandless
FastVectorHighlighterについて解説記事を寄稿しました。
+ RECOMMEND
+ SELECTED ENTRIES
+ RECENT COMMENTS
+ RECENT TRACKBACK
+ CATEGORIES
+ ARCHIVES
+ MOBILE
qrcode
+ SPONSORED LINKS