How to design search autocomplete

In this lesson, we’ll design the drop-down list of suggestions under a search box. It has two halves: how it gets built, and how it gets served. We work through both, and every number we rely on is derived here. By the end you’ll be able to defend the 24 ms retrieval budget, size the index and decide whether it shards or replicates, say why the index is rebuilt instead of updated live, and name the client-side moves that delete most of the traffic.

The estimation habits it leans on (rounding, latency numbers) are covered in the back-of-the-envelope chapter, but you do not need to read it first.

What goes in, and what comes out

The input is a prefix (the characters typed so far, such as car) plus a locale like en-US. A locale is a language-and-region pairing; it is the unit in which suggestions differ, because what people search in Japan is unrelated to what they search in the United States. The output is an ordered list of ten complete queries that start with those characters, most popular first: carrot cake, car rental, and so on.

That is the whole contract. There is no personalization in the server response, no query is run against a document corpus, and nothing about the answer depends on who is asking. The suggestion for a prefix is the same for every user in a locale, so this is a cache-fill problem, not a query problem. The interesting question is how the cache gets filled and how stale it is allowed to be.

Ranking the suggestions themselves (understanding what a query means, personalizing per user, correcting spelling) is a machine-learning problem and is out of scope here. The retrieval half of that problem is covered in the video-search retrieval chapter.

The two numbers that force the design

The latency budget starts from what “feels instant”: under 100 ms from keypress to painted list. Most of that is already spoken for by the client’s debounce, the network round trip, and the browser drawing, and after those retrieval gets about 24 ms (derived below). That budget forbids a database query, forbids a hop to another region, and forbids any structure not already in the memory of a machine near the user.

Write amplification is the ratio between the work a system does internally and the useful change that work produces. The classic structure for prefix lookup is a trie: a tree where each edge is one character, so the path from the root spells out a prefix and everything beneath a node shares it. To make a read a lookup instead of a search, you store the top-k answer at each node (the k highest-ranked completions beneath it, here k = 10), computed in advance. Precomputing is what makes reads cheap, and also what makes writes expensive: every incoming search must update the stored list at every node on its path. That comes to roughly 5,000 units of internal work for every one that changes anything a user could see (derived below), which is why the index is a build artifact shipped on a schedule, not a live data structure.

Requirements

Functional

• suggest(prefix, locale) -> top 10 completions, ordered by popularity.
• Suggestions come from real query traffic, not an editorial list.
• Fresh terms (a breaking-news phrase) must be suggestable within minutes.
• Abusive, illegal, and blocklisted strings must never be suggested.

Out of scope, because none of them changes the storage or serving architecture: personalization ranking, spelling correction, and multi-language transliteration (typing one script for a language written in another, such as Latin letters for Hindi).

Non-functional

p99 means the 99th percentile: the number 99 of every 100 requests come in under, describing the slow tail, not the typical case.

The consistency row licenses everything else. There is no read-your-writes promise, no transaction, and no ordering guarantee to preserve, which is what makes an hours-old immutable image an acceptable answer. An immutable image is a frozen, read-only snapshot of the whole index: never modified in place, only replaced wholesale.

Load-bearing assumptions

Some assumptions, if wrong, give you a different architecture. Others only change how much hardware you buy. The load-bearing ones:

• The answer for a prefix is identical for everyone in a locale. If false, responses stop being cacheable, the edge cache and the client-side head blob both die, and ranking becomes a per-request ML serving problem.
• No consistency is required; tens of minutes of staleness is fine. If false, the index must become writable and replicated live, which is exactly the expensive write path this design rejects.
• The vocabulary fits in one machine’s memory (100 M queries, ~23 GB). If false, replication is replaced by partitioning within a locale, which reintroduces the hot-key problem.
• You control the client, so it can debounce, sequence requests, and hold a cached head. If false, the traffic reduction from the browser disappears.
• Ranking is popularity from query logs, not a learned model. If false, a precomputed top-10 per node is no longer a valid answer.
• The perceived target is 100 ms. If false, and 500 ms is acceptable instead, a database prefix scan becomes legal and most of this design evaporates.

The soft ones just scale the machine count: 500 M daily active users, 8 searches each, 8 keystrokes per search; peak at 3x the mean; 50 locales across 6 regions with 3 copies per region; a 26-character alphabet after case-folding.

Back of the envelope

