Design Search Autocomplete: Prefix Matching at Scale

A senior-engineer reference for query autocomplete (typeahead): the prefix data structures that determine the latency floor, the dual-path indexing that keeps suggestions fresh, the cache hierarchy that absorbs traffic, and the WAI-ARIA combobox contract the UI must honor. The article is opinionated about one architecture (in-memory trie with pre-computed top-K) because it is the canonical pattern used at LinkedIn-, Google-, and Twitter-scale; the Elasticsearch completion suggester is covered as the managed-infrastructure alternative.

Mental model

Autocomplete is a prefix-completion problem under a hard latency budget. Seven ideas drive every design decision:

• Perceived latency caps the budget. The product target is the keystroke cadence — typing at ~150ms between keys means a P99 of ~100ms keeps the dropdown visually inside the typing rhythm. Anything past ~250ms reads as lag.
• The data structure sets the latency floor. A trie gives O(p) prefix lookup where p is the prefix length, independent of corpus size. Lucene’s Finite State Transducer (FST) compresses the same shape further by sharing prefixes and suffixes and storing the result as a packed byte array for in-memory serving¹.
• Pre-computed top-K eliminates query-time ranking for candidate generation. Each node stores the K best completions of its prefix. Candidate generation becomes pure traversal — no sort, no subtree walk.
• Top-N is two stages. Cheap candidate generation (top-K from the trie/FST) feeds an expensive reranker that adds personalization, freshness, and click-through signals on the few hundred candidates returned, not on the corpus.
• Typo tolerance is bounded. Production systems cap edit distance at 1 or 2 and intersect a Levenshtein automaton with the prefix index, not BK-trees, because the automaton prunes the index instead of measuring distance per term.
• Freshness comes from a dual path. Weekly batch rebuilds give stable, well-ranked indexes; streaming hot updates merge trending queries within minutes.
• Client-side debouncing is mandatory, not optional. Without it, typing javascript at normal speed fires ~10 requests in 1.5 seconds. With a 200-300ms debounce² you fire ~1, and an AbortController cancels the previous request when the user types again.

The fundamental trade-off is latency vs. relevance. Pre-computed suggestions are fast but stale; real-time ranking is fresh but slow. Production systems layer both.

Requirements

Functional requirements

Out of scope: full document search (separate system), voice input, image search.

Non-functional requirements

Scale estimation

Assumptions:

• Daily Active Users (DAU): 1 billion
• Searches per user per day: 5
• Characters per search: 20 average
• Autocomplete trigger: every 2-3 characters past the minimum prefix

Traffic:

1Queries/day = 1B users × 5 searches × (20 chars / 3 chars per trigger)2            = 1B × 5 × 7 triggers3            ≈ 35 billion autocomplete requests/day45QPS average ≈ 35B / 86,400  ≈ 405K QPS6QPS peak (3×) ≈ 1.2M QPS

Storage (rough):

1Unique queries indexed: ~1B (typical query-log distribution)2Average query length:   25 bytes3Metadata per query:     16 bytes (score, timestamp)45Raw storage: 1B × 41 bytes ≈ 41 GB6Trie overhead (pointers, node structure): 3-5×7Trie storage per replica: ~150-200 GB

Bandwidth:

1Request size:  ~50 bytes  (prefix + metadata)2Response size: ~500 bytes (10 suggestions with metadata)34Ingress: 1.2M QPS × 50 B  ≈ 60 MB/s5Egress:  1.2M QPS × 500 B ≈ 600 MB/s

Design paths

Path A — Trie with pre-computed top-K

Best when:

• Suggestion corpus is bounded (millions to low billions of unique queries)
• Latency target is sub-50ms P99
• Ranking signals are mostly stable popularity-based

Architecture:

• In-memory tries sharded by prefix range
• Top-K suggestions pre-computed at every node during the index build
• Weekly full rebuilds + sub-hour delta updates for trending queries

Trade-offs:

• Sub-10ms query latency is achievable; query is pure traversal with no sort
• Predictable, consistent performance regardless of prefix popularity
• High memory footprint (every replica holds the full shard)
• Freshness limited by the rebuild + delta cadence
• Personalization requires a separate lookup pass

Real-world reference: LinkedIn’s Cleo serves generic typeahead in ≤1ms within a cluster and network-personalized typeahead in ≤15ms, with an aggregator layer adding up to ~25ms end-to-end³.

