Webクローラの設計

概要

この記事は、「システム設計の面接試験」（Alex Xu 著）を読み学習した内容を個人学習用にまとめ直したものです。

本記事では、Web上のページを自動的に巡回して収集するWebクローラの設計について解説します。

やること自体は「ページを取得し、リンクをたどって次のページへ進む」の繰り返しにすぎません。しかし数十億ページを対象にしようとすると、巡回する順番、同じページの取得を避ける仕組み、相手のサーバーへの配慮など、設計上の論点が多く現れます。本記事ではそれらを順に整理していきます。

Webクローラとは

Webクローラ（web crawler）とは、Web上のページを自動的に巡回し、その内容を収集するプログラムである。ロボット（robot）やスパイダー（spider）とも呼ばれ、リンクをたどって渡り歩く様子がクモの巣を渡る姿になぞらえられている。

主な用途

用途	説明
検索エンジンのインデックス作成	収集したページから検索用のインデックスを構築する。もっとも代表的な用途
Webアーカイブ	将来に残すことを目的に、Web上の情報を収集・保存する。図書館などが行っている
Webマイニング	収集したデータから傾向や知見を抽出する
Web監視	著作権や商標の侵害といった、監視したい情報の出現を継続的に検知する

基本的なアルゴリズム

クローラは、URLリストを入力として受け取り、次の3つの手順を繰り返す。

リストからURLを1つ取り出し、そのURLが指すWebページをダウンロードする
ダウンロードしたページからURLを抽出する
抽出したURLをURLリストに追加し、1に戻る

この手順のままでは、同じページを何度もダウンロードしてしまいます。一度取得したページのURLであっても、別のページからリンクされていれば手順2で再び抽出され、リストに戻ってくるためです。実際に動かすには、これを防ぐ仕組みが必要になります。

設計の要件

本記事では、Alex Xu の設計演習にならい、検索エンジンのインデックス作成を目的としたWebクローラを設計する。

そのうえで、以下の制約・前提のもとで設計する。

収集規模: 1か月あたり 10億ページ（1 billion）を収集する
対象コンテンツ: HTMLページのみを対象とする
更新への追従: 新しく追加されたページや、内容が更新されたページも収集の対象とする
保存期間: 収集したHTMLページは最長5年間保存する
重複の排除: 内容が重複しているページは無視する

最後に、実運用に耐えるクローラとするため、次の非機能要件も満たす必要がある。

スケーラビリティ（scalability）: 並列化によって、膨大な数のページを現実的な時間で収集できる
堅牢性（robustness）: 不正なHTMLや応答しないサーバー、クローラを無限に巡回させ続ける罠など、Web上の想定外の状況に対処できる
ポライトネス（politeness）: 同一のWebサイトに対して、短時間に過剰なリクエストを送らない
拡張性（extensibility）: 新しい種類のコンテンツを扱うことになっても、最小限の変更で対応できる

概算見積もり

上記の要件、とくに「1か月あたり10億ページ」を起点に、システムが支えるべき負荷とデータ量を概算しておく。設計に入る前に、どこにボトルネックが生じうるかを把握するためである。

ダウンロードの量（QPS）: 1か月を30日とすると 30 × 24 × 3600 = 2,592,000 秒なので、1秒あたりの取得数は 10億 ÷ 2,592,000秒 ≈ 400 ページ/秒 となる
ピーク時の量: 常に一定のペースで取得できるとは限らないため、平均の2倍を見込んで 400 × 2 = 800 ページ/秒 とする
ストレージの量: 1ページあたりの平均サイズを500KBとすると、1か月分は 10億ページ × 500KB = 500 TB。要件より最長5年間保存するので、500 TB × 12か月 × 5年 = 30 PB が必要になる

以上を整理すると次の通りである。

指標	概算値	前提
ダウンロードQPS	約 400 ページ/秒	1か月10億ページ
ピーク時QPS	約 800 ページ/秒	平均の2倍
ストレージ（1か月）	約 500 TB	1ページ平均500KB
ストレージ（5年）	約 30 PB	500 TB × 60か月

特に毎秒数百ページをダウンロードし続ける必要がある点は、以降の設計を考えるうえで重要な前提になる。1台のサーバーで達成できる規模ではないため、処理をどう分散させるかが論点になる。

アーキテクチャ概要

要件を満たすクローラは、次のコンポーネントで構成する。

シードURL
URLフロンティア
HTMLダウンローダ
DNSリゾルバ
コンテンツパーサ
コンテンツ収集済み判定
コンテンツストレージ
URL抽出
URLフィルタ
URL訪問済み判定
URLストレージ

これらを組み合わせた全体構成は次の通りである。

点線でつないだ要素は、処理の流れそのものではなく、各工程が参照する先である。HTMLダウンローダはDNSリゾルバでホスト名をIPアドレスに変換し、2つの判定はそれぞれ対応するストレージに問い合わせて行う。

シードURL

シードURL（seed URL）は、クロールの出発点となるURLである。ここから到達できる範囲が、そのままクローラの守備範囲になるため、できるだけ多くのページへリンクをたどれるURLを選ぶ必要がある。

選び方に唯一の正解はなく、何を集めたいかによって決まる。代表的な分け方は次の2つである。

地域で分ける: 国や地域ごとに、その地域で人気のあるサイトを起点にする。地域が違えばリンクされる先も異なるため、幅広く到達しやすくなる
トピックで分ける: ショッピング、スポーツ、医療といったカテゴリごとに、別のシードURLを用意する

本記事の目的は検索インデックスの作成であり、対象を特定の分野に絞らない。そのため、これらの考え方を組み合わせて幅広い起点を用意することになる。

URLフロンティア

URLフロンティア（URL frontier）は、ダウンロード待ちのURLを保持するコンポーネントである。シードURLが最初に置かれる場所であり、URL抽出で新たに見つかったURLが戻ってくる場所でもある。

担う役割は「次にどのURLをダウンロードするか」を決めることであり、単純な先入れ先出し（FIFO）のキューとして扱うこともできる。ただし要件を満たすには、次のような点を考慮する必要がある。

ポライトネス: 同一のサイトへ短時間に集中してリクエストを送らない
優先度: 重要なページを先に取得する
鮮度: 更新されたページを再度取得する

これらをどう実現するかは、詳細設計で扱う。

HTMLダウンローダ

HTMLダウンローダ（HTML downloader）は、URLフロンティアから受け取ったURLにHTTPでアクセスし、ページのHTMLを取得するコンポーネントである。要件の「1秒あたり数百ページ」を実際にこなす部分であり、クローラの中心となる。

ただし、クロールを禁止されているページを取得してはならない。この点をどう守るかは、詳細設計で扱う。

DNSリゾルバ

DNSリゾルバ（DNS resolver）は、URLに含まれるホスト名をIPアドレスに変換するコンポーネントである。HTMLダウンローダがページを取得するには、example.com のようなホスト名ではなくIPアドレスが必要になるため、ダウンロードの前段で必ず通る処理になる。

コンテンツパーサ

コンテンツパーサ（content parser）は、ダウンロードしたHTMLを解析して扱える形に変換するコンポーネントである。以降の工程で使うページの中身やリンクを、ここで取り出せる状態にする。

解析にはCPUと時間を要するため、ダウンロードの流れの中で行うと取得の速度を落としてしまう。そのため独立したコンポーネントとして分離する。

コンテンツ収集済み判定

コンテンツ収集済み判定（content seen?）は、解析したページの内容がすでに収集済みのものと同じかどうかを判定する工程である。要件の「重複コンテンツがあるページは無視する」に対応する。

Web上には、同じ内容のページが別々のURLで存在することが珍しくない。

SEOツールのRaven Toolsが約89万サイトをクロールした調査では、クロールしたページの29%に重複コンテンツが見られたと報告されています。無視できる量ではありません。

