The System Design Method

1.1Four guesses

The sentence says what the service does and nothing about how much of it there will be, so the first job is to guess the amounts, out loud, and see what they imply. Four guesses are enough to start.

The first is how many people use it. We'll count daily active users, the number of different people who use the service on an ordinary day, and guess ten million. The second is how many messages each of them sends in a day: say forty. The third is how many bytes one stored message takes, counting its text plus the metadata kept with it, such as the sender, the time and the conversation: say two hundred. Multiplying the first two gives messages per day. Dividing that by the 86,400 seconds in a day gives messages per second, which is the write rate, because storing each new message is one write to the database.

Dividing by the whole day treats every second alike, but people aren't awake evenly, and a system has to survive its busiest moments and not just its average ones. So the fourth guess is the peak factor, how many times busier the busiest period is than the average. For a consumer chat app with an evening rush, three is a reasonable guess. Multiply the average write rate by it and you get the peak write rate, the one we'll compare with capacity.

Storage is the other number we want. Messages per day times bytes per message times 365 gives the bytes added in a year. We'll count a single copy for now. Later we'll add replicas, extra copies of the data on other machines, kept so that one dead disk doesn't lose anyone's messages.

1.2Trying it

The script below does exactly that sum. Each guess is a variable at the top with a comment marking it as an assumption, so anyone reading it can change one and rerun. 10_000_000 is Python's way of writing ten million, with _ marks that only help the eye, the :, inside the f-strings prints thousands separators, and dividing by 1e9, a billion, turns bytes into gigabytes. The qps in two variable names stands for queries per second, here the number of writes per second. Save it as est.py and run python3 est.py.

users_per_day   = 10_000_000          # assumption: daily active users
msgs_per_user   = 40                  # assumption: messages sent per user per day
bytes_per_msg   = 200                 # assumption: text plus metadata
peak_factor     = 3                   # assumption: busiest second vs the daily average
 
msgs_per_day = users_per_day * msgs_per_user
avg_qps      = msgs_per_day / 86_400
peak_qps     = avg_qps * peak_factor
per_year_gb  = msgs_per_day * bytes_per_msg * 365 / 1e9
 
print(f"messages per day  : {msgs_per_day:,}")
print(f"average writes/s  : {avg_qps:,.0f}")
print(f"peak writes/s     : {peak_qps:,.0f}")
print(f"storage per year  : {per_year_gb:,.0f} GB  (~{per_year_gb / 1000:.1f} TB, before replicas)")

messages per day  : 400,000,000
average writes/s  : 4,630
peak writes/s     : 13,889
storage per year  : 29,200 GB  (~29.2 TB, before replicas)

Read the output from the top. Ten million users sending forty messages each is 400 million messages a day. Spread over the day that's 4,630 writes a second, and at three times the average the peak is 13,889. The history grows by 29,200 GB a year, about 29.2 TB, for one copy.

1.3What the numbers already decide

Those four figures already rule some designs in and out, before anything is drawn. A few thousand writes a second is an ordinary load for one database server, and a few million is not (section 5 puts real numbers on that line), so we already know which side of it we're on. The 29 TB added every year keeps growing, so sooner or later it outgrows any single machine. Neither conclusion needed a diagram. Each is a comparison between a number we computed and a limit, and each says whether one machine is enough or something has to be added.

Hold on to that shape, because the rest of the chapter repeats it: a number, a limit, and a component added only when the number is above the limit.

1.4Say the assumptions out loud

You'll rarely be given every number, which is why we made guesses. A guess is fine as long as it's written down next to the estimate. "Assuming a 3× evening peak" is a design input that someone in a review can correct, while a silent assumption is a bug nobody can find.

Four guesses gave us load and storage. They said nothing about how fast a conversation must open, or whether a message may ever be lost, and those change a design as much as volume does.

2.1Two kinds of requirement

How fast a conversation must open, and whether a message may be lost, need numbers too. Requirements come in two kinds. Functional ones say what the system does: send a message, load a conversation, search history. Non-functional ones say how well it does it: how many users, how fast, how durable. Two services with the same functional list and different non-functional answers are different designs, so the second kind is the one to pin down.

2.2The questions that change the design

A few words first, because the questions use them. Latency is how long one request takes, from the moment it's sent to the moment the answer arrives. An average latency hides the slow requests, so targets are usually given as a percentile: p99 is the latency that 99 out of every 100 requests beat, which means the slowest one in a hundred takes longer. A system is durable if a message it has acknowledged is still there after a crash, which in practice means it reached a disk (Chapter 08 explains why that takes a deliberate flush). Consistency, here, asks what a reader sees right after a write, such as whether the sender sees their own message at once. Availability is the share of requests that get a proper answer, so 99.9% means one request in a thousand may fail.

Each of these becomes a question to ask before designing, and each answer changes something:

?Why ask about percentiles and not just "fast"?

Because the average hides the requests that make users leave. A p99 target says what the slowest 1% may take (the slowest requests are called the tail), and that decides whether a synchronous call to a slow dependency is allowed on the path. Chapter 16 shows how quickly the tail grows with load and fan-out.

Now we have the questions. Before we use them, one practical matter: the arithmetic in section 1 needed Python, and in a meeting or an interview nobody hands you a terminal.

3.1Conversions worth memorising

A few conversions carry most estimates, rounded so that the multiplication is easy. Request rates are often written QPS, queries per second, as in the script's variable names, so you'll see that name for what we've been calling requests per second.

Rounding a day to 10⁵ seconds makes every estimate about 14% too low, which is smaller than the error in any of our guesses, so it doesn't matter. Two shortcuts follow from the table. A million requests a day is about ten a second, and a billion is about ten thousand.

With the conversions and the questions in hand, we can redo section 1 properly, using a fuller set of requirements that also says how people read.

4.1The requirements

Here are the fuller requirements for the chat service. The numbers are assumptions, stated, so you can change any of them. A conversation is a thread of messages between a set of people, and opening one shows its most recent messages.

• 20 million daily active users.
• Each sends 40 messages a day, averaging 300 bytes with metadata.
• Each opens 100 conversations a day; opening one loads its last 50 messages.
• Messages are kept forever. An acknowledged message must never be lost.
• p99 under 200 ms to open a conversation. Evening peak is 3× the average.

4.2Requests, storage, bandwidth

Reads need one more decision, which is where the messages live. Let's assume the first design stores them in Postgres, a widely used relational database, with one row per message and an index next to the table: a sorted lookup structure that lets the database find the last 50 messages of one conversation without scanning the whole table. In a test table of one million rows, a message's row plus its index entry came to about 340 bytes, a little more than the 300 bytes of the message itself, and we'll use that for storage.

Read the table from the top. Twenty million users at forty messages is 800 million writes a day, which becomes 28,000 a second at peak. Each of the 20 million users opens a hundred conversations, so 2 billion loads a day, which becomes 69,000 a second at peak. The storage rows multiply the daily volume by the row size, then by 365, then by three for the replicas.

?Why did bandwidth show up as a big number?

Bandwidth is how many bytes per second move through a link. Every conversation load returns 50 messages, so 69,000 loads a second is 1 GB/s of payload leaving the storage tier, before protocol overhead. That's a reason to cache recent messages close to the app servers, return fewer messages per page, and compress responses. The request count alone would never have told you.

4.3Working set and connections

Two more estimates decide how big a cache is and how many connections the database needs.

The first is the working set, the part of the data that's touched often enough to be worth keeping in fast memory. Most conversation loads are of recent, active conversations. If a cache, a fast copy of recent data kept close to the app servers, holds the last 50 messages of every conversation active today, say 20 million conversations, that's 20M × 50 × 300 B = 300 GB. If a tenth of them take most of the reads, then 30 GB of cache memory covers the hot set. The cache could be Redis, a server that keeps values in memory and looks each one up by a name, its key, such as the conversation ID.

The second is how many database connections we need. Little's Law (Chapter 16) says that the number of requests in flight at once equals the arrival rate times the time each spends in the system. A database connection is busy for the whole query, so requests in flight is also the number of connections in use. At 69,000 reads a second and 0.2 ms per query, about 14 queries are in flight at once. If the database is struggling and each query takes 20 ms, it's 1,400, which is more connections than a Postgres node should hold. A connection pool, a fixed set of open connections that requests borrow in turn, has to be sized and given timeouts for the slow case and not the fast one.

