Design an Email Service at Gmail Scale (1.8B Users, 300B Messages/Day)

TL;DR. Email at hyperscale is a storage problem wearing a messaging costume. Gmail serves 1.8 billion users ^[1] and handles a share of the roughly 300 billion messages per day sent globally ^[2], but the majority of inbound traffic is spam killed before inbox. The pivotal trade-off is between server-side plaintext access (enabling search, Smart Compose, and spam ML) and zero-access encryption (Proton Mail model, which sacrifices those features). The architecture that works: SMTP ingress with layered authentication (SPF/DKIM/DMARC), a cost-ordered spam cascade, delivery into a Bigtable-style wide-column mailbox, content-addressed attachment dedup saving 36% of storage ^[3], and a per-user sharded inverted index holding search p99 under 200 ms.

Learning Objectives#

• Design SMTP ingress and a multi-stage spam cascade for 3.5M messages/sec peak under a 2-second pre-delivery budget
• Justify per-user sharded search over a global index and estimate capacity for 200 ms p99 across decade-deep mailboxes
• Implement RFC 5322 header threading with subject-line fallback using the jwz algorithm
• Tier exabyte-scale storage (hot SSD, warm HDD, cold archive) and deduplicate attachments by content hash
• Compare cloud-trust (Gmail) and zero-access (Proton) models and articulate what each sacrifices
• Estimate capacity for 1.8B mailboxes at 15 GB each across three storage tiers

Intuition#

A single-server email system works fine for 100 users. Accept SMTP, drop the message in a file, let the user POP it off. At 1.8 billion users exchanging 300 billion messages per day, three forces shatter this model.

First, the adversarial flood. A large share of inbound traffic (commonly estimated at 45-85% depending on provider and era) is spam, phishing, or malware ^[4]. You must classify 3.5 million messages per second before delivery, under a 2-second latency budget, with 99.9% precision. A false positive silently costs a user a job offer. A false negative costs them money.

Second, the storage cliff. Each user gets 15 GB free ^[5], shared across mail, drive, and photos. Multiply by 1.8 billion accounts and you are in the exabyte range. Attachments dominate: Mail.Ru measured that message bodies and indexes account for only 15% of mailbox storage, with the remaining 85% in files ^[3:1]. You cannot afford to store the same 5 MB newsletter PDF separately for 10 million recipients.

Third, the search expectation. Users search a decade of mail and expect results in under 200 ms. A global shared index leaks data across tenants on any query bug. Per-user sharding solves privacy, quota isolation, and tail latency in one stroke, but forces you to maintain billions of tiny index shards.

The naive architecture fails on all three axes simultaneously. The design that ships is a cost-ordered spam cascade (cheap signals first, ML only on the ambiguous middle), a columnar mailbox store with tiered lifecycle, content-addressed attachment dedup, and a per-user inverted search index fed asynchronously from the delivery log.

Requirements#

Clarifying Questions#

• Q: Cloud-trust model or end-to-end encryption? Assume: Cloud-trust (server can read content). This enables server-side search, spam ML, and Smart Compose. Note the Proton alternative in trade-offs.
• Q: Full-text search including attachments? Assume: Yes for message bodies and metadata. Attachment content search is best-effort (PDF/DOCX extracted at index time).
• Q: Which client protocols must we support? Assume: SMTP (ingress/egress), IMAP with IDLE ^[6], JMAP (RFC 8620/8621) ^[7][8], and a proprietary web/mobile REST API.
• Q: Spam SLA: pre-delivery or post-hoc? Assume: Real-time pre-delivery. Users never see classified spam in their inbox.
• Q: Attachment size limit? Assume: 25 MB inline; larger via drive-link integration.
• Q: Threading model? Assume: RFC 5322 References/In-Reply-To primary, subject-line clustering fallback ^[9][10].

Functional Requirements#

