13 — Design A Search Autocomplete System

This chapter is about the drop-down list under a search box: how it gets built, and how it gets served.

By the end you will be able to:

• derive the time budget that every other decision falls out of,
• size the data structure that holds a hundred million queries,
• say why that structure is rebuilt on a schedule instead of kept up to date as searches arrive,
• explain why the obvious way of splitting it across machines makes things worse,
• name the client-side technique that removes most of the traffic.

Everything you need is derived here. The links go to extra depth; none of them is a prerequisite.

What goes in, and what comes out

The input is a prefix — the characters the user has typed so far, such as car — together with a locale like en-US.

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 response. No query is executed against a corpus of documents. Nothing about the answer depends on who is asking.

The two numbers that force the whole design

The first is the latency budget. “Feels instant” means under 100 ms from keypress to painted list.

Most of that 100 ms is already spoken for: the debounce (the deliberate pause the client waits before sending, so it does not fire on every keystroke), the network round trip, and the time the browser spends drawing. 3b the latency budget which is the design does the subtraction and lands on roughly 24 ms for actually retrieving the answer — enough time for about two disk seeks.

That one subtraction forbids a database query, forbids a hop to another region, and forbids any structure that is not already in the memory of a machine near the user.

The second is write amplification — the ratio between the work a system performs internally and the useful change that work produces.

Here is where write amplification comes from in this system. The classic structure for prefix lookup is a trie: a tree in which each edge is one character, so the path from the root spells out a prefix and everything beneath a node shares that prefix. To make a read a lookup rather than 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 the answer is what makes reads cheap. It is also what makes writes expensive: every incoming search has to update the stored list at every node along its path. Deep dive 2 why the index is rebuilt not updated prices that at 800,000 node updates per second to change roughly 16 million lists a day — 5,000 units of work for every one that changes anything a user could see.

That ratio is why the index is a build artifact shipped on a schedule rather than a live data structure.

Where candidates lose this question

Three places, in order of how often they happen:

• They quote “use a trie” without ever sizing the trie.
• They split the data by first letter as though the alphabet were uniform.
• They never mention the client at all, which is where more than two thirds of the traffic can be deleted outright.

Scope, and the technique used throughout

The estimation technique is the rounding discipline in Rounding discipline.

Ranking the suggestions themselves — understanding what a query means, personalizing it per user, correcting spelling — is a machine-learning problem and is not this chapter. The retrieval half of that problem lives in Retrieval architecture.

1. Framing: what decision, and what breaks

Autocomplete is a read-only, precomputed, keyed lookup with a hard deadline and no tolerance for a network hop it did not budget for. Take that phrase apart:

• Read-only, because users never write to it directly. They type; the writes come from the query log, later, offline.
• Precomputed, because the answers are built in advance rather than calculated per request.
• Keyed, because a prefix maps to exactly one stored answer.

Everything interesting comes from three properties that pull against each other, each with a cost.

One term in that table needs a definition. A locale is a language-and-region pairing such as en-US or ja-JP. It is the unit in which suggestions differ, because what people in Japan type is unrelated to what people in the United States type.

Say this early: “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 — and the interesting question is how the cache gets filled and how stale it is allowed to be.”

What actually breaks

Three things, in order of how often you will see them:

1. The browser renders the list for a prefix the user typed two characters ago, because responses came back out of order. The ordering bug derives how often.
2. The scheduled rebuild fails silently and nobody notices for a day, because stale suggestions look exactly like fresh ones.
3. A coordinated botnet promotes an abusive string into the top slot of a two-character prefix. A botnet is a fleet of machines under one operator’s control, imitating many separate users.

2. Requirements

With the framing in hand, pin down the contract — and, underneath it, which assumptions would force a different design if they broke and which would merely change the machine count.

Functional

The system owes its users the following:

• 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.

Three things are out of scope, and it is worth saying so out loud in an interview:

• personalization ranking,
• spelling correction,
• multi-language transliteration — suggestions typed in one script for a language written in another, such as Latin letters for Hindi.

Each is real work. None of them changes the storage or serving architecture, which is why they are cut.

Non-functional — these decide the design

These are the performance and correctness targets. Every row here is a constraint some later section spends. p99 means the 99th percentile: the number that 99 out of every 100 requests come in under, so it describes the slow tail rather than the typical case.

The consistency row is the licence for everything else, so spend a moment on it.

Consistency is the guarantee that different readers see the same data at the same time. Here it is not required. There is no read-your-writes promise (the promise that after you change something you will immediately see your own change), no transaction, and no ordering guarantee to preserve.

That 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. Say the consistency row out loud before you propose one, so the image reads as a consequence rather than a shortcut.

Assumptions, and which ones are load-bearing

Every derivation below rests on assumptions, and they are not all equal:

• A load-bearing assumption is one where being wrong gives you a different architecture.
• A soft assumption only changes how much hardware you buy.

Three terms show up in the table below before the sections that derive them, so take them now:

• A blob is one opaque file of bytes the browser downloads and keeps in memory for the session.
• Scatter-gather is the pattern where one request is fanned out to many shards and their answers combined. It makes a request as slow as the slowest shard it waited on.
• A hot key is a single key that is genuinely more popular than the rest. No hash can spread it, because one key lives on one shard however good the hash is.

All three are priced in Deep dive 3 sharding and why the obvious key skews.

The first row is the one to defend hardest. Every cheap thing in this design — the public edge cache, the 100 KB blob in the browser, the single precomputed list per node — exists only because the answer does not depend on who asked.

3. Back of the envelope

Four numbers drive everything that follows: how many requests per second arrive, how many milliseconds are left to answer one, how big the index is, and therefore whether it fits on one machine.

3a. Volume

Start with the request rate, which turns out to be far larger than the search traffic it decorates.

Two acronyms first. DAU is daily active users: the count of distinct people using the product on a given day. QPS is queries per second. The same 500 M DAU figure is used by Framing and the arithmetic that forces two stages, so the two chapters price the same product.

One convention needs stating before the arithmetic, because it appears in every division below. To turn a per-day count into a per-second rate, this chapter divides by 1e5 (100,000), not by the 86,400 seconds actually in a day. That is the drill convention of Rounding discipline: 100,000 is close enough to 86,400 to think with and far easier to divide by in your head. It is not free, and the size of the error is worked out below, under “What the 1e5 shortcut costs”.

The arithmetic chains four steps: keystrokes per day, mean QPS, peak QPS, and then two ratios that put the peak in context.

assume  500 M DAU, 8 searches/day, 8 keystrokes typed before a selection
        (users stop typing when the right suggestion appears, so the
         keystroke count is well below the 20-character mean query length)

suggest requests, if every keystroke fires one
  500,000,000 x 8 x 8                    =  32,000,000,000
mean QPS, at the 1e5 drill convention (ch 02 section 2)
  32,000,000,000 / 100,000               =  320,000
peak at 3x
  320,000 x 3                            =  960,000

the searches those keystrokes decorate, per day
  500,000,000 x 8                        =  4,000,000,000
at peak, same convention and same 3x
  4,000,000,000 / 100,000 x 3            =  120,000
suggest against the search it decorates
  960,000 / 120,000                      =  8
and, separately, against the URL shortener's peak read
rate of 30,000 (ch 08) -- a different product entirely
  960,000 / 30,000                       =  32

Autocomplete generates 8x the request rate of the search it decorates, for a result nobody asked for. That ratio is the reason the chapter exists.

Notice where the 8 comes from, though: it is not measured. It is the 8 keystrokes per search assumption read straight back out of the arithmetic — 8 suggest requests per search divided by 1 search. The only way to move it is to change that assumption.

The 32x is a different comparison, and it is worth keeping the two apart. It says a suggest tier at peak outruns a whole URL shortener’s read path by more than an order of magnitude. That is real and interesting, but it is measured against ch 08, a different product entirely — not against the search box this feature sits under. Quote whichever you mean and say which one it is.

Either way the conclusion holds: every design decision here is about deleting requests or making them absurdly cheap. A design that treats a suggest call like a search call is off by nearly an order of magnitude before it starts.

What the 1e5 shortcut costs

Now pay for the convention declared above, because it is load-bearing on every rate in the chapter.

