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

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第2回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2000年から2001年ぐらいまでの検索システムの一部の紹介となっています。個人的には転置インデックスの詳細な符号化方式が公開されているのが印象に残りました。Googleにとっては過去のインデックス構造でしょうが、商用の全文検索エンジンの詳細な仕様が公開されるのは珍しい気がします。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。

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

インデックスサイズとクエリ・キャパシティの増加

  • インデックスサイズの急激な増加 (1999年、2000年、2001年・・・)。
    • 5千万ページから10億ページ以上に。
  • 同時にトラフィックも急激に増加。
    • 毎月20%のトラフィックの成長 (1999年、2000年・・・)。
    • それに加えて新たなメジャーなパートナーと提携。例えば、2000年7月のYahooとの提携はトラフィックを倍にさせた。
  • インデックスサーバの性能が再重要課題だった。
    • マシンを継続的に追加した、しかし、
    • ソフトウェアによる10%から30%の性能改善が毎月必要だった。

毎月10%から30%の性能向上はさすがです。毎月20%の向上とすると、1年で9倍の性能になっている計算になります。

成長への取り組み

成長に伴ってshard数とレプリカ数が拡大していく様子がアニメーションで示されています。

影響

  • shardの応答時間に影響を与える要素。
    • 処理に必要なディスク・シークの回数。
    • ディスクから読み込むデータのサイズ。
  • 大きな性能改善を可能にするのは：
    • ディスクのスケジューリングの改善。
    • インデックス符号の改善。

インデックス符号 circa 1997-1999

  • 最初の符号(1997年)は非常に単純。
    • 先頭はdocidとhit数の32bit。hit数だけ16bitのhitが連続して格納される。以後、この繰り返し。
    • hit: 単語位置 + 属性（フォントサイズ、タイトルか否か、などなど）
    • そのうち、大きなポスティング・リストにはスキップ・テーブルが追加された。
  • 単純でバイト単位のアライメント。
    • 復号は高速だが、そんなにコンパクトではない。
    • 従って、大きなディスク帯域が必要。

以後の符号の話は、転置インデックスになじみがないと分かりにくいと思いますので、転置インデックスのボトルネックについて簡単に説明します。転置インデックスでは、単語毎にその単語が出現した全ての文書情報のリストを保持します。このリストをポスティング・リストと呼びます。ポスティング・リストに保持する情報は様々ですが、1997年のGoogleの場合、単語の文書での出現位置と重要度を保持していたようです。
転置インデックスの処理で最も重い処理の1つが、圧縮して格納されたポスティング・リストの読み込みです。具体的には、圧縮された符号のディスクからの読み込みと、読み込んだ符号の復号が転置インデックスの主要なボトルネックになります。その為、高性能な検索システムを実現するには、圧縮効率が高く復号速度が高速な符号化方式を開発することが必要であり、以後、この話題が数ページ続きます。

符号技術

  • ビット単位符号。
    • アルファ符号：N-1個の"0"の後1を出力。 (例：5,3 => 00001001)
    • ガンマ符号：Nのbit数をアルファ符号で出力。後は値をそのまま出力。(例：5,3 => 00101011)
    • ライス符号：Nを2のK乗で割った商をアルファ符号で出力。余りはそのままKbitで出力。
      • グロム符号の特別な場合。
    • ハフマン整数符号：基本はガンマ符号だが、Nのbit数の符号化にアルファ符号ではなくハフマン符号を用いる。
  • バイト単位符号
    • 可変長符号：バイト毎に7bitを割り当て、残り1bitで次のバイトと連結するか否かを割り当てる。UTF-8の符号化方式とほぼ同じ。
      • 0-127: 1バイト
      • 128-4095: 2バイト

転置インデックスでの符号化の対象は主に非負の整数となります。例えば、単語数が1万の文書の単語の出現位置を格納するには、1から1万までの整数を1万個格納する必要があります。また、転置インデックスに出現する整数は値が小さいことが多いです（そうなるように工夫も加えます）。そのため、値が小さければ小さいほど符号長が短くなる整数符号が採用されます。一般にビット単位符号の方が圧縮率が高いですが、バイト単位符号の方がビット演算やシフト演算が不要なため復号処理が高速です。なお、OSSの検索エンジンですとバイト単位符号の方が実装が容易なためバイト単位の符号を採用していることが多いです。なお、各符号の詳細はWikipediaやManaging Gigabytesを参照してください。