URLが違えば訪問済み判定では弾けないため、内容そのものを突き合わせて判定する。すでに収集済みと分かったページはここで処理を打ち切り、保存もURL抽出も行わない。

コンテンツストレージ

コンテンツストレージ（content storage）は、収集したHTMLページを保存しておくコンポーネントであり、次の2つの役割を担う。

収集したページの保存: ここに溜めた内容が、検索インデックスを作るための材料になる
収集済み判定の問い合わせ先: 新しく取得したページが収集済みかどうかを、保存されている内容と突き合わせて判断する

保存先は、データ量に応じて使い分ける。要件より収集したページは最長5年間保存するが、概算見積もりのとおり5年で約30PBに達するため、すべてをメモリに載せることはできない。

大半はディスクに保存する
アクセスの多い人気のコンテンツはメモリに保持し、読み出しのレイテンシーを抑える

URL抽出

URL抽出（link extractor）は、解析したHTMLからリンクを取り出す工程である。ここで取り出したURLが、次の巡回先の候補になる。

対象となるのは、HTML内のアンカータグに書かれたリンクである。

<a href="https://example.com/page">リンク</a>

なお、href の値は必ずしも https:// から始まる完全な形とは限らず、/page のようにパスだけが書かれていることも多い。この場合は、取得元のページのURLを補って完全なURLに直す必要がある。

URLフィルタ

URLフィルタ（URL filter）は、抽出したURLのうち巡回する必要のないものを除外する工程である。除外の対象は次のようなものである。

対象外のコンテンツ: 要件よりHTMLページのみを扱うため、画像・動画・PDFなどを指すURL
アクセスできないURL: エラーが返ることが分かっているもの
クロールを禁止されているサイト: 巡回してほしくないと表明しているサイトのURL

ここで落としておけば、以降の判定やダウンロードの対象そのものが減る。無駄な処理を早い段階で切り捨てるのがこの工程の役割である。

URL訪問済み判定

URL訪問済み判定（URL seen?）は、フィルタを通過したURLがすでに訪問したもの、あるいはフロンティアに積まれているものかどうかを判定する工程である。

同じページが複数のサイトからリンクされていれば、そのURLは何度でも抽出される。この判定がなければ同じページを延々と取得し続けることになるため、クローラの巡回はここで成立している。判定は次に述べるURLストレージへの問い合わせで行い、通過した未訪問のURLだけがフロンティアへ進む。

URLストレージ

URLストレージ（URL storage）は、すでに訪問したURLを保存しておくコンポーネントである。URL訪問済み判定の問い合わせ先であり、判定を通過した未訪問のURLはここに記録されたうえでフロンティアへ進む。

コンテンツストレージが「ページの中身」を保持するのに対し、こちらが保持するのは「どのURLを処理したか」という記録である。取り出すと消えるURLフロンティアとは異なり、巡回を続けるかぎり蓄積され続ける。

クロールのワークフロー

ここまでに挙げたコンポーネントが、実際にどうつながって動くのかを通して追う。

図中の番号は、次の手順に対応する。大きく3つのまとまりに分けられる。

ページを取得する

1 シードURLをURLフロンティアに追加する
2 HTMLダウンローダが、フロンティアからURLを1つ取り出す
3 DNSリゾルバで、ホスト名をIPアドレスに変換する
4 HTMLを取得し、コンテンツパーサが解析する

コンテンツの重複を判定する

5 収集済みかをコンテンツストレージに問い合わせる → 一致すれば破棄して打ち切る
6 未収集であればコンテンツストレージに保存し、URL抽出でリンクを取り出す

次に巡回するURLを選ぶ

7 URLフィルタが、対象外のコンテンツや禁止されたサイトのURLを除外する
8 訪問済みかをURLストレージに問い合わせる → 記録があれば破棄する
9 未訪問であればURLストレージに記録し、URLフロンティアに追加する（手順2へ戻る）

基本的なアルゴリズムで示した3ステップ（ダウンロード → URL抽出 → URLリストに追加）が骨格であり、そこに2つの判定（コンテンツが収集済みか、URLが訪問済みか）とURLフィルタが加わった形になっている。

