Design Autocomplete

Problem statement

The prompt is short: design autocomplete. A search box shows completions while a person is still typing, before any search has run, and the service behind the box has to supply those completions for every keystroke. The completions are called search suggestions: the terms the box offers for the text typed so far, drawn from what people have searched before.

The scale is fixed by the prompt and it is large. The service handles 5,000,000,000 searches a day, which is 57,870 searches per second, and typing multiplies that load because each new letter sends a fresh request. The answer is also tightly bounded in two directions: the box shows the top 5 suggestions for the typed prefix, and the whole answer must come back in about 100 milliseconds, or the suggestions arrive after the typist has already moved on.

Two properties make the problem hard rather than merely large. The first is the shape of the traffic: requests are tiny, answers are tiny, but they arrive at 57,870 searches per second and every one of them is impatient. The second is that popularity changes: the counts that rank suggestions shift as new searches land all day, so an answer that was right an hour ago can quietly become the wrong order, or miss a rising term altogether.

In scope

• Returning the top 5 suggestions for the typed prefix, ranked by how often each term is searched
• One fresh answer per keystroke, inside a budget of about 100 milliseconds
• Building the ranking from a log of finished searches, counted into term counts
• Keeping suggestions reasonably fresh as new searches arrive through the day
• Serving every language from counts and terms of that language

Out of scope

• Running the search itself and showing the results page; the box only suggests terms
• Personalised suggestions drawn from one person's own history; one stored list serves every user for a prefix
• Spelling correction and query rewriting beyond offering completions
• Ranking the results of a finished search

The scope line matters because autocomplete is an assistant to search, not search itself. A suggestion service that is down must never take the search box down with it, and a suggestion list that is slightly stale is a far smaller problem than a search that never runs. Those two facts shape the failure behaviour and the freshness choices that follow.

Requirements

The requirements are the contract the rest of the design is judged against. A prefix is the starting letters of a word, or the text typed so far in the box, and almost every requirement is stated in terms of prefixes and their suggestion lists. Each functional item names a behaviour with its consequence, and each non-functional item names a bar that behaviour has to clear.

Functional requirements

• Answer a prefix: given the text typed so far, return the top 5 suggestions for that prefix, ranked by past search count, so the most likely completions are the ones on screen
• Answer every keystroke: each new letter asks for a fresh answer, so a person typing a 5 letter word sends 5 requests and the list must keep up with the typing
• Rank by popularity: terms are ordered by how often each term is searched, because the box is a popularity contest among the terms sharing a prefix
• Count finished searches: every completed search is recorded in a search log, because the counts that rank tomorrow's suggestions come from today's searches
• Refresh the lists: stored suggestions are rebuilt from the newest counts on a regular cycle, so rising terms eventually appear and fading terms eventually leave
• Serve each language separately: a prefix in one language is answered from that language's terms and counts, because the same letters mean different completions in different languages

Non-functional requirements

• Speed: the whole answer comes back in about 100 milliseconds, because a slower answer is overtaken by the next keystroke and wasted
• Throughput: the service sustains 57,870 searches per second, and the per-keystroke traffic that sits behind those searches, without the suggestion path becoming the bottleneck of the search product
• Small answers: each answer holds at most 5 suggestions, so responses stay tiny and cheap to send at very high rates
• Bounded staleness: suggestions may lag real searches by up to one rebuild cycle, and no longer, so a new term has a known worst-case wait before it can appear
• Equal answers: the stored list for a prefix is the same for every user, which keeps serving a plain lookup and is also the stated limit on personalisation
• Graceful failure: if suggestions fail, typing and searching carry on without them, because the assistant must never break the tool it assists

The ranking rule deserves one precise statement before any structure is chosen. Terms carry a count of past searches, and the box ranks the matches for the typed text by that count, highest first. Only the first few matches are shown, even when more terms match, and the demo below shows the shape exactly: 6 terms match the prefix in the demo data, the counts order them, and the answer holds the top 5 while the lowest-count match is left out.