Four numbers drive everything: the request rate, the milliseconds left to answer one, the index size, and whether it fits on one machine. Rates below use round numbers (a day treated as 100,000 seconds); redo any figure exactly before it becomes a purchase order.

Volume

DAU is daily active users; QPS is queries per second.

500 M DAU × 8 searches × 8 keystrokes is about 32 billion suggest requests a day, roughly 320,000 QPS mean and 960,000 at peak (3x). The searches those keystrokes decorate are 8x fewer, so:

Autocomplete generates about 8x the request rate of the search it decorates, for a result nobody explicitly asked for. Every decision here is about deleting requests or making them absurdly cheap.

Bytes matter too, which is unusual for a system this small per request. A response is about 400 B (ten suggestions plus framing), so peak egress is roughly 960,000 × 400 ≈ 3 Gbps worldwide. That is a floor of a few machines’ worth of network cards, but request rate binds first, not bandwidth.

The latency budget, which is the design

Start from the user’s 100 ms and deduct everything that is not retrieval:

perceived budget, keypress to painted list           100 ms
  debounce before the request is sent                 50
  client -> regional PoP, warm HTTP/2, 1 RTT          20
  PoP -> service and back, same datacenter             1
  deserialize + paint                                  5
                                                      ---
  what retrieval gets                                 24 ms

A PoP (point of presence) is a small cluster the provider runs close to users. Twenty-four milliseconds is easier to reason about as operations it can pay for, using standard latency figures:

• a memory reference (one RAM read) is ~100 ns, so 24 ms buys ~240,000 of them,
• an SSD random read is ~100 µs, so ~240 of them,
• a disk seek (a spinning disk moving its head) is ~10 ms, so ~2.4 of them.

Three conclusions, each killing a tempting design:

• A cross-continent round trip is ~150 ms, six times the whole budget. The index must be replicated into every region its users are in.
• You get 2.4 disk seeks. A relational prefix scan is not slow here, it is arithmetically impossible.
• You get 240,000 memory references. In-memory anything is affordable; the design problem is what fits in memory.

How big is the thing that must fit in memory

Case-folding treats upper and lower case as the same character, so the effective alphabet is 26.

A plain character trie storing 100 M queries of ~20 characters is about 1.5 billion nodes, and almost all of them have exactly one child. Below the depth where prefixes become distinct (around 6 characters), a node like the chain c -> a -> r -> r -> o -> t is a link in a chain, not a branch point. Collapse each one-child chain onto a single edge and you get a radix tree: a trie with the one-child chains squeezed out.

flowchart TD
    subgraph T["Character trie: one node per character"]
        C1["c"] --> C2["a"] --> C3["r"] --> C4["r"] --> C5["o"] --> C6["t (carrot)"]
    end
    subgraph R["Radix tree: chains collapsed onto edges"]
        RN["car"] --> RL["rot (carrot)"]
    end

A radix tree has at most one branch point and one leaf per query, so about 200 M nodes (a 7.6x compression). With the shape settled, the bytes fall out per tier:

A commodity box carries 64-256 GB of memory; default to 128 GB. Twenty-three gigabytes fits comfortably, which deletes a whole section a reader expects. Sharding splits one dataset across machines; replication gives several machines the same complete copy. At this size the index is not sharded, it is replicated. (Sharding returns later, for a different reason.)

API sketch

Two endpoints. The first answers one prefix; the second hands the browser a thousand prefixes at once (the head blob, priced later).

GET /v1/suggest?q=car&locale=en-US&n=10&seq=7
  200 {"prefix": "car", "seq": 7,
       "suggestions": [{"t": "carrot cake", "s": 8123},
                       {"t": "car rental",  "s": 7740}, ...]}
  200 {"prefix": "xqz", "seq": 8, "suggestions": []}
  Cache-Control: public, max-age=300

GET /v1/suggest/head?locale=en-US
  200 gzip blob of the top 1,000 prefixes, loaded once per session

Three deliberate choices:

• seq is echoed back. It is the client’s keystroke counter. The client drops any response whose seq is below the highest it has already drawn, which defends against the ordering bug covered in the client deep dive.
• Cache-Control: public, legal only because the response is not personalized. The same prefix and locale produce the same bytes for everyone, so an edge PoP can serve it. Personalization still happens, on the device, by blending a locally kept history list into the result. Keeping personalization on the client is what keeps the server response cacheable.
• An empty list, never a 404. A prefix with no completions is a normal outcome, not an error. A 404 would force the client to tell “nothing matched” apart from “the service is broken”.

Data model: what is built, and what serves

The tree the offline pipeline builds is not the thing that serves.

build artifact (offline)
  radix tree over 100 M queries
    node: edge label, children, subtree count, cached top-10 ids

serving artifact (in every process)
  the same tree, serialized into one flat mmap-able byte array:
    nodes as fixed-width records, children as offsets not pointers
    a separate string table, addressed by 4-byte id
  plus: trending overlay, a small hash map of prefix -> top-10, hot-swapped
  plus: blocklist bloom filter, checked at render time

The key move is offsets, not pointers. A pointer is a memory address, valid only inside the process that created it; an offset is a distance in bytes from the start of the array, valid on any machine. A pointer-based tree cannot be copied to another machine and used; a flat array of offsets can be mmaped (mapped directly into a process’s address space) straight off disk and read as-is.

Two consequences. The operating system’s page cache (shared memory holding recently read file pages) means every process on the box shares one copy, so 23 GB is paid once per machine, not once per process. And swapping in a new index is atomic: installing it is opening a new file and flipping a single reference, so no reader ever sees a half-installed index.

The string table is separate for a reason: one entry in a cached top-10 list costs 8 bytes (a 4-byte id plus a 4-byte score) instead of ~30 bytes of text. Storing strings inline would multiply the 16 GB top-k tier by about 4x. Looking an id up in the table is a single array index.

The bloom filter is a compact probabilistic set that answers “is this string blocklisted?” using a few bits per entry. It can say definitely not or probably yes, and never misses a real member. That is the safe direction of error for a blocklist: it may occasionally suppress an innocent suggestion, but never lets a blocked one through.

High-level architecture

The design has two halves that meet at one box. The read path runs downward from the browser. The build path feeds an hourly rebuild, with a faster streaming lane beside it. They meet at the suggest service, the only box both halves touch. The query log is the one authoritative store; every other store is derived from it and could be rebuilt by replaying it.

flowchart TD
    U["Browser<br/>debounce 50 ms · seq counter<br/>top-1,000 head blob in memory"]
    U -->|"miss on the local head"| PoP["Edge PoP<br/>public cache, 5 min TTL"]
    PoP -->|"miss"| SVC["Suggest service<br/>23 GB mmap'd radix image<br/>+ trending overlay"]
    SVC --> BL{"Blocklist bloom"}
    BL -->|"clean"| RESP["top 10"]
    BL -->|"hit"| FILT["drop the entry,<br/>promote the next"]

    LOG[["Query log (authoritative)<br/>4 billion events/day"]] --> AGG["Hourly aggregation<br/>count, dedupe by user, filter"]
    AGG --> BUILD["Trie build<br/>top-k cached at every node"]
    BUILD --> DIST["Tree fan-out to 18 replicas<br/>15.3 min"]
    DIST --> SVC

    LOG --> TREND["Streaming detector<br/>count-min sketch, 30 s window"]
    TREND -->|"400 KB every 30 s"| SVC

On the read path, the browser debounces 50 ms and tags each request with a seq counter, checks its own top-1,000 head blob (most keystrokes stop here and never leave the machine), then on a miss hits an edge PoP with a 5-minute TTL cache (TTL, time-to-live, is the age at which a cached copy is discarded), then on a miss there reaches a suggest service that reads its mmaped radix image plus the trending overlay. Every candidate is checked against the blocklist bloom filter; a hit is dropped and the next entry promoted, so ten results still come back.

On the build path, the query log collects ~4 billion events a day. Hourly aggregation counts occurrences, dedupes repeated searches by the same user (so one person cannot vote twice), and filters blocked and low-quality strings. The trie build produces a radix tree with top-k cached at every node. Distribution ships the finished image by tree fan-out to 18 replicas in ~15.3 minutes.

Beside all of that, a streaming detector reads the same log continuously through a count-min sketch over a 30-second window and pushes 400 KB to the serving processes every 30 seconds, carrying freshness the batch pipeline cannot.

Deep dive 1: the trie, and why top-k is cached at every node

A trie gives you prefix matching: given car, it finds the subtree of everything starting with car. It does not give you ranked prefix matching, which is what a user needs. Closing that gap is where the memory goes.

