Webクローラーの設計

要件と規模の見積もり

まず何を作るかを固定します。設計面接では要件を自分で狭めるのが最初の得点源です。ここでは「検索エンジンのインデックス用に、公開Webページを大規模に収集するクローラー」を対象とし、以下を仮定します。

機能要件: シードURLから出発しHTMLを取得、リンクを抽出して再帰的に巡回する。robots.txt を尊重する。同一コンテンツの重複取得を避ける。ページの再クロールで鮮度を保つ。非機能要件: スケーラブル（数十億ページ）、礼儀正しい（サーバーを過負荷にしない）、頑健（不正HTML・無限空間で落ちない）、拡張可能（画像やPDFなど新種を後から足せる）。

規模をフェルミ推定で桁まで出します。目標を「10億ページ/月」とします。

この桁感が後の判断を支配します。400〜800 QPS は1台では到底さばけず、ストレージも単一ノードに載りません。ゆえに最初から分散・水平スケール前提で設計します。逆に、レイテンシ要件は緩い（リアルタイム応答不要のバッチ処理）ので、スループットと堅牢性に全振りできる、という判断が立ちます。

大枠の設計

全体はキュー（URLフロンティア）を心臓に据えたパイプラインです。BFS（幅優先探索）を採る理由は、DFSだと1サイトの深部へ潜り込んで礼儀正しさを壊しやすいのに対し、キューによるBFSは自然に浅く広く辿り、優先度制御も差し込みやすいからです。

[シードURL] → URLフロンティア（優先度つきキュー群）
                   │ dequeue
                   ▼
        DNSリゾルバ（キャッシュ付き）
                   ▼
        ダウンローダ（非同期HTTP取得・robots遵守）
                   ▼
        コンテンツ保存（生HTML → オブジェクトストレージ）
                   ▼
        パーサ（HTML解析・リンク抽出）
                   ▼
   ┌── コンテンツ重複検出（SimHash / ハッシュ）
   └── URL重複検出（ブルームフィルタ「URL Seen?」）
                   │ 新規URLのみ
                   ▼
        フロンティアへ再投入（ループ）

データモデルの中心は3つです。URLフロンティア（未取得URLを優先度・ドメイン別に保持）、訪問済みインデックス（URLと簡易フィンガープリント）、ページストア（生HTML＋メタ）。フロンティアの取り出しは「どのドメインを・いつ・どの優先度で」引くかを内包した擬似コードで表せます。

def crawl_loop(worker):
    while True:
        url = frontier.dequeue()        # 礼儀正しさを満たすURLだけ返る
        if not robots.allowed(url):     # robots.txt（キャッシュ済み）
            continue
        ip = dns.resolve(url.host)      # DNSキャッシュ参照
        html = downloader.fetch(url, ip, timeout=10)
        page_store.save(url, html)
        if content_seen.is_duplicate(html):   # SimHash 近似重複
            continue
        for link in parser.extract_links(html):
            norm = normalize(link)             # 正規化（後述）
            if not url_seen.contains(norm):    # ブルームフィルタ
                url_seen.add(norm)
                frontier.enqueue(norm, priority_of(norm))

各段を独立プロセスにし、フロンティアを共有キュー（分散メッセージキュー）にすれば、ダウンローダとパーサを別々に水平スケールできます。処理特性が違う（ダウンローダはI/O待ち主体、パーサはCPU主体）ため、段を分けて別々に増やせることがこの構成の勝ち筋です。

主要コンポーネントの深掘り

URLフロンティアと礼儀正しさ。単一のFIFOでは礼儀正しさを守れません。同一ドメインへの同時多発アクセスを避けるため、Mercatorが示した二段キュー構成が定番です。前段（フロントキュー群）を優先度別に並べ、後段（バックキュー群）を1キュー＝1ホストに固定します。各バックキューにはヒープで「次に叩いてよい時刻」を持たせ、直前の応答時間や robots.txt の Crawl-delay からドメイン別レートを算出します。これにより「重要ページを優先しつつ、どのサーバーにも一定間隔でしか触れない」を同時に満たせます。ワーカ数がホスト数を超えても、同一ホストは1本のバックキューに直列化されるため過負荷が起きません。

