Design search autocomplete

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

We assume about 8.64 million daily users at launch, at 5 searches per user a day: 43.2 million searches a day.

43,200,000 / 86,400 = 500 searches a second on average. The evening peak is twice that, our assumption: 1,000.

Later we grow 10 times, to 86.4 million daily users: 5,000 searches a second on average, 10,000 at the peak.

A search is about 20 keystrokes, counting corrections, our upper-side estimate. Twenty keystrokes are not twenty requests.

The client waits for a pause before it asks, so about 1 keystroke in 4 sends. Its own cache answers about 1 request in 5.

20 x 1/4 x 4/5 = 4 suggest requests per search. At the 10,000 peak that is 40,000 requests a second.

Check in: Close the page and derive 40,000 suggest requests a second at the peak.

From keystroke to request

The client, not the server, decides how many requests a search costs. That makes it the first thing to design.

Debounce: the client sends only after a pause in typing. It waits about one and a half times the user's own median gap between keys.

That is about 400 ms on a keyboard, where people type about 230 to 300 ms a key. It is about 550 ms on a phone, where they type slower.

About 1 keystroke in 4 sends on either, our estimate.

The price is stated up front: suggestions appear about 0.4 to 0.5 seconds after the user stops typing, about 0.6 seconds on a phone.

Cached locally: the client answers a prefix it already has, as after a backspace. Answers carry a 5-minute cache lifetime.

Sent: each request carries a sequence number. Shown: the client drops any answer older than the newest it has shown, so answers never flicker.

Large search engines take the other side: a request on every keystroke, with fast servers and reuse on the device.

Step through the figure to follow 20 keystrokes down to 4 requests.

The trade-off:

Half a second of waiting is the price of a quarter of the load. It is a choice, and the interviewer will ask you to defend it.

Twenty keystrokes, four requests

1. A search takes about 20 keystrokes, counting corrections. Sending each one would be 20 requests.
2. The client waits about one and a half times the user's own gap between keys. That is about 400 ms on a keyboard, 550 ms on a phone. About 1 keystroke in 4 sends.
3. The client's own cache answers about 1 request in 5, such as after a backspace. That leaves 4 requests a search.
4. Each request carries a sequence number. An answer older than the newest shown is dropped, so suggestions never flicker.
5. The price: suggestions appear about 0.4 to 0.5 seconds after the user stops typing, about 0.6 on a phone. The server is the smallest part.

Check in: Why a pause of about 400 ms on a keyboard, and not 150 ms?

Every suggest request queries the database

The simplest answer is a table of past queries and their counts, refreshed nightly, with the top 10 computed on every request.

Each request runs WHERE query LIKE 'pre%' ORDER BY count DESC LIMIT 10 on an Aurora reader, using an index on the normalised query.

The index finds the matches, but the sort must read all of them. We assume 5 ms of reader CPU a query.

A reader's 8 vCPUs each give 1,000 ms of CPU a second. At 5 ms a query that is 8 x 1,000 / 5 = 1,600 queries a second.

A stateless suggest service runs it, at about 1 ms of CPU a request. At 1,000 searches a second it gets 1,000 x 4 = 4,000 requests.

The fleet adds tasks to keep each near 70% busy, our target, leaving room for a spike while new tasks start. 4,000 / (1,000 x 0.7) = 5.7, so 6 tasks, 66.7%.

The database: 4,000 / (1,600 x 0.7) = 3.6, so 4 readers, 62.5%.

Read the four tiles. Here the load buttons count searches a second. "First to saturate" notes the Suggest service, at 67%.

A part saturates when it gets more work than it can serve. A card turns red at 90% of its limit; only past 100% does the result name it.

The latency tile shows 8ms: load balancer 1.5 + service 1 + database 5 = 7.5 ms. The cost tile shows $5,155/mo.

Of that, $613.92 is data out to the internet, called egress: 4,000 answers a second of about 0.7 KB each.

AWS bills egress per GB, with the first 100 GB a month free. The price per GB falls as the volume grows.

The search log is async: no user waits on it, so it is off the latency path.

Press 500, the average hour. Nothing saturates.

Press 2,000. The Query counts database saturates: 8,000 queries against 6,400, so the wall is 1,600 searches a second.

The tile shows "≥ 23ms". A saturated node shows a slower answer; really, work past capacity queues until it times out, unless something sheds it first.

The trade-off:

Computing the top 10 at request time works while the table is small and the rate low.

Stage 1: Every suggest request queries the database

• Load: 1,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $5,155/mo

Check in: Why is a one-letter prefix the expensive one?

