Ch.10: System Design: Autocomplete in 100 Milliseconds

0:00 Welcome to Learning Podcasts. System Design for Backend Engineers: Autocomplete in 100 Milliseconds. The tiny search box is a brutal distributed-systems test. One letter goes in, and before the user notices anything, the backend has to retrieve candidates, rank them, filter them, personalize them, and send back something useful. And it has to do that again on the next letter. Then again on the next one. The whole feature lives inside a deadline the user never sees. Exactly. If the box feels instant, the architecture is doing a lot of quiet work.

0:33 Start with the finished map. The read path runs from client typeahead to edge cache, gateway, sharded prefix-index nodes, ranking, personalization, then deny-list and legal filter. The write side is separate: logs stream in, the batch aggregator groups by prefix, the builder publishes segments, and replicas roll them out. What matters is that the map has two rhythms. Reads happen on every keystroke. Writes happen in batches, because rebuilding on every keypress would turn serving into a construction site.

1:10 Keep that split in mind. We will unpack the boxes, then come back when the tradeoffs have names. One user types one letter. The timer starts before the request even leaves the device. The hundred milliseconds includes the network hop, gateway routing, prefix lookup, ranking, filtering, and the return trip. So the data structure cannot spend 90 milliseconds and call itself fast. Right. And the budget repeats for every character. 5 letters is 5 requests, not one slow request with 5 steps inside it.

1:43 That is why autocomplete failures feel weirdly personal. The page is not down. The box just hesitates after every keypress, and suddenly the product feels heavy. The first tempting answer is, Precompute everything. For every query anyone has typed, store every prefix and its best completions. Then serving is a lookup. That sounds good until the index turns into a warehouse of nearly-duplicate prefixes. Exactly. The second tempting answer is the opposite: keep the query log as truth and scan it on every keystroke.

2:20 That saves precompute work and loses the latency budget immediately. So one answer explodes memory and rebuild cost. The other answer explodes serving latency. Autocomplete is the compromise between those failures, not a cute search-box feature. Let us pin down the functional requirements before picking data structures. The system has to accept a prefix from a typeahead UI, return a ranked list of completions, support multiple languages and writing systems, and learn from query logs because user behavior is the signal.

2:53 Right. It is not returning every string that starts with the prefix. It is returning a small ranked answer that reflects what people actually search for. And that distinction is important. A dictionary lookup can be complete and still useless. Autocomplete has to be selective. It is a product contract, then: the right few suggestions, not the theoretically complete set. Safety and control are product requirements too. Filter offensive, dangerous, and legally problematic terms. Personalize from recent history when available.

3:27 Expose admin controls for deny lists, takedowns, and curated boosts. And keep explainability, even if the user never sees it. When someone asks why a suggestion appeared, the system should answer with the source: popularity, recency, personalization, or manual boost. Otherwise the team ends up staring at a dropdown and guessing which part of the system made the decision. Exactly, and those special cases become permanent. Non-functional requirements are where autocomplete gets strict. End-to-end latency has to stay under one hundred milliseconds at a high percentile, not just at the median.

4:07 Availability has to be very high because the box is on every search page. Freshness needs to be minutes, not days, for trending terms. And policy filtering has to stay correct even when the cache misses or the index is slightly behind. That last point is easy to underweight. If a banned suggestion comes back fast, it is not a successful request. It is a fast failure. Exactly. Correctness includes what you refuse to show. The rest of the non-functional requirements protect the fleet. Write amplification has to be bounded because the logs never stop arriving.

4:46 Replica cost has to stay controlled. Hot prefixes need isolation so one trending query does not pin one shard. And observability has to split by path. Ingest lag on the write side, cache hit rate and tail latency on the read side, ranker time in the middle, filter drops at the gate. Right. A healthy average can hide a sick prefix. You need per-prefix dashboards because the distribution is not smooth. That is the recurring theme: the user types evenly, but the world searches in bursts. And the architecture has to be ready for the burst, not the average.

5:20 The serving index is usually modeled as a prefix tree or a compact finite-state transducer. The useful idea is simple: each step follows the next character in the prefix, and the node you land on already stores the top completions and counts. So the query path is not sorting the universe. It is walking to a node and reading a prepared answer. Exactly. The expensive work moved to index build time. That is the whole reason the read path can stay small enough for the budget. But the prepared answer cannot be final-final, right?

