Ten suggestions before your next keystroke, with nothing computed

transcript

Type s, y, s. Ten suggestions appear before your next keystroke. The server computes none of them. Here's why it can't.

From keystroke to screen, you get 100 milliseconds. The whole trip. Network and browser eat most of it. The server gets 10 to 20. About 70,000 times a second. So the server can only look an answer up.

You say trie. A plain trie finds s, then y, then s. Three steps. But the best ten? You'd walk the whole subtree below. For a short prefix, millions of nodes. So precompute. Offline, every node stores its own top 10. Online, walk one node per letter, and return that list.

Root, then s, then s y. Then s y s. System design, sysadmin, and the rest. Already sitting there. The millions of nodes below? Never touched while you type.

Here's the twist. The ranking still happens. Just not now. An offline builder ranks billions of past searches. Servers load its snapshot.

Two systems in one. An offline path that decides. An online path that looks up. Nothing is computed while you type.

Full breakdown in the lecture.