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

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第3回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2004年から2007年ぐらいまでの検索システムの紹介とインデックスの符号化方式、検索精度を向上させるための実験環境についての紹介となります。個人的には分岐処理を徹底的に排除したGoogleの最新の符号化方式が興味深かったです。イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。

第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１） - llameradaの日記
第2回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（２） - llameradaの日記

サーバ設計 2004年版

2001年のサーバ構成から大きく変更されています。検索サーバはペアレント・サーバとリーフ・サーバの木構造となっています。これは、リーフサーバの数が増えたため、サーバの階層構造を2層構造から多層構造にする必要が生じたためでしょう。

インデックスは分散ファイルシステムであるGFSに格納され、File LoaderがGFSからリーフサーバ上のレポジトリshardsにインデックスをコピーするモデルとなっています。おそらく、GFSにインデックスのマスタを格納しておき、リーフサーバがスレーブの役割になるのでしょう。マスタ・スレーブの対応関係は制御するため、File Loaderに指示を出すレポジトリ・マネージャーが導入されているようです。

新しいインデックス形式

  • ブロック・インデックス形式は2段階のスキーマを利用していた。
    • 各hitは（docid. 文書中の単語位置）のペアとして符号化される。
    • docidの差分値はライス符号で符号化される。
    • 圧縮率は非常に良かったが（元々はディスクベースのインデックス向けに設計されたため）、復号処理がCPUに負担をかけるため復号処理が遅かった。
  • 新形式：単一のフラットな単語位置空間
    • 文書の境界は別のデータ構造で記録する。
    • ポスティング・リストとは差分値を符号化した単語位置のリストとする。
    • コンパクトであることが必要（1つの単語位置を格納するのに32bitは提供できない）。
    • しかし、復号処理は非常に高速である必要がある。

従来のインデックスでは単語位置毎にdocidを保持していたので、このdocidが色々と無駄だったようです。例えば、ある単語Wが文書Dの3番目と5番目に出現した場合、(D, 3)と(D, 5)を格納するためDを2回格納することになります。ただ、このページの記述は前のブロックインデックスの記述と整合がとれていない気がするので、なにか勘違いしているかもしれません。

バイト整列された可変長符号

  • 可変長符号
    • 各byteは7bitのデータと継続bitで構成される。
    • 欠点：復号処理で大量の分岐処理・シフト演算・マスク処理が必要。
00000001  00001111  11111111  00000011  11111111  11111111  00000111
========  ========  ==================  ============================
   1         15             511                     131071
  • アイデア：バイト長を下位2bitに符号化
    • 良い点：分岐処理、シフト演算、マスク処理が少ない
    • 欠点：値の上限が30bitに制限される。また、以前としてデコード処理にシフト演算が必要。
00000001  00001111  01111111  00000011  10111111  11111111  00000111
========  ========  ==================  ============================
   1         15             511                     131071

可変長符号はバイト単位符号なので、bit単位符号よりは復号は高速です。しかし、可変長符号の復号には、（bit単位符号よりは少ないですが）分岐処理・シフト演算・マスク処理が大量に必要であり、これらの処理はCPUの高速化の恩恵を受けにくいため、やはり復号速度が問題となります。特に分岐処理はパイプライン・ハザードのコストの高いCPUにとっては鬼門です（参考：パイプライン処理 - Wikipedia）。そのため、なるだけ分岐処理の少ない、すなわちif文が少ない符号の方が復号処理は高速になります。最初の符号と改善された符号を見比べると、青い領域の数が7個から4個に減っています。青い領域毎に分岐処理・シフト演算・マスク処理が必要となるため、改善後の符号の方が高速に復号できるわけです。

グループ可変長符号

  • アイデア：1つ1つ整数を符号化するのではなく、4つの整数をまとめて5-17バイトに符号化する。
    • 2bitのバイト長を4つまとめて先頭バイトとする。
00000001  00001111  01111111  00000011  
10111111  11111111  00000111
                              ↓
00000110  00000001  00001111  11111111  00000011  
========  ========  ========  ==================  
  tag        1         15             511            

11111111  11111111  00000001
============================
            131071
  • 復号処理：先頭バイトを読み込み256個のエントリがあるテーブルを参照する。
...
00|00|01|01 => Offsets: +1,+2,+3,+5; Masks: ff000000,ff000000,ffff0000,ffff0000
00|00|01|10 => Offsets: +1,+2,+3,+5; Masks: ff000000,ff000000,ffff0000,ffffff00
00|00|01|11 => Offsets: +1,+2,+3,+5; Masks: ff000000,ff000000,ffff0000,ffffffff
00|00|10|00 => Offsets: +1,+2,+3,+6; Masks: ff000000,ff000000,ffffff00,ff000000
...
  • 他の手法よりも復号処理は非常に高速
    • バイト毎に7ビット：1秒間に180Mレコード
    • 30ビット制限 + 2bitバイト長：1秒間に240Mレコード
    • グループ：1秒間に400Mレコード