Dividing by 100,000 instead of 86,400 understates every rate:

error introduced by the shortcut
  1 - 86,400 / 100,000                   =  0.136   (13.6% low)

so the rates carried forward are really
  32,000,000,000 / 86,400                =  370,370   (quoted as 320,000)
  80,000,000,000 / 86,400                =  925,926   (quoted as 800,000, section 8)
   4,000,000,000 / 86,400                =   46,296   (quoted as 40,000, section 8)

Ch 02 §2 is explicit about which number to use when: 1e5 is for thinking, 86,400 is for anything you report — a fleet size, a bill, a utilisation figure. Every figure carried forward below is therefore 13.6% flattering. Redo the division exactly at the moment one of them stops being an argument and becomes a purchase order.

The response is big enough to matter

Bytes matter almost as much as requests here, which is unusual, so price the response size too.

Egress is outbound traffic leaving the datacenter. A NIC is the network interface card: the port on a machine through which that traffic goes.

one suggestion: 30 B of text + 4 B of score
10 suggestions plus JSON framing              ~400 B

peak egress, bytes/s
  960,000 x 400                          =  384,000,000
in Gbps
  384,000,000 x 8 / 1,000,000,000        =  3.07

Two terms used precisely throughout this chapter are worth pinning down here, because mixing them up is how the fleet-sizing arithmetic in Deep dive 3 sharding and why the obvious key skews goes wrong:

• Offered load is how much work arrives.
• Service capacity is how much work a machine can absorb.

So 3.07 Gbps is peak offered load, worldwide. A 1 Gbps NIC is service capacity, per machine. Three Gbps over 1 Gbps per machine is three machines’ worth of NIC — call it four, since nobody runs a NIC at 100% — and that is an absolute floor, not a fleet.

Bandwidth is not the binding constraint here; request rate is. But it is close enough that the response format matters, which is unusual for a system this small per request.

3b. The latency budget, which is the design

The 100 ms target is mostly spoken for before retrieval gets a turn, and the subtraction rules out entire categories of design.

A PoP is a point of presence: a small cluster of machines the provider runs close to users, in the city rather than in a distant datacenter.

Start from the user’s 100 ms and deduct everything that is not retrieval; the last line is what retrieval gets.

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

Twenty-four milliseconds. A budget in milliseconds is hard to reason about, so convert it into the operations it can pay for, using the standard latency figures in Latency numbers and what each one forbids.

Three of those figures are used below:

• A memory reference is one read from RAM, about 100 nanoseconds (0.0001 ms).
• An SSD random read is one read from a solid-state disk at an arbitrary location, about 100 microseconds (0.1 ms).
• A disk seek is a spinning disk physically moving its head, about 10 ms.

Each line divides the 24 ms budget by one of those costs, in milliseconds, to get a count of operations:

memory references at 100 ns each
  24 / 0.0001                            =  240,000
SSD random reads at 100 us each
  24 / 0.1                               =  240
disk seeks at 10 ms each
  24 / 10                                =  2.4

Three conclusions, and each one kills a design a candidate might otherwise propose:

• A cross-continent round trip is 150 ms, six times the entire budget. The index is replicated into every region the users are in, full stop. This is also the first argument against maintaining it online: an online structure would have to replicate every update to every region.
• You get 2.4 disk seeks. A relational prefix scan is not slow here, it is arithmetically impossible.
• You get 240,000 memory references, which is enormous. In-memory anything is affordable; the design problem is what fits in memory, not whether memory is fast enough.

3c. How big is the thing that has to fit in memory

The last of the four numbers is the index itself, and the answer — that it fits on one machine — deletes the sharding section a reader expects.

Case-folding means treating upper and lower case as the same character, which is why the effective alphabet is 26 rather than 52.

Count the nodes in a plain character trie by depth, where depth means “number of characters typed”. At each depth, the number of nodes is capped by two different things at once:

• the alphabet: at depth d there are at most 26^d distinct character sequences,
• the data: there are only 100 M queries, so at any depth there are at most 100 M distinct prefixes.

Near the top the alphabet is the smaller cap. Further down the data is. The saturation depth is where they cross, and the first line of the block finds it by solving 26^d = 100,000,000 for d, which is d = ln(100,000,000) / ln(26). Everything above that depth is counted with 26^d; everything below it is counted with 100 M. Mean query length is 20 characters, so the tree is 20 levels deep.

assume  100 M distinct queries retained from a year of logs, mean 20 characters
        effective alphabet 26 after case-folding and punctuation stripping

depth at which distinct prefixes saturate at 100 M:
  ln 100,000,000 = 18.42 and ln 26 = 3.26, so
  18.42 / 3.26                           =  5.65

character-trie nodes above the saturation depth, sum of 26^d for d = 1..5
  26 + 676 + 17,576 + 456,976 + 11,881,376  =  12,356,630
nodes at depths 6..20, about 100 M distinct prefixes at each depth
  15 x 100,000,000                       =  1,500,000,000
total
  12,356,630 + 1,500,000,000             =  1,512,356,630

A plain character trie is 1.5 billion nodes, and almost all of them have exactly one child.

That last part is the opening. Below depth 6 the prefixes are already distinct, so a node down there almost always has exactly one child: it is a link in a chain, not a real branch point. Storing c -> a -> r -> r -> o -> t as six nodes when nothing ever branches off them wastes five nodes.

Collapse each chain into a single node — store the whole run of characters on one edge instead of one character per node — and you have a radix tree: a trie with the one-child chains squeezed out.

Counting a radix tree is much easier than counting a character trie, because only two kinds of node survive the squeeze. Every query contributes at most one branch point (the place where it diverges from its neighbours) and exactly one leaf (the query itself):

branching nodes, at most one per query                  100,000,000
leaves, one per query                                   100,000,000
radix nodes
  100,000,000 + 100,000,000              =  200,000,000
compression
  1,512,356,630 / 200,000,000            =  7.6

Now put bytes on those 200 million nodes. The block below has three tiers — the tree structure itself, the cached top-10 list at every node, and the query text — and the middle tier is the expensive one:

per radix node: 8 B child offset, 8 B edge-label offset,
                4 B subtree count, 4 B frequency             24 B
structure, GB
  200,000,000 x 24 / 1,000,000,000       =  4.8
cached top-10 at every node, 10 x (4 B id + 4 B score) = 80 B
  200,000,000 x 80 / 1,000,000,000       =  16
the query strings themselves, at 24 B each
  100,000,000 x 24 / 1,000,000,000       =  2.4
                                             ----
  4.8 + 16 + 2.4                         =  23.2

Twenty-three gigabytes, which fits in one commodity box. A commodity box is an ordinary rented server, which today carries 64-256 GB of memory. Numbers worth memorizing cold says to default to 128 GB and say so out loud, because silently taking one end of that range is how two chapters reach opposite fleet sizes. Twenty-three gigabytes fits at either end, so nothing here turns on the choice — but Deep dive 3 sharding and why the obvious key skews is where it does, and that is where the habit pays.

That one fact is the most important structural claim in the chapter, because it deletes a whole section people expect to write. Two words that get used interchangeably and should not be:

• Sharding means splitting one dataset across machines so each holds a different slice.
• Replication means giving several machines the same complete copy.

At this vocabulary size the index is not sharded, it is replicated. Sharding does show up later, and for an entirely different reason (Deep dive 3 sharding and why the obvious key skews).

4. API sketch

With the numbers fixed, the contract can be written down exactly — two endpoints, and three choices inside them doing real work. The first endpoint answers one prefix; the second hands the browser a thousand prefixes at once, which is the lever Replicating the head all the way into the browser prices.

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, not just accepted. It is the client’s keystroke counter. The client drops any response whose seq is below the highest it has already drawn. The ordering bug derives the bug this defends against: it fires on 0.6% of the keystrokes that actually reach the network, which at peak is 1,603 wrong lists drawn per second.

• Cache-Control: public, which is only legal because the response is not personalized. That header tells every cache between the server and the browser that this response may be stored and handed to other users, not just the one who asked. The same prefix and locale produce the same bytes for everyone, so the response is a public object an edge PoP can serve.

  Personalization still happens — it is just done on the device, by blending a locally kept history list into the rendered result. Keeping personalization on the client is exactly what keeps the server response cacheable. That is a deliberate trade, not an oversight.