重複URL検出。数十億URLを訪問済み判定するのに、全URLをハッシュセットで持つとメモリが破綻します。ここでブルームフィルタが効きます。偽陰性ゼロ（「未訪問」と言えば本当に未訪問）で偽陽性のみという非対称性が、クローラーに理想的です。偽陽性は「実は新規なのに訪問済みと誤判定」してそのURLを捨てるだけで、致命傷になりません。要素あたり約10ビットで偽陽性1%弱に抑えられるので、10億URLでも約1.2GB程度に収まります。判定前にURLを正規化（スキーム小文字化、既定ポート除去、フラグメント削除、クエリ順序整列、末尾スラッシュ統一）することが、無駄な重複を根本から減らす前処理として重要です。

コンテンツ重複と近似重複。別URLが同一・ほぼ同一の中身を返すことは頻繁にあります（ミラー、印刷用ページ、パラメータ違い）。完全一致はコンテンツのSHA-256などで弾けますが、広告やタイムスタンプだけ違う近似重複はハッシュでは捕まりません。そこでSimHashを使います。文書を特徴語のハッシュから1本の指紋（例 64ビット）に落とし、指紋間のハミング距離が小さいほど内容が近いという性質を利用します。距離が閾値（例 3ビット）以下なら重複とみなし、インデックスから外します。

優先度と鮮度。すべてを同頻度で再クロールするのは無駄です。ページの重要度（被リンク数・PageRank的スコア）と変更頻度は相関しないため、両者を分けて扱います。優先度はフロントキューの選択確率に反映し、鮮度は「変更が観測された頻度」からポアソン過程的に再訪間隔を推定して、よく変わる重要ページほど短周期で再取得します。HTTPの Last-Modified / ETag と条件付きGET（If-Modified-Since）を使えば、変わっていないページは304応答で本文取得を省け、帯域を大きく節約できます。

ボトルネックとトレードオフ

横にスクロール

DNSが最初の隠れた壁。ホスト名解決は同期的だと1件あたり数十msかかり、400 QPSでは解決だけで詰まります。対策は、TTLを見つつ積極的にキャッシュするローカルDNSキャッシュと、複数リゾルバへの並行問い合わせです。DNSを軽視した設計は、コードが正しくてもスループットが出ません。

I/O待ちとスループット。ダウンローダの時間の大半はネットワーク待ちです。スレッドを1接続1本で増やすとメモリとコンテキストスイッチで頭打ちになるため、非同期I/O（イベントループ）で1ワーカが数千接続を多重化するのが定石です。ここでCPU律速のパーサと分離しておくと、それぞれを最適な台数・機種で増やせます。

分散クローラーの協調。数百ノードで走らせるとき、URL空間をどう分割するかが核心です。ホスト名のハッシュでノードを決めるコンシステントハッシュ法を使えば、ノード追加・故障時の再配置を最小化しつつ、同一ホストは常に同一ノードへ集約できます。この集約が礼儀正しさを分散環境でも成立させます（ホスト別レート制御が1ノード内で完結する）。フロンティアの永続化と各ノードの担当範囲はシャーディングで分け、データベースのシャーディング戦略と同じ原理でホットスポットを避けます。

一貫性と可用性のトレードオフ。分散フロンティアは厳密な整合より可用性を優先します。同一URLが稀に2ノードで取得されても、コンテンツ重複検出が後段で吸収するため実害は小さい——これはCAP定理でいうAP寄りの割り切りです。逆に「訪問済み集合」を全ノードで強整合にしようとすると調整コストで失速するので、各ノードにローカルなブルームフィルタを持たせ、緩やかに突き合わせる設計が現実的です。フロンティアへの投入を確実に一度届けたい部分では、メッセージキューの配信保証の考え方（at-least-once＋冪等な重複排除）がそのまま効きます。

まとめ