Design Search Autocomplete

Assume 3 billion searches a day. With debouncing, a typical search produces about six suggestion requests before the user picks a suggestion or presses enter. Browsers and the CDN answer about half of those from cache, mainly for short, popular prefixes.

Three paths make up the system. The request path is a fleet of suggest servers, each holding complete in-memory indexes for its region's locales. A request does a single lookup of the normalised prefix, gets back ten phrase ids with scores, merges a few trending entries and returns. Nothing on this path touches a disk or another service.

The batch path runs every six hours. It reads the search event log, counts each phrase with time decay, removes anything that fails safety and privacy filters, and produces a new index file per locale. Servers download the new version, load it alongside the old one, and switch atomically. The streaming path watches the same events in near real time, spots phrases whose rate has jumped far above their usual level, and publishes a small trending overlay that servers merge at query time.

Start with a trie of all eligible phrases, each leaf carrying a score. Walk it bottom up once: each node's top ten is the best ten among its own phrase, if it ends one, and its children's top tens. That merge is cheap because every child list is already sorted and short. After the walk, a query for any prefix is a descent of at most a couple of dozen characters and a read of ten ids, which is microseconds of work regardless of how many phrases share the prefix.

For serving, the tree shape itself is not needed. We flatten it into a hash table from prefix string to a list of ten phrase ids, plus a phrase table from id to text. We also skip storing lists for deep prefixes with very little traffic. If someone types a rare 30-character prefix, the server finds the deepest stored ancestor and filters its phrases, or returns nothing. That cut takes the index from billions of prefixes to about 300 million.

Raw counts favour phrases that were popular for years and miss what people want today. Each event adds weight that decays with a half-life of about a week, so a phrase searched heavily in the last few days outranks one searched evenly over two months. We count distinct users, not raw events, so one script repeating a query cannot push it up. Clicks matter too: a suggestion that is shown often and rarely chosen gets demoted, which removes completions people find useless or embarrassing.

The browser or app does more than draw a list. It waits for a short pause in typing before sending, and it cancels any request whose prefix the user has already typed past, so stale answers never flash on screen. It keeps a small in-memory cache of recent prefixes, so backspacing is instant. When a response arrives flagged as complete, meaning fewer than ten phrases exist under that prefix, the client can answer every longer prefix by filtering that list locally without calling the server at all. On mobile networks, where a round trip can take 200 ms on its own, the app may also prefetch the next likely prefix in the background while the user is still reading the list.

Normalisation has to match on both sides. The server lowercases, trims repeated spaces, folds accents and applies script-specific rules, and the client applies the same rules before checking its cache. For languages written without spaces, or typed through an input method that composes characters, the client sends the composed text rather than raw keystrokes, and the index is built over the same units.

Rebuilding a 19 GB index every few minutes is wasteful, and most of it would not change. Instead, the streaming detector keeps a sliding count per phrase over the last 10 minutes and compares it with the same phrase's usual rate for that hour. A phrase whose rate is many times its baseline, from enough distinct users, enters the overlay with a boost that fades over a few hours. The batch job eventually absorbs real trends into the main index, and the overlay entry expires. The risk is manipulation: coordinated accounts can try to fake a trend, which is why overlay entries need a distinct-user floor and pass the same safety filters as everything else.