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

第12回 索引の分散

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

はじめに

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

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

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

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

転置索引の分散方法

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

  • 文書分散方式(Document Partitioning)
  • 単語分散方式(Term Partitioning)

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

文書分散方式

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

図1 文書集合の分割と各方式の割り当ての違い

図1 文書集合の分割と各方式の割り当ての違い

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

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

図2 文書分散方式の概要

図2 文書分散方式の概要

単語分散方式

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

図3 単語分散方式の概要

図3 単語分散方式の概要

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

著者プロフィール

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

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

コメント

コメントの記入