28 — Search autocomplete

Autocomplete shows a short list of likely queries while someone types into a search box. Each keystroke is a request, the answer has to arrive before the next keystroke, and the list should reflect what people search for now rather than last year. It’s a read-heavy system with a strict latency budget, and most of its work happens offline.

Requirements

Functional

• Given a prefix, return the top 10 completions, ranked by popularity.
• Popularity reflects recent searches more than old ones.
• Filter out unsafe or blocked suggestions.
• Tolerate small typos.
• Optionally, blend in the user’s own recent searches.

Non-functional

• Fast. The suggestions have to appear while the user is still typing.
• Highly available. If autocomplete is down, search still works, so it’s acceptable to return nothing. Returning errors or slow responses is worse.
• Fresh enough. Hours of delay are fine for most queries. Breaking news is the exception, discussed below.
• Read-only at serving time. Searches are logged, and the index is built elsewhere.

Estimates

The method is from chapter 4. These inputs are assumptions:

The data is small. Ten million queries at 20 bytes each is 200 MB of text. Even with an index several times that size, a full copy fits in one server’s memory, so serving from RAM on every replica is the natural design. The challenge is latency and request rate, not storage.

The latency budget

Assume a target of 100 ms from keystroke to rendered suggestions. That’s an assumption, but a useful one: anything much slower lags behind typing. A rough split:

The lookup itself is a tiny share. The network dominates, which is why serving close to users and caching responses at the edge matter more than shaving microseconds off the data structure. The data structure still matters, because a slow structure makes the tail worse under load (chapter 10).

API

GET /v1/suggest?q=new%20yo&limit=10&locale=en-US

HTTP/1.1 200 OK
Cache-Control: public, max-age=300

{"q": "new yo", "suggestions": ["new york", "new york times", "new york weather", ...]}

A GET with the prefix in the URL makes responses cacheable by a CDN and the browser. Popular short prefixes are requested by millions of people, and their answers change slowly. Personalized suggestions can’t be cached publicly, so they come from a separate call or get merged in the client.

The client also helps:

• Debounce. Wait for a short pause in typing before sending.
• Cancel stale requests. If the user typed more, the old response is useless, and out-of-order responses must not overwrite newer ones.
• Filter locally. Results for new y often contain all the answers for new yo, so the client can narrow the list without a request.

Data model

Two kinds of data exist: the raw log of searches, and the derived index.

The log is append-only and large. Each search writes an event to Kafka, and a batch or stream job aggregates it (chapter 9). Aggregated counts can live in PostgreSQL:

CREATE TABLE query_counts (
    query  text   NOT NULL,
    day    date   NOT NULL,
    locale text   NOT NULL,
    count  bigint NOT NULL,
    PRIMARY KEY (locale, query, day)
);

CREATE TABLE blocked_queries (
    pattern    text PRIMARY KEY,           -- exact string, or a normalized form
    reason     text NOT NULL,
    created_at timestamptz NOT NULL DEFAULT now()
);

The index servers don’t query PostgreSQL. A build job reads the counts, applies the blocklist, computes scores, builds the index, and writes it as a versioned file to object storage. Servers download the new version, load it into memory, and swap a pointer. The old version stays loaded until in-flight requests finish, so the swap causes no errors.

Scoring with decay

Raw counts favor old, steady queries over new ones. A decayed score weights each day by its age:

Here $h$ is the half-life. With $h = 2$ days, a search from yesterday counts 0.71 of a search today, and one from a week ago counts about 0.09. A shorter half-life reacts faster to trends, and is noisier. The decayed score can also be updated incrementally: multiply yesterday’s scores by $2^{-1/h}$ and add today’s counts, so the build never rereads old logs.

Other signals usually feed the score too: whether people clicked a result after the query, query length, and locale. Counting distinct users, rather than raw searches, makes the score harder to manipulate, because one script repeating a query thousands of times counts once.

Two index structures

The core operation is: given a prefix, return the 10 best queries that start with it.

A trie with cached top-k

