Everyone thinks autocomplete is a LIKE 'prefix%' query. “Index the search terms, run a prefix match, return the top ten, done.” Then the interviewer adds the real constraints: the dropdown must update on every keystroke, so you are firing a query every ~50ms while someone types; it must feel instant, which means the whole round trip - network, lookup, ranking, render - has a budget under 100ms; the corpus is billions of queries and the popular ones shift by the hour; and “top ten” is not alphabetical, it is ranked by popularity, which a prefix index does not give you for free.

Autocomplete is deceptive because the naive version demos fine on a laptop with a thousand terms and collapses the moment you have real scale and a real latency budget. The whole design comes down to four decisions: how you find every completion of a prefix fast (the trie), how you rank them to the top-k without scanning all completions (precomputed top-k), how you cache so the common prefixes never touch the index (prefix caching), and how you keep the rankings fresh as query popularity drifts (the offline pipeline). All of it under a 100ms keystroke budget.

Let me do it properly.

Functional Requirements (FR)

In scope:

  • Prefix suggestions. Given a prefix string the user has typed so far ("new y"), return an ordered list of the top N completions ("new york", "new york times", "new years eve", …). N is small, typically 5-10.
  • Ranked by relevance. Suggestions are ordered by popularity (how often that full query is searched), not alphabetically. The whole point is that the most likely completion is first.
  • Per-keystroke latency. The endpoint is hit on every keystroke as the user types, so it must be fast enough that the dropdown feels live - the hard sub-100ms budget end to end.
  • Fresh-ish rankings. Popular queries change over time (a breaking news term spikes in minutes). Rankings should reflect recent popularity, updated on the order of hours (not necessarily seconds).
  • Prefix normalization. Case-insensitive, trim whitespace, collapse repeats. "New York" and "new york" hit the same suggestions.

Explicitly out of scope (say this out loud so you control the scope):

  • Personalization and per-user history. Suggestions tailored to a specific user’s search history is a large separate system (a personalization/ranking layer on top). We build the global, popularity-ranked layer and note where personalization would graft on.
  • Spell correction / fuzzy matching. “Did you mean” and typo tolerance (edit-distance matching) is a related but distinct feature. Our trie does exact prefix matching; fuzzy is an extension.
  • Full search results. We return query suggestions, not documents. Turning a chosen query into a page of results is the search engine’s job, a different system entirely.
  • Semantic / embedding-based suggestions. Vector-similarity “queries like this” is a bonus layer, not the core prefix system.
  • Real-time (sub-second) ranking updates. We target hourly-ish freshness. True streaming top-k on every event is possible but overkill for the base design; we note it as an extension.

The one decision that drives everything: autocomplete is a read-dominated, latency-critical lookup that runs on every keystroke. Writes (new queries entering the corpus) are batched and offline; reads are enormous and must be sub-100ms. So the design is dominated by “precompute everything you possibly can offline, and make the online path a near-pure cache/trie lookup with no ranking work at request time.”

Non-Functional Requirements (NFR)

  • Scale: ~10B distinct historical queries in the corpus, of which only a few hundred million are common enough to ever suggest. Read traffic on the order of 100K-500K QPS at peak (every keystroke of every searching user), writes (corpus updates) are batched offline, not per-request.
  • Latency: p99 end-to-end under 100ms including network; server-side lookup budget well under that, target p99 ~20-30ms server-side so the network and render fit in the rest. A slow suggestion is worse than none - it arrives after the user has typed the next character.
  • Availability: 99.9%+. Autocomplete is a nice-to-have overlay on search; if it fails, the search box must still work (graceful degradation - return nothing rather than error). But it is user-facing on the most-used surface, so it should almost never be down.
  • Consistency: eventual and loose. It is completely fine if a brand-new trending query takes an hour to start appearing in suggestions, and fine if two data centers show slightly different rankings. There is no correctness contract to violate - a suboptimal suggestion is not a bug, just less helpful.
  • Durability: low for the serving layer (the trie is a derived, rebuildable structure - lose it and rebuild from logs), high for the raw query logs (they are the source of truth the whole pipeline derives from, stored durably in the data lake).

Back-of-the-Envelope Estimation (BoE)

Let me ground the design in numbers.

Traffic:

Daily active searchers:        100,000,000 (100M)
Searches per user per day:     ~4
Avg characters typed/search:   ~20 (before submitting or picking a suggestion)

Autocomplete requests are per-keystroke, so ~1 request per character:
  Requests/day = 100M users * 4 searches * 20 keystrokes
               = 8,000,000,000  (8B autocomplete requests/day)

Average QPS = 8B / 86,400 sec ≈ 92,600  -> ~93K QPS average
Peak (say 3x average)         -> ~280K QPS peak

So ~93K QPS average, ~280K peak - and note this is ~20x the number of actual searches, purely because each search fires ~20 keystroke lookups. That multiplier is the whole reason latency and caching dominate.

Read vs write:

Reads (keystroke lookups):  ~280K QPS peak. This is the whole system.
Writes (new/updated ranks): batched offline. The corpus is rebuilt
  from logs on a schedule (hourly aggregation, periodic full rebuild),
  NOT written on the request path. Online write QPS ≈ 0.

This read/write asymmetry is the key architectural lever: there is no online write path to the trie. All the expensive ranking work happens offline in a batch pipeline, and the online path only reads an immutable, prebuilt structure. That is what makes sub-100ms achievable.

Corpus and storage:

Distinct historical queries:   10B
Queries common enough to suggest (say freq >= some threshold):
  ~100M  (the long tail of 10B is searched once and never suggested)

Trie storage for the serving set (~100M queries):
  Avg query length:            ~20 chars
  Naive: 100M queries * 20 chars = 2B nodes if no prefix sharing.
  With prefix sharing (the point of a trie), shared prefixes collapse:
    effective ~5-10 nodes/query after sharing -> ~1B nodes.
  Per node: char + children map ptr + top-k list.
  If each node stores a precomputed top-10 (10 * ~40 bytes = 400 bytes):
    1B nodes * ~450 bytes ≈ 450 GB.

That ~450 GB is too big for one machine’s RAM and is why the trie is sharded. But note: storing the full top-k at every node is what makes reads O(prefix length) with zero ranking work - a deliberate space-for-time trade we will refine.

Cache sizing:

Prefix requests are wildly skewed - short prefixes ("a", "ne", "the")
are hit constantly; long specific prefixes are rare.
Cache the top ~1M hottest prefixes:
  1M prefixes * (top-10 list ~500 bytes) = ~500 MB.  Trivially fits in RAM.

That is the punchline of the whole system: a 500 MB cache absorbs the overwhelming majority of 280K QPS, because prefix popularity follows a steep power law - a tiny set of short prefixes accounts for most keystroke lookups. The trie behind it only serves cache misses (longer, rarer prefixes).

Bandwidth:

Response size: top-10 suggestions * ~20 bytes each + overhead ≈ 300-500 bytes.
280K QPS * 500 bytes = ~140 MB/sec egress. Modest; fits comfortably.

The bandwidth is trivial. The scarce resource is time: 280K lookups each needing to finish inside a shared ~100ms budget. Size the design for latency and cache hit rate, not for bytes.

High-Level Design (HLD)

Autocomplete splits cleanly into two systems that meet at the trie: an offline pipeline that aggregates query logs into a ranked, top-k-annotated trie, and an online serving path that answers keystroke requests from a cache backed by that trie. The offline path is where all the heavy computation lives; the online path is deliberately dumb and fast.

                          ONLINE (per-keystroke, must be <100ms)
      ┌──────────────────────────────────────────────────────────────┐
      │  Browser (debounce ~50ms, cancel stale in-flight requests)     │
      └───────────────────────────┬──────────────────────────────────┘
                                  │  GET /autocomplete?q=new+y
                        ┌─────────▼──────────┐
                        │   API Gateway / LB  │
                        └─────────┬──────────┘
                        ┌─────────▼──────────┐   HIT (~95%)
                        │  Suggestion Service │────────────────┐
                        │  (stateless)        │                │
                        └─────────┬──────────┘                 │
                       MISS       │  check prefix cache         │
                        ┌─────────▼──────────┐                 │
                        │   Prefix Cache      │◄────────────────┘
                        │  (Redis, top-k by   │
                        │   prefix string)    │
                        └─────────┬──────────┘
                       MISS       │  route by prefix shard key
             ┌────────────────────┼────────────────────┐
      ┌──────▼──────┐      ┌──────▼──────┐       ┌──────▼──────┐
      │ Trie Shard 0│      │ Trie Shard 1│  ...  │ Trie Shard M│
      │ (in-RAM,    │      │ (in-RAM,    │       │ (in-RAM,    │
      │  top-k/node)│      │  top-k/node)│       │  top-k/node)│
      └─────────────┘      └─────────────┘       └─────────────┘
                                  ▲
                                  │ atomic swap of new immutable trie
      ┌───────────────────────────┴──────────────────────────────────┐
      │                    OFFLINE (batch, hourly-ish)                 │
      │                                                                │
      │  Raw query logs ──► Aggregate counts ──► Filter + normalize    │
      │  (data lake)        (MapReduce/Spark:    (drop tail, PII       │
      │                      count per query,     scrub, dedup)        │
      │                      time-decay weight)        │               │
      │                                                ▼               │
      │                        Build trie + compute top-k per node     │
      │                        ──► serialize ──► push to serving shards│
      └────────────────────────────────────────────────────────────────┘

