WEB Search For A planet: The google cluster architecture May 12, 2009

Paper describes the issues involved in the large cluster systems and provides key insight that should be taken care while coming up with the solution for these systems. Google has adopted to take care the system reliability in the software rather than the in-built reliability of the servers. Google query serving architecture consists of index server, document servers, spell checker and ad server. Load balancers are used at different levels to achieve the high utilization of resources. Most of the quires are read only which avoids the issue of synchronization. Further tasks are parallelizing like table lookup and then results are merged to achieve final solution. Decision to use commodity components rather than using high-end solution is based on the several analyses of the application and system. Another important insight of the paper is in terms of taking the full advantage of the application nature while coming up with a system solution. High parallelization present in the search application made Google to decide to make system where tasks can be partitioned. Another key insight described in the pper is the fact that depending on the application parallelism might not be there at instruction level but may be present at higher level as hown by the instructuona level measurements. In these scenario architectural techniques like aggressive out-of order execution, speculative execution, does not give much return. More useful way of the parallelism will be to use thread level parallelism such as SMT and CMP. Another key insight that paper provides is the fact that they are worried about price per performance not the absolute performance due to the nature of application and in built amortization cost involved due to the short life span of building blocks. Traditional server solution do give high performance ut reduces this performance per cost metric. Paper rejects the solution for low power which are expensive because amortization cost is significant part of the total cost. Paper describes that they observed good memory performance for the instruction cache and instruction TLB due to smaller inner loop code. And it does not seem to be a bottleneck . They reject the idea of shared memory architecture because they are useful only when computation to communication ratio is small. At Google they partition the index data and computation to to minimize communication overhead. Another aspect they mentions is the fact that large scale shared memory solutions still does not handle failures gracefully and often results in complete system failure.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

(i) The three most important things the paper says:

1. The paper demonstrates how commodity PCs can be much more efficient servers than the normal high end servers used by many companies. Their array of mid-grade PCs saves them money from power, maintenance and even gives astonishing performance. They use cost/performance analysis to find which PCs will be most efficient and find huge savings from using only mid-grade ones.

2. The other insight that google makes is that there is more parallel to find than just parallelizing each separate request. Google splits each requests into many subparts to minimize latency. Each part therefore only needs to search through a small section of the internet for results and then all are returned and quickly sorted.

3. Another byproduct of having large arrays of PCs is it allows for stability via redundancy. Because of there sheer number of computers Google attributes multiple PCs to each part it divides out of each request. This means that if any node is down another will finish and the request will still complete. It also means that if some are varying in speed google only needs to wait for the fastest to finish.

(ii) The most glaring problem with the paper:

Because this is a business they keep a pretty tight lip about their own custom software and hardware. It may be unavoidable in the circumstances but certainly leaves the reader with many unanswered questions. This is avoided in normal papers because they are written by researches that do not have the profit motive to keep secrets.

(iii) The future research directions of the work:

This paper brings out the importance of being able to manage and control huge clusters of computers. It also shows the need for real-world support for accomplishing this task. Google repeatedly states having to use their own custom equipment and software for their tasks. Part of this is so now outside support will be needed for management, but it also is because there were improvements they could make over options currently in the marketplace. The paper also presents a call for more research on what other applications can benefit from highly parallelizable code running on a redundant array of inexpensive machines.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

This paper talks about the cluster architecture maintained by the Google to respond to web search queries using low cost commodity-class PCs as compared to high-end servers. The authors comment that most important factors that influence the design of Google’s cluster architecture are energy efficiency and price-performance ratio. The application talked about is servicing a search query which affords easy parallelization and hence, peak processor performance is less important than its price/performance. The authors make a point that Google strives to provide reliability in software rather than server class hardware therefore they can let go its benefits of robust design. Also, speed is not a factor because of the parallel environment possible. The authors discusses the complete flow of a serving a Google query. The query is given to a Google web server which is nearest to the end host and which has appropriate load. The web server passes on the query to index servers which consult an inverted index and maps each query word to matching list of documents. The process is parallelized by dividing index into pieces (index shards) and an ordered list of document identifiers is generated. This is given to document servers which again use sharding to parallelize the process. Google cluster architecture employs replication for capacity needed in serving huge amount of queries and it also provide fault tolerance which is typically done in a general purpose database. In essence, the replication provides better throughput and availability.  The paper also talks about the how the cluster is connected in racks. They cite power consumption and cooling issues as major challenges for these high density clusters. They talk about hardware-level characteristics like simultaneous multi-threading and chip multiprocessor (CMP) architectures for thread level parallelism for improving performance of their servers. They denounce large-scaled shared memory machines because they do not handle individual hardware components or software failures gracefully. Therefore, many small multiprocessors suites to their needs of providing reliability and fault tolerance and containing the effects of faults to smaller pieces of the system.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

