Googleの分散データ処理言語Sawzallの統計ライブラリをC++, Ruby, Pythonから利用するライブラリSZaruを公開しました

Googleで利用されている分散データ処理言語SawzallのOSS実装 szl が公開されました。


公開されたソースの中にはSawzallの実行環境の他に大規模データ向けの統計ライブラリが含まれています。この統計ライブラリには高度なアルゴリズムが実装されているので、これを他の言語からも利用できると便利だなと思い、C++, Ruby, Pythonから利用できるようにしました。


便利な統計アルゴリズムの1つに出現回数が上位のN件の要素の抽出(top-N)があります。


top-Nを求める具体例としては、自然言語処理でよく使う、出現回数上位の単語を求める処理があります。この処理の単純な実装では、まず全単語の出現回数を求めておき、次に各単語を出現回数の降順でソートして出現回数上位の単語を求めます。しかし、この実装ではユニークな単語数K（数十万から数百万）に比例したメモリと計算量が必要となります。


それにたいしてSawzallの統計ライブラリでは、Nに比例したメモリと計算量*1でtop-Nを求められます。通常 N は K より非常に小さいので非常に少ないメモリで上位要素を求めることができます。そのかわり、ペナルティもあり、厳密なtop-Nではなく誤差を含む推定量となりますが、データ量が大きい場合は誤差は無視できます。*2


公開元は次のページとなります。
SZaru: Porting of excellent Sawzall aggregators.
今のところ有用性が高そうな3つの集計処理(top, unique, quantile)を移植しています。


SZaruの実装の過程でsawzallの内部実装を色々とみてみたのですが、オブジェクトのバイナリ列へのシリアライズが言語レベルで結びついているのが面白かったです。分散処理ではプロセス間でオブジェクトをやり取りするにシリアライズが必須なので、言語レベルで統合されている方が色々と便利なのでしょう。


なお、名前の意味は笊（ざる）になんとなくSをつけてSawzallに近い語感にしてみまいた。名前をつけてから知ったのですがszaruはハンガリー語だとツノの意味みたいです。

*1:厳密にはやや違いますが。

*2:top-Nの推定アルゴリズムはCount-Sketchと呼ばれており日本語での解説記事があります。radiumsoftware.com

レコメンド（推薦）・サービスに一番大切なこと

flickrの写真をクリック履歴から自動的に推薦するサービス「フォト見る」を数日前にリリースしました。さいわい、気に入って頂いた方もいるようです（Route 477(2009-03-12)）。「フォト見る」をリリースしてみて思ったのですが、レコメンド（推薦）を軸としたサービスでは初心者ユーザにいかに使ってもらえるかが一番大切だなと思いました。

ユーザに何かを推薦するには、当たり前ですが、そのユーザの好みを知っている必要があります。例えば、「フォト見る」では、ユーザが過去にクリックした写真から好みを推定しています。ところが、初めてページを訪れたユーザの好みは全く分かりません。1つでも写真をクリックしてくれれば、ユーザの好みが少しでも分かります。ところが、ユーザの好みが分からない状態では推薦は無理なので、初めてのユーザに対してはどうでもよい写真が表示されやすく、写真をクリックしてもらうのがなかなか難しいようです。

つまり、「初めてのユーザに使ってもらう方法」を考えないと、レコメンド・サービスが成功するのは難しそうです。もちろん、この問題は一般のサービスにも共通する課題です。ただ、レコメンド・サービスでは、使ってもらわずにサービスのメリットを分かってもらるのがより難しい気がします。

この問題を解決する1つのアプローチは、最初は一般的に好まれるものを推薦する方法でしょう。現在の「フォト見る」もそうなっています。具体的には、最近クリックされた写真や、よく使われるタグの写真を最初に表示するようになっています。ただ、1画面で8枚程度の写真しか表示されないため、もう少しインパクトが欲しいところです。人気のあるタグのタグクラウドを表示するのもありかもしれません

もう1つのアプローチは、たとえ初めてのユーザでも、手に入る情報を最大限利用して可能な限りのレコメンドを行うことでしょう。例えば、アクセス元やリファラーなどに応じて推薦内容を変える方法が考えられます。ただ、初めのユーザーに関してサービス側で手に入れられる情報は非常に限られるので、どこまでのことが出来るかは疑問の残るところです。

まとめると、レコメンド・サービスでは初めてのユーザに対する推薦が難しいため、まずはサービスを使ってもらうための工夫が必要です。使ってもらうための方法として、一般的に好まれるものを推薦する方法と、初めてのユーザでも手に入る情報を利用して推薦する方法を紹介しました。

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

GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の最終回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は将来の課題についての紹介となります。イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。

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

今後の進化の方向と課題

  • 最後に興味深い方向についていくつか紹介する。

言語をまたがった情報検索

  • 全ての世界の文書を全ての言語へと翻訳
    • インデックスサイズの大幅な増加
    • 高い計算コスト
    • しかし、うまく出来ればユーザにとって巨大な利益
  • 課題：
    • 継続的な翻訳品質の向上
    • より大きくて複雑な言語モデルを扱うための大規模システム
      • 1センテンスの翻訳 => 数TBのモデル上での100万回の参照