The same design, ten times the users

The interviewer asks: We grow ten times. What breaks?

Stage 2 runs Stage 1's design at 10,000 searches a second: 40,000 queries.

Aurora allows up to 15 readers in a cluster: 15 x 1,600 = 24,000 queries a second, against 40,000.

The Query counts database saturates. Its warning reads "Readers 167% used: 40,000 reads/s against 24,000 across 15 readers".

The tile shows "≥ 23ms". Past the readers' capacity, queries queue. Each waits longer, until statements time out or the connection pools run out.

Then the suggest service returns errors. With load shedding in front, at best two requests in five fail fast; without it, fewer than 24,000 finish in time.

The cost tile shows $25k/mo.

Ten times the users do not bring ten times the distinct queries: new text grows more slowly than volume, which is Heaps' law.

But the queries that pass the admission rule grow faster, as more cross the 5-user threshold. We take about 2M at launch and about 20M after growth, our estimate.

So a short prefix sorts several times the rows, and the drawn 5 ms is the launch figure.

Bigger readers would carry today's 5 ms, for about $30,000 a month of instances. But the work per query keeps rising with the data.

Press 5,000, the average hour. Nothing saturates, but the database reads 83% and warns, and the tile shows 14ms.

That 14ms is the simulator's queue curve. An 8-vCPU reader at 83% adds a few milliseconds of queueing, our estimate: a many-core database queues far less than one server.

The trade-off:

The work per request grows with the data, and readers stop at 15. Move the work out of the request.

Stage 2: The same design, ten times the users

• Load: 10,000 req/sec
• First to saturate: Query counts database
• Estimated cost: $25k/mo

• Latency past saturation is a lower bound, not an estimate. Query counts database is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Query counts database: Readers 167% used: 40,000 reads/s against 24,000 across 15 readers (the writer takes no reads while readers exist).

Check in: Why not buy bigger readers?

A trie, flattened into one key a prefix

Every request recomputes an answer that changes once a day. Compute it once, ahead of time, instead.

A prefix is the start of a query, such as "wea" for "weather". A trie is a tree of prefixes, one letter a step.

The top-k at a prefix are its k most popular completions. Here k is 10, cached at every node of the trie.

Flattened, that is one key a prefix: look up the prefix and read its top 10. A request is one key read.

The keys live in a suggestion store on Valkey, an open-source, Redis-compatible store run by ElastiCache.

A key looks like s:{locale:prefix}, for prefixes of 1 to 20 characters. 20 million kept queries of about 20 characters have 400 million prefixes.

Counting each shared prefix once leaves about 150 million, because past about 8 characters most prefixes belong to one or two queries, our estimate.

About 85% of keys are long prefixes with one to three completions, about 155 bytes each, with the store's own overhead of about 70.

The 15% short prefixes hold a full list of 10, about 350 bytes. 0.85 x 155 + 0.15 x 350 = about 185 bytes a key.

150,000,000 x 185 B = 25.8 GiB. The keys are split over 3 shards, each a slice of the keys on its own cache.r7g.xlarge node, with one replica each.

They give 59.2 GiB usable at AWS's default 25% reserve: 44% used. Two copies would not fit comfortably, so one is overwritten in place each day.

Step through the figure to see a trie become keys.

The trade-off:

The store costs memory and a daily build. In exchange, a request does no sorting at all.

A trie, flattened into one key a prefix

1. A trie is a tree of prefixes, one letter a step. Here each node also keeps its top 10 completions, worked out ahead of time.
2. Flatten it: one key per prefix, whose value is that prefix's top 10. A request reads one key.
3. About 150 million keys at about 185 bytes is 25.8 GiB, 44% of what 3 shards can hold at AWS's default reserve.
4. Each day a loader overwrites the keys in place, in about 200 seconds. Two copies would not fit comfortably, so there is one.

Check in: What do you size the store by?

Other places to keep the top 10

The precompute is the lesson. The store's technology is secondary, and an interviewer may ask what else would work.

DynamoDB, provisioned: about $1,970 a month at the peak, a third dearer than the store's about $1,500, and about $1,440 at the average, a tie.

That includes loading by a daily import from S3 into a new table, about $90 a month, which uses no write capacity.

Loading by writes instead would be 150 million a day, 4.5 billion a month. That is $2,812.50 on demand at today's rate, which is why the design imports.

The store also wins on latency: under a millisecond, against single digits.

In the service's own memory: a compact automaton of 20 million queries is about 1 GB, our estimate. Bigger tasks cost about $370 more, less than the store.