A trie stores queries character by character, with one node per distinct prefix. Searching every query under a node at request time would be slow for short prefixes, so each node caches its own top 10. Building fills them bottom-up: a node’s top 10 is the best 10 among its children’s top 10s and the query ending at that node, if any. A lookup walks the prefix and returns the cached list, so its cost depends only on the prefix length. The data structure itself is covered in DSA chapter 11.

A sorted array

Sort all queries alphabetically. Every query with a given prefix sits in one contiguous range, found with two binary searches. The top 10 then has to be picked from that range at request time. The cost depends on the size of the range, which is large for short prefixes.

Measuring both

The test data is synthetic. A vocabulary of 20,000 words from the system dictionary forms 200,000 distinct queries of one to three words. Popularity is Zipf-distributed, like the access pattern in chapter 7. A week of logs is 300,000 searches a day, decayed with a 2-day half-life. The key parts of the program:

import bisect, heapq, random
from collections import Counter

K = 10
rng = random.Random(42)

words = [w.strip().lower() for w in open("/usr/share/dict/words")]
words = sorted({w for w in words if w.isalpha() and 3 <= len(w) <= 9})
rng.shuffle(words)
vocab = words[:20_000]
distinct = set()
while len(distinct) < 200_000:
    n = rng.choice((1, 2, 2, 3))
    distinct.add(" ".join(rng.choice(vocab) for _ in range(n)))
distinct = sorted(distinct)
rng.shuffle(distinct)
weights = [1 / (r + 1) for r in range(len(distinct))]          # Zipf, s = 1

DAYS, PER_DAY, HALF_LIFE = 7, 300_000, 2.0
scores = Counter()
for day in range(DAYS):                                       # day 6 is today
    decay = 0.5 ** ((DAYS - 1 - day) / HALF_LIFE)
    for q in rng.choices(distinct, weights=weights, k=PER_DAY):
        scores[q] += decay
items = list(scores.items())


class Node:
    __slots__ = ("kids", "top")
    def __init__(self):
        self.kids = {}
        self.top = []          # up to K (score, query), best first


def build_trie(items):
    root = Node()
    for q, _ in items:
        node = root
        for ch in q:
            node = node.kids.setdefault(ch, Node())
    ends = dict(items)
    def fill(node, prefix):    # bottom-up: best K of the children's lists and this node
        cands = [(ends[prefix], prefix)] if prefix in ends else []
        for ch, kid in node.kids.items():
            fill(kid, prefix + ch)
            cands.extend(kid.top)
        node.top = heapq.nlargest(K, cands)
    fill(root, "")
    return root


def trie_lookup(root, prefix):
    node = root
    for ch in prefix:
        node = node.kids.get(ch)
        if node is None:
            return []
    return [q for _, q in node.top]


def build_sorted(items):
    pairs = sorted(items)
    return [q for q, _ in pairs], [s for _, s in pairs]


def sorted_lookup(keys, vals, prefix):
    lo = bisect.bisect_left(keys, prefix)
    hi = bisect.bisect_left(keys, prefix + "\uffff")
    best = heapq.nlargest(K, range(lo, hi), key=lambda i: (vals[i], keys[i]))
    return [keys[i] for i in best], hi - lo

The harness times each build, measures memory with tracemalloc, and replays 20,000 prefixes taken from queries drawn with the same popularity. It checks that both structures return identical lists for every prefix. Results on an Apple M3 Pro with Python 3.14:

query strings themselves: 9.0 MiB (shared, not counted below)
log entries: 2,100,000  distinct queries seen: 161,279
trie     build  6.94 s   memory  442.7 MiB
sorted   build  0.08 s   memory    2.8 MiB

len trie p50 us trie p99 us sorted p50 us sorted p99 us median range
  1         0.9         2.7         627.9        1781.1        8,631
  2         1.0         2.5         101.4         435.2        1,236
  3         0.9         2.2          18.5          75.8          141
  4         1.1         2.2           6.6          28.6           23
  6         1.0         2.4           2.5           8.8           10

