Design a Search Autocomplete System

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is Autocomplete?

You Already Know It: Finishing Someone's Sentence

A friend starts a sentence, "How do you b…", and you jump in: "boil an egg?" You didn't wait for the whole question. You guessed the most likely ending from what people usually say.

Autocomplete (also called typeahead) does the same thing for a search box. You type how to b, and before you type the next letter a list appears: how to boil an egg, how to be happy, how to budget. Each item is a completion: a whole query that starts with what you've typed so far, which we call the prefix.

What Makes It Hard

• Time. The list has to appear before the next keystroke. People type a character every 150 to 300 ms (a 40 words-per-minute typist types about 200 characters a minute, one every 300 ms; at 80 words per minute it's one every 150 ms). So the whole round trip gets about 100 to 150 ms, and our servers get only a few milliseconds of that.
• Numbers. Every search is several requests, one per pause in typing, and a big search engine handles billions of searches a day.
• Freshness. When news breaks, people search for it within minutes. A list built yesterday doesn't know about it.
• Safety. A suggestion is the product speaking. It must never suggest something offensive, illegal or private, even when bots try to push it in.

The Question the Whole Loop Answers

How do we answer every keystroke in milliseconds with the best, freshest and safest completions?

The answer gets sharper every round:

• Round 1: do the expensive work offline. Build a prefix tree with the top completions stored at every node, once a day, and serve it from memory.
• Round 2: keep that offline structure, but add a fast lane for trending queries, an edge cache, safe deploys of a 16 GB structure, a typo fallback and a safety filter.
• Round 3: add languages, people and law: tries per locale, sharding, personal history, privacy-preserving counts, regions and experiments.

---

Round 1 · Mid-level · "Autocomplete for One Online Store"

~35 min · SDE II (L5) · 1 region, 3 AZs · ~1M distinct queries · ~1K requests/s peak · P99 < 50 ms · 99.9%

R1.1 Establish Design Scope

The interviewer says: "Our online store has a search box. Add autocomplete to it." Before we draw anything, we ask questions and say what each answer changes.

Out of scope for this round:

• Trending queries. Something that became popular an hour ago waits for tomorrow's build.
• Typos. snaekers gets no suggestions.
• Safety filtering beyond not suggesting anything with personal data in it.
• Personalization and other languages.

R1.2 Functional Requirements, Derived Step by Step

Not yet: trending, typos, safety filtering, personalization, other languages.

R1.3 Non-Functional Requirements: the Questions

We state each quality in words first. The numbers come in R1.7.

• Latency against the keystroke. The list must feel instant. With 150 to 300 ms between keystrokes and a network round trip of 20 to 80 ms inside one country, our server should answer in a few milliseconds. We set the target at the load balancer: P99 < 50 ms, which is generous; an in-memory design will do far better.
• Availability, with graceful failure. Autocomplete is a helper. If it's down, the user types the whole query and presses Enter, and the search still works. So we aim for 99.9% (at most 0.1% × 8,760 h ≈ 8.8 h a year), and the bigger promise is that autocomplete failing never breaks search.
• Freshness. Daily. A query that became popular today appears tomorrow.
• Cost. It's a small feature on a store's website. It should cost hundreds of dollars a month, not thousands.

R1.4 The API

Ask for suggestions

httpCopy
GET /v1/suggest?q=sne&limit=5 HTTP/1.1
Host: api.shop.example.com
Accept: application/json

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: private, max-age=300

{
  "prefix": "sne",
  "snapshot": "2026-09-27",
  "suggestions": [
    { "text": "sneakers" },
    { "text": "sneakers men" },
    { "text": "sneakers white" },
    { "text": "sneaker cleaner" },
    { "text": "sneaker socks" }
  ]
}

• q is the prefix exactly as typed; the server lowercases and trims it.
• limit is at most 10.
• snapshot names the daily build that answered. It helps debugging ("why did I see this?") and tells the client when the data changed.
• Cache-Control: private, max-age=300 lets the browser reuse the answer for 5 minutes. When the user deletes a character and retypes it, the browser already has the answer.
• An empty list is a normal answer: "suggestions": [].

What the client does, and why

The client is half of the design. Without it, the server would get one request per keystroke and the screen would flicker.

1. Debounce. A debounce waits until the user pauses. After each keystroke the client starts a short timer (about 100 ms; a design choice in the 100–200 ms range), and restarts it on the next keystroke. The request goes out only when the timer runs out. A fast typist entering sneakers white (14 characters) pauses only a few times, so the client sends about 4 requests instead of 14. That "about 4 requests per search" is the number we size everything with.
2. Cancel stale requests. When a new request goes out, the client cancels the previous one still in flight (in a browser, with fetch and an AbortController). There's no point waiting for sn when the user has typed sne.
3. Ignore out-of-order answers. Responses can still arrive out of order on a mobile network. The client numbers its requests and drops any response older than the newest one it has shown, so sn's answer can never replace sne's.
4. Fail quietly. If no answer arrives within about 300 ms, or the server returns an error, the client shows no list. It never blocks typing or the Enter key.

Recap

• One operation: prefix in, top 5 queries out.
• About 10M searches a day and 1M distinct queries; English only.
• Daily freshness; P99 < 50 ms at the load balancer; autocomplete failing never breaks search.

Let's build it, starting with the simplest version that works.

R1.5 Design Evolution: From a SQL Query to a Precomputed Trie

Every step follows the same pattern: a problem, your turn to think, the answer, and what the answer costs us. The cost is always the next problem.

Step 1.0: The Baseline

A table in the store's existing database, filled by a nightly job from the search log:

sqlCopy
CREATE TABLE query_counts (
  query        TEXT PRIMARY KEY,   -- lowercased, trimmed
  count_30d    INTEGER NOT NULL
);

SELECT query FROM query_counts
WHERE query LIKE 'sne%'
ORDER BY count_30d DESC
LIMIT 5;

Synthesizing vector architecture diagram...

Every keystroke becomes a query against the store's main database.

It works, and for a demo it's the right answer. Everything that follows exists because this query does more work than it looks like.

Step 1.1: The Query Gets Slower as the Table Grows

Primitive: Trie Data Structure & Inverted Index

Step 1.2: Finding the Top 5 Under "s" Means Visiting Thousands of Nodes

A worked example. Seven queries from the store's log, with their 30-day counts: socks 1,200 · sneakers 900 · snow boots 700 · sandals 650 · sunglasses 500 · sneakers men 400 · socks wool 300. We show the top 3 at each node to keep the picture small.

Synthesizing vector architecture diagram...

A radix tree for seven queries. Each edge carries a string, and each node stores its top list. Notice the sn node: its top 3 merges its children's lists (sneakers 900, sneakers men 400 and snow boots 700). And the s node's top 3 comes from its four children's lists without looking at any leaf.

Three lookups, traced:

The third row is the radix-tree rule worth remembering: a prefix that ends inside an edge has exactly the same completions as the node at the end of that edge, because everything below that point is below that node. So we only store lists at real nodes, not at every character.

Step 1.3: Counts Change All Day

Step 1.4: Where Does the Trie Live?

Primitive: Distributed Cache Patterns & Eviction

How a server switches to a new snapshot. Every 5 minutes it reads latest.json. If the manifest names a new file, the server downloads it next to the one it is serving, checks the checksum and the size, builds its lookup structures, then swaps a single pointer so new requests use the new trie. Requests already running finish on the old one. Then the old one is freed. There is never a moment with no trie.

Step 1.5: Every Keystroke Fires a Request, and Answers Arrive Out of Order

Round 1 Step Summary

R1.6 Architecture v1

Now the concepts get AWS names.

Synthesizing vector architecture diagram...

The request path is short: load balancer, then a lookup in memory. Everything that takes real work (reading logs, counting, building) happens once a day, offline, and reaches the servers as one file.

Why these pieces:

• Firehose collects the search service's log lines and writes them to S3 in files every few minutes. Firehose bills each record rounded up to 5 KB, so the search service packs about 25 log lines (200 bytes each) into one record instead of sending one record per line.
• AWS Glue runs the daily Spark job. The job is small this round (a few hundred million log lines); Glue means no cluster to keep running between builds.
• Graviton m7g.large (2 vCPUs, 8 GiB): far more memory and CPU than we need. There are three of them for availability, one per AZ, not for load.
• ALB health checks call /health, which returns 200 only after the server has loaded a snapshot. A server that's still loading gets no traffic.

The snapshot file

The top lists hold query IDs, not text. The text lives once, in the query-string table, and the server turns 5 IDs into 5 strings with 5 array reads.

Tracing one request: the user types sne

Synthesizing vector architecture diagram...

One pause, one request, one walk in memory. The only real latency is the network.

Tracing the daily build

1. At 02:00 UTC, the Glue job reads the last 30 days of log files from S3: about 300M lines.
2. It normalizes, counts, and keeps about 1M queries seen at least 5 times.
3. It builds the radix tree, computes every node's top 5 bottom-up, and writes snapshots/2026-09-27/trie.bin with its checksum.
4. It writes snapshots/latest.json → {"snapshot": "2026-09-27", "file": "snapshots/2026-09-27/trie.bin", "crc32c": "…", "bytes": 167772160}.
5. Within 5 minutes each server sees the new manifest, loads the file beside the old one, checks it, and swaps.

R1.7 Numbers

Targets

Traffic

Memory for the trie (every per-node figure is an assumption for a compact array layout)

An 8 GiB server is more than enough. Loading 160 MB from S3 at ~100 MB/s takes about 2 seconds.

Servers

Rough monthly cost (us-east-1 on-demand list prices; check the AWS Pricing Calculator before quoting)

About $280 a month. That's what "precompute everything" buys: the serving path is so cheap that the servers are there for availability, not load.

R1.8 Trade-Offs

Where the suggestions come from

Why not just use a search engine with prefix matching? An inverted index (a map from each word, or each word's leading characters with edge n-grams, to the list of documents containing it) answers "which queries start with sne?" well. But it then has to score and sort the matches for every request, and for a one-letter prefix that is a large fraction of the whole index: the same "search the subtree" work as step 1.2, just inside another system, and an index built with edge n-grams stores every prefix of every word, so it is several times larger than the text. OpenSearch's completion suggester is closer to our design: it keeps a compact prefix structure (a finite-state transducer) in memory and returns completions ordered by a weight we set at index time. It's a fine choice; we'd still pay for a cluster and a network hop to get what a 160 MB file in our own process already gives us. We'll use OpenSearch in Round 2 for what it's good at: typos.

How many completions to store at each node (k)

At this size any of them fits. We store 5, because we show 5 and nothing filters them yet. Round 2 revisits this at 200M nodes, where each extra entry costs 1.6 GB.

Daily vs hourly builds. An hourly build is possible (the job takes minutes). But hourly doesn't really solve freshness (a news spike is minutes, not hours), and it multiplies build cost and deploys by 24. For a store, daily is right; for news, Round 2 adds a separate fast lane.

Drill: The search bar that stalled on every keystroke (step 1.2 answers why walking the subtree on every keystroke breaks down as the phrase count grows; the paragraph above answers why not an inverted index with prefix matching)

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Asks about ranking, freshness and where the data comes from before designing.
• Explains why an index doesn't fix ORDER BY count LIMIT 5 for short prefixes.
• Arrives at a trie and, crucially, at storing the top-k at every node, with a correct way to build it.
• Separates the offline build from the read-only serving path.
• Designs the client: debounce, cancel, drop stale, fail quietly.
• Sizes memory and servers from the numbers, and notices the servers exist for availability.

Follow-up questions

1. "Why not compute the top 5 for every prefix string, instead of a trie?" Answer: that's the key-value table, and it works. It stores one entry per distinct prefix string, which is several times more entries than a radix tree has nodes, because the radix tree shares one list among every prefix that ends inside the same edge. At 1M queries either fits; at 100M the difference is gigabytes.

2. "A query is in the top 5 for sn. Must it be in the top 5 for s?" Answer: no. s has more competitors: socks can push it out. The rule goes the other way: anything in s's top 5 that starts with sn must be in sn's top 5. That's why lists are built from the leaves up, not from the root down.

3. "The build ran, but one server is still showing yesterday's suggestions an hour later. Why might that be, and how would you know?" Answer: its manifest poll may be failing (permissions, network), or the new file failed its checksum on that server and it kept the old one, which is the safe behavior. The response's snapshot field and a per-server "snapshot in use" metric show it immediately; an alarm fires when any server's snapshot is older than the newest manifest by more than 30 minutes.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "1B Searches a Day, Trending Topics, Typos"

~40 min · Senior SDE (L6) · 1 region, 3 AZs + CloudFront edge · 100M queries, ~16 GB trie · 100K requests/s peak · server P99 < 10 ms · 99.99% · trending within 5 minutes

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built autocomplete for one online store: 10M searches a day, about 1M distinct queries, English only, top 5 by 30-day popularity, refreshed daily. The expensive work is offline. Once a day a Glue job reads 30 days of search logs from S3, normalizes and counts queries, and builds a radix tree where every node stores its top 5 completions, computed bottom-up from its children's lists. The snapshot, about 160 MB, goes to S3 with a manifest written last. Three suggest servers, one per AZ behind an ALB, each hold the whole trie in memory, so a request is one walk and one read: microseconds. They poll the manifest and swap in a new snapshot beside the old one. The client debounces about 100 ms, cancels stale requests and drops out-of-order answers, so a search is about 4 requests, about 1K a second at peak. About $280 a month. Open costs: a day of staleness, no typo help, no safety filtering, and everything sized for one small store."

Architecture v1, compact

Synthesizing vector architecture diagram...

Round 1 in one picture: a daily build turns logs into one file, and every server answers from its own copy in memory.

Round 1 step summary

Open costs: a day of staleness; no typo help; no safety filtering; 160 MB was easy to load and swap, and a much bigger snapshot won't be.

R2.1 The Scope Raise

Interviewer: "Now it's the autocomplete for a general web search engine. A billion searches a day. When news breaks, people search for it within minutes, and the suggestions must show it within 5 minutes. People make typos and still expect help. Some suggestions must never appear: hateful, sexual content about real people, things a court has ordered removed. 'Café' and 'cafe' are the same search. Our servers must answer in under 10 ms at P99, at 99.99%."

A scope raise is not the end of scoping. We ask back, and say what each answer changes.

Scope change

Why not 99.999%? Five nines allows 5.26 minutes of downtime a year. Autocomplete is a helper: when it fails, search still works. Paying for five nines (several regions, instant failover) buys little for a feature whose failure users barely notice. We state 99.99% for the service and keep the Round 1 promise that search never depends on it.

R2.2 What Breaks in the Round 1 Design

We fix them in this order: freshness (2.1), short prefixes at the edge (2.2), safe deploys of a big snapshot (2.3), typos (2.4), safety (2.5), normalization (2.6).

R2.3 New Requirements and API Additions

A locale parameter and a fuzzy flag

httpCopy
GET /v1/suggest?q=sytem%20des&locale=en-US&limit=5 HTTP/1.1
Host: suggest.example.com

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: private, max-age=60

{
  "prefix": "sytem des",
  "normalized": "sytem des",
  "locale": "en-US",
  "snapshot": "2026-09-27",
  "fuzzy": true,
  "suggestions": [
    { "text": "system design interview", "type": "FUZZY" },
    { "text": "system design primer", "type": "FUZZY" },
    { "text": "system design course", "type": "FUZZY" }
  ]
}

• locale selects the trie. In Round 2 there is only en-US, but putting it in the API now is free and saves a breaking change in Round 3.
• fuzzy: true tells the client the list comes from typo matching, so it can say "Did you mean…" style text instead of pretending these complete what was typed.
• Each suggestion has a type: POPULAR (from the nightly trie), TRENDING (from the fast lane) or FUZZY. The client can mark trending items, and our logs can measure each source.

An admin API for blocked terms (internal, trust-and-safety reviewers only)

httpCopy
POST /admin/v1/blocked-terms HTTP/1.1
Host: suggest-admin.internal.example.com
Authorization: Bearer <reviewer token>
Content-Type: application/json

{
  "locale": "en-US",
  "phrase": "<the phrase, as typed>",
  "match": "PHRASE",
  "reason": "HARASSMENT",
  "ticket": "TS-4412",
  "urgent": true
}

httpCopy
HTTP/1.1 201 Created
Content-Type: application/json

{ "id": "bt_01J8ZK4", "normalized": "<normalized phrase>", "list_version": 4127 }

DELETE /admin/v1/blocked-terms/{id} removes an entry; GET /admin/v1/blocked-terms?locale=en-US lists them. Every change records who made it and the ticket, and bumps list_version. urgent: true also pushes the change to the serving fleet within about a minute (step 2.5).

R2.4 Design Evolution: Fresh, Fast, Forgiving and Safe

Step 2.1: Breaking News Takes a Day to Appear

Primitive: Message Queues vs Event Streams (a stream lets both the Flink job and the log archive read the same events)

Synthesizing vector architecture diagram...

Every step waits for the one before, so the worst cases add up: about 164 s (2.7 minutes) until every edge location has it, and about 224 s (3.7 minutes) until a browser that cached the old answer (max-age=60) asks again. That leaves over a minute of the 5-minute budget for enough people to search the phrase: at 1,000 searches a minute, 300 distinct users take well under a minute.

Step 2.2: The Top 1–3 Letter Prefixes Are Most of the Traffic

Drill: The image service that made every origin server sweat (this step answers why an edge cache instead of a bigger origin: distance and bursts, not server count; step 2.5 answers how long a removed item stays visible: at most the edge TTL plus the browser's cache time, unless we invalidate it)

Step 2.3: Swapping a 16 GB Snapshot Causes Errors

Synthesizing vector architecture diagram...

A snapshot only reaches the fleet after the offline checks and a canary. The previous snapshot stays in memory for 2 hours, so rollback costs nothing but a pointer swap.

Step 2.4: "sytem des" Returns Nothing

Primitive: Circuit Breaker, Bulkhead & Fault-Tolerance Patterns · Drill: The slow recommendation service that took down checkout (this step answers both: why a slow dependency exhausts the caller's threads, and why a timeout alone isn't enough; see also "The fuzzy backend is slow" in R2.8)

Why a timeout alone isn't enough. Suppose OpenSearch slows from 10 ms to 5 seconds. With no timeout, each fuzzy request holds a server thread for 5 seconds; at 1,800 fuzzy requests a second, that's thousands of threads, and the threads serving the trie run out too: a failure of an optional feature takes down the whole service. A tight timeout (our 30 ms) caps each wait, but every request still goes to a sick backend, still costs 30 ms, and adds load while it struggles. The bulkhead caps how many threads fuzzy calls can ever hold, and the breaker stops sending them at all until a trial call succeeds. And making the timeout even tighter everywhere backfires: normal variation (a garbage-collection pause, a slow disk read) then fails healthy calls, which look like an outage and trip the breaker for no reason.

The fuzzy index

jsonCopy
{
  "settings": {
    "number_of_shards": 1,
    "number_of_replicas": 2,
    "analysis": {
      "analyzer": {
        "folded_phrase": {
          "type": "custom",
          "tokenizer": "keyword",
          "filter": ["lowercase", "asciifolding"]
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "suggest":  { "type": "completion", "analyzer": "folded_phrase" },
      "query_id": { "type": "integer" }
    }
  }
}

One shard with two replicas puts a full copy on each of the three data nodes, one per AZ. Each document looks like {"suggest": {"input": "system design interview", "weight": 98500}, "query_id": 18234}.

The fuzzy query

jsonCopy
{
  "suggest": {
    "typo": {
      "prefix": "sytem des",
      "completion": {
        "field": "suggest",
        "size": 5,
        "skip_duplicates": true,
        "fuzzy": { "fuzziness": "AUTO", "prefix_length": 1 }
      }
    }
  }
}

prefix_length: 1 requires the first character to match, which keeps the search small (people rarely mistype the first letter). The nightly build writes a new index, suggest-fuzzy-en-us-2026-09-27, and moves the alias suggest-fuzzy-en-us to it only after it has been checked: the same blue/green idea as the trie.

Step 2.5: An Offensive Phrase Is Trending

Primitives: Bloom Filters & Counting Filters · Bot Defense, Sybil Resistance & Registration Abuse · Drill: The web crawler that forgot its history (answered in "Bloom filter sizing" below)

Bloom filter sizing, and why ours is optional. For a 1% false-positive rate, a Bloom filter needs about −ln(0.01) ÷ (ln 2)² ≈ 9.6 bits per element and 9.6 × ln 2 ≈ 7 hash functions: about 1.2 MB for 1M phrases. If we keep adding phrases past the size it was built for, its bits fill up and the false-positive rate climbs (to 15% or worse). In a filter used alone, that means more and more legitimate items wrongly treated as "in the set". In ours, it only means more lookups fall through to the exact set: slower, never wrong. We rebuild the filter at the right size with every snapshot. Why not keep the exact set of phrase hashes in Redis instead? It would be exact, but it would put a network call on the path of every request for a few dozen membership checks, and our exact set fits easily in each server's memory. A Bloom filter earns its place when the exact set is too big to keep local, so the filter saves remote lookups for the "definitely not" answers.

Step 2.6: "Café" and "cafe" Are Counted Separately

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Three paths. Serving (top): short prefixes from the edge, the rest from the fleet, which merges the trie with the trending overlay and filters the result. Speed (middle): completed searches become a new overlay every minute. Batch (bottom): the same events become tomorrow's trie and fuzzy index. The two paths meet only inside the servers.

What one suggest server holds in memory

Tracing a normal keystroke: the user pauses after earthq

Synthesizing vector architecture diagram...

Six characters is past the edge's 1–3, so it goes to the region. Every step is local memory; the server's own work is well under a millisecond.

Tracing a trending term appearing

Synthesizing vector architecture diagram...

About two minutes from the first searches to the suggestion appearing everywhere, including the edge.

Tracing a typo

Synthesizing vector architecture diagram...

Only requests that find nothing locally reach OpenSearch, and at most one call per prefix is in flight per server.

R2.6 Numbers and Cost

Traffic

Trie memory (the per-node sizes are assumptions for a compact array layout; measure the real build)

Every ID fits in 4 bytes (100M < 2³² ≈ 4.3B), and so does every score: even a query searched 10M times a day reaches only 300M in 30 days.

Bandwidth

Suggest fleet

Server latency budget (trie-served requests; the steps run one after another, so they add)

The speed layer

Fuzzy fallback

Monthly cost (us-east-1 on-demand list prices; check the AWS Pricing Calculator before quoting)

The line that surprised us: CloudFront's request fee. Together with the other CloudFront lines it is about 83% of the bill (the request fee alone is 77%), and the edge doesn't save money anywhere else: serving from our fleet costs a few cents per million requests in server time ($2,815 a month ÷ ~73B origin requests ≈ $0.04 per million), and CloudFront charges $1 per million. So the edge is there for latency and bursts, not for cost, and we buy it only where it helps: the 1–3 letter prefixes whose answers every user shares. If every request went through CloudFront, requests alone would be 121.6B a month × $0.0100 per 10,000 = $121,600, and the total about $136K. At this volume, AWS offers discounted pricing for committed traffic and a Security Savings Bundle (up to 30% off with a one-year commitment); we don't count on either in the estimate. COST 5 · COST 7

Which numbers changed the design? The ~16 GB trie made us plan double memory per server and blue/green loads. The 224-second worst case of the fresh path at the user (step 2.1, including the edge's and the browser's 60-second caches) told us a 60-second TTL fits the 5-minute budget. And the per-request CDN price decided which requests go through the edge.

R2.7 Trade-Offs

Batch + speed layers vs streaming only

The streaming-only design (often called Kappa) is simpler on a diagram and harder in practice here: keeping a top 5 at 200M nodes correct under decreasing counts is exactly the problem the offline build avoids.

In-process trie vs Redis

The 41.6 GB is optimistic, for two reasons. First, a flat key-value table needs a key for every prefix a user can type, not just the ~200M radix nodes, because it has no tree to tell it that sne ends inside the edge leading to sneakers: probably several hundred million to a billion keys (an estimate). Second, Redis spends several dozen bytes of bookkeeping on each key before the data. Realistically, it's around 100 GB per copy. And ElastiCache reserves 25% of a node's memory by default for background work, so a cache.r7g.xlarge (26.32 GiB) holds about 19.7 GiB of data. The in-process trie wins here on latency and on memory. Redis would win if many different services needed the data, or if the trie were too big for one server (Round 3 shards it instead).

Edge TTL

Because CloudFront charges per request whether it hits or misses, a longer TTL doesn't lower the CDN bill; it only lowers origin load, which is small already. So we pick the TTL for freshness.

Top-k per node vs searching at request time

8 GB of memory buys constant-time answers. Ranking experiments that need a different order are Round 3's problem.

Our consistency stance. Different servers can serve different snapshots or overlays for a minute or two during swaps, and the edge can be 60 seconds behind. Suggestions are hints, so this is fine. The one thing that must be immediate is removal, which is why the blocklist is checked at serve time and pushed separately.

R2.8 Failure Modes

How the stampede drill applies here. The drill asks what happens when a cache restarts empty and the first wave all misses at once. Our servers hold no cache that starts empty (they load the whole snapshot before taking traffic), but the edge and the fuzzy-answer cache do start empty. The first wave at each edge location is collapsed into one request, Origin Shield collapses edge locations into one, and single-flight collapses concurrent fallback calls. The drill's second question, why not cache forever and skip TTLs, has a direct answer here: trending terms must appear within minutes and removed terms must disappear within minutes, so our edge answers live 60 seconds.

R2.9 Production Gotchas

1. Traversing the trie on every keystroke

• Symptom: CPU climbs with the size of the data; short prefixes are the slowest requests.
• Cause: searching the subtree and sorting on each request.
• Fix: top-k stored at every node (step 1.2), computed in the build.

2. No edge caching for short prefixes

• Symptom: far-away users see suggestions late for the first letters; bursts on one letter hit the origin directly.
• Cause: every request, including the ~18,000 shared short prefixes, crosses to the region.
• Fix: CloudFront for 1–3 letters with a 60 s TTL, request collapsing and Origin Shield (step 2.2).

3. No normalization

• Symptom: a popular query is missing from the top 5; the trie is bigger than expected.
• Cause: case, accent and width variants counted separately.
• Fix: one versioned normalization function for counting and lookup; display the most common spelling (step 2.6).

4. A Bloom filter as the final blocklist

• Symptom: some harmless suggestions never appear, and nobody knows which.
• Cause: the filter's false positives are treated as "blocked".
• Fix: confirm every Bloom hit with an exact check, or skip the filter (step 2.5).

5. One P99 for two paths

• Symptom: P99 alarms fire whenever typo traffic rises, though the trie path is fine.
• Cause: 3% of requests take the 30 ms fallback, so they own the 99th percentile.
• Fix: separate targets and alarms for trie-served and fuzzy requests (step 2.4).

R2.10 Pillar Check

Operations in detail.

R2.11 Round 2 Rubric and Follow-Ups

What a strong senior (L6) answer adds over L5

• Separates a batch layer from a speed layer, and gives the freshness budget as a sum of steps.
• Merges two sources with a common scoring unit, and makes replays harmless.
• Knows why the edge helps (latency, bursts) and what it costs (per-request fees, staleness).
• Deploys a large in-memory structure safely: validation, canary, pointer flip, rollback.
• Adds a fallback without letting it hurt the main path: budget, bulkhead, breaker, separate latency targets.
• Treats safety as a serve-time guarantee, not only a build step, and knows Bloom filters can't be the last check.
• Normalizes the same way everywhere, and versions it.

Follow-up questions

1. "Why count distinct users rather than searches for trending?" Answer: a search count measures activity, and one script can produce any amount of it. Distinct users measure how many people care. We count each pseudonymous user once per query per window, so 10,000 searches by one bot add 1. It doesn't stop many accounts, which is why we also look at network and behavior diversity.

2. "A trending item is wrong: it was a bot campaign we missed. How fast can we remove it, everywhere?" Answer: the reviewer adds a blocked-term entry marked urgent. AppConfig delivers the emergency list within about 15–30 seconds, and every server filters it from every source at serve time. The admin tool invalidates the affected short prefixes at CloudFront. The next overlay (within a minute) and next snapshot won't contain it. Browsers may hold a copy for their cache time (60 s for these answers).

3. "Why not have the client call OpenSearch directly when the list is empty?" Answer: then OpenSearch is exposed to the internet, every client needs its own budget and backoff logic, and we lose single-flight, the answer cache and the serve-time blocklist. The server is the one place where we can bound the fallback's load and filter its output.

Interview gotchas from this round's wrong answers

---

Round 3 · Architect · "Every Language, Personal, Private and Global"

~45 min · Principal (L7) · 4 regions, 3 AZs each, + edge · ~5B searches/day · 40 locales, ~98 GB of tries · server P99 < 10 ms in every region · 99.99% per region

R3.0 Where We Left Off

What the candidate says in the first 60 seconds of Round 3, and everything you need if you start here.

Round 2 in 60 seconds. "We run autocomplete for a web search engine in one region: a billion searches a day, 100K requests a second at peak, US English. A nightly Glue build turns 30 days of logs into a 16 GB radix trie with the top 5 stored at every node, validates it, canaries it, and nine r7g.2xlarge servers load it beside the old one and swap a pointer set in Parameter Store; the old copy stays two hours for rollback. A speed layer (Kinesis into a Flink job with a 10-minute sliding window over distinct users) publishes a trending overlay every minute, and servers merge it with the trie by searches per day: trending within about four minutes at the user, worst case. Prefixes of 1–3 letters are served by CloudFront with a 60-second TTL, request collapsing and Origin Shield. Typos fall back to an OpenSearch completion index with fuzzy matching, behind a 30 ms budget, a bulkhead and a circuit breaker. Every candidate is checked against an exact blocklist, with an emergency list pushed by AppConfig. One normalization function, versioned, for counting and lookup. About $63K a month, about 80% of it CloudFront. Open costs: one language, one region, nobody's personal history, raw logs full of personal data, and no way to test a new ranker safely."

Architecture v2, compact

Synthesizing vector architecture diagram...

Round 2 in one picture: the edge answers what everyone shares, each server answers the rest from memory, and two offline paths (minute-by-minute and nightly) keep that memory fresh.

Rounds 1–2 step summary

Open costs: one language and one trie on every server; no personal signal; raw logs with user IDs; one region; no safe way to compare rankers.

R3.1 The Scope Raise

Interviewer: "We're launching worldwide: 40 languages and locales, including Japanese, Chinese, Korean and Thai. About 5 billion searches a day. Suggestions should reflect your recent searches, for people who want that. Our privacy team says query logs are personal data: they need retention limits and deletion on request, and nothing personal can leak into suggestions. Users everywhere need the same speed: under 10 ms on our servers, from a region near them. And the product team wants to A/B test new rankers."

We ask back, and say what each answer changes.

Scope change

R3.2 What Breaks in the Round 2 Design

R3.3 New Requirements and API Additions

Locale detection. locale is optional now. The router picks it in this order: the locale parameter (the user's setting) → the site or app language → the Accept-Language header → the script of what was typed (hiragana means Japanese). The answer says what it chose. Requests to the edge hostname always carry a resolved locale: the client resolves it (from the user's setting, the app language, the browser language and the script typed) before sending, because locale is in the CDN cache key and Accept-Language is not. Otherwise a Japanese and an English user asking for the same short prefix would share one cached answer. (A CloudFront Function could do the same by mapping Accept-Language to a locale parameter at the edge.) The router's own detection only fills in locale for origin requests that arrive without one:

httpCopy
GET /v1/suggest?q=%E3%81%A8%E3%81%86%E3%81%8D%E3%82%87 HTTP/1.1
Host: suggest.example.com
Accept-Language: ja-JP,ja;q=0.9
X-Exp: ranker=control

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: private, max-age=60

{
  "prefix": "とうきょ",
  "locale": "ja-JP",
  "locale_source": "ACCEPT_LANGUAGE",
  "snapshot": "2026-09-27",
  "suggestions": [
    { "text": "東京 天気", "type": "POPULAR" },
    { "text": "東京駅", "type": "POPULAR" },
    { "text": "東京タワー", "type": "POPULAR" },
    { "text": "東京都", "type": "POPULAR" },
    { "text": "東京 ホテル", "type": "POPULAR" }
  ]
}

The session call: history, blend rules and experiment assignment. When the search box gets focus, a signed-in client makes one call:

httpCopy
GET /v1/session HTTP/1.1
Host: suggest.example.com
Authorization: Bearer <user token>

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: private, no-store

{
  "personalization": "ON",
  "history": [
    { "id": "h_9f2a", "text": "tokyo marathon results", "at": "2026-09-26T21:14:03Z" },
    { "id": "h_77c1", "text": "tomato soup recipe", "at": "2026-09-25T18:02:40Z" }
  ],
  "blend": { "max_history": 2, "history_first": true },
  "experiments": { "ranker": "control" }
}

Opt-out and deletion

httpCopy
PUT /v1/settings/personalization HTTP/1.1
Authorization: Bearer <user token>
Content-Type: application/json

{ "enabled": false, "delete_existing": true }

httpCopy
DELETE /v1/history HTTP/1.1
Authorization: Bearer <user token>

httpCopy
HTTP/1.1 202 Accepted
Content-Type: application/json

{ "cleared_at": "2026-09-27T10:41:07Z", "raw_logs_deleted_by": "2026-10-29" }

DELETE /v1/history/{id} removes one entry. The answer states both deadlines honestly: history is gone from suggestions now on this device and in every future session call; another device that is signed in keeps its session copy until its next session call (the next time its search box gets focus); raw logs age out by a stated date (step 3.4).

The experiment header. X-Exp: ranker=<variant> comes from the session call (or, for signed-out users, from a hash of a device cookie). The client sends it on every suggest request, and the CDN includes it in the cache key along with q and locale, so users in different variants never share a cached answer.

R3.4 Design Evolution: Languages, People, Privacy and Regions

Step 3.1: 40 Languages

Synthesizing vector architecture diagram...

For Japanese, the prefix the user sees and the prefix we look up can differ: kana typed through an input method goes straight to the reading index; Latin letters are converted to kana first, and also tried against English.

Step 3.2: The Trie Is Too Big for One Server in Big Locales

Primitive: Database Sharding & Partition Keys · Drill: The search bar that stalled on every keystroke (answered in step 1.2 and R1.8)

Step 3.3: Show My Own Recent Searches First

The history item

The session call is a Query on user_id, newest first, Limit 50: about 7.5 KB, one read request unit with eventually consistent reads.

Step 3.4: Query Logs Are Personal Data

Synthesizing vector architecture diagram...

Personal data never leaves the region and never lives past 30 days in the pipeline. What crosses the boundary is a count per query that at least 50 people searched. History is a separate store the user controls.

Step 3.5: Users Are Far From Our Region

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active

Step 3.6: Test a New Ranker Safely

Round 3 Step Summary

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Users reach the nearest healthy region. Counts flow in to one build (no identifiers), and snapshots flow back out to every region.

Synthesizing vector architecture diagram...

Inside one region: routers do everything that doesn't need a trie, and each shard server holds one shard's trie. The overlay now lives in the routers, because it is small and every request needs it.

Tracing a Japanese query (a user in Osaka types とうきょ: four characters, so it goes to the region, not the edge; the 1–3 rule counts characters as they are in the box, kana included)

Synthesizing vector architecture diagram...

The user typed kana; the answer is in kanji, because the reading index maps one to the other.

Tracing a personalized result

Synthesizing vector architecture diagram...

One history read per session. Every keystroke after that is a shared, cacheable request, blended on the device.

Tracing a deletion request

Synthesizing vector architecture diagram...

History disappears from suggestions at once on this device, and on the user's other devices at their next session call. Raw logs age out by their stated date; aggregates never held the user's ID.

R3.6 Numbers and Cost

Traffic by region (shares from R3.1; 2.2× local daily peak; 40% of requests served by the edge)

Memory per locale (160 B per query = Round 2's 16 GB ÷ 100M; reading indexes add ~2 nodes × 70 B = 140 B per query; all assumptions)

Shards (each ≤ 24 GB, so a 64 GiB r7g.2xlarge holds it plus a swap copy: 48 GB + the process)

Shard servers per region. Same rule as Round 2: a server's planned maximum is 10K requests/s (50% CPU), and a shard must survive losing an AZ, so it needs load ÷ 10K servers in two AZs, with at least one per AZ. Worked for us-east-1 (English is 75% of its origin traffic, split evenly by the load-based boundary):

99 shard servers worldwide. Of them, 21 × 4 = 84 would exist even with almost no traffic: 7 shards × 3 AZs in each region. That's the fixed cost of holding every locale everywhere.

Routers. Same planned maximum, 10K/s per c7g.2xlarge, sized for an AZ loss: us-east-1 91,667 ÷ 10K → 10 needed in two AZs → 15; eu-west-1 and ap-northeast-1 76,389 → 8 → 12 each; ap-southeast-1 61,111 → 7 → 12 (9 would leave only 60K after an AZ loss). 51 routers.

Server latency budget (measured at the router, P99; parallel steps take the maximum, dependent steps add)

If a shard call hasn't answered after about its P95 (2 ms), the router sends the same call to another server of that shard and takes the first answer. A typical hedged request costs 0.3 + (2 + 1) + 0.3 + 2 + 2 = 7.6 ms, the same as the budget. This isn't a hard worst case (if the second call also hits its own P99 tail, the request can pass 10 ms); hedging makes that tail much rarer, which is all a P99 target needs. Romaji's five kana lookups go to one shard in one call. The history read is not in this budget at all: it happens once per session, before typing.

Personalization store

Snapshot replication: ~98 GB a night × 3 destination regions = 294 GB a day × 30.4 × $0.02/GB inter-region transfer ≈ $179 a month. The data is small next to the serving fleet; the reason to replicate is load speed and independence, not cost.

Monthly cost (us-east-1 list prices for every region, so real costs in the other regions are somewhat higher; check the AWS Pricing Calculator before quoting)

That's about $0.67 per million suggest requests (608B requests a month), of which $0.48 is CloudFront's request fee. The design's own machinery (shards, routers, pipelines, fuzzy clusters) is about $60K. At this volume, the CDN contract matters more than any server choice. COST 1

Which numbers changed the design? English's 32 GB, not the 98 GB total, forced sharding. The minimum of 3 servers per shard per region made us pack small locales together (30 shards of 0.48 GB would need 90 servers per region). The per-keystroke history read ($15K a month and no edge caching) moved history to once per session. And the CDN's per-request price is again the biggest line.

R3.7 Trade-Offs

Personalization vs latency

Privacy threshold vs coverage

Shard layouts

Central build vs a build per region

A per-region trie is a reasonable later step for locales whose regions search very differently (English in India vs the US). We'd start central, because it's one pipeline to operate.

Closing the loop. The question was: how do we answer every keystroke in milliseconds with the best, freshest and safest completions?

• Milliseconds: everything expensive is precomputed. The answer for any prefix is one walk and one read, in memory, on a server in the user's region, or already cached at the edge.
• Best: popularity counted over 30 days, normalized per locale, blended with your own history, and improved only by experiments that prove it.
• Freshest: a nightly build for what's popular, a minute-by-minute overlay for what's trending, and a 60-second edge TTL that fits inside the 5-minute budget.
• Safest: filtered at build time and checked exactly at serve time, with an emergency push; manipulation met with distinct-user and source checks; and privacy built into the pipeline: aggregate early, threshold, and keep identifiers local and short-lived.

R3.8 Failure Modes

R3.9 Runbook

Golden signals, per region and per locale OPS 8 · REL 6

Procedure: snapshot cutover for one shard in one region

1. Confirm the replicated manifest and files are present, and checksums match.
2. Load the new snapshot on one canary server per AZ beside the current one; compare latency and empty-answer rate on replayed traffic for 10 minutes.
3. Set the shard's pointer parameter; servers load and swap a few at a time.
4. Watch P99, empty-answer rate and blocked-candidate rate for that shard for 30 minutes.

Procedure: rollback (within 2 hours of a flip)

1. Set the shard's pointer back to the previous version. Servers swap back at their next poll (≤ 30 s), with no loading.
2. After 2 hours the old copy is freed; rolling back further means a normal cutover of an older snapshot.

Checked CLI commands, in order: see which snapshot each shard in Tokyo serves; roll the G3 shard back; push an urgent blocklist version to one region; remove two cached short-prefix answers from the edge; confirm a replicated manifest arrived (the response shows ReplicationStatus: REPLICA).

textCopy
aws ssm get-parameters-by-path --path /suggest/prod/snapshot --recursive --region ap-northeast-1
aws ssm put-parameter --name /suggest/prod/snapshot/g3 --value 2026-09-26 --type String --overwrite --region ap-northeast-1
aws appconfig start-deployment --application-id a1b2c3d --environment-id e4f5g6h --configuration-profile-id p7q8r9s --configuration-version 4128 --deployment-strategy-id AppConfig.AllAtOnce --region eu-west-1
aws cloudfront create-invalidation --distribution-id E2EXAMPLE1 --paths "/v1/suggest?q=ba&locale=en-US" "/v1/suggest?q=bad&locale=en-US"
aws s3api head-object --bucket suggest-snapshots-apne1 --key g3/2026-09-27/manifest.json --region ap-northeast-1

For the invalidation, the client always sends q before locale, so the path we invalidate is exactly the path that was cached.

Game days. Monthly: fail a region's health checks on purpose during business hours and watch the neighbors absorb it; flip a canary to a deliberately broken snapshot and check validation stops it. Quarterly: run a history deletion end to end and check nothing of the user's appears anywhere afterwards. REL 12

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Treats "a language" as a normalization, an input method and a data set, not a translation.
• Shards for fit and blast radius, knows it isn't cheaper, and packs cold data to avoid per-shard minimums.
• Keeps personalization off the hot path, and says what staleness that costs.
• Builds privacy into the data flow: short-lived identifiers, in-region raw data, thresholds, honest deletion deadlines, and knows TTL-style deletion isn't a deadline.
• Runs regions from one build with independent flips, and plans for a neighbor's traffic.
• Makes ranking changes prove themselves, with guardrails that act on their own.
• Knows which line dominates the bill and what moves it.

Follow-up questions

1. "Cut the bill by 30%." Answer: 30% of ≈ $407K is about $122K, and $292K of the bill is CloudFront requests, so the lever is request count, not servers or hit ratio (CloudFront charges per request whether it hits or misses). If about one request in four is a single letter (an assumption), dropping the one-letter request and showing history plus a per-locale "popular now" list on focus instead (one cacheable request per session, about 2B a day) takes edge requests from 8B to about 5B a day: roughly 3/8 of $292K, about $110K saved. A committed-use deal (the Security Savings Bundle is up to 30% on CloudFront, or custom pricing for committed volume) covers the rest.

2. "A user in Germany deletes their history, then flies to Tokyo. Can they still see a deleted search?" Answer: no. History lives only in their home region (eu-west-1). In Tokyo, the session call is forwarded there, and it filters on cleared_at, so even an item written in the same second as the delete isn't shown. Their raw search events from Germany age out of eu-west-1's logs within 30 days; the ones they make in Tokyo stay in ap-northeast-1's logs under the same rule. Aggregates never held their ID.

3. "Why not a DynamoDB global table for history, so every region has it?" Answer: it would put every user's personal history in all four regions, which the privacy team ruled out, and it would multiply write costs by the number of replicas. One cross-region read per session, off the keystroke path, is a better price for travelers.

Interview gotchas from this round's wrong answers

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening a round: "Before I design, let me ask a few scoping questions."
• When the scope is raised: "Here's what breaks in the current design, and here's the order I'll fix it in."

And the one idea for this system: "Everything expensive happens offline; a keystroke is one walk and one read."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels