CSE Roadmap

Core tier · about 4 hours · 8 parts

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