(i) the three most important things the paper says

One of the most important things that this paper says is the fact that, at the volume of requests that Google receives, aggregate throughput is much more important than single request latency.  This reasoning follows quite well with reasoning of a typical scenario: does it matter more that a single user receives a response in .1 seconds vs 1 second, or does it matter more that a particular server/cluster served 10x more users at 1 second versus just 1x at .1 seconds.  This observation allows Google to save tons of money in server hardware by purchasing with the most economical (performance/price) mindset.  Another important idea that the paper demonstrates is that hardware replication (redundancy) is much easier/cost-effective when handling failures than writing software that will handle those failures gracefully.  Hardware replication, at the price-point of commodity hardware is extremely cheap, while software developer time is much more expensive.  Also, this type of software might require frequent changes depending on the type of hardware used, which would require even more engineering time.  A third important observation made in the paper detailed the price/performance disadvantage of concentrating on low-power hardware versus standard commodity hardware (typically).  The paper says that the power and cooling cost savings must outweigh the cost of the hardware itself (while factoring in how long that hardware will last).  When this paper was written, commodity hardware won this battle.

(ii) the most glaring problem with the paper

One of the biggest problems in this paper is that it is devoid of any alternate storage analysis.  We’re expected to take the analysis that hard disks are the way to go without any explanations.  Alternate memory technologies are much more prevalent now and should be included in such a justification, as many of them provide great latency, power, and durability advantages over commodity disks.

(iii) the future research directions of the work

It would be interesting to see some analysis numbers on how switching to lower-power servers would impact the power usage of Google as a whole (and how that impact would translate to power generation companies, and thereby the environment as a whole).  It would also be interesting to see how CMPs and SMT would help power usage (versus single processor commodity hardware).  It may be the case that a mix of low-power hardware with CMP or SMT technology might save money overall.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

Main contributions:

A scalable architecture to provide an internet scale service with cheap desktop-class PCs.

Showed that Fault-Tolerance can be achieved at a large scale using software to overcome faulty hardware.

Provided an alternative metric for evaluating large scale architectures. (i.e. not just raw performance, but a cost to performance ratio)

1. A scalable architecture to provide an internet scale service with cheap desktop-class PCs.
2. Showed that Fault-Tolerance can be achieved at a large scale using software to overcome faulty hardware.
3. Provided an alternative metric for evaluating large scale architectures. (i.e. not just raw performance, but a cost to performance ratio)

Major problem:

This architecture is for a very specific application, and workload. (i.e. easily parallelized tasks, throughput oriented performance goals and a read-dominant workload) In applications that require communication between tasks, or maintain state between jobs, shared-memory systems with closely coupled CPUs might be more necessary.

Future implications:

This raises large issues about power efficiency of desktop-class PCs. There are two routes that can be taken; either improve the cooling mechanisms used in large data centers, or increase the power efficiency of the machines while keeping the cost to compute ratio exactly the same. Both are difficult problems.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

Three Important Things:

• The Google service requires massive computational power and storage. A key insight is that handling queries is an embarrassingly parallel operation. Thus the service architecture is tailored for high request throughput. This is achieved through data distribution and replication, as well as load balancing across data centers and within data centers.
• There are many choices for fulfilling the needs of a web search service. Google uses a cluster of commodity machines, which they have identified as the most cost effective way to build a data center. This follows the principle of aggregating large numbers of components with the best cost/performance ratio, as opposed to purchasing components with the highest absolute performance per component.
• Web search is ideally an “always on” service, which means that it needs to be highly reliable and available. The google approach is to move reliability to software, as opposed to investing in safe hardware and high quality components. Data is replicated logically across multiple servers/clusters, and a level of indirection implemented with DNS allows catastrophic failures to be masked.

Glaring Problem:

Being a proprietary work and relatively short, this paper gives a high level overview of cluster architecture and does not delve into the implementation details. It would have benefited from mentioning the MapReduce framework as well as including more statistics on power usage, deployment numbers, and operational cost.

Future Work:

Computing clusters are becoming more and more prevalent as service  backbones. They happen to serve the needs of Google very well at the moment, but are they really the choice of the future for internet services? Future work could examine the general applicability of clusters and also alternative to them.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The Google cluster architecture is a cost effective approach to data center scaling. Price/performance is the only measure when trying to super-size a data center. The correct type of performance is paramount.  Commodity computers are able to solve problems that allow parallel processing serving thousands of users concurrently.

Compiling and searching index information is a highly parallelizable problem. Independent serches add another parallel dimention to this enterprise. Distributing this problem over many thousands of machines results in a nearly linear speedup per machine.

The sheer number of machines means that some of the units are always out of service. The solution is to use a software based fault-tolerance to identify and exclude the malfunctioning machines. Loss of a subset of computers is expected and remediation is integrated into the software and mangement practice.