詳細設計

全体の構成と流れが決まったので、ここからは主要な論点を個別に掘り下げる。

巡回の順序
URLフロンティアの設計
HTMLダウンローダの設計
堅牢性の確保
拡張性の確保
問題のあるコンテンツの検知

巡回の順序

Webは、ページをノード、リンクをエッジとする巨大なグラフとみなせる。クロールはこのグラフをたどる探索であり、たどり方には深さ優先探索（DFS）と幅優先探索（BFS）がある。

深さ優先探索（DFS: depth-first search）: 1本のリンクをたどれるところまで先へ先へと潜っていき、行き止まったら分岐点まで戻って次のリンクへ進みます
幅優先探索（BFS: breadth-first search）: まず今のページのリンクをすべてたどってから、その先のリンクへ進みます。起点から近い順に広がっていきます

DFSは A → B → D と潜ってから C に戻り、BFSは A → B → C と近い順に見てから D へ進む。

このうちDFSは適さない。リンクをたどれる深さには限りがなく、一度潜り始めるとどこまで深くなるか分からないためである。

そこで、リンクの近い順にたどるBFSを使う。これはFIFOのキューで実現でき、URLフロンティアをキューとして扱う設計と一致する。ただしBFSにも、そのままでは次の2つの問題がある。

同じホストに集中する: あるページに貼られたリンクの大半は、同じホスト内の別ページを指している。そのままキューに積むと、同一サイトへ短時間に大量のリクエストを送ることになり、ポライトネスの要件を満たせない
優先度を付けられない: BFSはすべてのURLを平等に扱う。実際にはページごとに重要度が異なり、重要なページから先に取得したい

つまりURLフロンティアは、単なるFIFOキューでは足りない。

URLフロンティアの設計

URLフロンティアで挙げた3つの考慮点（ポライトネス・優先度・鮮度）を、どう実現するかを見ていく。

このうち優先度とポライトネスは、キューを2段に分けて両立させる。前段のフロントキュー（front queue）で優先度ごとに、後段のバックキュー（back queue）でホストごとに振り分ける構成である。

1つのURLは、次の順に2段を通る。

プライオリタイザが優先度を割り当て、対応するフロントキューに入れる
フロントキューセレクタが、優先度の高いキューほど高い確率で選び、URLを取り出す
バックキュールータが、そのURLをホストに対応するバックキューへ入れる
バックキューセレクタが選んだキューから、担当ワーカーがURLを取り出してダウンロードする

段ごとに決めていることが異なる。

段	決めること	満たす要件
フロントキュー	どのURLを先に流すか	優先度
バックキュー	どのホストへ、いつアクセスするか	ポライトネス

フロントキュー（優先度）

すべてのURLを平等に扱うのではなく、重要なページから先に取得する。重要度は、ページの人気度やトラフィック量、更新の頻度といった指標から決める。

プライオリタイザ（prioritizer）: URLに優先度を割り当て、対応するフロントキューへ入れる
フロントキューセレクタ（front queue selector）: 取り出すキューを選ぶ。優先度の高いキューほど高い確率で選ぶことで、重要なページが先に処理される

バックキュー（ポライトネス）

同一のホストへ短時間に大量のリクエストを送らないようにする。考え方は単純で、同じホストへのダウンロードは一度に1つだけとし、その間に待ち時間を入れるというものである。

バックキュールータ（back queue router）: ホスト名とキューの対応表を持ち、同じホストのURLは必ず同じキューへ入れる
バックキューはホスト単位: 1つのキューには、同じホストのURLだけが入る
バックキューセレクタ（back queue selector）: 各ワーカーが担当するキューを選ぶ。1つのワーカーは1つのキューだけを担当し、ダウンロードのたびに一定時間待つ

こうすると、あるホストへのアクセスは常に1つのワーカーが順番に行うことになり、同時に何本もリクエストが飛ぶことがなくなる。なお優先度が効くのはバックキューに入るまでで、いったんバックキューに入った後は、ホストごとの順番待ちになる。

