Email Service (Gmail)

The problem

"Design an email service like Gmail." Users get mail from any server on the internet, keep it for years, organize it with labels, search it and send their own. This practice problem reuses the pattern of Design a Notification System: outgoing mail waits on a queue and retries, and new mail triggers a push. What's new is around the mailbox: mail from strangers, much of it spam; years of storage per user; search over your own mail; and proof for other providers that your mail is yours. Park smart replies and chat.

The numbers

From the interviewer: 1 billion users, each getting about 40 emails a day of about 50 KB, and 1 in 10 carries an attachment of about 1 MB. Round a day to 100,000 seconds.

quantity        working                     result
mail            40 × 50 KB                  2 MB a user a day
attachments     4 × 1 MB                    4 MB a user a day
one mailbox     6 MB × 365                  ≈ 2.2 GB a year
everyone        1 billion × 2.2 GB          ≈ 2 billion GB (2 exabytes) a year
arriving mail   40 billion ÷ 100,000 s      ≈ 400,000 a second

Two facts shape the design: storage only grows, and two thirds of the bytes are attachments.

Receiving: spam before the inbox

Mail servers hand mail to each other over SMTP. When Bob at othermail.com emails Ana:

1. Bob's mail server looks up your domain's MX record in DNS, which names the servers that take its mail.
2. It connects to one of your SMTP servers and hands over the mail.
3. Your server checks SPF and DKIM and scores the mail for spam.
4. It saves the mail in Ana's mailbox: in Inbox, or under Spam.
5. Ana's phone gets a new-mail alert.

Say half of what arrives is spam, so the filter sits before the mailbox. Mail from addresses known for spam is refused during the SMTP conversation, before you store a byte; the rest is scored, and likely spam is labeled Spam on its way in. Filtering after saving would show spam in the inbox first, and you'd store and index all of it. SPF and DKIM are proof the mail really came from the domain it claims.

Labels: each message once

Ana has about 150,000 messages from 10 years (40 a day × 365 × 10 = 146,000), each with any number of labels. Store each message once with its label ids, plus a label index:

record        fields
message       user_id, id, from, subject, body, labels, attachment hashes
label index   (user_id, label, time) → message id

Opening Work reads its newest 50 index rows. A copy per label stores a mail in three labels three times, and "mark as read" must change every copy; no index means reading all 150,000 messages to open one label. Key everything by user id and split the mailboxes by user, so each one lives on a single shard.

Attachments: stored once, by hash

HR sends a 5 MB PDF to 2,000 people at Acme. Kept inside each message it costs 2,000 × 5 MB = 10 GB and slows every read of those mailboxes; one file per recipient in object storage is still 10 GB. Instead, name the file by the SHA-256 hash of its bytes, as the Dropbox lesson names its chunks: the same bytes give the same hash, so copies 2 to 2,000 find the file already there. Each message keeps the hash, and the file keeps a count of the messages pointing at it, deleted when it reaches zero. Hash on the server, so a sender can't learn whether someone else already has a file.

Search: an index per user

Reading Ana's mail for invoice march means 150,000 messages × 50 KB, about 7 GB, per search. One index of everyone's mail, as for web search, makes each search walk the giant list for "invoice" to keep Ana's few, and a bug in that filter leaks other people's mail. Give each user a small inverted index, word → their message ids, on their mailbox's shard: the Search Engine lesson's index, one per user. A search walks two short lists together, and each new mail adds its words as it arrives.

Sending: retries and trust

Outgoing mail waits on a queue, and your SMTP servers deliver it with backoff, as in the Notification System. The other server's reply decides what happens:

reply                        what you do
421 busy, try again later    retry with backoff
451 error, try again later   retry
connection timed out         retry
550 no such user             bounce to the sender now
554 rejected as spam         bounce, and check SPF and DKIM

A 4xx reply is temporary: keep trying, commonly for up to about 5 days, then bounce. A 5xx reply is permanent: bounce at once, with the reason, in a mail from your own service. Other providers trust your mail when it passes SPF and DKIM: proof it really came from your domain.

Same pattern as the Notification System

Outgoing mail is a channel like SMS: a queue, workers that call another company's servers, retries with backoff and jitter, and a cap on how fast you send to each provider. New mail triggers a push through the notification service itself.

Summary

• Numbers: about 2 GB per user a year, two thirds attachments.
• Receiving: MX record, SMTP, a spam check, then the mailbox.
• Labels: each message once, a label index, mailboxes split by user.
• Attachments: in object storage, once, named by their hash.
• Search: a small inverted index per user.
• Sending: a queue; 4xx retried for days, 5xx bounced; SPF and DKIM.