• Compose, send, and receive messages via SMTP with DKIM/SPF/DMARC authentication ^[11]
• Thread messages into conversations using RFC 5322 headers with subject-line fallback
• Full-text search across a user's entire mailbox (bodies, subjects, senders, labels)
• Labels, filters, forwarding, vacation auto-reply, and archive
• Attachment upload with virus scan, preview generation, and CDN-backed download
• Spam/phishing/malware classification pre-delivery with user feedback loop

Non-Functional Requirements#

• Load: 3.5M messages/sec peak ingress; 5M search QPS peak
• Latency: search p99 < 200 ms; message delivery p99 < 2 s (including spam classification)
• Availability: 99.99% on read path; 99.9% on write path
• Durability: 11 nines; no message loss after SMTP 250 OK
• Storage: 15 EB across tiers; 15 GB per-user quota ^[5:1]

Capacity Estimation#

• Read:write ratio: Inbox views dominate; roughly 50:1 reads to writes per user per day.
• Spam ratio: A large share of inbound is spam, killed before mailbox write. Only a fraction reaches storage.
• Hot tier: Last 30 days on SSD; warm (30-365 days) on HDD; cold (>1 year) on archive.

API and Data Model#

API Design#

POST /v1/messages/send
  Body: { "to": [...], "subject": "...", "body_html": "...",
          "attachments": ["obj_id_1"], "thread_id": "..." }
  Returns: 201 { "message_id": "...", "thread_id": "..." }
  Idempotent on client-generated Idempotency-Key header

GET /v1/messages?label=INBOX&before=<cursor>&limit=50
  Returns: 200 { "threads": [...], "next_cursor": "..." }

GET /v1/search?q=from:alice+has:attachment&limit=20
  Returns: 200 { "messages": [...], "total_estimate": 342 }

PATCH /v1/messages/{id}
  Body: { "add_labels": ["STARRED"], "remove_labels": ["UNREAD"] }
  Returns: 200

POST /v1/attachments/upload
  Body: multipart/form-data (file <= 25 MB)
  Returns: 201 { "object_id": "sha256:abc...", "preview_url": "..." }

Data Model#

-- Mailbox messages (Bigtable-style columnar store)
-- Row key: user_id | inverted_timestamp | message_id
-- Column families: headers, body, flags, thread_ref
-- Range scan on user_id prefix serves inbox view (newest first)

-- Attachment store (object storage, content-addressed)
-- Key: SHA-256 of file content
-- Metadata: { ref_count, content_type, size, upload_ts }
-- Lifecycle: hot (SSD, <90d) -> cold (archive, >90d)

-- Thread state (PostgreSQL, regional primary + read replicas)
CREATE TABLE threads (
    user_id       bigint,
    thread_id     bigint,
    message_ids   bigint[],
    participants  text[],
    subject_norm  text,
    last_updated  timestamp,
    PRIMARY KEY (user_id, thread_id)
);

-- Search index (per-user sharded inverted index)
-- Shard key: user_id
-- Terms: tokenized per-locale (language detect, stem, stopword)
-- Supports operators: from:, to:, has:attachment, older_than:, label:

Each user's mail lives in a dedicated Bigtable shard; messages reference content-addressed attachments and belong to threads tracked in PostgreSQL.

High-Level Architecture#

SMTP ingress flows through authentication and a spam cascade before the delivery router writes to the user's Bigtable shard; Kafka fans out to search indexing, push notifications, and compliance.

Write path: A peer MTA connects on port 25. The edge checks MX routing, runs SPF/DKIM/DMARC ^[11:1], then feeds the message into the spam cascade. Clean messages hit the delivery router, which evaluates per-user filter rules and writes to the user's Bigtable partition (row key: user_id | inverted_timestamp | message_id). The write is committed to the delivery log (Kafka), which triggers async consumers for search indexing, mobile push, and legal hold.

Read path: Clients connect via JMAP or the proprietary REST API. Inbox view is a range scan on the user's Bigtable shard (newest-first by inverted timestamp). Search queries route to the user's dedicated index shard. Attachment downloads go through a CDN with signed URLs.

