"Cluster-Based Scalable Network Services"

This paper addresses the issue of scalability in network services, highlighting three fundamental advantages of using clusters:  scalability, availability, and cost-effectiveness. Scalability means an incremental and linear increase in hardware can maintain constant service performance as load increases. Availability means that the service must be available 24x7, regardless of failures (which are masked by software). Cost-effectiveness means that the service must be economical to scale (emphasis on commodity hardware). However, clusters also present challenges for administration, component vs. system replication (matching hardware to software scaling), partial failures, and lack of shared state among cluster nodes.

The paper proposes a layered architecture based on separation of content from services, using a service-programming model based on workers that perform Transformation, Aggregation, Caching, and Customization (TACC) of content on top of a Scalable Network Service (SNS) layer. It then identifies several techniques: BASE (Basically Available, Soft State, Eventual Consistency), allowing partial failure in clusters, but with less complexity and cost than ACID.  Many web services don't need the strong consistency or durability of data provided by ACID, and instead place more value on high availability.  By not requiring durability and consistency across partial failures, BASE effectively reduces communication and disk activity (or postponement), increasing availability.

The SNS layer provides incremental/absolute scalability of worker nodes (which are simple and stateless), worker load balancing by the manager, front-end availability/fault tolerance, and system monitoring. On top of this, the TACC layer provides an API for transformation of data objects, aggregation (combining data from various objects), customization, and caching.

The paper then looks at the implementation of two network services that use BASE (or BASE-like techniques). TranSend, a scalable transformation and caching proxy for Berkeley dialup users, and HotBot, the Inktomi search engine. In TranSend, web content and other application data exploited BASE semantics: load balancing data was stale (timeouts help recover from extreme cases), transformed data was cached (i.e. soft state), and approximate objects were used by distillers (which transform/aggregate content). However, some data—user profiles—did require the guarantees provided by ACID-compliant databases.

Some of the ideas in the paper are specific to the problems the authors were most concerned with at the time and which have become less relevant (e.g. caching and distillation of web content, etc.). Nevertheless, many of the general ideas presented in this paper have been very influential (or predictive of future trends). The layered architecture is very similar to (if more narrow than) the WSCs described in the Google paper. Likewise, the use of commodity servers is a trend that has only increased in popularity (and servers are becoming more and more lower-end). The BASE techniques and a general shift way from ACID (where immediate consistency, etc. is not absolutely necessary) have also proven influential--and quite logically led to Brewer's CAP theorem--leaving a significant impact on cloud computing.

"Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services"

The CAP theorem states that it is impossible for a internet service to simultaneously provide consistency, availability, and partition-tolerance. Only any two of the three can be provided. By consistency, Brewer meant atomic data objects, such that it appears that each operation was completed at a single instant (e.g. any read that occurs after a write returns the newest written value). Availability is defined as the guarantee that every request by a non-failing node will (eventually) result in a response. Partition tolerance means that the network can lose arbitrarily many messages sent from one node to another and still return a result.

The proof of this theorem uses an asynchronous network model, where there is no clock and nodes make decisions based on messages received. First, the authors prove that asynchronous networks cannot provide a data object that guarantees availability and atomic consistency when messages are lost, since a read could return data from a stale write (which was not updated due to lost messages). In synchronous (or partially synchronous) network models, a weaker form of consistency can be achieved using timeouts. In general, most web services have to settle for "most of the data, most of the time."

This theorem is highly relevant today and is becoming more and more important. Cloud computing and Internet services are increasingly relying on distributed systems, where networks are not entirely reliable (even more so as applications begin to span several datacenters). The work done in the paper was new (i.e. the theorem had not been proved), but I'm not sure that a formal proof was necessary for people to understand that only two of the three conditions can be possible at once. For me, the most interesting part of the paper was the realization that services need to determine what sort of failure is acceptable (e.g. which of the CAP) -- with web applications often valuing availability over consistency. These tradeoffs are fundamental decisions that application designers need to acknowledge and keep in mind.

"The Datacenter Needs an Operating System"

