面接の質問とスコープ
検索インデックスにHTMLを提供する大規模ウェブクローラーを設計してください。100億件の既知のURLを追跡し、1日あたり最大10億件のリクエストを発行できます。URLフロンティア、ホストレベルのPoliteness、重複排除、再クロール、障害復旧、および検証計画を、キャパシティ見積もりを含めて設計してください。
これは、バックエンド、インフラストラクチャ、検索、およびデータプラットフォームのシニアエンジニア向けのシステム設計問題です。出力には、圧縮された生のHTML、取得メタデータ、および新しく発見されたリンクが含まれます。全文検索インデックス作成、検索ランキング、認証が必要なページ、画像や動画、およびデフォルトのJavaScriptレンダリングはスコープ外です。カバレッジはベストエフォートであり、システムがウェブ全体を巡回することを保証するものではありません。
以下の数値は面接用の前提条件であり、本番環境の測定値ではありません。成功したレスポンスボディの平均サイズは200 KBです。1日の取得上限には、成功、304レスポンス、失敗、および再試行が含まれます。平均負荷は1日の上限を完全に使用し、計画ピークは毎秒25,000回の取得です。新しく発見されたURLは60秒以内に永続化されます。キャパシティが利用可能な場合、期限を過ぎた優先度の高いURLの99%が10分以内にリースを受け取ります。ホストのPolitenessは厳格な制約であり、スループットを取り戻すために緩和することはできません。
ある公開された面接レポートでは、クローラーのコードが既に存在し、候補者がスケーラブルなアーキテクチャを設計しなければならない25分間の設計ラウンドが説明されています。2026年の公開システム設計資料でも、分散クローラーを単独の課題として扱っています。1つのレポートだけでは企業の固定された問題バンクや出題頻度を確定できないため、この記事ではこれを代表的なシステム設計問題として扱い、特定の企業との関連付けは行いません。
面接官が評価するポイント
最初のシグナルはスコープと見積もりです。優秀な候補者は、スループットとストレージを計算する前に、クロール対象、鮮度の目標、ダウンストリームのコンシューマ、および障害セマンティクスを定義します。キュー、クローラーワーカー、データベースをすぐに描くだけでは、なぜそれらのコンポーネントが必要なのかを説明したことにはなりません。
2つ目のシグナルは、URLフロンティアのスケジューリング不変条件です。1つのグローバルなFIFOで作業を分散することはできますが、同じホストに対するすべてのコンシューマ間で同時実行数、遅延、およびバックオフを強制することはできません。優れた設計は、「どのホストの準備ができているか？」を「このホストは次にどのURLを取得すべきか？」から分離し、各host_keyにそのトークン状態の論理所有者を1つ割り当てます。
3つ目のシグナルは、3種類の重複を区別することです。すなわち、同じ正規化されたURL、バイト単位で同一のコンテンツを持つ異なるURL、そしてコンテンツにわずかな違いがあるページです。これらにはそれぞれ、正確なURL状態、コンテンツハッシュ、およびニアデュープ（準重複）フィンガープリントが必要です。1つのBloomフィルタでこれら3つの役割すべてを果たすことはできません。
最後のシグナルは障害モデルです。外部からの取得では、タイムアウト、429、5xx、DNSエラー、リダイレクトループ、巨大なレスポンス、悪意のあるページとの遭遇が避けられません。優れた回答は、少なくとも1回（at-least-once）の実行を受け入れ、リース、バージョン条件付き書き込み、および冪等な完了によって重複する副作用を制限し、設計を反証しうるテストとメトリクスを提案します。
回答前に明確にすべき質問
- 何が出力を消費するのか？ 検索インデックスには、HTML、取得時刻、ステータス、および正規化されたURLが必要です。アーカイブには不変のバージョンも必要です。トレーニングコーパスでは、品質とライセンスのフィルタが重視されます。この問題では、出力は検索インデックスにのみ送信されます。
- どのようなコンテンツが対象か？ この設計では、公開されているHTTP/HTTPSのHTMLを取得します。PDF、メディア、認証されたセッション、またはJavaScriptレンダリングを対象に含めると、フェッチャー、パーサー、コストモデル、およびセキュリティの分離が変化します。
- カバレッジと鮮度のトレードオフをどうするか？ 既知の100億件のURLのうち、この問題では1億件の高価値URLを毎日更新し、残りの99億件については30日間隔を目標とします。すべてのページを毎日更新することは、1日あたり10億回の取得というバジェットと数学的に両立しません。
- どの境界でPolitenessを強制するか？ 設計では
scheme + authorityからhost_keyを形成し、そのキーに対してrobotsポリシー、同時実行数、最小遅延、およびサーバー指示によるバックオフを一元管理します。個別に合意された許容量は、そのホストのポリシーのみを変更し、グローバルな不変条件は変更しません。 - 「重複なし」はどれほど厳格か？ URLディスカバリーは、Bloomフィルタの偽陽性によってURLを暗黙的に失ってはならないため、永続的な一意キーが信頼できる情報源（source of truth）となります。ネットワーク取得は繰り返される可能性がありますが、ストレージとダウンストリームのイベントは冪等でなければなりません。
- 削除されたページや失敗したページはどれくらい保持されるか？
404、410、繰り返される失敗、および一時的な5xxには、異なる再訪問間隔が必要です。この設計では、再発見によって新しいURLが作成されないように、トゥームストーンと最新のステータスを保持します。
30秒での回答
「1日あたり10億回の取得は平均で毎秒約11,600回であるため、毎秒25,000回のピークを計画し、鮮度を毎日更新する1億件のURLと30日ごとに更新する99億件のURLに分割します。ディスカバリーでは保守的な正規化と厳密な一意キーによる重複排除を実行します。フロンティアはホストごとにシャーディングされます。シャードはまずnext_allowed_atに達したホストを選択し、次にそのホストのキューから最も優先度の高いURLを取得します。これにより、robotsポリシー、同時実行数、およびバックオフに1つの所有者が与えられます。フェッチャーはリースと条件付きリクエストを使用し、HTMLをオブジェクトストレージに書き込み、ディスカバリーにリンクをフィードバックするパーサーに送信します。実行は少なくとも1回（at-least-once）であり、URLバージョンと冪等な完了によって重複を吸収します。検証では、ホストごとのレート制限、リースの期限切れ、429/503、到達不能なrobotsファイル、リダイレクトループ、およびクローラートラップに焦点を当てます。」
ステップごとの詳細解説
ステップ1：目標がバジェット内に収まることを証明する
10億回の取得を86,400秒で割ると、平均で毎秒約11,574回の取得になります。トラフィックの変動や遅延のキャッチアップを考慮して、計画ピークを毎秒25,000回に切り上げます。すべてのレスポンスが200 KBのボディを返した場合、イングレスは1日あたり最大で約200 TB、平均で毎秒2.31 GBになります。304 Not Modifiedにはレスポンスコンテンツがないため、実際のイングレスはこの保守的な上限よりも低くなるはずであり、負荷テストと観測された分布を用いて調整する必要があります。
1日の再訪問計画には以下が必要です：
100,000,000 + 9,900,000,000 / 30 = 430,000,000 fetches
これにより、新しく発見されたページ、再試行、および変化の速いページのために、約5億7,000万回の取得が残されます。URLあたり200バイトの未加工の論理状態を想定すると、100億件のURLレコードには約2 TBが必要です。レプリケーション、インデックス、LSM増幅、およびオブジェクトストレージは除外されています。この桁数から、水平分割されたメタデータとHTML用の個別のオブジェクトストレージが必要であることがわかります。ページボディはフロンティアに含めるべきではありません。
ステップ2：段階的なデータフローを構築する
全体のパスは次のとおりです。シードとSitemap → URLディスカバリーと正規化 → 厳密な既読状態 → URLメタデータ → フロンティアスケジューラ → robotsおよびホストPolitenessチェック → DNS/HTTPフェッチャー → HTMLオブジェクトストレージ → パーサー → 発見されたリンクをディスカバリーへフィードバック。解析された出力と取得完了イベントは、検索インデックスと再訪問計算モジュールに送られます。
Sitemapはシードを補完するものであり、カバレッジを保証するものではありません。1つのSitemapファイルには最大50,000件のURLを含めることができ、非圧縮で最大50 MBです。大規模なサイトでは、これらをSitemapインデックス配下に分割します。リンクディスカバリー、Sitemap、およびオペレーターが提供するシードはすべて同じ重複排除エントリポイントを使用するため、3つのステートマシンが不一致になることはありません。
取得と解析を分離することには、2つの直接的な利点があります。低速な外部I/OがパーサーのCPUを占有せず、パーサーがクラッシュしてもサイトに再アクセスすることなく保存されたHTMLを再処理できます。各ステージには、解析やストレージのキャパシティを超える一時的なダウンロードレートによってメモリが枯渇しないよう、有界なキューとバックプレッシャーが必要です。
ステップ3：ホストPolitenessをフロンティアのスケジューリングプリミティブにする
フロンティアは2つのキューレベルを使用します。上位レベルは各ホストのnext_allowed_atと優先度を格納し、準備ができておりバックオフ状態にないホストのみを選択します。下位レベルはそのホストのURLの優先度キューであり、ビジネス価値、期日、リンク深度、過去の変更頻度などのシグナルによって順序付けられます。1つのURLをリースすると、ホストのin_flightカウントと次に利用可能な時刻がアトミックに更新されます。
host_keyをハッシュ化することで、ホストが1つのスケジューラシャードに割り当てられます。ホストに100万件の保留中URLがある場合でも、取得作業を多くのマシンで実行しながら、1つの論理所有者がそのトークンを付与します。アクセスの多いホストは複数の同時接続を持つ場合がありますが、同じホスト状態がその許容量を制御し続けます。ワーカーを追加するとホスト間の並行性が向上しますが、1つのホストの許容量を不当に超えることはできません。
robots.txtはサービスの最上位の/robots.txtから取得されます。取得が成功した場合、クローラーは解析可能なルールに従う必要があります。400–499でファイルが利用できない場合、プロトコルはアクセスを許可します。ネットワークエラーや500–599で到達できない場合、クローラーは完全な拒否（disallow）とみなします。キャッシュされたコピーは、ファイルが到達不能でない限り、通常24時間以上使用すべきではありません。「ホストごとに1つの同時リクエストと1秒の遅延」はこの面接での設定可能なデフォルトにすぎず、プロトコルは普遍的なレートを定義していません。429または503が発生した場合はRetry-Afterに従い、それが存在しない場合はジッター付きの指数バックオフを適用してそのホストの許容量を減らします。
ステップ4：URL重複排除とコンテンツ重複排除を分離する
正規化では、セマンティクスを保持する変換のみを実行します。相対参照の解決、フラグメントの削除、スキームとホスト名の大文字小文字の正規化、デフォルトポートの処理、パスのドットセグメントの解決です。クエリパラメータをグローバルに削除したり並べ替えたりしてはいけません。一部のサイトでは、順序や重複したキーに意味を持たせています。ページで宣言された正規URL（canonical URL）はスコアリングやクラスタリングに影響を与える可能性がありますが、観測されたURLを事実として上書きしてはなりません。
canonical_url、またはその衝突耐性のある一意キーをパーティション化されたメタデータストアに保存します。Bloomフィルタはネガティブアクセラレータとしてのみ機能します。「確実に存在しない」場合は直接挿入を試み、「存在する可能性がある」場合は永続的な一意キーを引き続きチェックします。したがって、偽陽性が発生しても、ページを破棄する代わりに読み取りが1回追加されるだけです。ハッシュ衝突は、完全なURLまたは2つ目のフィンガープリントを比較して解決します。
コンテンツハッシュは取得後にのみ計算します。バイト単位で同一のコンテンツは、各URLのメタデータを保持しながら1つのオブジェクトを再利用できます。ニアデュープ（準重複）ページは、SimHashなどのフィンガープリントを使用してグループ化できます。研究により、数十億ページ規模でこの種のフィンガープリントが実証されていますが、準重複シグナルはストレージ、インデックス作成、または再訪問の優先度への入力として使用する方が安全です。ページを完全に破棄すると、そのページ固有のリンクも破棄されてしまう可能性があります。
ステップ5：バージョン管理された状態とリースによる復旧
コアカスタムレコードをコンパクトに保ちます：
UrlState( urlid, canonicalurl, hostkey, stateversion, lastfetchat, nextfetchat, priority, etag, lastmodified, contenthash, failure_count )
HostState( hostkey, robotspolicy, robotsexpiresat, nextallowedat, inflight, backoffuntil, policy_version )
FetchLease(leaseid, urlid, urlversion, expiresat, attempt)
スケジューラはurl_versionを含む有界なリースを発行します。フェッチャーはHTMLを書き込んだ後、タスクを確認（ACK）する前にクラッシュする可能性があるため、リースの期限切れによって別の取得が発生することがあります。完了処理では(url_id, url_version)に対する条件付き書き込みを使用します。古いリースまたは重複した確認は既存の結果を返し、別のインデックスイベントを発行しません。新しい再訪問では最初にバージョンがインクリメントされるため、前回のラウンドの冪等性キーが正当な新しい作業を抑制することはありません。
ETagが利用可能な場合はIf-None-Matchを送信します。それ以外の場合は、保存されたLast-Modifiedを使用してIf-Modified-Sinceを駆動できます。304は、空のボディを書き込むことなく、取得時刻と次のスケジュールを更新します。DNSタイムアウト、接続障害、および5xxは、上限付きの再試行ポリシーに入ります。永続的な404/410はトゥームストーンを作成し、再訪問間隔を大幅に長くします。リダイレクトにはホップ制限とループ検出が適用されます。
ステップ6：再訪問、トラップ保護、セキュリティを単一のバジェットで管理する
再訪問の優先度は、ページの価値、最近の変更間隔、ステータス、およびサイトの許容量を組み合わせます。コンテンツの変更は間隔を短縮し、変更のない結果が繰り返されると間隔が長くなり、1日から30日の間にクランプされます。これにより、最小限の鮮度保証を維持しながら、安定したページから変化するページへとバジェットをシフトします。
最大リンク深度だけでは、カレンダー、ファセットナビゲーション、または無制限のクエリの組み合わせを止めることはできません。ホストごとの日次バジェット、URLテンプレートの増加制限、クエリパラメータ数、重複パスの検出、レスポンスボディおよび展開後のサイズ制限、パーサー時間の制限、およびリダイレクトホップ制限を追加します。パターンがバジェットを消費した場合は、無関係なホストをブロックすることなく、そのパターンを一時停止しサンプルを保持します。
フェッチャーは信頼できない入力を処理します。DNS結果からループバック、プライベート、リンクローカル、およびクラウドメタデータのアドレスを拒否し、接続直前にそれらを再チェックして、SSRFおよびDNSリバインディングのリスクを軽減します。メモリとCPUの制限を設けてパーサーを実行し、圧縮ボムや不正なHTMLを隔離します。robotsルールはクロールの希望を表すものであり、アクセスの認可ではありません。
ステップ7：フォールトインジェクションで不変条件を検証する
決定論的なスケジューリングシミュレーションから始めます。3つのホストに異なるレート、robotsルール、およびRetry-Afterの値を設定し、仮想クロックを進め、いかなる時間枠も許容量を超えず、拒否されたパスがリースを受け取らないことをアサートします。次に、「HTTP成功後にプロセスがクラッシュする」、「リースの確認が失われる」、「robotsキャッシュが期限切れになる」、「DNSがプライベートアドレスに解決される」、「パーサーキューが停止する」という状況を注入します。タスクは復旧し、インデックスイベントは一意のままであり、取得ステージはバックプレッシャーを適用しなければなりません。
キャパシティテストでは、毎秒25,000件のリース付与、100億URLのキースペース全体でのパーティションの偏り、および100万件の保留中URLを持つ1つの高負荷ホストをカバーする必要があります。主要なメトリクスには、利用可能ラグ、取得およびバイトレート、2xx/304/429/5xx比率、ホストポリシー違反、リース再試行、URLおよびコンテンツの重複率、robotsキャッシュの経過時間、パーサーバックログ、およびバジェットトリガー率が含まれます。ホストポリシー違反はゼロのままでなければなりません。Politenessに違反しながら平均スループットを達成しても、テストは失敗です。
代替案とその適用限界
所有するサイトに対して1日あたり数百万件の取得を行う場合、リレーショナルデータベースでnext_fetch_atのインデックスを作成し、SKIP LOCKEDを使用してタスクを取得し、同じトランザクションでホストトークンを更新できます。デプロイとデバッグがよりシンプルになります。1日あたり10億件の取得では、グローバルインデックススキャン、ホットアップデート、およびクリーンアップがボトルネックになるため、2層のパーティション化されたフロンティアの方が適しています。
既読セットとしてBloomフィルタを使用すると読み取りを節約できますが、偽陽性によりカバレッジが永続的に低下します。この設計では、それをキャッシュに格下げし、永続的な一意キーを信頼できる情報源として維持します。確認のための読み取りをスキップすることは、製品が定量化された偽陽性バジェットを明示的に受け入れる場合にのみ合理的です。
優れた回答の例
「私はバジェットとPolitenessという2つの不変条件から始めます。1日あたり10億回の取得は、平均で毎秒約11,600回、ピークで毎秒25,000回です。毎日1億件のURLを更新し、99億件を30日ごとに更新すると、1日あたり約4億3,000万件の取得がスケジュールされ、ディスカバリー、再試行、および変更駆動の更新のための余地が残ります。レスポンスあたり200 KBの場合、1日あたり200 TBが保守的なネットワーク上限となります。304レスポンスによって実際のトラフィックは減少します。
エントリ時、URLは安全な正規化のみを受け、永続的な一意キーと照合されます。Bloomフィルタは、明らかに未読のURLに対する読み取りを回避するためだけに機能します。フロンティアはscheme + authorityによってパーティション化され、各シャードはホストの準備状態とホストごとのURL優先度キューを維持します。作業を要求するとホストトークンがアトミックに消費されるため、複数のフェッチャーが集合的に1つのサイトに過負荷をかけることはありません。到達不能なrobotsファイルはホストを一時停止し、429/503はRetry-Afterまたはジッター付きバックオフをトリガーします。
フェッチャーは有界なリースを受け取り、条件付きGETを実行し、HTMLをオブジェクトストレージに書き込み、次のステージに解析を渡します。解析されたリンクは同じディスカバリーエントリポイントを通じて戻ります。リースの期限切れによってリクエストが繰り返される可能性がありますが、URLバージョン管理された完了処理により、古いリースが状態を上書きしたり2回目のインデックスイベントを発行したりするのを防ぎます。コンテンツハッシュによって完全に重複するオブジェクトを再利用し、SimHashは潜在的にユニークなリンクを破棄するのではなく、準重複の優先度に影響を与えます。
仮想クロックを使用してホストごとの間隔を証明し、書き込み後のクラッシュ、失われた確認、期限切れのrobots状態、DNSリバインディング、およびパーサーのバックプレッシャーを注入して検証します。合格基準には、毎秒25,000回のピーク達成とホストポリシー違反ゼロの両方が含まれます。」
よくある間違い
- 間違い：1つのグローバルなメッセージキューを使用する。 失敗する理由：独立したコンシューマ同士ではホストの次に利用可能な時刻を共同で強制できないため、スループットが向上するとPolitenessに違反するリスクが高まります。修正方法：
host_keyによってスケジューリングの所有権を割り当て、ホスト準備完了キューとホストごとのURLキューを使用します。 - 間違い：Bloomフィルタを唯一の既読セットとして使用する。 失敗する理由：偽陽性により未読のURLが永続的にドロップされ、フィルタにはステータス、バージョン、または再訪問時刻を保存できません。修正方法：キャッシュとしてのみ使用し、永続的な一意キーの状態を保持します。
- 間違い：URL重複排除をコンテンツ重複排除として扱う。 失敗する理由：異なるURLが同じコンテンツを返す可能性があり、1つのURLが時間とともに変化する可能性があります。修正方法：ディスカバリー時に厳密なURLを重複排除し、取得後にコンテンツハッシュとニアデュープフィンガープリントを計算します。
- 間違い：正確に1回（exactly-once）のクロールを約束する。 失敗する理由：外部のHTTP成功と内部の確認は1つのアトミックなトランザクションを形成できず、クラッシュのウィンドウが残ります。修正方法：少なくとも1回（at-least-once）の実行を受け入れ、リース、バージョン条件付き書き込み、および冪等なイベントによって内部の副作用を制御します。
- 間違い：robotsのエラーすべてにおいて処理を継続する。 失敗する理由：プロトコルは利用不可（unavailable）と到達不能（unreachable）を区別します。ネットワークエラーや
5xxは完全な拒否を必要とします。修正方法：明示的なステートマシンを実装し、キャッシュの経過時間、リダイレクト、および障害クラスを個別にテストします。 - 間違い：クローラートラップ対策を最大深度のみに依存する。 失敗する理由：単一の深度でも、無制限のファセット、カレンダー、およびクエリパラメータの組み合わせが含まれる可能性があります。修正方法：ホストバジェット、URLパターンの増加制限、パラメータ数、レスポンスサイズ、およびパーサー時間制限を組み合わせます。
フォローアップの質問
保留中のURLの50%が1つのホストに属している場合はどうなりますか？
まず、そのサイトが許可している同時実行数とレートを特定します。固定の許容量がある場合、ワーカーを増やしてもそのホストの正当なスループットは向上せず、他のホスト間の並行性が向上するだけです。ホストのURLキューを分割してストレージのホットスポットを減らすことはできますが、すべてのパーティションは依然として1つの論理トークンサービスにキャパシティを要求します。ビジネス上さらに速度が必要な場合は、サイトと専用のフィードまたはより大きな許容量を交渉し、新しいポリシーをバージョン管理します。
なぜ「正確に1回（exactly-once）」を保証しないのですか？
フェッチャーはHTTPレスポンスを受信した後、リースを確認する前にクラッシュする可能性があり、外部サイトは内部トランザクションに参加しません。分散トランザクションであっても、すでに発生したGETを取り消すことはできません。実現可能な規約は、少なくとも1回の要求、重複取得の可能性、および冪等な内部完了です。重複率を測定し、条件付きリクエストによってそのコストを削減します。
コンテンツを公開するためにページにJavaScriptが必要な場合はどうなりますか？
通常のHTTP取得を第1層として維持します。解析結果が空であり、サイトポリシーがそれを許可し、ページ価値がしきい値を超えている場合にのみ、URLを個別のレンダリングキューに入れます。レンダラーは同時実行数が少なく、CPU、メモリ、および時間のバジェットがより厳格であり、元のホストトークンを共有します。そうしないと、コストのかかるレンダリングがPolitenessをバイパスし、グローバルバジェットを消費してしまいます。
ホストに2回アクセスすることなく、クローラーを複数のリージョンで実行するにはどうすればよいですか？
各host_keyにホームリージョンを割り当て、そのリージョンのみがホストトークンを付与できるようにします。他のリージョンは解析と保存を行うことができます。リージョン障害が発生した場合は、フェンシングトークンを含むリースを使用して所有権を移転します。復旧した古いリージョンは、作業を付与する前に新しいエポックを保持していなければなりません。複数のリージョンで同じホストに対してアクティブなスケジューリングを行うと、Politeness不変条件に違反します。
ストレージコストが突然バジェットを超過しました。最初に何を削減すべきですか？
まず、条件付きリクエストのヒット率、圧縮、および完全に重複するオブジェクトの再利用を改善します。次に、コンテンツの価値に応じて生のHTMLの保持期間を短縮します。URLメタデータと取得監査レコードを一緒に破棄してはいけません。再訪問、重複排除、およびコンプライアンス調査はそれらの状態に依存しています。準重複検出によって優先度を下げたり、ストレージ層を選択したりすることはできますが、検証されていない一括削除をトリガーすべきではありません。