Async path: The delivery log decouples the write path from expensive downstream work. Search indexing, push notification fan-out, and compliance archival all consume from Kafka independently, each at their own pace.

Deep Dives#

Spam classifier cascade#

Gmail blocks over 99.9% of spam, phishing, and malware before inbox ^[4:1]. In 2019, TensorFlow-based models added 100 million additional blocks per day on top of existing rule-based filters ^[12]. The cascade is ordered by cost, not accuracy: cheap signals short-circuit, and expensive ML runs only on the ambiguous middle.

Stage 1: IP reputation. Check the sender's IP against blocklists (Spamhaus, internal reputation from Google Postmaster Tools ^[13]). Known-bad IPs are rejected with SMTP 550 immediately. This kills the majority of spam volume at near-zero CPU cost.

Stage 2: Authentication results. Evaluate SPF, DKIM, and DMARC. Since February 2024, Google and Yahoo require all three for bulk senders (5,000+ messages/day) ^[11:2]; Microsoft Outlook enforced the same starting May 2025 ^[14]. Gmail escalated to rejecting non-compliant traffic in November 2025. Messages failing DMARC with p=reject are dropped without further processing.

Stage 3: Content ML. A TensorFlow model scores subject, body, and embedded content. It catches image-only spam, hidden embedded text, and messages from newly registered domains ^[12:1]. The model runs only on the ~10% of traffic that passed stages 1-2 but scored ambiguous.

Stage 4: Link and hash lookup. URLs are checked against a reputation database. Attachment SHA-256 hashes are compared against known-malware signatures. Microsoft's Safe Links takes this further by rewriting URLs and re-scanning at click time ^[15].

Stage 5: User feedback. "Mark as spam" signals retrain the model daily. A single user's report adjusts their personal filter immediately; aggregated reports shift the global reputation signal within minutes.

Cheap signals (IP reputation, authentication) short-circuit 90%+ of spam before the expensive content ML model runs, keeping per-message CPU low.

Per-user sharded search index#

A user searches a decade of mail and expects results in under 200 ms. The key insight: per-user sharding solves three problems with one answer. Privacy (no cross-tenant data leak from a query bug), quota (one user cannot blow up another's latency), and tail latency (p99 is bounded by one user's worst segment) ^[16].

Index structure: Each user's shard is a small inverted index (~5 GB for a heavy user). Terms are tokenized per-locale with language detection, stemming, and stopword removal. The query parser supports Gmail-style operators (from:, has:attachment, older_than:1y, label:).

Async indexing: New messages are indexed off the Kafka delivery log, not inline with the write path. This keeps delivery latency tight and lets the indexer batch and optimize writes. Indexing lag is typically under 5 seconds; users rarely search for a message they received 3 seconds ago.

Proton Mail's alternative: Proton takes the opposite approach. Because the server cannot decrypt content, search is implemented entirely client-side. On activation, the client fetches every message, decrypts with the user's OpenPGP key, re-encrypts under a per-session AES-GCM key, and stores the ciphertext in IndexedDB ^[16:1]. Query latency is noticeably slower than server-side search, and attachment content is excluded. This is the cost of zero-access encryption.

Scale: At 5M QPS peak, with each query hitting exactly one shard, you need a fleet large enough to serve the hot working set from memory. Most users' recent mail (last 30 days) fits in a few hundred MB of index; cold segments are loaded on demand.

Threading with the jwz algorithm#

Email threading looks simple until you encounter clients that strip References headers, mailing lists that rewrite subjects, and users who reply to the wrong message.

Primary signal: RFC 5322 headers. Each message carries a globally unique Message-ID. Replies include In-Reply-To (immediate parent) and References (full ancestor chain, oldest to newest) ^[9:1][17]. The canonical threading algorithm is Jamie Zawinski's "jwz threading" from Netscape Mail ^[10:1]: build a forest from References, then group orphans by normalized subject within a recency window.

