Email Service deep dive: storage design and per-user search

The first lesson established that storage leads this design: 200 PB of bodies that are rarely read, and a thin layer of metadata that serves every query. This lesson turns that ratio into a storage layout, then builds the search system that the layout makes possible.

There are three kinds of data with three different access patterns and three different stores.

Metadata: a distributed database, partitioned by user

Every listing, search result, unread count, and flag change touches metadata. It is small, hot, and queried by mailbox.

Partition by user ID. All of one user's metadata lives on one partition, so opening a mailbox is a single-partition range scan rather than a scatter-gather across the cluster. A wide-column store fits the shape well: the partition key is the user, the clustering key is the folder or label plus a timestamp, and rows are wide and sparse.

The cost of this choice is that anything crossing users becomes expensive. A shared mailbox for support@ has many readers and one partition, so it becomes a hot key — the same problem as the global leaderboard in Section 27 (Design a Real-Time Gaming Leaderboard). Model a shared mailbox as its own pseudo-user with its own partition and grant access, rather than duplicating messages into each member's mailbox.

Bodies: blob storage, written once, read rarely

The message body — headers, text, HTML — goes into an object store as an immutable blob. The metadata row holds the blob's identifier. Bodies are never updated, only created and deleted, which makes them a perfect fit for the object storage of Section 26 (Design an S3-like Object Storage).

Small bodies have a problem worth naming: a 4 KB message in an object store with per-object overhead and a minimum billable size is inefficient. Pack many small bodies into larger container blobs and store an offset and length in the metadata. Now one read fetches a byte range from a large object, and the per-object overhead is amortised across thousands of messages.

Attachments: deduplicated by content hash

Compute a hash of each attachment's bytes. Store the blob under that hash. If the hash already exists, store only a reference.

The saving, computed. A 4 MB presentation sent to a 300-person team, stored naively, is 1.2 GB. Deduplicated, it is 4 MB plus 300 small references — a 300× reduction on that message. Across a whole system the aggregate saving depends entirely on how much mail is internal and broadcast; tens of per cent of attachment bytes is a plausible order of magnitude, and it should be presented as an estimate rather than a fact.

The caveats, both real. Reference counting must be exact, or deleting one user's copy destroys everybody's. And cross-user deduplication has a privacy edge: an attacker who can observe storage growth can test whether a specific file already exists in the system. Deduplicating within a user, or within an organisation, removes most of that risk and captures most of the saving — and that is the recommendation unless the interviewer wants the full cross-user analysis.

Search

With metadata partitioned by user, search follows the same line. Search over email is not a smaller version of web search. The constraint that changes everything is that every user must see only their own mail.

Why one shared index does not work

An inverted index maps a term to the list of documents containing it. A single global index over 100 million mailboxes would answer "invoice" with a posting list spanning every user, and the system would then filter it down to one user's messages.

Two problems, one of them fatal.

Performance. The posting list for a common term such as "invoice" would contain billions of entries, of which one user's few dozen are relevant. You would read a gigabyte to return twelve results.

Safety. One filtering bug exposes other people's mail. A design where a single missing predicate causes a privacy breach is a bad design regardless of how carefully it is written. The property you want is that a user's query is structurally incapable of reaching another user's data.

Per-user indexes

Give every mailbox its own inverted index, stored alongside that user's metadata partition. A query touches exactly one user's index, so the posting lists are small — a mailbox with 50,000 messages has posting lists in the thousands, not the billions — and cross-user access is impossible by construction rather than by predicate.

Index size. For a 2 GB mailbox of mostly text, an inverted index typically lands somewhere around 10–30% of the indexed text size. Bodies are a minority of a mailbox's bytes once attachments are counted, and attachment contents may or may not be indexed. A working estimate is a few hundred megabytes per heavy user and a few megabytes for a typical one — worth flagging as an estimate that must be measured rather than a number to quote confidently.

Incremental indexing on delivery. When a message is accepted and placed, extract its terms and append to the user's index in the same pipeline. Search freshness then equals delivery latency, which is what users expect — mail is searchable the moment it appears.

The cost of reindexing

Changing the analyser — adding stemming, changing tokenisation, supporting a new script — means rebuilding every index. 100 million users is 100 million rebuild jobs. At a throughput of, say, 1,000 mailbox rebuilds per second across a large fleet, that is roughly 28 hours of continuous work.

So build for it: version the index format, run old and new side by side, migrate mailboxes in the background, and switch each user's queries over when their new index is ready. This is a migration design, not a one-off script, and saying that is a mark of experience.

What to index, and the honest limits

Index the headers, the plain-text body, and the extracted text of common attachment formats if the product requires it — but note that attachment extraction multiplies indexing cost and is frequently descoped.

End-to-end encrypted mail cannot be indexed server-side at all, because the server never sees the plaintext. The options are client-side indexing, which does not work well across devices, or searchable encryption schemes, which are an active research area with real performance and leakage trade-offs. The honest answer in an interview is that server-side search and end-to-end encryption are fundamentally in tension, and every product picks one.