第12回　索引の分散

はじめに

GoogleなどのWeb検索エンジンでは、2004年ごろには数10Tバイトの索引を数万台のサーバに分散させていたと言われています。これは、大量のデータを索引化したり大量のクエリを捌く必要がある際に、1台のマシンでは十分な速度が出ないことがあるためです。近年のハードウェアの進化はめまぐるしいですが、それでもハードウェアによるスケールアップには限界があるため、大規模な検索エンジンにおいて検索処理をスケールさせるには複数台のマシンの利用が不可欠となります。今回は、転置索引の複数のサーバへの分散方法について見ていきます。

複数台サーバにおける転置索引

複数のサーバを利用して検索処理を高速化させる方法には、索引のレプリケーション（replication）と索引の分散（distribution）の2つがあります。索引のレプリケーションとは、複数台のマシンに同じ転置索引（のコピー）を配置する方法です。検索時は、中継サーバ（receptionist）がそのうちのどれか1つのマシンにクエリを配送します。レプリケーションは、クエリのスループットが問題である場合は非常に有効な解決方法となり、中継サーバのオーバーヘッドは小さいためマシンを増やした分だけスループットの向上が期待できます。

一方、索引の分散は、文書や辞書が分割されて、それらが各サーバに配置される方法となります。検索時は、中継サーバはいくつかの、あるいは全てのサーバに問い合わせを行い、システム全体としての結果を集約する必要があります。分散はデータの量やレスポンスタイムが問題である場合に有効な解決方法となります。今回はこの分散方法について、もう少し詳しく見ていきます。

転置索引の分散方法

索引の分散方法には、主に以下の2つの方式があります。

文書分散方式（Document Partitioning）
単語分散方式（Term Partitioning）

以下に、これらのアーキテクチャや特徴を示します。

文書分散方式

文書分散方式は文書集合を分割し、それぞれの部分文書集合を各サーバに割り当てる方法です。

図1のように転置索引は縦に分割され、各部分索引が各サーバ（以後、索引サーバ）に配置されます。各マシンでは、部分文書集合に対して（他の索引サーバとは独立に）索引が構築されます。検索時は、クエリは中継サーバから全索引サーバに配送され、各々のローカルの索引に対して検索処理が行われ、各索引サーバからの結果を中継サーバで集約し、最終的な結果がリクエスト元に返されます。文書分散方式の概要を図2に示します。

中継サーバの集約処理は主に結果のマージと再ランキングとなります。関連度上位10件がリクエストされた場合、各索引サーバからはローカルでの上位10件の文書情報（文書ID、スコア等）が返されます。中継サーバでは、各索引サーバからの結果をマージし、システム全体での上位10件の文書IDを求め、文書IDに該当する文書情報とともにリクエスト元に結果を返します（文書情報の保存先は、索引サーバである場合もあれば、別のサーバに集約されている場合もあります⁠）⁠。

単語分散方式

単語分散方式では、辞書を分割し、各部分辞書とその単語を含む文書集合を各サーバに割り当てる方法となり、転置索引は図1のように横に分割されます。検索時は、中継サーバはクエリをタームと索引サーバの対応付け表からクエリ内のタームを含む索引サーバに配送します。各索引サーバではタームの引き当てを行い、結果の転置リストを中継サーバに返し、中継サーバでマージ処理や連接判定を行います。単語分散方式の概要を図3に示します。

単語分散方式の索引の構築は少し複雑になります。索引が1台にサーバに収まる場合は、1台でサーバを構築し、完成した索引をタームごとに索引サーバに分散させます。しかし、索引が1台にサーバに収まらない場合、一旦文書分散方式で各部分索引で構築し、その後タームの割り当てによって各サーバ間でポスティングリストの転送（交換）を行います。

文書分散方式 VS. 単語分散方式

2つの分散方式を紹介しましたが、それぞれ長所・短所があります。ここでは2つの分散方式の定性的な比較を行います（定量的な比較は参考文献[3]をご参照ください⁠）⁠。

文書分散方式は、文書集合を分割するため、各索引サーバに同程度のサイズの文書集合が格納されます。これにより、検索時の各索引サーバのワークロードが均一になりやすいという特徴があります。このため、マシンの追加によりシステムをスケールアウトさせることが比較的容易となります。一方、単語分散方式では、辞書を分割するため、各索引サーバの文書集合のサイズは不均一になります（ある単語は多くの文書に含まれ、ある単語はごく少数の文書に含まれることがあるため⁠）⁠。

また、検索時はクエリタームを含む索引サーバのみに問い合わせを行うため、クエリの検索頻度により、索引サーバに問い合わせる回数に偏りが発生してしまいます。このため、各索引サーバのワークロードが不均一となり、一部の索引サーバが高負荷になる可能性もあります。また、単語分散方式では中継サーバで多くの処理が行われるため、中継サーバがボトルネックになりやすいという問題もあります（※1⁠）⁠。しかし、各タームにおけるポスティングリストのディスクからの読み取り処理に関しては単語分散方式が有利となります。

各タームごとのポスティングリストは、索引サーバのいずれかの連続領域に格納されるため、1台のマシンにおいて1回のシークと1回の連続ディスク読み取りで取得することができます。一方、文書分散方式における各タームのポスティングリストは、各索引サーバに分散されているため、各索引サーバごとに1回のシークと1回の連続ディスク読み取りが発生してしまいます（※2⁠）⁠。

現段階では、各マシンに負荷が分散されスケールアウトが可能となるため、文書分散方式がより有効であると考えられています。文書分散方式のその他の利点としては、構築方法がシンプルであることや、一部のサーバが落ちてもサービスを提供することが可能である (結果が若干減るだけ)ことなども挙げられます。文書分散方式の有用性については、Googleにおいてもレプリケーションと文書分散方式を併用していることからも伺えます（参考文献[3]⁠）⁠。

近年の研究

参考文献[2]では、単語分散方式における中継サーバのボトルネックを解消するため、索引サーバ間でクエリとポスティングリストを中継する方法が提案されています。しかし、各索引サーバへのワークロードが均衡にならないことによる欠点が大きく、現段階では文書分散方式に劣ると結論づけられています。

まとめ

簡単にではありますが、転置索引の分散方法について説明してきました。スループットが問題の場合はレプリケーションを利用し、文書データのサイズやレスポンスタイムが問題である場合は文書分散方式が利用することにより、大量のデータや検索リクエストに対応することが可能となります。

【参考文献】: [1] Justin Zobel, Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), 2006; [2] A. Moffat, W. Webber, J. Zobel and R. Baeza-Yates, A pipelined architecture for distributed textquery evaluation. Inf Retrieval, 2005; [3] L. A. Barroso, J. Dean, and U. H¨olzle. Web search for a planet: The Google cluster architecture.　IEEE Micro, 23(2):22-28, Mar. 2003