Part 5 of 8 · 2 min read
Data model
Keys decide the queries.
What the data looks like.
- Mail is read mostly in the first days. The book notes that most reads are for recent mail, about 82 per cent for mail under a week old.
- Bodies are infrequently read, but vary from small to large.
- Almost every action touches one user's mail only: list folders, mark read, search.
- Loss is not acceptable.
Which store? A relational database is poor for large, unstructured bodies and big text search. Plain object storage is good for backup, but cannot mark read or thread easily. A large NoSQL column store fits best, and big providers often build their own. Gmail uses Bigtable. In an interview, name the properties the store needs and not a product: a single disk-friendly store per user, strong consistency per mailbox, and support for a partition key and a sort key.
Partitioning. Use user_id as the partition key, so all of one user's data lives on one shard. The cost is that a message shared by many users is stored once for each.
Tables (sketch).
folders_by_user(user_id, folder_id, name): all folders of one user.emails_by_folder(user_id, folder_id, email_id, from, subject, preview, time): key is the composite partition (user, folder), andemail_idis the sort key (a time-based id, so the newest comes first).emails_by_user(user_id, email_id, ...): the full message by id, with body and headers.attachments(email_id, filename, object_reference).
Read and unread. The store only answers queries by partition key and sort key. A query for "all unread mail in a folder" cannot filter on a normal column. The fix is denormalisation: keep two tables, read_emails and unread_emails. Marking a message as read deletes it from one and inserts it into the other. This makes the code more complex but the reads fast.
Threads. A reply carries the id of the message it answers (headers In-Reply-To and References). A client can rebuild a conversation from them.
Consistency. Email must be correct, so each mailbox has a single primary copy. If the primary fails, the mailbox is unavailable for a short time until failover. This favours consistency over availability, which is acceptable for mail.
A worked example (made up). A user opens the inbox. The query is "give the 50 newest rows for (user 7, folder inbox)". It reads one partition, and the newest rows come first because of the sort key. The cache already holds those rows, so the page returns in a few milliseconds.
Read it as
In a key-based store, the queries come first and the tables follow. List the queries, then design one table for each.
Check yourself: 1. What is the partition key and why? 2. How is "unread in this folder" answered? 3. What does the single primary trade away?