Path B — Inverted index with completion suggester

Best when:

• Corpus is large and dynamic (e-commerce catalogs, document search)
• You need flexible query types (prefix, infix, fuzzy)
• You already operate Elasticsearch / OpenSearch

Architecture:

• Elasticsearch completion suggester backed by a Lucene FST per segment
• Edge n-gram tokenization for flexible matching
• Real-time indexing via Kafka

Trade-offs:

• Flexible query types and built-in fuzzy matching
• Near-real-time updates without full rebuilds
• Sharding and replication built into the engine
• Higher latency than a custom trie (10-50ms typical)
• Index size with edge_ngram + completion suggester runs ~15-17× larger than the default analyzer⁴
• Operational complexity of an Elasticsearch cluster

Path comparison

Comparable systems in production

Before committing to a build, look at the existing engines that have already absorbed the design pressure of multi-tenant autocomplete at scale.

If your corpus and traffic look anything like the assumptions above, the buy-vs-build trade is real. Build a custom trie service when you need sub-10ms P99 with a static schema, you already operate the streaming + batch infra, and you can amortize the engineering cost across many surfaces. Otherwise, start on Algolia or a managed Elasticsearch / OpenSearch and re-evaluate when latency or per-query cost becomes the binding constraint.

Article focus

The rest of this article goes deep on Path A, because:

1. It is the canonical autocomplete architecture used by Google, Twitter, LinkedIn, and Bing for their primary suggestion services.
2. It exposes the prefix data structures that underpin even inverted-index implementations (the FST in AnalyzingSuggester, the radix tree in Algolia, the ART in Typesense).
3. Sub-10ms latency is reachable, which Path B cannot match end-to-end.

Path B implementation details are summarized in the Elasticsearch alternative section.

High-level design

Component overview

Request flow

Sharding strategy

Prefix-based sharding routes queries by their first character(s):

1Shard 1: a-f2Shard 2: g-m3Shard 3: n-s4Shard 4: t-z

Why prefix-based, not hash-based:

1. Locality: related queries (system, systems, systematic) live on the same shard
2. Deterministic routing: the prefix sys routes to shard 3 without a directory lookup
3. Range scans: aggregations across prefix ranges stay on a single shard

Handling hot spots: English letter frequency is uneven — common starting letters dominate the request mix. Two complementary mitigations:

1. Finer granularity: split the hottest first-letter buckets into multi-letter ranges (e.g., s → sa-se, sf-sm, sn-sz)
2. Dynamic rebalancing: a Shard Map Manager monitors per-shard load and adjusts ranges
3. Replication: more replicas for hot shards

API design

Suggestion endpoint

1GET /api/v1/suggestions?q={prefix}&limit={n}&lang={code}

Request parameters:

Response (200 OK):

1{2  "query": "prog",3  "suggestions": [4    {5      "text": "programming",6      "score": 0.95,7      "type": "query",8      "metadata": { "category": "technology", "trending": false }9    },10    {11      "text": "progress",12      "score": 0.87,13      "type": "query",14      "metadata": { "category": "general", "trending": false }15    },16    {17      "text": "program download",18      "score": 0.82,19      "type": "query",20      "metadata": { "category": "technology", "trending": true }21    }22  ],23  "took_ms": 8,24  "cache_hit": false25}

Error responses:

Rate limits:

• Anonymous: 100 requests / minute / IP
• Authenticated: 1000 requests / minute / user
• Burst: 20 requests / second max

Response optimization

Compression: enable gzip for responses >1KB. A typical 10-suggestion payload compresses from ~500 bytes to ~200 bytes.

Cache headers (per RFC 9111):

1Cache-Control: public, max-age=3002ETag: "a1b2c3d4"3Vary: Accept-Encoding, Accept-Language

Pagination is intentionally not supported. Autocomplete is a bounded result set (≤20). If the user wants more, they should submit the full search.

Data modeling

Trie node structure