We now have the numbers that matter: 28,000 writes a second, 69,000 reads a second, 1 GB/s of read traffic, 100 TB a year, and a 30 GB hot set. A number is only big or small compared with something, though, so we need to know what one machine can do.

5.1Latency: how long one operation takes

The classic reference is the table of approximate timings in Peter Norvig's Teach Yourself Programming in Ten Years, widely circulated as "latency numbers every programmer should know". Its figures are old, so the table below gives the same kinds of operations on current hardware, next to Norvig's.

A few rows need explaining. A loopback round trip sends one byte over TCP (the protocol under most network connections, HTTP included) to a program on the same machine and gets a reply, with no real network involved, so it shows the cost of the software alone. fsync and fdatasync ask the operating system to flush a file's data to the storage device, and F_FULLFSYNC is macOS's stronger request, which also makes the drive empty its own internal cache before answering. p50 is the median, the latency that half the requests beat.

A virtual machine (VM) is a computer simulated in software on a bigger one, and "Linux VM" here means a small one with four CPUs shared with other work. The "laptop SSD" row is a Mac's built-in drive. Each figure is the median of three runs, and all of them will differ on your hardware; what carries over is the size of the gaps between rows.

Look at the flush rows. Even the cheapest one is hundreds of times slower than a memory access, and the two flush rows differ from each other by a factor of 60.

?Why is the VM's flush 60 times faster than the laptop's?

Because they do different amounts of work. On macOS, plain fsync (about 20 µs in the same test) hands the data to the drive without making the drive empty its cache, while F_FULLFSYNC waits for that too, which is where the 3.9 ms goes. The VM's fdatasync lands in a virtual disk that is itself a file on the host machine, so the host may still be holding the data in memory when the VM is told it's done. Treat the 65 µs as a lower bound on what a flush can cost, with no promise that the data is safe. Real server SSDs with power-loss protection sit in between. Chapter 08 explains what fsync promises. For design, the lesson is to time the disk you'll run on before you size anything that commits on every request.

5.2Throughput: how much one node sustains

Latency tells us how long one operation takes. Throughput tells us how many a node completes per second, and that's what we compare with 28,000 writes and 69,000 reads. These are one small node's numbers, meant as orders of magnitude and not as benchmarks.

Here's how to read the rows below.

• A client is one connection that sends a request, waits for the answer, and sends the next.
• Rates are counted in operations per second (ops/s) or, for Postgres, transactions per second (tps).
• Pipelining means a Redis client sends sixteen commands before waiting for any answer, which saves most of the round trips.
• pgbench is Postgres's own benchmarking tool, and -S makes it run only the simplest read, a lookup of one row by its unique ID, the primary key.
• A normal commit makes Postgres record the change in its write-ahead log and flush that log to disk before confirming. Setting synchronous_commit = off skips the wait for the flush and confirms early, which risks losing the last moments of commits in a crash.
• Inserting in batches of 100 rows means one transaction and one commit for every hundred rows.
• "TPC-B-like" is a standard bank-account workload where every transaction updates one account, one teller and one branch row.

All of these come from the same Linux VM, with Postgres left at its default of 128 MB of memory for caching table pages (the shared_buffers setting), each figure the median of three runs of 10 to 15 seconds. "In RAM" means the whole table fits in memory, so no query waits for the disk.

The VM's cheap flush flatters every commit-per-row number. When several clients commit at the same moment, Postgres can cover all of their commits with one flush of the log, which is called group commit. On a disk where each flush takes milliseconds, group commit is what keeps commit-per-row throughput from collapsing, and the numbers above would be lower.

Now lay the chat service's peak writes against the node.

Single-row commits would leave one node nearly full at peak, and grouping the writes leaves it nearly empty.

The last row of the table looks wrong at first. A bank-account workload on the same node gets only 4,600 transactions a second, a tenth of what plain inserts reached.

?Why is the TPC-B-like number so much lower than plain inserts?

