Webクローラ解剖メモ ~ With great power comes great responsibility ~

はじめに

Webクローラについて調べたメモ。

特にスケーラブルで効率的なシステム設計に焦点を当てている。参考にした資料には古いものが含まれるが、コアなコンセプトは変わらないため、問題にはしないものとしてメモる。

Webクローラは、インターネット上の文書を体系的に収集するプログラムだ。収集した情報は様々な用途で活用される。

用途	詳細
検索エンジンインデックス	・クローラが集めたページをインデックス化し、ユーザーのクエリに対して関連性の高い結果を提供できる
Webアーカイブ	・Internet Archiveのようなサービスで、Webの歴史的記録を保存する
データマイニング	・Webページの統計的特性を調査したり、特定の情報を抽出したりする
モニタリング	・特定のクエリに合致するページを継続的に監視し、発見次第クライアントに通知する

Webは中央で管理されたリポジトリではなく、多数の独立したコンテンツプロバイダから成り立っている。この分散的な性質のため、検索エンジンなどの情報アグリゲータは「プル型」アプローチを採用する必要がある。クローラはそのプル型モデルの中核技術だ。

基本的な動作原理

Webクローラの動作は再帰的なプロセスだ。シンプルに説明するとこんな流れになる。

このプロセスはWebグラフの探索操作と見なせる。各ページをノード、リンクをエッジとするグラフを辿っていくわけだ。

主な課題

基本的なクローリングアルゴリズムは単純だが、実際には多くの課題がある。

課題	説明
Webの規模	・数兆ページに達し、総データ量はゼタバイト級 ・毎秒数百ページ以上のダウンロードが必要
コンテンツ選択	・全ページのクロールは不可能なので、価値の高いコンテンツを優先 ・JavaScriptやSPAの動的コンテンツも考慮が必要 ・カバレッジと鮮度のバランスが重要
ポライトネス	・サーバに過度の負荷をかけず「礼儀正しく」振る舞う必要がある ・robots.txtのポリシー尊重 ・サーバへのアクセス間隔調整
堅牢性	・スパイダートラップなどの罠に対する耐性が必要
敵対的挙動	・SEO目的のスパムページ ・クローカ（人間とクローラに異なるコンテンツを見せる手法） ・高度なアンチクローリング技術

これらの課題に対処するには、洗練されたアーキテクチャとアルゴリズムが必要だ。

クローラアーキテクチャ

効率的でスケーラブルなWebクローラは、複数の機能コンポーネントを組み合わせたアーキテクチャで構成される。

コアコンポーネント

一般的なWebクローラは、以下の主要なコンポーネントで構成されている。

https://moodle2.units.it/pluginfile.php/431314/mod_resource/content/1/Lecture 8.pdf

コンポーネント	役割
URLフロンティア	・これからダウンロードすべきURLを管理するデータ構造 ・優先度付けやポライトネス制御も担当
DNSリゾルバ	・ホスト名をIPアドレスに解決 ・効率化のためキャッシングが重要
フェッチモジュール	・HTTP/HTTPSでWebページを取得
パーシングモジュール	・HTMLなどを解析し、テキストとリンクを抽出
重複検出モジュール	・URL重複排除（既発見URLの判定） ・コンテンツ重複排除（同内容ページの検出）
URLフィルタと正規化モジュール	・クロール対象として適切なURLを選別 ・特定のドメイン,パス,拡張子の除外 ・相対URLを絶対URLに変換 ・URL表記の正規化（大小文字統一、パラメータ整理など）

近年の大規模システムでは、これらのコンポーネント間の連携にApache Kafkaのような分散メッセージングシステムが利用されることが多い。スケーラビリティと耐障害性の向上が図れるからだ。

クローリングサイクル

クローリングは通常、複数のワーカースレッドで並行実行される。各スレッドはこんなサイクルを繰り返す。

このサイクルに加え、バックグラウンドで統計情報の記録やクロール終了判定、チェックポイント作成などのハウスキーピングタスクが実行されることが多い。

分散クローラ