• An empty list, never a 404. HTTP status 404 means “not found”. A prefix with no completions is a perfectly normal outcome, not an error. Returning 404 forces the client to tell “nothing matched” apart from “the service is broken” at exactly the moment it should be doing neither.

5. Data model: what is built, and what actually serves

The tree the offline pipeline builds is not the thing that serves. The build job produces a normal tree of objects — the top half of the listing below. What a serving process actually holds in memory is the bottom half, and the differences between the two are what make the index shippable. The cached top-10 that appears in both forms is the deep dive in Deep dive 1 the trie and why top k is cached at every node.

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

Four terms in that listing need unpacking:

• A pointer is a memory address. It is valid only inside the process that created it.
• An offset is a distance in bytes from the start of the array. It is valid anywhere, in any process, on any machine.
• mmap is the operating-system call that maps a file directly into a process’s address space, so the file can be read as if it were memory without being copied into the process first.
• The page cache is the region of memory the operating system uses to hold recently read file pages. It is shared by every process on the machine.

Using offsets rather than pointers is not a micro-optimization. It is what makes the artifact shippable.

A pointer-based tree cannot be copied to another machine and used, because the addresses mean nothing there; it has to be rebuilt from scratch on arrival. A flat array of offsets can be mmaped straight off disk and read as-is.

Two consequences follow. The page cache means every process on the box shares one copy, so the 23 GB is paid once per machine rather than once per process. And the swap to a new index is atomic — there is no moment at which a reader could see a half-installed index — because installing it is opening a new file and flipping a single reference.

Why a separate string table

The string table exists so that one entry in a cached top-10 list costs 8 bytes (a 4-byte id plus a 4-byte score) instead of about 30 bytes of text.

Storing the strings inline at every node would multiply the 16 GB top-k tier by roughly 4x — the tier that already dominates the index. Looking an id up in the table is a single array index, so the indirection costs nothing worth measuring.

One more term from the listing: a bloom filter is a compact probabilistic set. It answers “is this string in the blocklist?” using a few bits per entry rather than storing the strings. It can say definitely not or probably yes, and it never misses a real member. That is the safe direction of error for a blocklist: it may occasionally suppress an innocent suggestion, but it will never let a blocked one through.

6. High-level architecture

The whole design fits in one picture with two halves that meet in a single box. The top half is the read path, running downward from the browser. The bottom half is the build path: the query log feeding an hourly rebuild, plus a much faster streaming lane beside it. They meet at SVC, the suggest service, which is the only box both halves touch.

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<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

    style LOG fill:#1d3557,color:#fff
    style U fill:#2d6a4f,color:#fff
    style SVC fill:#2d6a4f,color:#fff
    style TREND fill:#bc6c25,color:#fff
    style DIST fill:#bc6c25,color:#fff

Reading the colours

The colours are ch 01’s published key, and they say something the box labels do not:

• Blue is the authoritative copy of the data. Here that is the query log and nothing else. Every other store in the picture is derived from it and could be rebuilt by replaying it.
• Green is read capacity. The browser’s head blob and the suggest service both answer reads without asking the authority. That is exactly what a 23 GB immutable image is.
• Orange is a box forced by something other than processor time. Both orange boxes are bound by bytes on a wire: the distribution fan-out pushing 23 GB to 18 replicas, and the trending pusher.
• The trie build is deliberately left uncoloured. It is the most processor-hungry box on the page, and the key has no colour for that. That absence is the point the key is making.

The read path, top to bottom

1. The browser debounces for 50 ms and tags each request with a seq counter.
2. It checks its own top-1,000 head blob, already in memory. Most keystrokes stop here and never leave the machine.
3. On a miss, the request goes to an edge PoP holding a public cache with a 5-minute TTL. TTL is time-to-live: the age at which a cached copy is discarded.
4. On a miss there, it reaches a suggest service process, which reads its 23 GB mmaped radix image plus the trending overlay and produces a candidate top 10.
5. Every candidate is checked against the blocklist bloom filter. Clean entries are returned. On a hit the service drops that entry, promotes the next one, and still returns ten results.

The build path, which never touches a live read

1. The query log collects roughly 4 billion events a day, one per search.
2. An hourly aggregation step counts occurrences, dedupes repeated searches by the same user so one person cannot vote twice, and filters blocked and low-quality strings.
3. The trie build turns that output into a radix tree with the top-k list cached at every node.
4. Distribution ships the finished image by tree fan-out to 18 replicas in about 15.3 minutes.

Beside all of that runs a second, much faster lane: a streaming detector reads the same query log continuously through a count-min sketch over a 30-second window and pushes 400 KB straight to the serving processes every 30 seconds. The exception terms that cannot wait an hour says what a count-min sketch is and prices the lane.

Four claims are embedded in that picture, and each has a section behind it:

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

Storing a precomputed answer at every node in the tree is the single largest memory decision in the design, so it has to be priced from both sides: what ranking costs without the cache, and what the cache costs in RAM. The bill the cache runs up on the write path is the whole of Deep dive 2 why the index is rebuilt not updated.

A trie gives you prefix matching: given car, it finds the subtree containing everything that starts with car. It does not give you ranked prefix matching, which is what a user needs — the ten most popular of those, not ten arbitrary ones — and the gap between those two operations is where the memory goes.

The cost of not caching

Start with the version that stores nothing extra, so ranking has to happen at read time. Answering the prefix s then means traversal: walking every node beneath it — every descendant — and keeping the ten highest counts seen.

So the cost of a read is the number of descendants times the cost of touching one node. The block below computes that for a one-character prefix, assuming for now that the 100 M queries split evenly across the 26 first letters (they do not, and Deep dive 3 sharding and why the obvious key skews shows the real distribution makes s worse, not better):

descendants under a 1-character prefix, uniform
  100,000,000 / 26                       =  3,846,154
at 100 ns per memory reference (ch 02) a machine does
1 / 100 ns = 10,000,000 of them per second, so the walk
takes, in seconds
  3,846,154 / 10,000,000                 =  0.385
0.385 s is 385 ms; against the 24 ms retrieval budget
  385 / 24                               =  16

Sixteen times over budget on the shortest, most common prefix in the system.

And 16x is generous, because the traversal has poor locality — the property that data used together sits close together in memory, which is what lets the processor’s cache do its job. Walking a radix tree is a chase from one address to an unrelated one, so 100 ns per node is an optimistic figure, not a conservative one.

Notice which direction the problem runs. Short prefixes are cheap to find and ruinous to rank. That is the opposite of most search intuitions, where a broad query is the cheap one.

The cost of caching

Now price the other version, in which the offline build stores the top ten at every node. A read becomes three steps: walk down one node per character, read the stored list, return it.

The walk is the only part that costs anything, and it is bounded by the length of the prefix rather than by the size of the subtree — at most 20 nodes for a 20-character query, against 3.8 million:

hops for a 20-character prefix, in seconds at 100 ns each
  20 / 10,000,000                        =  0.000002
ratio to the traversal
  0.385 / 0.000002                       =  192,500

Five orders of magnitude, bought with the 16 GB derived in 3c how big is the thing that has to fit in memory. That is the trade in one line, and it is the sentence to say out loud: “I am spending 16 GB of RAM to turn a 385 ms subtree scan into a 2-microsecond array read, and I can afford it because the whole index is 23 GB and a box holds 128.”

Two refinements are worth having ready.

Refinement 1: you do not have to cache at every node

A node whose subtree is small is cheap enough to traverse at read time, so the cached list is only worth its bytes higher up the tree.

Set the threshold from the budget rather than by taste. At 100 ns per node, one millisecond of traversal buys 10,000 node visits. So cache the top-k list only at nodes with more than 10,000 descendants, and traverse everything below that.

Then count how many nodes actually clear that threshold, rather than eyeballing it, because the eyeball answer is off by orders of magnitude. The block does it twice: once under the uniform 26-ary model, and once with a bound that does not depend on any model at all.

descendants of a node at depth d, uniform 26-ary over 1e8 queries
  depth 1   100,000,000 / 26           =  3,846,154
  depth 2   100,000,000 / 26^2         =    147,929
  depth 3   100,000,000 / 26^3         =      5,690
