[2009 WSDM] 大規模情報検索システム構築の課題

情報検索システムの主要な次元とトレードオフ

• システム設計では、次のような要素間のエンジニアリング上のトレードオフをバランスよく考慮する必要があります。
  • インデックス化された文書数
  • 1秒あたりに処理するクエリ数 (QPS)
  • インデックスの鮮度/更新速度
  • クエリ遅延時間 (Latency)
  • 各文書について保存される情報量
  • スコア計算/検索アルゴリズムの複雑さ/コスト
• エンジニアリングの難易度は、これらのパラメータの積に比例する傾向があります。
• これらすべての要素は、全体性能およびコスト対性能（1ドルあたりの性能）に影響します。

システム規模の変化 (1999 vs 2009)

• この10年間で、システム規模と性能要件は劇的に変化しました。
  • #文書: 約7,000万件 → 数十億件（約100倍増）
  • 1日あたりの処理クエリ数: （約1000倍増）
  • 文書あたりのインデックス情報: （約3倍増）
  • 更新遅延時間: 数か月 → 数分（約10000倍減）
  • 平均クエリ遅延時間: <1秒 → <0.2秒（約5倍減）
  • システム資源: より多くのマシン * より高速なマシン（約1000倍増）
• これらのパラメータは継続的に、時には桁違いに変化するため、システム設計は絶えず進化する必要があります。
  • ある時点(X)で適切だった設計が、10倍、100倍の規模ではまったく不適切な設計になり得ます。（したがって約10倍の成長を見込んで設計しつつ、100倍になる前に再実装を計画すべき）
  • この10年間で7回の大規模な改修がありました。

初期システムアーキテクチャ (1997-1999)

• 研究プロジェクト段階 (1997):
  • フロントエンドWebサーバーがクエリを受け取り、インデックスサーバー群と文書サーバー群に分散処理を依頼
  • インデックスサーバー: 文書ID(docid)基準のシャーディング(sharding)
  • 文書サーバー: 文書ID(docid)基準のシャーディング