terms = [
    ("photo", 900),
    ("photos", 800),
    ("photo editor", 700),
    ("photography", 500),
    ("photo print", 300),
    ("photo book", 200),
    ("pizza", 950),
]
prefix = "pho"
matches = [pair for pair in terms if pair[0].startswith(prefix)]
matches.sort(key=lambda pair: -pair[1])
for term, count in matches[:5]:
    print(term, count)
print("suggestions shown:", len(matches[:5]))

That small demo fixes the meaning of a correct answer for the whole design. An answer is not every term sharing the prefix, and it is not the terms in alphabetical order; it is the 5 highest-count matches, in count order. Every structure considered later — the trie, the count table and the stored lists — exists to produce exactly that answer, fast enough and fresh enough.

Scale estimates

The estimates start from the figures the prompt itself fixes, and every later number is derived from those inputs in the open. The stated inputs are 5,000,000,000 searches a day, the top 5 suggestions per answer, and a budget of about 100 milliseconds per answer. One day holds 86,400 seconds, and that constant converts the daily count into the rate the serving fleet actually feels.

The scale of the problem

The request multiplication comes first, because it is the easiest load to underestimate. Typing the word photo sends one request per letter, 5 requests in all, one for each growing prefix. The printout shows the text growing letter by letter, and the count at the end is the load multiplier hiding inside a single search.

typed = "photo"
prefix = ""
for letter in typed:
    prefix = prefix + letter
    print("typed so far:", prefix)
print("requests sent:", len(typed))

The daily count becomes a rate by a single division. A daily count becomes a per-second rate by dividing by the seconds in a day, and the printout shows both numbers for the service: the stated daily total and the rate that falls out of it. That rate, 57,870 searches per second, is the average the fleet must sustain before any peak or any per-keystroke multiplication is considered.

searches_per_day = 5000000000
seconds_per_day = 86400
per_second = round(searches_per_day / seconds_per_day)
print("searches per day:", searches_per_day)
print("searches per second:", per_second)

The arithmetic itself is short enough to state in one line: 5,000,000,000 ÷ 86,400 = 57,870 searches per second. The average hides the peaks of a real day, and it also hides the keystroke effect, because the finished searches counted in the daily total each began as a short stream of prefix requests. Both effects push the true request rate upward from the average, which is why the serving path is designed to be a single cheap lookup rather than any kind of search through the term list.

The closing model of the ask combines the two effects on a small stage. Two typed words send one request per letter, each finished word is answered from the stored counts, and the two searches take 10 requests in all. Each answer holds the top suggestions for its word, and the word with only one matching term simply returns a shorter list.

terms = [
    ("photo", 900),
    ("photos", 800),
    ("photo editor", 700),
    ("photography", 500),
    ("photo print", 300),
    ("photo book", 200),
    ("pizza", 950),
]

def suggest(prefix):
    matches = [pair for pair in terms if pair[0].startswith(prefix)]
    matches.sort(key=lambda pair: -pair[1])
    return [term for term, count in matches[:5]]

total_requests = 0
for word in ["photo", "pizza"]:
    prefix = ""
    for letter in word:
        prefix = prefix + letter
        total_requests = total_requests + 1
    print(word, "->", suggest(word))
print("total requests:", total_requests)

Three conclusions follow from the estimates and drive everything after them. First, the answer must be produced by lookup, not by computation, because 57,870 searches per second leave no room for scanning or sorting inside a budget of about 100 milliseconds. Second, the ranking work has to happen somewhere else and at some other time, because the counts behind the ranking change constantly while the budget never does. Third, the stored answer for a prefix can be very small — 5 short terms — so keeping ready answers for popular prefixes is cheap in space even when the prefix set is large.

API design

A small set of operations carries the whole design, and only one of them faces the typing user. The suggestion read is synchronous: the box is waiting, the budget is about 100 milliseconds, and nothing may queue in front of it. Everything else — recording a finished search, counting it, rebuilding the stored lists — is asynchronous work that travels through a queue, because none of it is allowed to slow down either the search itself or the next keystroke.

Core operations