鮮度

要件に「新規追加・編集ページも考慮する」があるため、一度取得したページも再び取得する必要がある。ただし、すべてのページを同じ頻度で取り直すのは無駄が多い。次のように対象を絞る。

更新頻度の高いページを優先する: 過去の更新履歴をもとに判断する
重要なページを優先する: よく見られるページほど、内容を新しく保つ価値が高い

保存先

保存先は、2つの制約の板挟みで決まる。

すべてをメモリには載せられない: 1ページから多数のリンクが見つかるため、フロンティアは取り出す量より積む量のほうが多く、クロールが進むほど膨らみ続ける
すべてをディスクに置くと遅い: ディスクへのアクセスはメモリより桁違いに遅く、毎秒数百ページを処理する裏で大量のURLが出入りするため、1件ごとにディスクを触ると律速になる

そこで大半のURLはディスクに保存し、エンキュー（追加）とデキュー（取り出し）のためのバッファだけをメモリに置く。

HTMLダウンローダの設計

HTMLダウンローダには2つの課題がある。クロールを禁止されたページを取得しないことと、毎秒数百ページという速度を出すことである。

robots.txt の遵守

多くのサイトは robots.txt（Robots Exclusion Protocol）というファイルをルートに置き、クローラがアクセスしてよいパスを宣言している。

User-agent: *
Disallow: /private/
Disallow: /tmp/

上の例は、すべてのクローラに対して /private/ と /tmp/ 以下へのアクセスを禁じている。ダウンローダはページを取得する前に対象サイトの robots.txt を確認し、許可されたパスだけを取得する。

なお robots.txt は頻繁に変わるものではないため、毎回取得するのは無駄である。取得した内容は一定期間キャッシュして使い回す。

パフォーマンスの最適化

概算見積もりのとおり、平常時で毎秒約400ページ、ピーク時で約800ページを取得し続ける必要がある。1台のサーバーで達成できる規模ではないため、次のような手を打つ。

分散クロール: クローラを複数のサーバーで動かし、担当するURLをサーバーごとに割り振る。各サーバーの中でも複数のスレッドを走らせる。要件のスケーラビリティは、この分散によって満たす
DNSキャッシュ: ホスト名の解決はDNSサーバーへの問い合わせであり、応答を待つ時間が発生する。1件ごとに問い合わせると待ち時間が積み上がるため、ホスト名とIPアドレスの対応をキャッシュし、定期的に更新する
地理的な配置: クロールするサーバーを、対象のサイトに地理的に近い場所へ置く。通信距離が短いほどダウンロードは速くなる
短いタイムアウト: 応答の遅いサーバーを待ち続けると、その間ワーカーが止まってしまう。待つ時間の上限を決め、超えたら打ち切って次のURLへ進む

堅牢性の確保

クロールの相手はWeb全体であり、こちらの都合に合わせてはくれない。不正なHTMLを返すサイトもあれば、応答しないサーバーもある。加えて、クローラ自身も数か月にわたって動き続けるため、途中でサーバーが落ちることも前提に置く必要がある。次の4点で備える。

コンシステントハッシュ: どのダウンローダがどのURLを担当するかを決めるのに使う。サーバーを増減させても担当の割り当てが大きく崩れないため、障害時の切り離しや増設に耐えられる
クロール状態の保存: URLフロンティアの中身や訪問済みURLといった状態を、定期的にディスクへ書き出す。サーバーが落ちても、保存した時点から再開できる
例外処理: 1つのURLで発生したエラーで全体を止めない。そのURLの処理だけを打ち切り、次へ進む
データの検証: 受け取った内容が想定した形式かを確認し、不正なデータが後続の工程へ流れないようにする

コンシステントハッシュについては、同シリーズの「コンシステントハッシュって何？ ─ 分散システムのデータ分散を支える仕組みを学ぶ！」で扱っています。