Leveraging commodity componets provides  superior cost/performance. A fewer number of high performance machines would not provide the same level of performance as the current soluion. The addiional burden of managing such a great number of machines is offset by the use of custom fault-tolerant software and management.

The document describes Google’s business practices without exploring other types of problems for which this type of system may be used. Additional information on the price/performance and speedup per unit is required in order to apply these techniques to other problems.

A generalized model that allows researchers to determine how to size and maintain very large clusters for various problems based on price/performance and speedup/unit is required. Such a model would allow researchers to determine what problems are solvible in a given amount of time and the cost associated with deployment and maintence during that period.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

This paper describes the Google cluster architecture. It evaluates the workload required to offer a high-performance web search system and shows how the cluster architecture provided in Google’s data center allows high query throughput while keeping the cost per query low.

The main goals of their cluster are as follows:

1. Provide reliability in software instead of hardware. Typical data centers use many redundant hardware systems (redundant power supplies, RAID arrays for disk accesses, etc.) in order to maintain system uptime. However, Google chooses not to use these mechanisms because they increase cost. Rather, they design their software to detect and route around failed hardware. This allows them to use much cheaper commodity machines, even though they are more prone to failure because the software is resilient against the failure of a small number of nodes.
2. Use replication to provide throughput and availiability. Since their workload is very easily distributed, they exploit a huge amount of thread-level parallelism. When a query enters the data center, it is portioned out to dozens of machines, some of which access a distributed inverted index, some of which perform spell checking and ad generation from the search query, and some of which look up the documents which are returned by the index access. This allows the query to be satisfied very quickly even though each node in the system is not particularly fast. In addition to intra-data-center replication, Google also has multiple data centers spread throughout the world in order to provide availability in the face of natural disasters as well as localizing query responses to improve query latency.
3. Maximize price per unit of performance instead of peak performance. In many respects, using “modern hardware” is not too helpful. The Pentium IIIs they are using in their system are objectively much slower than Pentium IVs for many workloads. However, since their workload consists of a large amount of thread-level parallelism and has minimal instruction-level parallelism, moving to Pentium IVs, which only improve on Pentium IIIs on code which contains higher ILP would actually reduce the performance of their system, especially from a cost/query point of view. It also means that any power saving measures need to be balanced against the resulting performance loss, since the metric that Google cares about is Watts/query.

The weakness of this paper is that it is a very high-level overview which does not provide too much detail to allow someone else to implement a similar system. This is to be expected because Google’s architecture is part of their “secret sauce,” which allows them to provide high performance search queries and dominate the search (and thus their advertisement) market.

Future research in this field should include a more general framework for distributing these tasks over a wide cluster as well as an analysis of the class of problems which can be solved by this approach. Clearly it is not well-suited for applications like scientific computing, which are very much peak performance based and relatively insensitive to latency, as well as being more dependent on communication between computation nodes (as compared to Google’s essentially read-only architecture). However, as a general model for serving web requests to a large number of users, it could easily serve as a more realistic model than the traditional “small number of powerful machines” approach.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

In the paper “Web Search for a Planet: The Google Cluster Architecture”, three Google Engineers describe the architecture in place behind the most popular web search engine. The three main compelling features of this architecture are:

1. No specialized hardware is used to build the computing cluster for this architecture. Fault-tolerating hardware components are not used. The selection criteria for hardware components are focused on performance-per-watt or gigabyte-per-dollar, not on peak performance of single components. Reliability in this cluster is achieved by a software layer and massive redundancy of data and machines for the same function.

2. It is a multi-tiered architecture which has load-balancing functionality on each tier, therefore handling fail-over on each tier and reducing the overall complexity. This also addresses scalability issues when the document index grows, as machines only have to be added on one tier.

3. Since the data (term index and documents) is seldom subject to update operations, replication and distribution of this large dataset is easy, because the search queries don’t have inherent state information which needs to be passed around during query execution. The commodity machines each hold a little part of their data (index shards) and answer subqueries for it.

The most glaring problem of this paper would be the claim that this architecture is in its characteristics applicable to a wide range of web applications. As we have seen in the following years (paper is dated 2003), most web applications and web sites are not stateless anymore, as they are personalized for each user. This takes away some of the parallelism properties of this query-only architecture.

Future research could go into the power consumption of this commodity hardware to optimize the query-per-watt ratings of this architecture. This may also lead to research into specialized query-processing hardware with simpler processors, as indicated in the paper.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The paper briefly describes the architecture of Google’s clusters used for supporting web search. Their focus is on utilizing many cheap, commodity computers rather than few expensive, powerful servers. The main contributions of the paper are:

1. Applications (such as web search) that can be broken down into smaller tasks, depend highly on parallelization. For such applications, it’s the throughput of the system rather than peak thread performance that really matters. The authors show that it is most cost sensible to use many cheap commodity computers rather than few powerful server for throughput-oriented tasks. This is because many computer can achieve higher parallelization. It also helps if the task can be broken down into smaller tasks where the computation-to-communication ratio between the tasks is quite high; that is, the sub-tasks can run in isolation without requiring much communication with each other.
2. When using low-end systems, reliability should be handled by the software rather than hardware. This reduces the need for the hardware to be ultra-reliable. Reliable hardware often costs more; therefore by designing a software that can provide fault tolerance through redundancy, they can focus on utilizing cheaper hardware that is not as reliable as high-end servers.
3. The price-performance ratio should be an important decision in choosing the commodity servers. This allows Google to increase the number of its server, allowing for a good level of fault tolerance and load balancing, as well as higher availability. This is because with cheaper hardware, Google can afford to have more replicas of each of its servers. More replicas provide fault tolerance, while a load balancer can more easily divide tasks between them.

Glaring problems: I don’t see any particular problems with their design, aside from high power consumption.

Future research: The paper does not mention anything about virtual machines, so I’m not sure if this is already used: for the power consumption problems, I can’t see why Google couldn’t utilize many virtual machines on the PCs to take better utilization of CPU and power. Also, it would be valuable to see a mix of cheap and expensive computers handling different tasks for the Google web-server. For example the less parallelizable tasks such as query analysis and spell-checking could be performed on single higher-end servers.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

In this paper three engineers from Google give an overview of how the famous research engine is structured. In particular they present the parameters they took into account when they structured the Google hardware infrastructure.

These are the three most important features of their architecture:

1. Software instead of hardware reliability. The entire Google’s infrastructure consists of a very large cluster of inexpensive desktop-class machines and hardware load balancers that distribute the workload among the different machines within different subclusters. This allows  to one side to achieve extremely high performance  and to the other side to provide reliability. The machines that answers the queries are stateless, and share a common index within the subcluster they are in. So if a machine goes down, the load balancer for that subcluster would reroute seamlessly the requests on the other machines.
2. Cost/performance, cost/query. The main parameter they use when they have to choose the hardware components of the cluster is the cost/performance, expressed as the overall cost of the machine (capital expenses and operating costs). They also wanted to maximize the throughput instead of the peak performance. So they purchase the CPU generation that gives the best performance per unit price, not the high end server that can be several time more expensive than a normal pc. At the time of the paper, the best CPU for Google was the Pentium III. It was preferred to the Pentium IV because of its shorter pipeline and branch misprediction cost, as well as for its considerably smaller power consumption.
3. Hardware structure reflecting the software architecture. Folks at Google did a really good job in understanding how their software works and how it scales up. They hence recreated in hardware such structure, with clusters and subcluster handling different parts of the query answer. By doing so, they achieved a very high throughput as well as they can easily almost linearly scale  up their architecture by adding more machines. I think that a linear scaling up of the performance with the hardware is really a remarkable result.

In the paper the authors present an interesting analysis of the trade-offs between different CPU architectures and their relative power consumption cost and heat dissipation. These are two key aspects in nowadays data centers as well as they are a very important topic for the US administration. The fact that folks at Google were already considering those issues several years ago when those topics were not so much discussed, is another proof of the quality of the people working at the famous research engine. However, in the paper the authors did not really explained how they solve the power and heating problems. They kind of leave the questions open. An interesting article on the topic is the following:

http://asia.cnet.com/crave/2009/04/03/google-uncloaks-once-secret-server/

As a direction for future research I would definitely identify the power consumption reduction problem. As said in the article, it is becoming a dominating part of the operating cost of a data center. Accordingly to the article above, people at Google are working hard on this topic. UCSD with the CALIT2 and the CSE is working on the same area as well with the Greenlight project. I am sure some interesting results will come out quite soon!

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The paper provides an overview of Google’s network architecture and query processing in which they use a cluster based approach of several PCs instead of using a few high end and powerful servers. This is because Google parallelizes their searching by indexing and assigning them to different servers which can process parallelly and independently since the communication needed between them is minimum. Hence such a design is tailored for the best aggregate throughput request rather than peak server performance since response time can be managed by parallelizing individual requests. Thus the best price performance ratio comes from a infrastructure of cluster of commodity PCs than high end servers. The Google architecture also uses replication of its internal services across multiple nodes to have fault tolerance. In the hardware level, the use of powerful single threaded processors becomes useless in the context of the server applications that they have to run given its inherent low IPC. Hence thread level parallelism offered by multithreading and multiprocessing is a much more viable option that can reduce the time to service a request almost linearly by dividing it among many parallel threads. Also for the memory systems, moderate L2 cache sizes are sufficient due to the tight loop of code executed by the server applications and the amount of computation per data memory access is quite high. Moreover large scale shared memory system do not handle failures gracefully as the entire system may crashes where as leveraging several commodity PCs provides the redundancy for fault tolerance.

