Search Mail.Ru、パート2：大規模な検索エンジンのデータ準備アーキテクチャのレビュー

Big Search Engineデータ準備アーキテクチャの概要

前回は、2010年にGo.Mail.Ruがどのように開始されたか、そして以前は検索がどのようだったかを思い出しました 。 この投稿では、全体像を描いてみます-他のユーザーがどのように機能するかについて詳しく説明しますが、最初に検索配信について説明します。

検索エンジンの配布方法

ご要望のとおり、最も人気のある検索エンジンの配信戦略の基本について説明することにしました。



インターネット検索は、ほとんどのユーザーが自分で選択するサービスの1つであり、最強のものがこの戦いに勝つべきだという意見があります。 この立場は私たちにとって非常に魅力的です。この理由から、私たちは常に検索技術を改善しています。 しかし、市場の状況は修正されており、いわゆる「ブラウザ戦争」がそもそも介入しています。



検索がブラウザに関連していなかった時代がありました。 その後、検索エンジンは、ユーザーが自分の裁量でアクセスした別のサイトに過ぎませんでした。 想像してみてください-2006年に登場した第7バージョンまでのInternet Explorerには検索バーがありませんでした。 Firefoxには最初のバージョンから検索バーがありましたが、彼自身は2004年にのみ登場しました。



検索文字列はどこから来たのですか？ ブラウザの作者によって発明されたのではありません-2001年にリリースされたGoogleツールバーに初めて登場しました。 Googleツールバーは、ブラウザに「Google検索への迅速なアクセス」機能、つまりパネルの検索行を追加しました。







Googleがツールバーをリリースしたのはなぜですか？ これが、当時のGoogleのブランドマネージャーであるダグラスエドワーズが彼の本「I'm Feeling Lucky：The Confessions of Google Employee Number 59」で彼の使命を説明する方法です。



「ツールバーはマイクロソフトとの戦争における秘密兵器でした。 Googleは、ブラウザにツールバーを埋め込むことで、ユーザーへのフィルタリングされていないアクセスをめぐって戦いの別の面を開きました。 Bill GatesはPCエクスペリエンスを完全に制御することを望んでおり、Windowsの次のバージョンではデスクトップ上に検索ボックスが組み込まれるという噂がたくさんありました。 Googleの検索ボックスが時代遅れの遺物にならないようにする必要がありました。」



「ツールバーは、マイクロソフトとの戦争における秘密兵器でした。 Googleは、ツールバーをブラウザに統合することで、ユーザーへの直接アクセスの戦いで別の面を開きました。 Bill Gatesは、ユーザーがPCと対話する方法を完全に制御したいと考えていました。次のバージョンのWindowsでは、検索バーがデスクトップに直接インストールされるという噂が広まりました。 Google検索バーが過去の遺物にならないように対策を講じる必要がありました。」



ツールバーはどのように配布されましたか？ はい、すべて同じで、人気のあるソフトウェア： RealPlayer 、Adobe Macromedia Shockwave Playerなど。



他の検索エンジンがツールバー（たとえば、Yahooツールバー）を配布し始めたことは明らかであり、ブラウザーメーカーはこの機会を利用して検索エンジンから追加の収入源を得ることにためらわず、「デフォルト検索エンジン」の概念を導入して検索ラインに組み込みました。



ブラウザーメーカーの事業部門は、明らかな戦略を選択しました。ブラウザーはインターネットへのユーザーのエントリポイントであり、ブラウザーの視聴者はデフォルトの検索設定を使用する可能性が高いので、これらの設定を販売しませんか？ また、インターネット検索は「粘着性」がほとんどない製品であるため、彼らは独自の方法で正しかったのです。



この時点で、さらに詳しく説明する価値があります。 「いや、人は検索に慣れて、自分が信頼するシステムだけを使用します」と多くの人が怒りますが、実際は逆のことを証明します。 たとえば、受信トレイまたはソーシャルアカウントの場合。 何らかの理由でネットワークが利用できず、すぐに別のメールサービスや他のソーシャルネットワークにアクセスしないでください。アカウントに「スタック」しているためです。友人、同僚、家族はそれらを知っています。 アカウントの変更は、長くて苦しいプロセスです。 検索エンジンでは、すべてがまったく異なります。ユーザーは特定のシステムに縛られていません。 何らかの理由で検索エンジンが使用できない場合、ユーザーは座って最終的に機能するのを待ちません-他のシステムに移動するだけです（たとえば、競合他社の1つがクラッシュしたときに、LiveInternetカウンターでこれを明確に確認しました） ） 同時に、すべての検索エンジン（検索行、クエリ、結果ページ）がほぼ同じように配置されているため、ユーザーは事故にあまり苦しみません。 さらに、約90％の場合、ユーザーはどのシステムを検索しても、質問に対する回答を受け取ります。