なお、要件で挙げた「クローラを無限に巡回させ続ける罠」への対処は、問題のあるコンテンツの検知で扱う。

拡張性の確保

本記事の要件では対象をHTMLページに絞ったが、運用を続ければ「画像も集めたい」「PDFも対象にしたい」といった要望が出てくる。そのたびにクローラ全体を作り直すことにならないよう、新しい種類のコンテンツを、既存の流れを変えずに追加できる構造にしておく。

やり方は、処理を差し込める場所（プラグイン）を用意しておくことである。

実線が既存の流れで、点線でつないだものが追加するモジュールである。

PNGダウンローダ: 画像を集めたくなったときに、コンテンツパーサの後ろに差し込む
Webモニタ: 著作権侵害の監視など、別の目的の処理を差し込む

いずれも既存のコンポーネントには手を入れず、新しいモジュールを追加するだけで済むのがねらいである。要件の「新しい種類のコンテンツに最小限の変更で対応できる」は、この形で満たす。

問題のあるコンテンツの検知

Web上には、収集する価値がないどころか、クローラの動作そのものを妨げるコンテンツが存在する。代表的なものは次の3つである。

重複コンテンツ

前述のとおり、Web上のページには重複が多く含まれる。同じ内容を何度も保存すれば、ストレージも処理時間も無駄になる。

内容をそのまま比較すると1ページ500KBの突き合わせになり現実的でないため、ページのハッシュ値を比較する。値が一致すれば同じ内容とみなす。

スパイダートラップ

スパイダートラップ（spider trap）は、クローラを無限に巡回させ続けるページである。たとえば次のように、いくらでも深い階層を作れるURLがこれにあたる。

example.com/foo/bar/foo/bar/foo/bar/...

このようなページは意図的に作られることも、カレンダーのように「次の月」へのリンクが際限なく続く構造として偶然生まれることもある。いずれもクローラはたどり続けてしまい、そこから抜け出せなくなる。

完全に見分ける方法はない。現実的な対処は次のようなものである。

URLの長さや階層の深さに上限を設ける: 一定を超えたURLはたどらない
手動で除外リストに加える: 罠だと分かったサイトを、URLフィルタで弾く

データノイズ

広告、スクリプト、スパムページなど、収集しても価値のないコンテンツである。クロールの妨げにはならないが、保存しても検索インデックスの役に立たない。可能なかぎり除外する。

まとめ

Webクローラの設計で掲げた「要件」と、それに応えた「設計」を整理する。

要件	設計上の対応
1か月あたり10億ページの収集	分散クロール（複数サーバー × 複数スレッド）で毎秒数百ページを処理する
HTMLページのみを対象とする	URLフィルタで画像・動画・PDFなどのURLを除外する
新規追加・編集ページへの追従	URLフロンティアで鮮度を考慮し、更新頻度の高いページを優先して再取得する
最長5年間の保存	コンテンツストレージに保存する（約30PB）。大半はディスク、人気のものはメモリ
重複コンテンツの無視	コンテンツ収集済み判定で、ページのハッシュ値を比較して弾く
スケーラビリティ	担当URLをコンシステントハッシュでサーバーに割り当てる
堅牢性	クロール状態の保存、例外処理、データの検証、罠への上限設定
ポライトネス	バックキューでホストごとに分け、1ワーカーが待ち時間を挟みながら順に処理する
拡張性	新しい処理をプラグインとして差し込める構造にする

そのうえで、設計の中心となる論点は次の2つである。

URLフロンティアの2段構え: 前段のフロントキューで優先度順に、後段のバックキューでホストごとに振り分ける。単純なFIFOキューでは両立しない「重要なページから取得する」と「相手に負荷をかけない」を、キューを2段に分けることで同時に満たす
2つの判定が巡回を成立させる: 抽出したURLをそのまま積み続けると同じページを延々と取得してしまう。URLが訪問済みかとコンテンツが収集済みかの2つを問い合わせることで、無限の巡回と重複の保存を防いでいる

参考文献

この記事は以下の情報を参考にして執筆しました。