so the threshold cuts BELOW depth 3, not above it: depths 1 and 2
qualify and depth 3 does not
  26 + 676                             =        702  nodes
the bound that does not depend on the uniform model: at most
1e8 / 10,000 nodes at any one depth can have 10,000 descendants,
over 20 depths
  10,000 x 20                          =    200,000  nodes
against the full radix tree
  200,000,000 / 200,000                =      1,000

The model-free bound in the middle is worth understanding, because it is the one that survives contact with a real distribution. If a node has 10,000 descendants and there are only 100 M queries in total, then at any single depth at most 1e8 / 10,000 = 10,000 nodes can clear the threshold — the descendants have to come from somewhere. Twenty depths gives 200,000 nodes, out of 200 million.

So: 702 nodes under the uniform model, at most 200,000 without it, against a full tree of 200 million.

Quote the saving as 100x, not 1,000x. A real query trie is far denser near the threshold than a uniform 26-ary tree, which badly understates node counts near the top. 100x survives a real distribution; 1,000x does not.

What the uniform model does get right is the direction: depth 3 falls below the threshold, so “cache depth 3 and above” is the wrong half of the tree.

Take selective caching when memory is tight. Take full caching when it is not, because full caching removes a whole class of surprises in the slow tail of the latency distribution.

Refinement 2: store a subtree count at every node

The subtree count is what makes that threshold checkable at read time — the serving process can tell whether a node is above or below the line without walking anything. It is also what lets the build decide, node by node, whether writing a cached list is worth the space.

The update cost this buys, which is the whole of the next section

The cache is not free in a second currency, and this is where the bill arrives. Caching top-k at every node means one new query event can invalidate the stored list at every one of its 20 ancestors — every node on the path from the root down to that query. The read got 192,500x faster; the write got 20x more expensive and, worse, became a read-modify-write — fetch the list, adjust it, write it back — on exactly the nodes that every read in the system also touches. Deep dive 2 why the index is rebuilt not updated prices that trade.

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

An immutable artifact rebuilt on a schedule sounds like a compromise. Priced against the live-update path — total writes, where those writes land, and what replicating them costs — it is a rout, and the real bound on freshness turns out to be distribution rather than computation. The one class of term that cannot wait gets its own carve-out at the end.

The write amplification, derived

Start by counting how much work a live-update design would do. One search event has to bump the counter at its own node and refresh the cached list at every node above it, so the multiplier is the depth of the tree — one ancestor per character.

search events/day
  500,000,000 x 8                        =  4,000,000,000
ancestor nodes per event, one per character            20
node updates/day, maintained online
  4,000,000,000 x 20                     =  80,000,000,000
per second
  80,000,000,000 / 100,000               =  800,000

Eight hundred thousand writes a second is a large number, but volume alone is not an argument. The question is how many of those writes change anything a user could see. A node’s cached top-10 only moves when some query’s count crosses the count of whatever currently sits in tenth place — every other increment leaves the rendered list byte-for-byte identical.

The block below establishes the scale of that gap two ways: a sanity estimate at the root, then a measured figure over a week of logs.

at the root, the 10th-ranked query holds about 1e-4 of traffic, so
displacing it takes, in a day,
  4,000,000,000 x 0.0001                 =  400,000
increments. Measured over a week of logs, 0.02% of ancestor touches
actually reorder a cached list:
  80,000,000,000 x 0.0002                =  16,000,000
wasted-work ratio
  80,000,000,000 / 16,000,000            =  5,000

Five thousand to one. That is the number to put on the whiteboard.

Where those writes land is worse than how many there are

The ratio is only half the argument. The other half is placement.

root-node updates per second, since every event touches the root
  4,000,000,000 / 100,000                =  40,000
reads of that same node per second at peak                960,000

Forty thousand serialized writes per second against 960,000 reads, on one node, forever.

Serialized means the writes have to happen strictly one after another, because two of them editing the same list at once would corrupt it. A lock is the usual mechanism for enforcing that — and a lock on the root node is effectively a global lock, since every single request passes through the root.

Removing the lock does not remove the problem. A lock-free structure puts one cache line — the 64-byte unit processors exchange between cores — under contention from every core in the fleet. You have moved the queue from software to hardware.

And the writes do not stay in one datacenter

There is a third bill, and it arrives on the network. Every one of those 800,000 updates a second has to reach every replica holding that locale’s index, so the block below multiplies the write rate by the replica count derived in Sizing the fleet.

replicas of one locale's index (section 9)
  3 x 6                                  =  18
node-update messages per second, fanned out
  800,000 x 18                           =  14,400,000

That is 14.4 million messages per second of replication traffic, spent keeping consistent a structure that nobody requires to be consistent.

Go back to the requirements table: consistency is not required. An online update path spends its entire budget buying a property the product explicitly does not want.

The batch alternative, priced

Against that, price doing the whole day’s ranking work offline, in one pass over the logs. The chain is: how big is the log, how long does one machine take to read it, how much more than reading does the build cost, and how does that divide across a cluster.

raw search log at 40 B/event, GB/day
  4,000,000,000 x 40 / 1,000,000,000     =  160
one machine's sequential read of that at 1 GB/s (ch 02), in seconds
  160 / 1                                =  160
aggregate, sort, and build, roughly 10x the scan, in machine-seconds
  160 x 10                               =  1,600
on 50 machines, wall clock in seconds
  1,600 / 50                             =  32

Thirty-two seconds of arithmetic. Real builds land in the tens of minutes, because they are shuffle-bound: the slow part of a distributed aggregation is not the counting, it is the network step that moves every record to whichever machine owns its key. The point survives the correction.

The entire day’s ranking work is 1,600 machine-seconds, against a write path that does 5,000 units of work for every one that changes anything a user could see.

State the comparison in exactly that shape, because it is the one that reproduces. Nothing in this chapter prices a single node update in seconds or in dollars. So any sentence that converts 800,000 writes per second into machine-time and sets it against the 1,600 is asserting a conversion factor it never states, and an interviewer who asks for that factor will get silence. Compare a bounded, measured batch cost against a measured waste ratio, and leave it there.

Distribution is the real cost, and it sets the freshness floor

Building the index turns out to be the cheap part. Copying it to every machine that serves it is what actually bounds how fresh the suggestions can be.

Price the naive version first: one origin machine pushing the finished image to every replica, one after another, over its own 1 Gbps link. Note the x 8 in the line that produces seconds: it converts gigabytes to gigabits, because network links are rated in bits and storage in bytes.

serialized image, one locale, GB                         23
replicas of that image (section 9)
  3 x 6                                  =  18
bytes shipped if one origin pushes to all, GB
  23 x 18                                =  414
seconds at 1 Gbps out of that origin (ch 02)
  414 x 8 / 1                            =  3,312
minutes
  3,312 / 60                             =  55

Fifty-five minutes, which eats the whole hourly cadence before the build has even run.

Double-check the replica count when you quote this, because getting it wrong changes the character of the answer rather than just its size. At the correct 18 replicas derived in Deep dive 3 sharding and why the obvious key skews, a single-origin push is a budget with nothing left in it. At an incorrect 120 replicas the same arithmetic gives 23 x 120 x 8 = 22,080 seconds, or 6.1 hours, which reads as a flat impossibility instead. The conclusion is the same either way, but only one of the two numbers is real.

Fan out as a tree instead

The fix is to stop pushing from one origin. Fan out as a tree: on each hop, every machine that already holds the image seeds exactly one more machine, so the population of holders doubles.

Say one, not two. A holder seeding two more triples the population every hop, which is a different tree with a different hop count. “Each seeds two, so it doubles” is the slip that produces a number nobody can reproduce.

The cost is then one image transfer per hop, times the number of hops needed to reach every replica:

one hop, in seconds
  23 x 8 / 1                             =  184
hops to cover 18 machines: 2^4 = 16 < 18 <= 32 = 2^5, and
log2 18 = 4.17 is not a hop count because you cannot perform
0.17 of a hop, so round UP
  ceil(4.17)                             =  5
wall clock, seconds
  184 x 5                                =  920
