Web クローラーのシステム設計：URL フロンティア、ポライトネス、重複排除

クローラーは単純に見えます。ページをダウンロードし、リンクを抽出し、それをダウンロードし、繰り返すだけです。ループとして書けば、1,000 ページなら動きます。ところが 10 億ページになると、教訓的な形で破綻します。小さなサイトに何百もの並列リクエストを浴びせ、同じページを 50 通りの URL でダウンロードし、終わりのないカレンダーで迷子になり、時間の大半を DNS の待ちに費やします。

この記事では、スケールしつつ礼儀正しいクローラーを設計します。容量の数値、優先度キューとホスト別キューを持つ URL フロンティア、RFC 9309 で標準化された robots.txt、URL とコンテンツの重複排除、クローラートラップ、それらを取り巻くコンポーネントを、ループ全体の図とともに扱います。

要件と数値

目標は、検索または分析用のインデックスのために月に約 10 億ページをクロールし、重要なページはより頻繁に更新し、どの Web サイトにも過負荷をかけないことです。

最も重要なのは最後の行です。発見のペースは取得を大きく上回るので、クローラーは常に何を取得しないかを選んでいます。優先順位付けは最適化ではなく、中核の機能です。

クロールのループ

1. フロンティアから次の URL を取り出します。
2. そのホストの robots.txt をキャッシュから確認します。
3. ホスト名をローカルの DNS キャッシュから解決します。
4. ホストのポライトネス遅延を守ってページを取得します。
5. 生のレスポンスを保存します。
6. パースしてリンクを抽出し、正規化します。
7. 既出のリンクを捨て、残りを優先度付きでフロンティアに追加します。
8. コンテンツのフィンガープリントを取り、後の処理ではほぼ重複したものを飛ばします。

最初のステップ以外はどれも、素朴なクローラーが労力を無駄にしたり、害を与えたりする場所です。

URL フロンティア

フロンティアはクローラーの心臓部です。2 つの異なる問いに同時に答えなければならないキューだからです。どの URL が最も重要か。そして、いまどのホストに接続してよいか。

古典的な答えは Mercator の設計で、Introduction to Information Retrieval の URL フロンティアの章で説明されています。

• フロントキューが優先度を扱います。 優先度付け器が、ページの更新頻度、リンクの人気度、サイトの重要度といったシグナルに基づいて、新しい URL を F 個のキューのいずれかに割り当てます。
• バックキューがポライトネスを扱います。 各バックキューは、ちょうど 1 つのホストの URL だけを保持します。ヒープが、ホストごとに次に接続してよい最も早い時刻を記録します。
• フェッチャースレッドはヒープの先頭のホストを取り、そのホストのバックキューから URL を 1 つ取得し、新しい最早時刻を付けてホストをヒープに戻します。バックキューが空になると、優先度の高いものを優先しながらフロントキューから補充します。

Mercator の設計者は、スレッドが配慮すべきホストを待つことがめったにないよう、フェッチャースレッドのおよそ 3 倍のバックキューを用意することを勧めていました。

大規模になったら、フロンティアをホストで分割します。ホスト名をハッシュしてフロンティアのシャードを選べば、あるホストの URL はすべて 1 か所に集まり、ポライトネスを調整なしにローカルで守れます。

ポライトネスと robots.txt

礼儀正しいクローラーは、ホストごとに一度に 1 つのリクエストしか送らず、リクエストの間に待ち時間を入れます。同じ章にある一般的な経験則は、そのホストからの直前の取得にかかった時間の約 10 倍待つことです。こうすれば、遅いサーバーほど自動的に余裕が生まれます。429 や 503 の応答ではさらに間隔を空け、Retry-After ヘッダーがあればそれに従います。

robots.txt は 2022 年に RFC 9309 で標準になりました。クローラーが正しく守るべきルールは次のとおりです。

