🙎🏽 🈳 🤲🏼 ボンネットの下を検索します。 👩🏽‍🤝‍👨🏾 🐡 🍼

インターネット上の情報を検索する機能は不可欠です。お気に入りの検索エンジンで「検索」ボタンをクリックすると、1秒後に答えが得られます。

ほとんどの人は「裏側」で何が起こっているのかまったく考えていませんが、検索エンジンは有用なツールであるだけでなく、複雑な技術製品でもあります。最新の検索システムは、ビッグデータ、グラフおよびネットワーク理論、自然言語テキスト分析、機械学習、パーソナライゼーション、ランキングなど、コンピューター業界の高度な成果のほとんどすべてを使用しています。検索エンジンがどのように機能するかを理解することで、技術開発のレベルを知ることができるため、どのエンジニアでもこれを理解するのに役立ちます。

いくつかの記事では、検索エンジンがどのように機能するかを段階的に説明し、さらに、説明のために、根拠のないように独自の小さな検索エンジンを構築します。もちろん、この検索エンジンは「トレーニング」され、GoogleまたはYandexの内部で起こっていることを非常に強力に単純化しますが、一方で、あまり単純化しません。

最初のステップはデータ収集（または、クロールとも呼ばれます）です。

ウェブはグラフです

私たちが興味を持っているインターネットの部分はウェブページで構成されています。検索システムがユーザーの要求で特定のWebページを見つけることができるようにするには、そのようなページが存在し、要求に関連する情報が含まれていることを事前に知る必要があります。ユーザーは通常、検索エンジンからWebページの存在について学習します。検索エンジンはWebページの存在をどのように知るのですか？結局のところ、誰も彼女にこれを明示的に報告する義務はありません。

幸いなことに、Webページはそれ自体では存在せず、互いにリンクしています。検索ロボットはこれらのリンクをたどり、すべての新しいWebページを発見できます。

実際、ページの構造とページ間のリンクは、「グラフ」と呼ばれるデータ構造を記述しています。定義によるグラフは、頂点（この場合はWebページ）とエッジ（この場合は頂点間のリンク、ハイパーリンク）で構成されます。

グラフの他の例は、ソーシャルネットワーク（人々-ピーク、エッジ-友情関係）、ロードマップ（都市-ピーク、エッジ-都市間の道路）、さらにはチェスのすべての可能な組み合わせ（チェスの組み合わせが頂点であり、ピーク間のエッジが存在する場合） 1つの動きで1つの位置から別の位置に移動できます）。

グラフは、方向がエッジに示されているかどうかに応じて、方向付けられています。ハイパーリンクは一方向にしか移動できないため、インターネットは有向グラフです。

さらに説明するために、インターネットは強力に接続されたグラフであると想定します。つまり、インターネット上のどこからでも開始することで、他のポイントに到達できると仮定します。この仮定は明らかに間違っています（どこからでもリンクされない新しいWebページを簡単に作成できるため、そこにアクセスすることはできません）。リンクは検索にはあまり関心がありません。

Webグラフのごく一部：

グラフトラバーサルアルゴリズム：幅と深さの検索

深さ検索

2つの古典的なグラフトラバーサルアルゴリズムがあります。最初の-シンプルで強力な-アルゴリズムは、深さ優先検索（DFS）と呼ばれます。再帰に基づいており、次の一連のアクションを表します。

処理された頂点の現在の頂点をマークします。
現在の頂点を処理します（検索ロボットの場合、処理は単にコピーを保存します）。
現在の頂点から移動できるすべての頂点について、頂点がまだ処理されていない場合、再帰的に処理します。

このアプローチを文字通り実装するPythonコードは次のとおりです。

seen_links = set() def dfs(url): seen_links.add(url) print('processing url ' + url) html = get(url) save_html(url, html) for link in get_filtered_links(url, html): if link not in seen_links: dfs(link) dfs(START_URL)

完全なgithubコード

ほぼ同じ方法で、たとえば、標準のLinux wgetユーティリティは-rパラメーターを使用して機能します。これは、サイトを再帰的にポンプアウトする必要があることを示します。

 wget -r habrahabr.ru

深さ検索方法は、小さなサイトのWebページをクロールするために適切に適用されますが、インターネット全体をクロールするにはあまり便利ではありません。

その中に含まれる再帰呼び出しは、あまりうまく並行していません。
この実装を使用すると、アルゴリズムはリンクをどんどん深くなり、最終的には再帰呼び出しスタックに十分なスペースがなくなる可能性が高くなり、スタックオーバーフローエラーが発生します。

一般に、これらの問題は両方とも解決できますが、代わりに別の古典的なアルゴリズムである幅優先探索を使用します。

広い検索

幅優先検索（BFS）は深さ検索と同様の方法で機能しますが、開始ページからの距離の順にグラフの上部を回ります。このため、アルゴリズムは「キュー」データ構造を使用します。キューでは、要素を最後に追加し、最初からそれらを取得できます。

アルゴリズムは次のように説明できます。
最初のピークをキューと多くの「表示された」ピークに追加します。
キューが空でない場合、処理のためにキューから次の頂点を取得します。
トップを加工します。
「表示された」頂点に含まれていない、処理された頂点からのすべてのエッジ：
1. 「seen」に追加します。
2. キューに追加します。
ステップ2に進みます。

Pythonコード：

 def bfs(start_url): queue = Queue() queue.put(start_url) seen_links = {start_url} while not (queue.empty()): url = queue.get() print('processing url ' + url) html = get(url) save_html(url, html) for link in get_filtered_links(url, html): if link not in seen_links: queue.put(link) seen_links.add(link) bfs(START_URL)

完全なgithubコード

キューには、最初に最初のリンクから1つのリンク、次に2つのリンク、次に3つのリンクなどの距離にある頂点があります。つまり、幅優先探索アルゴリズムは常に最短パスで頂点に到達します。

もう1つの重要なポイント：この場合、キューと「見られる」ピークの多くは単純なインターフェイス（追加、取得、エントリのチェック）のみを使用し、これらのインターフェイスを介してクライアントと通信する別のサーバーに簡単に移動できます。この機能により、 マルチスレッドグラフトラバーサルを実装できます。同じキューを使用する複数のプロセッサを同時に実行できます。

Robots.txt

実際の実装を説明する前に、適切に動作するクローラーは、robots.txtファイルでWebサイトの所有者によって設定された禁止事項を考慮していることに注意したいと思います。たとえば、lenta.ruのrobots.txtの内容は次のとおりです。

 User-agent: YandexBot Allow: /rss/yandexfull/turbo User-agent: Yandex Disallow: /search Disallow: /check_ed Disallow: /auth Disallow: /my Host: https://lenta.ru User-agent: GoogleBot Disallow: /search Disallow: /check_ed Disallow: /auth Disallow: /my User-agent: * Disallow: /search Disallow: /check_ed Disallow: /auth Disallow: /my Sitemap: https://lenta.ru/sitemap.xml.gz

ここでは、Yandexロボット、Google、その他すべての人を訪問することを禁じられているサイトのいくつかのセクションが定義されていることがわかります。 Pythonでrobots.txtの内容を考慮するために、標準ライブラリに含まれるフィルターの実装を使用できます。

 In [1]: from urllib.robotparser import RobotFileParser ...: rp = RobotFileParser() ...: rp.set_url('https://lenta.ru/robots.txt') ...: rp.read() ...: In [3]: rp.can_fetch('*', 'https://lenta.ru/news/2017/12/17/vivalarevolucion/') Out[3]: True In [4]: rp.can_fetch('*', 'https://lenta.ru/search?query=big%20data#size=10|sort=2|domain=1 ...: |modified,format=yyyy-MM-dd') Out[4]: False

実装

そのため、インターネットを一周し、さらに処理するために保存する必要があります。

もちろん、デモンストレーションのために、インターネット全体を回って保存することはできません-非常に高価ですが、潜在的にインターネット全体のサイズに拡大縮小できるという事実を考慮してコードを開発します。

これは、同時に多数のサーバーで作業し、結果を簡単に処理できる何らかの種類のストレージに保存する必要があることを意味します。

ソリューションの基礎としてAmazon Web Servicesを選択しました。特定の数のマシンを簡単に作成し、結果を処理して、 Amazon S3分散ストレージに保存できるからです。同様のソリューションは、たとえばgoogle 、 microsoftおよびYandexです。

開発したソリューションのアーキテクチャ

私のデータ収集スキームの中心的な要素はキューサーバーです。このサーバーには、ダウンロードして処理するURLのキューと、プロセッサが既に「見た」多くのURLが格納されています。私の実装では、それらは最も単純なキューに基づいており、Pythonデータ構造を設定しています。

実際の本番システムでは、おそらくそれらの代わりに、キュー（たとえば、 kafka ）およびセットの分散ストレージ（たとえば、 erospikeなどのデータベースのメモリ内キー値クラスのソリューションが適切です）に既存のソリューションを使用する価値があります。これにより、完全な水平スケーラビリティを実現できますが、一般的にキューサーバーの負荷はそれほど大きくないため、私の小さなデモプロジェクトでは、このような小規模では意味がありません。

稼働中のサーバーは、ダウンロード用の新しいURLグループを定期的に選択し（キューに不必要な負担をかけないように、すぐに多くを取り除きます）、Webページをダウンロードし、s3に保存し、新しいキューをダウンロードキューに追加します。

URLを追加する負担を軽減するために、追加もグループで行われます（Webページで見つかったすべての新しいURLを一度に追加します）。また、作業ノードの側で既に追加されたページを事前にフィルタリングするために、多くの「表示された」URLを運用サーバーと定期的に同期します。

ダウンロードしたWebページを分散クラウドストレージ（S3）に保存します-これは後で分散処理に便利です。

キューは、追加および処理されたリクエストの数に関する統計を統計サーバーに定期的に送信します。作業ノードごとに合計で個別に統計を送信します。これは、ダウンロードが正常に行われていることを明確にするために必要です。個々の作業マシンのログを読み取ることは不可能なので、チャートで動作を監視します。ダウンロードを監視するためのソリューションとして、グラファイトを選択しました。

クローラーの打ち上げ

すでに書いたように、インターネット全体をダウンロードするには膨大なリソースが必要なので、そのほんの一部、つまりhabrahabr.ruとgeektimes.ruというサイトに限定しました。ただし、制限はかなり条件付きであり、他のサイトに拡張することは、利用可能な鉄の量の問題です。実行するために、Amazonクラウドに新しいクラスターを作成するシンプルなスクリプトを実装し、そこにソースコードをコピーして、対応するサービスを開始します。

 #deploy_queue.py from deploy import * def main(): master_node = run_master_node() deploy_code(master_node) configure_python(master_node) setup_graphite(master_node) start_urlqueue(master_node) if __name__ == main(): main()

 #deploy_workers.py #run as: http://<queue_ip>:88889 from deploy import * def main(): master_node = run_master_node() deploy_code(master_node) configure_python(master_node) setup_graphite(master_node) start_urlqueue(master_node) if __name__ == main(): main()

呼び出されたすべての関数を含むdeploy.py スクリプトのコード

統計ツールとしてグラファイトを使用すると、美しいグラフを描くことができます。

赤いグラフは検出されたURLを示し、緑のグラフはダウンロードされたURLを示し、青いグラフはキュー内のURLを示します。期間全体で、550万ページがダウンロードされました。

作業ノードごとに分類された、1分あたりのクロールされたページの数。グラフは中断されず、クロールは通常モードになります。

結果

habrahabrとgeektimesのダウンロードには3日かかりました。

各作業マシンのワーカーのインスタンス数を増やし、ワーカーの数を増やすことで、はるかに高速にダウンロードすることができますが、ハブ自体の負荷は非常に大きくなります。お気に入りのサイトで問題が発生するのはなぜですか？

その過程で、クローラーにいくつかのフィルターを追加し、検索エンジンの開発に関係のない明らかに不要なページを除外し始めました。

開発されたクローラーはデモですが、一般にスケーラブルであり、同時に多数のサイトから大量のデータを収集するために使用できます（ただし、実稼働環境では、 heritrixなどの既存のクロールソリューションに焦点を当てることが理にかなっています。一度だけではなく、定期的に起動し、多くの追加機能を実装する必要がありますが、これまでは無視していました。

クローラーの時代、私はAmazonクラウドに約60ドルを費やしました。合計550万ページをダウンロードし、合計ボリュームは668ギガバイトです。

シリーズの次回の記事では、ビッグデータ技術を使用してダウンロードしたWebページにインデックスを作成し、ダウンロードしたページで実際に検索するための最も簡単なエンジンを設計します。

プロジェクトコードはgithubで入手できます

ボンネットの下を検索します。