Without a cache, ranking happens at read time by traversal: walking every descendant of the prefix node and keeping the ten highest counts. A one-character prefix like s has roughly 100 M / 26 ≈ 3.85 M descendants. At ~100 ns per memory reference that is about 385 ms, which is 16x over the 24 ms budget on the most common prefix in the system. And 385 ms is optimistic, because chasing tree pointers has poor locality (data used together sitting close in memory), so the processor cache cannot help. Short prefixes are cheap to find and ruinous to rank, which is the opposite of what most search intuition would suggest.

With the cache, the offline build stores the top ten at every node. A read walks down one node per character (at most ~20 for a 20-character query), reads the stored list, and returns it: about 2 microseconds. That is roughly 192,500x faster, bought with the 16 GB top-k tier. The whole index is 23 GB against a 128 GB box, so it is affordable.

You do not have to cache at every node. A node whose subtree is small is cheap to traverse at read time. Set the threshold from the budget: one millisecond of traversal buys 10,000 node visits, so cache only at nodes with more than 10,000 descendants. At most 100M / 10,000 = 10,000 nodes can clear that threshold at any one depth (the descendants have to come from somewhere), and over 20 depths that is at most 200,000 nodes out of 200 million, roughly a 100x saving. Take selective caching when memory is tight; take full caching when it is not, because it removes a whole class of slow-tail surprises. A subtree count stored at every node is what makes the threshold checkable at read time.

The cache is not free in a second currency, though. Caching top-k at every node means one new query event can invalidate the stored list at all ~20 of its ancestors, and each becomes a read-modify-write on exactly the nodes every read also touches. That write cost is the whole of the next section.

Deep dive 2: why the index is rebuilt, not updated

The write amplification

A live-update design bumps the counter at a query’s node and refreshes the cached list at every node above it, so the multiplier is the tree depth. That is 4 billion events × 20 ancestors = 80 billion node updates a day, about 800,000 per second.

But volume alone is not the argument. A node’s cached top-10 only moves when a query’s count crosses whatever sits in tenth place; every other increment leaves the rendered list byte-for-byte identical. Measured over a week of logs, only about 0.02% of ancestor touches actually reorder a list, so roughly 16 million real changes a day hide inside 80 billion updates: a 5,000:1 waste ratio.

Placement is worse than volume. Every event touches the root, so that single node takes ~40,000 writes per second while serving ~960,000 reads per second at peak. Those writes must be serialized (one after another, because two editing the same list at once would corrupt it), and a lock on the root is effectively a global lock. Going lock-free only moves the contention from software to one hardware cache line shared by every core.

The writes do not stay in one datacenter either. Each of the 800,000 updates per second must reach every replica of that locale’s index (18 of them, derived below), which is 14.4 million replication messages per second to keep consistent a structure that has no consistency requirement.

The batch alternative

Doing the whole day’s ranking offline is cheap by comparison. The raw log is ~160 GB/day (4 billion events × 40 B). One machine reads that sequentially in ~160 s at 1 GB/s; aggregating, sorting, and building costs roughly 10x the scan, or ~1,600 machine-seconds, which is ~32 s across 50 machines. Real builds land in tens of minutes because they are shuffle-bound (the slow part of a distributed aggregation is the network step moving every record to the machine that owns its key), but the comparison holds: 1,600 machine-seconds of batch work against a live path that wastes 5,000:1.

Distribution sets the freshness floor

Building the index is the cheap part; copying it to every serving machine is what bounds freshness. One origin pushing 23 GB to 18 replicas over its own 1 Gbps link is 414 GB of egress, about 55 minutes, which eats the whole hourly cadence.

The fix is tree fan-out: on each hop, every machine that already holds the image seeds exactly one more, so the population of holders doubles. One image transfer is ~184 s at 1 Gbps, and covering 18 machines takes ceil(log2 18) = 5 hops, or ~15.3 minutes for the same bytes, because 18 machines upload instead of one.

flowchart TD
    O["Origin (hop 0)"] --> A["holder"]
    O --> B["holder"]
    A --> C["holder"]
    A --> D["holder"]
    B --> E["holder"]
    B --> F["holder"]
    G["...doubles each hop: 5 hops cover 18 replicas"]

Build plus distribution is tens of minutes, so an hourly cadence is the natural floor, and average staleness is about 30 minutes (half the interval, since a request is equally likely anywhere inside it). Nobody chose hourly; the 23 GB image and the 1 Gbps link chose it. To push freshness tighter, shrink the image with delta shipping (send only the ~16 million node lists that actually moved), not the scheduler.