minutes
  920 / 60                               =  15.3

Fifteen minutes instead of fifty-five, for the same bytes over the same links, because 18 machines are uploading instead of one.

Build plus distribution is 32 s + 15.3 min before shuffle overhead — tens of minutes, so an hourly cadence is the natural floor, and average staleness is about 30 minutes. Staleness is how old the answer a user sees is. It averages half the rebuild interval because a request is equally likely to arrive anywhere inside it.

State the hour as a derived number, not a policy. Nobody chose hourly; the 23 GB image and the 1 Gbps NIC chose it.

That also tells you which lever to pull if the product demands 10-minute freshness: image size, not scheduler configuration. Delta shipping is how you pull it — send only the nodes whose top-k list actually moved, measured above at 16 million a day, instead of the whole image.

The exception: terms that cannot wait an hour

One class of term breaks the hourly cadence, and it can be handled with a rounding error’s worth of extra machinery. An hour is fine for carrot cake and useless for a name that did not exist at breakfast.

The failure is asymmetric, which is what makes it worth special machinery. A trending term is precisely the one every user is typing at that moment, so an hour of blindness is an hour in which the highest-value suggestions are the ones missing.

The fix is a small side-channel: a table of the hottest few thousand prefixes, pushed far more often than the image. Price it, and notice how small it is against the 23 GB it rides alongside:

trending overlay: 5,000 hot prefixes x 10 suggestions x 8 B
  5,000 x 10 x 8                         =  400,000
as a fraction of the 23 GB image
  400,000 / 23,000,000,000               =  0.0000174
pushed to 18 replicas every 30 s, bytes per push
  400,000 x 18                           =  7,200,000
averaged over the 30 s window, in Mbps
  7,200,000 x 8 / 30 / 1,000,000         =  1.92

The overlay is 0.0017% of the image and 1.92 Mbps of push traffic, and it buys the entire freshness story.

Three parts make it work:

• Detection uses a count-min sketch over the query stream. That is a small fixed-size table of counters, hashed into several times per item, which estimates how often each item has been seen using a few kilobytes instead of one counter per distinct term. The price is that it occasionally overestimates, never underestimates.
• The trigger rule flags any term whose 5-minute rate exceeds a multiple of its trailing 24-hour rate — a term rising sharply against its own baseline, not just a popular term. It is subject to a floor on how many distinct users searched it, so one enthusiastic script cannot fire it.
• Merging happens at read time: the service overlays the fresh list on top of the baked-in list for the same prefix.

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

9. Deep dive 3: sharding, and why the obvious key skews

One machine stops being enough the moment more locales or a bigger vocabulary arrive, and the question becomes how to split. The obvious key fails, hashing improves matters without fixing them, and the right key turns out to be locale — after which the fleet is sized by something other than traffic entirely.

What forces the question at all

3c how big is the thing that has to fit in memory established that 23 GB fits on one box, so a single English index does not need sharding at all. Two things change that: supporting more locales, and retaining a bigger vocabulary.

Take the locales first. Non-English locales are smaller than English — fewer retained queries — so the block below prices one at 30% of the English vocabulary and then adds them all up:

locales                                                 50
index per non-English locale, at ~30% of the English vocabulary, GB
  23 x 0.3                               =  6.9
all locales resident on one machine: English at full size plus
the other 49 at 30%, GB
  23 + 6.9 x 49                          =  361

361 GB — one English index at 23 GB plus 49 others at 6.9 GB each.

It is not 6.9 x 50 = 345. That version multiplies the non-English per-locale size by all fifty locales, which prices English at 6.9 GB when the chapter just spent a whole subsection deriving it at 23.

The conclusion survives the correction, which is why it is worth doing rather than fudging: 361 / 256 still rounds up to 2 boxes at the very top of the commodity range, and against the 128 GB default of Numbers worth memorizing cold it is nearly three. Either way, something has to split.

Why sharding by first character fails

The instinct is to shard by first character: everything starting with a on one machine, b on the next, 26 machines. Routing is trivial and the shard map is human-readable.

It is wrong, and one table of real traffic is enough to show why. The block lists the measured share of English searches by first letter, top and bottom, then compares the hottest against a uniform split and against the coldest:

share of English search traffic by first character, one month of logs
  s                                      =  0.081
  c                                      =  0.072
  a                                      =  0.066
  ...
  x                                      =  0.004
  z                                      =  0.002
a uniform share would be
  1 / 26                                 =  0.0385
hottest shard against the mean
  0.081 / 0.0385                         =  2.10
hottest against the coldest
  0.081 / 0.002                          =  40.5

s is 8.1% of traffic, not 3.85%, so the hottest shard runs at 2.1x the mean and 40x the coldest.

Skew is that unevenness: the gap between what a uniform split would give and what the real distribution gives.

The cost of skew is that you must provision every shard for the hottest one. Every one of the 26 shards has to be built for 2.1x the mean load, so you are buying 26 x 2.1 = 55 shards’ worth of capacity to serve 26 shards’ worth of traffic. And the skew is not even stable: it moves with language, with locale, and with whatever is in the news.

Hashing helps, and then stops helping

The standard fix is to stop routing on a semantic key — one whose value means something to a human — and route on a hash instead: a function that scrambles the key into a number with no relation to its spelling, so adjacent keys land on unrelated shards. Hash the first three characters and you get 17,576 routing buckets rather than 26, which you then spread across the shards you have. That is exactly the virtual-node argument from Virtual nodes buy variance not mean.

To compare evenness you need one number for it. The coefficient of variation (CV) is the standard deviation divided by the mean: a unitless measure of how uneven the load is, where 0 is perfectly even and 1 means the spread is as large as the average itself. For n independent buckets landing in a shard, the CV of the shard’s load is about 1 / sqrt(n), so more buckets per shard means more evenness.

The block does three things: computes the CV at 100 shards, redoes it at 26 shards so it is comparable to the letter-sharding it replaces, and then puts a hard ceiling on the CV of the thing being replaced.

3-character routing buckets
  26 x 26 x 26                           =  17,576
buckets per shard at 100 shards
  17,576 / 100                           =  176
coefficient of variation of load, 1 / sqrt(buckets per shard)
  1 / 176^0.5                            =  0.0754

like-for-like: the thing being replaced is 26 letter-shards, so
put the same hash on 26 shards
  17,576 / 26                            =  676
  1 / 676^0.5                            =  0.0385

and bound the figure being replaced before quoting it. A share
bounded in [0.002, 0.081] with mean 1/26 = 0.0385 has
  Var <= (b - m)(m - a)
       = (0.081 - 0.0385) x (0.0385 - 0.002)  =  0.001551
  sd  <= 0.001551^0.5                         =  0.0394
  CV  <= 0.0394 / 0.0385                      =  1.02

CV 0.039 with hashing, against roughly 0.7 with letters — at the same shard count. Both figures are unitless ratios, so read 0.039 as 3.9% and 0.7 as 70%.

Two disciplines are buried in that comparison, and both are the kind of thing an interviewer probes.

First, compare like with like. The 0.0754 in the first part of the block is the CV at 100 shards. The first-character skew is a fact about 26 shards. Setting one against the other compares two different fleets, and the difference in shard count is doing part of the work. Redo the hash at 26 shards — 676 buckets each instead of 176 — and hashing gives CV 0.0385.

Second, sanity-check the number you are improving on. It is tempting to quote the letter-shard CV as something dramatic like 1.1, but that number is not reachable here. The variance bound at the end of the block caps the CV at 1.02, and that ceiling assumes every single letter sits at one of the two extremes — which the chapter’s own intermediate values rule out, since c is 0.072 and a is 0.066, both nowhere near 0.002 or 0.081.

That bound is worth reading closely, because the technique generalises. For any quantity known to lie in [a, b] with mean m, the variance is at most (b - m)(m - a). Substituting the measured extremes 0.002 and 0.081 and the mean 1/26 gives a standard deviation of at most 0.0394, and dividing by the mean gives a CV of at most 1.02.

Interpolate monotonically between the endpoints this section measured, normalise, and a realistic English first-character distribution lands around 0.7. Hashing therefore takes CV from about 0.7 to 0.0385, an 18x improvement. The argument for hashing is unchanged — it just has to be made with a number that exists.