The split between the synchronous read and the queued work is the point of the shapes. A suggestion read does exactly one thing: it takes the prefix, finds the shard and the stored list for that prefix, and returns the list. Recording a search does the opposite: it accepts the term, appends it to the search log durably, and returns, leaving the counting to workers that drain the log between rebuilds.

Two details of the read operation repay care. An empty or very short prefix still gets an answer — the stored list for that prefix, which may hold the most popular terms overall — because the box must never flicker into an error state while someone types. A prefix with no matching terms returns an empty list rather than an error, for the same reason: no suggestions is a normal answer, and the box simply shows nothing.

Data model

Four stored shapes carry the design, and each exists because one flow needs it. The search log is the raw record of finished searches, in the order they happened. The count table holds the number of past searches for each term, counted from the log, and the trie and the stored suggestion lists are both built from those counts.

Core entities

The stored suggestion list is the deliberate denormalisation at the heart of the model. Denormalisation means storing data in the shape a read needs, copied and rearranged, instead of the single shape a write prefers. A stored list copies the top 5 terms for a prefix into one small record, so a read fetches one record and checks nothing else, and the price is that the copies have to be rebuilt whenever the counts move enough to matter.

The partition choice follows from the read shape. The shard key — the value that decides which machine holds a piece of data — is the first letter of the typed prefix, because a lookup always knows its first letter before it knows anything else. Every prefix therefore lives on exactly one shard, a lookup visits exactly one machine, and no read ever has to fan out across the fleet and merge partial answers inside the budget.

High-level architecture

Requests enter through a load balancer, which spreads them across a fleet of suggestion servers, and each server routes a request by the first letter of the prefix to the shard that owns that letter range. A shard is one machine holding the tries and stored lists for its range of first letters, with the data held ready to serve from memory. Behind the serving path, the search log feeds a queue of counting jobs, workers fold new searches into the counts, and a builder rebuilds the stored lists on a cycle and publishes them to the shards.

┌─────────┐  prefix per keystroke  ┌───────────────┐
│ Search  │ ─────────────────────▶ │ Load balancer │
│ box     │ ◀───────────────────── └───────────────┘
└─────────┘   top 5 suggestions            │
     │                                     ▼
     │ finished search            ┌───────────────┐
     ▼                            │ Suggestion    │
┌─────────┐                       │ servers       │
│ Search  │                       └───────────────┘
│ log     │                              │ first letter
└─────────┘                              ▼
     │                       ┌────────┐ ┌────────┐ ┌────────┐
     ▼                       │ Shard  │ │ Shard  │ │ Shard  │
┌─────────┐                  │  a-i   │ │  j-r   │ │  s-z   │
│ Queue + │                  └────────┘ └────────┘ └────────┘
│ counting│                       ▲          ▲          ▲
│ workers │                       └──────────┴──────────┘
└─────────┘                  fresh lists, hourly rebuild

The suggestion flow

1. The box sends the typed prefix and the language with each keystroke
2. The load balancer passes the request to a suggestion server
3. The server reads the first letter and routes the request to the one shard owning that letter range
4. The shard reads the single stored list for the prefix and returns it
5. The box shows the top 5 suggestions from the returned list

The counting and rebuild flow

1. Each finished search is appended to the search log and placed on the counting queue
2. Workers drain the queue and fold each search into the pending counts
3. On the rebuild cycle, the builder adds pending counts to the stored counts and rebuilds the stored lists
4. The fresh lists are published to the shards, replacing the previous build in one swap

Scaling the serving side means splitting the stored tries across machines, so no single machine holds the whole alphabet. The trie is sharded by first letter, and each lookup visits one shard, which keeps the read a single-machine operation however large the term set grows. The cost is visible immediately in a small model: the demo deals a fixed term list into 3 shards by first letter, and the shards hold 5, 7 and 2 terms, so first letters do not split the store evenly.

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

for name in ["a-i", "j-r", "s-z"]:
    print(name, "holds", len(shards[name]), "terms:", shards[name])

