“Few Web services require as much computation per request as search engines. On average, a single query on Google reads hundreds of megabytes of data and consumes tens of billions of CPU cycles. Supporting a peak request stream of thousands of queries per second requires an infrastructure comparable in size to that of the largest supercomputer installations.” So begins the description of the computational power required for Google's Web search engine in “Web Search For A Planet: The Google Cluster Architecture”, a publication of the IEEE Computer Society.

Though we most often associate high performance computing with high-end mathematical applications such as climate modeling, fusion reaction simulations or quantum chromodynamics, one of the most common forms of data intensive computing is Web searching. It is used by millions of people worldwide on a daily basis. Today, Web searching is so ubiquitous that most of us now take it for granted that we can find the answer to just about anything on the Internet. But for the average person, it's hard to imagine the computational resources required to search and analyze petabytes of data millions of times per day.

So what is the nature of Google's computing infrastructure? How is it able to process thousands of queries per second from all over the world? And how will its infrastructure scale as the Web continues to grow? HPCwire recently spoke with Jeffrey Dean, Google Fellow in the Systems Infrastructure Group, to get the answers to these and other questions.

HPCwire: Tell us a little bit about your background and why you came to Google.

Dean: I received a B.S. in computer science and economics from the University of Minnesota. I then worked for a year and a half for the World Health Organization's Global Programme on AIDS, developing software for modeling the impact of the AIDS pandemic, before going to grad school. I received a Ph.D. in computer science from the University of Washington, doing research in high-level compiler optimizations for object-oriented languages. After graduating, I went to work for Digital Equipment Corporation's Western Research Lab (DEC WRL), where I worked on a variety of projects, including low-overhead profiling systems, some microprocessor architecture work, and some work on web-based information retrieval.

I joined Google in mid-1999 because my work at DEC WRL on information retrieval whet my appetite for working in that area. I knew a couple of people at Google, and figured it would be a fun place to work. I've always enjoyed working on problems that span a pretty wide range of computer science disciplines, and working on large-scale search engines is one of the best ways of doing that, because it requires solving problems across a really broad range of topics, including low-level system design, distributed systems, data compression, information retrieval, machine learning, user interfaces, with lots of general algorithmic problems thrown in at every turn.

HPCwire: Could you briefly describe the Google computing infrastructure and its rationale?

Dean: When designing our computing clusters, we place a great deal of emphasis on what sort of systems will give us the best price/performance. Search applications are relatively easy to parallelize, both within processing of a single query (by partitioning the index across machines), and across queries (by replicating each piece of the index across multiple machines and having each replica serve a fraction of the total traffic). Given this easy parallelism, the price/performance argument leads towards using clusters of large numbers of commodity PCs, that is, x86 processors, inexpensive hard drives, commodity Ethernet networking, etc.

Our clusters typically are composed of several thousands of these commodity machines, all connected via commodity Ethernet. The individual machines typically have gigabit NICs, and groups of around 40 machines are connected to commodity gigabit Ethernet switches. These switches are then connected into a large-scale core switch for the cluster, using a small number of Gigabit connections per group of 40 machines. So, our bisection bandwidth is considerably less than a gigabit per machine. More bandwidth would be great, but it's obviously considerably more expensive, and our current configuration is the current sweet spot given our applications.

We don't disclose the exact number of clusters that we have, but we do have many of them around the world at various locations. There are a couple of reasons for this. First, we can given our users faster response times by using software that tries to direct user queries towards a cluster that is located nearby to that user in terms of network latency. Second, it makes our search service considerably more robust. We try to have a bit of extra capacity at all times, so that we can turn off clusters at various points, either for planned events like hardware or network upgrades, or because we need to quickly turn off serving from a particular cluster — for example if one of the core network switches fails.

Having lots of relatively small machines means that you get a lot more bang for the computing dollar, but it also means that the machines are less reliable than more expensive machines, and because there are so many of them, higher-level software has to be designed to tolerate failures — with thousands of machines, machine failures happen many times per day. Our software is designed to assume that the hardware can fail.  Once you do that, it becomes fairly simple to deal with a lot of failures. Our serving systems generally have multiple replicas for each piece of the system to provide fault tolerance to individual machine failures.

We've also designed our own file system, the Google File System (GFS), to reliably store large amounts of data on large clusters of machines. [For information on GFS visit http://labs.google.com/papers/gfs.html.]

Finally, when you're doing large-scale data processing, it's important not to separate the storage from where you're going to do the computation. You don't need really high-end storage arrays with massive amounts of bandwidth to process a large amount of data. If you do the scheduling right, you can read the data from local disks on thousands of machines, simultaneously. By doing this, you can attain really good bandwidth from low-end storage systems with slightly clever software.  So rather than moving the data to the machine, we try to move the computation to the data.