そのため、一方で検索には実質的にゼロの「粘着性」があります（英語では「粘着性」という特別な用語があります）。 一方、ある種の検索はデフォルトでブラウザにすでにプリインストールされており、かなりの数の人がそこから使用するのが便利であるという理由でのみそれを使用します。 また、検索行の背後の検索がユーザーのタスクを満たしている場合、ユーザーは引き続き使用できます。

私たちは何に来ますか？ 主要な検索エンジンには、ブラウザの検索文字列を争う以外に選択肢がありませんでした。デスクトップ検索製品-ツールバーは、インストールプロセス中にユーザーのブラウザのデフォルト検索を変更します。 この闘争のイニシエーターはグーグルであり、残りは身を守らなければなりませんでした。 たとえば、Yandexの作成者であり所有者であるArkady Volozhのインタビューでそのような言葉を読むことができます。



「2006-2007年 ロシアの検索市場でのGoogleのシェアは拡大し始めましたが、最初はその理由を理解できませんでした。 その後、Googleがブラウザ（Opera、Firefox）に埋め込むことで、Googleが自らを宣伝していることが明らかになりました。 また、独自のブラウザとモバイルオペレーティングシステムのリリースにより、Googleは関連する市場全体を破壊し始めました。」

Mail.Ruも検索であるため、「ブラウザ戦争」から免れることはできません。 他の市場よりも少し遅れて市場に参入しました。 現在、検索の品質は著しく向上しており、私たちの配信は、市場で繰り広げられているツールバーの非常に苦労に対する反応です。 さらに、検索を使用しようとしている人の数が増えていることが結果に満足していることは、私たちにとって本当に重要です。



ところで、私たちの配信ポリシーは、最も近い競合他社の配信ポリシーよりも数倍アクティブではありません。 これは、runetのほとんどのWebサイトにインストールされているカウンターtop.mail.ruで確認できます。 ユーザーが配信製品（ツールバー、独自のブラウザー、パートナーブラウザーのブラウザーボックス）のいずれかを介してオンデマンドでサイトに移動すると、パラメーターclid =がURLに存在します...したがって、配信リクエストの容量を見積もることができます。私たちのものより。



しかし、配布から他の検索エンジンの動作に移りましょう。 結局、他の検索エンジンのアーキテクチャソリューションの研究から、アーキテクチャの内部議論を自然に始めました。 アーキテクチャの詳細については説明しません。代わりに、公開資料へのリンクを示し、重要なソリューションの特徴を強調します。

大規模な検索エンジンでのデータ準備

ランブラー

現在閉鎖されているランブラー検索エンジンには、興味深い建築上のアイデアがたくさんありました。 たとえば、独自のデータストレージシステム（NoSQL、現在そのようなシステムを呼び出すことが流行しているため）および分散コンピューティングHICS（ またはHCS ）について知られており、特にリンクグラフでの計算に使用されました。 HICSでは、検索内のデータの表示を単一の汎用形式で標準化することもできました。



ランブラーのアーキテクチャは、クモの組織において私たちのものとはまったく異なっていました。 私たちのスパイダーは、ダウンロードされたページのアドレスの独自の自己記述ベースで、別個のサーバーとして実行されました。 各サイトをダウンロードするために、個別のプロセスが起動され、ページを同時にダウンロードし、それらを解析し、新しいリンクを強調表示して、すぐにフォローすることができました。 ランブラーのクモはもっと簡単になりました。



1台のサーバーで、Ramblerが認識しているドキュメントのすべてのアドレスが1行に1つずつ、辞書編集順に並べられた大きなテキストファイルが見つかりました。 1日1回、このファイルはバイパスされ、ポンピング用のその他のテキストファイルタスクが生成されました。これは、アドレスのリストからのみドキュメントをダウンロードできる特別なプログラムによって実行されました。 次に、ドキュメントが解析され、リンクが抽出され、すべての既知のドキュメントのこの大きなファイルリストの隣に配置され、ソートされた後、リストが新しい大きなファイルにマージされ、サイクルが再び繰り返されました。



このアプローチの利点は、単純さ、すべての既知のドキュメントの単一のレジストリの存在でした。 欠点は、新しいドキュメントのダウンロードがスパイダーの次の反復でのみ発生する可能性があるため、新しく抽出されたドキュメントアドレスにすぐに移動できないことでした。 さらに、データベースのサイズとその処理速度は1つのサーバーに制限されていました。



それどころか、スパイダーはサイトからのすべての新しいリンクをすばやくたどることができましたが、外部からの管理は非常に不十分でした。 追加のデータをアドレスに「注ぐ」ことは困難でした（サイト内のドキュメントのランク付け、ポンプの優先順位の決定に必要）、データベースをダンプすることは困難でした。