The routing rule is what makes the split cheap to use. The typed prefix pe belongs to one shard only, so only that shard is checked, and the printout shows the 7 terms checked there against the 14 terms in the whole store. Halving the checked set is not the real prize at production scale; the prize is that the checked set stays one shard's worth, however many shards the fleet grows to.

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

typed = "pe"
name = shard_for(typed[0])
answer = [term for term in shards[name] if term.startswith(typed)]
print("shard visited:", name)
print("answer:", answer)
print("terms checked:", len(shards[name]))
print("terms in the whole store:", len(terms))

Language is the second split, and it is a split of stores rather than of machines. Each language needs its own trie and its own counts, because suggestions differ by language, and the same typed prefix is answered from two language stores with two different answers in the demo. One shared store cannot serve both languages, so language travels with every request and every stored list from the start.

stores = {
    "english": ["mango", "maps", "market"],
    "spanish": ["madrid", "manzana", "mar"],
}
typed = "ma"
for language in ["english", "spanish"]:
    answer = [term for term in stores[language] if term.startswith(typed)]
    print(language, "answer for " + typed + ":", answer)

The routing model closes the scaling picture by running several prefixes end to end. Four typed prefixes are routed by their first letter and answered by their own shard, and each line shows the prefix, the shard it visited and the answer that shard returned. Every functional requirement lands on a component in the diagram: suggestions on the shards and their stored lists, counting on the log, the queue and the workers, freshness on the rebuild, and language separation on the per-language stores.

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

for typed in ["ap", "ki", "pe", "st"]:
    name = shard_for(typed[0])
    answer = [term for term in shards[name] if term.startswith(typed)]
    print(typed, "-> shard", name, "->", answer)

Deep dive: finding the words under a prefix — the trie

The first hard sub-problem is retrieval: given a prefix, find every term that starts with it, quickly enough to leave room in a budget of about 100 milliseconds. A prefix can match a handful of terms or a very large family, and the match set has to be found without looking at terms that start with other letters. Two structures compete for the job, and the difference between them is where the shared beginnings of words are paid for.

Two ways to find the terms under a prefix

A trie is a tree that stores words one letter per node, so words with the same start share their early nodes. Lookup walks one node per typed letter, then collects every word stored under that node, and the demo builds a trie from a fixed word list and walks to the node for car. Every word collected under that node starts with car, and no word outside that subtree is visited at all.

words = ["cat", "car", "card", "care", "dog", "door"]

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node["end"] = True
    return root

def collect(node, prefix):
    found = []
    if "end" in node:
        found.append(prefix)
    for letter in sorted(node):
        if letter != "end":
            found = found + collect(node[letter], prefix + letter)
    return found

def walk(trie, prefix):
    node = trie
    for letter in prefix:
        if letter not in node:
            return None
        node = node[letter]
    return node

trie = build_trie(words)
node = walk(trie, "car")
for word in collect(node, "car"):
    print(word)

Sharing is where the trie earns its keep. A flat list stores every letter of every word, even the letters words share, while the trie stores a shared beginning once and branches only where words diverge. The printout counts the two shapes for the same words: the 6 words in the demo hold 21 letters in a flat list, but the trie stores them in 12 nodes, root included.

words = ["cat", "car", "card", "care", "dog", "door"]

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node["end"] = True
    return root

def collect(node, prefix):
    found = []
    if "end" in node:
        found.append(prefix)
    for letter in sorted(node):
        if letter != "end":
            found = found + collect(node[letter], prefix + letter)
    return found

def walk(trie, prefix):
    node = trie
    for letter in prefix:
        if letter not in node:
            return None
        node = node[letter]
    return node

trie = build_trie(words)

def count_nodes(node):
    total = 1
    for key in node:
        if key != "end":
            total = total + count_nodes(node[key])
    return total

flat_letters = 0
for word in words:
    flat_letters = flat_letters + len(word)
print("letters in a flat list:", flat_letters)
print("nodes in the trie, root included:", count_nodes(trie))