1interface TrieNode {2  children: Map<string, TrieNode>  // character → child node3  isEndOfWord: boolean4  topSuggestions: Suggestion[]     // pre-computed top-K5  frequency: number                // aggregate frequency for this prefix6}78interface Suggestion {9  text: string                     // full query text10  score: number                    // normalized relevance score [0, 1]11  frequency: number                // raw query count12  lastUpdated: number              // unix timestamp13  trending: boolean                // recently spiking14  metadata: {15    category?: string16    language: string17  }18}

Storage schema

Query log (Kafka topic query-logs):

1{2  "query": "programming tutorials",3  "timestamp": 1706918400,4  "user_id": "u123",5  "session_id": "s456",6  "result_clicked": true,7  "position_clicked": 2,8  "locale": "en-US",9  "platform": "web"10}

Aggregated query stats (Redis hash):

1HSET query:programming\ tutorials \2  frequency 1542389 \3  last_seen 1706918400 \4  trending 0 \5  category technology

Trie snapshot (S3 / HDFS):

1s3://autocomplete-data/tries/2  └── 2024-02-03/3      ├── shard-a-f.trie.gz      (~50 GB compressed)4      ├── shard-g-m.trie.gz      (~40 GB compressed)5      ├── shard-n-s.trie.gz      (~60 GB compressed)6      ├── shard-t-z.trie.gz      (~40 GB compressed)7      └── manifest.json

Storage selection

Low-level design

Trie implementation

Children: hash map vs. array.

Chosen: HashMap because:

1. Unicode support is required (multi-language)
2. Most nodes have <5 children (sparse trie)
3. Modern hash maps approach constant-time lookup

Show 8 hidden lines910type TrieNode struct {11    children       map[rune]*TrieNode12    isEnd          bool13    topSuggestions []Suggestion14    mu             sync.RWMutex15}1617type Suggestion struct {18    Text      string19    Score     float6420    Frequency int6421    Trending  bool22}2324func (t *TrieNode) Search(prefix string) []Suggestion {25    t.mu.RLock()26    defer t.mu.RUnlock()2728    node := t29    for _, char := range prefix {30        child, exists := node.children[char]31        if !exists {32            return nil33        }34        node = child35    }36    return node.topSuggestions37}3839func (t *TrieNode) Insert(word string, score float64) {40    t.mu.Lock()41    defer t.mu.Unlock()42    // insertion logic with top-K propagation up the spine43}44Show 16 hidden lines61    })62    if len(candidates) > TopK {63        candidates = candidates[:TopK]64    }65    t.topSuggestions = candidates66}

Why pre-compute top-K at every node

Without pre-computation, returning suggestions for the prefix p requires traversing the entire subtree below the p node — potentially millions of descendants. With pre-computed top-K, the query is bounded by the prefix length:

• Query time: O(p) where p is the prefix length
• No subtree traversal at query time
• Predictable latency, regardless of how popular the prefix is

The trade is build time. Top-K must propagate up the trie post-order during the index build, but the build runs offline; the query path is the one that has to fit in 100ms.

FST: prefix + suffix sharing for in-memory dictionaries

A plain trie shares prefixes; a DAWG shares suffixes; an FST does both and annotates each transition with an output value (a weight, a posting offset, an ordinal). Lucene’s FST is the canonical implementation: built incrementally from sorted input, minimised on the fly, and serialized as a packed byte array that fits in a few hundred MB even for very large term dictionaries¹.

What this buys in production:

• Memory. Sharing suffixes typically halves the size of an English term dictionary versus a hash-map trie.
• Cache locality. Traversal walks contiguous bytes; modern CPUs prefetch well across the FST’s packed representation.
• Composability with automata. Lucene intersects an FST with an arbitrary Automaton (regex, fuzzy, prefix) using FSTUtil to enumerate matching paths in O(matches) rather than O(terms) — this is what makes Lucene’s FuzzyQuery viable on multi-billion-term indexes¹⁰.

Typo tolerance

A user typing progrmming should still see programming. Three families of techniques are in production use; the choice depends on corpus size, latency budget, and how dynamic the dictionary is.

How Levenshtein automaton intersection works. For a query string q and an edit distance k, build a deterministic finite automaton A_{q,k} that accepts every string within Levenshtein distance ≤ k of q. The states of A_{q,k} track (position in q, edits used so far); for k=2 the automaton has at most a few hundred states regardless of |q|. Then walk the FST and A_{q,k} in lockstep — at every FST byte, check whether A_{q,k} can still reach an accepting state; if not, prune the entire subtree. Lucene compiles A_{q,k} once and intersects it with the term FST using FSTUtil; this is the optimization that took FuzzyQuery from “rarely usable” to “default-on” in Lucene 4.0¹⁰.

1q = "prog"      k = 12A_{q,1} accepts: prog, prog?, prg, prog?, prog?, …  (all strings within 1 edit)3walk FST byte-by-byte; prune any path that A_{q,1} cannot complete

Why not BK-trees in production search engines. A BK-tree partitions terms by Levenshtein distance to a chosen root, then prunes by the triangle inequality. It works well for static, in-memory dictionaries up to ~1M terms but degrades on long-tail data and does not compose with prefix matching — you cannot ask “all completions of prog within edit distance 1” without two separate passes. The Levenshtein-automaton approach handles both in one traversal.

Typical bounds.

• Edit distance: 1 for short terms (≤4 chars), 2 for longer terms — Algolia, Meilisearch, and Lucene all default to this.
• Damerau-Levenshtein (adds transpositions) catches progrmaming → programming in one edit instead of two; it is the default in Lucene’s FuzzyQuery and Algolia.
• For very short prefixes (<3 chars) typo tolerance is usually disabled — the recall explosion is not worth it.

Ranking algorithm

Production rankers are two-stage: cheap candidate generation from the trie/FST followed by an expensive reranker that runs only on the few hundred candidates returned. This keeps the prefix structure pure (no per-user state in the index) and confines all expensive features to a bounded candidate list.

Coarse scoring formula (run at index build, stored in trie nodes):

1score = w1 × popularity + w2 × freshness + w3 × trending + w4 × personalization

Default weights (generic suggestions):

Trending detection (illustrative threshold):

A query is considered trending when its frequency in the most recent hour exceeds 3× its average hourly frequency over the trailing week. The 3× factor and 168h window are tunable; they should be re-derived from your own query distribution.

Show 5 hidden lines6def is_trending(query: str) -> bool:7    now = datetime.utcnow()8    hour_key = f"freq:{query}:{now.strftime('%Y%m%d%H')}"910    current = int(r.get(hour_key) or 0)1112    total = 013    for i in range(1, 169):  # 168h = 1 week14        past_hour = now - timedelta(hours=i)15        past_key = f"freq:{query}:{past_hour.strftime('%Y%m%d%H')}"16        total += int(r.get(past_key) or 0)1718    avg = total / 16819    return current > 3 * avg if avg > 0 else current > 100Show 6 hidden lines

Learning to rank with click-through data

Hand-tuned weights work for the first deploy; production systems graduate to a learned reranker once they have enough click-through data. The labelled signal is implicit: when prefix p was shown, the user either clicked one of the suggestions or submitted a different query. Pairwise objectives turn that into training data — for every shown set, the clicked suggestion should rank higher than every unclicked one.

Feature families in a typical QAC reranker:

• Query-level: prefix length, language, character class (Latin/CJK), is-numeric.
• Candidate-level: popularity (log frequency), freshness (days since last seen), edit distance from the prefix, candidate length, language match.
• Interaction: per-prefix CTR, per-(prefix, candidate) CTR, conversion-to-search-results ratio.
• User-level (when authenticated): historical CTR by category, recent searches, locale, device class.
• Session-level: previous prefix in this session, dwell time on previous suggestions, count of typed-and-deleted characters.

Elasticsearch alternative (Path B)

For teams that already operate Elasticsearch, the completion suggester is a viable Path-B implementation. It stores terms in a Lucene FST built per segment.

Index mapping:

Show 3 hidden lines4      "suggest": {5        "type": "completion",6        "analyzer": "simple",7        "preserve_separators": true,8        "preserve_position_increments": true,9        "max_input_length": 50,10        "contexts": [11          { "name": "category", "type": "category" },12          { "name": "location", "type": "geo", "precision": 4 }13        ]14      },15      "query_text": { "type": "text" },16      "frequency":  { "type": "long" }17    }18  }19}

