Googleを支える技術 -- 巨大システムの内側の世界 ([著]西田圭介, [版]技術評論社) #2

「第1章 Googleの誕生」を読んだ。

まず、Googleの出発点として「良い検索結果」＝「役に立つ検索結果」だと捉え直したことがある。これを実現するための概念がWebページのランク付けであり、ランク付けのために(有名な)PageRankを始めとするアルゴリズムが考え出され、そして実装された。ページのランク付けは、Googleの誕生当時(1990年代後半)はもちろん、今なおホットで難しい問題であり、現在でもGoogleの技術的探求の中心でもある。

1.4がインデックス化、1.5が事前に作成されたインデックスを使った検索そのものの仕組みの解説。1.3で解説されるクローリング(Webページを集めること)とともに、1.4は事前作業だから比較的時間をかけても良い。一方で、1.5の検索はユーザが検索語を入力してから、その結果が表示されるまでの短い時間(たいていは数秒)で行われなければならないことだ。それにもかかわらず、ここにはページのランク付けという困難がふくまれている。ここでの困難はランク付けの適切なアルゴリズムを考えることが難しいということではなく、膨大なWebページの情報(インデックス化で事前に作成されている)に対してランク付けアルゴリズムを適用し、その結果で並べ替えて、ユーザに検索結果として送り返す。それをごく短い時間でやらなければならない、という「スケール」に対する困難さだ。

実際、初期のGoogleではページのランク付けに関しては、一部のページのみが対象であったと書かれている(p.36)。

2008-03-30(23:39)時点で、本書の書名「"Googleを支える技術"」(書名をダブルクォーテーションで囲ってある)で検索したところ「約16,100件」という検索結果をGoogleは返してきた。時間は0.26秒だそうだ。「Googleを支える技術」としてダブルクォーテーションを取ると、「約236,000件」になり、これには0.40秒かかったとある。数十万という単位のデータに対して複雑な計算を実行し、結果をソートする。そこからさらにテキストの取り出し、結合、HTML化とやること時間のかかることはまだまだ多い。それをこの短い時間でやってのけるための仕組みがちょっと思い浮かばない。少なくとも第1章で解説されている方法を何の工夫もないまま素直に実装したら、このパフォーマンスは得られない。まあ、テキスト処理は実際に「検索結果ページ」を作るのに必要な件数(デフォルトは10件だっけ?)だけなんだが。それにしてもランク付けの計算は全部でやってるだろうしね。

その当たりの工夫が「第2章 Googleの大規模化」以降で解明されるらしい。