The walk also behaves cleanly at the edges, which matters for a box that receives every half-typed fragment. Each typed prefix gets its own short walk down the trie, starting again from the root, and a prefix no word starts with collects an empty list rather than causing an error. An empty answer is a normal answer for the box, and the structure produces it by simply failing to find the next node.

words = ["cat", "car", "card", "care", "dog", "door"]

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node["end"] = True
    return root

def collect(node, prefix):
    found = []
    if "end" in node:
        found.append(prefix)
    for letter in sorted(node):
        if letter != "end":
            found = found + collect(node[letter], prefix + letter)
    return found

def walk(trie, prefix):
    node = trie
    for letter in prefix:
        if letter not in node:
            return None
        node = node[letter]
    return node

trie = build_trie(words)
for prefix in ["c", "do", "z"]:
    node = walk(trie, prefix)
    if node is None:
        print(prefix, "->", [])
    else:
        print(prefix, "->", collect(node, prefix))

Ranking joins the structure at exactly one point. The trie stores words only, and the ranking counts live at the end node of each word, so collecting the words under a prefix also collects their counts. The closing model stores each word at a node that also holds its search count, ranks the words under pho by those counts, and shows the top 5 in count order, with the lowest-count word left out.

terms = [
    ("photo", 900),
    ("photos", 800),
    ("photo editor", 700),
    ("photography", 500),
    ("photo print", 300),
    ("photo book", 200),
]

def build_trie(terms):
    root = {}
    for term, count in terms:
        node = root
        for letter in term:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node["count"] = count
    return root

def collect(node, prefix):
    found = []
    if "count" in node:
        found.append((prefix, node["count"]))
    for letter in sorted(node):
        if letter != "count":
            found = found + collect(node[letter], prefix + letter)
    return found

trie = build_trie(terms)
node = trie
for letter in "pho":
    node = node[letter]
matches = collect(node, "pho")
matches.sort(key=lambda pair: (-pair[1], pair[0]))
for term, count in matches[:5]:
    print(term, count)
print("suggestions shown:", len(matches[:5]))

The verdict is the trie. The flat scan charges every lookup for the whole term list, while the trie charges one step per typed letter plus the collection of the subtree the typist actually asked about, and shared prefixes are stored once instead of once per word. The cost is a node structure that must be built, held in memory and rebuilt as counts change — and that last cost is exactly what the precomputation choice, examined next, turns into an advantage.

Deep dive: serving from the trie or serving precomputed suggestions

Finding the matches is only half the answer, because the matches still have to be ranked, cut to the top 5 and returned, all inside about 100 milliseconds and at 57,870 searches per second. The ranking work is the same work for every keystroke that lands on the same prefix, and popular prefixes receive that same keystroke very many times. The question is when the ranking work happens: once per keystroke, at the moment of asking, or once per build, before anyone asks.

Two times to do the ranking work

Precomputation is working out an answer before it is asked and storing it ready to serve, and its inputs are built in two steps. The first step counts the past: the search log, the record of finished searches, is counted into a count table holding the number of past searches for each term. The demo counts a fixed log into a table where each term appears once with its total beside it, 16 searches counted into 6 counted terms in all.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
counts = {}
for term in log:
    counts[term] = counts.get(term, 0) + 1
for term in sorted(counts):
    print(term, counts[term])
print("searches counted:", len(log))

The second step turns counts into ready answers. For each popular prefix, the counted terms that start with it are sorted by count, and the stored list keeps the top 5 as a single ready answer. The printout shows the stored list for each prefix in the demo, highest count first, and a prefix with only one matching term stores a list of one.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

counts = count_terms(log)
store = build_store(counts)
for prefix in sorted(store):
    print(prefix, "->", store[prefix])

Serving then collapses to a single read. A lookup reads a single stored list instead of checking all 6 counted terms, and the printout shows the answer, the lists touched and the terms a live scan would check: 1 stored list touched against 6 counted terms. At production scale the same shape holds with far larger counts on the scan side, which is precisely why the precomputed answer fits the budget and the live one strains it.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