なかなか思いつかない方式です。2ビットのバイト長を4つまとめて先頭バイトに格納することで分岐処理を完全に無くしています。従来方式ですと先頭bit毎に処理を分岐していたのが、先頭バイトの値から4つのOffsetとMaskの組をテーブルから取得して、各Offsetから4バイト読み込みMaskをかけるだけとなります。また、シフト演算もなくなっています。分岐処理とシフト演算をなくし、また、マスク処理の回数を減らすことにより1.7倍の高速化を実現しています。また、この符号ですと値の30bit制限はなくなります。ただし、符号サイズは例からも分かるように最大25%増加します。非常に興味深い方法なので特許の問題がなければOSSの全文検索エンジンなどで試したいところです。

2007：ユニバーサル・サーチ

フロントのWebサーバの配下にスーパー・ルートが存在し、その配下にWeb, Image, Blogsといった専門検索サーバ群が配置され、最下層にインデックスを作成するインデックス・サービスが存在しています。

それをインデックスしてくれって？ 1分待ってくれ！

  • 短時間でのクロールおよびインデックスは大変。
    • クロール・ヒューリスティクス：どのページをクロールすべきか？
    • クロール・システム：ページを素早くクロールすることが必要。
    • インデックス・システム：グローバルデータに依存する。
      • ページランク、そのページを指しているページのアンカーテキストなどなど。
      • これらのグローバル属性値をオンラインでの近似が必要。
    • 検索サーバ・システム：検索要求処理中に更新できるようにしておくことが必要。
      • オンライン更新用のデータ構造はバッチによる更新とは全く異なる。

最初の方のスライドにあるように10年間で最も進化した指標の1つがインデックスされるまでの時間です。ページをアップロードするとすぐにクローラがやってくるのは当たり前のようですが、実現するのは非常に大変です。

情報検索システムにおける柔軟性と実験

  • 実験が容易であることは非常に重要。
    • 実験の所要時間が短い => たくさんの実験 => より多くの改善
  • いくつかの実験は簡単にできる。
    • 例えば、既に存在するデータの重みを変える場合。
  • それ以外の実験は実行するのがより大変：現在のインデックスに存在しないデータが必要。
    • 新しいデータを作り出して組み込み、そのデータを使って実験することが簡単であることが必要。

これより数ページ、ランキング・アルゴリズムを向上させるための実験インフラ・実験方式の紹介が続きます。

検索システムのためのインフラ

  • インフラのキーとなるパーツ
    • GFS: 大規模分散ファイルシステム
    • MapReduce：大規模なジョブを簡単に作成・実行
      • 商用のインデックスを短期間で作成
      • アドホックな実験を迅速に実行
    • BigTable：半構造化ストレージシステム
      • 文書毎の情報への任意の時間でのオンラインで高速なアクセス。
      • 複数のプロセスが文書毎の情報を非同期に更新可能。
      • 文書を数時間ではなく数分で更新する場合には非常に重要。

実験サイクル パート1

  • 新しいランキングのアイデアからスタート。
  • 実験を実行するのが簡単で、高速に実行するのも簡単でないといけない。
    • MapReduceã‚„BigTableのようなツールをつかってデータを作成する。
    • 最初はオフラインで実験を実行し、そのアイデアの効果を確認する。
      • 様々な種類の人手で重要度が付けられたクエリセットでの効果。
      • 既存のランキングへの影響を調べるためのランダムなクエリセットでの効果。
    • 応答速度とスループットはこのプロトタイプでは気にしない。
  • 実験結果に基づいて、アイデアの練り込みと実験を繰り返す。

実験サイクル パート2

  • いったんオフラインでの実験結果が有望であったならば、ライブ実験の実行を求める。
    • ユーザートラフィックのごく一部を使った実験。
    • 通常はランダムサンプリング。
      • ただし、しばしば特定のクラスのクエリのみをサンプルとして選ぶ。
        • 例えば、英語のクエリ、地名の含まれたクエリ、などなど。
  • この時、スループットは重要ではないが応答速度は問題！

実験結果は良好だった。次は?

  • ローンチ！
  • 全トラフィックに耐えられるように性能チューニングと再実装を行う。
    • 例1) 実行時にデータを計算するのではなく事前に計算しておく。
    • 例2) 「十分良い」がより底コストな近似手法に置き換える。
  • ロールアウト・プロセスは重要
    • 絶え間ない「質」と「コスト」のトレードオフ
    • 素早いロールアウトは、サイトの安定性と短い応答速度とは両立しない。
      • 検索品質グループとシステムを高速・安定にするグループとの間に良好な関係を築くことが必要。

続き