Request flow - a keystroke lookup (the read hot path):

  1. The browser debounces (waits ~50ms after the last keystroke so it does not fire a request for every character in a fast burst) and cancels any still-in-flight request for an older prefix. It sends GET /autocomplete?q=<prefix>.
  2. The API gateway routes to a stateless Suggestion Service instance.
  3. The service normalizes the prefix (lowercase, trim, collapse spaces) and checks the prefix cache keyed by the normalized prefix string. On a hit (the common case, ~95%), it returns the cached top-k immediately. Sub-millisecond, done.
  4. On a miss, the service routes to the trie shard that owns this prefix (sharded by prefix, covered in the deep dive), which walks the trie to the prefix node and reads that node’s precomputed top-k list - no ranking at request time.
  5. The service writes the result into the prefix cache (with a short TTL) and returns it. Next time this prefix is hit, it is a cache hit.
  6. If the trie shard is unreachable or slow, the service returns an empty list, not an error - autocomplete degrades gracefully so the search box keeps working.

Data flow - the offline rebuild (the write path):

  1. Every search that a user actually submits is logged (query string, timestamp) to the durable query-log store / data lake.
  2. On a schedule (say hourly for incremental, daily for a full rebuild), a batch job aggregates counts per distinct query, applies time decay so recent searches weigh more, and filters out the long tail (queries too rare to ever suggest), plus PII scrubbing and normalization.
  3. A build job constructs the trie from the surviving ranked queries and precomputes the top-k for every node (the hard part - covered in the deep dive).
  4. The serialized trie is pushed to the serving shards, which atomically swap the old trie for the new one (build a fresh immutable copy, flip a pointer) so reads never see a half-built trie.

The key architectural insight: the online path never ranks anything. Ranking is expensive (you would have to gather all completions of a prefix and sort them), so it is done once, offline, and baked into the trie as per-node top-k lists. The request path is reduced to “walk to a node, read a precomputed list, or hit the cache.” That is the only way to hold sub-100ms at 280K QPS.

Component Deep Dive

Three hard parts: (1) the trie and how you find completions of a prefix, (2) computing and storing top-k so reads do zero ranking, and (3) prefix caching plus sharding to hold the latency budget at scale. I will walk each from naive to scalable.

1. Prefix Lookup: SQL LIKE -> Trie -> Top-k Annotated Trie

Approach A: The database prefix query (the naive instinct)

Store queries in a table and match the prefix with SQL:

SELECT query, popularity
FROM search_queries
WHERE query LIKE 'new y%'
ORDER BY popularity DESC
LIMIT 10;

Simple, and with a B-tree index on query the LIKE 'prefix%' can even use the index (a range scan on the prefix). Where it breaks: the ORDER BY popularity DESC LIMIT 10 cannot use the same index. The index is sorted by query string, so the DB finds all rows matching the prefix - which for a short prefix like "n" could be tens of millions of rows - and must then sort all of them by popularity to get the top 10. That sort, per keystroke, at 280K QPS, is hopeless. A short popular prefix is the worst case, and short prefixes are exactly the most frequent requests. You could add a composite index, but you cannot index “all queries starting with an arbitrary prefix, sorted by popularity” for every possible prefix in a B-tree. The database is the wrong shape for this.

Approach B: A trie (prefix tree)

