Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１）

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドを翻訳してみました。Googleの検索システムの10年間の進化の軌跡が紹介されており、興味深い話が満載です。個人的にはディスクの外周部と内周部を使い分けている話がツボでした。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。

スライドの入手元：Jeffrey Dean – Google AI

検索システムに取り組む理由

検索システムの様々な側面

  • 次の技術上のトレードオフのバランスをとることが必要。
    • インデックスする文書数
    • 1秒間に処理するクエリ数(QPS)
    • インデックスの新鮮さ・更新頻度
    • 応答時間
    • 各文書に大して保持する情報量
    • スコアリング・検索アルゴリズムの複雑さ・コスト
  • 技術上の難易度は大雑把にいえばこれらのパラメータの掛け算に等しい。
  • これら全ての要素が、全体としてのパフォーマンスおよびコスト・パフォーマンスに影響を与える。

例えばインデックスする文書数を増やすとQPSは低下しますし、複雑なスコアリング・アルゴリズムは応答速度を悪化させます。検索システムは大量のハードウェア資源を要求するので、優れた検索システムの構築には、コストを睨みながらこれらの要素のバランスをとることが必要です。

1999年 対 2009年

  • 文書数は7千万から数十億 => 100倍
  • 1日あたりにクエリ数 => 1000倍
  • インデックスされた文書の情報量 => 3倍
  • ページを更新するまでの時間は数ヶ月から数分 => 1万倍
  • 平均的な応答時間は1秒から0.2秒 => 5倍
  • マシン台数 * 単一マシンの性能向上 => 1000倍

残りのお話

  • Googleの検索システムの進化
    • クロール・インデックス・サーバシステムのいくつかの一般情報。
    • システムをサポートするインフラの簡単な説明。
    • 本当に多くの人々との共同作業の結果です。
  • 興味深い目標と課題

これ以降、Googleの検索システムの概要の説明となります。

Google Circa 1997

研究プロジェクト circa 1997

フロントエンドWebサーバとインデックスサーバ、文書サーバのシンプルな構成。まず、フロントエンドがインデックスサーバにクエリを問い合わせ、クエリに合致した文書のdocidを取得する。次に取得したdocidを文書サーバに問い合わせ、タイトル・スニペットを文書サーバを取得してクライアントに返却する。

インデックスの分割方法

  • 文書分割：各shardは一部の文書のインデックスを持つ。
    • 利点：各shardは独立にクエリを処理できる。
    • 利点：文書単位の付加情報（ページランクなど）の保持が容易
    • 利点：ネットワークトラフィック（リクエスト・レスポンス）が小さい
    • 欠点：あるクエリを全てのshardで処理する必要がある。
    • 欠点：N個のshardでK単語のクエリを処理する場合O(K*N)のディスクシークが必要。
  • 単語分割：各shardは全ての文書の一部の単語のインデックスを持つ。
    • 利点：K単語のクエリ処理で最大K個のshardを扱うだけで良い。
    • 利点：K単語のクエリ処理でO(K)のディスクシークが必要。
    • 欠点：大量のネットワーク帯域が必要
      • 各単語にマッチした文書を1箇所に集める必要があるため。
    • 欠点：文書単位の付加情報の保持が難しい。

Googleでは文書分割の方が理にかなっている。

本講演ではインデックスとは転置インデックスを指します。転置インデックスは単純化すると単語をkey、その単語が出現した文書情報の配列をvalueとしたmapになります。従って、転置インデックスを分割するならば単語毎に分割するのが自然に思えます。しかし、上述のように単語分割はネットワーク帯域が大量に必要なため、Googleでは文書分割を使っています。

基本原則

  • 各文書には小さい整数のid(docid)を割り当てる。
    • 高品質・重要な文書はidが小さい方が望ましい。
  • インデックス・サーバ
    • 与えられたクエリに対して、スコア順にソートされたdocidのリストを返す。
    • docidによって格納先のshardを決定する（パーティショニング）。
    • インデックスshardはキャパシティ性能向上のためにレプリケーションされる。
    • 計算コストは O(クエリ数 * インデックス中の文書数)。
  • 文書サーバ
    • 与えられたdocidとクエリに対して、タイトルとスニペットを返す。
    • docidから文書の本文を返すmapをディスク上に持つ。
    • インデックスと同様docidによるパーティショニング。
    • 計算コストは O(クエリ数)。

キャパシティ性能はQPSに相当するようです。この頃のレプリケーションの目的に耐障害性の向上はないようです。

