24 — Design A Distributed Email Service

Design an email service for a billion mailboxes: send, receive, store, and search mail. This is a storage and retrieval problem, not a messaging problem. One multiplier drives the design: a message is submitted once and delivered to several recipients.

This chapter covers how to:

• size the stored mail, and the search index over it, from first principles;
• explain why the same message body is stored once but the search index is built once per recipient;
• state what the SMTP protocol does and does not promise about delivery;
• design outbound sending against the reputation failures that take mail systems down.

What goes in and what comes out

Two inputs, two outputs.

Inbound. A raw message arrives from another mail server over the network. Out of it come three things: one stored copy of its bytes, one small row per recipient mailbox, and one batch of search-index entries per recipient. Only after all three are safely on disk does an acceptance code go back to the sender.

Outbound. A user submits a message through the API. Out of it comes a queued item per destination domain, retried for days. The eventual outcome arrives later as a separate inbound message, not as the response to the submission.

Two shapes follow. Inbound: one stored lump of bytes (a blob) with many small rows referring to it. Outbound: no immediate answer at all.

Why this is a storage problem

Email looks like a messaging problem. It is a storage and retrieval problem behind a delivery protocol.

Two numbers decide the architecture before anything else. First, the corpus (the complete body of stored mail) reaches exabytes if you keep one copy per recipient. Second, the search index over that corpus is the second-largest thing you own.

Two units get used constantly below. A petabyte (PB) is a million gigabytes. An exabyte (EB) is a billion gigabytes, which is a thousand petabytes.

Three places candidates lose this round

• They store a copy per recipient and never notice they have multiplied the corpus by the fanout — the average number of mailboxes one submitted message is delivered to.
• They reach for “we add Elasticsearch” (a popular open-source search engine) without sizing an index or asking whose messages are in it.
• They treat delivery status as something an API call returns. It is not. The protocol is store-and-forward: each server accepts the message, takes responsibility for it, and passes it on later, retrying for days. Failures come back out of band, as new mail, not as a response.

What this chapter borrows from elsewhere

Four outside results are used below. Each is restated in one line where it is used, so nothing here depends on reading them first.

• Chapter 02 — the estimation method, and the 86,400 -> 1e5 rounding. Treating a day as 100,000 seconds instead of 86,400 makes a per-second number a shift of the decimal point.
• Chapter 15 — blob storage, content addressing (naming stored bytes after a hash of themselves), and the privacy side channel that sharing one copy between users opens up.
• Chapter 20 — outbound queueing and retry behaviour.
• sql 03 — how much extra disk writing log-structured storage does as it reorganises itself, and how to choose the column that decides which server a row lives on.

1. Framing: what decision, and what breaks

The decision: where the fanout lands

A message submitted once is delivered to many mailboxes. Every subsystem in the design either pays that multiplier or dodges it.

Storage dodges it. One blob — a single opaque lump of bytes stored under a name, with no structure the storage system understands — with many references pointing at it.

The search index does not dodge it. That is a deliberate choice, and section 8 derives its price exactly.

The four properties, and what each costs

Each guarantee the service makes forces machinery to be built. The right-hand column lists the subsystems it obligates.

Four terms in that table are used throughout the chapter.

• 250 is the SMTP success code: the receiving server saying “I have this message and I take responsibility for it”. That is why durability has to be achieved before it is sent.
• Content addressing means naming a stored object by a hash of its own bytes. Identical content then automatically shares one name and one copy, with no coordination.
• Reference counting and a garbage collector are how you learn that the last mailbox pointing at a blob has gone away and the bytes may be reclaimed.
• Deliverability is the fraction of your mail that reaches an inbox rather than a spam folder. Other companies decide it, by scoring your sending behaviour, which is why section 12 treats reputation as a subsystem rather than a footnote.

The sentence that contains the design

State the core design in one sentence: “the same message body is stored once and referenced by every recipient, but the search index is per-user, so I pay the fanout exactly once and I choose where.”

Section 8 is the arithmetic that proves it.

Three things that break in production

Each of these gets its own section later.

• A mailing-list blast. One submission turns into a million mailbox rows and a million index updates (section 14).
• A compromised account. It sends spam from a shared outbound IP address, and every other customer’s mail on that address starts landing in junk folders (section 12).
• A large receiving provider goes down. The outbound queue grows for four days, not because of a bug, but because four days of retrying is what the protocol asks for (section 10).

2. Requirements

SMTP is the Simple Mail Transfer Protocol, the language mail servers speak to each other; a server that speaks it is a mail transfer agent (MTA). Both terms run through everything below.

Functional

• Receive mail over SMTP from the internet; accept, defer, or reject.
• Send mail: authenticated submission, queueing, retry, and bounce handling.
• Read: list a mailbox by label, read a message, download attachments.
• Search a user’s own mail by keyword, sender, date, and label.
• Label, star, mark read, archive, delete; sync those across devices.
• Classify spam and enforce sending reputation.

Three things are out of scope, and it is worth stating so in the interview.

• Calendaring and contacts. Separate products that happen to share a login.
• End-to-end encryption, where only the two humans hold the keys. Excluded from the main design because it destroys deduplication; section 15 prices exactly that.
• The mail client that renders the message. Its own product.

Non-functional — the constraints that pick the architecture

Each target forces a specific mechanism later in the chapter. The right-hand column says where the number comes from, not just what it is.

Some shorthand from that table, in plain words.

• p99 is the ninety-ninth percentile: the figure 99 out of 100 requests come in under. It describes the slow tail users complain about. An average hides that tail, which is why nobody quotes one.
• Eventually consistent means the different parts of the system are allowed to disagree for a while, but converge on the same answer if you stop changing things.
• Immutability means the stored bytes are never edited in place. Anything a user changes lives somewhere else.

The consistency contract, stated precisely: a user must never see a message vanish, and must never see one they were told arrived fail to be searchable within seconds. Everything else — counts, label totals, thread ordering during a rebuild — may lag.

Section 13 turns that into a table with a mechanism against every row.

3. Back of the envelope

A back-of-the-envelope estimate is a deliberately rough calculation in round numbers, done to settle an argument rather than to be precise. Three follow: how much mail flows, how much of it you actually have to store, and what that costs in physical disk. Each one rules out a class of wrong answer, and the first produces the number the rest of the chapter keeps returning to.

3a. Flow

The estimate has to produce the delivery rate, the submission rate, and above all the ratio between them.

Two terms first. QPS means queries per second — how many operations of that kind the system handles each second. Daily actives are the users who open the product on a given day; there are far fewer of them than there are accounts, because most accounts are dormant.

The block below starts with the assumptions, and the line to watch is average in-system fanout.

assume  1 B mailboxes, 300 M daily actives, 30 messages received and 5 sent
        per active per day, 10 KB of headers and body, 20% carry an
        attachment averaging 300 KB, peak = 3x average

messages delivered per day
  300,000,000 x 30                       =  9,000,000,000
messages submitted per day
  300,000,000 x 5                        =  1,500,000,000
average in-system fanout
  9,000,000,000 / 1,500,000,000          =  6
delivery QPS, at 86,400 -> 1e5
  9,000,000,000 / 100,000                =  90,000
peak delivery QPS
  90,000 x 3                             =  270,000
submission QPS
  1,500,000,000 / 100,000                =  15,000
bytes per message
  10,000 + 0.20 x 300,000                =  70,000

Two lines in that block deserve a second look.

Bytes per message is a weighted average, not a typical message: 10,000 bytes of headers and body always, plus a 300,000-byte attachment on 20% of messages, so 10,000 + 0.20 x 300,000 = 70,000 bytes. No individual message is 70 KB. Most are 10 KB and one in five is 310 KB.

Average in-system fanout is 9 billion deliveries per day divided by 1.5 billion submissions per day, which is 6. The word in-system matters: it counts only mailboxes you host, because those are the only copies you would have to store.