The natural data structure for “all strings sharing a prefix” is a trie: a tree where each edge is a character and each root-to-node path spells a prefix. Every query is a path from the root to a node marked as a terminal word.

                (root)
                /    \
              n        t
              |        |
              e        h
              |        |
              w        e  <- "the" (terminal)
             / \
          (sp)  s
            |    |
            y    (sp)
            |    |
            o    y...   <- "news y..." 
          "new y..."

To find completions of a prefix: walk down the trie following the prefix’s characters (O(prefix length), independent of corpus size), arriving at the prefix node. Every terminal descendant of that node is a completion. This solves the finding problem beautifully - locating the prefix subtree is O(len), not O(corpus).

Where it breaks: the ranking is still not free. Reaching the prefix node gives you the subtree of all completions, but you still need the top 10 by popularity. For a short prefix that subtree can contain millions of terminals. Doing a DFS over the whole subtree to collect completions and then sorting them by popularity - per keystroke - is the same fatal cost as Approach A, just in a tree instead of a table. The trie fixed finding; it did not fix ranking. That is the crux, and it is what the top-k precomputation section solves.

Approach C: The top-k annotated trie (the fix, detailed in section 2)

The insight: since the corpus only changes offline, precompute and store the top-k completions directly at every node. When a request walks to the prefix node, the answer is already sitting there - read the list, return it, zero traversal of the subtree, zero sorting. This turns a request into O(prefix length) pointer-walks plus one list read. That precomputation is the second deep dive.

2. Top-k Precomputation: The Space-for-Time Trade That Makes Reads O(1)

The online path must not rank. So at build time, every trie node gets a precomputed, sorted list of its top-k completions. The question is how to compute those lists efficiently and how to store them without blowing up memory.

Approach A: Recompute per request (rejected, see above)

DFS the subtree, collect all terminals with their popularity, sort, take top-k. Correct but O(subtree size) per request - fatal for short prefixes. Rejected. The only reason to state it is to justify precomputation.

Approach B: Precompute top-k at every node via a bottom-up merge

Build the trie, then compute top-k for every node in a single post-order (bottom-up) pass. A leaf/terminal node’s top-k is just itself. An internal node’s top-k is the merge of its children’s top-k lists (plus its own terminal, if it is one), keeping only the highest-k by popularity.

build_topk(node):
    candidates = []
    if node.is_terminal:
        candidates.append( (node.word, node.popularity) )
    for child in node.children:
        build_topk(child)                 # child.topk already computed
        candidates.extend(child.topk)     # each child contributes <= k items
    node.topk = k_largest_by_popularity(candidates, k)   # merge, keep top-k
    return

Why the merge is cheap: a node’s top-k can only come from the union of its children’s top-k lists (a global winner for a prefix is a winner for exactly one child’s sub-prefix). So each internal node merges at most (num_children * k) candidates and keeps k - not the whole subtree. The entire build is one bottom-up pass over the trie, roughly O(total_nodes * k) - done once, offline, where we have all the time we want.

Now a request is: walk to the prefix node (O(len)), read node.topk (O(1)), return. No ranking online. This is the core trade: spend build-time compute and serving-memory to make every read trivial.

Approach C: Controlling the memory blowup (the refinement)

Storing a full top-k list at every node is expensive. The BoE put this near ~450 GB, because every node - including deep, rarely-hit ones - carries a k-sized list. Refinements:

  • Store top-k only above a depth threshold, or only at nodes with high enough traffic. Very deep prefixes ("new york times square webcam liv") are rare and specific; the subtree is small, so recomputing their top-k on the fly by a quick bounded DFS is cheap. Store precomputed lists only for short/popular prefix nodes (the hot ones), and compute long-prefix completions on demand. This is the classic hot/cold split: precompute the hot, compute the cold.
  • Store references, not full strings. A node’s top-k stores query IDs (4-8 byte ints) pointing into a shared string table, not repeated full query strings. Massive dedup since the same popular query appears in the top-k of all its prefixes’ ancestors.
  • Cap k at what the UI shows. You display 10 suggestions; store exactly 10, not 50. Every extra stored suggestion multiplies across a billion nodes.

The decision table:

StrategyRead costBuild costMemoryVerdict
Recompute per request (DFS subtree)O(subtree) - fatal for short prefixnoneminimalRejected
Top-k at every nodeO(len) read, O(1) listO(nodes*k) oncevery high (~450 GB)Correct but heavy
Top-k at hot nodes + on-demand coldO(len) hot, O(small subtree) coldO(hot nodes*k)much lowerBest in practice
Store IDs not strings + cap ksamesamefar lowerAlways do this

The answer: precompute top-k bottom-up and store it as ID references, capped at the display count, at hot (short/popular) prefix nodes, computing the rare long-prefix completions on demand. Reads stay O(prefix length) for the prefixes that actually get traffic.

Handling freshness: rebuild vs incremental

The trie is immutable while serving (so reads are lock-free). Freshness comes from rebuilding and swapping, not from mutating in place:

  • Full rebuild (say daily): reaggregate all logs, rebuild the whole trie, push, atomic-swap. Simple, expensive.
  • Incremental / delta (say hourly): aggregate only the last hour’s logs, update popularity counts with time decay (recent searches weigh more so trending terms rise and stale ones fade), and rebuild only the affected subtrees, or rebuild fully but more cheaply from a maintained aggregate. Push and swap.

Time decay is what makes a breaking-news query climb the rankings within an hour and a last-week fad fall off - each query’s weight is sum over events of decay(age), e.g. an exponential half-life, recomputed each aggregation.

3. Prefix Caching and Sharding: Holding 100ms at 280K QPS

Even with O(len) trie reads, going to the trie shards for every one of 280K QPS is more load and latency than needed, because prefix popularity is wildly skewed. Caching and sharding are what actually hold the budget.

Prefix caching: naive -> skew-aware

Naive: no cache, every request hits the trie shard. Works, but wastes the enormous skew: the prefix "a" or "the" is requested millions of times an hour and returns the same top-k every time until the next rebuild. Recomputing/re-fetching identical answers is pure waste, and cross-network hops to shards add latency.

Better: a prefix cache keyed by the normalized prefix string. A Redis (or in-process) cache mapping normalized_prefix -> top-k list. The BoE showed the hottest ~1M prefixes fit in ~500 MB, and because of the power-law skew those ~1M prefixes absorb the large majority of traffic. Cache mechanics:

  • Key: the normalized prefix ("new y"). Value: the serialized top-k list.
  • TTL: short-to-medium (minutes), so a cache entry cannot be more stale than the TTL even between rebuilds; on rebuild we can also proactively bust/refresh the hottest prefixes.
  • Two-layer: an in-process LRU on each stateless Suggestion Service instance (nanosecond hits, no network) in front of the shared Redis (survives instance restarts, shared across the fleet). The in-process layer catches the ultra-hot short prefixes; Redis catches the warm mid-tail.
  • Fill on miss: on a miss, fetch from the trie shard, write to both cache layers.

The hit rate is the whole game. At ~95% cache hit, only ~5% of 280K QPS (~14K QPS) reaches the trie shards, and each of those is an O(len) in-RAM walk. That is what keeps p99 comfortably inside the budget.

Sharding the trie: how to split ~450 GB across machines

The trie does not fit on one machine, so it is partitioned. The shard key choice is the interesting part.

  • Naive: shard by hash of the full query. Spreads storage evenly, but a single prefix’s completions are now scattered across every shard (each completion hashed independently), so a prefix lookup must fan out to all shards and merge - the opposite of what you want. Rejected.
  • Better: shard by prefix (the first 1-2 characters, or a hash of a short prefix). All queries starting with "ne" live on the same shard, so a lookup for "new y" goes to exactly one shard - the request routes deterministically by its own prefix, no fan-out. This is the right shard key because it preserves prefix locality, which is the entire access pattern.
Shard by first-2-chars (with balancing):
  "aa".."am"  -> shard 0
  "an".."az"  -> shard 1
  "ne".."nz"  -> shard 4   (a lookup "new y" -> hash("ne") -> shard 4, ONE shard)
  ...
Hot first-chars (like "s", "t", "a") get split finer / given more shards
to balance load, since prefix popularity is uneven.

The catch: prefix distribution is skewed (far more queries start with "s" than "z"), so naive equal-range sharding creates hot shards. Fix by splitting hot prefix ranges across more shards (give "s" several shards keyed by the next character) and balancing by measured traffic, not alphabetically. Since each shard is an immutable prebuilt structure, replicate each shard N times behind a load balancer for read throughput and availability - reads are trivially parallel across replicas because nothing mutates online.