統計的な機械翻訳の基本的なアプローチでは、翻訳対象の文の訳となり得る全ての単語列（文）を列挙して、それらの中から最も適切な単語列を選択します。その為、大量の計算が必要であり、大規模化に際して様々な問題を解決する必要があります。

情報検索におけるアクセス制御リスト(ACL)

  • 様々な公開レベル（プライベート、セミプライベート、広く共有、パブリック）が混じった文書に対する検索システム
    • 例：電子メール <=> 10人の共有文書 <=> 10万人のメンバーのグループでのメッセージ <=> 公開Webページ
  • 課題：様々な大きさのACLを効率よく扱える検索システムの構築
    • 10人で共有する文書の対する最適な解は、世界中で共有する文書に対するものとは異なる。
    • ドキュメントの共有パターンは時間と共に変化する。

現在のGoogleの電子メールに対する検索は、電子メールに閉じたものであり、また、その検索方式も一般的なアルゴリズムとなっています。電子メールのようなWebとは異なる文書に対する検索システムの洗練を目指しているように思えます。

効率の良い情報検索システムの自動構築

  • 現在のところ、いくつかの検索システムを使っている。
    • 例えば、あるシステムを1秒以内の更新のために使用し、別のシステムを大量の文書を日単位に更新するために使用している。
    • 共通のインターフェイスだが、主に効率性のため非常に異なった実装となっている。
    • 動作は良好だが、異なるシステムを構築・維持・拡張するのには大きな労力が必要。
  • 課題：パラメータで特性の変えられる単一のシステムにより、パラメータを調整することで効率の良い検索システム自動的に構築できるだろうか？

半構造化データからの情報抽出

  • セマンティックな意味を明確に付与されたデータは、世界中のデータのごく一部。
  • しかし、半構造化されたデータは大量に存在
    • 本やWebページのテーブル、入力フォームの背後に存在するデータ、
  • 課題：未構造化・半構造化された情報源からの構造化された情報の抽出技術・抽出アルゴリズムの向上
    • ノイズが多いが、冗長度も大きい
    • 複数の異なる情報源の関連性をとり、合わせて、集約することを実現したい。

セマンティックWebとは全く異なるGoogleらしいアプローチです。Webページのテーブルからの情報抽出技術は以前より開発されていましたが、複数の情報源の取扱い方法をより洗練させることで、実用レベルまで情報抽出技術を発展させることを目指しているようです。

さいごに

  • 大規模情報検索システムの設計と構築はやりがいのある、楽しい試み
    • 新しい問題には継続的な進化が必要。
    • 多くのユーザに利益をもたらす仕事
    • 新しい検索技術にはしばしば新しいシステムが必要。
  • 傾聴感謝

参考文献

Ghemawat, Gobioff, & Leung. Google File System, SOSP 2003.

Barroso, Dean, & H〓lzle. Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, 2003.

Dean & Ghemawat. MapReduce: Simplified Data Processing on Large Clusters, OSDI 2004.

Chang, Dean, Ghemawat, Hsieh, Wallach, Burrows, Chandra, Fikes, & Gruber. Bigtable: A Distributed Storage System for Structured Data, OSDI 2006.

Brants, Popat, Xu, Och, & Dean. Large Language Models in Machine Translation, EMNLP 2007.

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) 「十分良い」がより底コストな近似手法に置き換える。
  • ロールアウト・プロセスは重要
    • 絶え間ない「質」と「コスト」のトレードオフ
    • 素早いロールアウトは、サイトの安定性と短い応答速度とは両立しない。
      • 検索品質グループとシステムを高速・安定にするグループとの間に良好な関係を築くことが必要。

続き

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個のマザーボードがむき出しで搭載されています。

続き

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日でラックで一杯になっています。

続き

検索キーワードを入力するのが面倒な人向けのflickrの写真を検索するサービス

検索キーワードの入力がいらない、「フォト見る」というflickrの写真を検索するサービスを作りました。気に入った写真をクリックしていくと、クリックされた写真と同じタグの写真が次々と表示されます。例えば、「海」の写真をクリックすると「夕日」や「ビーチ」の写真が表示されるようになります。なにも考えずにクリックしていくだけで、自然と自分の好みにあった写真が出てくる、らくちんな検索サービスを目指しています。

flickrのタグは英語ばかりなので、ちょうどよい検索キーワードを見つけるのは日本人には難しいのですが、「フォト見る」では写真をクリックするだけなので単語の意味が分からなくても大丈夫です。スペイン語やイタリア語・アラビア語のタグがついた写真もかんたんに検索できます。

仕組みは単純なサービスですが、検索キーワードによる検索では、なかなか出会うことのできない写真が見つかるのが楽しいです。

技術的にはレコメンド型サービスの一つになるのかと思います。レコメンドエンジンの練り込みはまだ甘いですが、flickr以外にもtwitterやはてなブックマークにも応用できそうなので、どんどん試してみたいと思っています。