Part 7 of 8 · 2 min read
Scale and follow-ups
Spread the trie.
Sharding, trade-offs and follow-ups
Sharding. When the trie does not fit on one server, split it. The simplest rule is by first letter: a to m on one server, n to z on another, and so on up to 26 servers. Going further, split by the second letter. The problem is imbalance. Many more queries begin with "c" than with "x", so some servers hold far more.
The book's fix is a shard map manager: a lookup table that records which prefix ranges live on which server, built from the history of query counts. If "s" alone has as many queries as "u" to "z" together, then "s" gets one shard and "u" to "z" gets another.
| Choice | Gain | Cost |
|---|---|---|
| Top k cached at each node | Very fast reads | More memory |
| Weekly rebuild | Cheap, simple | Stale for trending terms |
| Browser cache | Fewer requests | Slightly old suggestions |
| Sampling | Less logging cost | Counts are approximate |
| Shard by smart ranges | Even load | A map to maintain |
Interview angle
Answer in your head first, then open it.
Which structure?
A trie with the top k cached at each node.
How do you keep it fresh?
Rebuild offline from aggregated logs and swap it in.
How do you remove bad suggestions?
A filter layer now, and a data clean-up for the next build.
What if one server is too small?
Shard by prefix ranges using a shard map.
What is the speed limit?
About 100 ms for the whole answer.
Follow-ups from the book.
- Other languages. Store Unicode characters in the nodes instead of only the 26 letters.
- Different results per country. Build one trie per country, and place them near users, for example on a CDN (Level 1).
- Trending queries. The weekly build is too slow for a breaking story. Ideas: shard to shrink the data each job handles, weight recent searches more, and use stream processing (Level 6) to update counts continuously.
One follow-up to try. "A new event makes a term trend right now." A good reply: keep the weekly trie, and add a small second structure of recent counts built from a stream, updated every minute. The query service merges the two lists, giving extra weight to recent counts. The big trie stays cheap, and only the small part changes fast.
Check yourself: 1. Why is first-letter sharding uneven? 2. What does the shard map manager do? 3. How can the design show trending queries?
Words you will meet
| Word | Meaning |
|---|---|
| Autocomplete | Suggesting completions while a user types |
| Top k | The k highest-scoring items |
| Trie | A tree where each step adds one letter |
| Prefix | The first letters of a string |
| Aggregator | A job that combines raw records into totals |
| Sampling | Logging only some of the events |
| Filter layer | A step that removes unwanted results |
| Shard map | A table of which data lives on which server |