Subject-line fallback. When References is missing (common on older mobile clients and some Outlook versions), normalize the subject (strip Re:, Fwd:, [list-tag]) and cluster by sender + normalized subject within a 30-day window. This rescues threads but occasionally false-merges unrelated "Lunch?" messages.

Implementation: On delivery, the threading service checks References against the thread table. If a parent Message-ID is found, attach to that thread. If not, fall back to subject clustering with a 30-day + shared-participant constraint to reduce false merges.

Headers are the primary threading signal; subject-line clustering is a narrow, time-bounded fallback for clients that stripped References.

Content-addressed attachment dedup#

Attachments are 85% of mailbox storage ^[3:4]. The same newsletter PDF sent to 10 million recipients should store once, not 10 million times.

Mechanism: On upload, compute SHA-256 of the file content. If the hash already exists in the object store, increment the reference counter and return the existing object ID. The message stores only the hash reference, not the bytes.

Consistency challenge: A crash between "delete message" and "decrement counter" leaves the system inconsistent. Mail.Ru's solution uses a "magic number" per message: a random value added on upload and subtracted on delete. When the counter reaches zero but the magic number does not match, the blob is quarantined rather than deleted, and physically removed only after a delay ^[3:5].

Results: Mail.Ru reduced their email storage from 50 PB to 32 PB, a 36% savings ^[3:6]. At Gmail's exabyte scale, this translates to petabytes of savings and proportional cost reduction on the storage tier.

Tiered lifecycle: After dedup, blobs follow a lifecycle: hot SSD for the first 90 days, warm HDD for 90 days to 1 year, cold archive beyond. Bigtable's tiered storage feature automates this demotion under a single interface ^[18]. Reads against cold tiers trigger async promotion back to warm.

Real-World Example#

Gmail on Bigtable + Colossus.

Gmail runs on Bigtable, the distributed wide-column store published at OSDI 2006 ^[19]. Bigtable is a sparse, distributed, persistent multi-dimensional sorted map designed for petabyte scale on thousands of commodity servers ^[19:1]. For Gmail, the row key is user_id + inverted_timestamp + message_id, with column families for headers, body, and flags. Range scans serve the inbox view with newest-first ordering.

Underneath Bigtable, Colossus is Google's distributed file system layer with separate Curator (metadata) and D file server (data) planes for independent scaling ^[20]. Bigtable now supports tiered storage that automatically demotes cold rows from SSD to infrequent-access storage under a single interface ^[18:1].

The December 2020 outage illustrates the fragility of quota systems at scale. An obsolete quota-management system, left in place during a migration, reported the User ID service's usage as zero. After a grace period expired, the automated quota system reduced the service's quota, preventing the Paxos leader from writing. Authentication lookups returned 5xx for approximately 45 minutes. Engineers root-caused by 04:08 PT and recovered by 04:33 ^[21].

Exchange Online's alternative: Microsoft replicates every mailbox database to at least three copies across geographically separate datacenters within a Database Availability Group (DAG); the most common configuration is three copies in three datacenters, with fewer in territories that have only two (Australia, Japan) ^[22]. On-premises Exchange Server DAGs scale to up to 16 Mailbox servers per group ^[23]. A lagged copy maintains 7-day snapshots for catastrophic logical corruption recovery. Shadow Redundancy keeps in-transit copies until the receiver acknowledges; Safety Net holds post-delivery copies for automatic resubmission after failover ^[22:1].

Trade-offs#

The single biggest meta-decision is the trust model. Gmail chooses server-side access, which enables Smart Compose ^[24], full-text search, and ML-based spam classification. Proton Mail chooses zero-access encryption, which means the server cannot search, moderate, or offer AI features without breaking the trust model ^[16:4]. Each is defensible; the choice is a product decision, not a pure engineering one.

Scaling and Failure Modes#

