In-Memory Typeahead Trie Service
Design a typeahead service that starts with a compact in-memory trie and scales through safe rebuilding, hot swaps, and prefix-aware sharding without introducing any external service.
Problem statement
Design a typeahead service that begins as a small deployment and can scale as demand grows. The serving index must be an in-memory trie owned by the system. Clients query a prefix and receive up to 10 matching keywords. Operators can add or remove keywords and update their integer scores.
Results are ordered by score descending and then keyword text ascending.
For this exercise, assume keyword text is normalized with Unicode NFKC and locale-independent case folding, queries shorter than two normalized characters return no results, and a write carries a stable operation ID plus the keyword's expected version.
The authoritative keyword records and accepted write operations live in an internally owned durable store. Trie snapshots are immutable and carry a monotonically increasing version.
A serving process loads and validates a complete snapshot before atomically swapping new queries to it; in-flight queries may finish on the preceding healthy version.
Start with one million active keywords, 1,000 peak prefix queries per second, and 50 peak writes per second, then explain a path to 50 million keywords and 100,000 peak queries per second. Target 100 milliseconds p95 for reads.
Storage, logs, caches, builders, routing, trie serving, and recovery must all remain owned components of the designed system. Scale-up may add owned replicas and prefix-aware shards but may not introduce any external service.
Cover read and write paths, score updates, internal keyword storage, rebuild and hot-swap behavior, skewed hot prefixes, sharding, failure recovery, and observability.
What to build
- Return up to 10 active normalized keywords matching a normalized prefix, ordered by score descending and keyword text ascending.
- Idempotently add, remove, and update scored keywords in the authoritative internal store using expected-version checks.
- Build, validate, and atomically hot-swap complete immutable in-memory trie versions without exposing partial state.
- Scale the owned trie serving path with replicas, caching, and prefix-aware sharding while retaining deterministic results and a recoverable last healthy version.
At scale
- For this exercise, assume the initial deployment holds one million active keywords and serves 1,000 peak prefix queries per second plus 50 peak writes per second.
- For this exercise, plan a growth path to 50 million active keywords and 100,000 peak prefix queries per second with a skewed prefix distribution.
- For this exercise, prefix reads should complete within 100 milliseconds at p95, and a successfully committed write should become visible through a published trie version within five minutes.
- For this exercise, keyword records and accepted operations are durable internally, while every serving trie snapshot is immutable, versioned, validated before activation, and recoverable to the last healthy version.