The down side of using thousands of PCs than few high end servers is the significant administration and repair cost. But in a homogeneous system like Google, such  cost is brought down since almost all the servers run the same few applications and also have the same configuration. Repair cost is also kept reasonably low by batching them. Another major challenge of such architecture is the power problem because the relatively large number of PCs being packaged in a single rack can easily exceed the power density limit tolerable in data centers. As a result even low-tech PC clusters using relatively straightforward packaging need special cooling or additional space to bring down the power density.

Future directions may include also considering the high end servers into the equation and given them at disposal to strike a optimum point of balance between cost and power or performance which might provide a better solution than only PC based clustered architecture.

Web Search For a Planet: The Google Cluster Architecture May 12, 2009

Google’s web service cluster follows the following key design principles.

1) The use of software reliability over reliable hardware. Commodity PC components were used to get the best performance per unit price and the cluster consists of about 15,000 of these servers.

2) The splitting of large index data to smaller index shards (a random subset of the full index) and replicating those shards across many index servers to provide fault tolerance and higher parallel throughput.

3) The GWS architecture handles queries by DNS load balancing to chose a cluster close to the end user and then hardware load balancing within a cluster. The query is sent to the index servers for ranking and results are merged. Document servers are queried based on the index server’s results to obtain parts of the actual documents from the docids. The ad server and spell check will add data to the result and the GWS returns the HTML result to the user.

The glaring problem with this paper is the authors present no detail on claims of index servers do not saturate the memory bus and cost calculations.

Further research can be done in the following areas:

1) low power computer/network architectures

2) the comparison of different network topologies like fat-tree and throughput

3) data center cooling and organization

4) How modern CPU architectures like Core i7 and how general purpose GPUs can perform in terms of throughput and dollar/query and performance/dollar since the application is highly parallel.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The article provides a high level overview of Google’s search infrastructure and the design decisions that motivated such an infrastructure.

The key design principles that Google’s clusters follow include:

• Software reliability: Failures are tolerated almost entirely in software and very little is actually spent on highly reliable servers or fault tolerant hardware designs.
• Use of replication for request throughput and availability: To deal with failures, all services are replicated across several machines. Requests to different services or replicas of the same service are highly parallelizable and this improves the throughput of the system.
• Price/performance rather than perk performance is the metric for making design choices. All designs are tailored to offer best aggregate request throughput rather than high performance for single request since their request processing can inherently be quickened by exploiting parallelism and distributing the task of computation for the particular request over more servers. This principle motivates the use of commodity PCs to build their clusters and reduce the overall price/performance.

The article provides an idea about the characteristics of applications that would benefit from the use of such commodity PC clusters rather than a few high performance machines. These typically include applications whose focus is on price/performance rather than peak performance, those with little private state, lot of request level parallelism etc.

One concept that is lacking in the article is a more detailed description of the network infrastructure. Increasingly, the network is becoming a very important entity in the data center due to massive amounts of data that has to be moved around to let the CPU’s on the servers do useful work rather than just stay idle. Perhaps, the network was not really a bottleneck at the time the article was written, but any similar article today would definitely have to contain a more detailed description of the network aspect of the data center.

It would be interesting to see how Google’s other services are structured around the commodity PC cluster architecture. While search is one application that can inherently be speeded up through parallelization since each query requires a lot of computation over large datasets. However, the same might not be true of other types of services that Google has expanded to over the past 5-6 years. For services like Youtube, there is not much processing to be done to serve a particular request. So the performance as seen by a client cannot be improved by spreading the computation over more servers. So in these cases the actual peak performance of a single server might begin to affect the design choices again. However today, commodity class PCs for data centers typically have enough computation power to service few requests.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The paper gives an overview of the design decisions made in architecting Google’s web servers that use multiple clusters of commodity PCs. The main design principles used behind the architecture are to induce reliability and fault tolerance in software and to build a cluster that gives the best aggregate bandwidth as opposed to peak performance bandwidth. The authors characterize performance in terms of price/performance and kw-h/performance instead of treating each metric disparately. Software reliability in such cluster systems is argued for and the replication of services across many different commodity PCs is highlighted. The main points to take away from the paper are the architecture of the Google’s query processing framework, the high-level hardware-software design decisions and the impact of using commodity PCs for implementing web search as against the usage of high-end servers.

Query processing starts with the host sending a DNS server request for Google.com, which is then routed to a load balancing framework to select from the nearest available cluster to service the request. Upon selecting the most suitable geographical location, secondary load balancing system selects a given cluster based on the available capacity of various clusters. The overall goal of this exercise is minimize the round trip time to service a request. When a cluster is assigned to service a request, the user’s browser makes a subsequent HHTP request for a search string that is looked up on the index servers that point to appropriate document servers. Google parallelizes the job of index search by splitting the index into multiple shards and offloading the search process onto multiple server pools which have search services replicated onto them. Indexing returns a set of docids which are then used to index into the documents servers which return the appropriate HTML files to be routed to the requesting host.

