June 23, 2004

オンラインゲーム業界を支える技術−Googleの掌中に?(その3)

今回はGoogle側の技術について整理しましょう。

IEEE MARCH-APRIL 2003に掲載された論文「WEB SEARCH FOR A PLANET:THE GOOGLE CLUSTER ARCHITECTURE」を引用します。

When a user enters a query to Google (such as www.google.com/search?q=ieee+society), the user’s browser first performs a domain name system (DNS) lookup to map www.google.com to a particular IP address. To provide sufficient capacity to handle query traffic, our service consists of multiple clusters distributed worldwide. Each cluster has around a few thousand machines, and the geographically distributed setup protects us against catastrophic data center failures (like those arising from earthquakes and large-scale power failures). A DNS-based load-balancing system selects a cluster by accounting for the user’s geographic proximity to each physical cluster. The load-balancing system minimizes round-trip time for the user’s request, while also considering the available capacity at the various clusters.

ロードバランサーによって世界中に配置されたWebサーバーの塊(何と2、3000台単位)が選択されその中の1台のサーバーが、以降の検索プロセスをコントロールします。

The search process is challenging because of the large amount of data: The raw documents comprise several tens of terabytes of uncompressed data, and the inverted index resulting from this raw data is itself many terabytes of data. Fortunately, the search is highly parallelizable by dividing the index into pieces(index shards), each having a randomly chosen subset of documents from the full index. A pool of machines serves requests for each shard, and the overall index cluster contains one pool for each shard. Each request chooses a machine within a pool using an intermediate load balancer-in other words, each query goes to one machine (or a subset of machines) assigned to each shard. If a shard's replica goes down, the load balancer will avoid using it for queries, and other components of our cluster-management system will try to revive it or eventually replace it with another machine. During the downtime, the system capacity is reduced in proportion to the total fraction of capacity that this machine represented. However, service remains uninterrupted, and all parts of the index remain available.

シャードと言われる細分化したインデックスが格納されているマシンと、シャード毎に配置されている、プールと呼ぶ検索実行用の複数のマシンがあります。Webサーバーからのクエリーが入ると、クエリーの内容によって選択されるシャードに対応するプールマシンの1台が、ロードバランサーで自動的に割り当てられ、シャードマシンに対して検索を実行します。

この仕掛けは、通常のインターネットの仕掛けで言えば、シャードマシンがデータベースサーバーに相当し、プールマシンがアプリケーションサーバーに該当します。しかも、通常の仕掛けであればデータベースサーバーやアプリケーションサーバーは多くても数台のマシンで運用されるものが、Googleではインデックス自体が千台単位のマシンに分割され、アプリケーションに至ってはその何倍ものマシンで実行されるという、壮大なスケールを実現しています。

ここで考える必要があるのは、果たしてこのGoogleの仕掛けと言うのは検索と言う「特殊」用途にしか適用できないものなのかどうかです。以下次回です。 KAI

投稿者 : June 23, 2004 10:38 PM | トラックバック