Every submitted message becomes six delivered messages. That ratio drives the storage saving in section 3b, the index cost in section 8, and the mailing-list failure mode in section 14. It is the central number in this chapter.

3b. Storage, and what dedup is worth

This estimate prices the central design decision.

Deduplication, or dedup, means storing one copy of identical content and pointing every user at it, instead of keeping a copy each. It applies here at two levels — whole messages, and individual attachment parts — and the two savings multiply.

The block below runs in four steps: what one copy per recipient would cost, what one copy per submission costs instead, what the second dedup stage (identical attachments) removes on top, and then both figures extended over five years of retention.

one copy per recipient, bytes per day
  9,000,000,000 x 70,000                 =  630,000,000,000,000
one copy per submitted message, bytes per day
  1,500,000,000 x 70,000                 =  105,000,000,000,000
saved per day by message-level dedup, in bytes
  630,000,000,000,000 - 105,000,000,000,000  =  525,000,000,000,000
saved, as a fraction
  525,000,000,000,000 / 630,000,000,000,000  =  0.833
attachment bytes inside the unique stream, per day
  1,500,000,000 x 0.20 x 300,000         =  90,000,000,000,000
content-hash duplicates among them, at 30%
  90,000,000,000,000 x 0.30              =  27,000,000,000,000
stored per day after both dedup stages
  105,000,000,000,000 - 27,000,000,000,000  =  78,000,000,000,000
naive corpus over 5 years, in bytes
  630,000,000,000,000 x 365 x 5          =  1,149,750,000,000,000,000
deduplicated corpus over 5 years, in bytes
  78,000,000,000,000 x 365 x 5           =  142,350,000,000,000,000

Those are raw byte counts, so translate the zeros before quoting them. 630,000,000,000,000 bytes is 630 terabytes (a terabyte is a trillion bytes, and there are 1,000 of them in a petabyte). 105,000,000,000,000 is 105 TB. 78,000,000,000,000 is 78 TB. And 1,149,750,000,000,000,000 bytes is 1.15 EB, against 142,350,000,000,000,000 = 142 PB.

Message-level dedup saves 525 TB a day, 83.3% of everything written, by storing each message once instead of once per recipient. The saving is exactly the fanout, by construction: dividing the corpus by 6 removes 5/6 of it, and 5/6 is 0.833.

Over five years that is 1.15 EB naive against 142 PB deduplicated.

The extreme case makes it intuitive. Take a single message sent to a thousand people:

a 70 KB message to 1,000 recipients, one copy each, in bytes
  1,000 x 70,000                         =  70,000,000
the same message stored once and referenced, saved in bytes
  70,000,000 - 70,000                    =  69,930,000
as a fraction
  69,930,000 / 70,000,000                =  0.999

One message to a thousand recipients is 99.9% redundant. The mean fanout of 6 gives 83%. The tail is where per-recipient storage becomes indefensible.

What dedup does not collapse

Sharing one copy of the bytes does nothing for per-recipient state: whether this user has read it, which labels they filed it under, whether they deleted it, and where it sits in their view of the conversation. Those differ per user by definition.

That state is the metadata tier — the small mutable rows describing one user’s relationship to a message, as opposed to the large immutable bytes of the message itself.

The block below adds up one such row field by field, then scales it to the whole fleet. The last two lines show that metadata is about 1% of what you write and 100% of what a user can change.

mailbox row: user_id 8 + message_id 16 + thread_id 8 + received_at 8
             + flags 4 + labels 8 + blob_ref 32 + index and row overhead 40
  8 + 16 + 8 + 8 + 4 + 8 + 32 + 40       =  124
mailbox metadata per day, in bytes
  9,000,000,000 x 124                    =  1,116,000,000,000
as a fraction of the unique content written per day
  1,116,000,000,000 / 105,000,000,000,000  =  0.0106
metadata over 5 years, in bytes
  1,116,000,000,000 x 365 x 5            =  2,036,700,000,000,000

That is 2 PB of metadata against 142 PB of content: 1.06% of the write volume and 100% of the per-user semantics.

That split is what makes the two-tier design work. The blob tier can be immutable, eventually consistent and cheap. The metadata tier is mutable, strongly consistent, and sharded on user_id — split across many database servers, with the user’s identity deciding which server holds their rows, so every query about one user touches exactly one machine.

3c. Physical layout

Logical bytes are not disk bytes. You store more than you keep, because you store redundantly. This estimate converts logical bytes into physical ones.

Two more terms first.

• A replica is one complete copy of the data on a different machine. Three replicas is the normal way to survive disk and machine failures, and it costs three times the size.
• Erasure coding instead stores the data along with recovery information spread across machines, surviving comparable failures at roughly 1.4 times its size. The price is slower reads — reconstructing a lost piece means fetching from several machines. That is why erasure coding is used for the cold tail and replication for recent mail.

The block below splits the corpus into a hot tier (the last 30 days, replicated 3x) and a cold tier (everything older, erasure coded at 1.4x), then compares the total against the naive design.

hot tier: 30 days of stored bytes
  78,000,000,000,000 x 30                =  2,340,000,000,000,000
hot tier at 3 replicas
  2,340,000,000,000,000 x 3              =  7,020,000,000,000,000
cold tier, in bytes
  142,350,000,000,000,000 - 2,340,000,000,000,000  =  140,010,000,000,000,000
cold tier erasure coded at 1.4x
  140,010,000,000,000,000 x 1.4          =  196,014,000,000,000,000
physical total, in bytes
  7,020,000,000,000,000 + 196,014,000,000,000,000  =  203,034,000,000,000,000
the naive corpus at 3 replicas throughout
  1,149,750,000,000,000,000 x 3          =  3,449,250,000,000,000,000
saving factor
  3,449,250,000,000,000,000 / 203,034,000,000,000,000  =  16.99

Dedup and tiering together are a 17x reduction: 3.45 EB of disk becomes 203 PB.

Neither one alone gets there. They are independent factors, so they multiply. This block separates them so you can quote either half:

dedup, on the logical corpus
  1,149,750,000,000,000,000 / 142,350,000,000,000,000  =  8.077
the deduplicated corpus at 3 replicas throughout, in bytes
  142,350,000,000,000,000 x 3            =  427,050,000,000,000,000
storage policy, on top of dedup
  427,050,000,000,000,000 / 203,034,000,000,000,000  =  2.103
product
  8.077 x 2.103                          =  16.99

That is 8.08x from dedup, 2.10x from the storage policy, and 8.08 x 2.10 = 17. Quote whichever half the interviewer pushes on.

A sanity check on one mailbox

Big aggregate numbers are easy to get wrong by a factor of a thousand without noticing. The cheapest defence is to divide back down to one user, where you have intuition. One active mailbox receives 30 messages a day for 5 years, which is 54,750 messages at 70,000 bytes each:

one mailbox after 5 years, logical, in bytes
  54,750 x 70,000                        =  3,832,500,000

That is 3.83 GB per active mailbox against a typical 15 GB quota. The quota binds almost nobody, which matches reality, and it is design-relevant: enforcing quotas is a billing feature, not a capacity mechanism.

3d. Assumption ledger

Every number above rests on an assumption. The difference between an estimate and a guess is whether those assumptions are on the table.

Sort each one into three buckets:

• State it — say it, move on, nobody will argue.
• Ask it — the answer changes the design, so get it from the interviewer.
• Load-bearing — if this is wrong by an order of magnitude, a conclusion in this chapter falls over.

The ledger is what lets you say, later in the interview, “that follows from the fanout of 6; if the real fanout is 2, the per-user index costs a third as much and the argument gets easier, not harder”.

The three to actually ask about are retention, the spam share, and the outbound IP count, because all three are numbers the business already has and all three change a decision rather than a digit.

4. API sketch

The two interfaces serve different callers. The SMTP surface is machine-to-machine: other organisations’ mail servers speak it to hand you mail. The HTTP surface is what the user’s own mail client calls to read, search and send.

One piece of SMTP vocabulary before the block: MAIL FROM, RCPT TO and DATA are the three commands of an SMTP conversation, carrying the sender, each recipient, and the message bytes, in that order.

The first two lines below are the SMTP side; everything after the blank line is the HTTP side, written as METHOD path -> response shape.

SMTP  25   inbound   MAIL FROM / RCPT TO / DATA -> 250 only after the blob and
                     every recipient's mailbox row are durable
SMTP  587  submission  authenticated, per-account rate limited, DKIM signed here

GET  /v1/mailbox/{label}?cursor=&limit=50 -> [{message_id, thread_id, snippet,
                                               from, received_at, flags}], cursor
GET  /v1/messages/{message_id}            -> headers, body, part manifest
GET  /v1/parts/{content_hash}             -> 302 to a signed, expiring blob URL
POST /v1/messages:send                    Idempotency-Key: ...
       {"to": [...], "subject": "...", "body": "...", "parts": [content_hash]}
POST /v1/messages/{message_id}:modify     {"addLabels": [...], "removeLabels": [...]}
GET  /v1/search?q=&cursor=                -> this user's index only, never global
GET  /v1/history?since=                   -> the per-user change journal

Two ports appear there and they do different jobs.

Port 25 accepts mail from the rest of the internet. Anyone may connect, so it has to assume every caller is hostile.

Port 587 is the submission port, where your own authenticated users hand you mail to send on their behalf. Only this port signs outgoing mail with DKIM — a cryptographic signature over the message that lets any receiver verify it really came from your domain and was not altered in transit.

Four choices in that sketch carry weight.

• 250 is returned after durability, never before. SMTP is store-and-forward: the moment you answer 250 the sending server is entitled to delete its copy. That response is the only durability contract in the protocol, and there is no way to take it back.
• Attachments are fetched by content hash, not by message id. The same 2 MB slide deck attached to a message that was forwarded to you is the same bytes. Naming it by a hash of its content makes the cache, the content delivery network (the geographically distributed copies that serve users from nearby) and the dedup index agree with each other with no coordination.
• Search takes no user parameter. The caller’s identity selects which index is read. A search API that accepts a mailbox id as an argument is one authorization bug away from leaking one account’s mail to another; section 8 turns that from a check the code must remember into a property of how the data is partitioned.
• :modify sends a list of labels to add and remove, not a rewritten message. Bodies never change; everything a user can change lives in the small mailbox row.

Sending carries an idempotency key for the same reason a hotel booking does (ch 23): an idempotency key is a client-chosen string that lets the server recognise a retry of the same intent, and without it a retried submission sends the mail twice, which the recipient sees and which nothing can undo.

5. Data model

Three decisions inside the schema hold up the rest of the design: what is sharded and what is not, why blob references are not counted transactionally, and why a user’s search index is stored as ordinary rows.

The sketch below is not runnable SQL; it is a column list per table with the interesting constraints written as comments. Read it top to bottom as “one row per user per message, one record per distinct message, one record per distinct attachment, then four supporting tables”.

mailbox                                   -- sharded on user_id
  user_id BIGINT, msg_seq BIGINT,         -- PK (user_id, msg_seq), monotonic
  message_id BYTEA(16), thread_id BIGINT,
  blob_ref BYTEA(32),                     -- content hash of the immutable message
  received_at TIMESTAMP, flags SMALLINT, labels BIGINT

messages                                  -- global, content-addressed, immutable
  message_id PK, envelope, header_blob, body_blob,
  part_manifest,                          -- [(content_hash, size, mime, filename)]
  recipient_count INT, first_seen

parts     content_hash BYTEA(32) PK, size BIGINT, mime_type, blob_locator, first_seen
segments  user_id, segment_id, min_seq, max_seq, dict_offset, postings_locator
history   user_id, seq BIGINT, op, message_id     -- the device sync journal
outbound  destination_domain, next_attempt_at, attempt_count, message_id, status
repute    ip_or_domain PK, class, score_1h, score_24h, complaint_rate

Seven tables, one line each:

• mailbox — one row per user per message. This is the metadata tier from section 3b: the 124 bytes that say what this user thinks about the message. msg_seq is a per-user counter that increases with every new message, which gives cheap ordering and cheap paging without sorting by timestamp.
• messages — one record per distinct message, shared by all its recipients. envelope is the SMTP-level sender and recipient list, as distinct from the From: and To: headers a human sees, which can say anything.
• parts — one record per distinct attachment, keyed by the hash of its bytes. blob_locator says which storage bucket and object actually holds them.
• segments — the per-user search index, in chunks. min_seq/max_seq say which range of that user’s messages a chunk covers; dict_offset and postings_locator point into the term dictionary and the posting lists inside it (section 8 defines those).
• history — a numbered log of every change to a user’s mailbox. A device that has been offline sends the last seq it saw and replays forward.
• outbound — the send queue, one row per message per destination domain, with the next retry time and how many attempts have been made (section 10).
• repute — reputation scores for the IP addresses and domains you send from and receive from, over a 1-hour and a 24-hour window (section 12).

Three decisions in that schema are worth defending out loud, because the rest of the design rests on them.

mailbox is sharded on user_id and nothing else is. Every query a user makes — list a label, page through a thread, search, sync a device — is about one user, so a read of one shard answers all of them. The messages and parts tables are keyed by content hash instead, which has no locality and no useful ordering, so nobody ever asks for “the next hundred messages by hash”. That is exactly the lookup-by-key pattern of ch 06, and those tables are partitioned by hashing the content hash itself.

blob_ref is a reference, not a foreign key with a count attached. Keeping an exact count of how many mailboxes point at a blob, across two stores sharded on different keys, needs a transaction spanning both, and the failure mode of getting that wrong is deleting data that is still live. The correct trade is mark-and-sweep with a grace period: a background pass marks which blobs are still referenced, sweeps away the rest, and waits long enough that a blob written seconds ago is never mistaken for an orphan. It is derived in ch 15 and used here as-is.

A user’s search index is rows in a table, not a separate search service. The index is stored as segments — chunks of index written once and never edited — addressed by (user_id, segment_id), so rebuilding an index, deleting a message, or closing an account is a row operation confined to one shard rather than a rewrite of a structure shared with everybody else. Section 8 is the whole argument.

6. High-level architecture

Every component on one page. Every claim carries the number of the section that proves it.

The diagram has three separate flows, best traced one at a time. Top to bottom on the left is the inbound path, from the internet down into storage. The middle branch is the read path, from clients to the Read API. The bottom branch is the outbound path, from clients back out to the internet. Cylinders are stored data; rectangles are services.

flowchart TB
    NET(["internet MTAs"]) --> GATE["Connection gate<br/>IP reputation, RBL, rate<br/>rejects before DATA"]
    GATE --> RX["SMTP receiver<br/>parse, DKIM verify"]
    RX --> FILT["Spam + policy<br/>content model"]
    FILT --> DEL["Delivery service<br/>fanout to recipients"]
    DEL --> BLOB[("Blob store<br/>content addressed<br/>hot 3x, cold EC 1.4x")]
    DEL --> MBX[("Mailbox metadata<br/>sharded on user_id")]
    DEL --> IDX["Index builder<br/>per-user segments"]
    IDX --> SEG[("Index segments<br/>co-sharded with mailbox")]
    MBX --> JRN[("History journal<br/>per-user seq")]

    APP(["clients"]) --> API["Read API"]
    API --> MBX
    API --> SEG
    API --> BLOB
    JRN --> API

    APP --> SUB["Submission 587<br/>authN, per-account limit, DKIM sign"]
    SUB --> OQ[["Outbound queue<br/>per destination domain<br/>ch 20"]]
    OQ --> POOL["MTA pool<br/>segmented IPs by sender class"]
    POOL --> NET
    POOL --> BNC["Bounce + DSN processor"]
    BNC --> OQ

    style BLOB fill:#2d6a4f,color:#fff
    style MBX fill:#1d3557,color:#fff
    style GATE fill:#9d0208,color:#fff
    style POOL fill:#bc6c25,color:#fff

The inbound path, box by box

1. Internet MTAs — other organisations’ mail servers — open a connection to you.
2. Connection gate. Scores the sending address against your own reputation data and public blocklists, historically called realtime blackhole lists (RBLs). It hangs up before the message bytes are ever transferred, which is the cheapest rejection available.
3. SMTP receiver. Parses what survived, and performs a DKIM verify — checking the cryptographic signature that ties the message to a domain.
4. Spam and policy. Runs a content model over what is left. This is the expensive layer, which is why so much was thrown away before it.
5. Delivery service. Does the fanout to recipients: one write to the blob store, and one row per recipient in the mailbox metadata.
6. Blob store. Content addressed, kept hot at three replicas and cold at 1.4x erasure coding.
7. Mailbox metadata. Sharded on user_id.
8. Index builder. Produces per-user index segments, which are co-sharded with the mailbox: a user’s index rows live on the same machine as their mailbox rows, so a search is one machine’s work.
9. History journal. Every change is appended to a per-user numbered log that devices replay to catch up.

The read and outbound paths

On the read side, clients talk to a Read API that reads four things and nothing else: the mailbox rows, the index segments, the blobs, and the journal.

On the send side, clients submit through port 587, which authenticates the account, applies a per-account rate limit, and signs the message with DKIM.

Submissions land in an outbound queue partitioned per destination domain (ch 20). That queue feeds the MTA pool, whose IP addresses are segmented by sender class.

The bounce and DSN processor handles failure reports that come back, and re-queues or suppresses accordingly. A DSN is a delivery status notification: the machine-readable “this did not arrive” message, which arrives as ordinary inbound mail.

The four claims this picture makes

Each has a section behind it.

• One blob and many mailbox rows (section 7).
• The index builder fans out per recipient, and that is deliberate (section 8).
• The connection gate rejects most spam before a byte of DATA is read (section 11).
• The outbound pool is segmented by sender class, because IP reputation is collateral shared between customers (section 12).

The arrow that does not exist is a synchronous one from the outbound pool back to the submitting client. Delivery takes anywhere between milliseconds and four days, so the send API returns “queued” and the real outcome arrives later, through the bounce processor.

7. Deep dive 1: one blob, many mailboxes

The inbound write path has three load-bearing properties: the order of the writes, why a repeated delivery is harmless, and when the sender may finally be told yes.

Delivery is a fanout over a single immutable object. The bytes are written once, and then one small row is written per recipient.

Read the code below as one sentence: one blob write, N metadata writes, N index appends, and then — only then — the 250. parse_parts, thread_of, inbox_label and nextval_for are stand-ins for machinery that does not matter here; what matters is the order the four steps happen in.

import hashlib

def deliver(blob_store, db, index, raw: bytes, recipients: list[int]) -> None:
    """One blob write, N metadata writes, N index appends.
    Blob first, metadata last -- the mailbox row is the linearization point."""
    message_id = hashlib.sha256(raw).digest()[:16]
    body_hash = hashlib.sha256(raw).hexdigest()

    if not blob_store.exists(body_hash):              # idempotent by construction
        blob_store.put(body_hash, raw)                # a retry rewrites the same bytes

    for part in parse_parts(raw):                     # attachments split out here
        if not blob_store.exists(part.content_hash):
            blob_store.put(part.content_hash, part.data)

    with db.transaction():                            # one shard per recipient batch
        for user_id in recipients:
            db.execute(
                "INSERT INTO mailbox (user_id, msg_seq, message_id, blob_ref, "
                "  thread_id, received_at, flags, labels) "
                "VALUES (%s, nextval_for(%s), %s, %s, %s, now(), 0, %s) "
                "ON CONFLICT (user_id, message_id) DO NOTHING",
                (user_id, user_id, message_id, body_hash,
                 thread_of(raw, user_id), inbox_label()))
    for user_id in recipients:
        index.append(user_id, message_id, terms_of(raw))   # section 8
    # only now may the SMTP session answer 250

Three properties are load-bearing.

Blob first, metadata last

The comment in the code calls the mailbox row the linearization point: the single instant at which the message becomes real for that user. Before that row commits, nobody can see the message. After it commits, everybody does. There is no in-between state to reason about.

Both orderings of the two writes have a failure mode. You do not get to avoid one; you get to choose which one you suffer.

• Metadata first, then a crash. A mailbox row points at bytes that are not there. The user sees a message that will not open — a visible, unfixable defect.
• Blob first, then a crash. An orphaned blob: bytes with nothing pointing at them. It costs storage until the sweep reclaims it, and no user ever notices.

Writing the blob first makes the survivable failure the one that actually happens.

ON CONFLICT DO NOTHING on (user_id, message_id)

Repeated deliveries are completely ordinary in this protocol. If the 250 is lost on the wire, the sending server rightly assumes failure and delivers the identical message again.

So delivery must be idempotent — safe to repeat, producing the same end state. The way to get that here is to key the mailbox row on a hash of the message’s own bytes, and let the database quietly discard the second insert.

This is the same trick as content-addressed uploads: the name is the content, so a retry is a no-op rather than a duplicate.

The 250 comes after both

Answering earlier turns any crash into permanent data loss — for a message whose sender has already deleted its only other copy on the strength of your 250.

Deletion inverts cleanly

Removing the mailbox row is immediate and visible to the user. The blob survives until no row references it and the sweep runs.

A user deleting a message must never be able to delete another user’s copy. Content addressing makes that impossible by construction, rather than by a permission check somebody has to remember to write.

8. Deep dive 2: search, and why the index is per user

Search decides the second-largest system you own. Sizing the index from first principles shows that building one per user — paying the fanout a second time — is worth it, on three grounds: query cost, privacy, and deletion.

Start with vocabulary, because none of the arithmetic makes sense without it.

• An inverted index is the data structure behind every search engine. A normal index maps each document to its words. An inverted index maps each word to the list of documents containing it, so answering a query is a list lookup rather than a scan of every message.
• Each entry in one of those lists is a posting — one “word W appears in document D” fact.
• Delta encoding stores the gaps between consecutive document numbers rather than the numbers themselves. A list like [1004, 1009, 1021] becomes [1004, 5, 12], and small numbers compress into fewer bytes. That is why a posting costs about two bytes instead of six.
• A positional index additionally records where in the document each word occurred. That is what makes exact phrase search possible, and it is why it costs several times more: you store one entry per occurrence instead of one per distinct word.
• Heaps’ law is the empirical observation that the number of distinct words in a text grows roughly as the square root of its length. A message ten times longer has only about three times as many different words, because common words repeat.

How big is an inverted index, really

The first question is what an index actually costs as a fraction of the text it covers. The common answer is “about 30%”, which holds only for a positional index, which this design does not use.

The block below sizes one message twice: once without positions, once with. Compare the two fractions at the end.

assume  1,500 words of text per message after markup stripping,
        distinct terms by Heaps' law V = 10 x n^0.5,
        2 B per delta-encoded posting inside a per-user index

distinct terms in one message
  10 x 1,500 ^ 0.5                       =  387
index bytes for one message, non-positional
  387 x 2                                =  774
as a fraction of the 10,000 B of text
  774 / 10,000                           =  0.0774
positional postings store every occurrence instead of every term
  1,500 x 2                              =  3,000
as a fraction of the text
  3,000 / 10,000                         =  0.30
positional over non-positional
  3,000 / 774                            =  3.88

In words: 1,500 words of text produce 387 distinct terms, each costing 2 bytes, so 774 bytes of index for 10,000 bytes of text — 7.7%. Add positions and you store one posting per occurrence instead of per distinct term, which is 1,500 x 2 = 3,000 bytes, or 30% of the text and 3.9 times as much index.

Why the postings are only two bytes

The postings are small because a per-user document number is small. One mailbox holds 54,750 messages over five years, which fits in 16 bits (2^16 = 65,536), and delta encoding inside a sorted list brings the average below two bytes.

A global index would need a document number spanning 16.4 trillion messages — 9 billion deliveries a day for 1,825 days — which is 44 bits before any compression. That is where the “indexes are 30% of the corpus” folklore comes from.

The choice of what a document number refers to is what sets the index’s size, and it is made long before any tuning.

Now scale one message up to one mailbox, and one mailbox up to the fleet. The dictionary line is new: on top of the posting lists you store the list of distinct words themselves, at about 20 bytes per term.

messages in one mailbox over 5 years
  30 x 365 x 5                           =  54,750
postings storage per user, in bytes
  54,750 x 774                           =  42,376,500
distinct terms across the whole mailbox
  10 x (54,750 x 1,500) ^ 0.5            =  90,623
term dictionary at 20 B per term, in bytes
  90,623 x 20                            =  1,812,460
per-user index, in bytes
  42,376,500 + 1,812,460                 =  44,188,960
per-user text, in bytes
  54,750 x 10,000                        =  547,500,000
index as a fraction of the text it covers
  44,188,960 / 547,500,000               =  0.0807
fleet index across 300 M active mailboxes, in bytes
  300,000,000 x 44,188,960               =  13,256,688,000,000,000
fleet text indexed, in bytes
  300,000,000 x 547,500,000              =  164,250,000,000,000,000

That is 44 MB of index per mailbox, 8.1% of the text it covers, 13.3 PB across the fleet.

(The per-mailbox fraction is 8.1% rather than the per-message 7.7% because the term dictionary is added on top. The dictionary grows as a square root, so it gets relatively cheaper as a mailbox fills.)

Adding positions for phrase search costs 3.88x on the postings and takes the whole index to 30% of the text:

positional index per user, in bytes
  54,750 x 3,000 + 1,812,460             =  166,062,460
fleet positional index, in bytes
  300,000,000 x 166,062,460              =  49,818,738,000,000,000
extra storage over non-positional, in bytes
  49,818,738,000,000,000 - 13,256,688,000,000,000  =  36,562,050,000,000,000

That is a real decision rather than a default. Stated as an interview line: “I ship non-positional postings and re-scan the top 100 candidate messages for phrases. That costs about a megabyte of blob reads per phrase query and saves 36.6 PB of index.”

Re-scanning means fetching those few candidate message bodies and checking the phrase directly. It is cheap precisely because the non-positional index already shortened the candidate list to a hundred messages: 100 messages x 10 KB is about 1 MB of reads.

One number worth noticing before moving on

Look at what the fleet-wide index is measured against: 164 PB of indexed text, while the unique messages themselves are only 27.4 PB (1.5 B submissions per day x 10 KB of text x 1,825 days).

Those differ by the fanout of 6. Per-user indexing means the same message is analysed once for every recipient, so the volume of text indexed carries the full 6x while the volume stored does not. Holding both numbers at once is the point of the next subsection.

Why per user rather than one global index

Having sized the index, the question is whose messages go into one of them. Three arguments say per user, and only the first is about performance.

Argument 1: query locality, quantified

Locality here means how much of what you read is relevant to the question you asked. Low locality means reading a lot to use a little.

Take a common word appearing in 5% of all mail, and compare the global posting list for it against one user’s share of that same word:

messages delivered over 5 years
  9,000,000,000 x 365 x 5                =  16,425,000,000,000
postings for a term appearing in 5% of them
  16,425,000,000,000 x 0.05              =  821,250,000,000
that global posting list at 2 B per posting, in bytes
  821,250,000,000 x 2                    =  1,642,500,000,000
one user's share of the same term, in bytes
  54,750 x 0.05 x 2                      =  5,475
ratio
  1,642,500,000,000 / 5,475              =  300,000,000

A global posting list for one ordinary term is 1.64 TB, of which the querying user’s share is 5,475 bytes — a factor of 300 million. That factor is not a coincidence: it is the active user count, by construction, because one user holds one 300-millionth of the mail.

A global index answers “who wrote about invoices” by reading everyone’s postings and then filtering by owner. A per-user index answers it by reading one 44 MB structure on the shard that already holds the mailbox.

Argument 2: privacy is a property of the partition, not of the query

In a global index, keeping accounts apart means applying a filter such as WHERE owner = me after retrieving results. Three ordinary things then leak across accounts: a ranking bug, a new code path whose author forgot the filter, and any word-suggestion feature built on global statistics.

In a per-user index, the other accounts’ postings are not in the structure being read at all. There is no filter to forget.

Access control enforced by partitioning survives the refactors that access control enforced by a query condition does not.

Argument 3: deletion is a row operation, not a rewrite

Deleting an account under the European Union’s General Data Protection Regulation (GDPR) drops that user’s segments, and is finished.

In a global index the same request means rewriting every posting list containing any of that user’s 90,623 distinct words — each list scattered through a structure that runs to 1.64 TB for a single common word.

The cost, stated honestly

You index the same message once per recipient. So 164 PB of text is analysed instead of 27 PB, and you give up any signal that spans users.

Two features die with it. There is no global measure of how rare a word is across the whole corpus — the inverse document frequency, or IDF, that ranking normally leans on. And there is no “popular in your organisation” suggestion.

That 6x is the bill for privacy and query locality, and it is the right bill to pay.

Index-update cost per delivered message

Storage is one cost. Write throughput is another, and it has to be sized separately, because a system can fit on disk and still be unable to keep up with the writes.

One term first. Write amplification is the ratio between bytes actually written to disk and bytes the application handed over. Log-structured merge (LSM) storage rewrites data as it merges sorted files together in the background, so it writes each byte several times over its life; a factor of ten is a normal figure.

The block below takes the 774 bytes of index per delivery, multiplies by the 90,000 deliveries per second, applies that amplification, and then compares the result against one disk.

index bytes written per delivery
  387 x 2                                =  774
fleet index write rate, in bytes per second
  90,000 x 774                           =  69,660,000
with LSM compaction at 10x write amplification
  69,660,000 x 10                        =  696,600,000
as a fraction of one NVMe device at 1 GB/s sequential
  696,600,000 / 1,000,000,000            =  0.697
raw text ingest for comparison, in bytes per second
  90,000 x 10,000                        =  900,000,000

That is 697 MB/s of index writes across the whole fleet, or 0.7 of a single sequential-write device. (An NVMe drive is a solid-state disk attached directly to the machine’s high-speed bus; one sustains roughly a gigabyte per second of sequential writes.)

Indexing is therefore not the throughput problem. Two reasons: the postings are 7.7% of text that had to arrive anyway, and the writes are appends to the end of a file rather than scattered updates (LSM vs B-tree).

Three index costs are real, and they are the ones to name if pushed:

• Storage — 13.3 PB.
• Fanout — 774 bytes per recipient, so one submission to a 1,000-recipient list writes 774 KB of index in one go.
• Rebuild time — how long it takes to regenerate everything when the segment format changes.

Segments are appended per user and merged together lazily in the background, a process called compaction. A message becomes searchable the moment its postings land in a small in-memory tip segment, not when compaction finishes; section 13 sizes that tip.

9. Deep dive 3: attachments

Attachments are separated from everything else for one reason: they dominate the bytes and participate in none of the features.

One line of arithmetic makes the case. Of the 70,000-byte average message, the attachment part is 0.20 x 300,000 = 60,000 bytes:

attachment share of message bytes
  0.20 x 300,000 / 70,000                =  0.857

85.7% of the bytes are attachments, and 0% of them are searched, listed, threaded or sorted.

That asymmetry is the whole argument for splitting a message into pieces that live in different places. The table shows where each piece goes and what read pattern put it there.

The part manifest in that table is the list of attachments belonging to a message, each entry recording the content hash, size, media type and filename. It is the join between the small metadata row and the large blobs.

Two consequences follow immediately.

• Drawing a mailbox list touches zero attachment bytes. The interactive path reads only the 1.06% metadata tier, which is why a 200 ms p99 on listing is reachable at all.
• The same attachment sent by twelve people is stored once. That is the 30% duplicate rate assumed in section 3b — worth 27 TB a day and 49 PB over five years.

The filename is not part of the blob

The filename lives in the manifest, not in the blob’s name. The same PDF arriving as q3.pdf and as Q3 final (2).pdf is one blob with two manifest entries.

The reason is that the name is something one message says about the bytes, while the bytes themselves are global. Putting the name in the identity would defeat the dedup.

Deduplication happens on the server only

A client that is allowed to ask “do you already have this hash?” before uploading has been handed a membership oracle over everybody’s storage — a way to test whether a specific file exists anywhere in the system.

The attack is not subtle. The timing difference between “upload the whole file” and “never mind, you have it” is seconds against milliseconds, so no statistical care is needed to read the answer.

That attack and its mitigation — accept the upload anyway, with a randomized threshold, so the client cannot tell — are derived in ch 15. The rule is repeated here because email attachments are exactly the guessable documents such an attack targets: contracts, payslips, standard tax forms.

10. Deep dive 4: SMTP is store-and-forward, so status is eventually consistent

“Was it delivered?” is a question the system genuinely cannot answer, and the retry schedule, the user interface, and the queue capacity all follow from that fact.

This is not an architectural choice. It is what the protocol is. Each hop accepts responsibility for the message, answers 250, and takes on the duty either to deliver it or to report the failure later.

A 250 from the next hop means “I have it on disk”. It does not mean “the human has it”.

The state machine

The diagram below is what happens to one outbound message. SMTP replies are three-digit codes, and only the first digit matters here: 2xx is success, 4xx is a temporary refusal (“try again later”), 5xx is a permanent refusal (“never come back”).

Trace the five transitions:

• 250 accepted — handed off, but NOT delivered. The next server has promised only to keep trying.
• 4xx deferred — a temporary refusal, so the message goes into retry with backoff, each attempt waiting longer than the last.
• 5xx rejected — a permanent refusal. Hard bounce, reported as a DSN.
• From handed off, a DSN arrives minutes to days later if the message eventually failed somewhere downstream.
• From handed off, silence. The message is assumed delivered, and this state is genuinely unverifiable — which is the point of the section.

A message that keeps being deferred until the queue lifetime runs out also ends as a bounce.

flowchart LR
    Q["queued"] --> A["attempt"]
    A -->|"250 accepted"| H["handed off<br/>NOT delivered"]
    A -->|"4xx deferred"| R["retry with backoff"]
    R --> A
    A -->|"5xx rejected"| B["hard bounce · DSN"]
    H -->|"DSN arrives<br/>minutes to days"| B
    H -->|"silence"| U["assumed delivered<br/>unverifiable"]
    R -->|"queue lifetime expires"| B

    style U fill:#bc6c25,color:#fff
    style B fill:#9d0208,color:#fff
    style H fill:#1d3557,color:#fff

Retries, sized

Backoff means waiting longer before each successive retry, so a struggling receiver is not hammered by a sender that is already failing.

Here the delay doubles from one minute up to a cap of four hours, and the schedule keeps running until the queue lifetime of 96 hours is used up. The block counts the attempts that fit: first the doubling ramp, then the flat 4-hour attempts in whatever time is left.

backoff 1, 2, 4, 8, 16, 32, 64, 128 minutes, then capped at 4 h,
over a 96 h queue lifetime

the ramp, in minutes
  1 + 2 + 4 + 8 + 16 + 32 + 64 + 128     =  255
the ramp, in hours
  255 / 60                               =  4.25
hours left after the ramp
  96 - 4.25                              =  91.75
attempts at the 4 h cap
  91.75 / 4                              =  22.9
total attempts before the queue gives up
  8 + 23                                 =  31

That is thirty-one attempts over four days: eight attempts in the 4.25-hour ramp, then 91.75 hours divided by the 4-hour cap, which rounds to 23 more.

Four days is not an arbitrary choice. RFC 5321, the specification that defines SMTP, asks senders to keep trying for at least four to five days before giving up, and receivers rely on that promise.

Greylisting is the clearest example of a receiver relying on it. The receiver deliberately answers 4xx to any sender it has not seen before, on the assumption that spam software will not bother to come back. So the first message between two correspondents is designed to be delayed by minutes.

A sender that gives up after three attempts and ten minutes is not being decisive. It is failing to implement the protocol, and its mail will not arrive.

Queue depth when a receiver goes down

One large receiving provider having a bad afternoon is routine rather than exceptional, so size what that does to you. Take a destination that normally takes 10% of your outbound, down for four hours (14,400 seconds):

one destination taking 10% of outbound, down for 4 h
messages queued
  15,000 x 0.10 x 14,400                 =  21,600,000
bytes queued, in bytes
  21,600,000 x 70,000                    =  1,512,000,000,000

That is 1.51 TB of queue from one receiver having a bad afternoon.

That is why the outbound queue is partitioned by destination domain (ch 20). One slow domain must not cause head-of-line blocking — where the item stuck at the front of a queue holds up everything behind it, no matter where those items were going.

There is a second reason the partition is per domain and not per message: the retry schedule for a domain answering 4xx is a property of that domain, not of any individual message. Knowing “gmail is deferring right now” is useful once, for all of it.

Bounces are out of band

The DSN that tells you a message failed arrives as a separate inbound message, minutes to days later, from a server you never spoke to.

Delivery status therefore has at least four states — queued, handed off, bounced, expired — and “handed off” looks final without being final. “Delivered” is not observable at all. Ch 10 reaches the same conclusion from the push-notification side.

Three consequences follow.

• No user interface may present the status as a completed result. It mostly moves forward, but it is not settled for four days.
• Bounce processing is a full inbound mail pipeline in its own right, and it must resist forged DSNs. Anyone can send you a message claiming your mail to some address failed.
• A hard bounce must feed the suppression list — the set of addresses you refuse to send to again. Continuing to mail an address that does not exist is the fastest way to destroy the reputation that section 12 is about.

11. Deep dive 5: spam is the largest subsystem you own

Filtering is layered cheap-to-expensive, and that ordering is worth about four orders of magnitude per rejected message.

Start from the fact that the 9 billion daily deliveries are what survives filtering, not what arrives. If 60% of attempts are spam, then deliveries are the other 40%, so the real inbound volume is 9,000,000,000 / 0.40. The block works forward from there to two numbers worth memorising: the bytes never read, and the cores held.

assume  60% of inbound connection attempts are spam, IP reputation rejects
        80% of it at connect time, 5 ms of CPU per content scan

inbound attempts per day
  9,000,000,000 / 0.40                   =  22,500,000,000
inbound attempt QPS
  22,500,000,000 / 100,000               =  225,000
spam attempts per day
  22,500,000,000 - 9,000,000,000         =  13,500,000,000
rejected at connect, before DATA
  13,500,000,000 x 0.80                  =  10,800,000,000
ingest avoided per day, in bytes
  10,800,000,000 x 70,000                =  756,000,000,000,000
messages reaching the content scan
  22,500,000,000 - 10,800,000,000        =  11,700,000,000
content scan QPS
  11,700,000,000 / 100,000               =  117,000
cores held by the content scan
  117,000 x 0.005                        =  585
the filter's rate against the delivery rate
  225,000 / 90,000                       =  2.5

The spam filter runs at 2.5x the rate of the system it protects. That reframes spam from a feature into a tier.

The “585 cores” line: 117,000 messages per second, each holding a processor for 5 milliseconds (0.005 s), is 117,000 x 0.005 = 585 core-seconds of work per second, so 585 cores busy continuously, plus headroom.

Because the filter is the biggest thing you run, it is layered by cost: each layer is cheaper than the next and throws away as much as it can before handing on what is left.

The ordering is the design. Rejecting at connection time costs one reputation lookup. Rejecting after content analysis costs 70 KB of transferred bytes plus 5 milliseconds of processor time. Moving a rejection earlier is therefore worth roughly four orders of magnitude per message.

SPF, DKIM and DMARC, kept apart

These three are easy to blur. They do different jobs, and the difference is worth stating precisely.

• SPF — Sender Policy Framework. A DNS record listing which IP addresses may send mail for a domain. It authorizes the sending machine, which is why it breaks when a message is forwarded by a third party: the forwarder’s IP is not on the original domain’s list.
• DKIM — DomainKeys Identified Mail. A cryptographic signature over the message itself. It survives forwarding, because the signature travels with the bytes.
• DMARC — Domain-based Message Authentication, Reporting and Conformance. Ties either of those results to the From address the human actually sees, and publishes what a receiver should do when neither lines up.

The gap DMARC closes is that SPF and DKIM both authenticate things the reader never sees — a connecting IP, a signing domain in a header — while the address on screen can say anything at all.

12. Deep dive 6: outbound reputation, and why a shared pool is a liability

This is the part of the system you do not control: other companies decide whether your mail arrives, and their decision is made about an IP address that many of your customers share.

Receivers score the sending IP address and the sending domain. Those scores decide whether your mail reaches an inbox, a junk folder, or a temporary refusal.

Reputation is earned slowly and lost in an afternoon. That is an unusual and unforgiving shape for a system property, and it is what makes this a design problem rather than an operations problem.

The block below asks two questions: how much legitimate mail sits behind one shared IP address, and how long it takes to replace one that has been blocklisted.

assume  100 outbound IPs carrying 15,000 submissions/s

per-IP send rate
  15,000 / 100                           =  150
messages behind one IP per day
  150 x 86,400                           =  12,960,000
warming a replacement from 50/day, doubling daily: 2^18
  2 ^ 18                                 =  262,144
volume reachable on day 19
  50 x 262,144                           =  13,107,200

The warm-up line needs unpacking. Warming is the practice of raising a new address’s daily volume gradually, so receivers build a positive history for it; a brand-new address sending at full volume is itself a spam signal. Start at 50 messages on day 1 and double daily: day n sends 50 x 2^(n-1). To reach 13 million a day you need 2^18 = 262,144, and 50 x 262,144 = 13,107,200. That is day 19.

One compromised account’s spam run gets an IP address blocklisted, and that address is carrying 12,960,000 legitimate messages a day for everyone else. Replacing it takes 19 days.

Note what kind of argument that is. It is blast radius — how much of the business one failure takes down — not capacity. The pool is not too small; it is too shared.

Five mitigations, in the order they matter.

• Segment the pool by sender class. Transactional mail — receipts, password resets, low complaint rate, high value — never shares an address with bulk marketing or with brand-new accounts. A contaminated bulk address then costs you bulk deliverability rather than password resets.
• Quarantine new senders. New accounts send from a separate warming pool that cannot contaminate the main one, and they graduate on measured complaint rate rather than on age.
• Limit each account’s outbound rate (ch 04), sized so that a single compromised account cannot emit enough volume to move a shared address’s 24-hour score before your detection fires.
• Sign everything with DKIM at submission, so that domain reputation — which you control, and which survives changing IP addresses — carries the weight that IP reputation cannot.
• Feed hard bounces and complaint feedback loops into suppression automatically. A complaint feedback loop is a report a large receiver sends you when its users mark your mail as spam. Continuing to send to addresses that bounce or complain is the strongest negative signal a receiver has.

The point to state directly: deliverability is a reputation system operated by parties you do not control, so the architecture’s job is to keep the blast radius of any one bad sender small and the recovery path short.

13. Consistency: what a user may never see

“Eventually consistent” stays a slogan until it becomes a specification: a list of things a user might observe, a verdict on each, and the mechanism that enforces the verdict.

The three Never rows at the top are the invariants. Everything below them is a lag you are choosing to accept, with a bound on it.

The one lag worth engineering away

Search immediately after arrival is the case not to accept, because a user who has just been notified about a message very often searches for it a second later. Waiting for background compaction would make the message invisible in exactly the window when it is most wanted.

The fix is a tip segment: the newest postings are kept in a small in-memory piece of the index, which search consults before the on-disk segments. A message is findable the instant it is listed.

That only works if the tip fits in memory, so size it. Take the last 100 messages per user at the 774 bytes of index each from section 8:

tip segment: last 100 messages per user, in bytes
  100 x 774                              =  77,400
resident for 1% of daily actives concurrently, in bytes
  300,000,000 x 0.01 x 77,400            =  232,200,000,000
the same for every active mailbox at once, in bytes
  300,000,000 x 77,400                   =  23,220,000,000,000

That is 232 GB across the fleet to hold a searchable tip for every user with an open session, or 23.2 TB to hold one for everybody.

The first figure is the one that matters, because it is sized by how many people are active at once rather than by how many accounts exist. Two design rules follow from that: build the tip when a session opens and drop it when the session goes idle, and have search read the tip first and the on-disk segments second.

The result is that a message is findable the instant it is listed, and compaction runs on its own schedule with nobody waiting on it.

Unread counts are the clean counterexample: they are recomputable from the mailbox rows, so they are a cache and never a source of truth. A count that drifts is repaired by a recount. A message that drifts is gone.

14. Bottlenecks, scaling, and failure modes

Every limit derived so far, collected in one place. The right-hand column is the mechanism that keeps each limit from becoming an outage.

The blob-write line deserves its own arithmetic, because it is the clearest single statement of what dedup buys. Naive storage writes at the delivery rate of 90,000/s; deduplicated storage writes at the submission rate of 15,000/s, because the other five copies are already there:

per-recipient blob writes, in bytes per second
  90,000 x 70,000                        =  6,300,000,000
the same in Gbps
  6,300,000,000 x 8 / 1,000,000,000      =  50.4
deduplicated blob writes, in bytes per second
  15,000 x 70,000                        =  1,050,000,000
the same in Gbps
  1,050,000,000 x 8 / 1,000,000,000      =  8.4

That is 50.4 Gbps of storage writes reduced to 8.4 Gbps. (Multiplying bytes per second by 8 gives bits per second, which is the unit storage and network capacity are quoted in.)

Taking a round 1 Gbps of sustained write throughput per storage machine, that is the difference between 51 machines doing nothing but absorbing writes and 9. All of it from a single decision about what a stored object is named after.

Failure modes

The table below is the one to rehearse before an interview. Each row is a concrete failure, the signal that tells you it is happening, and the design property that contains it. The first row is the only one with no detection, which is exactly why the 250 ordering is non-negotiable.

15. Alternatives rejected

Each entry names a design an interviewer may propose, says what it is good at, gives the number that rules it out here, and names the situation where it would be the right answer instead.

One copy per recipient. Good: deletion is trivial, no reference counting, no sweep, and one user’s actions provably cannot affect another’s bytes. Rejected on 1.15 EB against 142 PB — an 8x storage bill to avoid writing a garbage collector. Correct below the point where storage costs less than the engineering, which for a small tenant-isolated mail product is a real place to be.

One global inverted index. Good: relevance signals that span users, a global measure of word rarity (inverse document frequency), one index to operate rather than 300 million, and the same message analysed once instead of six times. Rejected on both axes: a single ordinary term’s posting list is 1.64 TB of which a querying user needs 5,475 bytes — 300 million to one — and cross-account isolation becomes a query predicate that one bad code path removes. Correct for a corpus that is genuinely public, such as web search, where there is no owner to isolate.