ブロック方式のインデックス形式

  • ブロック方式で、可変長フォーマットはディスクサイズとCPU効率の両面で効果的であった。
    • ポスティング配列の先頭にはもしサイズが大きい場合スキップテーブルを設ける。
    • 各ブロックには次の情報を格納する。なお、文書数をN、hit数をHとする。
      • 先頭のdocidからブロックの最後のdocidまでの差分：可変長符号（ヘッダ領域なのでバイトアライメント）
      • ブロックサイズ：可変長符号（ヘッダ領域なのでバイトアライメント）
      • 符号化方式：ガンマ符号
      • ブロック中の文書数：ガンマ符号
      • (N-1)個のdocidの差分リスト：ライス符号
      • N個の文書毎のhit数リスト：ガンマ符号
      • H個のhit属性：ランレングス・ハフマン符号
      • H個のhit単語位置：ハフマン整数符号
  • インデックスサイズを30%削減すると共に復号速度をより高速化した。

圧縮率・復号速度の向上の為に初期の単純な方式に比べると様々な工夫が凝らされています。まず、ポスティング・リストの基本ですが文書はdocid順にソートされています。そして、docidそのものではなく差分を格納するようになっています。例えば、最初のdocidが4で差分が2,1,3ならば、元のdocidのリストは4,6,7,10となります。このような差分表現の方が、元々のdocidより値が小さくなるため圧縮効率が高くなります。これは、整数符号は値が小さいほど符号長が短くなるためです。
ヘッダ領域は復号を高速化するためバイト単位符号の可変長符号を用いています。それ以外はデータの特性に応じて圧縮率の高い符号が選択されているようです。例えば、hit属性は文書中での単語の重みを表すため、多くの単語ではデフォルト値の1のはずです。そのため、同じ値が連続して出現しやすいデータに向くランレングス符号が使われています。

Ever-Wider Shardingの影響

  • 応答時間を短いまま保つには、インデックスサイズが増加するため、shardの追加が必要。
  • しかし、クエリの処理コストはshard数が増えると増加する。
    • 典型的には1回以上のディスクシークがクエリの1単語、1 shard毎に必要。言い換えると、ディスクシークの回数はO(shard数 * クエリの単語数)。
    • 非常に稀な単語、すなわち、殆どのshardの格納されていない単語でも処理コストは同じ。
  • レプリカの数が増加したので、利用可能なメモリの全体量は増加。
    • そのうち、インデックス全体のコピーをメモリ上に保持するのに十分なメモリ量になった。
      • 多くのシステム設計のパラメータを根本的に変化させた。

2001年の初頭：メモリ内インデックス

各shardがクラスタを構成すると共にshardにバランサーが導入されています。レプリカは示されていませんが、後の記述と合わせると、shard内でより複雑なレプリケーションを行いバランサーがクエリの送り先を調整しているようです。

メモリ内インデックスシステム

  • 多くの利点
    • スループットの大きな増加。
    • レイテンシの大きな減少。
      • 特に検索頻度の少ない単語（例："circle of life"）のレイテンシが減少した。以前は数GBのディスクIOが必要なクエリの処理が非常に速くなった。
  • いくつかの問題点。
    • マシンなどの多様性(Variance)：1つのクエリ処理に、数十台ではなく、数千台のマシンが係わるようになったため、マシンが持つ条件が非常に多様になった。
      • 例えば、マシン毎にランダムなcronジョブは、しばらくGoogleを悩ませた。
    • 可用性：各インデックスデータのレプリカは1個から数個。
      • 「死のクエリ」が全てのバックエンドを一度に落としてしまう。これは非常にまずかった。
      • マシン障害時のインデックスデータ、特に重要な文書の可用性。重要な文書を優先してレプリケートすることで対処した。

インデックスをディスクからメモリに移したため、1台のマシンで保持できるインデクス・サイズが減少しています。そのため、1つのクエリの処理で大量のマシンが必要になると共に、レプリカ数が減ったため、分散システム特有の課題がより全面に出てきています。
「死のクエリ」の説明はないですが、インデックス・サーバに想定外の負荷を与えるクエリと思われます。この頃には様々な検索オプションが利用できるようになっているため、事前に危険なクエリを洗い出すのが難しくなってたのだと思います。

大規模計算

データセンタと思われる写真が掲載されています。このあたりから1つの処理で数千台のマシンを扱うのが日常になっていたのでしょうか。

現在のマシン

  • 独自のラック設計。
  • PCクラスのマザーボード。
  • ローエンドなストレージとネットワーク機器。
  • Linux
  • 独自ソフトウェア

ネットワーク機器もローエンドなのは少し意外でしたが、ネットワーク機器に障害が起きてラック毎落ちても、おそらく全く問題がないのでしょう。
サインが書かれているラックの写真が掲載されています。1ラックについき20個のマザーボードがむき出しで搭載されています。

続き