検索エンジンはいかにして動くのか?

第12回 索引の分散

この記事を読むのに必要な時間:およそ 2 分

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

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

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

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

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

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

※1
ポスティングリストがそのままネットワーク経由で中継サーバに転送されるため,ネットワークがボトルネックになる可能性もあります。
※2
各ポスティングリストの取得にはブロックサイズの定数倍のI/Oが発生するため,文書分散方式ではより多くのI/Oも発生します。

近年の研究

参考文献[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

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。