5:53 We still have personalization and filtering later. Right. The prefix tree gives you strong candidates quickly. It does not replace the rest of the serving pipeline. One giant prefix tree is not the plan. The gateway shards by prefix range. Maybe a to c goes to one group, d to g to another. Routing is cheap because the first few characters pick the range. But the alphabet is not traffic-balanced. If a celebrity name or breaking-news term starts with one prefix, that range gets hammered. Exactly. You split heavy ranges finer, add replicas for hot prefixes, or send that hot range to several servers.

6:35 This is the distributed-cache hot-key problem in a different costume. So sharding gives you a map, but the live traffic decides where the pressure is. Ranking starts with global popularity: across all users, how often does this prefix complete to this query. Then recency boosts terms that just spiked. A product launch, a sports result, a news event. And then personalization bends the list toward this user, if we have enough signal and permission to use it. Yes, but that split matters. Global popularity and recency are shared.

7:10 They can be cached and precomputed. Personalization is per-user, so it is much harder to cache at the edge. The popular head is cheap because everyone shares it. The personalized tail is expensive because it has to be earned one request at a time. That is the clean way to think about it. Cache the head. Rank the tail. Filtering cannot live only inside the index build. A query can be acceptable at noon and banned at one. So if the index was built at noon, the serving layer still needs a current deny-list and legal-list check.

7:46 Exactly. Build-time filtering keeps the index cleaner. Serve-time filtering is the safety net. You need both because freshness and safety move on different clocks. And the serve-time filter has to run after ranking, before the response leaves. Right. A suggestion is not eligible until it survives the gate that exists now, not the one that existed during the last build. The update path starts with query logs. Every accepted search emits an event into a stream, like the queue pattern from the message-queue episode.

8:19 So the logs do not mutate the serving index directly. Correct. A batch aggregator groups events by prefix on a minute-level cadence, computes new counts and recency boosts, then the index builder publishes fresh segments to replicas. That means the index is a published artifact, not a shared object every request is trying to edit. Exactly. Per-keystroke mutation would make the serving nodes noisy. Minute-level publishing is fresh enough for trends and calm enough for reads. The user experiences it as live, but operationally it is controlled batch freshness.

8:53 In front of the service, an edge cache holds the most popular prefix answers. This is the caching episode's lesson in a sharper latency budget: the best request is the one that never reaches the core service. But only the shared answer belongs there. Right. If the prefix is hot and the answer is mostly global, the edge can return it in single-digit milliseconds. If the answer depends on the user's recent searches, the request goes through gateway, index, ranking, and filter. So the cache is not a magic speed layer.

9:24 It is a bet that many users want the same popular completions. Exactly. When that bet is true, the cache protects the entire backend. Three quiet rules decide whether this feels reliable. First, isolate hot prefixes before one range becomes a line outside one shard. 2Nd, late deletes: serve-time filtering still drops banned terms after the last build. Third, autocomplete does not paginate. Ranking mistakes are immediately visible. And the dashboards have to match those rules: write-side ingest lag, read-side latency, filter drops, and per-prefix hot spots.

10:05 Not one blended success graph. Exactly. Averages make autocomplete look healthier than it is. The user only feels the prefix they typed. Now return to the map. Typeahead hits the edge cache first. Hits protect the core. Misses go to sharded index nodes. Those nodes hold prefix trees or finite-state transducers with prepared candidate lists. Build time keeps serving to one walk and one read. Ranking adds popularity, recency, and user context. Serve-time filters apply current deny-list and legal-list rules before the answer goes back.

10:44 Update traffic stays separate: logs, batch aggregator, index builder, and replica rollout. That separation is the point. Reads stay predictable. Writes absorb churn in batches. The design is easier to remember as four limits. Precompute enough. Cache the head. Rank the tail. Update in batches. Right. Precompute enough so the index can answer a prefix quickly. Cache the head so popular shared queries avoid the core service. Rank the tail when personalization actually matters. Batch updates so freshness does not destabilize serving.

11:20 And the tradeoff is honest. Spend memory where it protects latency. Accept minute-level freshness when instant freshness would hurt the read path. Filter late because safety cannot wait for the next build. That is production autocomplete. The search box stays fast because the architecture is disciplined. Nicely put. Autocomplete is not a search engine squeezed into a dropdown. It is a read-optimized system that precomputes the right amount, caches the shared head, ranks the personal tail, and keeps safety checks current at serve time.

11:52 Next video, we move from a hundred-millisecond text box to video streaming, where the system has to keep playback smooth across devices, networks, and storage tiers. Thanks for listening to Learning Podcasts.