Web規模のクロールを実現するには、単一マシンでは不十分だ。複数のマシンに処理を分散させる必要がある。

要素	詳細
必要性	・スケーラビリティ（処理能力向上）と地理的分散（効率化）のため
ホスト分割戦略	・クロール対象のホスト空間を複数ノードに分割 ・ホスト名ハッシュ値やドメイン、IPアドレスでの分割が一般的 ・静的割当と動的負荷分散の組み合わせも使われる
ノード間通信	・あるノードで抽出したURLを担当ノードに転送する必要がある ・現代的なシステムではKafkaのような分散メッセージキューシステムを利用
分散環境の課題	・コンテンツ重複検出：ノード間でのフィンガープリント共有 ・データ構造の分散：フロンティアやDUE/USTの分散管理

主要コンポーネント詳細

URLフロンティア

URLフロンティアは、未訪問URLを保持し、次にクロールすべきURLを決定する重要なコンポーネントだ。実装における主な課題は以下の通り。

課題	説明
ポライトネス	・特定のホストに短時間で連続アクセスするのを避ける必要がある
優先度付け	・品質が高いページや変化が速いページを優先的にクロールする
スケール	・Web規模のクロールでは、フロンティアは簡単にメモリサイズを超える

Najork氏らのMercatorクローラ実装を参考にする。この実装はフロントエンド（優先度制御）とバックエンド（ポライトネス制御）の2層構造になっている。

https://www.cs.cornell.edu/courses/cs685/2002fa/mercator.pdf

この設計の主要コンポーネントと役割はこうなっている。

コンポーネント	役割
フロントエンドキュー群	・優先度レベル（1〜k）ごとに独立したFIFOキュー ・URLの優先度に基づいて振り分け ・各キューには優先度が同じURLが格納される
ランダム選択器	・高優先度キューに偏ったランダム選択を行う ・バックエンドキューの補充時に使用
バックエンドキュー群	・各キューは単一ホストのURLのみを格納 ・スレッド数の数倍（例：3倍）のキュー数を用意 ・常に空にならないよう管理
ホスト・キュー対応表	・どのホストがどのバックエンドキューに割り当てられているかを管理
ヒープ	・各バックエンドキューの「次アクセス可能時刻」を管理 ・最も早くアクセス可能なキューを効率的に取得

ワーカースレッドがURLを取得する流れはこうなる。

1. ヒープから最も早く次アクセス可能なバックエンドキューを取得し、必要なら待機
2. 取得したバックエンドキューの先頭URLを取得してフェッチ実行
3. フェッチしたURLをバックエンドキューから削除
4. バックエンドキューが空になったら、優先度バイアス付きでフロントエンドキューからURLを取得
5. フロントエンドから取得したURLのホストが他のバックエンドキューで既に管理されていれば、そのバックエンドキューに追加
6. 新しいホストの場合は、現在の空のバックエンドキューに割り当て
7. バックエンドキューの次アクセス可能時刻を設定（例：現在時刻 + 前回フェッチ時間×10）
8. 更新したバックエンドキューをヒープに再挿入

この仕組みで、「優先度の高いURLを優先」しながら「同一ホストへの連続アクセスを避ける」という相反する要求を両立させている。

Webクロールではフロンティアが急速にメモリサイズを超えてしまう。そのため、各キューの大部分をディスクに格納し、先頭と末尾の一部だけをメモリにバッファリングする方式を採用している。これによりメモリ容量の制約を受けずに大規模クロールが可能になっている。

Mercatorの実装では、継続的クロール（同じURLを再度クロールする）もサポートしている。変化頻度に応じた優先度付けで、変更の少ないページは低い頻度でクロールし、頻繁に変わるページは高頻度でクロールするといった制御も可能だ。

DNSリゾルバ

DNS解決はクローリングのボトルネックになりがちだ。

課題	説明
遅延	・DNSは分散システムで、解決に数秒かかることも
同期的実装	・標準ライブラリは同期的で、一つの解決が終わるまで他のスレッドが待たされる