HPCwire: What kinds of new infrastructure is Google looking at, in the near-term, to improve its price/performance?

Dean: Given the fact that our applications can be easily parallelized, chip multiprocessors (CMPs) look very attractive to us, compared with processors that go to great lengths to extract the highest single-thread performance possible.

My colleague, Luiz Barroso, has written up a nice article describing why CMP processors look very attractive for our applications [see http://labs.google.com/papers/priceofperformance.html].

As always, we're continually evaluating and refining our hardware infrastructure to explore which solutions provide the most attractive price/performance for our applications, but we are excited about the initial CMP processors coming out, as we feel their emphasis on high throughput for parallel applications rather than single-thread performance is a good match for our applications.

HPCwire: Could you describe the MapReduce model and implementation and how it is being used within Google?

Dean: MapReduce is a system originally developed by myself and my colleague, Sanjay Ghemawat, as a way of describing computations that want to process input data to compute some derived data. The general programming model is to break the computation down into two distinct phases: a Map phase, and a Reduce phase. Users specify a Map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a Reduce function that merges all intermediate values associated with the same intermediate key. The basic idea is similar to the Map and Reduce primitives found in LISP and many other functional languages.

What makes it interesting is that we've developed a MapReduce library that is able to take programs written in this style and make them run on clusters of hundreds or thousands of machines. The underlying library takes care of lots of the messy details that arise when running very large-scale parallel computations, including automatically parallelizing the computation, deciding which machines should work on which pieces (including biasing those scheduling decisions to consider data locality), and handling what happens when machines fail (with long-running jobs that execute on thousands of machines, machines failures happen with some regularity). It also does things like scheduling multiple copies of the same pieces of work towards the end of the computation, to minimize the job completion time (whichever copy finishes first “wins”), and collects progress information on a centralized status page to make it easy to monitor a MapReduce computation.

We've been pleasantly surprised at how applicable the general MapReduce model has been to a wide variety of problems: it's being used internally at Google in areas as diverse as our core crawling and indexing system, data mining, statistical machine translation, our advertising systems, processing of satellite imagery, etc. It makes it relatively easy for people within Google to write relatively simple code and have that code run reasonably efficiently on thousands of machines. In a typical day at Google, thousands of different MapReduce computations are run with hundreds of distinct Map and Reduce functions across our various computational clusters.

HPCwire: Is MapReduce something you would make publicly available?

Dean: We don't currently make it available. We've had thoughts about it. It would be a moderate amount of effort on our part to divorce it from other pieces of our software, such as our cluster scheduling system. Also, we put a fair amount of effort into it and it's not clear that we would want to make it available to our competitors. At the same time, we feel like there are a lot of academic projects that would benefit from having access to something like this. So, in the future, I wouldn't be surprised if we did make it available in some form. [For more information about MapReduce visit http://labs.google.com/papers/mapreduce.html.]

HPCwire: As the capacity of the Web grows, how is the Google infrastructure going to change? Is the current model scalable for the foreseeable future? And besides Web growth, what other kinds of changes do you foresee that will create infrastructure challenges for Google?

Dean: Our software infrastructure undergoes fairly rapid evolution in response to changes in the underlying hardware platform and also our desire to scale our system in a variety of dimensions. For example, for Web search, the major dimensions are the number of documents searched, the number of user queries we need to handle, and the speed with which the index is updated. We're also usually looking to introduce new capabilities in our infrastructure, for example, the ability to examine more information about documents when making ranking decisions, the ability to quickly try out new ideas for improving our ranking algorithms, etc. In designing a system, one tries to anticipate scaling in these various dimensions, but a given design really works well only when the design parameters are within one or two orders of magnitude of the original design goals. Beyond that, the level of scaling can change the design; solutions that weren't feasible originally suddenly become very attractive, and this often leads to significant redesigns of pieces of the system. As a consequence of this, in the six and a half years that I've been at Google, our query serving [software] infrastructure has undergone fairly radical changes at least five times. I expect this to continue to be true in the future.

In terms of general infrastructure, we place quite a bit of emphasis on developing tools and infrastructure to make it easier to develop new and interesting products. GFS and MapReduce are a couple of examples. We also have a number of internal tools that help with understanding performance bottlenecks in large-scale distributed systems.

Many of our newer products, like Gmail and Google Earth, have fairly different characteristics than Web searching, and it's important to have infrastructure and system building blocks that meet the needs of a diverse set of products that we want to offer, and to make it easy to develop new applications and services. One example is that we saw a need in many of our products to manage large amounts of semi-structured mutable data in interesting ways, and to help with that, we're developing BigTable, a large-scale distributed storage system for managing semi-structured data.

In the future, a combination of both new products and our goals for pushing our current products in new and interesting directions will guide our decisions about the right software tools and infrastructure to build. These are very exciting times to be working on large-scale systems and products at Google.