M4 Design Typeahead / Autocomplete

From rate limiting to typeahead: the same load problem, faster

Dr. Wei: Last time we designed rate limiting, which is really about surviving bursts and being fair under load. Today, typeahead is the perfect stress test: every keystroke is a burst.

Sam: So the big similarity is burstiness, but the difference is the user experience is interactive, so even small slowdowns feel obvious?

Dr. Wei: Keep token bucket and sliding window ideas in mind, because typeahead traffic is not just high volume, it is spiky and synchronized with user typing.

Sam: So the system is basically guaranteed to see mini bursts, even from a single user session, because each new character triggers a call?

Dr. Wei: Exactly. And the interview goal is: can you return top K suggestions, personalized and fresh, while staying under one hundred milliseconds end to end.

What we are building: suggestions faster than the next keystroke

Dr. Wei: This is one of those systems where humans set the latency bar: if the suggestions lag, the UI feels broken. So the stakes are very real: return results faster than the user can type the next character.

Sam: When you say faster than the next keystroke, is the mental model that we need p ninety nine under one hundred milliseconds, not just average, because people notice jitter immediately?

Dr. Wei: Scope wise, it is not just people. It is multiple entity types, which usually means multiple indices or a unified index with type filters.

Sam: And the part I always wondered about is why my friends show up before a celebrity even when the celebrity is globally more popular.

Dr. Wei: That is the ranking blend. And the last bullet is the forcing function: one hundred milliseconds end to end means we must precompute aggressively and keep query time work tiny.

Estimate the scale: every keystroke is a query

Dr. Wei: Before we do any math, pause and make a falsifiable guess: if typeahead sees about forty billion prefix queries per day, what is your order of magnitude for average queries per second? Commit to a range.

Sam: I would guess on the order of a few hundred thousand queries per second on average, maybe two hundred thousand to one million, because forty billion over a day is huge but the day is long.

Dr. Wei: Now we can reveal it: forty billion per day works out to roughly four hundred sixty thousand queries per second on average. If your estimate was high or low, it is usually because of forgetting there are eighty six thousand four hundred seconds in a day.

Sam: And peak is what kills you, right? Like lunch time spikes plus big live events, so you plan for around three times.

Dr. Wei: Exactly. Three times the average puts you around one point five million queries per second at peak. Then, separately, think about memory: if you have on the order of five billion entities, you cannot scan, so you keep a compact in-memory index. Even a rough budget like two hundred to six hundred bytes per entity for IDs, weights, pointers, and overhead gets you into the one to three terabyte range, which is why sharding and replication are part of the core design.

API and client behavior: control QPS before the server

Dr. Wei: At Meta, the best typeahead designs treat the client as part of capacity planning. You want fewer, higher quality queries, not a firehose of redundant prefixes.

Dr. Wei: The API needs the prefix, user identity, a limit, and often entity type filters so you can return mixed results or separate tabs without rebuilding the world.

Sam: Debounce and cancel sound like small UI tricks, but they directly reduce queries per second and tail latency during fast typing.

Dr. Wei: Right. And logging is non negotiable: you log what you showed and what was clicked, especially the position, because that is the training data for ranking and for trending detection.

Data model: split lookup, metadata, and personalization signals

Dr. Wei: This separation is a big Meta signal: the index is for fast candidate generation, and the entity store is for rendering. Do not overload the index with heavy blobs.

Sam: So I should think of the index as just a fast pointer structure, and the entity store as the place that holds the full details the UI needs to show.

Dr. Wei: The prefix index only needs to answer: for this prefix, what are the best candidate IDs, usually top K, using global signals that are easy to precompute.

Sam: Then you fetch metadata from the entity store so the payload can include the display name, subtitle, and image, without the trie having to store all that.

Dr. Wei: Exactly. And personalization signals are separate again, because they are per user and dynamic: recent searches, friend affinity, and also safety features like blocks and privacy constraints.

High-level architecture: candidate generation, then ranking

Dr. Wei: This is the core shape interviewers want: generate a small candidate set fast, then spend a little compute to rank it. If you try to rank the whole world, you lose instantly.

Dr. Wei: The online path goes through the edge and gateway into a dedicated typeahead service, because you want specialized timeouts, caching, and load shedding policies.

Sam: Parallel reads are the only way to hit the budget: pull from the prefix index, user signals, and trending at the same time, then merge.

Dr. Wei: And the final step is rank and filter: blend scores, enforce privacy, then return top K. That separation makes graceful degradation easy when one input is slow or down.

Prefix index deep dive: sharded, replicated, and compressed

Dr. Wei: Now we zoom into the prefix index. The whole point is that work scales with the prefix length, not with the number of entities in the corpus.

Dr. Wei: On each query, you traverse characters in the prefix, then read a precomputed top K list at that node. That is what buys you predictable latency.

