Design search autocomplete
A hundred thousand keystrokes a second, each wanting ten suggestions inside a tenth of a second. You get there by doing the ranking once an hour, offline, so a lookup is a walk of a few nodes and never a sort.
The round this design follows
Why store the top ten at every node instead of searching the subtree?
Because the subtree under a short prefix is enormous. Under one letter sit, on average, 384.6 thousand of the ten million queries, and ranking that many on every keystroke cannot fit in a 100 ms budget. Storing each node's top ten when the trie is built turns a lookup into a walk of at most twenty nodes and a list that is already sorted. The cost moves to the build and to memory, and both are cheap at this size.
Does the trie need to be sharded?
Not at this prompt. An upper bound of 200 million nodes with ten query ids each comes to about 21 GB, and even with a second copy loading during the hourly swap that is 42 GB, inside a 64 GB box. So every trie server holds the whole trie and you add replicas for load. The headroom is only about one and a half times, so you name the shard key now, the first letters in ranges cut by traffic, and turn it on when the query count grows by half.
How fresh are the suggestions?
The trie is rebuilt every hour from the query log, and the cdn keeps an answer for ten minutes, so a suggestion can be up to about seventy minutes behind what people are searching. That is a product decision the prompt made when it said hourly rebuilds. If trending queries must show within minutes, the usual answer is a small overlay of fast-rising queries merged into the answer at the api, not a faster rebuild of the whole trie.
Why put a CDN in front of an autocomplete API?
Because the answers are the same for everyone for a whole hour. A prefix like "wea" has one list of ten suggestions until the next rebuild, so an edge cache keyed by the prefix can answer it without touching the origin. On this page the assumption is that the edge answers half the lookups, which halves the 100 thousand a second at the peak to 50 thousand at the origin. Personalised suggestions break that, which is why they are usually a second, smaller request.
What happens when a trie server dies?
The api stops sending it lookups once its health check fails, and the other servers take its share. With eight servers for a load that needs a little over six, losing one leaves 56 thousand lookups a second of capacity against 50 thousand at the origin, so nothing waits. Losing a second one at the peak does make a queue, and suggestions arrive after the user has typed the next letter, which is why the fleet is sized with one spare, not zero.