counts = count_terms(log)
store = build_store(counts)
typed = "ph"
touched = 0
answer = store[typed]
touched = touched + 1
print("answer for " + typed + ":", answer)
print("stored lists touched:", touched)
print("counted terms a live scan would check:", len(counts))

Building for every prefix of every term shows the true storage shape of the choice. The closing model counts the log first, then stores the top 5 terms for every prefix of every counted term, and the build makes 28 stored lists from the small demo vocabulary. Each typed prefix after that reads exactly one list, so storage grows with the number of distinct prefixes while serving cost stays flat at one read.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

counts = count_terms(log)
store = {}
for term in counts:
    for i in range(1, len(term) + 1):
        prefix = term[:i]
        matches = [t for t in counts if t.startswith(prefix)]
        matches.sort(key=lambda t: (-counts[t], t))
        store[prefix] = matches[:5]
print("stored lists:", len(store))
print("pho ->", store["pho"])
print("p ->", store["p"])

The verdict is precomputed stored lists for serving, with the trie kept as the building structure underneath. Serving becomes one lookup on one shard, which is the only shape that comfortably holds about 100 milliseconds at 57,870 searches per second, and the counting and sorting work happens once per build rather than once per keystroke. The admitted cost is freshness: a stored list is a snapshot, and keeping the snapshot honest is a separate problem with its own cycle.

Deep dive: keeping suggestions fresh

A precomputed answer is a snapshot, and search counts change every hour of the day. New terms are born when news breaks or a name trends, and existing terms surge and fade, while the stored lists say whatever the last build computed. Freshness — how recent the stored suggestions are — is therefore a designed quantity with a chosen value, not an accident of the pipeline.

Three rebuild rhythms