• 基本原則:
  • 文書には整数ID（docids）を割り当てる（重要/高品質な文書には小さいIDを付与）
  • インデックスサーバー: （クエリ）→ ソート済みの（スコア, docid, ...）リストを返す。docidベースでシャーディングし、容量確保のため複製(replication)する。コストは O(#クエリ * インデックス内の#文書)。
  • 文書サーバー: （docid, クエリ）→ （タイトル, スニペット）を生成。docid → ディスク上の文書全文にマッピング。docidベースでシャーディング。コストは O(#クエリ)。
• サービングシステム (1999):
  • 研究プロジェクト構造にキャッシュサーバーと広告システム連携を追加
  • インデックス/文書サーバーのシャード複製(Replicas)を運用
  • キャッシュ: インデックス結果と文書スニペットの両方をキャッシュ。キャッシュヒット率は30-60%。性能向上とクエリ遅延時間の低減に大きく寄与。（ただし、インデックス更新/キャッシュフラッシュ時に大きな遅延時間スパイクが発生し得る点に注意）

インデックスパーティショニング戦略

• 文書基準 (By doc): 各シャードが文書の一部のインデックスを持つ（Googleの選択）
  • 長所: シャードごとに独立してクエリ処理できる、追加の文書別情報を保持しやすい、ネットワークトラフィック（要求/応答）が少ない
  • 短所: すべてのシャードがクエリを処理する必要がある、K語クエリに対してN個のシャードで O(K*N) のディスクシーク(seek)が必要
• 単語基準 (By word): 各シャードが全体文書に対する単語の一部のインデックスを持つ
  • 長所: K語クエリは最大K個のシャードだけが処理し、O(K) のディスクシーク
  • 短所: はるかに高いネットワーク帯域が必要（マッチした文書の単語別情報を1か所に集約する必要がある）、文書別情報の保持が難しい

初期クローリングとインデクシング (1998-1999)

• クローリング:
  • シンプルなバッチクローリングシステム: 開始URLリスト → ページをクロール → リンクを抽出してキューに追加 → 十分なページを収集したら停止
  • 検討事項: 特定サイトの過負荷防止、未クロールページの優先順位決定（例: PageRank）、未クロールURLキューの効率的な管理、マシン障害への対応
• インデクシング:
  • シンプルなバッチインデクシングシステム: 単純なUnixツールベース
  • 問題点: チェックポイントがないためマシン障害時の復旧が大変、元データのチェックサム不在によりハードウェアのビットエラー問題が発生（初期マシンにECC/パリティがなかったことで悪化し、「ほぼソート済み」問題が発生）、"敵対的なメモリとプログラミング"を経験
  • 解決策: 小さなレコード用チェックサムを保存し、破損したレコードをスキップ/再同期できるファイル抽象化を開発

インデックス更新方式 (1998-1999)

• 周期: 月1回程度
• 過程:
  1. トラフィックの少ない時間帯まで待機
  2. 一部の複製をオフラインに切り替え
  3. 新しいインデックスをオフライン複製にコピー
  4. 更新済みインデックスを指す新しいフロントエンドを起動し、一部のトラフィックを処理
• インデックスサーバーのディスク活用戦略:
  • ディスクの外周部(outer part)はより高い帯域を提供
  1. （既存インデックスをサービス中に）新しいインデックスをディスク内周部(inner half)にコピー
  2. 新しいインデックスを使うよう再起動
  3. 既存インデックスを削除
  4. 新しいインデックスをより高速な外周部(faster half)へ再コピー
  5. 内周部にコピーしていた最初の新インデックスを削除
  6. 空いた内周部領域を性能向上用データ構造（例: Pair cache - 一緒に頻出するクエリ用語ペアのポスティングリスト積集合結果を事前計算）構築に活用

成長への対応と拡張 (1999-2001)

• '99、'00、'01年にインデックスサイズとトラフィックが急増（約5,000万 → 10億ページ超、月20%のトラフィック増加 + Yahoo提携で一晩でトラフィックが2倍になるなど）
• インデックスサーバー性能が極めて重要に: 継続的なマシン増設 + 毎月10-30%のソフトウェアによる性能改善が必要
• 拡張方法: より多くのシャード(Shards)と複製(Replicas)を追加
• 示唆:
  • シャード応答時間はディスクシーク回数と読み込むデータ量の影響を受ける
  • 性能改善の余地: より良いディスクスケジューリング、改良されたインデックス符号化

インデックス符号化技術の進化

• 初期符号化 ('97): 非常に単純なバイト整列形式 (WORD → [docid+nhits:32b, hit:16b, hit:16b...])。ヒット(hit)は位置 + 属性（フォントサイズ、タイトルなど）。大きなポスティングリスト用にスキップテーブルを追加。デコードは低コストだが圧縮率が低く、多くのディスク帯域を必要とする。
• さまざまな符号化手法:
  • ビットレベル: Unary, Gamma, Rice_k (Golombコードの特殊ケース), Huffman-Int
  • バイト整列: varint（1バイトあたり7ビット + 継続ビット）
• ブロックベースのインデックス形式: 空間とCPU使用量の両方を削減（約30%サイズ減）、デコード速度も向上。可変長ブロックを使用。ヘッダー（デルタ、長さなど） + 文書IDデルタ(Rice_k) + ヒット数(Gamma) + ヒット属性（ランレングス Huffman） + ヒット位置(Huffman-Int)。
• 新しいインデックス形式 (2004以降): 単一のフラットな位置空間を使用。補助データ構造で文書境界を追跡。ポスティングリストはデルタ符号化された位置リスト。コンパクトさと非常に高速なデコード速度の両方が重要。

インメモリインデックスシステム (2001年初頭)

• 背景: シャーディングの拡張 + 複製増加 → インデックス全体のコピーをメモリ上に保持できるだけの総メモリを確保可能に
• アーキテクチャ: フロントエンド → ロードバランサー(bal) → シャード（シャードごとに複数のインメモリインデックスサーバー複製）
• 長所: スループット(throughput)が大幅増、遅延時間(latency)が大幅減（特に以前はGB単位のディスクI/Oが必要だった複雑なクエリが高速化 - 例: "circle of life"）
• 問題点:
  • ばらつき(Variance): 数十台ではなく数千台のマシンを使うことで、予測が難しくなる（例: ランダムなcronジョブが問題を引き起こす）
  • 可用性(Availability): 各文書インデックスデータの複製数が1個または少ない → "死のクエリ"（全バックエンドが同時ダウン）、マシン障害時のインデックスデータ可用性問題（特に重要文書は複製が必要）

後期システム設計と技術 (2004年以降)

• ハードウェア: より大規模なデータセンター、自社設計ラック、PC級マザーボード、低価格ストレージ/ネットワークハードウェア、Linux + 自社開発ソフトウェア
• サービング設計 (2004 Edition): 階層構造
  • Rootサーバー → Parentサーバー群 → Leafサーバー群（GFSからFile Loader経由でRepository Shardをロード）
  • キャッシュサーバー連携

Group Varint 符号化

• アイデア: Varintデコードの非効率性（多くの分岐/シフト/マスク演算）を解決。4個の整数値を1グループとして5〜17バイトに符号化。
• 方式:
  • 各値のバイト長（1〜4バイト）を表す2ビットタグ4個をまとめ、1バイトの接頭辞(prefix)バイトを生成。
  • 接頭辞バイトの後ろに実データバイトを保存。
• デコード: 接頭辞バイトを読み、それをインデックスとして事前計算済みの256エントリテーブルを参照 → オフセットとマスク情報を取得し、4個の値を一度にデコード。
• 性能: 既存方式よりはるかに高速（Group Varint: 約400M/秒, 7-bit Varint: 約180M/秒, 30-bit Varint w/ 2-bit len: 約240M/秒）

ユニバーサル検索 (2007)

• Web検索結果だけでなく、さまざまな種類の情報（画像、地域情報、ニュース、動画、ブログ、書籍など）を統合して表示するシステム。
• Super rootノードが複数の専門検索システム（垂直検索エンジン）にクエリを送り、結果を集約。

低遅延クローリングとインデクシングの課題

• 数分以内に更新を反映するのは非常に難しい課題。
• クロールヒューリスティック: どのページをクロールするか?
• クロールシステム: ページを高速にクロールする必要がある。
• インデクシングシステム: PageRank、アンカーテキストなどのグローバル(global)データに依存 → リアルタイム近似(online approximation)が必要。
• サービングシステム: クエリ処理中に更新を受け入れられるよう準備されている必要がある（バッチ更新システムとは大きく異なるデータ構造が必要）。

実験の重要性とインフラ

• 実験のしやすさ: 非常に重要（迅速な実験サイクル → より多くの実験 → より多くの改善）。
• 実験の種類:
  • 容易な実験: 既存データの重み調整など。
  • 難しい実験: 運用インデックスに存在しない新しいデータが必要。（新データの生成/統合と、実験での利用が容易であるべき）
• 中核インフラ:
  • GFS: 大規模分散ファイルシステム
  • MapReduce: 大規模データ処理ジョブを容易に記述/実行。（運用インデックスデータ生成を高速化し、一時的な実験を迅速に実施）
  • BigTable: 半構造化(semi-structured)ストレージシステム。（文書別情報へのオンライン/効率的アクセス、複数プロセスによる非同期な文書情報更新が可能 - 時間単位 → 分単位更新に重要）

実験サイクルとリリース

1. アイデア立案とオフライン実験:
   • MapReduce、BigTableなどでデータを生成。
   • オフライン実験を実行し、効果を検証（人手評価クエリセット、ランダムクエリセットなど）。
   • この段階ではプロトタイプの遅延時間/スループットは重要ではない。
   • 実験結果に基づいて反復改善。
2. ライブ実験:
   • オフライン実験結果が良ければ、実ユーザートラフィックの一部(tiny sliver)を対象にライブ実験を実施（主にランダムサンプル、時には特定クエリクラスを対象）。
   • この段階ではスループットより遅延時間が重要! 実験フレームワークは本番環境の遅延時間に近く動作する必要がある。
3. 性能チューニングとリリース:
   • ライブ実験結果が良ければ、全負荷で実行可能にするため性能チューニング/再実装を行う（例: 実行時計算の代わりにデータを事前計算する、"十分に良いなら"より安価な近似値を使う）。
   • リリース(Rollout)プロセスが重要: 品質 vs コストのトレードオフを継続的に考慮し、迅速なリリースと低遅延/サイト安定性のバランスを取る（検索品質チームと性能/安定性担当チームの良好な協業が必要）。

将来の方向性と課題

• 多言語情報検索 (Cross-Language IR): 世界中のすべての文書をすべての言語に翻訳 → インデックスサイズが急増し、計算コストも高い。（翻訳品質の継続的改善、より大きく複雑な言語モデルを扱う大規模システムが必要）
• 情報検索システム内のアクセス制御リスト (ACLs): 個人/半個人/広く共有/公開文書が混在する環境。（サイズが大きく異なるACLを効率的に処理するシステム構築が必要 - 10人共有の文書と全世界共有の文書では最適解が異なり、共有パターンも時間とともに変化し得る）
• 効率的なIRシステムの自動構築: 現在は用途別に複数のシステムを使用（超高速更新用、超大規模文書用など）。（パラメータを入力すると、その要件に合った効率的な検索システムを自動構築できる単一システムを開発できるか?）
• 半構造化データからの情報抽出: 明確なセマンティックラベルを持つデータはごく少数。テーブル、フォームなどの半構造化データは豊富。（非構造化/半構造化ソースから構造化情報を抽出するアルゴリズム/手法の改善が必要 - ノイズは多いが冗長性を活用し、複数ソースの情報を関連付け/結合/集約する能力が重要）

結論

• 大規模情報検索システムの設計と構築は、挑戦的であり、かつ非常に面白い作業です。
• 新しい検索技術は、しばしば新しいシステム設計を必要とします。