Design Gmail Fast Search
Search billions of mailboxes — inverted index per user, sharding, and instant query completion.
Interview tip User mailbox shard, inverted index segments, async indexing on delivery, prefix suggest trie + ranking by recency.
① Functional requirements
- Full-text search in mailbox
- Filter by sender, label, attachment, date
- Autocomplete query suggestions
- Search as you type
- Snippets with highlights
- Include spam/trash optional
② Non-functional requirements
- p99 < 200ms per user search
- Index new mail within seconds
- Petabyte total corpus
- Per-user data isolation
③ Back-of-the-envelope scale
Assumptions
- 1.5B users
- Sharding by user_id
- Average 10GB mailbox index overhead
④ High-level architecture
Gmail Search
Mail delivery
Per-user index shard
Query coordinator
Suggest trie
⑤ Data flow & execution path
Search query
Parse query→Route user shard→Intersect postings→Rank + snippet
CDC from mail store to index
Bloom pre-filter spam corpus
⑥ API & interfaces
| Endpoint / flow | Purpose | Notes |
|---|---|---|
| GET /mail/search | Query DSL | user auth |
| GET /suggest | Prefix complete | cached |
⑦ Data model & storage
Domain-specific entities sharded by user_id or geographic key.
| Store | What | Why |
|---|---|---|
| Distributed store | Primary data | Sharded for scale |
| Kafka / Pub/Sub | Event log | Async pipelines |
| Object store | Media / blobs | GCS-style durability |
⑧ Deep dive — core components
Per-user sharding
All mail for user_id on same index shard — query never cross-shard fan-out.
Ranking
BM25 + strong recency boost + personal signals (frequent correspondents).
⑨ Trade-offs & alternatives
| Decision | Option A | Option B | Pick when |
|---|---|---|---|
| Index | Per-user | Global | Per-user isolates blast radius |
| Suggest | Trie | ML rank | Trie fast; ML for quality |
⑩ 45-minute interview script
- 0–5 min: Requirements + Google-scale assumptions
- 5–12 min: Back-of-envelope QPS and storage
- 12–22 min: Architecture diagram
- 22–35 min: Deep dive on hot path
- 35–42 min: Failure modes and trade-offs
⑪ Likely follow-up questions
| Question | Short answer |
|---|---|
| How roll out globally? | Regional cells + gradual feature rollout |
⑫ Revision checklist
- User shard
- Inverted index
- CDC indexing
- Query DSL
- Suggest trie