4xx と 5xx の非対称性は意外に感じられます。ファイルがなければ「どうぞ」ですが、サーバーエラーなら「立ち入らないで」です。ルールが何と言っていたのかをクローラーは知りようがないからです。Crawl-delay は RFC 9309 には含まれておらず、従うかどうかはクローラーによって異なります。連絡先を記載した URL を含む、わかりやすいユーザーエージェントでクローラーを名乗りましょう。

URL の重複を排除する

同じページが多くの URL の裏に隠れています。HTTP://Example.com:80/a/./b?utm_source=x#top と http://example.com/a/b は同じページです。URL が既出かどうかを確認する前に正規化します。

• RFC 3986 の 6 章に従い、スキームとホストを小文字にし、デフォルトポートを除き、. と .. のセグメントを解決し、パーセントエンコーディングを正規化します。
• サーバーに届くことのないフラグメントを除きます。
• utm_* のような既知のトラッキングパラメーターを慎重に取り除きます。ほかのパラメーターはコンテンツを変えることがあります。
• 取得後は rel="canonical" のヒントに従います。

そのうえで既出 URL の集合を確認します。数十億の URL なら、Bloom フィルターが一般的な選択です。10 億の URL を偽陽性率 1% で扱うサイズにすると、URL あたり約 9.6 ビット、合計でおよそ 1.2 GB、ハッシュ関数は 7 つ必要です。偽陽性とは、実際には見ていない URL を飛ばしてしまうことで、ほとんどのクロールでは 1% なら許容できるコストです。サイトマップのエントリーのように取りこぼせない URL には、正確なストアを別に持ちましょう。

コンテンツの重複を排除する

ミラー、印刷用ページ、セッションパラメーターは、異なる URL で同一の、あるいはほぼ同一のページを生み出します。完全な重複は簡単で、正規化したコンテンツをハッシュして比べるだけです。ほぼ重複には、ページが少し変わったときに少ししか変わらないフィンガープリントが必要です。標準的な手法は simhash で、似た文書ほど異なるビットが少なくなる 64 ビットのフィンガープリントです。Google の研究者は 2007 年に、80 億ページのリポジトリでは、異なるビット数のしきい値を 3 とした 64 ビットの simhash フィンガープリントが、ほぼ重複の検出に実用的な設定だったと報告しています。

クローラートラップ

一部のサイトは、多くの場合は意図せず、無限の URL 空間を生み出します。いつまでも「翌月」リンクが続くカレンダー、すべての URL に付くセッション ID、あらゆるフィルターの組み合わせを持つファセット検索、パスを伸ばし続ける相対リンクなどです。対策は次のとおりです。

• URL の長さとパスの深さに上限を設けます。
• ホストの重要度に応じて、クロール周期ごとのホストあたりのページ数に上限を設けます。
• /a/b/a/b/a/b のように繰り返すパスセグメントを検出します。
• コンテンツのフィンガープリントが既存のページと一致し続ける URL の優先度を下げます。

サイトマップは逆方向に役立ちます。サイトがクロールしてほしい URL を列挙したもので、サイトマップファイル 1 つにつき最大 50,000 URL、非圧縮で 50 MB までで、それを超える場合はサイトマップインデックスファイルを使います。

ループの周辺：DNS、ストレージ、再クロール

• DNS は隠れたボトルネックです。毎秒数百件の取得では、フェッチャーの近くに共有のキャッシュリゾルバーを置けば、すべての問い合わせを上流に送らずに済みます。
• ストレージ。 生のレスポンスは大きなバッチファイルにまとめてオブジェクトストレージに書き込み、パースしたテキストとリンクはストリームを通じてインデックス作成へ送ります。
• 再クロール。 ページによって変更の頻度は異なります。各ページが過去の訪問でどのくらい変わったかを記録し、それに合わせて次の取得を予定します。If-Modified-Since や ETag を使った条件付きリクエストは、何も変わっていないときに帯域を節約します。
• JavaScript の多いページにはヘッドレスブラウザーが必要で、ページあたりのコストがはるかに高くなります。必要なホストだけをレンダリングしましょう。

