A shop's search box should suggest completions while the user types: after ipho it shows iphone 15, iphone case, iphone charger. Every keystroke is a request, so suggestions are read far more often than anything else and must feel instant. The ten best completions of a prefix are the ones searched most often recently; they change slowly, so they can be computed ahead of time.
Functional requirements
Suggest: the search box sends GET /suggest?q=<prefix> and gets the top ten completions of the prefix. Model it with two scenarios:
"Edge hit": the prefix is popular and the CDN (a real CDN, not a load balancer) answers from its cache (suggestions may be up to 5 minutes old).
"Edge miss": the CDN passes the request on and the top ten are read from the precomputed suggestion index, kept in memory.
Search: the user submits a query and gets results from the search cluster. Every query is appended to a query log for the index to learn from; logging must never slow a search down, so the API does not wait for the log.
Rebuild index: every 15 minutes the scheduler starts a rebuild (its first step is sent by scheduler), which reads the recent queries from the query log, counts them per prefix and writes the new top ten of every prefix into the suggestion index.
Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
Suggestions: 100k rps at peak; 80% of them are for popular prefixes the CDN can cache.
Searches: 2k rps.
About 5 million distinct prefixes with ten completions each: a few GB, small enough to keep in memory.
Constraints
p99 of a suggestion under 50 ms; of a search under 300 ms.
Suggestions available 99.95% of the time.
The search cluster is sized for searches only (about 9k rps); suggestions must never reach it, nor any database.
Losing any single machine must not take either use case down.
At most $5,500 / month, the search cluster and the scheduler included.
What is given
problem.proschi declares the user, the existing search cluster search (three Elasticsearch nodes) and the scheduler that starts the rebuild, and holds the traffic, requirements and tests. Add the suggestion path, the query log, the index builder, the connections and the three use cases.
How your design is checked
You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.
You are building the suggestion box of a shop's search bar. The user types i, ip, iph, ipho, and after each keystroke the box shows the ten most popular completions: iphone 15, iphone case, iphone charger. Every keystroke is a request, so suggestions are by far the most frequent call, and they must feel instant: a list that arrives after the next letter is useless.
There are three use cases:
Suggest: GET /suggest?q=<prefix> returns the top ten completions. In "Edge hit" the CDN already holds the answer and replies itself. In "Edge miss" the CDN forwards the request to your servers, which read the precomputed top ten from an in-memory store.
Search: the user submits a full query and gets results from the existing search cluster. Every query is also appended to a query log (tomorrow's suggestions are learned from today's searches), and logging must never slow a search down.
Rebuild index: every 15 minutes a scheduler starts a batch job that reads recent queries from the log, counts them per prefix and writes each prefix's new top ten into the suggestion store.
The non-functional requirements: 100k suggestion requests per second at peak, a p99 under 50 ms (99% of requests finish within 50 ms), 99.95% availability, survival of any single machine failure, and a hard budget of $5,500 a month.
What is given.given.proschi fixes the user, the existing search cluster (three Elasticsearch nodes, about 9k rps in the simulation, sized for searches, not keystrokes) and the scheduler (an EventBridge rule) that kicks off the rebuild. You design around them.
What the tests check, in plain words:
Suggestions never touch the search cluster or any database: a prefix lookup must not be a search.
Suggestions go to a real CDN first and only then to a cache. The hit scenario never reaches a service; the miss scenario reads the cache.
A search calls the search cluster and writes to a queue, but never waits for the queue before answering.
The rebuild starts at the scheduler, reads the queue before writing the cache, and never queries the search cluster.
The requirements add p99, availability, failure survival and cost.
The search cluster is out. Serving keystrokes from Elasticsearch needs over 30 search nodes at 100% utilisation: at $400 a node, about $13,600 a month, more than twice the budget.
The data fits in memory. A Redis replica takes about 100k operations a second in the simulation, so the 20k edge misses use a fifth of one. Two replicas are for failure, not load.
The servers behind the CDN are sized for 20k rps, not 100k. A service replica handles about 2k rps, so the Suggest Service needs at least 10 replicas just to avoid saturation, and more to keep queueing small.
Deep dive How the simulation sees it
Utilisation is load ÷ (replicas × per-replica capacity). Latency is base latency plus M/M/c queueing delay: a pool at 50% barely queues, at 90% it roughly triples. An idle hop's p99 is about 2.8× its mean.
The miss path is CDN (5 ms) + load balancer (2 ms) + service (10 ms) + Redis (1 ms): about 18 ms of base latency, so its own p99 is already near 50 ms. The use case's p99 mixes 80% hits with 20% misses, which pulls it well below that, but only if the service is not queueing. Keep the service about half busy, as the hints suggest.
Budget. The search cluster ($1,200) and scheduler ($200) leave about $4,100. Services cost $100 per replica, Redis $150, a CDN replica $100, Kafka $200. Without the CDN, 100k rps at a sane utilisation needs about 100 service replicas: $10,000 for one tier.
Availability. A node is up when any replica is, so two replicas of everything on the suggestion path clear 99.95%; one replica is a single point of failure and fails survive any node failure.
A trie (prefix tree) stores strings by their characters: the root has a child per first letter, each child a child per second letter, and so on. Every node is a prefix, so finding all strings starting with ipho means walking four edges, then visiting the subtree below.
That subtree is the problem: under i there may be millions of queries, far too many to collect and sort on every keystroke. The classic fix is to store the answer at each node: its own top k completions, ranked by frequency. A lookup becomes "walk to the node, return its list"; flatten the trie into a key-value map (top10:ipho -> [...]) and it is a single GET.
It works because rankings change slowly: this hour's top completions of ipho look like last hour's, so you can recompute them in a batch and serve them read-only. The trade-off is freshness: a suddenly trending query waits for the next rebuild. You also spend memory on k completions per prefix, which is why real systems cap prefix length and drop rare prefixes.
The pattern in Proschi is a service reading one key from an in-memory store:
title"Precomputed lookup"client "Client"[Actor]api "Lookup API"[REST API] x4store "Top-k Store"[Redis] x2client -> api : HTTPSapi -> store : GETusecase"Lookup" { client -> api : GET /lookup?prefix=ab api -> store : GET topk:ab store --> api : ["abc", "abd"] api --> client : 200}
A CDN (content delivery network) is a fleet of caching proxies close to users. When a response carries a header such as Cache-Control: max-age=300, the CDN may serve the same answer to everyone who asks for that URL in the next five minutes, without contacting your servers.
Autocomplete fits unusually well: a few thousand short prefixes (i, ip, sam, nik) make up most requests, and their answers are the same for every user. Caching them at the edge removes most of the load and shortens the round trip for users far from your data center.
The trade-offs are staleness (up to the TTL, which the problem allows) and control: evicting one prefix from thousands of edge caches is hard, so you rely on short TTLs. Do not use it for personalised responses, data that must be fresh to the second, or long-tail keys rarely requested twice (the CDN only adds a hop).
Deep dive An edge cache in Proschi
The edge is two scenarios of the same use case, a hit that returns from the CDN and a miss that goes on to your servers:
Logging off the request path, rebuilding in batch #
Updating counters synchronously puts a write, and its failure modes, on every search. Instead, append each query to a log (a Kafka topic) asynchronously and let an offline job count. In Proschi an async send is ->>: the sender hands the message over and does not wait for the consumer. Searches keep working if the builder is slow or down, and the builder can reprocess days of queries at its own pace.
A scheduled batch job reads the log, counts per prefix (often with time decay), and writes each prefix's new top ten with a plain SET. That replaces the old list atomically per key: readers see the old or the new list, never half of one.
Trade-offs: minutes of lag, and a full rebuild is real work. A streaming job is fresher but has more moving parts; sampling the log is cheaper but less accurate. When freshness is a product requirement (breaking news), use streaming with a short window instead.
title"Log now, aggregate later"client "Client"[Actor]api "API"[REST API] x2log "Event Log"[Kafka] x2client -> api : HTTPSapi -> log : produceusecase"Act" { client -> api : POST /actions api ->> log : ActionDone api --> client : 202}
Ask: prefix-only or fuzzy? Global or personalised? How fresh? How many results, ranked by what? What scale? Here: prefix-only, global, up to five minutes stale at the edge and 15 minutes behind on rankings, top ten by popularity, 100k rps. Say it out loud: global, slightly stale answers are what make caching legal.
Suggest: user → CDN → (on a miss) load balancer → Suggest Service → suggestion store.
Search: user → load balancer → Search API → search cluster, plus an async append to the query log.
Rebuild: scheduler → index builder → reads the query log → writes the suggestion store.
Dismiss two tempting designs with numbers. The first is the starter's prefix query on Elasticsearch, natural because the cluster exists: 100k rps against a 9k-rps cluster. The second is computing suggestions from a database (LIKE 'ipho%' ORDER BY count DESC LIMIT 10), which reads and sorts many rows per keystroke on the hottest path.
What wins is to precompute and cache twice: the lists live in memory, and the most popular are also cached at the edge.
Sizing the miss path. Only 20% of keystrokes reach your servers. Size the load balancer, the Suggest Service and Redis for 20k rps, then check that no node goes above roughly 70% (the simulation paints it amber) and that removing one replica of each does not saturate it. For the service, aim lower than 70%: the miss path already has four hops, and queueing at the busiest node is what pushes p99 over. Compute replicas = load ÷ (2k × target utilisation) and try it; if p99 is just over 50 ms, the service is queueing, so add replicas there.
Why the edge hit never touches a service. The check "Suggest" scenario "Edge hit" never calls any service (in the test "Suggestions are served by the CDN, then the cache") encodes the whole point of the CDN. If your hit scenario still goes to an API (say, one that checks a cache), you have built a cache, not an edge, and you pay for the servers anyway.
Search and rebuild. The Search API takes 2k rps, so a few replicas suffice, and the log write is ->>, so a slow broker never slows a search. The builder reads the log and writes the store; it never queries the search cluster, which is busy serving searches.
Failure. Give every node you run at least two replicas, the lightly loaded builder and store included, then check the analysis for single points of failure.
Summarise: precompute the top ten per prefix every 15 minutes, serve it from Redis behind a CDN that answers 80% of keystrokes, log searches asynchronously. Then name next steps: time-decayed ranking, and client-side debouncing and caching that cut the request rate before it reaches the CDN.
Suggestions without a CDN (wrong/suggestions-without-cdn.proschi). Every keystroke goes through the load balancer to the Suggest Service, which then needs about 100 replicas ($10,000, about $13,000 a month in total). The most common whiteboard design, not wrong so much as expensive: you pay to serve the same few thousand answers millions of times. It fails the flow test "Suggestions are served by the CDN, then the cache" and the cost requirement.
The search waits for the query log (wrong/search-waits-for-query-log.proschi). The API sends the query to Kafka with -> and waits for an acknowledgement. In production every Kafka hiccup, rebalance or slow disk becomes search latency, and a broker outage a search outage, all for data no user is waiting for. It fails "Searches feed the query log without waiting for it".
The rebuild triggered by the Search API (wrong/rebuild-from-search-api.proschi). The API starts a rebuild instead of the scheduler. That couples heavy batch work to user traffic: a spike becomes a rebuild storm, and quiet hours mean no rebuilds at all. It fails "The index is rebuilt offline from the query log", whose first check is that the rebuild starts at the scheduler.
Prefix queries on the search cluster (the starter design). The cluster is sized for 2k searches a second (about 9k at most), not 100k keystrokes, and the design fails "Suggestions never touch the search cluster".
A load balancer instead of a CDN. Load balancers spread requests; they do not cache them. An [AWS Load Balancer] in the CDN's place fails the flow test, and the servers behind it still see every keystroke.
Lead with the insight, then the numbers. Draw the three flows, then do the arithmetic for the miss path on the board.
Follow-up questions you should expect:
How do you handle a trending query? Shorten the rebuild interval for the top prefixes, or add a streaming path that updates a small set of hot prefixes between rebuilds. The CDN TTL bounds how stale the edge can be.
How do you personalise? Keep the global list at the edge and merge a small per-user list (recent searches) on the client or in the service. Personalised responses cannot be cached at the CDN, so keep that part small.
What if the suggestion data no longer fits in one Redis? Shard by prefix (or by a hash of the prefix). Short prefixes are the hottest keys, so replicate those widely or keep them in every shard.
How do you stop offensive suggestions? Filter in the builder before publishing, and purge the few already cached.
What if Kafka is down? Searches still work, because logging is asynchronous; the next rebuild just uses older data.
Why not a trie in the service's own memory? It saves a hop, but every replica must load and refresh the whole structure. Either is fine if you name the trade-off.
awesome-scalability: see "Distributed Searching" for engineering posts on autocomplete and search at real companies.
System Design Interview – An Insider's Guide, Vol. 1 (Alex Xu): the chapters "Design A Search Autocomplete System" and "A Framework For System Design Interviews".