Query:

1{2  "suggest": {3    "query-suggest": {4      "prefix": "prog",5      "completion": {6        "field": "suggest",7        "size": 10,8        "skip_duplicates": true,9        "fuzzy": { "fuzziness": 1 },10        "contexts": { "category": ["technology"] }11      }12    }13  }14}

Performance characteristics:

• Latency: typically 10-30ms (vs. <10ms for a custom trie)
• Fuzzy matching: built-in with configurable edit distance
• Index size: ~15-17× larger when combined with edge_ngram analyzer⁴
• Operational: managed service available (AWS OpenSearch, Elastic Cloud)

When to choose Elasticsearch:

1. You already run ES for document search
2. You need fuzzy matching without standing up extra infrastructure
3. Your corpus changes frequently and you want near-real-time updates
4. The team lacks the bandwidth to operate custom trie infrastructure

Frontend considerations

Debouncing strategy

Problem. Without debouncing, typing javascript at typical speed (~150ms between keystrokes) generates 10 API requests in 1.5 seconds.

Solution. Debounce with 200-300ms delay — only send the request after the user stops typing for that interval. The window matches the median human reaction time, so the UI still feels instantaneous. Pair the debounce with an AbortController so a late response from a stale prefix never overwrites a fresh one.

Show 5 hidden lines6export function useAutocomplete() {7  const [query, setQuery] = useState("")8  const [suggestions, setSuggestions] = useState<string[]>([])9  const [isLoading, setIsLoading] = useState(false)10  const abortControllerRef = useRef<AbortController | null>(null)11  const timeoutRef = useRef<number | null>(null)1213  const fetchSuggestions = useCallback(async (prefix: string) => {14    abortControllerRef.current?.abort()15    abortControllerRef.current = new AbortController()1617    setIsLoading(true)18    try {19      const response = await fetch(`/api/v1/suggestions?q=${encodeURIComponent(prefix)}&limit=10`, {20        signal: abortControllerRef.current.signal,21      })22      const data = await response.json()23      setSuggestions(data.suggestions.map((s: { text: string }) => s.text))24    } catch (error) {25      if ((error as Error).name !== "AbortError") {26        console.error("Autocomplete error:", error)27      }28    } finally {29      setIsLoading(false)30    }31  }, [])3233  const handleInputChange = useCallback(34    (value: string) => {Show 16 hidden lines51  )5253  useEffect(() => {54    return () => {55      if (timeoutRef.current) clearTimeout(timeoutRef.current)56      abortControllerRef.current?.abort()57    }58  }, [])5960  return { query, suggestions, isLoading, handleInputChange }61}

Key implementation details:

1. AbortController cancels in-flight requests when the user types more — without it, you get out-of-order responses
2. Minimum prefix length avoids the dominant 1- and 2-character buckets that match almost everything
3. Cleanup clears timeouts and aborts requests on unmount

Keyboard navigation and the ARIA combobox contract

The WAI-ARIA Authoring Practices Guide defines the canonical “editable combobox with list autocomplete” pattern. Keyboard interaction:

Required ARIA contract:

1<input2  role="combobox"3  aria-autocomplete="list"4  aria-expanded="true"5  aria-controls="suggestions-list"6  aria-activedescendant="suggestion-2"7/>8<ul id="suggestions-list" role="listbox">9  <li id="suggestion-0" role="option">programming</li>10  <li id="suggestion-1" role="option">progress</li>11  <li id="suggestion-2" role="option" aria-selected="true">program</li>12</ul>

Optimistic UI updates

For frequently-typed prefixes, render the cached suggestions immediately and refresh them when the network responds:

1const handleInputChange = (value: string) => {2  const cached = localCache.get(value)3  if (cached) {4    setSuggestions(cached)5  }67  fetchSuggestions(value).then((fresh) => {8    setSuggestions(fresh)9    localCache.set(value, fresh)10  })11}

This is the pattern Twitter’s typeahead.js uses with its Bloodhound engine: prefetch a static suggestion set into localStorage, then backfill from a remote when the local index is insufficient.

Indexing pipeline

Pipeline architecture

Batch vs. streaming

Dual-path approach:

1. Weekly batch: complete trie rebuild from all query logs
2. Sub-hour hot updates: merge trending queries into the running trie
3. Real-time streaming: update trending flags and frequency counters

Aggregation job

Show 10 hidden lines11    .filter(col("query") != "")12    .filter(~col("query").rlike(r"[^\w\s]"))13    .groupBy("query")14    .agg(15        count("*").alias("frequency"),16        spark_max("timestamp").alias("last_seen"),17        when(18            col("recent_freq") > 3 * col("avg_freq"),19            True20        ).otherwise(False).alias("trending")21    )22    .filter(col("frequency") >= 10)23    .orderBy(col("frequency").desc())24)2526max_freq = aggregated.agg(spark_max("frequency")).collect()[0][0]27scored = aggregated.withColumn(28    "score",29    col("frequency") / max_freq * 0.5 +30    when(col("trending"), 0.2).otherwise(0.0)31)3233scored.write.parquet("s3://autocomplete-data/aggregated/2024-02-03/")