The client side counts too

Half the latency budget is outside the server. The browser must:

  • Debounce (~50ms): do not fire on every keystroke in a fast burst; wait until typing pauses briefly. Cuts request volume and avoids showing suggestions for a prefix the user already typed past.
  • Cancel stale requests: if the user types another character, cancel the in-flight request for the old prefix so a slow old response cannot overwrite the newer suggestions (out-of-order responses are a classic autocomplete bug).
  • Client-side prefix cache: if the user backspaces from "new yo" to "new y", the browser already has "new y"’s suggestions - serve them locally, zero network.

API Design & Data Schema

Serving API (the data plane)

One tiny, read-only, cache-friendly endpoint:

GET /autocomplete?q=<prefix>&limit=10&lang=en

  q       string   the raw prefix the user has typed (required)
  limit   int      max suggestions to return (default 10, capped ~10)
  lang    string   language/locale for the right corpus (optional)

200 OK
{
  "prefix": "new y",
  "suggestions": [
    { "query": "new york",        "rank": 1 },
    { "query": "new york times",  "rank": 2 },
    { "query": "new years eve",   "rank": 3 }
  ]
}

On backend trouble: return 200 with an empty "suggestions" list
(graceful degradation), NEVER a 5xx that breaks the search box.

Notes: it is a GET so it is cacheable at every layer (CDN edge for the very hottest short prefixes, gateway, service, Redis). It is idempotent and side-effect free. limit is capped server-side so a client cannot ask for a huge k the trie did not precompute.

Ingestion / control-plane API (offline)

POST /internal/v1/logs/search        # fire-and-forget log of a submitted search
     { "query": "new york times", "ts": 1751846400, "lang": "en" }
     -> appended to the durable query-log stream; NOT written to the trie

POST /internal/v1/trie/rebuild        # trigger an offline rebuild job
     { "mode": "incremental|full", "decay_half_life_hours": 72 }

POST /internal/v1/trie/publish        # push a built trie version to shards
     { "version": "2026-07-07T04:00Z", "shards": [...], "checksum": "..." }
     -> shards load and atomic-swap; old version kept for instant rollback

Data model: derived in-memory trie, durable logs

Two very different stores for two very different jobs - the raw logs (durable, append-only, the source of truth) and the serving trie (derived, in-memory, rebuildable).

Raw query logs (durable, in the data lake - e.g. object storage / a columnar table):

search_log
  query        STRING        # the submitted query (normalized separately)
  ts           INT64         # event epoch seconds (for time-decay weighting)
  lang         STRING        # locale
  (append-only, partitioned by day; this is the source of truth)

This is the only durable, authoritative data. Everything else is derived from it and can be rebuilt.

Aggregated query weights (intermediate, produced by the batch job):

query_weight
  query        STRING  PK    # normalized query
  weight       FLOAT         # time-decayed popularity score
  lang         STRING
  updated_at   INT64
  INDEX (weight DESC)        # to filter the long tail before building the trie

Serving trie node (in RAM on a shard - conceptual layout):

TrieNode {
  children    map<char, TrieNode*>   # or a compact array; the edges
  is_terminal bool                    # is this node the end of a query?
  topk        list<query_id>          # PRECOMPUTED top-k completion IDs
                                       #   (IDs into a shared string table,
                                       #    only stored on hot/short nodes)
}

Shared string table:  query_id -> (query_string, weight)   # dedup the strings

Why a trie in RAM and not SQL: the access pattern is “walk characters of an arbitrary prefix and read a precomputed ranked list,” at hundreds of thousands of QPS, under 100ms. That is exactly what an in-memory trie does in O(prefix length) with no per-request sorting - and exactly what a relational engine cannot do (it would range-scan then sort per keystroke, as Approach A showed). The corpus is read-only online and rebuilt offline, so the durability/transaction machinery of a database is pure overhead on the serving path. We keep the trie in memory, immutable, sharded and replicated; the durable SQL/lake store holds only the logs and aggregates the offline pipeline needs.

Prefix cache entry (Redis):

