webdevqa.jp.net

どうしてGoogleはこんなに高速なのでしょうか?

Googleが非常に高速にクエリを処理できるようにする技術とプログラミングの決定は何ですか?

何かを検索するたびに(1日に数回のいずれか)、1秒近くまたは1秒未満で結果を提供する方法に常に驚かされます。これを実現するために、どのような構成とアルゴリズムを導入できますか?

サイドノート:デスクトップアプリケーションを置いて、それを自分のマシンで使用したとしても、おそらく半分の速度ではないだろうというのは、圧倒的な考えです。 Googleとして。私が言う学習を続けてください。


以下に、提供される優れた回答とポインタをいくつか示します。

89
Jorge Ferreira

以下に、提供される優れた回答とポインタをいくつか示します。

5
Jorge Ferreira

レイテンシはディスクアクセスによって殺されます。したがって、クエリに応答するために使用されるすべてのデータはメモリに保持されると考えるのが妥当です。これは、それぞれが多くの断片の1つを複製する数千のサーバーを意味します。そのため、検索のクリティカルパスが、GFS、MapReduce、BigTableの主要な分散システムテクノロジーにヒットする可能性はほとんどありません。これらは、クローラーの結果を大まかに処理するために使用されます。

検索の便利な点は、強力な一貫性のある結果や完全に最新のデータを取得する必要がないことです。したがって、より最新の検索結果が利用可能になったため、Googleはクエリへの応答を妨げられません。

したがって、可能なアーキテクチャは非常に単純です:フロントエンドサーバーはクエリを処理し、それを正規化して(ストップワードを削除するなど)、クエリスペースのその部分を所有するレプリカのサブセットに配布します(代替アーキテクチャはWebページごとにデータを収集するため、クエリごとにすべてのレプリカセットの1つにアクセスする必要があります)。多くの場合、多くのレプリカが照会され、最も速い応答が勝ちます。各レプリカには、ドキュメントへのクエリ(または個々のクエリ用語)をマッピングするインデックスがあり、それらを使用して、メモリ内の結果を非常にすばやく検索できます。さまざまなソースからさまざまな結果が返される場合、フロントエンドサーバーはhtmlを吐き出すときにそれらをランク付けできます。

これはおそらくGoogleが実際に行うこととはかなり長い違いがあることに注意してください-彼らはこのシステムの寿命を設計しているので、他の可能な違いの中で奇妙な領域、奇妙なインデックス、ある種のファンキーな負荷分散スキームでより多くのキャッシュがあるかもしれません。

47
HenryR

1つの答えに入れるのは少し多すぎます。 http://en.wikipedia.org/wiki/Google_platform

26
Vasil