Corkboads (1999)

検索システム circa 1999

初期のシステムに対して、キャッシュ・サーバ、広告システム、shardのレプリカが追加されています。

キャッシング

  • キャッシュ・サーバ
    • インデックス結果と文書スニペットの両方をキャッシュ。
    • キャッシュ・ヒット率はだいたい30%-60%。
      • 更新頻度、クエリトラフィックの構成、パーソラナイズのレベルなどの依存してヒット率は変化。
  • 主な利点
    • パフォーマンス！ 10台のマシンで100台や1000台のマシン分の仕事。
    • キャッシュ・ヒットした場合の応答速度の低下。
      • キャッシュにヒットするクエリは人気クエリや計算コストの高いクエリであることが多い。
  • 注意点
    • インデックス更新やキャッシュ・クリア時に応答速度が急に長くなったり、キャパシティ性能が低下する。

クローリング (circa 1998-1999)

  • 単純なバッチ方式クロールシステム。
    • 少数のURLから出発。
    • ページをクロール。
    • リンクを抽出し、キューに追加。
    • 十分なページを収集したら停止。
  • 問題点
    • リンクをたどりにくいサイトを収集できない。
    • 未クロールページの優先度付け。
    • 未クロールURLのキューの効率的な管理。
      • 1つの解：キューを複数のサーバに分割して格納する。
    • マシン障害の扱い。

インデキシング (circa 1998-1999)

  • 単純なバッチ方式インデキシング・システム
  • 完全なチェックポイント方式が無いため、マシン障害が致命的。
  • 生データのチェックサムが無いため、ハードウェアのビット誤りによる問題が発生。
    • 初期のマシンはECCやパリティといった誤り訂正機構が無いため、問題がより悪化した。
    • 1TBのデータをソートすると、パリティなしだと「だいたいソート」された結果が得られた。
    • この結果をもう一度ソートすると、別の「だいたいソート」された結果が得られた。
  • 信頼できないメモリ上でのプログラミング
    • この問題に対処するため、Googleでは少数レコードに対するチェックサムを持ち、壊れたレコードをスキップ・修復できる仮想ファイルを開発した。

1TBのデータを何度ソートしても正しい結果が得られないというのは、なかなか恐ろしい話です。

インデクス更新 (circa 1998-1999)

  • 1998-1999のインデクス更新 (1月に1回)
    • トラフィックが減るのを待つ。
    • いくつかのレプリカをオフラインにする。
    • 新しいインデックスをそれらのレプリカにコピーする。
    • 更新されたインデックスを参照する新しいフロントエンドを立ち上げ、それらのフロントエンドでサービスを開始する。

インデクス更新 (circa 1998-1999)

  • インデックス・サーバのディスクの有効利用
    • ディスクの外周部はディスク帯域が大きい。そこで、サービス中のインデックスはディスクの外周部に配置しておく。
  1. 新しいインデックスをディスクの内周部にコピーする。この時、旧インデックスはサービス中とする。
  2. 新しいインデックスを使うようにインデックス・サーバを再起動する。
  3. 旧インデックスを削除する。
  4. 新インデックスをディスクの外周部に再コピーして、こちらのインデックスを使うようにする。
  5. 最初にコピーした内周部の新インデックスを削除する。
  6. ディスクの内周部は空となるので、性能を向上させるためのデータ構造などを格納する。例えば、ペア・キャッシュを格納する。ペア・キャッシュは「new」と「york」などの頻繁に共起する単語のAND検索結果の文書リストを保持するキャッシュである。

さらっと、ディスクの外周部と内周部を使い分けていると述べてありますが、どうやって制御しているのでしょうか？ （追記）id:kzkさんに教えて頂きましたが、「通常、HDDでパーティションを半分に切ると、前は外周部、後ろは内周部になる、はず」だそうです。意外に簡単にできるんですね。

ペア・キャッシュが有効な理由は、転置インデックスではヒットした文書数で計算コストが決まり、しかも、AND検索ではヒット数の多い単語の計算コストが支配的になるためです。例えば、「new」で1万件ヒット、「york」で1000件ヒット、「new」「york」のAND検索で100件ヒットの場合、ペア・キャッシュを導入すると「new」「york」のAND検索の計算コストはざっくり100分の1ぐらいになります。

Google データセンタ (2000)

扇風機が見えます。

Google (新データセンタ 2001)

空っぽだったマシンルームが、たった3日でラックで一杯になっています。

続き