System design deep dive · HLD
Design a search autocomplete / typeahead system: full high-level design.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for the online lookup and offline rebuild paths, and an entity-relationship diagram for the supporting data model - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
Autocomplete looks like a small feature bolted onto search, but it has its own request pattern (every keystroke, not every submitted query) and its own freshness contract (near-real-time is fine; the base ranking can lag by hours). Pinning both down changes every diagram below.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide whether a database can even be on the hot path (it can't), how many trie shards are needed, and how much memory the whole serving fleet needs. Scope: a large e-commerce/search product doing roughly 500M full searches/day - not the ~8-9B/day scale of a global web search engine.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Search volume | 500M searches/day | 500M ÷ 86,400s ≈ 5,800 QPS average, ≈17,400 QPS peak (3× diurnal) |
| Autocomplete request volume | Fires per keystroke after a ~150ms debounce; ≈4× search QPS net of debounce savings | ≈23,000 QPS average, ≈70,000 QPS peak |
| Query log volume (90-day rolling window) | 500M/day × 90 days, ≈120 bytes/row (text + user_id + timestamp + flag) | 45 billion rows ≈ 5.4 TB raw log storage |
| Distinct historical query strings | Heavy repetition, ≈1 distinct string per 150 searches | 45B ÷ 150 ≈ 300 million distinct queries; top 20M cover ≈95% of autocomplete traffic |
| In-memory trie size | Top 20M queries, compressed/radix trie (shared prefixes collapse the tree ≈4-5×) ≈80M nodes, ≈180 bytes/node (char + child pointers + cached top-10 completions) | 80M × 180B ≈ 14.4 GB total trie |
| Shard count | Shard by first 2 characters of the prefix, consolidated into 32 practical shards (≈450MB each), replicated 3× per region × 2 regions | 32 × 3 × 2 = 192 shard-replica instances, each a small fraction of one host's RAM |
3. High-level design (HLD)
The HLD names the major components and the one-directional data flow between them - the online read path that serves keystrokes, and the offline pipeline that keeps the trie's rankings fresh - without committing yet to replica counts or regions, which belongs in the architecture diagram next.
What each box owns
Autocomplete service (read path)
Accepts the raw prefix, hashes/routes it to the trie shard responsible for that prefix range, reads the precomputed top-K list already sitting at that trie node, asks the trending counter for a boost score, merges the two into a final ranked list, and returns it. It never touches a database and never blocks on the offline pipeline.
In-memory trie shards
Each shard owns a contiguous prefix range (e.g. "a-c") and holds a trie where every node already caches its own top-K completions, computed at build time. Shards are replicated across nodes and regions purely for read fan-out and availability - there is no write traffic to them at request time.
Query log ingestion & trending counter
Every completed search from the search service is written asynchronously into the query log - this never blocks the user-facing search response. A streaming job continuously aggregates the last few minutes of that log into a small "trending terms" table, catching spikes (breaking news, a flash sale) long before the next batch rebuild would notice them.
Offline batch aggregation & trie builder/publisher
A scheduled job (daily, or hourly for a fresher base ranking) re-aggregates the full query log window, recomputes frequency counts, ranks and truncates completions per node, and hands the result to a builder that constructs new trie shards and publishes them to serving nodes without ever taking the read path offline.
4. Detailed architecture diagram
The architecture diagram splits the system along its most important seam: an online serving path that only ever reads an immutable, replicated, in-memory trie, and an offline build pipeline that produces the next version of that trie and swaps it in - plus a real-time trending path merged in at read time for freshness the batch pipeline can't provide fast enough.
| Decision | Choice | Reasoning |
|---|---|---|
| Rebuild strategy | Offline batch rebuild + a merged real-time trending overlay, not online incremental trie updates | Recomputing global ranks incrementally on every write is complex and error-prone at 23k+ QPS; batch keeps ranking logic simple, and the trending layer covers the freshness gap batch can't. |
| Sharding scheme | Prefix-range sharding (first N characters), not consistent hashing of the full query | Prefix sharding keeps every completion for a given prefix on one shard, so a lookup never fans out across the cluster; consistent hashing would scatter completions for "lap" across many nodes and defeat per-node top-K caching. |
| Data structure | In-memory trie with cached top-K per node, not a sorted string table or ternary search tree | A trie gives O(prefix length) descent to the answer with zero extra ranking work at request time; a TST saves some memory but adds comparison overhead per character, and a sorted list needs a binary search plus a scan to collect the top-K on every request. |
| Multi-region replication | Read-only replicas per region, no cross-region write path | Because the trie is immutable between versions, "replication" is just shipping the same published artifact to every region - none of the write-conflict problems a live multi-region database would have. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether you understand exactly which hop is on the synchronous, latency-critical path and which hop is asynchronous - and here, whether you understand that the trending merge is a second, parallel lookup rather than a blocking chain.
5.1 Online lookup (keystroke to dropdown)
Step 3 is a single hop because the trie shard already stored the top-K completions at that exact node when it was built - there is no subtree traversal at request time. Steps 5-6 run in parallel with (or shortly after) step 3 against a tiny, separately-hosted trending cache, not the trie itself, so a slow trending lookup never blocks the base result; a request that times out on step 6 simply merges with a zero boost.
5.2 Offline pipeline (log to published trie)
Step 3 is the step that actually keeps the trie fast: ranking and truncation happen once, offline, per node - not once per request. Steps 7-9 are drawn as a poll-and-pull rather than a push specifically so a slow or unreachable serving node can catch up on its own schedule without the publisher needing to track per-node delivery state; the blue-green swap in step 9 guarantees no in-flight lookup ever reads a half-loaded trie.
6. Entity-relationship diagram and schema
The hot path never touches a schema at all - it reads an in-memory trie. But three supporting tables exist around that trie: the raw log the rankings are computed from, a small hot table for trending spikes, and a control-plane table that tracks which trie version is published where.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Columnar/log store (Kafka + data lake, or a wide-column store) for query_logs | Ingest volume is enormous (23k+ writes/sec) and the only access pattern is append plus full-window batch scan. | Terrible for point lookups; never query this table on the request path, only from the batch job. |
| Relational store (Postgres) for trie_shards metadata | You need simple, consistent queries by shard_id or prefix_range and an audit trail of published versions. | This table is tiny and never on the hot path - don't over-engineer it, it exists purely for the control plane. |
7. Deep dives interviewers actually probe
How does a single trie lookup return ranked suggestions without scanning a subtree?
The naive approach - descend to the prefix node, then walk the entire subtree beneath it collecting and sorting every completion - is far too slow for a <50ms budget on a popular one- or two-character prefix with millions of descendants. Instead, the top-K completions are precomputed and cached directly on every trie node at build time, so a request only has to descend to the node (O(prefix length)) and return the list that's already sitting there.
// Build time: propagate top-K up from leaves, cheapest first
struct TrieNode {
children: Map<char, TrieNode>,
topK: Vec<(String, u64)> // precomputed, sorted by score desc
}
// merge child topK lists into the parent, keep only the best K
fn buildTopK(node) {
for child in node.children.values() { buildTopK(child) }
node.topK = mergeAndTruncate(node.children.values().map(c => c.topK), K)
}
// Request time: O(prefix length), no traversal, no sorting
fn lookup(prefix) -> Vec<(String,u64)> { descend(prefix).topK }Offline batch rebuild vs online incremental updates - why not update the trie live?
Updating the trie live on every search would mean recomputing per-node top-K lists on the write path, which is exactly the kind of global, order-dependent aggregation that's hard to do correctly and cheaply at 23k+ QPS - a single popular query jumping in rank can touch every ancestor node up to the root. Batch rebuild sidesteps this entirely: ranking is recomputed from scratch on a schedule, which is simple, easy to test, and easy to roll back (just don't publish the new version). The cost is that a brand-new trending query can't appear until the next batch run - which is exactly why the trending counter exists as a separate, much cheaper real-time overlay merged in only at read time, rather than trying to make the trie itself real-time.
How would you add personalization without blowing up the index?
A per-user trie is a non-starter - it would multiply the 14.4GB base index by however many active users exist. Instead, personalization is layered on as a thin re-ranking step that runs after the global top-K comes back: a small client-held or session-scoped list of the user's own recent queries (tens of entries, not millions) is used to boost or re-order matching completions, or to prepend an exact recent-query match ahead of the global ranking. This keeps the expensive, shared part of the system (the trie) completely user-agnostic while still giving each user a noticeably personalized-feeling result.
How do you keep offensive or embarrassing suggestions out of the dropdown?
Filtering happens in the offline pipeline, before anything is ever published: the batch job runs candidate completions through a denylist/classifier stage and drops or suppresses matches before the trie builder ever sees them, so a bad suggestion never reaches a serving node in the first place. Because that only runs once a build cycle, a fast-path emergency denylist (a small, frequently-refreshed set the autocomplete service checks in-line) is also needed so a suggestion that suddenly turns embarrassing can be suppressed within minutes rather than waiting for the next scheduled rebuild.
What is the single biggest bottleneck as this scales 10x?
Not the trie build - that's an offline batch job and can simply run on a bigger cluster or more often. The real pressure is on the online serving fleet: 10x the QPS (roughly 700k peak) needs 10x the read fan-out, and the 14.4GB trie itself would also grow well past 100GB if query diversity grows with traffic. The fix is the same lever twice - add more replicas per shard to absorb QPS, and split shards more finely (e.g. 3-character prefixes instead of 2) to keep each individual shard's memory footprint and hot-key skew manageable, rather than trying to make any single node bigger.
Post a Comment
Add