Web クローラーの図

図の読み方は次のとおりです。

• フレームは URL フロンティアです。 優先度キューが、ポライトネスを守るホスト別キューに URL を供給します。
• フェッチャーはホストごとに一度に 1 つの URL を取り、robots.txt キャッシュと DNS キャッシュを参照して、インターネットからダウンロードします。
• 生のページはオブジェクトストアに送られます。パーサーがリンクとテキストを抽出します。
• 新しいリンクは既出 URL フィルターを通り、フロンティアに戻ってループが閉じます。コンテンツのフィンガープリントがほぼ重複を検出します。
• パース済みのページは、右側のストリームを通じてインデックス作成へ流れます。
• Markdown ブロックは、容量の数値とポライトネスのルールを並べています。

ループを含むパイプラインを描く

• ループを見えるようにします。 クローラーは循環です。まっすぐなパイプラインとして描くと、トラップや重複の問題を生むフィードバックが隠れてしまいます。
• ポライトネスをどこで守るかを示します。 ホスト別キューは脚注ではなく図の中に置きましょう。
• キャッシュはキャッシュとして示します。 robots.txt と DNS のキャッシュは外部への負荷を変えます。有効期限をラベルに書きましょう。
• エッジに数値を書きます。 入ってくる毎秒のページ数と、出ていくページあたりのリンク数です。

一般的な進め方はシステム設計図の例を参照してください。各ホストへのレート制御はレートリミッターのシステム設計と同じ考え方を使い、クロール後の処理はデータパイプラインのアーキテクチャ図に似ています。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. URL frontier という名前の基本パックの フレーム を追加し、その中にデータパックの キュー ノードを 2 つ置きます。優先度キューとホスト別キューです。
3. フェッチャー用にクラウドパックの コンピューティング ノード、ネットワークパックの DNS ノードと インターネット ノード、robots.txt キャッシュ用にデータパックの Redis ノードを追加します。
4. 生のページ用にデータパックの オブジェクトストア を、パーサー用にもう 1 つの コンピューティング ノードを追加します。
5. 既出 URL フィルター用に 2 つ目の Redis ノード、コンテンツのフィンガープリント用にクラウドパックの マネージドデータベース、インデックス作成へ向かうページ用にデータパックの Kafka ノードを追加します。
6. ラベル付きのエッジでループを描き、数値を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 13 個で、Free プランの範囲に収まります。

よくある質問

URL フロンティアとは何ですか？ クローラーが次に何を取得するかを決めるデータ構造です。URL を重要度で並べる優先度キューと、どのホストにも頻繁に接続しすぎないようにするホスト別キューおよびスケジュールを組み合わせたものです。

クローラーはどうやって礼儀正しさを保つのですか？ ホストごとに同時接続は 1 つ、サーバーの応答時間に応じて伸びるリクエスト間の遅延、429 や 503 の応答での後退、そして robots.txt の順守です。

robots.txt がエラーを返したらどうなりますか？ RFC 9309 では、4xx のステータスならクローラーはそのサイトをクロールしてよく、5xx のステータスやネットワークエラーなら、ファイルを読めるようになるまですべて禁止とみなさなければなりません。

クローラーは同じページを 2 回ダウンロードするのをどう避けるのですか？ URL を正規化して、多くの場合は Bloom フィルターで実装した既出 URL の集合と照合します。さらに、完全一致のハッシュと simhash でコンテンツのフィンガープリントを取り、異なる URL の同じページを見つけます。

10 億 URL 用の Bloom フィルターはどのくらいの大きさが必要ですか？ 偽陽性率 1% なら、URL あたり約 9.6 ビットとハッシュ関数 7 つで、約 1.2 GB です。誤り率を下げるほど、エントリーあたりのビット数が増えます。

無料で始める — 1 シート、クレジットカード不要。