At 10x load (35M msg/sec): The spam cascade becomes the bottleneck. The content ML stage cannot scale linearly because model inference is GPU-bound. Mitigation: more aggressive early-stage filtering (tighter IP reputation thresholds), model distillation for cheaper inference, and horizontal GPU scaling behind a queue.

At 100x load (350M msg/sec): The delivery log (Kafka) saturates. Mitigation: partition by user-hash rather than conversation, add regional Kafka clusters with cross-region replication only for compliance, and move search indexing to a dedicated streaming pipeline (Flink).

At 1000x load: The architecture shifts to edge-first processing. SMTP ingress, spam classification, and even mailbox writes happen at regional edge clusters. A global coordination layer handles cross-region delivery and dedup reconciliation.

Failure mode: Quota system bug (Dec 2020). An automated quota enforcer incorrectly zeroed the User ID service's allocation, blocking Paxos writes. Gmail was down ~45 minutes ^[21:1]. Mitigation: quota changes require human approval above a threshold; never auto-reduce below a floor.

Failure mode: Metadata blob overload (Aug 2020). An overloaded metadata service in the internal blob store cascaded into Gmail and Drive unavailability ^[25]. Mitigation: circuit breakers on metadata lookups; serve inbox from cached headers even when blob metadata is degraded.

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Dedup reference-count consistency#

A message referencing attachment sha256:abc is deleted. The deletion service decrements the ref-count from 1 to 0 and is about to delete the blob when it crashes. Meanwhile, a new message arrives referencing the same hash. Design a protocol that prevents both data loss (blob deleted while referenced) and storage leaks (blob never deleted).

Key Takeaways#

• Email is a storage problem. Ingress is tractable at 3.5M msg/sec; the 15 EB mailbox footprint across tiers shapes every architectural decision.
• Spam classification is a cascade, not a model. Cheap signals (IP reputation, authentication) short-circuit 90%+ of volume; expensive ML polishes only the ambiguous middle ^[4:3][12:2].
• Per-user index sharding is the right search design. Privacy, quota isolation, and tail-latency bounding all land on the same answer.
• Content-addressed dedup is existential at exabyte scale. 36% savings on 50 PB is 18 PB freed; the ref-counting complexity pays for itself many times over ^[3:11].
• The trust model is a product decision. Server-side access enables search, Smart Compose, and spam ML. Zero-access encryption sacrifices all three. Neither is wrong.
• Threading is an RFC with a subject-line escape hatch. Neither is perfect alone; the hybrid (headers primary, subject fallback with constraints) is what ships ^[10:4].

Further Reading#

• Bigtable: A Distributed Storage System for Structured Data (OSDI 2006). The canonical paper on the store underpinning Gmail; explains the sorted-map model and tablet splitting that makes per-user range scans efficient.
• Behind the scenes of Proton Mail's message content search. First-person engineering writeup of client-side encrypted search using IndexedDB and Web Crypto API; the clearest articulation of the zero-access trade-off.
• Efficient storage: how we went down from 50 PB to 32 PB. Mail.Ru's attachment dedup with the magic-number consistency trick; the best public source on ref-count correctness at scale.
• Ridding Gmail of 100 million more spam messages with TensorFlow. Google's public engineering note on the ML layer of the spam cascade; explains what categories TensorFlow catches that rules miss.
• RFC 8620 (JMAP Core) and RFC 8621 (JMAP Mail). The modern replacement for IMAP; batched JSON-over-HTTPS with back-references eliminates multi-round-trip mobile sync.
• Exchange Online Data Resiliency. Microsoft's public architecture for DAG replication, lagged copies, Shadow Redundancy, and Safety Net.
• jwz threading algorithm. The canonical email threading algorithm from Netscape Mail (1997); still the foundation of Gmail's conversation view.
• Smart Compose: Using Neural Networks to Help Write Emails. The hybrid BoW+RNN-LM model serving per-keystroke suggestions at ~100 ms; shows what server-side plaintext access enables.

Flashcards#

References#