Cheat sheet · Whole systems
Design search autocomplete
The problem
Every keystroke in the search box asks for ten suggestions, and the answer must arrive before the next key. We build it step by step: the budget, why `LIKE 'pre%'` fails, a trie with precomputed top-k, prefix shards, debounce and CDN, an offline pipeline with an atomic swap, a real-time layer for trends, filtering and the price of personalization.
What you learn
- How to turn keystrokes into a request rate and a latency budget
- Why a prefix tree with top-k stored in every node beats a database query
- How debounce, a client cache and a CDN remove most requests before they reach you
- How an offline pipeline, an atomic index swap and a small real-time layer keep suggestions fresh and clean
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_user(["Search box"])
n_api["Suggest API"]
n_index{{"Index shard 1"}}
n_index2{{"Index shard 2"}}
n_cdn[/"CDN edge"\]
n_queue[["Query log"]]
n_agg("Aggregation job")
n_storage[("Snapshots")]
n_trend{{"Trending 5 min"}}
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn -.-> n_user
n_cdn --> n_api
n_api -->|"async"| n_queue
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trendMermaid: request sequence
sequenceDiagram
participant n_user as Search box
participant n_api as Suggest API
participant n_db as Queries DB
participant n_index as Index shard 1
participant n_cdn as CDN edge
participant n_agg as Aggregation job
participant n_storage as Snapshots
participant n_trend as Trending 5 min
participant n_queue as Query log
Note over n_user,n_api: Ten suggestions per keystroke, before the next key
n_user->>n_api: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_api-->>n_user: HTTP/1.1 200 OK
Note over n_api,n_db: LIKE 'ip%' reads millions of rows to return ten
n_api->>n_db: EXPLAIN ANALYZE
n_db-->>n_api: Limit (actual time=611.4..611.5 rows=10)
Note over n_api,n_index: A trie with the answer already stored in each node
n_api->>n_index: lookup prefix=#34;ip#34;
n_index-->>n_api: walk root -#62; i -#62; p (2 hops)
Note over n_api,n_index: Shard the index by prefix range
n_api->>n_index: shard map v7 (split by traffic, not alphabet)
n_index-->>n_api: [a, iq) -#62; idx-1 heap 29 GB 49% of traffic
Note over n_user,n_api: Every keystroke is a request
n_user->>n_api: 18:14:02.110 GET /suggest?q=i
Note over n_user,n_cdn: Most requests never reach the backend
n_user->>n_cdn: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OK
Note over n_agg,n_storage: Query logs become the next index
n_agg->>n_storage: agg output window=2026-11-17T08:00Z/1h
Note over n_storage,n_index: Load the new trie beside the old, then swap one pointer
n_storage->>n_index: 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
Note over n_api,n_trend: A small real-time layer for what is hot right now
n_api->>n_trend: trend.match prefix=#34;st#34; window=5m
n_trend-->>n_api: storm warning 1 812 / 5m x46 vs usual
Note over n_queue,n_trend: Filter before anything is shown
n_queue->>n_trend: filter drop #34;cheap pills now#34; from trend:en
n_trend-->>n_queue: rule blocklist match (spam)
Note over n_user,n_cdn: Personalization costs the cache
n_user->>n_cdn: GET /suggest?q=iph#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OKD2
direction: right
n_user: "Search box" {
shape: rectangle
}
n_api: "Suggest API" {
shape: rectangle
}
n_index: "Index shard 1" {
shape: hexagon
}
n_index2: "Index shard 2" {
shape: hexagon
}
n_cdn: "CDN edge" {
shape: oval
}
n_queue: "Query log" {
shape: queue
}
n_agg: "Aggregation job" {
shape: rectangle
style.multiple: true
}
n_storage: "Snapshots" {
shape: stored_data
}
n_trend: "Trending 5 min" {
shape: hexagon
}
n_api -> n_index
n_api -> n_index2
n_user -> n_cdn
n_cdn -> n_user {
style.stroke-dash: 3
}
n_cdn -> n_api
n_api -> n_queue: "async"
n_queue -> n_agg
n_agg -> n_storage
n_storage -> n_index
n_storage -> n_index2
n_queue -> n_trend
n_api -> n_trendPlantUML: request sequence
@startuml
participant "Search box" as n_user
participant "Suggest API" as n_api
database "Queries DB" as n_db
collections "Index shard 1" as n_index
participant "CDN edge" as n_cdn
participant "Aggregation job" as n_agg
database "Snapshots" as n_storage
collections "Trending 5 min" as n_trend
queue "Query log" as n_queue
note over n_user, n_api : Ten suggestions per keystroke, before the next key
n_user -> n_api : GET /suggest?q=ip&lang=en HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
note over n_api, n_db : LIKE 'ip%' reads millions of rows to return ten
n_api -> n_db : EXPLAIN ANALYZE
n_db --> n_api : Limit (actual time=611.4..611.5 rows=10)
note over n_api, n_index : A trie with the answer already stored in each node
n_api -> n_index : lookup prefix="ip"
n_index --> n_api : walk root -> i -> p (2 hops)
note over n_api, n_index : Shard the index by prefix range
n_api -> n_index : shard map v7 (split by traffic, not alphabet)
n_index --> n_api : [a, iq) -> idx-1 heap 29 GB 49% of traffic
note over n_user, n_api : Every keystroke is a request
n_user -> n_api : 18:14:02.110 GET /suggest?q=i
note over n_user, n_cdn : Most requests never reach the backend
n_user -> n_cdn : GET /suggest?q=ip&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
note over n_agg, n_storage : Query logs become the next index
n_agg -> n_storage : agg output window=2026-11-17T08:00Z/1h
note over n_storage, n_index : Load the new trie beside the old, then swap one pointer
n_storage -> n_index : 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
note over n_api, n_trend : A small real-time layer for what is hot right now
n_api -> n_trend : trend.match prefix="st" window=5m
n_trend --> n_api : storm warning 1 812 / 5m x46 vs usual
note over n_queue, n_trend : Filter before anything is shown
n_queue -> n_trend : filter drop "cheap pills now" from trend:en
n_trend --> n_queue : rule blocklist match (spam)
note over n_user, n_cdn : Personalization costs the cache
n_user -> n_cdn : GET /suggest?q=iph&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
@endumlPlantUML: components
@startuml
left to right direction
agent "Search box" as n_user
component "Suggest API" as n_api
stack "Index shard 1" as n_index
stack "Index shard 2" as n_index2
frame "CDN edge" as n_cdn
queue "Query log" as n_queue
collections "Aggregation job" as n_agg
storage "Snapshots" as n_storage
stack "Trending 5 min" as n_trend
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn ..> n_user
n_cdn --> n_api
n_api --> n_queue : async
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trend
@endumlRecap
Autocomplete is a race against the next keystroke: about 100 ms end to end, 20 ms on the server.
1) Count keystrokes, not searches: 3 500/s average, 14 000/s at peak. 2) LIKE 'pre%' reads every match to rank them; a trie with top-k stored in each node answers in microseconds. 3) Shard by prefix range cut by traffic, with replicas. 4) Debounce, a client cache and a CDN for short prefixes take most of the load. 5) An offline pipeline turns query logs into snapshots, swapped in atomically; a tiny real-time layer adds trends. 6) Filter with a blocklist and a distinct-user floor; personalize only where the cache is not helping anyway.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Suggest p95 | 60 ms | 35 ms |
| Requests to backend | 3 500/s | 3 600/s |
| Freshness lag | 86 400 s | 60 s |
| Bad suggestions | 140/day | 3/day |
Steps
- Case Ten suggestions per keystroke, before the next key
Say 25 million searches a day, about 12 keystrokes each: 300 million suggest calls a day, 3 500/s on average and four times that in the evening peak.
- Problem
LIKE 'ip%'reads millions of rows to return tenA B-tree index on
querycan find where theiprange starts. - Fix A trie with the answer already stored in each node
A trie (prefix tree) has one node per prefix:
i, thenip, theniph. - Fix Shard the index by prefix range
The full trie needs about 60 GB, too much for one process and one CPU at the evening peak.
- Problem Every keystroke is a request
In the evening peak the API takes 14 000 requests/s.
- Fix Most requests never reach the backend
Three layers, cheapest first.
- Fix Query logs become the next index
Every search the user actually submits goes to a query log stream, fire-and-forget.
- Fix Load the new trie beside the old, then swap one pointer
Each shard downloads its new snapshot into spare memory while still serving the old one.
- Fix A small real-time layer for what is hot right now
A second consumer reads the same query log and keeps counts for the last five minutes in memory.
- Fix Filter before anything is shown
Suggestions are words we put in front of users, so they need the same care as any content.
- Case Personalization costs the cache
Product wants the user's own past searches on top.
- Recap Recap
Autocomplete is a race against the next keystroke: about 100 ms end to end, 20 ms on the server.
Terms
- Trie (prefix tree)
- A tree with one node per prefix; lookup cost depends on the prefix length, not on how much data there is.
- Top-k
- A precomputed list of the k best results, so nothing has to be sorted at request time.
- Debounce
- Send the request only after a short pause since the last event, so a burst of keystrokes becomes one request.