Papers
Designs, Lessons and Advice from Building Large Distributed Systems
Jeff Dean · LADIS 2009 (keynote), 2009
What is this talk: design advice distilled from large-scale systems
This material is a keynote by Jeff Dean, Google Fellow, presented at the LADIS 2009 workshop on large-scale distributed systems. It is a set of slides, not a classic paper, so there is no single algorithm or theorem: there are design lessons and rules of thumb drawn from building large systems. The slides start from a question: given a basic problem, how do you choose the best solution? And they remind us that 'best' can mean the simplest, the highest-performing, the easiest to extend, among others. They then point to one skill as important: estimating the performance of a design without having to build it first. This material covers the design-advice part of the talk: the table of costs of basic operations and a step-by-step worked estimate (tools of that skill), as well as guidance on designing for growth, shared infrastructure, and low-latency applications. The rest of the slides describe Google systems (GFS, MapReduce, BigTable, among others), which are not covered here. One warning is essential for anyone reading this today: all the numbers in the talk are from 2009 hardware. They serve to give orders of magnitude and proportions between operations, not as current specifications. In real capacity work, replace the values with current measurements.
Numbers Everyone Should Know (2009 values)
A slide lists approximate costs of basic operations, with figures from that time (2009). An L1 cache reference costs 0.5 ns, a branch mispredict 5 ns, an L2 cache reference 7 ns, and a mutex lock/unlock 25 ns. A main memory reference costs 100 ns. Compressing 1 KB with Zippy (a fast compressor used at Google) appears as 3,000 ns. Sending 2 KB over a 1 Gbps network costs 20,000 ns, reading 1 MB sequentially from memory 250,000 ns, and a round trip within the same datacenter 500,000 ns. A disk seek costs 10,000,000 ns (10 ms), reading 1 MB sequentially from disk 20,000,000 ns (20 ms), and a packet going from California to the Netherlands and back 150,000,000 ns (150 ms). The value is in the differences between the rows. By simple division of the listed values, a disk seek costs about 100,000 times a main memory reference, and an intercontinental round trip costs about 300 times a round trip within the datacenter. Reading 1 MB sequentially from disk takes only twice as long as a single seek in this table, which shows why avoiding random accesses matters so much. These ratios guide decisions such as using an in-memory cache, keeping data close together, or batching work.
Back-of-the-envelope calculation in practice: the results page with 30 thumbnails
The talk shows how to use these numbers in a concrete estimate: how long does it take to generate an image results page with 30 thumbnails? The first design reads the images serially and generates thumbnails on the fly from 256 KB images. With a 10 ms seek and reads at 30 MB/s, the slide adds up 30 seeks of 10 ms plus 30 reads of 256 KB at 30 MB/s and arrives at about 560 ms. The second design issues the reads in parallel: the page waits for only one seek and one 256 KB read, which comes to about 18 ms. The slide adds a caveat: the calculation ignores variance, so the realistic value would be something like 30 to 60 ms. The slides also list variations to explore, such as caching (of individual images or of whole sets of thumbnails) and precomputing the thumbnails. Two lessons follow. First, a few minutes of arithmetic with the right costs separate two designs before any code exists: by dividing the slide's two totals (560 ms / 18 ms), the serial one comes out about 30 times slower in the estimate that ignores variance. Second, the estimate is only as good as your model of what the system does, and what was ignored must be stated. Capacity estimation follows the same recipe: list the operations, multiply by the costs, and say what you left out.
Designing for growth: 10X or 20X, not 100X
The slides carry a short, specific rule about scale. Try to anticipate how the requirements will evolve and keep the likely features in mind when designing the base system. Then make sure the design keeps working if the scale changes by 10X or 20X. The same slide carries the counterweight: the right solution for a scale X is often not ideal for 100X. One possible reading, which is ours and is not in the slides: a design sized for today's load but verified against a tenfold increase tends to survive growth for a good while, whereas designing for a hundred times pays a complexity cost now for demand that may never arrive. This ties into estimation: to check a design at 10X, you redo the math in your head with ten times more requests or data and see which resource runs out first, be it memory, disk seeks, or network. The slides also warn, under the infrastructure theme, against imagining unlikely needs that do not actually exist. Anticipating likely changes is encouraged; speculating about unlikely ones is the kind of over-engineering the talk advises against.
Lessons on infrastructure and low-latency applications
Two groups of advice in the slides deserve highlighting. The first is about building shared infrastructure: identify common problems and build software that solves them in a general way, but do not try to be everything to everyone. The slides illustrate this with customers who demand eight different things: serving six is easy, serving seven takes real thought, and trying to serve all eight usually results in a worse, more complex system that compromises the other customers. Do not build infrastructure for its own sake and do not imagine needs that do not exist. The suggested approach is to use the infrastructure yourself, especially early on, because that gives much faster feedback on what works. The second group is about interactive applications that require low latency. Aim for low average times, but the 90th and 99th percentiles are also very important, so worry about variance. Think about how much data you move: dozens of 1 MB RPCs per user request make latency bad. To tame the latency tail, the slides cite redundancy or timeouts; as general low-latency measures, they list judicious use of caching, higher priority for interactive requests, and parallelism. All of this ties back to the table of numbers, since every megabyte moved or extra round trip has a cost that can be added up.
See the ideas at work
Practice the designs that use this paper in the System Design school.