key:   ac:{lang}:{normalized_prefix}          # e.g. ac:en:new y
value: serialized top-k list  [ {query, rank}, ... ]
TTL:   a few minutes (bounds staleness; refreshed/busted on rebuild)

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Per-request ranking cost (breaks first, conceptually). A short popular prefix ("a", "the") has millions of completions; ranking them per keystroke is fatal. Fix: precompute top-k at build time and store it on the node, so the request does O(prefix length) walk + O(1) list read and never sorts. This is the single most important move - it removes ranking from the request path entirely.

2. Trie does not fit in one machine’s RAM (~450 GB). A single node cannot hold the corpus. Fix: shard by prefix (first 1-2 chars / short-prefix hash) so a lookup routes to exactly one shard with no fan-out, and replicate each shard for throughput and availability. Split hot prefix ranges ("s", "t") across more shards to balance skew.

3. Read QPS on the shards (280K peak). Sending every keystroke to the trie is more load and latency than needed. Fix: prefix caching - a two-layer cache (in-process LRU + shared Redis) keyed by normalized prefix. Power-law skew means ~1M cached prefixes in ~500 MB absorb ~95% of traffic, so only the mid/long tail reaches the trie.

4. Hot prefix / hot shard. The shortest, most popular prefixes concentrate load on one cache key and one shard. Fix: the ultra-hot short prefixes are served from the in-process cache and even the CDN edge (they are GET-cacheable and identical for everyone), so they barely reach Redis or the shards at all. Replicate the hot shard more heavily and cache its answers longest.

5. Staleness / freshness lag. Rankings drift as query popularity shifts (breaking news spikes in minutes). Fix: incremental hourly rebuilds with time decay so recent searches weigh more; short cache TTLs bound how stale a served answer can be; proactively bust/refresh the hottest cached prefixes on each rebuild.

6. Rebuild-and-swap safety. Pushing a new ~450 GB trie must not make reads see a half-built structure or take a lock. Fix: build the new trie as a fresh immutable copy, load it alongside the old one on each shard, then atomically flip a pointer. Reads are always lock-free against a complete, immutable trie. Keep the previous version loaded for instant rollback if the new one is bad.

7. Ingestion volume / log write load. Logging every submitted search is a firehose. Fix: logs are append-only and asynchronous (fire-and-forget to a stream like Kafka, batched into the data lake) - never on the autocomplete read path. The read path and write path are fully decoupled; the trie is only ever updated by the offline job.

8. Availability of a user-facing surface. If autocomplete errors, it must not break search. Fix: graceful degradation - on any backend failure return an empty suggestion list, not an error, so the search box always works. Replicate shards and cache across AZs; the stateless service and immutable data make failover trivial.

Wrap-Up

The trade-offs that define this design:

  • Precompute offline over rank online. We spend large build-time compute and serving memory (top-k stored per hot node) to make every read O(prefix length) with zero sorting. This is the whole reason 100ms is achievable - ranking a short prefix’s millions of completions per keystroke is impossible, so we never do it at request time.
  • Immutable, rebuilt trie over a mutable one. We give up real-time updates (a new query takes ~an hour to appear) in exchange for lock-free reads, atomic swaps, trivial replication, and instant rollback. For autocomplete, hour-fresh rankings are completely fine, so this is a cheap trade for a big serving simplification.
  • Shard by prefix over shard by hash. We deliberately do not spread a prefix’s completions across shards, because prefix locality is the entire access pattern - one lookup, one shard, no fan-out. We pay for it by having to balance skewed prefix ranges manually, which is worth it.
  • Cache the skew hard. A ~500 MB prefix cache absorbing ~95% of 280K QPS is the difference between a comfortable and an impossible latency budget. Power-law prefix popularity is the friend we lean on completely - short prefixes are hit constantly and cache perfectly.
  • Two stores for two jobs. Durable, append-only query logs are the source of truth (rebuildable everything derives from them); the in-memory sharded trie is a derived, disposable serving structure. Never confuse the durable log firehose (write path, offline) with the immutable read-only trie (read path, online).

One-line summary: an offline batch pipeline aggregates time-decayed query logs into an immutable, prefix-sharded trie with precomputed top-k lists at every hot node, and an online path serves keystroke lookups from a two-layer prefix cache backed by O(prefix length) trie reads - trading real-time freshness and serving memory for ranked suggestions delivered in well under 100ms at hundreds of thousands of QPS.