Papers
Web Search for a Planet: The Google Cluster Architecture
Luiz André Barroso, Jeffrey Dean, Urs Hölzle · IEEE Micro, vol. 23, no. 2 (March-April 2003), 2003
The problem: web search consumes too much compute per request
Few web services require as much computation per request as a search engine. According to the authors, on average a single Google query reads hundreds of megabytes of data and consumes tens of billions of CPU cycles. Sustaining a peak of thousands of queries per second therefore calls for an infrastructure comparable in size to the largest supercomputing installations. The paper's answer is a cluster of more than 15,000 commodity-class PCs running fault-tolerant software. The central thesis is that this combination delivers superior performance for a fraction of the cost of a system built with fewer, but more expensive, high-end servers. The authors highlight two factors that guide the whole design: energy efficiency and price/performance. Energy matters because, at Google's scale, power consumption and cooling become significant operational factors and push against the power-density limits of the available data centers. The paper also notes that the application lends itself well to parallelization: different queries can run on different processors and, because the index is partitioned, a single query can also use multiple processors. For that reason, the peak performance of each processor matters less than its price/performance.
Serving a query: DNS, GWS, index servers, and document servers
The article walks through the path of a query. The browser first resolves the name via DNS. The service is made up of several clusters spread around the world, each with a few thousand machines, which protects against catastrophic failures of a data center, such as earthquakes or large-scale power outages. DNS-based load balancing picks the cluster taking into account the user's geographic proximity and the capacity available at each location, minimizing round-trip time. Once the cluster is chosen, all processing of the query is local to it. A hardware load balancer monitors the set of Google Web Servers (GWS) and distributes requests among them. The GWS that receives the query coordinates execution and assembles the HTML response. Execution has two phases. In the first, the index servers look up an inverted index, which maps each query word to a list of documents containing it (the hit list). They intersect the lists for the words and compute a relevance score per document, which defines the order of the results. The output of this phase is an ordered list of document identifiers (docids). In the second phase, the document servers (docservers) take the docids and fetch each document from disk to extract the title, URL and a snippet with the keyword in context. In parallel, the GWS triggers auxiliary tasks, such as the spell checker and the ad server.
Index shards and replication: parallelism per query
The challenge of search is the volume of data. The authors indicate that the raw documents add up to several tens of terabytes uncompressed, and that the inverted index derived from them itself takes up many terabytes. The way out is to split the index into pieces called index shards, each containing a randomly chosen subset of the documents of the full index. For each shard there is a pool of machines that serves requests, and the index cluster contains one pool per shard. An intermediate load balancer picks a machine within each pool, so that each query goes to one machine (or a subset of them) of each shard. The same scheme holds for the document servers: documents randomly distributed across smaller shards, several replicas per shard, and routing by a load balancer. The design consequence is that adding machines to each pool increases serving capacity, while adding shards accommodates index growth. Since the shards do not need to communicate with each other, the speedup from parallelizing the search is nearly linear and the average query latency drops, because the total work is split among more CPUs and disks. For this reason the speed of an individual CPU does not directly affect overall performance: the number of shards can be increased to compensate for slower CPUs.
Software reliability and replication for capacity and fault tolerance
The authors argue that the best price/performance comes from building a reliable infrastructure out of unreliable commodity PCs, delivering reliability at the software level: replicating services across many machines and detecting and handling failures automatically. The paper summarizes four principles. First, reliability in software: give up fault-tolerant hardware features, such as redundant power supplies, cheap disk arrays (RAID) and high-quality components, and tolerate failures in software. Second, use replication for throughput and availability: since the service is already replicated to get capacity, this fault tolerance comes for free. Third, price/performance beats peak performance: you buy the CPU generation with the best performance per unit of price. Fourth, commodity PCs reduce the cost of computation, allowing more resources to be spent per query, more expensive ranking techniques to be used, or a larger index to be searched. In practice, if a shard's replica goes down, the load balancer avoids using it, and the cluster management system tries to revive or replace it. During the outage, capacity drops in proportion to the slice the machine represented, but the service keeps running without interruption and all parts of the index remain available. It also helps that most accesses are read-only, with infrequent updates done by steering queries away from the replica, which avoids many of the consistency problems of a general-purpose database.
Price/performance with commodity parts: the rack example
Google's racks hold 40 to 80 x86 servers mounted on both sides of a custom-built rack. The servers look like mid-range desktop PCs, except for the choice of large disks. Each server has one or more 80 GB IDE disks, and the paper cites a range of CPU generations in use, from a 533 MHz Celeron with one processor to a dual 1.4 GHz Pentium III. The final selection criterion is cost per query: capital expenses (with depreciation) plus operating costs, divided by performance. The paper argues that a server rarely lasts more than two or three years, so the cost of the equipment weighs heavily. To illustrate, it compares a rack of PCs costing about US$278,000 (176 2 GHz Xeon CPUs, 176 GB of RAM, and 7 TB of disk) with a typical multiprocessor server costing about US$758,000 (8 2 GHz Xeon CPUs, 64 GB of RAM, and 8 TB of disk). The multiprocessor costs about three times as much, with 22 times fewer CPUs and three times less RAM. The difference comes largely from the interconnect and the reliability of high-end machines, attributes that Google's redundant architecture does not depend on. Operating thousands of PCs brings administration and repair costs, but these are manageable because the application is quite homogeneous, with identical configurations, group installation tools, and batch repairs.
Power density, limits and legacy
The paper devotes a section to the power problem. A mid-range server with two 1.4 GHz Pentium IIIs draws about 90 W of direct current under load: approximately 55 W for the CPUs, 10 W for a disk, and 25 W for DRAM and the motherboard. With a typical power supply efficiency of about 75%, this becomes about 120 W of alternating current per server and approximately 10 kW per rack. A rack fits in about 25 square feet, which gives a density of about 400 W per square foot, and it can exceed 700 W/ft² with more powerful processors. Typical commercial data centers, however, sit between 70 and 150 W/ft², well below that. Thus, even clusters of simple PCs need special cooling or extra space, and packing even more servers per rack has limited practical use. Low-power servers are attractive, but what counts is watts per unit of performance, and they cannot cost much more: the authors estimate cooling and power at about US$1,500 per month per rack, versus US$7,700 of depreciation. In the end, they acknowledge limits of massive parallelism, such as the cooling capacity of commercial data centers and the imperfect fit of the CPUs of that era to throughput-oriented workloads. Even so, the model holds for other applications with servers that have no private state and request-level parallelism, such as high-volume web servers.
See the ideas at work
Practice the designs that use this paper in the System Design school.