The trie answers every prefix in about a microsecond, whatever its length. The sorted array is slow for one- and two-character prefixes, where it has to rank thousands of candidates, and fast once the range is small. By six characters it’s competitive.

The cost is memory. These 161,279 queries have 1.5 million distinct prefixes, and every one is a trie node with a dictionary and a list of 10 tuples. That came to about 290 bytes per node, or 443 MiB, against 2.8 MiB for the sorted arrays. Python inflates both figures, but the ratio is structural: a trie stores something for every prefix, and a sorted array stores something for every query.

A hybrid

The measurement suggests a split. Short prefixes are few, very popular, and slow to scan. Long prefixes are many, rarely requested, and fast to scan. So precompute the top 10 for prefixes of up to three characters, and scan the sorted array for anything longer:

D = 3
def build_hybrid(items):
    ks, vs = build_sorted(items)
    table = {}
    for p in {q[:L] for q in ks for L in range(1, D + 1) if len(q) >= L}:
        table[p] = sorted_lookup(ks, vs, p)[0]
    return ks, vs, table

def hybrid_lookup(prefix):
    if len(prefix) <= D:
        return table.get(prefix, [])
    return sorted_lookup(hk, hv, prefix)[0]

hybrid   build  0.28 s   memory    3.5 MiB
prefixes precomputed: 2,913
hybrid len 1: p50 0.1 us  p99 0.2 us
hybrid len 3: p50 0.2 us  p99 0.3 us
hybrid len 4: p50 6.5 us  p99 25.0 us
hybrid len 6: p50 3.0 us  p99 9.5 us

It used 3.5 MiB, about one-hundredth of the trie’s memory, and its worst p99 was 25 µs, well inside the budget. The results matched the trie for every prefix. The threshold $D$ is a tuning knob: raise it if four-character prefixes turn out slow on real data.

A production trie is also far more compact than a Python one. Common techniques:

• Store query IDs, not strings, in the top-k lists: 10 four-byte IDs is 40 bytes per node.
• Compress chains. A radix tree merges nodes with one child, which removes most nodes in long, rare queries.
• Use a flat array layout with offsets, instead of pointers and hash maps, which also makes the index a file that can be memory-mapped.
• Use finite-state transducers, as Lucene does, which share suffixes as well as prefixes.

Topology

                     [ query logs ] ──> Kafka ──> [aggregation job] ──> PostgreSQL counts
                                                                            │
                                                         [index build: decay, filter, top-k]
                                                                            │
                                                              object storage: index v123
                                                                            │ download, swap
 client ──> CDN / edge cache ──> [load balancer] ──> [suggest servers: index in RAM] x N
                                                           │
                                               [personal history service]  (optional)

Every suggest server holds a full copy of the index, so any server can answer any prefix. Scaling reads means adding replicas, and there’s no coordination between them. The edge cache absorbs the most popular prefixes. One- and two-character prefixes number in the hundreds or low thousands per language, and they receive a large share of requests.

Sharding by prefix

A full copy per server works while the index fits in memory. If it doesn’t, for example with many languages or much longer tails, the index gets split by prefix (chapter 11). There are two obvious ways, and they balance differently. The same harness counted how 20,000 popularity-weighted requests land on 8 shards:

SHARDS = 8
letters = sorted({q[0] for q in distinct})
letter_shard = {c: i * SHARDS // len(letters) for i, c in enumerate(letters)}  # contiguous ranges
for q in traffic:
    by_letter[letter_shard[q[0]]] += 1
    by_hash[zlib.crc32(q[:2].encode()) % SHARDS] += 1

shard load, busiest / mean: first-letter ranges 2.26x, hash of 2-char prefix 1.50x

Contiguous letter ranges put 2.26 times the average load on the busiest shard. Real text is more skewed than this synthetic set, because initial letters aren’t equally common in any language. Hashing the first two characters spread the load better, though not evenly, because a few very popular queries dominate whichever shard holds their prefix.

Hashing has a cost. A one-character prefix like n covers every shard that holds na, ne, no and the rest, so it needs either a scatter-gather across shards or a separate small table of short prefixes replicated everywhere. The second is the hybrid design again: the short-prefix table is small, so every server keeps a full copy, and only long-prefix lookups go to a shard. Range-based shards can also be rebalanced by splitting a busy range at a finer boundary, such as sa–sm and sn–sz, guided by measured load rather than by letters.

Freshness

The daily build handles most queries. Two cases need more:

• Trending queries. When something breaks in the news, its queries spike within minutes. A streaming job counts recent searches in short windows, and pushes a small “trending” overlay to the servers, merged with the main results at request time.
• Removals. A suggestion that has to go, for legal or safety reasons, can’t wait for tomorrow’s build. Servers check a small blocklist at request time, updated within seconds, in addition to filtering at build time.

The overlay and the blocklist are small enough to replace frequently. The main index is large enough to rebuild only in batch.

Filtering

Autocomplete puts words in front of people who didn’t type them, so a bad suggestion causes more harm than a bad search result. Common layers:

• A blocklist of exact queries and normalized patterns, applied in the build.
• Classifiers for adult, violent or hateful content, also applied in the build.
• A minimum number of distinct users before a query can appear. This blocks queries that one person or one script made popular, and it keeps one person’s rare searches from being shown to others.
• The request-time blocklist above, for urgent removals.

Personalization

A user’s own recent searches are usually the best suggestions for that user. They can’t come from the shared index or a public cache, so a separate service stores a short history per user, perhaps the last 100 queries in a key-value store. The client or an aggregation layer merges the two lists, typically by placing matching personal queries first and filling the rest from global results. Location and language select which index to use, rather than changing the ranking within it.

Typo tolerance

A user who types nwe yo still means new yo. The simplest approach generates every string within edit distance 1 of the prefix, meaning one deletion, insertion, substitution or swap of adjacent characters, and looks each one up. For a prefix of length $n$ over an alphabet of size $a$, that’s about $n(2a + 2) + a$ candidates before removing duplicates, a few hundred for six characters.

ALPHA = "abcdefghijklmnopqrstuvwxyz "
def edits1(w):
    splits = [(w[:i], w[i:]) for i in range(len(w) + 1)]
    deletes = [a + b[1:] for a, b in splits if b]
    swaps = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b) > 1]
    replaces = [a + c + b[1:] for a, b in splits if b for c in ALPHA]
    inserts = [a + c + b for a, b in splits for c in ALPHA]
    return set(deletes + swaps + replaces + inserts)

def fuzzy(prefix):
    exact = trie_lookup(root, prefix)
    if len(exact) == K or len(prefix) < 4:      # only correct when exact results run short
        return exact, 0
    cands = edits1(prefix)
    pool = []
    for c in cands:
        node = root
        for ch in c:
            node = node.kids.get(ch)
            if node is None:
                break
        else:
            pool.extend(node.top)
    best = heapq.nlargest(K, set(pool) | {(scores[q], q) for q in exact})
    return [q for _, q in best], len(cands)

The fuzzy lookup only runs when the exact prefix returns fewer than 10 results and is at least four characters long. It then merges the top lists of all candidates that exist in the trie. A test took 2,000 queries, cut each to six characters, and introduced one swap or wrong letter:

typos (6-char prefix, one swap or substitution): intended query in top 10 for 94%;  candidates tried p50 351;  p50 88 us, p99 119 us

It found the intended query 94% of the time, in under 0.12 ms. That’s affordable for the minority of requests that need it, and too slow to run on every keystroke. A real ranking would also penalize corrected matches relative to exact ones, which this test didn’t.

Alternatives scale better. Character n-gram indexes split queries into overlapping three-letter pieces and find candidates sharing most of them. The symmetric delete method precomputes deletions of every indexed term, so a lookup only generates deletions of the input. Both trade index size for lookup speed.

Failure modes

The takeaway

Autocomplete is a precomputed answer to a small set of questions. A trie with cached top-k makes every lookup fast and costs memory for every prefix. A sorted array is compact and slow only for short prefixes. Precomputing just the short prefixes got most of both. The rest of the system is about keeping that precomputed answer fresh, safe and close to the user.