ヤンデックス

Den Raskovalovが講義コースで語ったまで、Yandexの内部検索エンジンについてはあまり知られていませんでした。



そこから、Yandex検索が2つの異なるクラスターで構成されていることがわかります。

• バッチ処理
• リアルタイムデータ処理（これは、タスクの実行の遅延が重要になる可能性のある制御システムでこの用語が使用されるという意味で、実際には「リアルタイム」ではありません。むしろ、ドキュメントができるだけ早く、他者とは無関係にインデックスに入る可能性ですドキュメントまたはタスク、リアルタイムの一種の「ソフト」バージョン）

1つ目は通常のインターネットダウンロードに使用され、2つ目は表示されたばかりの最も興味深いドキュメントのインデックスへの配信に使用されます。 これまではバッチ処理のみを検討します。これは、インデックスがリアルタイムで更新される前にかなり離れていたため、2日ごとにインデックスを更新するために出かけたかったためです。







同時に、Yandexバッチ処理クラスターが外側のスイングクラスターとインデックスクラスターのペアに多少類似しているという事実にもかかわらず、いくつかの重大な違いがありました。

• ページアドレスのベースは1つで、インデックスノードに保存されます。 その結果、2つのデータベースの同期に問題はありません。
• ポンピングロジック制御は、インデックスノードに転送されます。 スパイダーノードは非常に単純なので、インデクサーが指示するものをダウンロードします。 私たちのスパイダー自身が、何をいつダウンロードするかを決定しました。
• そして、非常に重要な違い-内部では、すべてのデータはドキュメント、サイト、リンクのリレーショナルテーブルの形式で表示されます。 当社では、すべてのデータが異なるホストに配信され、異なる形式で保存されました。 データの表形式表示により、データへのアクセスが大幅に簡素化され、さまざまなサンプルを作成して、インデックスの最も多様な分析を取得できます。 このすべてを奪われ、その時点では2つのドキュメントベース（スパイダーとインデクサー）の同期に1週間しかかかりませんでした。この間、両方のクラスターを停止する必要がありました。

グーグル

Googleは間違いなく世界のテクノロジーリーダーであるため、Googleは常にそれに注目し、何を、いつ、なぜ行ったかを分析しています。 もちろん、Googleの検索アーキテクチャは私たちにとって最も興味深いものでした。 残念ながら、グーグルがそのアーキテクチャー機能を公開することはめったにありません。各記事は大きなイベントであり、説明されたテクノロジーを実装する並行オープンソースプロジェクト（時には1つではない）をほぼ瞬時に生成します。



Google検索の機能に興味のある方は、社内のインフラストラクチャに関する最も重要な専門家の1人、 ジェフリーディーン（ジェフリーディーン）のほぼすべてのプレゼンテーションとスピーチを自信を持って学習することをお勧めします。

• 「大規模な情報検索システムの構築における課題」 （スライド）は、ユニバーサル検索の導入前の2008年までスタンフォード大学の学生と大学院生によって作成された最初のバージョンから、Googleの開発方法を学ぶのに役立ちます。 このパフォーマンスのビデオとスタンフォードでの同様のプレゼンテーション「Googleでのソフトウェアシステムの構築と教訓」があります。
• 「MapReduce：大規模クラスターでのデータ処理の簡素化 。 」 この記事では、多数のサーバーで計算を簡単に並列化できる計算モデルについて説明します。 この出版の直後に、オープンソースのHadoopプラットフォームが登場しました。
• 「BigTable：分散構造化ストレージシステム」、BigBase NoSQLデータベースに関するストーリー。HBaseとCassandraの作成に基づいています（ ビデオはこちら 、スライドはこちら ）
• 「MapReduce、BigTable、および大規模なデータセットを処理するためのその他の分散システム抽象化」 は、Googleの最も有名なテクノロジーについて説明しています。

これらのプレゼンテーションに基づいて、Google検索アーキテクチャの次の機能を強調できます。

• データ準備用の表構造。 検索データベース全体は巨大なテーブルに格納されます。キーはドキュメントのアドレスであり、メタ情報は個別の列に格納され、ファミリーに統合されます。 さらに、テーブルは元々、スパースデータを効果的に使用するように作成されました（つまり、すべてのドキュメントから離れた列に値がある場合）。
• 統合分散コンピューティングシステムMapReduce。 データの準備（検索インデックスの作成を含む）は、分散GFSファイルシステム内のBigTableテーブルまたはファイルで実行される一連のmapreduceタスクです。

