難
Web クローラーを設計せよ
課題
URLのリストを起点にWebをクロールし、『単語→そのページ』の逆引き索引(reverse index)を作る。各ページのタイトルとスニペット(要約)も生成する。ユーザーが検索語を入力すると関連ページを返す。高可用で、無限ループ(同じページを延々クロールし続ける)を避けるのが課題。
制約・前提
- クロール対象は1B(10億)リンク
- ページ更新頻度は平均で週1回(人気サイトはもっと頻繁)
- 1ページ平均500 KB
- 検索は100B(1000億)/月
- 1,600 write req/s(クロール書き込み), 40,000 search req/s
- 無限ループ(サイクル)を避ける、高可用が必須
主要数値
概算（back-of-the-envelope）の出発点。
| クロール対象 | 1B (10億) リンク |
|---|---|
| クロール書き込み | 1,600 write req/s |
| 検索 | 40,000 search req/s |
| 1ページサイズ | 500 KB |
| 総ストレージ | 約500 TB |
| 再クロール間隔 | デフォルト週1回 |
主要数値の可視化
操作別 req/s（対数軸）
write検索
総ストレージ規模
検索が支配的 (25倍) 検索クエリ(40,000/s)がクロール書き込み(1,600/s)を圧倒。500TB の保存と転置インデックスがボトルネック。
まず自分で設計を考えてから、1ステップずつ答え合わせをしましょう。
Step 1: 要件・ユースケース（まだ伏せられています）
考えてみよう（面接官の追加質問）
- robots.txt(クロール禁止指定)や礼儀正しいクロール(同一ドメインへの過剰アクセス防止)はどう実装する?
- signatureはページ全文のハッシュにすべきか、本文だけにすべきか? 広告やヘッダの差をどう扱う?
- 1B URLの重複排除をMapReduceで行うとき、map/reduceそれぞれが何を出力するか具体的に書ける?
- 人気サイトの再クロール頻度を自動で上げたい。何を指標(被リンク数? 更新頻度?)にランクを決める?
- クロール中にworkerが落ちた場合、処理中だったリンクはどう扱う?(ヒント: at-least-once と冪等性)