The stale window is concrete rather than theoretical. Between rebuilds, new searches are logged and counted, but the stored lists stay as they are, so a brand-new term appears only after the next rebuild. In the demo, a new term searched 6 times still waits for the next rebuild: the stored answer is unchanged, and the new term is missing from it despite its searches.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
new_searches = ["photo booth", "photo", "photo booth", "photo booth", "photos", "photo booth", "photo booth", "photo booth"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

store = build_store(count_terms(log))
answer = store["ph"]
print("stored answer for ph:", answer)
print("photo booth in the answer:", "photo booth" in answer)
print("searches for photo booth since the rebuild:", new_searches.count("photo booth"))

Counting does not stop while the lists wait, and that separation is what makes the cycle workable. New searches wait in a queue as counting jobs, and a worker takes them one by one, folding each into the pending counts. The printout shows the pending counts for the waiting searches and the emptied queue, ready for the builder whenever the cycle turns.

new_searches = ["photo booth", "photo", "photo booth", "photo booth", "photos", "photo booth", "photo booth", "photo booth"]
queue = []
for term in new_searches:
    queue.append(term)
pending = {}
while len(queue) > 0:
    job = queue.pop(0)
    pending[job] = pending.get(job, 0) + 1
for term in sorted(pending):
    print(term, pending[term])
print("jobs left in the queue:", len(queue))

The rebuild is the moment the snapshot moves. The rebuild adds the pending counts to the old counts and stores fresh lists, and the printout shows the new term inside the answer, ranked by its count among the established terms. Nothing about serving changes at that moment: the shards swap one build for the next, and the following keystroke reads the fresh list by the same single lookup as before.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
new_searches = ["photo booth", "photo", "photo booth", "photo booth", "photos", "photo booth", "photo booth", "photo booth"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

counts = count_terms(log)
for term in new_searches:
    counts[term] = counts.get(term, 0) + 1
store = build_store(counts)
answer = store["ph"]
print("stored answer for ph:", answer)
print("photo booth in the answer:", "photo booth" in answer)

Two cycles side by side show the rhythm as a whole. The closing model runs two rebuild cycles over the same growing counts: the first cycle answers without the new term, the second cycle answers with it, and the prefix whose counts did not change keeps its old answer. A prefix nobody's counts touched is rebuilt to the same list, which is wasted work the cycle accepts in exchange for a simple, uniform build.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]
new_searches = ["photo booth", "photo", "photo booth", "photo booth", "photos", "photo booth", "photo booth", "photo booth"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

counts = count_terms(log)
store = build_store(counts)
print("cycle 1 answer for ph:", store["ph"])
print("cycle 1 answer for pi:", store["pi"])
for term in new_searches:
    counts[term] = counts.get(term, 0) + 1
store = build_store(counts)
print("cycle 2 answer for ph:", store["ph"])
print("cycle 2 answer for pi:", store["pi"])

The verdict is the hourly rebuild: the design rebuilds its lists every hour. An hourly cycle bounds the stale window at one cycle — a new term's worst wait is known and short enough for a popularity signal — while keeping rebuild work at 24 builds a day rather than a continuous write load. The cost is stated plainly: suggestions lag real searches, and a fast-breaking term spends its first hour invisible to the box.

Bottlenecks and failure modes

The first component to saturate is a hot shard, and the cause is built into the shard key. First letters are not equally popular, in vocabulary or in searches, so the shard holding a busy range receives a disproportionate share of the 57,870 searches per second while quieter shards idle. Adding machines does not help until the letter ranges are redrawn, because the routing rule sends every prefix to exactly one shard by design.

The rebuild pipeline is the second pressure point, and its symptom is staleness rather than error. If counting workers fall behind, pending counts grow and the next build is computed from older data, so lists drift further behind real searches while serving continues untouched. If a build itself overruns its cycle, the swap simply happens late, and the fleet serves the previous build for longer than planned.

• A shard fails: prefixes in its letter range lose their suggestions until a replica of that shard takes over, and every other letter range keeps answering normally
• A suggestion server fails: the load balancer routes around it, because any server can route any prefix to its shard
• Counting workers stall: searches are still logged, counting resumes from the log when workers return, and only freshness suffers in the interval
• A rebuild publishes a bad build: the previous build is kept until the new one is complete, so shards swap back or stay on the old lists rather than serving a half-built store
• The whole suggestion service fails: the box shows no completions, and typing and searching carry on exactly as before, which is the failure the scope promised to allow

The degradation order follows the requirements. Freshness degrades first, because stale suggestions are a mild fault; coverage degrades next, when one letter range goes dark; and speed must not degrade at all, because an answer slower than about 100 milliseconds is worse than no answer — it arrives after the typist has moved on and trains people to ignore the box. The one outcome that must never degrade is the search itself, which the suggestion path can slow or stop only by being wrongly coupled to it.

Trade-offs

The decisions and their costs

Every choice trades speed, freshness or storage against the others, and the ask decides which side wins. The sharpest of those trades is the first one, and the demo states it without decoration: the stored answer and a live answer are built from different counts for the same prefix, and the two lists side by side do not match. The stored answer is the fast one, and the live answer is the fresh one, and no design gets both at once.

stored = ["photo", "photos", "photo editor", "photo print", "photography"]
counts = {"photo": 7, "photos": 4, "photo booth": 6, "photo editor": 2, "photo print": 1, "photography": 1, "pizza": 3}
matches = [term for term in counts if term.startswith("ph")]
matches.sort(key=lambda term: (-counts[term], term))
live = matches[:5]
print("stored answer:", stored)
print("live answer:", live)
print("answers match:", stored == live)

The work accounting behind that trade is equally plain. Three lookups served both ways show 18 term checks the live way against 3 stored reads the precomputed way, because each live lookup checks all 6 counted terms while each precomputed lookup reads 1 list. The ratio grows with the vocabulary: the live cost is per keystroke and per term, while the precomputed cost is per build.

counts = {"photo": 6, "photos": 3, "photo editor": 2, "photo print": 1, "photography": 1, "pizza": 3}
store = {"ph": ["photo", "photos", "photo editor", "photo print", "photography"], "pi": ["pizza"]}
lookups = ["ph", "pi", "ph"]
live_checks = 0
stored_reads = 0
for typed in lookups:
    live_checks = live_checks + len(counts)
    stored_reads = stored_reads + 1
print("term counts checked the live way:", live_checks)
print("stored lists read the precomputed way:", stored_reads)

Sharding by first letter carries the mirror-image cost, paid in balance rather than freshness. Search counts totalled per shard for a fixed set of terms show one shard taking most of the searches while the others stay quiet: the s-z shard takes 90 searches, the a-i shard takes 15 searches, and the j-r shard takes 8 searches. Lookups stay on one machine, which was the point of the key, and the busiest machine sets the fleet's real capacity, which is the price.

searches = {"sun": 40, "sand": 30, "sea": 20, "apple": 10, "avocado": 5, "plum": 8}
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

totals = {"a-i": 0, "j-r": 0, "s-z": 0}
for term in searches:
    totals[shard_for(term[0])] = totals[shard_for(term[0])] + searches[term]
for name in ["a-i", "j-r", "s-z"]:
    print(name, "takes", totals[name], "searches")

The closing model runs the whole design end to end as a final check on the assembled choices. A log is counted, stored lists are built, and a typed prefix is routed to its shard for the answer, with 2 stored lists built for the demo prefixes. Each printed line is one stage of the design — counting, building, routing, answering — and the stages appear in the order the flows use them.

log = ["photo", "photos", "photo", "pizza", "photo editor", "photo", "photos", "photo print", "pizza", "photo", "photography", "photo", "photos", "pizza", "photo editor", "photo"]

def count_terms(entries):
    counts = {}
    for term in entries:
        counts[term] = counts.get(term, 0) + 1
    return counts

def build_store(counts):
    store = {}
    for prefix in ["ph", "pi"]:
        matches = [term for term in counts if term.startswith(prefix)]
        matches.sort(key=lambda term: (-counts[term], term))
        store[prefix] = matches[:5]
    return store

ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

counts = count_terms(log)
store = build_store(counts)
typed = "ph"
print("typed:", typed)
print("shard visited:", shard_for(typed[0]))
print("answer:", store[typed])
print("stored lists built:", len(store))

Taken together, the design spends storage and build work to buy speed at the keystroke, and spends freshness to buy both. Stored lists make each answer one read, the hourly cycle keeps that read honest within a known bound, and first-letter sharding keeps the read on one machine as the vocabulary grows. A far smaller search service, with a vocabulary that fits on one machine and a rate far below 57,870 searches per second, should make the opposite exchange and serve live from the trie, because the shape of the right answer follows the shape of the load.

Common questions

How fast does autocomplete have to answer?

The whole answer must come back in about 100 milliseconds, measured against traffic of 5,000,000,000 searches a day, which is 57,870 searches per second. The budget is strict because typing does not wait: each new letter sends a fresh request, and an answer that arrives after the next letter has been typed is discarded unread. That is why serving is one stored read rather than any form of computation at request time.

Why are the suggestion lists precomputed instead of served live from the trie?

Live serving repeats the collecting and sorting work for every keystroke, while precomputing pays that work once per build. The counted comparison is 18 term checks the live way against 3 stored reads the precomputed way for the same 3 lookups, and the gap widens as the vocabulary grows. The trie still does the finding during the build; precomputation changes when the work happens, not whether it happens.

When does a brand-new search term appear in the suggestions?

A brand-new term appears after the next rebuild of the stored lists, and the design rebuilds every hour, 24 times a day. Workers count the new searches in the interval — a term searched 6 times is fully counted long before it is visible — but the stored lists change only at a rebuild. The stale window is therefore bounded by one cycle, and that bound is the freshness guarantee the design offers.

Why is the trie sharded by first letter?

The first letter is the one fact every lookup knows before any work happens, so it routes each prefix to exactly one shard and keeps the read on one machine. The demo routing checked 7 terms on the visited shard against 14 terms in the whole store, and the same rule keeps a production lookup inside one shard however large the vocabulary grows. The accepted price is imbalance: busy first letters make hot spots, and one busy shard in the counted demo took 90 searches while the quietest took 8 searches.

The estimate at a glance