Its costs are a daily reload on every task, cold starts, and memory that grows with the fleet. It is defensible; we draw the store because it updates one copy.

An Aurora prefix table, one key lookup a request: about $3,000 of instances, dearer and slower than the store.

A CDN in front, at list price: about $54,600 a month, against the drawn origin's $8,357 at the average, egress included. Rejected.

The trade-off:

Each choice trades cost against latency and operations. Say which one you would pick, and why.

Check in: Why not put a CDN in front of the suggest service?

The daily build

The store is only as good as the counts behind it. Who decides what is popular, and how often?

Every search is logged once. A daily job rolls each day up into (query, count, a HyperLogLog of users), a small sketch that counts distinct users.

The build merges the last 28 rollups, weighting each day by 0.9 per day of age.

A query is admitted only after at least 5 different users, and at least 20 searches in all, so no one person's text is suggested.

A classifier then drops personal data such as phone numbers and emails, since a leaked number can pass a count threshold.

Each admitted query adds itself to every prefix up to 20 characters; each prefix keeps its top 10. Our upper estimate: $264 a month.

A loader overwrites the live store in place, about 200 seconds. Prefixes that dropped out are deleted. Rollback is a reload of yesterday's files.

An established query scores about 9.5 times its daily count, so a new one wins a short prefix only through trending, described later.

The trade-off:

Daily is cheap and simple. In exchange, a new query waits up to a day, except through trending.

Check in: How does the build keep any one person's text out of suggestions?

Run the precomputed store

Stage 3 puts the suggestion store on the read path at 10,000 searches a second.

The service: 40,000 / 700 = 57.1, so 58 tasks, 69.0%. "First to saturate" notes the Suggest service, at 69%.

The store takes 40,000 key reads. The store's card shows 3.8%; we size it by memory and network instead.

The search log takes 2,000 KB a second on 3 shards that hold 3,072: 65.1%.

The latency tile shows 3ms: load balancer 1.5 + service 1 + store 0.2 = 2.7 ms. The tile leaves out the typing pause and the network round trip.

The cost tile shows $15k/mo, against Stage 2's $25k that could not carry the load.

Press 5,000, the average hour. Nothing saturates, and the cost tile shows $8,357/mo.

Press 17,400, a heavy news day. The Search log saturates, and the latency tile stays 3ms.

The log is async: no user waits on it. A saturated log loses counts and trends for that hour, not searches.

The log is the first wall, at 3,072 / 0.2 = 15,360 searches a second.

The trade-off:

Precompute what every request would compute. Then size each part by its own unit: requests at the service, memory at the store, bytes at the log.

Stage 3: The top 10 for every prefix, precomputed

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $15k/mo

Check in: Why does the latency tile not move when the log saturates?

The search log, packed into shards

The log counts searches, not requests. Its limit is bytes, and how the producer packs them decides whether bytes bind.

The log is a Kinesis stream. Each of its shards takes at most 1,000 records or 1 MiB a second, enforced each second.

The KPL, the Kinesis Producer Library, packs many log entries into one record, so the record limit stays far away.

The search front end runs on at most about 50 hosts, and each buffers entries for up to half a second.

So packing = searches x 0.5 / (50 x shards). At the 10,000 peak on 3 shards that is 33.3 entries a record.

An entry is about 191 bytes of compact JSON. With the KPL's framing it is about 202 bytes on the shard, drawn as 0.2 KB, 204.8 B.

The card counts records: about 10 entries packed in each 2 KB record. So the edge carries 0.1 record a search, and each search is 0.2 KB.

KB here is 1,024 bytes, as on the card. Bytes bind once a record holds 6 or more searches.

A partition key picks a shard by hash. We use a constant short key plus an explicit hash key that each producer round-robins over the shards.

So every shard gets the same load. A random key per entry would add about 20 bytes. Hashed keys from a small set put uneven load on the shards, which the card cannot show.

The card warns over 70%. AWS publishes no such line; the real reason for headroom is that limits are enforced each second, and retries add load.

Step through the figure to follow entries into shards, then into the daily build.

The trade-off:

A packing producer adds up to half a second before an entry lands. No user waits for it, so the wait is free.

Searches into shards, then into tomorrow's store

1. Every search writes one log entry of about 191 bytes. The producer buffers entries for up to half a second.
2. It packs many entries into one record, so a shard's 1,000-record limit stays far away and bytes become the limit.
3. An explicit hash key sends each record to the next shard in turn, so every shard gets the same load.
4. The log is archived, rolled up daily, and the build turns 28 days of counts into tomorrow's store.

Check in: Why does the producer pack entries into records?