Trie serialization

To make snapshots cheap to ship and load, serialize the trie to a compact binary format and gzip it:

Show 8 hidden lines9func (t *TrieNode) Serialize(path string) error {10    file, err := os.Create(path)11    if err != nil {12        return err13    }14    defer file.Close()1516    gzWriter := gzip.NewWriter(file)17    defer gzWriter.Close()1819    encoder := gob.NewEncoder(gzWriter)20    return encoder.Encode(t)21}2223func LoadTrie(path string) (*TrieNode, error) {24    file, err := os.Open(path)25    if err != nil {26        return nil, err27    }28    defer file.Close()2930    gzReader, err := gzip.NewReader(file)31    if err != nil {32        return nil, err33    }34    defer gzReader.Close()3536    var trie TrieNode37    decoder := gob.NewDecoder(gzReader)38    if err := decoder.Decode(&trie); err != nil {39        return nil, errShow 3 hidden lines

Compression ratios (illustrative):

Chosen: Gob + Gzip for storage efficiency. The extra load time is acceptable for weekly rebuilds.

Caching strategy

Multi-layer cache

The hit rates are targets, not measurements; the actual cascade depends heavily on prefix distribution and how cacheable your responses are (anonymous vs. personalized, language-segmented, etc.).

Browser caching

1HTTP/1.1 200 OK2Cache-Control: public, max-age=36003ETag: "v1-abc123"4Vary: Accept-Encoding

• 1-hour TTL balances freshness and hit rate for stable popular prefixes
• ETag enables conditional revalidation when the cache goes stale
• Vary: Accept-Encoding keys the cache by encoding to avoid serving gzip to a client that did not request it

CDN configuration

1# Cloudflare page rules2rules:3  - match: "/api/v1/suggestions*"4    actions:5      cache_level: cache_everything6      edge_cache_ttl: 300       # 5 minutes7      browser_cache_ttl: 3600   # 1 hour8      cache_key:9        include_query_string: true

Cache key design. The full query string must be part of the key. /suggestions?q=prog and /suggestions?q=progress are different cache entries — collapsing them produces wrong answers.

Redis hot-prefix cache

Show 5 hidden lines6def get_suggestions(prefix: str) -> list | None:7    cache_key = f"suggest:{prefix}"89    cached = r.get(cache_key)10    if cached:11        return json.loads(cached)1213    suggestions = query_trie(prefix)1415    if is_hot_prefix(prefix):16        r.setex(cache_key, 600, json.dumps(suggestions))  # 10 min TTL1718    return suggestions1920def is_hot_prefix(prefix: str) -> bool:21    """Hot if queried >1000 times in the last hour."""22    freq_key = f"freq:{prefix}:{current_hour()}"23    return int(r.get(freq_key) or 0) > 1000

Infrastructure

Cloud-agnostic architecture

AWS reference architecture

Service configuration (rough sizing):

Deployment strategy

Blue-green for trie updates:

1. Build the new trie version in an offline cluster
2. Load it into “green” service instances
3. Smoke-test green
4. Switch the load balancer to green
5. Keep blue running for 1 hour for fast rollback
6. Terminate blue

Rolling updates for code changes:

Show 8 hidden lines9    minimumHealthyPercent: 10010  deploymentController:11    type: ECS12  healthCheckGracePeriodSeconds: 6013  loadBalancers:14    - containerName: trie15      containerPort: 808016      targetGroupArn: !Ref TargetGroup

Monitoring and evaluation

Key metrics

Business metrics

Observability stack

1monitors:2  - name: Autocomplete P99 latency3    type: metric alert4    query: "avg(last_5m):p99:autocomplete.latency{*} > 100"5    message: "P99 latency exceeded 100ms threshold"67  - name: Trie service error rate8    type: metric alert9    query: "sum(last_5m):sum:autocomplete.errors{*}.as_rate() / sum:autocomplete.requests{*}.as_rate() > 0.001"10    message: "Error rate exceeded 0.1%"1112  - name: Cache hit rate drop13    type: metric alert14    query: "avg(last_15m):autocomplete.cache.hit_rate{layer:redis} < 0.6"15    message: "Redis cache hit rate below 60%"

Multi-tenant isolation

If you serve autocomplete for many products, customers, or business units from one platform, isolation drives the architecture more than raw throughput.

Engineering rules.

• Quotas at the edge. Per-tenant QPS, payload size, and concurrent-request limits enforced at the API gateway, not the trie service. Reject early — autocomplete cannot afford queueing.
• Tenant-aware sharding. Hash the (tenant_id, prefix) tuple instead of just the prefix when tenants share shards, otherwise two tenants with the same vocabulary co-locate and amplify hot spots.
• Per-tenant rebuild cadence. Big tenants rebuild on their own schedule; long-tail tenants share a batched rebuild. Avoid one global Spark job that blocks on the slowest tenant.
• Cache namespacing. cache_key = sha1(tenant_id || prefix || locale || lang). Skipping tenant_id is the canonical multi-tenant footgun — one tenant sees another’s suggestions and you make the front page of an outage report.
• Noisy-neighbour controls. Token-bucket rate limiting per tenant and per IP within a tenant, with a circuit breaker that returns cached results when a tenant’s traffic exceeds their plan.

Failure modes and recovery

Practical takeaways

• Two-stage retrieval beats one-stage every time: cheap candidate generation from the trie/FST, expensive reranking on a bounded candidate set.
• Pre-computed top-K trumps ranking-at-query-time when latency is the binding constraint; reserve query-time work for the reranker.
• For typo tolerance, intersect a Levenshtein automaton with the prefix index; do not stand up a BK-tree unless the dictionary is small and static.
• Cache hierarchies before sharding tricks: most QPS should never reach your trie. Always include tenant_id and locale in the cache key.
• Dual-path indexing buys both stable rankings (batch) and freshness (streaming) without forcing you to pick.
• Graduate from hand-tuned weights to learning-to-rank once you have ~100K shown-and-clicked sets per surface; debias for position before training.
• Build the WAI-ARIA combobox contract before you build the dropdown — retrofits are painful.
• Pick Path B (Elasticsearch) when fuzzy matching and near-real-time updates matter more than every last millisecond. Pick Algolia / Typesense when the team’s bandwidth is the binding constraint.

Appendix

Prerequisites

• Distributed-systems fundamentals (sharding, replication, consistency)
• Data structures: tries, hash maps, sorted sets
• Caching strategies (TTL, invalidation, stampede control)
• Stream processing concepts (Kafka, event sourcing)

Terminology

References

• LinkedIn Engineering — Cleo: open source typeahead — multi-layer architecture serving generic typeahead in ≤1ms
• Twitter Engineering — Typeahead.js: You Autocomplete Me — client-side typeahead library design
• Microsoft Research — Learning to Personalize Query Auto-Completion — personalization impact on MRR (~9% lift)
• Microsoft Research — Deep Learning Methods for Query Auto Completion — survey of LSTM and pairwise LTR for QAC
• Amazon — Deep Pairwise Learning To Rank For Search Autocomplete — DeepPLTR vs LambdaMART on production traffic
• SIGIR 2022 — Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion — debiased QAC reranker
• EMNLP 2024 — Diversity Aware Listwise Ranking for Query Auto-Complete — DiAL listwise ranker
• Bing Search Blog — A Deeper Look at Autosuggest — Bing’s popularity-weighted trie and refresh cadence
• Elasticsearch Labs — autocomplete: search-as-you-type, query time, and more — completion suggester and edge n-gram comparison
• Mike McCandless — Using Finite State Transducers in Lucene — FST internals from the implementer
• Mike McCandless — Lucene’s FuzzyQuery is 100 times faster in 4.0 — Levenshtein automaton ⊗ FST
• Lucene API — FSTCompletion and FuzzyQuery
• Algolia — Inside the Algolia Engine, Part 1 and Part 2 — C++/NGINX engine, indexing-vs-search separation, radix tree
• Algolia — Typo tolerance — Damerau-Levenshtein bounds and configuration
• Typesense — Query Suggestions and FAQ — in-memory ART, on-disk JSON, infix mode
• WAI-ARIA APG — Combobox with list autocomplete — canonical pattern for accessible autocomplete
• Algolia — debouncing autocomplete sources — UX research on debounce timing
• RFC 9111 — HTTP caching — Cache-Control, ETag, Vary semantics