This paper encourages the development of a operating system for data centers. Taking fundamental OS concepts as applied to data centers, this boils down to a system that would manage resource sharing, data sharing, programming abstractions and global debugging/monitoring tools. This is motivated by the observation that applications that run in data centers are now more general-purpose than they were originally, and the current tools available are not necessarily well designed for general use (e.g. MapReduce provides resource sharing, but only among MR jobs -- what happens to other applications that don't translate to MR that easily?).

Resource sharing among diverse applications requires more fine granularity than is currently present (most cluster apps are written as standalone programs that require the entire use of their [sometimes virtual] hosts). Other resource sharing questions include network/bandwidth sharing, service/application dependencies, scheduling, and virtualization.

Data sharing in DCs is usually accomplished via a distributed fs, but this still entails a lot of overhead costs for loading data (e.g. into MapReduce jobs).  Resilient distributed datasets "remember" the transformations used to create them, facilitating re-running tasks -- and they can be kept in memory for extra speed. Other questions for the data sharing component of a DC OS would include a standardized interface for storage, streaming data, and performance isolation (e.g. live vs. non-live data).

New programming abstractions could help with developing applications more quickly and effectively: APIs for launching and monitoring tasks, standardizing communication patterns, and fault-tolerant data structures. Debugging on a DC app is geared both to correctness and performance analysis, since incorrect outputs could result from performance issues (e.g., with the underlying distributed software) as well as coding problems.

I think this paper does a good job of taking several of the core concepts of operating systems and applying them to cloud computing and data center applications. There doesn't seem to be much question that all of these issues are increasing relevant to datacenter computing and I liked seeing the parallels with classic operating systems, suggesting that much of what we know already can be applied to this new DC paradigm. With the rise in cloud computing, these issues will become only more relevant over the next decade. The idea of a unified system that addresses all of these issues seems attractive, but I wonder if this will really happen in practice, as many solutions for each of these issues (albeit not necessarily optimal ones) are already in place and it could be difficult to effect their replacement.

“Data-Level Parallelism in Vector, SIMD, and GPU Architectures”

This chapter from Hennessy & Patterson offers a detailed overview of single instruction multiple data (SIMD) architectures, comparing two main types: graphics processing units (GPUs) and vector processors (e.g. Cray).

GPUs are very widespread, which greatly helps push their adoption. However, CUDA/OpenCL have significant learning curves. Not only is the jargon an issue, as the book points out (with helpful--and somewhat humorous--translation tables), but learning to program them effectively is also non-trivial. They have many different layers of memory with different strengths/weaknesses (latency, scope of shared memory, etc.) and choosing the optimal combination can be difficult for the programmer. Transferring data from main CPU memory to internal GPU memory also is very costly and hinders overall I/O speed. The cores themselves are also not very powerful, although speed can be improved using faster (but less precise) math libraries, etc. At the same time, the vast number of cores available on GPUs provide an excellent opportunity for data parallel applications to run faster.

Vector processors, on the other hand, are somewhat more intuitive to program and effective in data parallelism.  However, this extra programmer-friendliness requires more architectural complexity, making them more expensive. GPUs are already so widespread (due to their graphics applications) that it seemsmost likely that they will be the dominant  trend going forward. As far as their application to cloud computing, it seems likely that some combination of CPUs and GPUs will certainly make their way into the servers in WSCs. The large amounts of cores make them great for MapReduce-style and other data parallel applications. Nevertheless, in addition to complexity of programming, virtualization and scheduling issues remain obstacles to widespread adoption of GPUs in cloud computing.

"Amdahl's Law in the Multicore Era"

This short article analyzes Amdahl’s Law in the context of multicore processors. Amdahl’s Law says that the amount of speedup depends on the fraction of the program that you can parallelize. Originally, the law was used to emphasize the importance of producing more powerful single-core chips, since parallel performance would always be limited by the sequential part of the code. However, massively parallel machines now allow computations on data that would have previously been thought impractical, greatly increasing the need for further development of parallel architectures.

To determine the law’s applicability to multicore processors, the authors examined three different types of multicore processors: symmetric, asymmetric, and dynamic. Symmetric multicore chips have cores that all use equal fractions of chip resources. Asymmetric chips have a single (or several) core that is more powerful than all the others. Dynamic chips could potentially allow cores to join forces for sequential portions or operate independently for parallel portions. The authors show that asymmetric and dynamic models offer the greatest potential for speedup (with dynamic even greater than asymmetric, due to its flexibility).

This article’s approach is certainly significant and relevant, as the number of cores in multicore processors continues to increase. Likewise, asymmetric multicore processors (like Cell -- or the combination of CPUs and GPUs) offer opportunities for improving both sequential and parallelizable portions of programs. It seems plausible that hundreds or thousands of GPU-style cores could begin to complement CPUs in cloud computing, though there are drawbacks including the complexity of writing the programs to exploit both the CPU for sequential and GPU for parallel portions of code (in addition to scheduling and virtualization issues).

“Performance modeling and Analysis of Flash-based Storage Devices”

As SSDs become more popular and less expensive, their widespread adoption necessitates a way to compare their performance both among themselves and to that of traditional hard disk drives. This article uses a black-box model to evaluate SSD performance, with enough granularity to take into account the particularities of SSDs -- especially the slow write speed (due to slowness of erases) and slow updates (which require copying, erase, and write).

The black-box model proposed by the authors seems reasonable, especially given the differing internal structure of SSDs (and the lack of knowledge thereof due to IP). As SSDs become the norm, there will need to be a way to differentiate between them and establish their relative performance. As the article shows, the main shortfalls with SSDs are several: slow erases (and, thus, writes) and the wearing-out of the cells themselves, especially on write-intensive workloads. However, I think that instead of comparing the SSDs in this article to a 5400 rpm HDD, it would have been helpful to see how they compare to a high-end disk (15k rpm) and/or an array of HDDs in RAID. This would help identify which higher-end hardware options provide better performance (i.e., whether  SSDs outperform fast disks, which they probably do, and by how much/on which operations).


That said, SSDs as they are now (or at the time of article writing) seem like an especially good choice for accelerating applications (e.g. as a cheap version of a RAM-based cache) where reliable storage is not really required. Likewise, read-intensive applications would also benefit tremendously from SSD adoption. As SSDs improve, the wear issue might become less relevant. However, the highest barrier to widespread adoption currently seems to be the price. As prices decrease, higher rates of SSD failure might simply not be relevant if they’re used in the distributed and redundant file/storage systems characteristic of cloud computing. That said, eventually phase-changing memory (PCM) will probably overtake SSDs, given their higher reliability.

“The Datacenter as a Computer” (Chapters 3, 4, 7)

Chapter 3 focuses on hardware choices for WSCs, primarily the difference of using high-end servers (e.g. HP Integrity Superdome) versus lower-end servers (e.g. HP ProLiant). While high-end servers have excellent internal communication speeds, as soon as the data sets get too large for a single server, network latency begins severely limiting the benefits of a cluster of high-end servers relative to their cost (especially for parallel tasks with high levels of inter-node communication). This motivates the prominence of commodity servers in datacenters, since their lower cost outweighs the small marginal benefit of using large servers. However, one major trade-off is that software may need to be optimized to tolerate the higher latency for requests caused by slower CPU speeds (among other deficiencies in low-end servers, e.g. low memory & disk capacity, etc.).

Chapter 4 details the power supply and cooling systems for datacenters. Datacenters can be classified according to their level of redundancy, with most large commercial datacenters providing multiple power and cooling distribution paths (though not necessarily more than one active one). Power systems usually include an uninterruptible power supply (UPS) system which feeds into power distribution units on the DC floors. For cooling, racks are raised from the floor and either cooled with air,  fluid-based cooling towers, and/or in-rack coolers. Datacenters determine their level of redundancy based on the amount of up-time that they need to be able to provide.

Chapter 7 provides a detailed discussion of managing hardware failures in WSCs. The huge amount of hardware required for a WSC ensures that hardware will fail -- the question is how to tune the balance between the cost of failure (and dealing with it) and the cost of preventing the failure. WSCs should implement a fault-tolerant software infrastructure layer to reduce the cost of making the applications themselves tolerant to hardware failures. This also makes it easier to perform upgrades (since servers don’t always need to be running) and repair failed hardware. Categorizing service faults by severity allows one to determine which faults are tolerable (e.g. those that provide intermittent service degradation) and which ones must be prevented (e.g. unavailability of the entire service).  Interestingly, the experience at Google (as well as in other papers cited) suggests that most service disruption events are caused by human elements: configurations, software, and other human interference, while network and hardware failures are responsible for relatively fewer service interruptions.

Is the problem real?

All three of the issues discussed: trade-offs in the choice between low-cost and high-performance hardware; trade-offs between power/cooling reliability and cost; and trade-offs between failures and the cost of preventing/repairing them are critical topics for large datacenters (and, consequently, WSCs).

What is the solution's main idea (nugget)?

The overarching idea of these three chapters is that for each of these questions (hardware, power/cooling, faults) a balance must be reached between the benefits of an ideal set-up and the cost benefits of allowing for failures and managing them as best as possible (with as little service degradation as possible). This balance depends on the WSC and its applications, but in general it is more cost-efficient to write fault-tolerant software.

Why is solution different from previous work?

The ideas presented here differ primarily from previous solutions by the emphasis on tolerance of failure and latency. With datasets much larger than any one computer can handle, hardware failures are inevitable and it makes sense to spend more time developing software that can tolerate faults (at various layers).

Does the paper (or do you) identify any fundamental/hard trade-offs?

All three chapters are essentially about the fundamental trade-offs presented by each issue (hardware quality, power/cooling redundancy, hardware faults) and striking a balance between the costs and benefits of varying levels of hardware reliability: see discussions above.

Do you think the work will be influential in 10 years?

Many details of the hardware and infrastructure will no doubt change over the next decade. However, the questions of hardware choices (high-end vs. low-end), power/cooling reliability, energy usage, and fault tolerance--as well as finding the right balance between the trade-offs implied by each question--will no doubt remain relevant as datacenters (or even groups of datacenters) expand and require more sophisticated infrastructure to accommodate surging amounts of data.