ウェブクローラーの設計

質問

もしあなたがウェブクローラーを設計しているとしたら、どのように無限ループに陥るのを避けますか」というインタビューの質問に遭遇しました。

最初からどのように始まるのでしょうか。 Google がいくつかのハブ ページ、たとえば何百ものハブ ページからスタートしたとします (これらのハブ ページがそもそもどのように発見されたかは別のサブクエスチョンです)。 Google がページからのリンクをたどっていくと、以前に訪問したページをたどらないように、ハッシュ テーブルを作成し続けるのでしょうか。

同じページが2つの名前（URL）を持っている場合、例えばURL短縮ツールなどがある昨今ではどうでしょうか。

私はGoogleを例にとってみました。Googleはウェブクローラーのアルゴリズムやページランキングなどがどのように機能しているかは公表していませんが、何か想像がつきますか？

どのように解決するのですか？

詳細な答えを知りたい場合は 3.8節 この論文 をご覧ください。最新のスクレイパーの URL を見るテストが説明されています。

リンクを抽出する過程で、どんな Web クローラーは、同じドキュメントへの複数の リンクに遭遇することがあります。これを避けるために ドキュメントを何度もダウンロードし、処理することを避けるため 何度もダウンロードし、処理することを避けるため、抽出されたリンクごとにURL 抽出された各リンクに対して を URL フロンティアに追加する前に実行する必要があります。 (別の設計としては URL がフロンティアから削除されたときに URL-seen テストを実行する を実行することです。 が、このアプローチでは より大きなフロンティアになります)。

を実行するために URL を見るテストを行うために、Mercator が見たすべての URLを正規化した形で 形式で、URL セットと呼ばれる大きなテーブルに格納します。ここでも、エントリーが多すぎて が多すぎてメモリに収まらないので、ドキュメントフィンガープリントセットと同様に ドキュメントフィンガープリントセットのように、URLセット セットはほとんどディスクに保存されます。

スペースを節約するために スペースを節約するため、各 URL のテキスト表現を の各URLのテキスト表現を保存せず、固定サイズのURL セットにはテキスト表現を保存せず、固定サイズの のチェックサムを格納します。フィンガープリントとは異なり に提示されるフィンガープリントとは異なり、ストリームフィンガープリントは、コンテンツシーンの ドキュメントフィンガープリントセットに提示されるフィンガープリントとは異なり、URL セットに対してテストされる URL のストリームは に対してテストされる URL のストリームは、URL のセットに対して は非自明な量の局所性を持っています。そのため の操作回数を減らすために ディスクの操作回数を減らすために をインメモリキャッシュとして保持する。 このキャッシュの直感的な理由は、以下のとおりです。 あるURLへのリンクは非常に一般的である。 をメモリ内にキャッシュしておくと、メモリ内 をメモリ内にキャッシュすることで、高いメモリ内ヒット率 率につながるからです。

実際、2^18 エントリのメモリ内キャッシュを使用すると 2^18エントリのメモリ内キャッシュとLRUライクな クロック置換ポリシーを使用して、私たちは インメモリ キャッシュの全体的なヒット率は 66.2%、ヒット率は 9.5% です。 66.2%、そして最近追加されたURLのテーブルのヒット率は9.5%です。 のヒット率を達成した。 のヒット率を達成し、正味のヒット率は75.7%であった。さらに で失敗したリクエストのうち、24.3%が また，人気 URL のキャッシュと最近追加された URL のテーブ また、人気URLのキャッシュと最近追加されたURLのテーブルの両方で失敗した24.3%のリクエストのうち、約 1=3がバッファにヒットしている。 ランダムアクセスファイルの実装では このバッファはユーザースペースに存在する。このため このバッファリングの正味の結果は URLセットに対して行う各メンバーシップテストは を実行すると、平均で 0.16のシークと0.17のリードカーネル の呼び出しが発生します（そのうちの一部は カーネルのファイルシステムバッファから提供される バッファから提供されます)。つまり、各URLセットのメンバーシップ テストが引き起こすカーネル呼び出しの数は を呼び出すことになります。 ドキュメントフィンガープリントセットのメンバーシップテストの6分の1のカーネルコールが発生します。この この節約は、純粋に URL の局所性（つまり、人気のある URL の繰り返し）に起因するものです。 クロール中に遭遇する URL のストリームに内在する URL の局所性（つまり、人気のある URL の繰り返し）の量に起因します。 の量によるものです。

基本的に、彼らはすべての URL をハッシュ関数でハッシュ化し、各 URL に対して一意のハッシュを保証しています。Google は、そのハッシュ関数をオープンソースにさえしています。 CityHash

警告!

ボットトラップについて話しているかもしれません!!! ボットトラップとは、ユニークなURLで新しいリンクを生成し続けるページのセクションのことで、そのページが提供するリンクをたどることで、本質的に無限ループに陥ることになります"。ループは同じURLにアクセスした結果なので、これは正確にはループではありませんが、クロールを避けるべきURLの無限連鎖なのです。

2012年12月13日更新 <ストライク - 世界が終わるとされた翌日 :)

Fr0zenFyr のコメント: もし人が AOPIC を使えば、無限ループのようなボットトラップを避けるのはかなり簡単です。以下は、AOPIC がどのように機能するかの要約です。

1. N 個の種ページのセットを取得します。
2. クロールが始まる前に、各ページが X/N クレジット (つまり同量のクレジット) を持つように、各ページに X 量のクレジットを割り当てる。
3. P が最も高いクレジット量を持つページ P を選択します (または、すべてのページが同じクレジット量である場合は、ランダムなページをクロールします)。
4. ページPをクロールします（クロールされたときのPのクレジットが100だったとします）。
5. ページPからすべてのリンクを抽出します（仮に10本あるとします）。
6. Pのクレジットを0に設定します。
7. 10%の "tax" を取り、Lambda ページに割り当てます。
8. Pの元のクレジットからPのページで見つかった各リンクのクレジットを等量割り当てる - 税：したがって、（100（Pクレジット）-10（10％税））/10（リンク）=各リンクごとに9クレジットです。
9. ステップ3から繰り返します。

Lambdaページは継続的に税金を徴収しているので、最終的には最大のクレジット量を持つページとなり、それを"クロール"する必要があります。引用符でquot;crawl"と言っているのは、実際にLambdaページに対してHTTPリクエストを行うわけではなく、そのクレジットを取得して、それを均等に 全て に均等に分配しています。

ボットトラップは内部リンクにしかクレジットを与えず、外部からのクレジットはほとんど得られないため、（課税による）クレジットをラムダページに継続的に漏えいさせることになります。Lambda ページはそのクレジットをデータベース内のすべてのページに均等に分配し、サイクルごとにボットトラップページはますますクレジットを失い、ほとんど二度とクロールされないほど少ないクレジットになります。優良なページは、他のページからのバックリンクでクレジットを獲得していることが多いので、このようなことは起こりません。これはまた、動的なページランクをもたらし、あなたが気づくことは、あなたのデータベースのスナップショットを取るときはいつでも、彼らが持っているクレジットの量によってページを並べることです。 真のページランク .

これは無限ループ的なボットトラップを避けるだけですが、そこには 他にも多くのボットトラップがあります。 があり、それを回避する方法もあります。