会社を創業した2年半前頃はLuceneを使って数百万件オーダーの文書の全文検索機能を企業システムなどに導入するコンサルティングを行っていた(もちろん、今でも)。ところが現在は、数千万件やそれを超える1億件、さらには十億件オーダーの文書を検索したいという依頼がある。Searchをサポートするが、大量の文書のインデックスをなるべく短い時間で作成するための並列化や、多数のハードウェアの故障をあらかじめ織り込んだ運用を行うために、だんだんとHadoopが無視できなくなりつつある今日この頃だ。Cutting氏のチェックポイント的な、今後の大規模検索のインフラのあるべき姿を彼なりに示したものであると見た。以下はその「デザイン」を解説したページの翻訳である。例によって翻訳はいい加減なところがあるので、正確なところは原文をあたっていただきたい。システム構成と機能システムはひとつの「マスター」と複数の「ノード」、複数の「クライアント」からなります。docidハッシュ値空間は「リング」とみなします。各「ノード」はリング上のドキュメントの「レンジ」の「インデックス」をメンテナンスします。「マスター」は各ノードとそれらがインデックスしているレンジのマッピングを管理します。「ノード」は仮想/論理ノードを参照します。物理「ホスト」は複数のノードをホストします。updateDoc(doc)search(query)「アプリケーション」はこれらの操作を「クライアント」を通じて行います。クライアントはノードとレンジのマッピング情報を取得するためにマスターと通信します。updateDoc(doc)したりsearch(query)したりします。パーティショニングロードバランシングのために一貫したハッシングを使うこととします。ノードXはリング上の「ポジション」にアサインされます。リング上の「次」のノード/ポジションはX+1です。これはレンジパーティショニングに似ています。レプリケーション耐障害性対策のためにレプリケーションを行います。N-wayレプリケーションとはデータをN個のノードに保存/インデクシングすることを意味します。X+1)はノードXに加えてノードX-2とノードX-1をサービスします。search(query)ノードとレンジのマッピングに基づき、クライアントは検索リクエストを複数のノードに送ります。X+6)で送られます。再検索の待ち時間を避けるための代替案はリングをR回(たとえばR=2)カバーすることです。addDoc(doc)/deleteDoc(doc)/updateDoc(doc)ドキュメントの追加、削除、更新はアプリケーションが指定したドキュメントのリビジョン番号が付加されるものとします。しないとベクタークロックなどのより複雑なオペレーションを行わなければなりません。各ノードは定期的に(定期的にのみ)ディスクにフラッシュされる軽量なログをメンテナンスします。ログはログエントリのシーケンスです。revision>です。更新リクエストは複数のノードに送られ、送られた全レンジはドキュメントを含んでいなければなりません。ノードがリビジョンRのドキュメントの更新リクエストを受け取った場合、リビジョンRがノードに保存/インデクシングされているリボジョンと比較して新しいことを確認します。ノードはその新しいリビジョンをメモリに保存およびインデクシングしてログにログエントリを書き込みます。W-way更新ではその更新が「完了」したとみなせるためには、少なくともW個のノードが更新リクエストを成功させる必要があります。1とは更新オペレーションに耐障害性を持たせることを意味します。各ノードはログ伝播ともいわれるレンジのオーバラッピングにおけるノード間でシンクします。Nなので、システムは結果として一貫性を具備します。ノードは、更新リクエストのためのリビジョンが現在ノード上に保存/インデクシングされているリビジョンよりも新しいことをチェックしますので、単調な更新一貫性をサポートします。クライアントの実装はセッションの一貫性をサポートしなければなりません。read-your-writesと単調なリード一貫性をサポートするといい感じです。X+1)の更新がどのようにノードX-2に伝播されるかを説明しています。最後のシンクの間、ノードX上のログエントリEの更新はノードX-2に伝播され、ノードX上の現在のログエントリはFであるとします。X+1)にあるものがノードX-2に送られます。ノードX-2はノードXから受信したログエントリをチェックします。revision>において、もしノードX-2の現在のリビジョンが古い場合は、ノードX-2は当該docidをリクエストリストにプットします。ノードX-2はdocidのリクエストリストをノードXに送信します。ノードXはリクエストリスト上のドキュメントの保存コピーをノードX-2に出荷します。ノードXからドキュメントを受信すると、ノードX-2はそれを通常の更新リクエストとして処理します。ノードX-2は単調な更新一貫性を確認するためにリビジョンを再度チェックしてログします。新しいノードが追加されると、新しいポジションがアサインされます。新しいX'がXとX+1の間のポジションX'にアサインされると仮定しましょう。X+3)を用意します。ノードX'はレンジオーバラッピングにおけるノードのシンクを開始します。実行中のノー・ライトあるいは更新伝播の喪失を保証するために、2-フェーズコミット風なことが行われます。比較のポイント商用検索エンジンを購入した企業担当者は読まないでください。McCandlessFastVectorHighlighterについて解説記事を寄稿しました。