Google servers use replicated software services across a pool of machines since individual machines could be unreliable and since this replication is obtained at no additional for multiple machines are used for data replication. Also since commodity PCs offer a cheap proposition, Google invests more on the search algorithms and query processing. Google servers use multiple x86 machines organized in racks connected by gigabit Ethernet backbones to implement clusters. The paper proves that use of multiple commodity PCs over high-end servers amortizes price over a performance range. And also the system administration overhead of handling multiple machines is amortized by batch processing lots comprising 1000s of machines. The authors suggest that although using multiple machine pools introduces significant power overhead, the expenditure on building cooling systems and power bills is much acceptable given the performance and throughput gain that is obtained over a period of time.

The authors indicate that the index-serving phase of query processing is computationally intensive, has significant control overhead and has a low CPI. For such processing the authors propose to leverage trivially parallelizeable tasks of index processing and use servers providing high TLP and CMP. This would result in an almost linear speedup of the application even when using modest sizes of caches in the memory hierarchy. The argument of using smaller caches is further strengthened since index accesses have good spatial locality resulting in good hit ratios.

All applications that have intensive index serving, document lookup and web server query processing requirements can benefit largely in terms of performance and cost from Google’s network architecture. The proposal made in the paper is highly application specific and its scalability is questionable when proposed to deploy in networks with disparate requirements and bursty traffic. However, like it is suggested in the paper with sound critical decisions about the class of machines, the degree of parallelism on individual machines and the required number of machines that replicate a given service, an efficient architecture implementation can be obtained.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

(i) The three most important things the paper says:

1. The designers chose to leverage cheap commodity machines (which were chosen based on cost per query rather than peak performance). Since one one of the consequences of this design choice was that the hardware may be unreliable and there was no inherent fault tolerance, additional redundancy was required for fault tolerance and availability.
2. One of the most importance characteristics of the Google cluster architecture is its parallelism: that is, the architecture breaks a query lookup in an overall index into multiple lookups in smaller indices (called index shards), then a cheap merge step is performed to consolidate the results. Furthermore, multiple processors can simultaneously run multiple queries.
3. An important question that needs to be answered in any large-scale data center is how to reduce power usage per server. The Google cluster architecture’s solution is to use low-power servers, with the stipulation that the servers need to maintain watts per unit of performance and price.

(ii) The most glaring problem with the paper:

The authors argue that the cost of maintaining a large number of commodity machines is not significantly greater than maintaining a few high-end servers. Their reasons include the homogeneity of the search application and amortizing costs by batching repairs and using identical configurations. While this may be the case for purely hardware/software-oriented costs, this seems like a bit of a simplification which does not factor in some of the costs, such as additional work to the administrator, especially in cases where servers fail and new ones need to be ordered and put in place of the failed servers. This would likely happen much more often. In addition, monitoring the health of the thousands of PCs would probably be a much greater task than monitoring only a few.

(iii) The future research directions of the work:

One potential thing to look at is caching entries based on the search query, rather than simply caching cache lines. That is, the results (or a portion of the results) from some popular search terms could be cached for easy future retrieval, and perhaps even gossiped in some way to other processors.

Web Search For A Planet: The Google Cluster Architecture May 12, 2009

This paper describes Google’s cluster that handles web searches. Google’s architecture goals were heavily influenced by energy efficiency and price-performance ratio. So basically Google wants its web searches to run quickly while maintaining low cost. The main points of this paper are tricks to achieve their goals of running quickly and cheaply.

Major Points:
1.) Software Reliability
It is very important that the authors use software reliability versus hardware reliability. This essentially accomplishes their low cost goals because they can use cheap commodity computers to build a high end computing cluster for a low price. They focus on tolerating failures in software instead of relying on hardware features like redundant power supplies and RAID.
2.) Replication
To get the web searches to run quickly, the authors use replication throughout the cluster to increase throughput and availability. Since the commodity computers are inherently unreliable, they need to be replicated anyway. Since they have to replicate them, they put them in certain locations to lower the latency for certain requests.
3.) Parallelism
Since web searches deal with a large subset of data, Google breaks this data into pieces they call shards that are a randomly chosen subset of documents from the full index. The request will then choose machines within a pool of machines (associated with a shard) using a load-balancer. By parallelizing the search over many machines, they reduce the average latency require to answer a query. Also since each shard doesn’t need to communicate with each other, the speed up of adding more machines to the pool is nearly linear.

