Googleの検索システムとは

Googleの検索システムのスピードと信頼性は、データをチャンク（塊）として扱う方法に負っている。同社のトップエンジニアはそう説明している。

　Googleのオペレーションおよびエンジニアリング担当副社長ウルス・ヘルツル氏によれば、Googleは100億以上のWebページと同社サーバ上の10テラバイト以上の情報を処理するために、安価なマシンを組み合わせ、十分な冗長性を持たせて利用している。Googleアーキテクチャでは、1台当たり1000ドル程度の一般的なサーバを、相互に連結したノードとして配置している。

　すべてのマシンでは、必要最低限の機能だけを備えたLinuxカーネルを実行している。ディストリビューションはRed Hatのものだが、ヘルツル氏によれば、Googleはその機能の多くは使用しておらず、オリジナルのカーネルで用意されていない機能については自社で独自にパッチを作成している。

　「安価なマシンの欠点は、信頼性を確保しながら連係させなければならない点だ。こうしたマシンは安くて、連携させるのも簡単だ。問題は故障しやすい点だ」とヘルツル氏。

　実際、Googleでは毎日、多くのマシンが故障している。そこでGoogleはマシンの故障に対処する方法を自動化し、高速で信頼性の高いサービスを安価なハードウェアを用いて構築できるようにしている。

　Googleは、キャッシュするWebページを「shards」と呼ばれる断片に分割することで複製している。shardsのサイズは非常に小さいため、いくつかのshardsをまとめて1台のマシンに収められる。さらにshardsは複数のマシンで複製され、どれか1台のマシンが故障したとしても、別のマシンで同じ情報を提供できるようになっている。マスターインデックスも数台のサーバに分割され、数回に渡って複製される。エンジニアはこれを「チャンクサーバ」と呼んでいる。

　システムに検索クエリーが届くと、クエリーがWebサーバに到達し、有効なチャンクに分割される。ワンセットのインデックスサーバにはインデックスが含まれ、ワンセットのマシンにフルインデックスが1つ含まれる。実際にクエリーに返答するためには、完全なワンセットのサーバが必要となる。そうしたセットはフェイルセーフ措置として複製されているため、スループットも増す。1つのセットがビジー状態であれば、新しいクエリーを次のセットにルーティングできるからだ。これにより、マシン1台当たりの検索時間も短縮できる。

　同時に、文書サーバのクラスタにはGoogleがキャッシュしたWebページのコピーが含まれる。ヘルツル氏によれば、更新速度は1～7日、平均で2日だが、たいていはWebパブリッシャーのニーズ次第という。

　「これはわれわれが予想していなかった制限だが、実際のところ、われわれは望んでいるほど迅速にはクロールを行えない。小規模なWebマスターが苦情を言ってくるからだ」と同氏。

　文書サーバの各セットにはWebのコピーが1部づつ含まれ、そのページに含まれる関連テキストをユーザーに示すために、コンテンツの抜粋を提供する役割を果たしている。

　「例えば、上位10件の検索結果が文書サーバに送られ、文書サーバはその10の検索結果ページをメモリにロードする。そして、その内容が構文解析され、すべてのキーワードを含む最善の抜粋が見つけられる」とヘルツル氏。

　Googleは、クエリーのルーティング、サーバの負荷分散、およびプログラミングの簡略化のために、それぞれ社内で開発した3種類のソフトウェアシステムを使っている。

　そのうちの1つ、Google File Systemは故障しがちな安価なマシンに対処するために特別に書かれたものだ。

「われわれはファイルを集め、チャンクに分割して、それを複数のマシンにランダムに分配し、各チャンクのコピーが少なくとも2部できるようにする。そして、そうしたコピーは同じ電源系統やスイッチ上ではなく、物理的に隣接していない環境に置くようにする。そうすることで、1つのコピーが駄目になっても、必ず、もう1つのコピーがまだあるという状態を保てる」とヘルツル氏。通常、チャンクは64Mバイトで、複製は3回行われる。

　ヘルツル氏によれば、こうした複製のおかげで変更を加えるのも簡単になる。Googleはオフラインで一度に1つの複製を用い、それを更新してから再びマシンを接続させている。

　こうしたチャンクはシステム全体にランダムに分散されるため、チャンクがどこにあるかを追跡するためのメタデータを含むマスターが必要となる。クエリーがシステムに届くと、ファイルシステムマスターはどのチャンクサーバにそのデータがあるかを告げる。「そこからは、チャンクサーバと対話するだけでいい」とヘルツル氏。

　クライアントマシンにはフォールトトレランスも必要だ。クライアントが指定のチャンクサーバにファイルを要求し、指定された時間内に返答がない場合、クライアントはメタ情報を使って別のチャンクサーバを見つけるとともに、最初のチャンクサーバが故障している可能性があることをファイルマスターに知らせる。ファイルマスターはチャンクの故障を確認すると、そこにあったチャンクを別のサーバに複製し、その情報が少なくとも最低限の回数は必ず複製されるようにする。

　「こうすれば、脆弱になる時間が非常に短くなる」と同氏。

　Googleのエンジニアは2004年、プログラマーが1000台のマシンで同時に動作するアプリケーションを作成できるよう、Map/Reduce Frameworkを作成した。

　「Map/Reduce Frameworkは自動的かつ効率的な平行化と配布を提供する。フォールトトレランスを備え、I/Oスケジューリングを行い、データがどこにあるかを賢く処理できる」とヘルツル氏。

　プログラマーはmapとreduceという2つのシンプルな関数を用いて、key/valueペアの長いリストを作成する。そして、map関数がそのほかのkey/valueペアを生成する。「1つのペアを別のペアにマッピングするだけだ」と同氏。

　例えば、アプリケーションがあるホストのURLをカウントする必要がある場合、プログラマーはそのURLとコンテンツを、ホスト名と1で構成されるペアにマッピングする。「これで、異なる値を持つkey/valueペアの仲介セットが生成される」とヘルツル氏。

　次に、reduce関数により、同じキーを持つすべてのアウトプットを取り出し、それを組み合わせて1つのアウトプットを生成する。

　「Map/Reduceは大規模データ処理の簡易版だ。非常にシンプルな抽出で、ほとんど手間をかけずにこうした何テラバイトものデータに対して実行できるプログラムの作成を可能にしている」とヘルツル氏。

　3つ目の自家製アプリケーションは、スケジューリングのためのGlobal Work Queueだ。

　Global Work Queueは昔のバッチ処理のように機能し、クエリーをバッチジョブにスケジューリングして、それをマシンプールに配置する役割を果たす。その設定は、大量のデータを使ってランダムな計算を実行するために最適化されている。