Trends, languages, filtering and privacy

A daily build cannot catch a story breaking now, and one locale is not a product. The interviewer will push on both.

Trending: a streaming counter on the same log compares 5-minute counts with the 28-day baseline. It writes a small overlay key a prefix, about $330 a month.

Languages: the locale is in the key. Prefixes are normalised for matching, with locale-aware case folding, and the original text is shown.

Offensive text is removed at build. Urgent removals use a denylist in every task, refreshed every minute.

They reach every screen within about 6 minutes: up to a minute for the denylist refresh, then up to 5 for answers already cached.

Typing errors: when a prefix has few or no completions, the service asks a second index for candidates within one or two edits. It shows them as "did you mean".

Personalisation: recent searches stay on the device and merge there, so server answers stay the same for everyone and cacheable.

Hot keys: the store hashes keys over 16,384 slots, so no shard holds "all of s". Each task keeps the 1,400 or so one- and two-letter prefixes in memory.

A store node fails: plan for under a minute without suggestions on that shard's keys. That covers detection, the replica's promotion, which AWS says typically takes a few seconds, and the client's refresh.

A lost store answers no suggestions until reloaded; search still works.

Going global is a copy per region. From India or Australia to us-east-1 the round trip alone is about 200 ms.

The trade-off:

Each of these is a small part with its own failure. Suggestions are optional, so each one fails open.

Check in: A story breaks at noon. How do its queries reach suggestions before tomorrow's build?

The whole design on one screen

Skip on a first read; come back before the interview. Every number on Stage 3 comes from the one before it, at the 10,000 peak.

Searches: 86.4 million users x 5 / 86,400, then x 2 at the peak: 10,000 a second.

Suggest requests: 10,000 x 20 x 1/4 x 4/5 = 40,000 a second.

Load balancer: $5,545.80 on the card.

Service tasks: 40,000 / 700 = 57.1, so 58, $2,061.69.

Store reads: 40,000, on 3 shards and 3 replicas, $1,510.27; memory 25.8 of 59.2 GiB.

Log bytes: 10,000 x 0.2 KB = 2,000 KB a second, on 3 shards at 65.1%, $68.69.

Answers to users: 40,000 x 0.7 KB a second x 2,592,000 seconds = 69,214 GiB a month, which AWS bills as GB.

Egress, with the first 100 GB free: $0.09 a GB to 10,340 GB, $0.085 to 51,300, then $0.07. That is $5,657.17.

Total: $14,843.62 a month at the peak; $8,356.95 at the average.

Check in: Close the page and rebuild the chain from 10,000 searches to the log's utilisation.

The new app asks on every keystroke

The interviewer asks: The new mobile app ships. What happens?

The app sends a request on every keystroke and keeps no cache: 20 a search. Stage 4 has no load buttons, as the mix is a launch-week figure.

Drawn at the worst case for launch week, half of all searches go through the app. That is 0.5 x 4 + 0.5 x 20 = 12 requests per search.

That is 120,000 requests a second. At its 110-task ceiling, our cost guard, the fleet can serve about 110,000.

The Suggest service saturates. Its warning reads "Scaled to the 110-task ceiling and 100% used at 120000 RPS"; here it counts requests.

The tile shows "≥ 6ms", a slower answer. Really, nothing sheds the rest, so requests queue on every task: answers slow down, and the load balancer times some out.

Busy tasks start failing health checks, which takes them out of service and makes it worse.

At least a twelfth of the demand, 10,000 requests a second, cannot be served; in practice more fails, because queued requests time out.

Both apps share the fleet, so web users see it too. The app's missing pause becomes everyone's problem.

The fleet reaches its ceiling within minutes and stays there until the app is fixed: days, with app review. Each scaling step takes minutes, so every surge starts worse.

The cost tile shows $36k/mo against Stage 3's $15k, with no new searches. The fleet, the load balancer as the card bills it, and egress all follow requests. The log did not move: it counts searches, not requests.

The trade-off:

One client's missing pause triples the load on everyone. The request rate is set in the client.

Stage 4: The new app asks on every keystroke

• Load: 10,000 req/sec
• First to saturate: Suggest service
• Estimated cost: $36k/mo

• Latency past saturation is a lower bound, not an estimate. Suggest service is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Suggest service: Scaled to the 110-task ceiling and 100% used at 120000 RPS.

Check in: Why did the web get slower when the app shipped?

Finish the job on the device

The fix belongs in the client. It can do more than pause: it can stop asking once it already holds the full answer.

Every answer carries a complete flag when the prefix has fewer than 10 completions.