Positional postings by default. Good: exact phrase search with no second pass. Rejected on 30% of the text instead of 7.7% — 49.8 PB of index instead of 13.3, so 36.6 PB of extra storage for a query type that is a minority of searches. Non-positional plus a re-scan of the top candidates gets the same answer for the cost of a megabyte of blob reads.

Relational storage for message bodies. Good: one system, transactional consistency between body and metadata. Rejected because bodies are immutable blobs with no predicates over them — the database would hold 142 PB to serve queries that only ever touch the 2 PB of metadata. The split is not a scaling workaround; the two halves have different access patterns and different consistency needs.

Synchronous delivery confirmation to the sender. Good: the sending user learns the truth. Rejected because the truth takes up to four days by protocol design, and holding a request open for four days is not an API. The honest design returns “queued” and delivers the outcome asynchronously, and refuses to render “handed off” as “delivered”.

One shared outbound IP pool. Good: simpler, better per-IP volume, faster warm-up, easier capacity planning. Rejected on blast radius — one compromised account can blocklist an IP carrying 12,960,000 legitimate messages a day, and the replacement takes 19 days to warm. Segmentation costs IPs and warm-up time; it buys a bounded failure domain, and reputation failures are the ones you cannot engineer your way out of after the fact.

Per-user encryption keys at rest. Good: a stolen blob store is useless to the thief, and a compromised operator cannot read mail.

Rejected for the dedup path. Encrypting the same plaintext under two different keys produces two different ciphertexts, so nothing matches anything, and the corpus reverts from 142 PB to 1.15 EB — 1,007 PB of extra storage.

Convergent encryption — deriving the key from a hash of the plaintext itself, so identical content always encrypts identically — restores deduplication. It also immediately reintroduces the confirmation-of-file attack: anyone who can guess the contents can encrypt their guess, see that the ciphertext already exists, and thereby confirm that some user holds that exact document.

The choice is between 1,007 PB of extra storage and an oracle that confirms guesses. Make it deliberately, rather than discovering it during a security review.

16. Interviewer pushback

These are the seven questions this design attracts, with each answer written the way it should be spoken aloud. The italic line names what the question is really testing.

“How much storage does this need?” Testing: whether you notice the fanout before you multiply. Thirty received messages a day for 300 million actives is 9 billion deliveries, at 70 KB each — 10 KB of text plus a 20% chance of a 300 KB attachment — so 630 TB a day if I store a copy per recipient, and 1.15 exabytes over five years. But only 1.5 billion of those are distinct submissions, because the average message has six recipients, so storing each message once takes it to 105 TB a day. Content-hash dedup on attachment parts takes about 30% more off, landing at 78 TB a day and 142 PB over five years. Then three replicas for the last 30 days and erasure coding at 1.4x for the tail gives 203 PB physical against 3.45 EB for the naive design — a 17x reduction, all of it from one design decision plus one storage policy.

“Why is the fanout the number you keep coming back to?” Testing: whether the estimate is load-bearing or decorative. Because every subsystem either pays it or dodges it, and I want to be deliberate about which. Storage dodges it: one blob, six references, 83% saved. Metadata pays it: six mailbox rows, because read flags and labels are genuinely per user, and that is only 124 bytes a row, so 1.06% of the write volume. The search index pays it too — 164 PB of text analysed instead of 27 — and that one is a choice I would defend, because the alternative is a global index. The pathological case is a mailing list: one submission to a thousand recipients is 99.9% redundant in storage and 774 KB of index writes, which is the failure mode I rate-limit for.

“How does search work? Don’t just say Elasticsearch.” Testing: whether you can size an index. A per-user inverted index. A 10 KB message is about 1,500 words, and Heaps’ law with k=10 gives roughly 387 distinct terms, so at 2 bytes a delta-encoded posting that is 774 bytes — 7.7% of the text. Over 54,750 messages in five years that is 42 MB of postings plus a 90,623-term dictionary at 20 bytes each, so 44 MB per mailbox, 8.1% of the text it covers, 13.3 PB fleet-wide. Positional postings for phrase search would store every occurrence rather than every distinct term, which is 3,000 bytes a message — 3.9x, 30% of the text — so I ship non-positional and re-scan the top hundred candidates for phrases, which costs about a megabyte of blob reads and saves 36.6 PB of index.

“Why not one index for everything? It would be far more efficient.” Testing: the best question in the problem. It would be more efficient at write time and catastrophic at read time. A term appearing in 5% of mail has a global posting list of 821 billion entries — 1.64 TB — while the querying user’s share of that same term is 5,475 bytes. That ratio is 300 million to one, which is not a coincidence, it is the active user count: a global index makes you read everybody’s postings to answer one person’s query, then filter by owner. And that filter is where the privacy story lives. In a global index, isolation is a WHERE owner = me that any new code path can omit; in a per-user index the other accounts’ postings are not in the structure being read. Access control by partition survives refactors that access control by predicate does not. Deletion is the third reason — closing an account drops its segments instead of rewriting posting lists across 90,000 terms. The price is real: I analyse each message once per recipient, 6x, and I give up global relevance signals.

“A user sends a message. When can they consider it delivered?” Testing: whether you know what SMTP actually promises. They cannot, and neither can I. SMTP is store-and-forward: a 250 means the next hop wrote it to disk and accepted the duty to keep trying, not that a human has it. Failures come back as a separate inbound message minutes to days later, so the status field has queued, handed off, bounced and expired — and “handed off” looks terminal without being terminal. The retry schedule is four to five days by convention because receivers rely on it; greylisting deliberately returns 4xx to unknown senders on first contact, so the first mail between two people is designed to be slow. With backoff ramping from one minute to a four-hour cap, that is 31 attempts over 96 hours. So delivery status is eventually consistent by protocol, not by my choice, and my UI must never render “handed off” as “delivered”.

“You share outbound IPs across customers. What’s wrong with that?” Testing: whether reputation is a subsystem in your head or a footnote. One compromised account is what is wrong with it. With 100 IPs carrying 15,000 submissions a second, each IP is behind 12,960,000 legitimate messages a day; a spam run from one account gets that IP blocklisted and everyone else’s mail starts deferring. Replacing it is not fast — a brand-new IP sending at full volume is itself a spam signal, so you warm it by roughly doubling daily from about fifty, and reaching 13 million a day takes 2^18, which is 19 days. So the pool is segmented by sender class: transactional mail never shares an IP with bulk or with new accounts, new senders live in a warming pool that cannot contaminate the main one, per-account rate limits are sized so no single account can move a 24-hour score before detection fires, and everything is DKIM-signed at submission so domain reputation — which I control and which survives IP rotation — carries the weight.

“What must a user never see, and what are you happy to let lag?” Testing: whether “eventual consistency” is a slogan or a specification. Never: a message that was listed and then is gone, a message SMTP accepted that never appears, or a body that changed. Those follow from three rules — blob before metadata, 250 only after the mailbox row commits, and bodies are content-addressed and immutable. Happy to lag: unread counts, because they are recomputable from the mailbox rows and therefore a cache; thread ordering during a rebuild, because threading is a derived view; a label change reaching a second device within a sync interval. The one I engineer rather than accept is search-after-arrival, because a user notified about a message immediately searches for it. So postings append synchronously to a small in-memory tip — the last hundred messages, 77 KB a user, 232 GB across the fleet at 1% session concurrency — and compaction into on-disk segments runs asynchronously. The message is findable the instant it is listed.

Cheat sheet

One line per idea, in the order the chapter builds them, for revision the morning of an interview. DAU means daily active users.

Related: 15 — Google Drive is the content-addressing and dedup-side-channel machinery this chapter reuses; 10 — Notification System reaches the same “delivered is a lie” conclusion from the push side; 20 — Distributed Message Queue is the outbound queue; 23 — Hotel Reservation is the same interview question asked where the invariant, not the storage, is the constraint.