Part 1 of 8 · 1 min read
Why this page comes third in Level 11
In this module you will
- Scope an autocomplete system and estimate its request rate and daily data growth.
- Explain a trie, and why caching the top results at each node makes reads fast.
- Split the system into a data gathering path and a query path.
- Describe how the trie is built, stored, cached, updated and cleaned of bad suggestions.
- Shard the trie so that no server gets far more than its share.
Autocomplete has an unusual shape. Reads are extremely frequent and must finish in a fraction of a second, while the underlying data changes slowly. That makes it a clean case for building a read-only structure offline and serving it from memory. It also applies sharding (Level 4), caching (Level 3) and batch jobs (Level 6) to one small problem. The book used is "System Design Interview" by Alex Xu, chapter 13. Numbers marked "made up" only show the idea.