これはかなり合理的に見えます：既知のすべてのドキュメントアドレスは1つの大きなテーブルに格納され、優先順位が付けられ、リンクグラフ上で計算されます。検索スパイダーはポンプアウトされたページのコンテンツをそこにもたらし、その結果、インデックスが構築されます。



もう1つのGoogleスペシャリストであるDaniel Peng（Daniel Peng）によるBigTableの革新に関する興味深いプレゼンテーションがあります。これにより、数分で新しいドキュメントをインデックスに追加することができます。 この「外部の」テクノロジーはCaffeineという名前で宣伝されており、出版物ではPercolatorと呼ばれていました。 OSDI'2010でのパフォーマンスのビデオはこちらでご覧いただけます 。



非常に無礼に言えば、これは同じBigTableですが、いわゆる トリガー-テーブル内の変更に対して機能するコードをロードする機能。 これまでのところ、データのバッチ処理、つまり 可能であれば、データが結合されて一緒に処理される場合、トリガーへの同じ実装は完全に異なります。 クモが何かをダウンロードし、新しいコンテンツをテーブルに配置したとします。 トリガーがトリガーされ、「新しいコンテンツが登場しました。インデックスを作成する必要があります。」 インデックス作成プロセスがすぐに開始されました。 結果として、検索エンジンのすべてのタスクをサブタスクに分割でき、各タスクは独自のクリックで起動されることがわかりました。 Googleが示したように、大量の機器、リソース、デバッグされたコードにより、新しいドキュメントを追加する問題をわずか1分ですばやく解決できます。



Googleアーキテクチャとリアルタイムインデックス更新システムも示されたYandexアーキテクチャの違いは、Googleが主張したように、インデックスの構築手順全体がトリガーで実行されるのに対し、Yandexは最高の、ほとんどのサブセットに対してのみ行われることです。貴重な文書。

ルセン

別の検索エンジンであるLuceneに言及する価値があります。 これは、Javaで書かれたフリーウェアの検索エンジンです。 ある意味では、Luceneは検索エンジンを作成するためのプラットフォームです。たとえば、Nutchと呼ばれるWeb検索エンジンはそこから発展しています。 実際、Luceneはインデックスと検索エンジンを作成するための検索エンジンであり、NutchはWeb上のドキュメントを検索するとは限らないため、ページをポンピングするスパイダーと同じものです。



実際、Lucene自体には、数十億のドキュメントを備えた大規模なWeb検索エンジンで使用できる興味深いソリューションはあまりありません。 一方、HadoopおよびHBaseプロジェクトを立ち上げたのはLucene開発者であることを忘れないでください（Googleからの新しい興味深い記事が登場するたびに、Luceneの著者は自宅で音声ソリューションを適用しようとしました。たとえば、BigTableクローンであるHBaseが登場しました） 。 ただし、これらのプロジェクトは長い間単独で存在していました。



Lucene / Nutchの私にとって、彼らがHadoopをどのように使用したかは興味深いものでした。 たとえば、Nutchでは、Webをポンピングするための特別なスパイダーが作成されました。これは、Hadoopのタスクの形で完全に実行されました。 つまり スパイダー全体は、MapReduceパラダイムのHadoopで実行されるプロセスにすぎません。 これは、Hadoopの使用方法を超えた、かなり珍しいソリューションです。 結局のところ、これは大量のデータを処理するためのプラットフォームであり、データがすでに利用可能であることを前提としています。 しかし、ここではこのタスクは何も計算も処理もしませんが、逆にダウンロードします。



一方では、このソリューションはそのシンプルさに魅了されます。 結局のところ、スパイダーは、ポンピングのために1つのサイトのすべてのアドレスを取得し、それらを次々に移動する必要があり、スパイダー自体も複数のサーバーで分散して実行する必要があります。 そこで、サイトのアドレスの区切りの形式でマッパーを作成し、レデューサーの形式で個々のポンピングプロセスを実装します。



一方、これはかなり大胆な決定です。サイトを送り出すのが難しいためです。すべてのサイトが保証時間の責任を負うわけではなく、クラスターのコンピューティングリソースは他の誰かのWebサーバーからの応答を待つだけです。 さらに、十分に多数のポンピングアドレスが存在する場合、「遅い」サイトの問題が常に存在します。 20％の時間で、スパイダーは高速Webサイトから文書の80％を汲み上げ、次に低速Webサイトをダウンロードしようと80％の時間を費やします-そして、それらを完全に汲み上げることはほとんど不可能です。



このような解決策をしばらく分析し、その結果、それを放棄しました。 おそらく私たちにとって、このクモのアーキテクチャは一種の「否定的な例」として興味深いものでした。



検索エンジンの構造、検索エンジンの構築方法についての詳細は、次の投稿で説明します。