Sam: But the index is too big for one machine, so first we route a query by its first two or three normalized characters using a directory or consistent hashing, then we shard by prefix range and replicate so reads stay fast even if a node is unhealthy.

Dr. Wei: Right. And memory discipline matters: use radix compression to reduce nodes, and store IDs plus small scores, not heavyweight profiles.

Personalized ranking: blend global, social, and recency

Dr. Wei: Personalized ranking is about combining multiple signals into one final ordering, instead of pretending any single signal is always right.

Dr. Wei: The equation is a weighted blend: global popularity, social affinity, and recency. Prediction check: if we double gamma, which results move up or down, and why?

Sam: So in practice, I pull candidates from the global top K, then inject user specific candidates like recent searches and friends who match the prefix, then re rank the union. For example, if candidates are A, B, and C, and C is the most recent, doubling gamma should push C up even if A is more globally popular.

Dr. Wei: Exactly. Mini example: suppose A has strong global score but is stale, C is very recent, and B is in between. Doubling gamma lifts C above A because the recency term contributes more to the total score. And when one signal is missing, like social timing out, treat it as zero or fall back to a cached value, then safely return results using the remaining signals under a hard latency budget.

Trending: a fast-moving boost layer

Dr. Wei: Trending is a separate concern because it changes faster than your main index rebuild cadence. Think of it as a small, hot overlay.

Dr. Wei: You usually start from logs: count queries in a sliding time window, like the last hour, so you respond quickly to events like the Super Bowl.

Sam: Then you compare against a baseline, and if it is over three times, you mark it trending so the ranker can boost it even if it was not usually popular.

Dr. Wei: And serving wise, keep it tiny and cacheable: a small side index and a short TTL, because trending rotates quickly and stale boosts are worse than no boosts.

Typo tolerance: expensive, so use it as a fallback

Dr. Wei: Typo tolerance is where many candidates over design. The IC6 move is to make it conditional, because fuzzy matching can explode your cost.

Dr. Wei: A common pattern is: if exact prefix matching returns too few candidates, then and only then you trigger the fuzzy pipeline.

Sam: Checkpoint: I would cap it pretty aggressively. For example, allow edit distance at most 1 when the prefix is 4 characters or fewer, cap fuzzy candidates at 200, and give the fuzzy path a 5 to 10 millisecond wall clock budget, sized to whatever is left from your end to end latency after network and the rest of the services.

Dr. Wei: Yes, that is the right kind of operational thinking. Then tune those caps to your latency goals: if your end to end budget is, say, 50 milliseconds and 30 milliseconds is already spent on network and other calls, keeping fuzzy to 5 to 10 milliseconds of wall clock time makes sense, and you can tighten further on short prefixes or under load by lowering the candidate cap or requiring distance 1 only.

Freshness, caching, and graceful degradation

Dr. Wei: This is the operational checklist interviewers probe on: can your system stay useful when parts are stale, slow, or down.

Dr. Wei: First, make the indexing path explicit: you do periodic batch rebuilds to generate a fresh shard snapshot, and you also run a delta stream consumer that applies new and changed terms onto each shard replica between rebuilds, typically within seconds end to end.

Sam: And caching is layered: edge caching for globally hot prefixes, and a fast cache for per user recents so personalization does not hit storage every time.

Dr. Wei: Finally, degrade and protect: if user signals fail, return global results; and if load spikes, apply token bucket and shed with HTTP 429 so the system stays responsive for everyone.

Tradeoffs Meta cares about: cost, latency, and correctness

Dr. Wei: Now we evaluate. Meta interviewers look for explicit tradeoffs with costs, not just a list of components.

Dr. Wei: First tradeoff: keeping the trie in memory buys latency, but it costs real money in multi terabytes of RAM, so compression and careful sharding are mandatory.

Sam: Second tradeoff: if I precompute top K lists, reads are fast, but I risk missing fresh items and per user ordering unless I add overlays like recents and trending.

Dr. Wei: And that is the level calibration: IC4 is getting it working, IC5 is making it scale reliably, and IC6 is enforcing latency budgets, adding overlays and guardrails, and describing safe rollout strategies.

Exit ticket: do the math, then choose a design lever

Dr. Wei: Let us lock in the skill Meta is grading: numbers drive design. We will compute peak queries per second from a few simple assumptions.

Dr. Wei: Here is the legend: U is daily active users, s is searches per user per day, k is keystrokes per search which become prefix requests, and p is the peak to average multiplier. The average query rate equals U times s times k divided by eighty six thousand four hundred, and the peak query rate equals p times the average query rate.

Sam: So if peak doubles, my first instinct is to increase debounce a bit and lean harder on edge caching for hot prefixes, because those reduce queries per second without changing relevance.

Thank you for watching!

Thanks for watching. Subscribe and share if you found this useful—see you next time!