Design typeahead: suggest, learn, block
"Typeahead is a prefix lookup that runs on every keystroke, so it is read-heavy and has almost no time. The question is when the ranking happens: at request time or ahead of time. The answer is ahead of time. The top 10 for every prefix is computed offline from the search log, every serving host holds that index in memory, and a keystroke reads a finished list instead of ranking candidates. The rest of the design is how the index gets built and swapped, how a trend or a block lands in minutes, and how the client and the CDN keep keystrokes off the hosts."
Understanding the problem
5 minFunctional Requirements
- As a user types, they see up to 10 suggestions that start with the prefix typed so far, most popular first.
- Suggestions come from what people search: every submitted search counts toward its query's popularity.
- An operator can block a suggestion, and it stops appearing.
Below the line (out of scope):
- Personalized suggestions that use a user's own history or location.
- Spelling correction, fuzzy matching, and matching in the middle of a query ("york" suggesting "new york").
- The search itself and the ranking of its results.
- Languages other than English, for the first design.
Non-Functional Requirements
- 5B searches a day / 86,400 s is about 58,000 searches/s, and each one is a write to the popularity data.
- 5,000,000,000 / 86,400 s = 57,870 on average, and peak is 2x average: 116,000 searches/s.
- A 20-character query sends up to 20 suggestion requests: 58,000 × 20 = 1.16M requests/s, about 2.3M/s at a 2x peak.
- Size for that figure: picking a suggestion early lowers the real rate, and backspacing and retyping raise it.
- Reads outnumber searches by up to 20 to 1.
- Each read has about 20 ms on a host, out of the 100 ms target below.
- So the work per request has to stay small and fixed, however many queries match the prefix.
- The inputs are assumptions: an average query is 20 characters (20 bytes in ASCII), and peak is 2x average.
- About 100M queries are popular enough to suggest: 100M × 20 B = 2 GB of text, and 100M × 20 characters = up to 2B distinct prefixes.
- The text is small.
- The prefixes are the hard part: any of 2B prefixes has to be answered inside the budget.
- Fast: a list renders within 100 ms of its request at p99, for a user anywhere, on an established connection.
- A host's budget is 20 ms at p99. The other 80 ms is the network round trip and the client's render.
- The 100 ms runs from request to render, which is the part this system controls.
- Available over consistent: suggestions are available 99.99% of the time.
- A stale list, or two users seeing different lists for a while, is fine.
- Search must keep working when suggestions do not.
- Fresh: a trending query appears within 5 minutes of passing the trending threshold, and a blocked suggestion is gone within 1 minute.
- Ordinary popularity may lag a day.
- The trending threshold is the point where the system counts a query as a trend; the dive on trending and blocked queries sets it.
- Scale: the system serves 2.3M suggestion requests/s at peak over about 100M queries worth suggesting.
- The first design covers English only: lowercase letters, digits and the space, 37 characters.
- Private: no suggestion reveals one person's search, and one person cannot put a query into suggestions.
Entities + API
5 minDefining the Core Entities
- Query
{text, score}: a normalized search string people have run, with a popularity score.- In the simple design the score is a count of searches.
- SearchSubmitted
{query, userId, signedIn, ip, lang, ts}: the event for one submitted search, and this system's only input.userIdis the account id, or an anonymous device id when the user is signed out.signedInsays which.
- BlockedQuery
{id, text, reason, addedBy, addedAt}: one blocklist entry. - The list for a prefix, its up-to-10 suggestions, is derived data: nobody writes it, it is computed from Query scores.
API or System Interface
GET /suggestions?q={prefix}&lang={lang} // -> 200 { q, suggestions: [text, ...] } up to 10, best first
POST /admin/blocklist // { query, reason } -> 201 { id }
DELETE /admin/blocklist/{id} // -> 204
event SearchSubmitted // { query, userId, signedIn, ip, lang, ts }, from the Search Service
GET /suggestions?q={prefix}&lang={lang}returns up to 10 suggestions, best first, and the response is the same for every user.- The request carries no auth token and the response no user data.
- The client and the service both normalize
q: lowercase, letters, digits and spaces only, no leading space, runs of spaces collapsed to one.- A single trailing space is kept, because "new " and "new" are different prefixes.
- The response echoes
q.
- An unknown prefix returns 200 with an empty list, never 404.
- The Search Service publishes one
SearchSubmittedevent per submitted search, at least once, and that event is this system's only input.- Search is out of scope, and the Search Service already exists.
- Blocklist calls need an operator role, and an entry blocks one exact normalized query.
- Pattern rules and a classifier for offensive text are out of scope.
High-level design
10 min, end to end, no dives yet1) Suggest as the user types
- Client → API gateway / load balancer → Suggestion Service → QueryCount table (Postgres).
- QueryCount is
{text PRIMARY KEY, count}, one row per query people have searched. - Each keystroke runs one prefix lookup:
SELECT text FROM query_count WHERE text LIKE 'spo%' ORDER BY count DESC LIMIT 10.- An index on
textwithtext_pattern_opsmakes the prefix a range scan.
- An index on
- The Suggestion Service is stateless and scales horizontally.
- A short prefix matches millions of rows, and the database reads every one of them to return 10; the dive on lookup speed handles it.
- Short prefixes are also the most-typed ones.
- The client sends one request per keystroke; the dive on request volume handles it.
2) Learn from searches
- The Search Service publishes one
SearchSubmittedevent per search to SearchLog, a Kafka topic.- Search never waits on typeahead.
- CountWorkers consume in batches, normalize each query, sum per query inside the batch, and upsert into QueryCount.
INSERT ... ON CONFLICT (text) DO UPDATE SET count = query_count.count + EXCLUDED.count
- Delivery is at least once, so a redelivered batch overcounts a little.
- A popularity ranking does not need exact counts. Say so.
- Reads and count writes share one table, and one person or one bot can inflate a raw count; the dive on building the index handles it.
- Sharing a table means each slows the other.
- Counts are all-time, so a query surging today sits below an old favourite; the dive on trending and blocked queries handles it.
3) Block a suggestion
- Operator → Admin Service → Blocklist table
{id, text, reason, addedBy, addedAt}, in the same Postgres.- The Admin Service checks the operator role and normalizes the text.
- The prefix lookup skips blocked rows: it adds
AND NOT EXISTS (SELECT 1 FROM blocklist b WHERE b.text = query_count.text). - A block applies on the next request, because the lookup checks the table every time.
- A query nobody has searched yet can be blocked: its row waits in Blocklist.
- Unblocking is a DELETE of the row.
Potential deep dives
~20 min, interviewer steers1) Lookup speed: how does one keystroke get its top 10 in a few milliseconds?
- The Suggestion Service runs the prefix lookup against Postgres on every keystroke.
- "s" matches 1 row in 10, which is at least 10M rows, and the database reads all of them.
- Say 1 query in 10 starts with "s".
- QueryCount holds every query ever searched, more than the 100M worth suggesting, so 1 row in 10 is at least 10M rows.
- The database keeps the best 10 in a heap as it reads.
- The shortest prefixes are the slowest and the most requested.
- 2.3M requests/s is far past one database.
- Hold the queries in an in-memory trie, a tree where each edge adds one character.
- Walk down the prefix to its node. Every query with that prefix sits beneath it.
- Ranking at request time is still too slow: the subtree under a short prefix is too big to walk.
- Under "s" sit at least 10M queries.
- At least 10M node visits at about 100 ns each (a cache miss) is at least 1 s for one request, against a 20 ms budget.
- So store the finished top 10 at every node: a lookup walks one node per character and reads a list.
- Still wrong: a plain trie has one node per prefix, and that is too big to load on every host.
- Up to 2B prefixes × 40 B a list (10 query ids of 4 B) = up to 80 GB of lists, before any structure.
- An index that size sits in a separate cluster, and every keystroke pays a network call to reach it.
- Do the ranking before the request: store the finished top 10 at every prefix, so a keystroke only reads a list.
- The index is a trie (a tree where each edge adds one character) whose nodes each hold the 10 best queries at or beneath them.
- A lookup walks one node per character typed and returns that node's list.
- That takes microseconds, the same for "s" as for a 20-character prefix.
- Use a radix tree, a trie with single-child chains merged into one edge, so every prefix inside an edge shares the list at the edge's end.
- For example, "s" ends inside the edge "sp", and every query under "s" is also under "sp", so the two lists are the same.
- The walk is shorter too: "spo" is 2 edges, "sp" then "o".
- It fits in memory: 100M queries make fewer than 200M nodes × 40 B (10 query ids of 4 B) = 8 GB of lists, about 15 GB in all.
- A radix tree of N queries has fewer than 2N nodes: at most N terminal nodes plus at most N - 1 branching nodes.
- A plain trie, or a hash map of 2B prefixes, would take up to 80 GB of lists.
- Every Suggestion Service host loads the whole index into its own memory, so a request makes no call to a database or cache.
- Cost: the index is expensive to change, so it is built as a whole; the dive on building the index covers how.
Follow-up answers (4)
- The lists are built bottom-up: each node's list is the best 10 from its children's lists, plus the node itself if it is a query.
- The parts sum to 13.6 to 15.2 GB, and that assumes a full 10-slot list at every node, so the real index is smaller.
- 100M query ids fit in 4 B, because 232 = 4.29B.
- To the 8 GB of lists add 2 GB of text, 0.4 GB of scores (one 4 B score per query), and 16 to 24 B of structure per node, which is 3.2 to 4.8 GB.
- It assumes nodes packed into flat arrays, which an immutable index allows.
- One heap object per node costs several times more.
- A key-value store holding prefix → list (Redis) also works and is simpler to run.
- It costs a network hop per keystroke and the larger hash-map form.
- Off the shelf, Elasticsearch's completion suggester is the closest design.
- It is an in-memory finite-state transducer, a compressed automaton that shares prefixes and suffixes.
- It stores no lists and searches for the top N at request time.
- So its index is smaller, and its work per request is harder to bound.
2) Building the index: every host answers from an in-memory index of the top 10 for each prefix, so how do 5B searches a day become a fresh index without slowing reads?
- Every search updates the index in place, on every host.
- One search can change the top-10 list of up to 20 prefixes.
- At peak, 116,000 searches/s × 20 = up to 2.3M top-10 list updates a second.
- Those updates land on the structure that 2.3M reads/s are walking.
- Every host must apply every update, or the copies drift apart.
- An index that is always changing has no version.
- There is nothing to validate before it serves.
- There is nothing to roll back to.
- Count offline: a daily batch job totals the search log into a count per query, and each host rebuilds its trie from the counts in the background.
- Reads no longer contend with writes.
- Still wrong: every host builds its own copy, nothing checks the result, and the counts are raw.
- Every host repeats the same build, competing with reads for CPU and memory.
- Each host switches when its own build finishes, so nobody can stage the change or stop it.
- When the counts are bad, there is no previous version to go back to.
- A raw count lets one person or one bot push a query into suggestions.
- Build the index once, offline, as one immutable versioned file (a snapshot) that every host loads; hosts never build it themselves.
- A daily batch job reduces yesterday's 500 GB of search log to one row per query: its count and an estimate of its distinct users.
- The search log is archived to object storage (LogArchive), and the job (Spark) reads it there. This job is the daily aggregate job.
- It replaces the CountWorkers and the QueryCount table of the simple design, and normalizes each query as they did. Postgres keeps only the Blocklist table.
- It writes one aggregate a day to a second bucket in LogArchive, apart from the raw log.
- The estimate is a HyperLogLog sketch, a small structure that estimates a distinct count and can be merged with another sketch.
- So 30-day distinct users come from merging 30 daily sketches, with no rescan of raw events.
- The log is 5B events × about 100 B = 500 GB a day, 15 TB for 30 days.
- Score a query in searches per day (30 daily counts with a 7-day half-life), and suggest it only with 100 distinct users in 30 days.
- The score is a weighted average of the last 30 daily counts, in which a day's weight halves every 7 days.
- Each day's weight is 0.906 of the next day's, and 30 such weights sum to about 10, so yesterday is about 10% of a score.
- A query is eligible only with at least 100 distinct users in 30 days, so one person's search never shows and one bot counts once.
- A second batch job, the index builder, reads the last 30 aggregates, computes the scores, applies the 100-distinct-user threshold and writes the snapshot.
- The two jobs share only what is stored in LogArchive and never call each other. A workflow scheduler (such as Airflow) starts the index builder once yesterday's aggregate is written.
- Object storage fits better than a queue: a failed or wrong day is rerun alone and overwrites that day's aggregate, and an append-only queue cannot replace a day.
- It fits better than a database: the builder reads each aggregate whole on 30 consecutive builds and never looks up one row by key, so an index would go unused.
- The score is a weighted average of the last 30 daily counts, in which a day's weight halves every 7 days.
- A snapshot must pass checks before any host sees it, then goes to one canary host, then to 10% of hosts at a time.
- The checks are that its size is within 10% of the last snapshot's, and that well-known prefixes return full lists.
- Snapshots live in object storage (SnapshotStore), each under a version number with a checksum.
- The rollout watches errors, latency and the empty-list rate.
- Each host loads the new snapshot beside the current one, verifies its checksum and swaps one pointer; rollback is the same swap backwards.
- Requests in flight finish on the old index: each request holds a reference to the index it started on, and the old index is unmapped when its reference count reaches zero.
- The previous snapshot stays on disk, so rolling back is a memory map and the same swap, with no download.
- Cost: the base index (the daily snapshot) is a day behind, plus the build and rollout time; the dive on trending and blocked queries covers the gap.
Follow-up answers (5)
- The snapshot file is the in-memory layout, so loading is a memory map and no parse.
- The checksum pass reads every page of the file, which also brings it into memory before the swap.
- A host needs memory for two copies during the swap: 2 × 15 GB.
- An anonymous device id costs nothing to create, so the distinct-user count takes every signed-in account and caps the anonymous ids it counts per IP address.
- The event's
signedInandipfields carry what that needs. - Beyond that, abuse detection is out of scope.
- The event's
- The index builder also drops blocked queries.
- Hosts run mixed versions for the length of the rollout, up to an hour, so two keystrokes can be answered by different versions.
- The availability-over-consistency target allows it.
- A starting host does not pass its health check until it holds a snapshot and a blocklist (the dive on trending and blocked queries puts the blocklist in host memory).
- It keeps the last of each on local disk, so a restart needs neither object storage nor Postgres.
- When Postgres is reachable, it polls the blocklist once before it serves, so a block added while it was down is not missed.
- A brand-new host needs both.
3) Trending and blocked queries: the index is rebuilt once a day, so how does a change show in minutes?
- Every change waits for the next daily build.
- A query that starts surging at 9 am is missing until tomorrow.
- A blocked suggestion stays up for up to a day.
- The simple design blocked on the next request. Moving to an index built once a day is what broke that.
- Count and build every hour: the index builder already drops blocked queries, so a trend or a block lands in about two hours.
- The aggregate job also totals the current day so far, and a rollout takes up to an hour.
- Still wrong: two hours misses both targets, 5 minutes for a trend and 1 minute for a block.
- It is also 24 full builds and fleet rollouts a day to move a handful of queries.
- Keep the base index (the daily snapshot) and apply two small, fast-changing things to each response: trending queries and the blocklist.
- The base index stays as it is, a day old.
- This is the lambda architecture: the base index is the batch layer, the trending queries are the speed layer, and the two merge at read time.
- Every score is in searches per day, so new and old compare directly: a 15-minute count times 96 is a daily rate.
- 15 minutes × 96 = 24 hours.
- 2,000 searches in 15 minutes scores 192,000 a day.
- A stream job counts each query over a sliding 15-minute window; 1,000 distinct users and 3 times its base score make it trending.
- The stream job (Flink) is the trending job, and its window advances every minute.
- A query is trending when at least 1,000 distinct users searched it in the window and its daily rate is at least 3 times its score in the base index.
- The job loads base scores from the latest snapshot.
- The trending job keeps one count and one distinct-user sketch per query per minute, and combines the last 15.
- A sketch of a few users is a few bytes, so the long tail of rare queries stays cheap.
- It counts distinct users the way the daily job does: signed-in accounts in full, anonymous ids capped per IP address.
- Every minute the job writes the trending delta, a small index of prefix → trending queries, to object storage, and each host swaps it in.
- A host checks SnapshotStore for a new one every 10 seconds, on the same timer as its blocklist poll, and replaces its copy with one pointer swap.
- Per request a host reads both indexes, merges by score, drops anything on the blocklist it polls every 10 seconds, and returns the top 10.
- It looks the prefix up in the base index and in the trending delta.
- A query in both keeps the higher score.
- The merge handles at most 13 entries, 10 from the base index and at most 3 trending, so the work per request stays small and fixed.
Follow-up answers (4)
- Both targets are met: a trend shows within 130 s of passing the trending threshold, and a block is gone within 40 s.
- The trend path is 30 + 60 + 10 + 30 = 130 s.
- Kafka lag and the watermark (how long the stream job waits for late events) take up to 30 s.
- The window takes up to 60 s to advance.
- Hosts take 10 s to see the new trending delta.
- Caches hold the old response for 30 s.
- Reaching the 1,000-distinct-user threshold comes first and depends on the surge: 1,000 distinct users at 5 a second is 200 s.
- The block path is 10 s of poll + 30 s of caches = 40 s. The dive on request volume sets the 30 s.
- That holds while Postgres is up. A block cannot be written while it is down.
- The trend path is 30 + 60 + 10 + 30 = 130 s.
- What counts as a trend: a query enters at 3 times its base score and leaves below 2 times.
- The 3x threshold keeps out evergreen queries (popular every day) and the daily peak (2x).
- The gap between entering and leaving is hysteresis, so a query sitting at the threshold does not flicker in and out each minute.
- If a trend lasted, the next daily build carries it, since yesterday is about 10% of a score.
- The trending delta is a small file that a host can always discard.
- It is a file in SnapshotStore, the object storage that holds the snapshots, and it is under 20 MB.
- At peak, 116,000 searches/s × 900 s = 104M searches per 15-minute window, so at most 104M / 1,000 = 104,000 queries can pass a 1,000-user threshold.
- It is a radix tree like the base index: fewer than 208,000 nodes at about 40 B each is about 8 MB, plus about 2 MB of text.
- It carries query text and scores, not ids.
- An id belongs to one snapshot, and hosts run two snapshot versions during a rollout.
- The merge matches a query in both by text.
- It is the riskiest way a change reaches the hosts: it lands on every host each minute with no validation gate and no canary, so it is bounded instead.
- Any prefix gets at most 3 trending entries.
- The delta's total size is capped.
- One switch makes every host ignore the delta.
- It carries the end time of its window, and a host drops a delta older than 5 minutes and serves the base index alone.
- So a stopped trending job, or one whose input has stalled, removes trends instead of pinning the last ones.
- It is a file in SnapshotStore, the object storage that holds the snapshots, and it is under 20 MB.
- The blocklist is polled from Postgres and applied last.
- The Blocklist table in Postgres is the source of truth, and every host polls it every 10 seconds.
- A poll reads one version number that the Admin Service raises on every change, and a host reloads the list only when the number has moved.
- The blocklist filter is the last step, after the merge, so it covers both indexes and any snapshot version.
- A list that loses an entry returns 9 until the next daily build drops the query at the source.
- A host that cannot reach the Blocklist table keeps serving with its last copy and raises an alarm on the copy's age.
- That chooses availability over the 1-minute target for that host. Say so.
- Unblocking is slower than blocking.
- Once a build has dropped the query, it returns with the next build that starts after the unblock.
- Before any build has dropped it, removing the block shows the query again within 40 s.
- The Blocklist table in Postgres is the source of truth, and every host polls it every 10 seconds.
4) Request volume: how do you keep 2.3M suggestion requests a second from all reaching the hosts?
- The client sends a request on every keystroke and renders whatever comes back.
- That is up to 20 requests per search, 2.3M/s at peak.
- Responses can also arrive out of order: the list for "sea" lands after the list for "seat" and replaces it.
- Debounce: send only after about 100 ms with no keystroke.
- It delays every request it sends by the full 100 ms, so a list appears up to 200 ms after the keystroke: 100 ms of waiting plus the 100 ms response target.
- An average typist leaves about 230 ms between keys, so debounce only drops requests inside fast bursts.
- Keep a client cache, a map of prefix → list in page memory, so backspacing and retyping cost nothing.
- An entry expires after 30 seconds, or a long-open tab keeps showing a blocked suggestion.
- Render a response only when its
qequals the current input, or abort the superseded request. - Still wrong: every user's first keystrokes still reach the hosts.
- That is 58,000 first characters a second, for which there are at most 36 answers: a first character is a letter or a digit.
- Debounce and cache on the client, then let a shared cache answer: a prefix's list is the same for every user.
- One host response can then serve thousands of people.
- Make the request a plain GET with no user data and return
Cache-Control: public, max-age=30, so a CDN and the browser reuse it for 30 s.- The GET carries the normalized prefix.
- Traffic piles onto few keys: every search sends its 1-, 2- and 3-character prefixes, at most 37 + 1,369 + 50,653 = 52,059 keys.
- The alphabet is 37 characters: letters, digits and space. A leading space is removed, so the true count is a little lower.
- Before any debounce, that is at least 3 of every 20 requests.
- At one CDN edge location, one cached entry for "s" answers about 870 requests: 29 a second for 30 seconds.
- Say 1 query in 10 starts with "s": 58,000 searches/s × 1/10 = 5,800 requests/s for "s" as a first keystroke.
- 5,800 / 200 edge locations = 29 a second, and 29 × 30 s is about 870.
- The 30 seconds comes from the block target: hosts learn of a block within 10 seconds, so 10 + 30 = 40 s fits inside 1 minute.
- A blocked suggestion must vanish within 1 minute, and a cache keeps serving it until its entry expires.
Follow-up answers (10)
- Add
must-revalidate, stale-if-error=0to the header: they forbid a cache from serving an entry past 30 s without reaching a host.- Without them, some CDNs serve an expired entry when a host returns a 5xx. CloudFront does by default.
- A 5xx is what load shedding returns, so a blocked suggestion would outlive the minute.
- Cost: when every host is failing, the CDN returns errors and the client shows no list.
- The 30 s runs from when a host built the response: the CDN reports an entry's age in the
Ageheader, and the browser cache and the client cache both subtract it.- A response that was already 20 s old at the CDN is kept 10 s more.
- A client cache that restarted the clock would stretch the block path to 10 + 30 + 30 = 70 s.
- The cache key is exactly (lang, normalized q).
- The CDN is configured to key on those two parameters, drop every other parameter and cookie, and cache this JSON route.
- How much the CDN answers depends on how uneven the prefixes are.
- Spread evenly over 200 edge locations, a 2-character key gets 58,000 / 1,369 / 200 × 30 s = about 6 requests per cached entry, and a 3-character key about 0.2.
- So the edge answers 1- and 2-character prefixes, and a 3-character prefix only where it is popular, or at a regional cache tier between the edges and the hosts.
- Long, rare prefixes mostly miss the CDN and reach the hosts.
- That is fine: the hot short ones are the load.
- The gateway rate-limits per client, because random long prefixes always miss the cache.
- Never retry a suggestion request: the next keystroke replaces it.
- When hosts are slow or shed load (503), the client shows no list and pauses requests for a few seconds, and search still works.
- Size the fleet for the whole peak, as if the client and the CDN removed nothing: 2.3M / 20,000 per host = 115 hosts.
- One host serves about 20,000 requests/s. That is an assumption: the lookup is microseconds, and HTTP handling is the cost.
- What the client and the CDN save is headroom. The CDN also answers the shortest prefixes at an edge location near the user, and absorbs a surge before the hosts see it.
- The whole serving side (hosts, snapshot, trending delta, blocklist) is repeated in each region, because one region cannot reach every user in 100 ms or meet 99.99% alone.
- A snapshot is a file, so another region is one more copy.
- Postgres has one primary, and each region's hosts poll a read replica. Replication lag, about a second, comes out of the 20 s between the 40 s path and the 1-minute target.
- 115 hosts is the minimum for the global peak, and each region adds spare hosts for one failed zone.
- If personalization is added, keep the shared response and merge on the client.
- The client holds the user's own recent searches and ranks matching ones above the shared list.
- The GET stays the same for every user, so it stays cacheable.
5) Outgrowing one host: the whole index sits in each host's memory, so how do you split it when it no longer fits?
- Today the index is about 15 GB, 30 GB while two versions are loaded, so one host holds it and sharding would only add a hop.
- At 1B queries it is about 150 GB, 300 GB during a swap.
- Split when two copies no longer fit in a host's memory.
- The index is split into one shard per first character.
- The shards are uneven: "s" starts about 1 query in 10, "x" almost none.
- There can only ever be as many shards as first characters.
- The "s" shard is the first to outgrow a host, with no way to split it.
- Cut first along a boundary every request already names, its language: each language gets its own index, built, shipped and served on a pool of hosts for that language.
- Small languages share one pool.
- Still wrong: the largest language can outgrow a host by itself, and its first characters are as uneven as before.
- Give each language its own index, and when one outgrows a host, split it by prefix range: each range is a shard, all the same size in bytes.
- The ranges are contiguous, so a big first character is split across shards and small ones share one.
- The offline index builder measures every subtree, picks the range boundaries and writes one self-contained index file per shard.
- For example [a, ca), [ca, e), … with "s" cut in three and "x", "y", "z" together.
- It publishes a shard map (the list of range boundaries) with the same version number as the shard files.
- A router in front of the shards binary-searches the shard map for the request's prefix and forwards to that one shard.
- A lookup never fans out: lists are computed over all the data before the cut, so each prefix and its full top 10 live on one shard.
- Cost: one more network hop, about 1 ms inside a data center, and the request now depends on a router and a shard, so both run replicated.
Follow-up answers (5)
- The list for "s" may name a query whose own node lives on another shard, so each shard file carries the text and score of every query its lists mention.
- Ranges balance bytes; load is balanced separately by giving a hot shard more replicas.
- The CDN already takes the shortest prefixes.
- Routers and shards must agree on the shard map: a shard keeps the old and new versions loaded during a rollout and serves the version the router names.
- The trending delta and the blocklist are small, so every shard holds all of both.
- Hashing the prefix also gives one shard per lookup, but scatters a word's prefixes across shards, so nothing shares a tree.
- Hashing fits a key-value index.
- The work per request grows with the subtree under the prefix.
- "s" holds at least 10M queries, and visiting them at about 100 ns each is at least 1 s per request.
- The biggest subtrees belong to the hottest prefixes, so the slowest requests are the most common ones.
- Store a finished top-10 list at every node, so a lookup walks one node per character and reads the list.
- A radix tree shares one list along an edge, so the lists take 8 GB.
- One search can change up to 20 top-10 lists, which is up to 2.3M list updates a second at peak on the structure reads are walking.
- Every host must apply every update, or the copies drift apart.
- A changing index has no version to validate or roll back.
- Build one immutable snapshot offline, and have each host swap a pointer.
- Freshness comes from a separate small index of trending queries, not from changing this one.
- A stream job counts each query over a 15-minute sliding window that advances every minute.
- A query is trending with at least 1,000 distinct users in the window and a daily rate of at least 3 times its base score.
- A window count × 96 is searches per day, the same unit as the base index.
- Hosts merge the base index and the trending delta by score at request time.
- The path is 30 s of lag + 60 s of window + 10 s of poll + 30 s of cache, which is under 2.5 minutes.
- The blocklist is a set in every host's memory, polled every 10 s.
- The blocklist filter is the last step of every response, so no index version leaks the blocked query.
- Every cache, the client's included, drops an entry 30 s after a host built it, so the block lands within 10 + 30 = 40 s.
must-revalidate, stale-if-error=0forbids a cache from serving an expired entry when hosts return errors.- The next daily build drops the query at the source.
- First characters are uneven, and a first-character shard cannot be split further.
- Give each language its own index first.
- Then cut a language into shards by prefix range, with boundaries set from measured subtree sizes and a versioned shard map.
- A router binary-searches the shard map and forwards each request to one shard.
- The lists are computed before the cut, so one prefix lives on one shard and no lookup fans out.
Final design + what is expected at each level
wrapFinal Design
- Client (debounce, 30 s client cache) → CDN (30 s) → API gateway / load balancer → Suggestion Service hosts, in each region.
- The client also drops out-of-order responses.
- Responses carry
Cache-Control: public, max-age=30, must-revalidate, stale-if-error=0, and every cache counts the 30 s from when a host built the response.
- Each host holds the base index (a radix tree with a top 10 at every node, about 15 GB), the trending delta and the blocklist set in memory.
- For growth, each language gets its own index and pool of hosts. Past one host, a router forwards each request to one shard chosen by prefix range, which adds one hop and no fan-out.
- The Search Service publishes each search to SearchLog (Kafka), and a daily build turns the archived log into a versioned snapshot.
- The log is archived to object storage.
- The daily aggregate job reduces it to counts and distinct-user sketches.
- The index builder scores 30 days with a 7-day half-life, applies the 100-distinct-user threshold and the blocklist, and writes a versioned snapshot.
- The two jobs share only what is stored in LogArchive, and a workflow scheduler starts the index builder after the aggregate job.
- After checks and a canary, hosts load it beside the current one and swap one pointer; rollback is the same swap backwards.
- The trending job writes a trending delta to object storage every minute, and hosts check for it and poll the Blocklist table every 10 s.
- The trending job counts a sliding 15-minute window, and a host drops a delta older than 5 minutes.
- A query is trending with at least 1,000 distinct users in the window and a daily rate of at least 3 times its base score, and it leaves below 2 times.
- Operators write the Blocklist table through the Admin Service, and the index builder reads it too.
- Once a request reaches a host, the host calls nothing and does a small, fixed amount of work. That is the invariant to close on: everything the host reads was built before the request arrived.
- The host reads two short lists from its own memory, merges at most 13 entries by score and checks them against the blocklist set.
- The base index can be a day old plus the build time, the trending delta about a minute old and the blocklist 10 seconds old, and the request path is the same three in-memory lookups.
- The blocklist filter is the last step of every response a host builds, so no index version can leak a blocked query.
- A copy already in a cache lives at most 30 seconds more.
- Hosts already running keep serving when the build pipeline, Kafka, Postgres and object storage are all down.
- Three things degrade.
- No new block lands while Postgres is down.
- Trends drop out after 5 minutes without a fresh trending delta.
- The base index ages a day per missed build.
What is Expected at Each Level
- Mid (E4):
- Clear API and entities.
- A working high-level design: a prefix lookup against a count table, with counts fed from the search log.
- Knows a trie fits the lookup.
- Maybe a client debounce.
- Senior (E5):
- Speeds through the high-level design.
- Goes deep on at least 2 of the dives.
- Lookup speed: moves the lookup into an in-memory trie, says a short prefix's subtree is too big to walk on every keystroke, stores a top 10 at each node, and says a plain trie is too big to load on every host.
- Building the index: counts offline in a daily batch, not per search, and says what goes wrong when every host rebuilds its own copy.
- Trending and blocked queries: counts and rebuilds every hour, so a trend or a block lands in about two hours, and says that still misses 5 minutes and 1 minute.
- Request volume: debounces, keeps a client cache and drops out-of-order responses, and says every user's first keystrokes still reach the hosts.
- Outgrowing one host: rejects first-character shards for skew, splits by language first, and says the largest language can still outgrow a host.
- Staff+:
- Likely covers all the dives.
- Surfaces these unprompted.
- A host calls nothing at request time, and the candidate says what degrades when each dependency is down.
- A bad build meets checks, a canary and rollback.
- Thresholds on distinct users protect privacy and resist manipulation.
- One score unit runs across the base index and the trending delta.
- A stalled trending job must not pin old trends.
- The cache lifetime is derived from the block target, with stale-on-error turned off.
- No lookup fans out after sharding.
Say the opener out loud without notes: a prefix lookup on every keystroke, ranked ahead of time, read from memory.
Then write the math from memory: 5B / 86,400 s = 58,000 searches/s; × 20 = 1.16M requests/s; × 2 = 2.3M at peak; fewer than 2 × 100M = 200M nodes × 40 B = 8 GB of lists.
Then say the swap in one sentence: build one snapshot offline, check it, load it beside the current one, swap one pointer, keep the previous version for rollback.