The Search Bar That Stalled on Every Keystroke
The Search Bar That Stalled on Every Keystroke
Your global streaming platform serves 80 million daily active users. As users type into the search bar, the UI sends a request for every keystroke to return the top 5 suggested movie and artist titles within an aggressive 25ms SLA. The search phrase catalog contains 40 million distinct historical query phrases. The original implementation built an in-memory Trie where each node represents a character. On every keystroke, the service traverses down the trie to the prefix node (e.g. mar), performs a Depth-First Search (DFS) over the entire subtree to gather all matching child words, and sorts them by historical popularity score using a min-heap. At 60,000 keystroke queries/second, CPU utilization spikes to 98%, p99 latency degrades from 15ms to 380ms, and queries for short 1-to-2 character prefixes (a, th, sh) frequently time out because their subtrees contain over 800,000 child nodes. You are asked to redesign the autocomplete architecture to serve sub-10ms suggestions at scale without deep subtree traversals.
The Search Bar That Stalled on Every Keystroke
Your global streaming platform serves 80 million daily active users. As users type into the search bar, the UI sends a request for every keystroke to return the top 5 suggested movie and artist titles within an aggressive 25ms SLA. The search phrase catalog contains 40 million distinct historical query phrases. The original implementation built an in-memory Trie where each node represents a character. On every keystroke, the service traverses down the trie to the prefix node (e.g. mar), performs a Depth-First Search (DFS) over the entire subtree to gather all matching child words, and sorts them by historical popularity score using a min-heap. At 60,000 keystroke queries/second, CPU utilization spikes to 98%, p99 latency degrades from 15ms to 380ms, and queries for short 1-to-2 character prefixes (a, th, sh) frequently time out because their subtrees contain over 800,000 child nodes. You are asked to redesign the autocomplete architecture to serve sub-10ms suggestions at scale without deep subtree traversals.
Provide 1–2 precise sentences for each architectural dimension. Each box guides you on what staff-level interviewers evaluate.
Define SLA targets, hard consistency constraints, and conditions the system must never violate.
Quantify throughput (QPS/RPS), read:write ratios, and peak burst multipliers.
Step-by-step path: client ingress → API gateway → queues → background workers → persistence.
Database engine, table schema, partition keys (PK/SK), and durability strategy.
What resource hits saturation first under 10x traffic? (CPU, disk IOPS, connection pools, network).
Worker crashes, network partitions, split-brain, poison pill DLQ, retries, and idempotency.
What did you sacrifice in exchange and why? (e.g. eventual consistency vs latency, cost vs redundancy).