Glaring Problem:
They claim that many other applications besides web searches share Google’s characteristics. Most applications update data that they are reading though unlike the read only data that the web searches deal with. This break the abstraction of synchronization and can greatly decrease the performance. Their solution really only works on a homogeneous cluster.

Future Work:
There is a growing trend of using commodity computers for large clusters as technology advances. If used with the right architecture, the cost will go down while the performance of a cluster will increased by commodity computers instead of special hardware. Using software fault tolerance over hardware fault tolerance gives the advantages of using these cheap commodity computers. Growing trends in parallelism technology will also increase the performance and reach of this architecture.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

1. Use of inexpensive PC-based clusters instead of high-end server

Google identifies that a much better performance/price values can be got by making use of large number of commodity PCs instead of a few high-end servers. This is the result of the application being compute intensive with low communication overhead.

2. Software based reliability over to hardware redundancy

Google handle failures and system outages by simply maintaining multiple copies of the data. This way it manages to obtain added capacity when all systems are in operation and takes a small hit on throughput when a hardware failure occurs. It does not provide for hardware based reliability solutions such as RAID/redundant power supplies, etc.

3. It identifies that chip multiprocessor (CMP) architectures and simultaneous multi-threading (SMP) is better suited for the application at hand as compared to architectures exploiting instruction level parallelism. Similarly it also identifies that the search application can benefit only from data prefetching based on spatial locality and not temporal locality

Drawbacks

Maintaining synchronization and coherance between multiple data centers maintaining replicate copies of the web is not as trivial a matter as they make it sound.  Every time an update is made it would have to be propogated to all data centers maintaining replicates. Communication overhead and latency would be substantial. However, for the application at hand, this overhead is probably not a mjor concern and can be tolerated.

Future Work

Since a large number of search requests arrive at a Google cluster simultaneously it might be possible to combine mutiple searchs with same or similar search strings. This might reduce the amount of parsing that needs to be done by the index and the document servers.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

1)

i. For highly parallelized applications, using a cluster of commodity PCs chosen for their price/performance ratio can yield significant savings compared to buying a high end server. In the paper the example was given of a rack that cost 1/3 the price of a typical high performance server, but has 22x more CPUs and 3x more RAM. The main thing that high end servers provide high reliability and high interconnect speed between the different CPUs.

ii. Reliability can be provided by replication and software. In the Google setup a high degree of replication is used. They then use software to manage switching to replicas when necessary and dealing with faults in the system.

iii. One big issue with using a commodity PC cluster is power issues. Their commodity cluster had much higher power demands than a typical data center. Dealing with this requires special cooling or spacing out racks to manage the heat. However due to the short lifespan of the hardware spending more for a lower power servers is not really worth it since the price of the hardware far exceeds the price of the power used.

2) One flaw in this paper is they did not talk about the network architecture for the system. They didn’t address how they deal with the large amounts of data moving through the cluster. They also failed to address if they use anything fancy like IP multicast to distribute a request to each shard pool. I think it would have been interesting if the paper included these details.

3) Future research directions include looking into how to lower the power usage. One thing worth investigating is instead of giving each PC a power supply they might be able to get a more efficient power supply to supply power to the entire rack. This would also save money in repairs since they said one of the more faulty components is the power supply.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

(i) Three most important things

1. Replication should be used for better request throughput and availability. The Google Cluster architecture replicates web services across many machines because machines are inherently unreliable. By parallelizing the web search over many machines, Google reduces the average latency necessary to answer a query and replication provides free fault tolerance.

2. Price per performance beats peak performance. Google purchases the CPUs that currently give the best performance per unit price and not the CPUs that give the best absolute performance because Google tailors the web service design for best aggregate request throughput since response times can be managed by parallelizing individual request.

3. The use of commodity PCs reduces the cost of computation. Google combines thousands of commodity-class PCs instead of few high-end PCs to implement Google web services since the hardware selection process focuses on machines that offer an excellent request throughput for their application. As a result, Google can afford to use more computational resources per query, employ more expensive techniques in their ranking algorithm, and search a larger index of documents

(ii) Most glaring problem

The most glaring problem would be that Google assumes that accesses to the index and other data structures involved in answering a query are read-only, but this avoids the consistency issues that arise in general purpose databases. Many applications would require updates to the data.

(iii) Future Research Directions

Future research directions for this work would be to see how the Google Cluster architecture could apply to other applications that query large databases and provide a way for these applications to update their data if necessary.

Web Search for a Planet: The Google Cluster Architecture May 12, 2009

The paper is really an overview of how Google’s search queries are handled and what factors are taken into account when making hardware decisions. The query architecture is massively parallelized and load balanced across many commodity PCs. Thousands of PCs form a cluster, and there are many clusters geographically distributed all over the world. Google’s query application is representative of a certain class of application that can be parallelized across computational units.

