Design a Search Autocomplete System
Type into Google's search box and suggestions appear instantly. This feature is called autocomplete, typeahead, search-as-you-type or incremental search. The question is usually phrased as: "design top k" or "design the top k most searched queries".
- 13.1Requirements and estimationMatch only at the beginning of a query; return the top 5 suggestions, ranked by popularity (historical query frequency) No spell check or…
- 13.2High-level design: gather data, serve queriesTwo services: Data gathering service: collects user queries and aggregates them in real time into a frequency table (query → count).…
- 13.3The trie (prefix tree)A trie (pronounced "try", from retrieval) is a tree built for string retrieval: The root is the empty string. Each node stores a character…
- 13.4Optimization: cache the top k at every nodeTwo optimizations make lookups O(1): Limit the max prefix length. Users rarely type long queries, so cap p at, say, 50. Finding the prefix…
- 13.5Data gathering serviceUpdating the trie on every single query (billions per day) would slow down the query service. And top suggestions don't change much minute…
- 13.6Query service and trie operationsA search query goes to the load balancer, then to API servers. The API servers get the trie data from the trie cache and build suggestions.…
- 13.7Scaling the storage: smart shardingWhen the trie no longer fits on one server, shard it. A naive approach shards by first character: 2 servers → 'a–m' and 'n–z'; 3 servers →…
- 13.8Wrap upMultiple languages: store Unicode characters in trie nodes. Unicode covers all the world's writing systems. Different countries: top…