Hashing does not fix a hot key

Hashing fixes variance: the random lumpiness you get when you scatter many independent buckets across shards. It does nothing about the hot key defined back in Assumptions and which ones are load bearing, because one key hashes to exactly one shard however good the hash is. What consistent hashing does not fix says so explicitly.

To find out how hot the hottest key is, you need a model of query popularity. Use Zipf with exponent s = 1, the standard empirical fit for word and query frequencies: the nth most popular item gets traffic proportional to 1/n. To turn those proportions into shares you divide by their total, the harmonic number H(K) = 1 + 1/2 + ... + 1/K, which is well approximated by ln K + 0.577. So the top item’s share is 1 / H(K).

The block below fits that model twice. The first fit is the obvious one and it produces an impossible answer; the middle of the block is the check that catches it; the refit at the end is the one to quote.

naive fit -- Zipf s = 1 over all 17,576 buckets: the top bucket holds
1 / H(17,576), and with ln 17,576 = 9.77 the harmonic number is
about 9.77 + 0.577 = 10.35
  1 / 10.35                              =  0.0966

CONTAINMENT CHECK, and it fails: every query whose 3-character prefix
is `sea` also has the 1-character prefix `s`, so
  share(3 chars) <= share(1 char) <= max over letters  =  0.081
  0.0966 > 0.081                         ->  impossible

refit inside the hottest first character instead -- 676 three-character
buckets under `s`, holding `s`'s measured 8.1% between them
  ln 676 = 6.52, so H(676) = 6.52 + 0.577  =  7.09
  0.081 / 7.09                             =  0.0114

and the shard that holds it, at 100 shards, carries its 175 neighbours too
  (1 - 0.0114) / 17,575 x 175            =  0.0098
  0.0114 + 0.0098                        =  0.0213
against a uniform 1 / 100 = 0.01
  0.0213 / 0.01                          =  2.13

The hottest three-character bucket is about 1.1% of traffic.

The check that catches the wrong answer is containment. Every query whose three-character prefix is sea also has the one-character prefix s, so a three-character bucket can never be hotter than the letter it starts with. The hottest letter in this chapter’s own measured table is s at 8.1%. A fit that returns 9.7% for a three-character bucket is therefore asserting that some letter exceeds 9.7%, which contradicts the very measurement it is being compared against.

Run that check on any Zipf fit before you quote it. Fitting 1/n across a space whose head is already bounded by a measurement is the standard way to produce a number larger than the thing containing it.

Fixing the fit does not rescue prefix sharding

It only relocates the argument.

Hashing genuinely helps: 1.1% against s’s 8.1% is a 7x reduction in the hottest key. But it does not fix the hot key, because a genuinely popular prefix is one key, and one key lives on one shard. Work out what that shard carries — its own hot bucket plus its 175 ordinary neighbours — and the last lines of the block give 2.13x the mean.

That is precisely where sharding by first character already was. The skew came back through a different door.

Shard by locale instead

So do not shard by prefix at all. Shard by locale, and replicate each locale’s whole index. Three reasons it is the right key:

• Each index is 7-23 GB, comfortably inside one box, so a lookup is always local. There is no scatter-gather, and therefore no tail-latency amplification — the name for the cost Assumptions and which ones are load bearing attached to scatter-gather, where a request that waits on ten shards is as slow as the slowest of the ten.
• Load per locale is known in advance and is stable, and replicas are placed where that locale’s users are, which satisfies the regional-latency requirement from 3b the latency budget which is the design for free.
• The hot-prefix problem dissolves into replication: a prefix that is 1.1% of one locale’s traffic, or a first character that is 8.1% of it, is served by every one of that locale’s replicas rather than by one machine.

Replicating the head all the way into the browser

The most popular prefixes — the head of the distribution, as opposed to its long tail of rare ones — can be replicated one level further out than any server: into the browser itself.

The Zipf model earns its keep here. If the nth prefix gets traffic proportional to 1/n, then the share covered by the top m of K buckets is ln(m) / ln(K). Substituting m = 1,000 and K = 17,576 says a thousand prefixes cover 70.7% of all requests. The rest of the block prices those thousand prefixes as a download and then applies the coverage to peak QPS:

Zipf s = 1: the top m of K buckets cover ln(m) / ln(K), so for the top 1,000,
with ln 1,000 = 6.91 and ln 17,576 = 9.77,
  6.91 / 9.77                            =  0.707
payload for those 1,000 prefixes, 10 suggestions x 30 B
  1,000 x 10 x 30                        =  300,000
gzipped, roughly 3x on short repetitive text
  300,000 / 3                            =  100,000
peak QPS that still reaches the network
  960,000 x 0.293                        =  281,280

The last line multiplies peak QPS by 1 - 0.707 = 0.293, the share of requests the blob does not cover.

A 100 KB blob fetched once per session answers 71% of suggest requests with zero network latency, and takes peak QPS from 960,000 to 281,280.

It is the single largest lever in the chapter. It costs less than one image on the page. And it changes the character of the latency target: sub-100 ms becomes trivially achievable for the majority of keystrokes, rather than marginally achievable for all of them.

Sizing the fleet

The remaining fleet is small, and sizing it is the single easiest thing to get wrong in this chapter. The guard against that is to say what kind of rate each number is before dividing anything by anything:

• 281,280/s is offered load, and it is a global rate. The 960,000 it comes from was built in 3a volume out of 500 M daily active users worldwide, and the head blob deletes the same 70.7% of it in every region.
• 50,000/s is service capacity: one machine running flat out. That figure is assumed, not derived — nothing above prices a suggest request in CPU — and the conclusion below does not turn on it, because the fleet ends up at 10% of whatever it is.

Regions divide offered load. They never multiply it. The block below does exactly that division, and stops at a number that turns out not to be the answer:

peak offered load reaching the network, WORLDWIDE        281,280
service capacity of one machine, saturated                50,000
utilization we design to, so a lost peer is absorbed          0.5
usable capacity per machine
  50,000 x 0.5                           =  25,000
machines of capacity for the entire world, at peak
  281,280 / 25,000                       =  11.3
regions, each serving its own users                             6
offered load per region
  281,280 / 6                            =  46,880
machines per region that capacity alone would buy
  46,880 / 25,000                        =  1.9

Two machines per region, twelve worldwide — so capacity is not what sizes this fleet.

What sizes it instead is footprint: how many gigabytes have to be resident in RAM, together with the minimum number of copies availability demands. Those two constraints have nothing to do with QPS.

One term for the block: a rolling deploy is the practice of upgrading machines a few at a time so the service stays up. It is why you need three copies and not two — during a deploy one copy is already out of service, and a second one can still fail while it is.

locale indexes a region must hold, GB                         361
one commodity box at ch 02 section 6's stated DEFAULT, GB      128
boxes to hold one full copy
  361 / 128                              =  2.82   ->  3
copies per region, to 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's index
  3 x 6                                  =  18
peak utilization of a region's serving capacity
  46,880 / (9 x 50,000)                  =  0.10

Fifty-four machines, one locale image replicated 18 ways, and the tier running at 10% of its serving capacity at peak.

Say the box size out loud, because this is the row where it bites. Numbers worth memorizing cold gives commodity memory as a 64-256 GB range and then tells you to default to 128 GB and declare it, precisely because “silently taking an end of a range is how two chapters reach opposite fleet sizes.”

Here it does exactly that. At 128 GB a copy needs 3 boxes and the fleet is 54. At the 256 GB top of the range the same 361 GB needs 361 / 256 = 1.41 -> 2 boxes a copy, and the fleet is 2 x 3 x 6 = 36. That is a 1.5x difference produced by nothing but an unstated choice. Fifty-four is the default answer; 36 is available to you if you say “256 GB box” first.

What does not move with box size is the 18 replicas of any one locale, because that is copies times regions.

The second error, which is worse

There is another mistake here, unrelated to box size, that turns this fleet into 120 machines.

It goes like this: size 20 machines per region against the global 281,280, then multiply by six regions and a redundancy factor. The regions have now been counted twice — once inside the load figure, which was already worldwide, and once outside it.

Divide by regions or multiply by them, never both.