解決策としては、キャッシングとカスタム非同期リゾルバの実装がある。特に非同期リゾルバは複数のリクエストを並行処理し、タイムアウトとリトライ機構を備えることでブロッキングを防ぐ。Mercatorでは、このカスタムリゾルバによりDNS解決時間が大幅に削減されたという報告がある。

フェッチモジュール

Webページを実際にダウンロードするコンポーネントだ。主にHTTP/HTTPSプロトコルを扱う。

要素	詳細
プロトコル対応	・HTTP/HTTPS以外にFTP、Gopherなどもサポート ・プラグイン可能なモジュール設計
ロボット排除プロトコル	・robots.txtファイルを尊重 ・効率化のためキャッシング実装
接続管理	・同時接続数の制御 ・タイムアウト処理 ・エラーハンドリング
帯域調整	・過度なネットワーク使用を避ける ・サーバ負荷を考慮した転送速度制限

フェッチモジュールの性能はクローラの全体スループットに直接影響する。

パーシングモジュール

取得したHTMLからテキスト情報とハイパーリンクを抽出するプロセスだ。

処理	詳細
テキスト抽出	・本文やタグ情報を抽出しインデクサに渡す
リンク抽出	・<a>タグなどからリンク先URLとアンカーテキストを抽出

モダンなパーサーでは、壊れたHTMLにも対応できる堅牢性や、JavaScript実行環境を持つヘッドレスブラウザとの連携機能も重要だ。SPAなどの動的コンテンツも適切に処理できるよう、単純なHTML解析だけでなく、実際のブラウザに近い環境でのレンダリング後のDOM解析も検討される。

重複検出モジュール

URL重複排除

同じURLを複数回フロンティアに追加しないための機構だ。無駄なクロールを防ぎ、フロンティアのサイズを抑制する。

実装方式	特徴
インメモリハッシュテーブル/Bloom Filter	・高速だがメモリ使用量がクロール規模に比例 ・分散化によりスケール限界を高められる
ディスクベースハッシュテーブル	・メモリ制限を回避できるがシーク時間がボトルネック ・現代的な高スループット要求には性能不十分なことが多い
ソート/マージ方式	・URLフィンガープリントをディスク上のソート済みファイルとして保持 ・シーケンシャルアクセスが主体でスループット向上 ・バッチ処理による遅延が発生
確率的データ構造	・Bloom Filterとその派生形が広く利用される ・少ないメモリで高速なチェックが可能 ・偽陽性が発生するが設計時に制御可能

大規模システムでは、メモリ効率と高速なチェックを両立できるBloom Filterが特に重要だ。

コンテンツ重複排除

異なるURLでも内容が類似しているページを検出する。冗長なコンテンツのインデックス作成や処理を避けるのが目的だ。

技術	特徴
フィンガープリント/チェックサム	・完全一致検出のための簡単な方法
Shingle/MinHashing	・文書を短い部分文字列の集合として表現 ・完全一致でなくても類似性の高いページを検出 ・LSHで類似性検索を効率化
DUST	・URL エイリアシングを検出するアルゴリズム ・URL正規化ルールの学習に繋がる
ミラーリング検出	・異なるホスト間での同一コンテンツを検出

近年では、LSH（Locality-Sensitive Hashing）とBloom Filterを組み合わせた手法も提案されており、大規模言語モデルの学習データセット構築における重複排除でも注目されている。

クローラの動作とポリシー

クローラの効率と品質を決定づける重要な要素として、Webサイトへのアクセス方法（ポライトネス）、予期せぬ問題への対処（堅牢性）、そしてどのページをいつクロールするか（クロール順序付け）がある。

ポライトネス

Webサーバに過度の負荷をかけず、良好な関係を保つための配慮だ。

要素	内容
Robots Exclusion Protocol	・robots.txtファイルに従ってアクセス制限を尊重 ・User-agentディレクティブで特定クローラへのルールを指定可能 ・キャッシュされるが、フェッチ直前に再確認が望ましい
アクセスレート制限	・暗黙的ポリシー：robots.txtがなくても負荷調整 ・ホストごとの単一接続：同時複数接続を回避 ・時間間隔：直前のフェッチ時間の数倍（例：10倍）の待機時間設定