Because every TPC-B transaction updates one of only ten branches rows at scale 10, so the eight clients spend their time waiting on each other's row locks. That's the difference between a workload's raw cost and its contention, and designs fail on the second one. (The mechanics are in Chapter 13.)

5.3Distance

Some latency no engineering removes. Light in optical fibre travels at about two-thirds of its speed in a vacuum, roughly 200,000 km a second, which is about 1 ms of round trip per 100 km. A cloud provider splits its servers into regions, and each region into several availability zones, separate data centres that fail independently.

Real paths aren't great circles, so real round trips are longer, which makes these figures a floor. A design that makes three sequential Los Angeles to Tokyo calls on every request has spent at least 264 ms before any code runs, more than a 200 ms target allows.

5.4Which number breaks one machine first?

We can now compare each requirement from section 4 with one node.

So the numbers say something specific: writes need grouping, reads need help, and storage needs the data split up. Each of those is a different box, and the next question is which box answers which number.

6.1Each component answers a number

Start from the simplest design that could work: stateless app servers (servers that keep nothing between requests, so any of them can answer any request) in front of one database. Then add a component only when an estimate crosses a line.

The table pairs each common component with the situation that justifies it and the price you pay. Some of its terms are defined inside the cells.

?Why not add them all up front, to be safe?

Because each one is a new way to fail. A cache can serve stale data or fall over and send its entire load to the database at once. A queue can back up for hours without anyone noticing. Partitioning makes every query that crosses partitions slower and every migration harder. Complexity is a cost you pay on every deploy and every incident, so you pay it only for a number.

6.2How far one box goes

Simple designs go further than you'd expect. Nick Craver's Stack Overflow: The Architecture – 2016 Edition reported, for one day in February 2016, 209,420,973 HTTP requests to the load balancers and 504,816,843 SQL queries, served by 11 web servers, 4 SQL Servers in two clusters and 2 Redis servers. That's about 2,400 requests and 5,800 queries a second on average. Craver adds that they're "down to needing only 1 web server", with the caveat "I'm not saying it's a good idea."

6.3How the chat design grows

Now we can build the chat design one forced component at a time. Two terms first. The primary is the copy of a database that accepts writes, and a synchronous standby is a second copy that receives every change before the commit is confirmed, so it can take over if the primary dies. In the picture, each card at the database is a load from the estimate, and its colour says whether one node can carry it: amber means close to the limit, red means over it, and green means handled.

Each step has a number next to it, and each number came from section 4. A design review can challenge any step by challenging its number.

Step five split the data by conversation ID, and that choice was more than a detail: a different key would have made the most common query much more expensive.

7.1Choosing the partition key

Picking a key means asking which query runs most often, and we know it: opening a conversation, "the last 50 messages in this conversation", at 69,000 a second. Consider two ways to split conversation 7, which has three members, Ana, Ben and Cy, and four new messages. Option A picks the partition from the conversation ID. Option B picks it from the sender's user ID.

?Why partition by conversation and not by user?

Because the dominant query is "the last 50 messages in this conversation". Partitioning by conversation makes it a single-partition index lookup. By user, a group conversation's messages are scattered across the senders' partitions, and every load has to ask every partition. The partition key should be whatever the hottest query filters on. Chapter 29 covers how keys map to partitions and how data moves when you add one.

That settles the key for one query. The API has more than one, though, and the others don't filter on conversation.

7.2Write the queries next to the API

The API is the handful of calls clients can make. For each one, write down the query it runs and how often. For the chat system:

?Why does the third row need a separate index?

Because it's keyed by user, and the messages are partitioned by conversation. Any query that doesn't filter on the partition key has to ask every partition, or be served from a second structure keyed the way it reads. That's the general pattern: one copy of the data per access pattern that matters, kept in sync by the write path or by a stream of changes.

The third and fourth rows are small. A feed shows the same problem on a much larger scale, because every reader's feed is a query over many authors' content.

7.3Fan-out on write, or on read

The biggest access-pattern decision in feed-like systems is when to do the work of assembling what a user sees. A timeline is the list of recent posts from the accounts a user follows, and fan-out is one post being delivered to many readers' lists. Twitter's home timeline is the well-documented example. From Raffi Krikorian's Timelines at Scale talk (2013), as summarised by High Scalability: "300K QPS are spent reading timelines and only 6000 requests per second are spent on writes." With reads 50 times more frequent than writes, Twitter did the work at write time:

The summary gives the details. Each home timeline is capped at 800 entries in Redis, and fan-out aims to finish "under 5 seconds, but it doesn't always work, especially when celebrities tweet". The same page says it could take up to 5 minutes for a tweet to reach Lady Gaga's 31 million followers. For accounts like Taylor Swift's, the advice was to skip fan-out and "merge in her timeline at read time".

The boxes are drawn and the key is chosen. Two checks remain before the design is finished: whether the latency target is reachable, and what happens when each box misbehaves.

8.1Spend the latency budget

A p99 target is a latency budget, and every hop on the request path spends some of it. We'll walk one conversation load from a phone to the database and back. Two terms appear on the way. TLS is the handshake that encrypts a new connection, and it costs extra round trips. The edge is the first server, near the user, that terminates that connection.

?Why count sequential calls and not total calls?

Because parallel calls cost you the slowest one, while sequential calls cost you the sum. If three sequential calls each have a p99 of 20 ms, budgeting 60 ms for them is the safe assumption, since all three can be slow together. Three parallel calls cost about the slowest of the three, which is still a tail, but only one of them. Chapter 16 covers what fan-out does to the tail.

The cache sits on that path and answers most loads, so we should also ask what happens when it stops answering.

8.2Walk each box's failure

For each component, ask three questions: what if it's slow, what if it's down, and what if it's overloaded? Start with the cache, because it's the box whose failure surprises people most. Take 100 conversation loads a second (a round number, so the percentages are easy to read) and a cache that holds what 95 of them ask for. Watch the database behind it.

What the picture shows has a name, a cache stampede. A cache that absorbs most reads means the database behind it was sized for the few that get through. When the cache empties, after a restart or a failover, the database suddenly gets the full read rate. The defences in the last frame have names too. Coalescing misses means letting one request fetch a key while the rest wait for its answer. Load shedding means refusing some requests quickly so that the rest still finish. The third defence, sizing the database for a cold cache, is capacity planning. Timeouts, retry budgets and load shedding for moments like this are covered in Chapter 40.

?Why does the cache row matter so much?

Because a cache is a load reducer until it fails, and then it's a load multiplier. With a 95% hit rate the database sees 5% of the loads, and with an empty cache it sees all of them, twenty times as many. The same three questions apply to every other box. For the chat design:

Most real designs are finished in this walk, and not in the earlier steps. What remains is to write the design down so that someone else can challenge it.

9.1The method you just followed

A design that lives only in a whiteboard photo can't be reviewed. Before the document, here are the steps you took, in order, since each one answered the question the previous one left open.

Read top to bottom, the steps are a series of questions, each answered with a number, and each answer narrows what the next step can be. That's why every box in the chat design arrived with a number from section 4 attached to it.

9.2The design document

The document doesn't need to be long. It needs to show its reasoning:

1. Requirements, with every number and every assumption.
2. Estimates: peak QPS, storage per year, bandwidth, working set.
3. API and data model, with the query each call runs.
4. The design, with the "this is here because" sentence for each component.
5. Alternatives considered, and the number that ruled each one out.
6. Failure modes from section 8.2.
7. What you'll measure to know it's working: the SLIs (service level indicators, measurements such as the share of conversation loads under 200 ms), and the capacity metrics that tell you when the next step in section 6.3 is due. Chapter 39 covers how to collect them.

9.3Rules that hold up

1. Estimate before drawing, and write every assumption next to its number.
2. Estimate more than requests per second: storage per year, bytes per second, working set and requests in flight.
3. Multiply by a stated peak factor, and size pools and timeouts for the slow case.
4. Start with one service and one database, and add a component only when you can write "this is here because number exceeds limit".
5. Choose the partition key from the hottest query, and keep a second copy for each other important access pattern.
6. Put expensive work on the rarer side of the ratio.
7. Size the database for a cold cache, and coalesce misses.
8. Run your own query shape on the hardware you'll deploy before the design depends on someone else's throughput numbers.

9.4What you trade for what

9.5Symptom, cause, fix in design reviews