面白いと思うのは、Googleが実際にバイオインフォマティクスによって運営されているということです(私はバイオインフ...説明させてください。

バイオインフォマティクスは、初期から巨大な文字列の小さなテキストを非常に高速に検索するという課題に直面していました。私たちにとって、「巨大な紐」はもちろんDNAです。多くの場合、単一のDNAではなく、異なる種/個体からの複数のDNAのデータベースです。小さなテキストはタンパク質またはそれらの遺伝的対応物である遺伝子です。計算生物学者の最初の仕事のほとんどは、遺伝子間の相同性を見つけるために制限されていました。これは、すでに知られている遺伝子との類似点に注目することにより、新しく発見された遺伝子の機能を確立するために行われます。

さて、これらのDNA文字列は実際に非常に大きくなり、(損失!)検索は非常に効率的に行われなければなりません。したがって、文字列検索の現代の理論のほとんどは、計算生物学の文脈で開発されました。

しかし、かなり前に、従来のテキスト検索は使い果たされました。準線形時間で、つまり各文字を見ることなく、大きな文字列を検索できる新しいアプローチが必要でした。これは、大きな文字列を前処理し、その上に特別なインデックスデータ構造を構築することで解決できることが発見されました。多くの異なるそのようなデータ構造が提案されています。それぞれに長所と短所がありますが、特に注目に値するものがあります。これは、一定の時間で検索できるためです。現在、Googleが運用している規模では、サーバー、前処理、およびその他の洗練されたものの間の負荷分散を考慮する必要があるため、これはもはや厳密ではありません。

しかし、本質的には、いわゆるq-gramインデックスにより、一定時間での検索が可能になります。唯一の欠点は、データ構造が途方もなく大きくなることです。基本的に、最大q文字(したがって名前)の文字列の検索を可能にするには、可能な組み合わせごとに1つのフィールドを持つテーブルが必要です。 q文字(つまり、q[〜#〜] s [〜#〜]、ここで[〜#〜] s [〜#〜]はアルファベットのサイズ、たとえば36(= 26 + 10))です。さらに、インデックスが作成された文字列の各文字位置(またはgoogleの場合は各Webサイト)ごとに1つのフィールドが必要です。

膨大なサイズを軽減するために、Googleはおそらく複数のインデックスを使用します(実際、スペル訂正のようなサービスを提供するために、それらはdoです)。最上位のものは文字レベルでは機能せず、代わりにWordレベルで機能します。これはqを減らしますが、[〜#〜] s [〜#〜]無限に大きいため、ハッシュテーブルとコリジョンテーブルを使用して、無数の異なる単語に対処する必要があります。

次のレベルでは、これらのハッシュされた単語は他のインデックスデータ構造を指し、それがWebサイトを指す文字をハッシュします。

要するに、これらのq-gramインデックスデータ構造は、おそらくGoogleの検索アルゴリズムの最も中心的な部分です。残念ながら、q-gramインデックスの仕組みを説明する非技術的な論文はありません。私が知っている唯一の出版物は、そのようなインデックスがどのように機能するかについての説明を含んでいます...悲しいかな、私の 学士論文 です。

22
Konrad Rudolph

彼らは、膨大な量のハードウェアで実行される、優れた分散アルゴリズムを実装しています。

4
Anders Sandvig

最も重要な遅延の1つは、WebサーバーがクエリをWebサーバーに送信し、応答を返すことです。この遅延は、Googleでさえ従わなければならない光の速度によって制限されます。ただし、世界中にデータセンターがあります。その結果、いずれか1つまでの平均距離が短くなります。これにより、遅延が抑えられます。確かに、差はミリ秒単位で測定されますが、応答が1000ミリ秒以内に到達する必要がある場合は重要です。

4
MSalters

ハトを使用する であるため、誰もがそれを知っています!

そうそう、それとMapreduce。

4
HanClinto

彼らはほとんどカスタムファイルシステム上の何千ものPCにキャッシュされたインターネットのローカルコピーを持っています。

3
Richard Walton

Googleは最高の人材を採用しています。 ITの最も優秀な人々の一部はGoogleで働いています。彼らは、ハードウェアとエンジニアに投げかける実質的に無限のお金を持っています。

彼らは実行するタスクのために高度に最適化されたストレージメカニズムを使用します。

地理的に位置するサーバーファームがあります。

3
Matthew Watson

一般化されたリストでの試み(Googleの内部ツールにアクセスできるかどうかに依存しません):

  1. Parellelizeリクエスト(たとえば、単一のリクエストをより小さなセットに分割する)
  2. 非同期(可能な限り非同期にします。たとえば、ユーザーの要求をブロックしません)
  3. メモリ/cache(ディスクI/Oが遅い、可能な限りメモリに保持する)
  4. 事前計算(可能な限り多くの作業を事前に行い、ユーザーがデータ/処理を要求するのを待たない)
  5. フロントエンドHTMLに注意(Yslowと仲間たちを参照)
3
Jilles

グーグル研究ホームページ で見つけることができます。グーグルの男たちによって書かれた研究論文に関するいくつかのポインタ。 googleファイルシステムmap/reduceアルゴリズム の説明から始めて、Googleページの背後で何が起こっているのかを理解してください。

2
Nicolas

このリンクは非常に有益です Googleクエリの舞台裏

2
user20804

ハードウェア。

たくさんのハードウェア。彼らは、コモディティPCの大規模なクラスターをサーバーファームとして使用しています。

1
TraumaPony

TraumaPonyは正しい。負荷分散/キャッシュのための大量のサーバーとスマートアーキテクチャ、および1秒未満でクエリを実行できます。 Googleサービスのアーキテクチャを説明する記事がネット上にたくさんありました。 Googleで見つけられると思います:)

1
aku

HenryRはおそらく正しいでしょう。

Map Reduceは検索自体の役割を果たしませんが、インデックス作成にのみ使用されます。 Map Reduceの発明者とのこのビデオインタビュー を確認してください。

1
kohlerm

追加の理由は、彼らがTCPスロースタートアルゴリズムをごまかすことです。

http://blog.benstrong.com/2010/11/google-and-Microsoft-cheat-on-slow.html

1
Thomas Langston

そして、 アルゴリズム は、そのハードウェアのパワーを活用できます。 mapreduce など。

0
Vinko Vrsalovic

Googleクラスターの仕組みについて詳しく知りたい場合は、 [〜#〜] hdfs [〜#〜] のこのオープンソース実装をお勧めします。

Googleによる Mapreduce に基づいています。

0
yann.kmm
  1. 多段階のデータ保存、処理、検索

  2. 上記のタスクの効率的な配布(数千台のマシンのうち数百台)

  3. 生データと処理結果を保存するための優れたフレームワーク

  4. 結果を取得するための優れたフレームワーク

これらすべてがどのように行われるかは、質問の要約にあるすべてのリンクによって要約されます。

0
computinglife