The fleet is a placement and redundancy problem, not a capacity one, and the two blocks above are what establish that rather than merely asserting it.

10. 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 in the chapter, and each is routinely left out of a whiteboard answer.

Debounce, derived from typing speed

The debounce is what turns a fast typist’s eight keystrokes into fewer than eight requests. Its length is derived, not chosen, and the derivation starts with typing speed:

40 words per minute x 5 characters per word, chars/min
  40 x 5                                 =  200
milliseconds between keystrokes
  60,000 / 200                           =  300

Model the gaps between keystrokes as an exponential distribution with that 300 ms mean. That is the standard model for waiting times between independent events: short gaps are common, long ones rare.

A debounce of d fires only when no further keystroke arrives within d milliseconds. Under the exponential model the probability of that is exp(-d/300), so that expression is the fraction of keystrokes that survive to become requests. At d = 50, exp(-50/300) = exp(-0.167) = 0.846, so 84.6% of keystrokes still fire and 15% are removed — the bold row below.

The table is a trade: requests removed are what you win, and the added latency is paid out of the same 100 ms the user is watching.

Debounce is not a free traffic reduction. Every millisecond of it is a millisecond taken off the same 100 ms the network and the service are spending.

So do not choose d from the table; solve for it. From the budget in 3b the latency budget which is the design, the round trip, the internal hop, the paint and the retrieval come to 20 + 1 + 5 + 24 = 50 ms. The perceived target is 100 ms. That leaves at most 50 ms for the debounce, and that is where the 50 in the budget table came from — the two numbers are the same subtraction read in opposite directions.

Anyone quoting 200 or 300 ms has traded away the product requirement to buy a 49% traffic saving that the client-side head blob delivers better anyway, and for free.

Two adjustments are worth stating:

• Debounce trailing, not leading — fire after the pause rather than on the first keystroke — so the request describes the prefix the user actually stopped on.
• Do not debounce a paste or a pick-from-history event at all. Neither is typing, and no further keystroke is coming, so waiting buys nothing and costs 50 ms.

The ordering bug

This is the defect the category ships most often, and it is worth being able to derive its rate rather than merely name it.

Three keystrokes produce three requests in flight at once, for c, ca and car. The response for ca happens to arrive after the response for car. The client draws it, because it is the most recent thing to arrive. The box now shows completions for a prefix the input no longer contains.

Two things have to line up for that to happen: the user has to type the next character before the previous response comes back, and the two responses have to cross on the wire. The block multiplies those two probabilities and then applies the result to the traffic that actually reaches the network:

p(the gap to the next keystroke is under 100 ms)
  1 - exp(-100/300)                      =  0.283
p(consecutive responses differ in latency by more than that gap),
from the client-side latency histogram                    0.02
p(an out-of-order render per keystroke)
  0.283 x 0.02                           =  0.0057
keystrokes that actually reach the network at peak, after the
head blob deletes 70.7% of them (section 9)               281,280
wrong lists rendered per second at peak
  281,280 x 0.0057                       =  1,603

Half a percent per keystroke, which is 1,603 wrong renders a second and effectively never reproducible on a developer’s machine.

Take the rate off the post-blob figure of 281,280, not off the naive 960,000. A response cannot arrive out of order if it never left the machine, and 70.7% of keystrokes are answered from the browser’s own head blob: no request, no response, no reordering. Applying the 0.57% to 960,000 gives 5,472 and counts renders in which no network was involved at all.

That combination — rare enough to survive code review, common enough to be constant in the field — is why this bug ships so reliably.

Three fixes, in increasing order of correctness:

1. AbortController on the previous request — the browser interface that cancels an in-flight request. It helps, but the response may already be on the wire or about to be served from an HTTP cache, so aborting is best-effort.
2. A monotonic seq per keystroke, dropped if lower than the highest already drawn. Monotonic means it only ever increases. This is correct against reordering, but it requires the client to keep that high-water mark alive across retries and across the interface component being torn down and rebuilt.
3. Render only if the response’s prefix equals the input’s current value. This is the one to say out loud. It is a single equality check, it is correct regardless of transport, retries, caches, or how many requests are in flight, and it fails safely: a mismatched response is simply dropped, and the correct one is already on its way.

Ship 3, add 1 to save bandwidth, and treat 2 as a telemetry key — something to measure the bug with — rather than as the control that prevents it.

Connection reuse

The last client-side item is the cheapest and the least visible: making sure the connection already exists by the time the first request needs it.

The block prices three cases against the same 20 ms regional round trip — a cold connection under TLS 1.3, the same under TLS 1.2, and a connection that is already open — and then compares the cheapest cold case to the whole budget:

cold TCP + TLS 1.3 at a 20 ms regional RTT: 1 RTT TCP + 1 RTT TLS
  2 x 20                                 =  40
TLS 1.2 adds another round trip
  3 x 20                                 =  60
warm HTTP/2 stream on an existing connection
  1 x 20                                 =  20
share of the 100 ms budget eaten by a cold handshake
  40 / 100                               =  0.40

A cold connection is one that does not exist yet and must be built from scratch: a TCP handshake to open it, then a TLS (Transport Layer Security) handshake to encrypt it, each costing a full round trip. A warm connection is already open and can carry a request immediately, which is what HTTP/2 buys — it multiplexes many requests over a single long-lived connection instead of opening one per request.

A cold handshake is 40% of the budget before any bytes are exchanged.

So open the connection when the search box receives focus, not when the first keystroke lands, and keep it warm for the rest of the session. This is the cheapest 20-40 ms in the system.

It is also invisible in every server-side latency dashboard — the server never sees the handshake it did not have to do — which is exactly why it goes unnoticed.

11. Bottlenecks and scaling

Every limit derived above lands in one table, each with its number and the design decision it forced. Nothing here is new — the table is the chapter’s argument in miniature.

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"]

The two levers that actually move the numbers are both on the client, and both are usually missing from a whiteboard answer. Say the client-side head blob before you say anything about the trie, because it deletes 71% of the problem and it is the part an interviewer can tell you have not memorized.

12. Failure modes

The system breaks in eight ways, and several of them look, from the outside, like nothing at all — which is exactly the problem. That is why each row pairs the trace an operator would actually 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.

13. Alternatives rejected

An alternative you cannot argue against with a number is one you have not actually rejected. So each discarded design below gets two things: what was genuinely good about it, and the number that ruled it out.

A relational prefix query, WHERE q LIKE 'car%' ORDER BY count DESC LIMIT 10. Good: no new system, always fresh, trivially correct. Rejected on the budget. The database’s index range scan has to return every matching row before the sort can pick the top ten, and for s that is 3.8 million rows against a 24 ms allowance and 2.4 disk seeks. The B-tree mechanics behind that, and why a leading-wildcard variant such as LIKE '%car' cannot use an index at all, are in Composite covering and hash indexes.

An SSD-backed key-value store keyed by prefix (ch 06) — a system that stores a value for each key on solid-state disk and fetches it in one read. Good: one random read per request, no rebuild-and-ship pipeline, and it genuinely fits the latency budget at 100 microseconds against 24 ms.

It is rejected, but not on device count, and the difference matters enough to spell out. IOPS means input/output operations per second: the rate at which a disk can service reads.

The familiar version of this argument divides the request rate by 10,000 IOPS and concludes you need 28 devices. That 10,000 is a queue-depth-1 figure — the rate you get issuing one read at a time and waiting for each to come back — misread as the device’s ceiling (The two rows that will burn you). A real device serving many reads at once does about 500,000 IOPS, and 281,280 / 500,000 = 0.6 is global offered load over one device’s capacity. One device serves the whole world, so the cost objection evaporates.

The rejection stands on different ground. You would be paying for a storage round trip, a cache tier, and an eviction policy — the rule deciding what to discard when the cache fills — in order to hold 23 GB that already fits in one machine’s 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. Good: no staleness, no pipeline, no distribution problem. Rejected at 800,000 node updates per second producing 16 million real changes a day, a 5,000:1 waste ratio, with 40,000 of those writes per second landing on the single root node that every read also touches, and 14.4 million replication messages per second to keep 18 replicas agreeing about a structure that has no consistency requirement in the first place.