Then every longer prefix is a filter of that answer, since its completions are a subset. The device filters, and sends nothing.

With the pause, a search's 4 requests fall at about 5, 10, 15 and 20 characters.

The third is skipped when the 10-character answer was complete, about 40% of searches; the fourth when the 15-character one was, about 60%.

So 4 - 0.4 - 0.6 = 3 requests per search, our estimates.

Past 20 characters, a complete answer is filtered on the device. Otherwise the service filters its top 10 by the full text and labels it approximate.

Step through the figure to follow one search being finished on the device.

The trade-off:

The flag is one bit the build already knows. A request saved in the client costs nothing; one served costs a task and a read.

Finished on the device

1. With a 400 ms pause, a search's 4 requests fall at about 5, 10, 15 and 20 characters.
2. An answer with fewer than 10 completions is marked complete. Every longer prefix is a filter of it, so the device answers.
3. Skipping the third request on about 40% of searches and the fourth on about 60% leaves 3 requests a search.

Check in: Why is the complete flag exact?

Fixed in the client, and isolated on the server

The app's fix ships: the adaptive pause, the cache, and the complete flag in both clients. On a phone, suggestions show about 0.6 s after typing stops.

App store review takes days. Meanwhile, raising the ceiling to 172 tasks would hold the load for about $6,100 a month of tasks.

Old app versions keep sending for weeks, as users update slowly. Remote config helps only if the buggy build already shipped the hook.

So isolation by version header is permanent. Every app version gets its own target group and a request limit, and the web never shares a fleet with an app build.

Past a concurrency limit, the service answers an empty list at once, as suggestions are optional.

Requests fall to 3 per search: 30,000 a second. Nothing saturates; the note names the Suggest service, at 70%.

The latency tile shows 3ms. The cost tile shows $12k/mo, less than Stage 3's $15k.

On the card the load balancer falls with requests; billed by connections, it follows searches and barely moves.

Press 5,000, the average hour. Nothing saturates, and the cost tile shows $6,682/mo.

The trade-off:

Fix the rate in the client, and isolate one client from another on the server. Either alone leaves a gap.

Stage 5: Fixed in the client, and isolated on the server

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $12k/mo

Check in: The app's fix is stuck in store review. What do you do today?

The real monthly bill

Skip on a first read; come back before the interview. The cost tile holds the peak all month, so this bill is the average month.

Stage 3 at 5,000 searches a second is $8,356.95 on the canvas; Stage 5 is $6,681.53. That is 12.96 billion searches a month: $0.64 and $0.52 per million.

The card bills the load balancer per request. Billed at about one new connection a search, the months are $6,744.15 and $5,759.93: $0.52 and $0.44 per million.

Internet egress on the 0.7 KB answers is in those totals: $2,984.29 on Stage 3 and $2,248.89 on Stage 5.

Compressed to about 0.4 KB, it would be about $1,724 and $1,303.

Not drawn: the Firehose archive, planned at about $1,792, and the raw log in S3 for 28 days, about $49.

Not drawn: the daily build at most $264, and the trending counter about $330.

The trade-off:

Egress is over a third of Stage 3's average month: $2,984.29 of $8,356.95.

The archive, the raw log, the build and trending add about $2,435 by hand, about 29% more. The tile is a floor.

Check in: What does a million searches cost, and what is missing from the tile?

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

A service task dies: its in-flight requests fail, and the client asks again on the next pause.

A store primary fails: under a minute without suggestions on its keys, then the replica serves. The whole store is lost: no suggestions until a reload; search still works.

The daily build fails: yesterday's store keeps serving, a day staler.

The log is under-sized: the producer buffers, then drops log records rather than block a search. That hour's counts and trends are lost.

Say it out loud: "A trie with the top ten at every node, flattened into one key a prefix, rebuilt daily. The client sets the rate."

Minutes 0 to 5: requirements. Suggestions optional, search not; privacy; North America.

Minutes 5 to 10: the numbers. Searches, keystrokes, requests from 20 down to 4, and the pause it costs.

Minutes 10 to 18: Stages 1 and 2. The top 10 at request time, and why it breaks.

Minutes 18 to 27: Stage 3. The flattened trie, the daily build, the admission rule.

Minutes 27 to 33: sizing. Memory for the store, with the per-key working; bytes for the log.

Minutes 33 to 39: Stages 4 and 5. The client sets the rate, the complete flag, isolation.

Minutes 39 to 45: trending, languages, filtering, a CDN and why not, going global.

The trade-off:

Each answer has a price. A store, a daily build and a log are more to run than a table, and they turn a sort per request into one read.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.