堅牢性

Webにはクローラの動作を妨げる様々な問題があるため、それらに対処できる堅牢性が求められる。

問題	対応
スパイダートラップ	・クローラを無限ループに陥れる仕組み ・URLの深さ制限 ・パスの繰り返し検出 ・サイトごとのクロール量制限
エラー処理	・DNS解決エラー、TCP接続エラー、HTTPエラーなどに適切に対処 ・リトライや該当URLの除外などの戦略が必要

クロール順序付け

どのURLをどの順序でクロールするかは、収集される情報の品質、鮮度、網羅性に大きな影響を与える。特にWebが広大で動的であるため、効率的な順序付けが重要だ。

目標	詳細
カバレッジ	・目的とするページ群をどれだけ網羅できたか
鮮度	・収集したページが最新かどうか（バイナリ値や経過時間で定義）
品質/重要度	・PageRankが高い、アクセス数が多いなど価値の高いページを優先
関連性	・特定のトピックや目的に関連するページを優先（スコープドクロール）

クロール方式には大きく分けて以下の2種類がある。

方式	特徴
バッチクロール	・一定期間でクロールを完了し、必要に応じて再度全体をクロール ・主にカバレッジや初期収集に焦点
継続的クロール	・クロールを停止せず、新ページ発見と再クロールを並行実施 ・鮮度維持が目的

順序付けポリシーにもいくつかの代表的なものがある。

ポリシー	特徴
幅優先探索	・発見された順にクロールする基本的な方法 ・実装は容易だが必ずしも最適ではない
優先度ベース	・PageRankや被リンク数などに基づいて優先度付け ・PageRankの計算コストが課題となることも
鮮度ベース	・ページの推定変更頻度に基づいて再クロール間隔を決定 ・非常に変化の速いページは対象外とする戦略も考えられる
トピカルクロール	・特定トピック関連ページを効率的に収集 ・機械学習モデルが関連性判断に活用される ・関連ページへの経路に無関係なページが含まれることにも配慮

カバレッジと鮮度のトレードオフも重要な検討事項だ。限られたリソースを未発見ページの探索と既知ページの再訪問にどう配分するかが最適化問題となる。Googleなどは「より少なく、しかしより賢くクロールする」方向性を目指しているようだ。

まとめ

結局のところ、Webクローラは情報の海を航海するデジタル探検家のようなものだ。単純なアルゴリズムから始まったが、広大で変化し続けるWebという環境に適応するため、高度な技術と戦略を身につけてきた。

側面	進化ポイント
規模への対応	・数兆ページにもなるWebを効率的に探索 ・メモリとディスクを組み合わせた大規模データ構造 ・分散システムによる並列処理
賢い判断	・価値の高いページを優先的に探索 ・変化の速いコンテンツを適切なタイミングで再訪問
礼儀作法	・robots.txtの尊重 ・アクセス間隔の制御 ・サーバに優しいリソース利用
障害物回避	・スパイダートラップの検知と回避 ・SEOスパムやクローキングへの対策 ・DDoS防止のための自己制御

Mercatorのようなクローラの設計は、まさに試行錯誤の叡智と言える。URLフロンティアの実装一つとっても、優先度付けとポライトネスという相反する要求をバランスさせるための巧妙な2層構造が実現されている。

検索エンジンの裏側では、これらのクローラが日々何百万（もっと？）ものページを収集し、インデックスを最新に保っている。まさにインターネットの地図作りを担う縁の下の力持ちだ。

今後のWebクローラは、単なるデータ収集から、より意味理解に踏み込んだ知的な探索へと進化していくだろう。SPAやJavaScriptで動的に生成されるコンテンツの理解、Deep Webの効率的な探索、プライバシー配慮と規制対応など、課題は尽きない。

探検家たちの旅は、いつ終わりを告げるのだろうか。