The exception: terms that cannot wait an hour

An hour is fine for carrot cake and useless for a name that did not exist at breakfast. The failure is asymmetric: a trending term is exactly the one everyone is typing, so an hour of blindness hides the highest-value suggestions.

The fix is a small side-channel: a table of the hottest few thousand prefixes, pushed far more often than the image. At 5,000 prefixes × 10 suggestions × 8 B it is 400 KB, which is 0.0017% of the 23 GB image, pushed to 18 replicas every 30 s (~1.9 Mbps). Three parts make it work:

• Detection uses a count-min sketch: a small fixed-size table of counters, hashed into several times per item, estimating how often each item has been seen using a few kilobytes instead of one counter per term. It occasionally overestimates, never underestimates.
• The trigger flags any term whose 5-minute rate jumps against its trailing 24-hour rate (rising sharply against its own baseline), subject to a floor on distinct users so one script cannot fire it.
• Merging happens at read time: the service overlays the fresh list on the baked-in list for the same prefix.

A large slow-moving artifact plus a tiny fast-moving overlay, merged at read time, is a shape that recurs across systems. You get batch economics on 99.998% of the data and streaming freshness on the 0.002% that needs it, and you never make the big structure writable.

Deep dive 3: sharding, why the obvious key skews, and the client head blob

One machine stops being enough when more locales or a bigger vocabulary arrive. English at 23 GB fits one box, but 50 locales together (English at 23 GB plus 49 others at ~30% of it) is about 361 GB, which needs 3 boxes at the 128 GB default. Something has to split; the question is on what key.

Sharding by first character fails

The instinct is 26 machines, one per first letter. But the alphabet is not uniform. Measured over a month of English logs, s is about 8.1% of traffic against a uniform share of 1/26 = 3.85%, and the coldest letters (x, z) are near 0.2-0.4%. So the hottest shard runs 2.1x the mean and ~40x the coldest. You must provision all 26 shards for the hottest one, and the skew shifts with language and with the news.

Hashing helps, then stops

Routing on a hash of the first three characters (which scrambles the key so adjacent prefixes land on unrelated shards) gives 17,576 buckets to spread across shards. The coefficient of variation (CV, standard deviation over mean, where 0 is perfectly even) drops from roughly 0.7 for letter-sharding to about 0.039 at the same 26 shards. This is the virtual-node result from the consistent-hashing chapter.

But hashing fixes variance (random lumpiness), not a hot key: one popular prefix hashes to one shard however good the hash is. Fitting query frequencies with Zipf (the nth most popular item gets traffic proportional to 1/n, the standard fit for query frequencies) within s puts the hottest three-character bucket at about 1.1% of traffic, and the shard holding it still runs ~2.1x the mean. Hashing removed the random lumpiness but not the skew from a single hot prefix.

A useful sanity check: containment. Every query starting with sea also starts with s, so no three-character bucket can be hotter than its first letter (8.1%). A naive Zipf fit across all 17,576 buckets returns 9.7%, which is impossible on its face. Run that check before quoting any Zipf number.

Shard by locale instead

Do not shard by prefix at all. Shard by locale and replicate each locale’s whole index:

• Each index is 7-23 GB, inside one box, so a lookup is always local. No scatter-gather (fanning one request out to many shards and combining answers), and therefore no tail-latency amplification where a request is as slow as its slowest shard.
• Load per locale is known and stable, and replicas are placed where that locale’s users are, satisfying the regional-latency requirement for free.
• The hot-prefix problem dissolves into replication: a prefix that is 1.1% of one locale’s traffic is served by every one of that locale’s replicas instead of by one machine.

Replicating the head into the browser

The most popular prefixes (the head of the distribution, versus its long tail of rare ones) can be replicated one level further out than any server: into the browser. Under the Zipf fit, the top m of K buckets cover ln(m) / ln(K), so the top 1,000 of 17,576 cover about 71% of all requests. Those 1,000 prefixes are ~300 KB of text, or ~100 KB gzipped, fetched once per session.

A 100 KB blob answers 71% of suggest requests with zero network latency, taking peak QPS from 960,000 to about 281,280. It is the single largest lever in the design and costs less than one image on the page.

Sizing the fleet

Before dividing anything, name what kind of rate it is. Offered load is how much work arrives; service capacity is how much a machine can absorb. The 281,280/s reaching the network is a global offered load; regions divide it, never multiply it.