The main contribution from this paper is that parallelizable applications can be deployed over many different computers. This flexibility provides scalability, robustness, and flexibly when evaluating and purchasing hardware.

Instead of purchasing several high-end computers that have multiple processors, Google can purchase considerably more mid-range computers with modest performance for the same price. Although these mid-range commodity PCs have slower peak performance, Google’s query application can still be served just as fast. The key is that because the application be partitioned to run on multiple computers, many PCs can run in parallel to provide the result. Thus, the primary metric for purchasing PCs becomes price/throughput, not price/peak-computation.

Of course, maintaining more PCs adds to the overhead cost. This is mitigated by the observations, that most PCs have a useful life of 3 years and that administering 100 PCs is about the same as 1000 PCs.

A result of having more computers is that the system becomes inherently more robust. If a computer fails, the loss represents a smaller percentage of the cluster. Furthermore, multiple individual PCs allow failures to be contained. A failure on a multi-processor or multi-core computer often brings down all the processors/cores.

Lastly, the distributed computational nature of Google’s query application allows for great scalability. Simply adding more computers reduces the amount of work performed on each computer for a single query, which allows each computer to perform computations for more queries.

The only drawback with this architecture is that it is only applicable to a class of application that can be easily parallelized. While many applications can be segmented to execute computations on pieces of disjoint data, with low synchronization or cross-computer communication, I feel that most applications cannot. Indeed, this is a great architecture for Map/Reduce applications.

I’d be interested to see how this architecture performs when the application has high inter-PC communication requirements. I expect that there is some point in the spectrum where a faster processor interconnect is necessary (i.e FSB).

Web Search For a Planet: The Google Cluster Architecture May 12, 2009

(i) The three most important things the paper says:

1) By providing reliability in software rather than in server class hardware, they can use commodity PCs to build a high end computing cluster at a low end price.  They argue that since hardware is intrinsically prone to failure, it was a more practicle idea to support reliability in software.  And sice they are going to support reliability in software, there was no advantage from a reliability point of view to buy more expensive hardware.

2) By choosing machines based on “price/performance”, then commodity PCs is the superior choice over specialize server hardware.  For instance, they argue that since their system parallelizes very well motherboards with 4 processors doesn’t perform well enough to recoup the cost.  However they do acknowledge that this was a case for the class of problems that they are solving, and that other applications may indeed demand a motherboard with 4 processor to satisfy the “price/performance” argument.

3) Even though the Google cluster has many machines by using commodity PCs, they show that this is manageable since they have a homogeneous system.  They argue that since indexes are broken up into shards and each machine has a specialized function, all machines have identical configuration.  This is another important factor in the argument to use commodity machines.

(ii) The most glaring problem with the paper:

The biggest problem with the paper is that they didn’t really address the “power problem” in full.  They provide calculations of how much power a “Google Cluster” would take and what it would take to justify the purchase of “low power servers”.  However they didn’t specify how they addressed this problem in their solution of commodity clusters.  Perhaps they were afraid of giving out their intellectual property though.

(iii) The future research directions of the work:

The future research of the work would be to see how scalable their system is as the searching/datamining algorithm becomes more complex.  Will the system of merging results from multiple processes continue to be a trivial task?  Also they didn’t discuss the merging step much, but since it is an aggregator, would it benefit from using a non-commodity PC?

WEB SEARCH FOR A PLANET: THE GOOGLE CLUSTER ARCHITECTURE May 12, 2009

The purpose of this article was to describe the Google cluster architecture of a large number of cheap PCs supporting parallel and identify the strengths of such a design compared to the alternative of several, high performance systems. The key points in this article were:

1.Google focuses on software reliability and simply assumes that all of their hardware is unreliable. This allows them to buy much cheaper machines and also focus their efforts on a large amount of replication so the loss of one or several computers is of no concern to the overall system as no one server maintains anything critical that is not maintained on several others. This is a reasonable approach since the software is in their control and the hardware is largely not.

2.Focusing on price per performance rather than just performance has enabled them to buy a significantly greater number of systems and therefore take advantage of the massive parallelism that was built into their search algorithm. This translates into more clock cycles being available for complex calculations and also better performance for the individual user.

3.There are several shortcomings to this method discussed in the paper. One significant one is the amount of resources that need to be dedicated to maintenance and repair. They were able to get away with this because most of the servers were all the same. There are also physical issues such as cooling power, and space that come into play.

One issue that I saw with the paper was that they did not address where they were looking to move forward and increase their scale. The problems that they briefly mentioned are serious concerns now, as is maximum bandwidth and switching.

The future research of this paper is to increase the scale of such systems even further and also to be able to handle the increased performance of commodity PCs across our existing internet architecture. Also, research into massively distributed systems is a field that is looking to extend systems such as Google’s into something more than a large number of Stateless PCs and into something that can communicate internally for large computations.