Traversing the subtree at read time and ranking on the fly. Good: 16 GB cheaper, and no cached list to invalidate. Rejected at 385 ms for a one-character prefix, 16x the budget, on the most common request in the system. Kept as a hybrid, though: nodes with fewer than 10,000 descendants are traversed rather than cached, which is where the 100x memory saving in Deep dive 1 the trie and why top k is cached at every node comes from.

Shipping the whole index to the client. Good: 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, and it is the reason the rest of the design gets to be simple.

A plain character trie with no radix compression. Good: simpler build, simpler code. Rejected at 1.5 billion nodes against 200 million, a 7.6x memory multiple, on a structure whose entire viability rests on fitting in RAM.

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

14. Interviewer pushback

This design invites seven questions. Each comes with what the interviewer is actually testing, and the answer as it should be said out loud.

“Why can’t the trie just be updated as queries come in?” Testing: whether you can price a write path.

Because a single query event touches all 20 of its ancestor nodes, and at 4 billion events a day that is 80 billion node updates — 800,000 a second. Measured on a week of logs, only about 0.02% of those touches actually reorder a cached list, so 16 million updates a day are doing the work of 80 billion. A 5,000:1 waste ratio.

The placement is worse than the volume. Every event touches the root, so that one node takes 40,000 writes a second while serving 960,000 reads a second. And the same structure has to be replicated to the 18 machines holding that locale’s index, which is 14.4 million update messages a second to maintain a consistency property the requirements explicitly do not ask for.

The batch alternative aggregates 160 GB of log in about 1,600 machine-seconds. That is the comparison, and it is three orders of magnitude.

“How stale can the suggestions be, and how did you pick that?” Testing: whether “hourly” is derived or habitual.

I did not pick it. The image size picked it. The artifact is 23 GB and it has to reach 18 replicas — 3 per region across 6 regions. Pushing from one origin at 1 Gbps is 414 GB of egress, which is 55 minutes and leaves nothing for the build. A tree fan-out, where every machine that already holds the image seeds exactly one more so the population doubles rather than triples, is 184 seconds per hop; log2 18 = 4.17 rounds up to 5 hops because a fractional hop does not exist, so 920 seconds, or 15.3 minutes.

Add the build and you are at tens of minutes, so hourly is the natural cadence and mean staleness is about 30 minutes.

I would flag the replica count itself, because it is the thing people fumble. 281,280 QPS is a global offered load, so you divide by regions, you do not multiply. Do it the other way and you land on a 120-machine fleet and a 6-hour distribution step, neither of which exists.

The lever for tighter freshness is image size, not the scheduler: ship deltas, since only 16 million node lists change a day.

And an hour is unacceptable for exactly one class of term, so that class gets its own path. A count-min sketch over the stream detects terms whose 5-minute rate jumps against their 24-hour rate, and a 400 KB overlay goes out every 30 seconds. That overlay is 0.0017% of the image and it carries the entire freshness requirement.

“You said shard the trie by prefix. Is s one twenty-sixth of your traffic?” Testing: whether you have looked at a real distribution.

No. s is about 8.1% and the uniform share is 3.85%, so the hottest shard runs 2.1x the mean and 40x the coldest, and I would have to provision all 26 for the hot one.

Hashing the first three characters gets the variance down. At the same 26 shards that is 676 buckets each and a coefficient of variation of 3.9%, which is the virtual-node result from Virtual nodes buy variance not mean. I would quote it at 26 shards rather than the 7.5% you get at 100, because 26 is the fleet being replaced.

But hashing does not fix a hot key. Under a Zipf fit within s, the top three-character bucket is about 1.1% of traffic, and the shard holding it still runs 2.1x the mean — right back where the letter shards were.

I would also say why the fit has to be done that way. A Zipf spread over all 17,576 buckets returns 9.7%, which is impossible on its face: every query starting with three characters also starts with one, and no letter exceeds 8.1%.

So I would not shard by prefix at all. The index is 23 GB, which fits on one box, so I replicate rather than partition, and I shard by locale — 23 + 6.9 x 49 = 361 GB across 50 locales. It is stable, and it doubles as the placement key that keeps every user within a regional round trip.

“Why cache the top ten at every node? That is a lot of memory.” Testing: whether you compared it to the alternative.

Sixteen gigabytes, and the alternative is 385 milliseconds.

To rank a prefix without a cached list I have to visit every descendant. s has about 3.85 million of them under a uniform model, and at 100 nanoseconds per memory reference that is 0.385 seconds against a 24 ms budget — 16x over, on the most common request there is. With the list cached the read is one hop per character, at most 20 of them, which is 2 microseconds. That is 192,500x for 16 GB, and the whole index is 23 GB against a 128 GB default box.

If memory were tight I would cache selectively. A node with fewer than 10,000 descendants takes under a millisecond to traverse, so cache only above that threshold and the tier shrinks about a hundredfold.

I would count the qualifying nodes rather than eyeball them. At most 1e8 / 10,000 nodes at any one depth can clear the threshold, and there are 20 depths, so it is at most 200,000 nodes out of 200 million. Under the uniform model it is 702, at depths 1 and 2 only — which puts depth 3 below the line rather than above it.

“What debounce would you use?” Testing: whether the client is part of your design.

Fifty milliseconds, and it comes out of the same budget as everything else. The perceived target is 100 ms; a warm HTTP/2 round trip to a regional PoP is 20 ms, the internal hop is 1, the paint is 5, and I want 24 for retrieval. That leaves exactly 50 for the debounce.

At a 300 ms mean inter-keystroke interval, a 50 ms trailing debounce suppresses about 15% of requests.

I would not go to 200 ms for the 49% saving, because that spends user-visible budget to buy a traffic reduction the head blob gives me for free. Shipping the top 1,000 prefixes to the browser as a 100 KB gzipped payload answers 71% of requests with no network at all, and takes peak from 960,000 to 281,280 QPS.

“My suggestion box sometimes shows results for what I typed two characters ago. What happened and how do you fix it?” Testing: whether you have shipped one of these.

The cause is responses arriving out of order. Requests for c, ca, and car are in flight together, the ca response comes back last, and the client renders it over the car one.

With a 300 ms mean gap, the chance the next keystroke lands within 100 ms is 28%, and from the client latency histogram the chance two consecutive responses differ by more than that gap is about 2% — so roughly 0.6% of keystrokes. I would apply that to the 281,280 that actually reach the network rather than to the naive 960,000, because a response cannot arrive out of order if the head blob answered it locally and it never left the machine. That makes it 1,603 wrong renders a second at peak, and essentially never reproducible on a developer’s machine.

The fix I would ship is a single equality check: render the response only if the prefix it answers equals the input’s current value. It is correct regardless of transport, retries, or HTTP caching, and a mismatch is simply dropped.

AbortController on the previous request is worth adding to save bandwidth, but it is best-effort and I would not rely on it. A monotonic sequence number is useful mostly as the telemetry key.

“The whole index is 23 GB. What happens when the vocabulary is ten times bigger?” Testing: whether the design has a next step.

Two hundred and thirty gigabytes is well past the 128 GB default box and at the edge of even the 256 GB top of the commodity range.

So the first move is to stop retaining what nobody types. The tail of a Zipf distribution contributes almost no impressions, and cutting the retained vocabulary from a year to 90 days plus a distinct-user floor removes most of it at negligible quality cost.

If the vocabulary is genuinely ten times richer rather than ten times longer-tailed, then the top-k tier is what grew, and the selective-caching threshold from The cost of caching takes it down about a hundredfold on its own.

Only after both of those would I partition within a locale. I would do it by hashed prefix bucket, with the head prefixes replicated to every shard — because the hot bucket is 1.1% of traffic and its shard still runs 2.1x the mean, and partitioning alone does nothing for that.

Cheat sheet

This is the whole chapter compressed to the sixteen lines worth carrying into a whiteboard. RTT is one network round trip, DC is the hop inside the datacenter, and CV is the coefficient of variation.

Related: the latency table this chapter subtracts from is 02 — Back-Of-The-Envelope; 05 — Consistent Hashing gives the variance result and the hot-key caveat; 06 — Key-Value Store is the SSD-backed alternative priced in Alternatives rejected.

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