大規模なデータベースへのクエリは、無視できる遅延でどのように戻りますか？

Question

たとえば、Googleで何かを検索する場合、結果は近づいています。

Googleはアルゴリズムなどでページを並べ替えてインデックスを付けていることを理解していますが、可能なすべてのクエリの結果がインデックス化されることは不可能だと思います（そして、結果はパーソナライズされており、これによりこれをさらに実行不可能にします）？

さらに、Googleのハードウェアのハードウェア遅延は巨大ではないでしょうか？ GoogleのデータがすべてTB/S SSDに保存されていたとしても、処理するデータが膨大な量を考えると、ハードウェアのレイテンシが巨大であると思います。

MapReduceはこの問題を解決するのに役立ちますか？

編集：わかりました、だから私は人気のある検索がメモリでキャッシュされる可能性があることを理解しています。しかし、不人気な検索はどうですか？私が行った最もあいまいな検索でさえ、検索が5秒以上大きいと報告されたことはないと思います。これはどのように可能ですか？

Answer 1

まあ、問題を解決するのがMapReduceであるかどうかはわかりませんが、あなたが提起したこれらすべての質問を解決するために単独でMapReduceではありません。しかし、ここに考慮すべき重要なことがあり、それはそれを作る 実行可能 さまざまなマシン内のこれらすべてのデータからのクエリにこのような低遅延を持つこと：

1. 分散コンピューティング：配布されることにより、インデックスが単純に異なるマシンに配布されることを意味するのではなく、実際に異なるクラスターに沿って複製されているため、多くのユーザーが検索時間が少ないさまざまなクエリを実行できるようになります（はい、巨大な企業はそれほど多くの余裕があります。機械の）;
2. キャッシュ：キャッシュは、クロールステップの場合、ページの取得、または結果のランキングと除外など、実行時間を大幅に短縮します。
3. 多くの調整：上記のすべておよび非常に効率的なアルゴリズム/ソリューションは、実装も効率的である場合にのみ効果的です。参照の局所性、圧縮、キャッシュなど、大量の（ハードコード化された）最適化があります。それらはすべて、通常、処理のさまざまな部分に適用可能です。

それを考慮して、あなたの質問に対処してみましょう。

しかし、可能なすべてのクエリの結果がインデックス化されることは実行不可能だと思います

はい、それはそうであり、実際には結果を得ることができません すべての可能なクエリ. 。世界には無限の用語があります（適切に綴られた項のみが入力されると仮定しても）。 n -> inf 条項 （2^n）。では、何が行われていますか？キャッシング。しかし、非常に多くのクエリ/結果がある場合、どのクエリをキャッシュするものですか？キャッシュポリシー。最も頻繁に/人気/人気のあるユーザーに関連するクエリは、キャッシュされたものです。

Googleのハードウェアのハードウェア遅延は巨大ではないでしょうか？ GoogleのデータがすべてTB/S SSDに保存されていても

今日、このような高度に開発されたプロセッサを備えた人々は、1秒以内（またはそれ以下）で終了する必要があり、非常に多くのデータを扱う可能性のあるあらゆるタスクを、複数のコアと多くのメモリを備えた非常に強力なプロセッサによって処理する必要があると考える傾向があります。しかし、一つのこと 裁定 市場はお金であり、投資家はそれを無駄にすることに興味がありません。では、何が行われていますか？

実際には、それぞれが単純/アクセス可能な（コストの面で）プロセッサを使用して多くのマシンを使用しているため、多くのクラスターを構築する価格が低くなります。そして、はい、それは機能します。メインのボトルネックは、の簡単な測定を検討する場合、常にディスクに要約されます パフォーマンス. 。しかし、非常に多くのマシンがあると、ハードディスクで作業するのではなく、メインメモリに物事をロードする余裕があります。

メモリカードはです 高価な 私たちにとって、単なる人間ですが、彼らはそのようなカードを一度に購入する企業にとって非常に安価です。費用がかからないため、インデックスをロードしてキャッシュを手元に置いておくために必要に応じて多くのメモリを持つことは問題ではありません。また、非常に多くのマシンがあるため、さまざまな場所にクエリを向けることができ、参加を担当する機械のクラスターがあるため、超高速プロセッサは必要ありません。 特定の地理的地域, 、それをもっと可能にします 専門 データキャッシュ、さらには応答時間が改善されます。

MapReduceはこの問題を解決するのに役立ちますか？

MapReduceを使用するかどうかはGoogle内の制限されている情報が制限されているとは思わないが、この点については精通しているわけではない。ただし、GoogleのMapReduceの実装（確かに いいえ Hadoop）は、上記の側面を含む多くの最適化が必要です。したがって、MapReduceのアーキテクチャは、おそらく計算がどのように物理的に分布するかをガイドするのに役立ちますが、クエリ時間でそのような速度を正当化するために考慮すべき他の多くのポイントがあります。

さて、人気のある検索がメモリにキャッシュされる可能性があることを理解しています。しかし、不人気な検索はどうですか？

以下のグラフは、方法の曲線を示しています 種類 クエリの発生。検索には3つの主要な種類があり、それぞれがクエリの量の約1/3を保持していることがわかります（曲線下の面積）。プロットは電力法則を示しており、より小さなクエリが最も人気があるという事実を強化します。クエリの2番目の3分の1は、単語がほとんどないため、処理することができます。しかし、いわゆるセット 不明瞭なクエリ, 、通常、経験のないユーザーのクエリで構成されており、クエリのごくわずかな部分ではありません。

そして、新しいソリューションのためのスペースがあります。それは1つまたは2つのクエリ（しかしその3分の1）だけではないので、彼らは持っている必要があります 関連する 結果。何かを入力する場合 あまりにもあいまいです Google検索では、結果のリストを返すのに時間がかかりませんが、おそらく何かを見せます 推測 言いたいです。または、そのような用語の文書がなかったことを単に述べることも、検索を32語に削減することさえあります（ここではランダムなテストで私に起こっただけです）。

いくつかの単語を無視するか、クエリをより小さなものに分割して、最も集めることを試みるために、適用可能なヒューリスティックが多数あります。 人気 結果。そして、これらすべてのソリューションは、尊敬するために調整および調整することができます 実行可能な待機時間 たとえば、秒よりも少ない？ ：d

Answer 2

MapReduceは、リアルタイムとは何の関係もありません。これは、ETLやインデックスビルディングなど、一部のオフラインタスクに適したバッチ指向の処理フレームワークです。 Googleは現在、ほとんどの仕事でMapReduceから移動しており、Hadoopエコシステムでさえも同じことをしています。

低遅延に対する答えは、一般に、事前計算されたインデックスをメモリに保つことです。ディスクに触れるものはすべて、高速でスケーリングするのが難しいです。これは、新しい生成のHadoopベースのSQLエンジンが好きです インパラ MapReduceベースのインフラストラクチャのような速度を獲得します ハイブ, 、 例えば。

検索インフラストラクチャは、すべてのクエリの結果をキャッシュできません。しかし、それは確かに中間結果をキャッシュすること、または上位クエリのより完全な結果をキャッシュすることができます。少しキャッシングを使用すると、すべてのクエリのかなりの少数派の結果を提供できます。

検索もサーバー間で分割されます。そのため、1つのマシンが100に委任して結果の一部を取得し、それらを結合できます。

ある程度の近似で逃げることもできます。 Googleは文字通り1000ページの検索結果を形成しません。最初のページを正しく取得する必要があります。

Googleが持っていることに留意してください 数百万 世界中のコンピューターの。あなたのクエリはあなたの近くに地理的にデータセンターに行きます、そしてそれはあなたの地理にのみ提供しています。これにより、データセンターの処理時間ではなく、ネットワークであるレイテンシの大部分が削減されます。

Answer 3

MapReduceは検索には使用されません。インデックスを構築するためにずっと前に使用されていました。しかし、それはバッチ処理フレームワークであり、ほとんどのWebが常に変更されていないため、新しいアーキテクチャはすべてです 増分 バッチ指向の代わりに。

Googleでの検索は、多くの細かい調整と最適化を除いて、LuceneとElastic Searchで機能するのと同じように機能します。しかし、まさに心から、彼らは何らかの形を使用します 反転インデックス. 。言い換えれば、彼らはそうします いいえ 検索クエリを入力するときに（キャッシュされていない場合でも）いくつかのテラバイトを検索します。彼らはおそらく実際の文書をまったく見ないでしょう。しかし、彼らはあなたのクエリ用語と一致するドキュメントをリストするルックアップテーブルを使用します（ステム、スペルミス、同義語などがすべて前処理されます）。彼らはおそらくそれを取得します リスト 各単語のトップ10000ドキュメント（10k整数 - ほんの数kb！）のドキュメントのうち、それから最高の一致を計算します。これらのリストに良好な一致がない場合にのみ、それらは次のそのようなブロックなどに拡大します。

一般的な単語のクエリは簡単にキャッシュできます。また、プリプロセシングを介して、上位10Kの結果のリストを作成し、ユーザープロファイルに従って再表示することができます。 「正確な」答えを計算することによって得られるものは何もありません。上位10Kの結果を見るだけで十分です。正解はありません。そして、位置10001のどこかでより良い結果が見逃された場合、誰も知らないか、気付かないでしょう（または気にします）。それはおそらくプリプロセシングでランク付けされており、最後にユーザーに提示されるトップ10にそれを作成しなかったでしょう（またはトップ3で、ユーザーは実際に見ます）

一方、まれな用語もそれほど課題ではありません。リストの1つには、いくつかの一致するドキュメントのみが含まれており、すぐに他のすべてのドキュメントを破棄できます。

この記事を読むことをお勧めします：

大規模なハイパーテキストWeb検索エンジンの解剖学
セルゲイ・ブリンとローレンスのページ
カリフォルニア州スタンフォード、スタンフォード大学のコンピューターサイエンス部門94305
http://infolab.stanford.edu/~backrub/google.html

そして、はい、それはこれを書いたGoogleの創設者です。最新の状態ではありませんが、すでにかなり大規模に機能します。