Capacity does not size this fleet. At an assumed 50,000 requests per second per saturated machine, run at 50% for headroom, the entire world needs only about a dozen machines. What sizes the fleet is footprint (gigabytes resident in RAM) and redundancy:

locale indexes a region must hold                        361 GB
one commodity box at the 128 GB default
boxes to hold one full copy   361 / 128  =  2.82  ->  3
copies per region (survive a loss during a rolling deploy)  3
machines per region           3 x 3      =  9
fleet                         9 x 6      =  54
replicas of any one locale    3 x 6      =  18
peak utilization              46,880 / (9 x 50,000)  =  10%

A rolling deploy upgrades machines a few at a time so the service stays up, which is why you need three copies and not two: during a deploy one is already out, and a second can still fail. The result is 54 machines, one locale image replicated 18 ways, running at 10% of serving capacity at peak. At a 256 GB box the same 361 GB needs 2 boxes a copy and the fleet is 36; the 18 replicas per locale do not move, because that is copies times regions.

The fleet is a placement and redundancy problem, not a capacity one. The trap is to size machines against the global rate and then also multiply by regions, counting them twice and landing on a fleet three times too large. Divide by regions or multiply by them, never both.

Deep dive 4: the client, where two-thirds of the work is deleted

The browser must do three things: wait before sending, refuse to draw a stale answer, and keep its connection warm. Each is worth more than any server-side optimization here.

Debounce, derived from typing speed

A debounce is the deliberate pause the client waits before sending, so it does not fire on every keystroke. At 40 words per minute (200 characters per minute) the mean gap between keystrokes is 300 ms. Model the gaps as an exponential distribution (the standard model for waiting times between independent events: short gaps common, long ones rare) with that 300 ms mean. A debounce of d fires only when no keystroke arrives within d ms, which happens with probability exp(-d/300).

Debounce is not a free traffic reduction: every millisecond of it comes out of the same 100 ms budget. So do not pick from the table, solve for it. The round trip, internal hop, paint, and retrieval come to 20 + 1 + 5 + 24 = 50 ms, leaving at most 50 ms for the debounce. Going to 200 ms trades away the product requirement to buy a saving the head blob already delivers for free. Two refinements: debounce trailing (fire after the pause, so the request describes the prefix the user stopped on), and do not debounce a paste or history-pick at all, since no further keystroke is coming.

The ordering bug

This is the defect the category ships most often. Requests for c, ca, and car are in flight together; the ca response arrives last; the client draws it, so the box shows completions for a prefix the input no longer contains.

Two things must line up: the user types the next character before the previous response returns (probability the gap is under 100 ms is 1 - exp(-100/300) ≈ 0.28), and the two responses cross on the wire (~0.02 from the client latency histogram). That is about 0.6% per keystroke. Applied to the 281,280 that actually reach the network (a response cannot arrive out of order if the head blob answered it locally), that is about 1,603 wrong renders per second at peak, yet effectively never reproducible on a developer’s machine. That combination is why the bug ships so reliably.

Three fixes, in increasing order of correctness:

1. AbortController on the previous request cancels an in-flight request, but the response may already be on the wire or in an HTTP cache, so it is best-effort.
2. A monotonic seq per keystroke, dropped if lower than the highest already drawn: correct, but needs the client to keep the high-water mark alive across retries and component rebuilds.
3. Render only if the response’s prefix equals the input’s current value. A single equality check, correct regardless of transport, retries, caches, or requests in flight, and it fails safely: a mismatch is dropped and the correct response is already on its way.

Ship 3, add 1 to save bandwidth, and treat 2 as a telemetry key.

Connection reuse

A cold connection does not exist yet and must be built: a TCP handshake plus a TLS handshake, each a full round trip. At a 20 ms regional round trip that is ~40 ms under TLS 1.3, or 40% of the whole budget, before any bytes are exchanged (60 ms under TLS 1.2). A warm connection is already open and carries a request immediately, which is what HTTP/2 buys by multiplexing many requests over one long-lived connection. Open the connection when the search box receives focus, not when the first keystroke lands. It is the cheapest 20-40 ms in the system and invisible in every server-side dashboard, which is why it goes unnoticed.

Bottlenecks and scaling

The peak load collapses in stages before it reaches the serving fleet:

flowchart LR
    K["Peak keystrokes<br/>960,000/s"] -->|"head blob answers 71%"| N["Reach the network<br/>281,280/s"]
    N -->|"6 regions divide load"| R["Per region<br/>46,880/s"]
    R --> F["Serving fleet<br/>54 machines, 10% utilized"]

Failure modes

Several of these look, from the outside, like nothing at all, which is exactly the problem. Each row pairs the trace an operator would see with the signal that makes an invisible failure visible.

The last row is the one people get wrong: a blocklist enforced only at build time cannot take effect faster than your slowest cache. Enforce it at render, in the process that talks to the client.

Alternatives rejected

Each discarded design gets what was good about it and the number that ruled it out.

A relational prefix query (WHERE q LIKE 'car%' ORDER BY count DESC LIMIT 10). Always fresh, trivially correct, no new system. Rejected on the budget: the index range scan must return every matching row before the sort picks ten, and for s that is 3.8 million rows against 24 ms and 2.4 disk seeks. The B-tree mechanics, and why a leading-wildcard LIKE '%car' cannot use an index at all, are in the database-internals chapter.

An SSD-backed key-value store keyed by prefix (the key-value store chapter). One random read per request, no rebuild pipeline, and it fits the budget at ~100 µs. Rejected not on device count: a real device does about 500,000 IOPS (input/output operations per second) serving many reads at once, so one device serves the whole world. It is rejected because you would pay for a storage round trip, a cache tier, and an eviction policy (the rule deciding what to discard when the cache fills) to hold 23 GB that already fits in RAM. The right question is not whether SSD is fast enough; it is whether the working set is small enough to make the question moot, and here it is.

Maintaining top-k online. No staleness, no pipeline, no distribution. Rejected at 800,000 node updates per second producing 16 million real changes a day (5,000:1 waste), 40,000 of those writes per second on the single root node every read also touches, and 14.4 million replication messages per second for a structure with no consistency requirement.

Traversing the subtree at read time. 16 GB cheaper, no cached list to invalidate. Rejected at 385 ms for a one-character prefix, 16x the budget, on the most common request. Kept as a hybrid: nodes with fewer than 10,000 descendants are traversed instead of cached.

Shipping the whole index to the client. Zero latency, zero server QPS. Rejected at 23 GB. The 100 KB head blob is the same idea applied to the 71% of traffic where it fits.

A plain character trie with no radix compression. Simpler build and code. Rejected at 1.5 billion nodes against 200 million (7.6x), on a structure whose viability rests on fitting in RAM.

Sharding by first character. Obvious routing, human-readable shard map. Rejected because the alphabet is not uniform: s at 8.1% against 3.85% uniform means every shard is provisioned for 2.1x the mean and the coldest is 40x under-used. The fix is a different key, locale, not a better hash.

Conclusion

Autocomplete is a read-only, precomputed, keyed lookup with a hard deadline, and a few facts cascade into the whole design:

• 24 ms of retrieval budget rules out databases, cross-region hops, and disk. The answer must be in memory, in region.
• No per-user personalization on the server makes the response a public, cacheable object, which is what lets a 100 KB head blob in the browser answer 71% of traffic and take peak from 960,000 to 281,280 QPS. That is the largest single lever.
• The 23 GB index fits on one box, so it is replicated, not sharded. When many locales force a split, the key is locale, because sharding by prefix reintroduces skew and hashing cannot fix a genuinely hot key.
• Precomputing top-k at every node turns a 385 ms ranked traversal into a 2 µs array read, at the cost of a write path that wastes 5,000:1. That is why the index is a build artifact rebuilt hourly, not a live structure, and why distribution (not computation) sets the freshness floor.
• A tiny streaming overlay carries freshness for the handful of terms that cannot wait an hour, without ever making the big structure writable.
• The client carries the design. Debounce, exact-prefix rendering, and warm connections each matter more than any server tweak, and the ordering bug is the one to guard against with a single equality check.

One line to remember: autocomplete is a cache-fill problem, so precompute the answer, keep it in memory in region, and delete or pre-answer as many requests as you can before they ever reach a server.

Further reading

• Cormode & Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications” (2005): the trending-detection structure.
• Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors” (1970): the blocklist filter.
• Morrison, “PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric” (1968): the radix-tree idea behind the index.
• The back-of-the-envelope chapter for the latency numbers this design subtracts from, and the consistent-hashing chapter for the variance result and the hot-key caveat.

Next: Design YouTube, the same read-heavy shape, with bytes instead of milliseconds as the binding constraint.