When a typeahead suggestion structure outgrows one machine, how do you choose between hash-sharding a prefix-to-list map and range-sharding a trie by prefix?
answer
- replicate before you partition
- flatten the structure into keys
- letters are not evenly used
- short prefixes cross boundaries
- traversal wants locality
basics
~20 sHash-sharding a flattened prefix-to-list map spreads load evenly and routes each lookup to one shard but blocks traversal features like fuzzy matching; range-sharding a trie keeps traversal but needs load-based split points and special handling for short prefixes.
solid answer
~50 sFirst check whether partitioning is needed at all: suggestion data per locale often fits in memory, and **replicating** whole copies scales reads without sharding. If it does not fit, there are two main shapes. A **flattened map** from every prefix (up to a length cap) to its top-k list can be **hash-sharded**: load spreads evenly, every exact lookup hits one shard, and hot keys are handled by caching and extra replicas, but traversal-based features such as fuzzy matching become hard because neighbouring prefixes live on different shards. A **trie range-sharded by prefix** keeps traversal local, but split points must follow measured load, not the alphabet, since a naive first-letter split is badly skewed and cannot split a hot letter. Short prefixes whose completions span several ranges need a separate top tier. Partitioning by locale first is often the simplest win.
go deeper
Recall the difference between copying the whole structure to more machines and splitting it across machines, and that splitting by first letter gives uneven shards.
Explain how a flattened prefix-to-list map is hash-sharded and why a trie needs contiguous prefix ranges instead.
Show operational judgment: load-based split points, a short-prefix top tier, hot-key caching, and versioned atomic swaps across shards.
Own the decision: whether to shard at all, whether traversal features justify range sharding, and the rebalancing effort each option commits the team to.
## Before sharding: do you need it? A typeahead structure holds precomputed **top-k** suggestion lists per prefix. Its size depends on how many distinct prefixes are stored and on k. Two different pressures can push it off one machine: - **Read load** too high for one server, which **replication** solves: identical full copies behind a load balancer. - **Data size** too large for one server's memory, which only **partitioning** (sharding) solves. Many deployments need only the first, especially when data is split by **locale** or market anyway, since each locale's structure is much smaller than the global one. Shard only when a single locale's structure does not fit. ## Shape A: hash-sharded prefix-to-list map Flatten the structure into a key-value map: every prefix up to a length cap maps to its stored list. - **Size.** An illustrative upper bound: **10 million** distinct queries of **20** characters average produce at most **200 million** prefixes, far fewer after shared prefixes are deduplicated. At 10 IDs of 4 bytes each, 200,000,000 x 40 bytes = **8 GB** of lists at that bound, plus keys. - **Routing.** Hash the prefix to pick a shard; each request touches exactly one shard. - **Balance.** Hashing spreads keys evenly, and **consistent hashing** limits data movement when shards are added. - **Hot keys.** Short prefixes are very hot but few; cache them in front and give them extra replicas rather than relying on the hash. - **Limitation.** Neighbouring prefixes such as `lapt` and `lapto` land on unrelated shards, so anything that walks the structure, such as fuzzy matching with an automaton, turns into many cross-shard lookups. ## Shape B: range-sharded trie Keep the trie and split it into contiguous **prefix ranges**, such as `[a, ca)`, `[ca, f)` and so on, with each shard owning one subtree range. - **Traversal stays local.** A fuzzy walk under a long prefix mostly stays inside one shard. - **Split points must follow data.** Choose boundaries from measured request load and subtree size, and move them as traffic shifts. - **Short prefixes span ranges.** If a boundary falls inside the `c` subtree, the list for prefix `c` depends on completions held by two shards. A common fix is a small **top tier** that stores the lists for all prefixes up to a few characters, served from memory and cache, with range shards handling longer prefixes. ## Why first-letter sharding fails Splitting into one shard per first letter looks natural but has several flaws: 1. **Skew.** Letter frequencies are uneven, so some shards carry many times the load of others. 2. **No further split.** A hot letter is a single shard by definition; the scheme has no way to divide it. 3. **Fixed count.** Capacity is tied to the alphabet, not to hardware. 4. **Other scripts.** Non-Latin writing systems, digits and symbols do not fit a 26-way split. Range sharding with measured boundaries is the generalization that removes these flaws. ## Comparing the options | Concern | Replicate full copies | Hash-sharded map | Range-sharded trie | |---|---|---|---| | Fits data larger than one machine | no | yes | yes | | Lookups per request | 1 | 1 shard | 1 shard, plus top tier for short prefixes | | Load balance | even | even by keys | depends on boundary choice | | Traversal features | easy | hard | mostly local | | Rebalancing | none | consistent hashing | move boundaries, copy subtrees | ## Making the call - If data fits per locale, **partition by locale and replicate**; this is the simplest and most common answer. - If exact prefix lookup is all the product needs, the **hash-sharded map** is operationally simpler. - If fuzzy matching or other traversal features matter, the **range-sharded trie with a short-prefix top tier** keeps them affordable. - In every shape, publish new builds by atomic swap per shard, with a version check so a request never mixes shards from different builds. This is a judgment call: the right answer depends on data size per locale, which features need traversal, and how much rebalancing effort the team can own.
- How do you keep a request from reading shards built from different daily builds?Tag every published build with a version, load the new version on all shards before switching, then flip a routing pointer to it in one step. Requests carry or resolve the version once, so all their reads use the same build; the old version stays loaded until in-flight requests finish.
- Why store short-prefix lists in a separate top tier when range-sharding a trie?A short prefix's completions can cover several prefix ranges, so no single range shard has its full top-k list. Precomputing those lists centrally during the build and serving them from a small, heavily cached tier means a request for a short prefix still reads one place.
saying these in an interview costs you the question
- Shard by first letter because that spreads load evenly.
- Replication and sharding solve the same problem.
- Hash sharding keeps neighbouring prefixes on the same shard.
- Every typeahead deployment must shard its suggestion data.
- Range boundaries can be fixed once by alphabet and never moved.