BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 2 · CH 8
System Design Interview Vol 2 · Ch 8 · Alex Xu & Sahn Lam · 2022
The mailbox you open every morning has to run a billion private mailboxes at once: take everything in, let you find any of it again, and look identical when you pick up a different phone. This chapter builds one of those from scratch.
The rules for moving mail around were written in the 1980s and have barely changed. Yet this is one of the heaviest chapters in the book — because the hard part was never "how do I get the letter there", it's "where do I put it once it lands, and how do I ever find it again". A mail service is not really a messaging system. It's an enormous warehouse.
Early mail servers were charmingly simple: one machine, and everybody's letters piled up in a folder on it. That falls over on every axis once the crowd arrives — a single day's incoming mail can fill a machine; when the machine dies, that whole group of people goes dark; and mail is essentially never deleted (lawyers and auditors want it kept), so the pile only grows.
There's a counter-intuitive part too. What actually strains the system isn't receiving mail — it's the little taps you don't think about. Marking something read, adding a label, dragging it to archive: every one of those is a write. Read forty letters a day and that's forty more writes.
1. One cubby per person. Mail has a luxury other systems envy: nobody ever looks inside someone else's mailbox. Every operation concerns exactly one person. So you cut the warehouse into one cubby per person, and every read and write touches only one cubby — which makes the whole category of "coordinate five machines to get one thing done" problems simply disappear.
2. Letters and parcels get stored apart. The text is light; the attachment is heavy. So attachments go to the big depot next door, and the cubby holds only a claim ticket. Flipping through your inbox then never has to drag the parcels along.
3. Everyone gets their own little catalogue. Searching mail and searching the web are different animals: web search is a billion people consulting one giant catalogue; mail search is a billion tiny catalogues, each serving one person. Yours is thin — which is exactly why a letter that landed a second ago is already findable.
4. The doorman only signs for it. When mail arrives you can't leave the courier standing outside: sign for it, drop it on the conveyor belt, and do the slow work — virus scan, spam filter, sorting — further down the line.
One letter actually gets written to three places: the cubby, the depot, and the catalogue. So deleting one means deleting three — and for a short while those three can disagree. You delete a message and search may still show a ghost of it for a moment.
The hard part of a mail service is storing and finding, not sending. Its great asset is that nobody reads anyone else's mailbox: cut the warehouse into one cubby per person and the expensive work collapses into single-cubby work. Heavy attachments move to the depot next door; catalogues are per-person. The cost is that one letter lives in three places and they briefly disagree.
Want the mechanisms, the notation and the diagrams? → Switch to Deep mode
On the surface this chapter builds a Gmail. In substance it is the cleanest partition key in the entire Xu series: the mail protocols froze forty years ago, and the whole engineering budget goes into a billion mutually irrelevant private mailboxes — and precisely because every query lands on exactly one person, the most expensive items in distributed systems (cross-partition transactions, global ordering, global indexes) never have to be bought. What the chapter really teaches is recognising that gift of a partition key and spending all of it.
Chapter 8 of Volume 2. It follows Ch7 (hotel reservations, contention over finite inventory) and leads into Ch9 (object storage). It opens the volume's "build the thing yourself" thread: this chapter spreads out the problem of metadata over huge numbers of tiny objects, and the next one dissects the storage layer that holds the attachments. Real-world counterparts: Gmail, Outlook, corporate mail gateways — and in fact any system where each user owns a private data space, such as file sync, notes, or a DM inbox.
Start with the book's assumptions: 1 billion users, each sending 10 and receiving 40 messages a day, body averaging 50KB, 20% carrying an attachment averaging 500KB.
10^9 × 10 / 86400 ≈ 116,000 messages/s. Receiving: 10^9 × 40 / 86400 ≈ 463,000 messages/s.10^9 × 40 × 50KB ≈ 2PB, attachments 10^9 × 40 × 20% × 500KB ≈ 4PB — about 6PB a day, and it essentially only grows.The traditional answer is a Maildir on one box, each user's mail sitting there as files. Against 6PB/day that breaks in three places at once: it doesn't fit (single-machine capacity), it can't be searched (full text means scanning files), and one dead machine takes a whole cohort offline (no replicas).
The subtler failure is write amplification in the flag bits. A body is written once and never touched again — but read/unread, labels and folder moves change constantly. On the assumptions above, "mark as read" alone is roughly 463,000 small updates per second globally, the same order as receiving mail itself. A mail service is not a read-mostly system, and that single fact rules out any storage engine tuned for read-mostly workloads.
Outward, you must speak SMTP: look up the recipient domain's MX record, open a connection, push the message. You cannot change this layer, and more importantly you do not control the far end — it may be down, rate-limiting you, or classifying you as spam and bouncing you.
That yields the first hard architectural constraint: outbound can never be synchronous. "Send" must return immediately, while actual delivery is a background job that may retry for hours or days. So outbound is a queue plus exponential backoff plus a dead-letter/bounce path.
Inward is a different story. POP3 is a relic of the single-device era; IMAP makes the server authoritative and syncs multiple devices; and what web and mobile clients actually use today is your own HTTPS API plus a WebSocket push channel — real IMAP is only needed when third-party clients such as Outlook or Apple Mail have to connect.
The book first characterises the data, then derives the choice from the character:
That last point is the hinge of the whole chapter. It means the consistency boundary can be drawn exactly around one user. Make the row key user_id — one user, one row — and every operation that needs atomicity (receiving a message, marking read, bulk-archiving) falls inside a single row. Nearly every wide-column store offers atomic single-row writes, so the most expensive item on the menu, the distributed transaction, is never ordered. Google's Megastore paper (CIDR 2011) uses a mail account as its canonical "entity group" example for exactly this reason: ACID inside the group, no guarantees across groups — mail is born that shape.
The column key buys a second free lunch. Compose it as folder:timestamp:message_id; wide-column stores keep columns sorted by key, so "give me the 20 most recent inbox messages" degenerates into one reverse range scan — no secondary index, no ORDER BY, no offset pagination.
A body is a few KB to a few tens of KB; an attachment starts in the hundreds of KB and runs to a 25MB ceiling (Gmail's published limit). Put attachment bytes inside the metadata row and the single most frequent operation — listing the inbox — has to drag hundreds of megabytes of irrelevant data along. So the book parks attachments in external object storage and keeps only a key in the metadata.
That hands you a neat bonus: content-hash deduplication. One message with a 10MB attachment sent to 100 people stores the bytes once and hands out 100 claim tickets — a 99% saving. The cost is that deletion stops being a single write and becomes a reference-counting and garbage-collection problem: the bytes cannot go until the last ticket does.
Large uploads also need multipart upload with resume: pushing 25MB in one PUT over a flaky mobile link fails often enough that only 5MB chunks with per-chunk retry are workable.
This is where intuition most often misleads. Mail search differs from web search on three axes:
Put the three together and the shard key has only one candidate: user_id again. One search hits one shard — no scatter-gather across thousands of shards, then merge. That is precisely why mail search can be tens of milliseconds without the cost exploding.
Search therefore reshapes the write path: an incoming message must be written to metadata, object storage and the index. Those three are not in one transaction, so the book's answer is asynchronous writes plus retries plus a periodic reconciliation sweep, accepting an inconsistency window measured in seconds. Treating search as a feature to bolt on later is the classic way to fail this question — it dictates the shape of the write path, it is not decoration on the read path.
Table 1 · Where metadata lives: three routes, the book takes the third
| Option | What it buys | What it costs (honestly) | When to pick it |
|---|---|---|---|
| Relational DB | Transactions, secondary indexes and SQL all free; entirely adequate for a mailbox with millions of users | At petabyte scale, sharding becomes the main body of work; full text either bolts on or crushes the primary; row width suits neither a mailbox of 300k columns | Under ~10M users with bounded per-user volume — don't over-engineer |
| Object storage only | Best capacity and cost; a natural fit for write-once bodies and attachments | Flipping one read flag rewrites the whole object; no range scan, no "newest N by time" | As the attachment tier and cold archive — never as the metadata tier |
| Wide-column NoSQL (the book's pick) | Row key = user_id partitions for free; column keys carry sort order; atomic single-row writes cover every transactional need; scales horizontally to PB | No cross-user query capability (not needed here); heavy operational burden; fat rows need a second level of splitting you build yourself | Billion-user scale where access is naturally isolated per person |
Table 2 · Search: buy it off the shelf, or grow it inside the store
| Option | What it buys | What it costs (honestly) | When to pick it |
|---|---|---|---|
| Elasticsearch and kin | Everything out of the box: tokenisation, relevance, aggregation, highlighting; a mature ecosystem you can ship on in weeks | A second storage and memory footprint of the same order as the data; operating a billion shards is brutal; a reindex is a multi-day project | Mid-sized user base, or when rich search features matter more than unit cost |
| Native index on the same LSM store | Indexing rides along with the write; no second system; best freshness; index shares shards and replicas with the data so they can't diverge | You implement tokenisation, merging and compaction yourself; far fewer features; only pays off at extreme scale | Billion users, cost-sensitive, and a team with real storage-engine capability |
Table 3 · How clients fetch mail: three sync models
| Protocol | Model | What it costs (honestly) | Its place today |
|---|---|---|---|
| POP3 | Download locally, delete on the server | Simply invalid with multiple devices: the phone takes it and the laptop never sees it | Kept alive only for very old clients |
| IMAP | Server is the truth; clients sync folders and flags | Stateful and complex to implement; the first sync of a large mailbox is expensive | Mandatory for Outlook / Apple Mail interop |
| HTTPS + WebSocket | Your own API: paged fetch plus real-time push for new mail | Works only for your own clients; third-party clients cannot connect | The main path for web and first-party apps |
What makes this question distinctive in an interview is that it is the one problem whose partition key is written into the prompt. The interviewer is not checking whether you can recite the SMTP handshake; they are watching whether you notice that "nobody reads anyone else's mailbox" buys out cross-partition transactions, global ordering and search fan-out in one move — and whether you then spend that dividend. Miss that layer and the whole question collapses into a pile of boxes and arrows.
1. A mail service is a storage-and-retrieval system, not a messaging one: the protocols have been frozen for forty years; all the work is in where things go and how they are found.
2. Scale: at 1B users, ~116K sends/s, ~463K receives/s, roughly 6PB of new storage a day, essentially append-only.
3. The real write pressure sits in read flags and labels, at the same order as arrival — which rules out read-optimised storage.
4. The hinge: nobody reads anyone else's mailbox. The consistency boundary lands on one user, the row key is user_id, and distributed transactions are never purchased.
5. Make the column key folder:timestamp:message_id and "newest 20" degenerates into a range scan — ordering becomes a by-product of layout.
6. Bodies and attachments separate: blobs go to object storage with content-hash dedup, metadata keeps a key; the cost is refcounting and GC on delete.
7. Mail search is not web search: a billion small indexes, time-ordered, findable within a second; the shard key is again user_id, so one query hits one shard.
8. One message lands in three stores (metadata / attachment / index), outside any single transaction, eventually consistent — search shapes the write path, it doesn't decorate the read path.
9. Selection: wide-column NoSQL beats both relational and pure object storage; search trades off between buying Elasticsearch and growing an index on the LSM store.
10. Two lessons paid for in incidents: replicas are not backups (2011 Gmail was recovered from tape), and spam defence is the main path, not an add-on (over 100M phishing mails blocked daily).