← all topics Typeahead board · say it in this order 1 Problem2 Entities + API 3 High-level design4 Deep dives 5 Final + levelsreset

Design typeahead: suggest, learn, block

5B searches a day · 2.3M suggestion requests/s at peak · a list within 100 ms · trending in 5 minutes, blocked in 1 · board rules, one idea per line
SAY THIS SENTENCE FIRST

"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."

STEP 1 OF 5

Understanding the problem

5 min

Functional Requirements

  1. As a user types, they see up to 10 suggestions that start with the prefix typed so far, most popular first.
  2. Suggestions come from what people search: every submitted search counts toward its query's popularity.
  3. 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

Do the scale math first, because it shows where the simple design breaks
  • 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.
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Private: no suggestion reveals one person's search, and one person cannot put a query into suggestions.
DONE WHEN: the interviewer has heard "2.3M requests a second at peak with 20 ms each on a host" and "trending in 5 minutes, blocked in 1". The first bounds the work a request may do; the second says popularity that lags a day is not enough by itself.
STEP 2 OF 5

Entities + API

5 min

Defining 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.
    • userId is the account id, or an anonymous device id when the user is signed out. signedIn says 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 SearchSubmitted event 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.
DONE WHEN: you have said "the response is the same for every user" and "the search event is the only input", and moved on inside 5 minutes.
STEP 3 OF 5

High-level design

10 min, end to end, no dives yet

1) Suggest as the user types

Suggest as the user types: one prefix lookup per keystroke Client sends GET /suggestions for every keystroke through APIGateway, which forwards to any SuggestionService host. SuggestionService normalizes the prefix and runs one prefix lookup on QueryCount in Postgres, which returns up to 10 rows, highest count first. The list goes back to the client through APIGateway. A short prefix matches millions of rows, and the database reads all of them to return 10. Every keystroke reaches the database. 1) Suggest as the user types: one prefix lookup per keystroke GET /suggestions?q={prefix}&lang={lang} -> {q, suggestions}. Up to 10, most popular first. The same answer for every user. Client search box,web + mobile APIGateway load balancer SuggestionService stateless,several hosts QueryCount (Postgres) {text PRIMARY KEY, count}one row per query,text_pattern_ops index A short prefix does not scale "s" matches millions ofrows, and the databasereads every one of themto return 10. The dive onlookup speed fixes it. One request per keystroke every keystroke reaches thedatabase, 2.3M requests/s atpeak. The dive on requestvolume fixes it. the prefix lookup: SELECT text FROM query_countWHERE text LIKE 'spo%'ORDER BY count DESCLIMIT 10; 1. Client sends GET /suggestions?q=spo one request per keystroke 2. APIGateway forwards to any host 3. SuggestionService normalizes q and runs the prefix lookup 4. QueryCount returns up to 10 rows, highest count first 5. SuggestionService returns {q, suggestions} 6. APIGateway relays the list the not-so-happy paths: an unknown prefix returns 200 with an empty list, never 404.a SuggestionService host dies: the load balancer drops it and the next keystroke lands on another host, since no host holds state.
  • 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 text with text_pattern_ops makes the prefix a range scan.
  • 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

Learn from searches: every search adds one to its query's count Client submits a search to the existing Search Service, which publishes one SearchSubmitted event to SearchLog, a Kafka topic, and never waits on typeahead. SearchLog delivers batches to CountWorkers, which normalize each query, sum per query inside the batch and upsert the totals into QueryCount in Postgres. Delivery is at least once, so a redelivered batch counts its queries twice. 2) Learn from searches: every search adds one to its query's count event SearchSubmitted {query, userId, signedIn, ip, lang, ts}, published by the Search Service at least once. It is the only input. Client search box Search Service existing,out of scope SearchLog (Kafka) at least once search search search CountWorkers normalize,sum per queryin the batch QueryCount (Postgres) {text PRIMARY KEY, count}all-time count Raw, all-time counts one person or one bot can inflate a count,and a query surging today sits below anold favourite. The dives on building the indexand on trending and blocked queries fix these. the upsert: INSERT INTO query_count (text, count)VALUES ('sports scores', 3)ON CONFLICT (text) DO UPDATESET count = query_count.count + EXCLUDED.count; 1. Client submits a search 2. Search Service publishes SearchSubmitted {query, userId, signedIn, ip, lang, ts}search never waits on typeahead 3. SearchLog delivers a batch to a CountWorker 4. CountWorker upserts count = count + n one row per query the not-so-happy paths: SearchLog redelivers a batch: its queries are counted twice. A popularity ranking does not need exact counts.CountWorkers fall behind: searches still work, and counts catch up from the log.
  • The Search Service publishes one SearchSubmitted event 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

Block a suggestion: one row in Blocklist filters every read Operator sends POST /admin/blocklist to AdminService, which checks the operator role, normalizes the text and inserts one row into Blocklist. Client sends GET /suggestions to SuggestionService, which runs the prefix lookup on QueryCount with a NOT EXISTS filter on Blocklist and returns the list without the blocked query. Blocklist and QueryCount are tables in one Postgres database, so one statement reads both. 3) Block a suggestion: one row in Blocklist filters every read POST /admin/blocklist {query, reason} -> 201 {id}. Operators only. An entry is one exact normalized query. Operator admin console AdminService checks theoperator role Client search box SuggestionService stateless one Postgres database Blocklist (Postgres) {id, text, reason, addedBy, addedAt} QueryCount (Postgres) {text PRIMARY KEY, count} the prefix lookup, with the filter: SELECT text FROM query_countWHERE text LIKE 'spo%'AND NOT EXISTS (SELECT 1 FROM blocklist b WHERE b.text = query_count.text)ORDER BY count DESCLIMIT 10; 1. Operator sends POST /admin/blocklist {query, reason} 2. AdminService normalizes the text and inserts the row 3. Client sends GET /suggestions?q=spo through APIGateway, as in 1) 4. SuggestionService runs the prefix lookup, skipping blocked rows 5. SuggestionService returns the list without the blocked query NOT EXISTS:the same statementreads Blocklist the not-so-happy paths: the blocked query has never been searched: its row waits in Blocklist and applies if the query ever appears.an operator blocks the wrong query: DELETE /admin/blocklist/{id} removes the row and the next request shows it again.
  • 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.
DONE WHEN: all three requirements have a path, and you have said out loud that the prefix lookup reads millions of rows for a short prefix and that every keystroke reaches the database.
STEP 4 OF 5

Potential deep dives

~20 min, interviewer steers
TRIGGER: "the LIKE is too slow" / "what data structure" / "how do you hit 100 ms"

1) Lookup speed: how does one keystroke get its top 10 in a few milliseconds?

PRECOMPUTE THE TOP 10 FOR EVERY PREFIX · A RADIX TREE IN EACH HOST'S MEMORY · A LOOKUP WALKS, IT NEVER SORTS
Bad Solution: the prefix lookup against Postgres on every keystroke
  • 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.
Good Solution: an in-memory trie with a top 10 stored at every node
  • 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.
Great Solution: a radix tree with a top 10 at every node, in each host's memory
  • 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.
Lookup speed: a top 10 stored at every node, so a lookup walks and never sorts A radix tree runs from root down the edge sp to the node sp, which branches to speed test, spa and spo; spa branches to spain and space, and spo to sports scores and spoon. Every node stores the list of the best queries at or beneath it, best first. The lookup for spo walks the edge sp, then the edge o, and returns the list stored at spo. A prefix that ends inside an edge, such as s or spoo, returns the list at the node where that edge ends. Lookup speed: a top 10 stored at every node, so a lookup walks and never sorts A radix tree in each host's memory. A list holds 10 query ids; a chip shows an id's text and score in searches per day, 3 per list here.Fewer than 200M nodes x 40 B = 8 GB of lists, about 15 GB in all. root sp speed test 900K sports scores 700K spain 80K speed test a query speed test 900K spa spain 80K space 60K spo sports scores 700K spoon 5K spain a query spain 80K space a query space 60K sports scores a query sports scores 700K spoon a query spoon 5K 1. For q = "spo", SuggestionService walks the edge "sp" "sp" q = "s"ends inside the edge:return the list at sp 2. SuggestionService walks the edge "o" and returns the list stored at spo "eed test" "a" "o" "in" "ce" "rts scores" "on" q = "spoo"ends inside the edge:return the list at spoon built bottom-up: a node's list isthe best 10 from its children's lists,plus itself if it is a query. three lookups: q = "spo" -> 2 hops (sp, o): return the list at spoq = "s" -> ends inside the edge "sp": return the list at spq = "spoo" -> ends inside the edge "on": return the list at spoon the not-so-happy paths: the prefix matches no edge: the walk stops and the response is an empty list.the same lookup with no stored lists would visit every query under the node: at least 10M under "s", at least 1 s.
TRIGGER: "how does the trie get updated" / "a search just happened, now what" / "what if the build is bad" / "can someone game the suggestions"

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?

COUNT OFFLINE · BUILD ONE IMMUTABLE SNAPSHOT · CHECK IT, CANARY IT · EVERY HOST SWAPS ONE POINTER
Bad Solution: update the index in place on every search
  • 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.
Good Solution: count offline in a daily batch, and let each host rebuild its own trie
  • 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.
Great Solution: one immutable snapshot, built offline, checked, and swapped with one pointer
  • 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.
  • 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 signedIn and ip fields carry what that needs.
    • Beyond that, abuse detection is out of scope.
  • 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.
Building the index: count offline, build one snapshot, swap one pointer Search Service publishes each search to SearchLog, which is archived to LogArchive. DailyAggregateJob reads yesterday's events and writes one aggregate a day to LogArchive. IndexBuilder scores the last 30 aggregates and writes snapshot v412 to SnapshotStore only if it passes the checks. A SuggestionService host downloads v412, memory-maps it beside v411 and verifies the checksum, then moves its current pointer from v411 to v412. Building the index: count offline, build one snapshot, swap one pointer 5B searches a day are 500 GB of log. The index is built once and shipped as an immutable file; hosts only load it. Search Service existing SearchLog (Kafka) at least once search search search LogArchive object storage:raw events by day,daily aggregates DailyAggregateJob Spark, once a dayper query: count +HyperLogLog sketchof distinct users IndexBuilder scores 30 days,7-day half-life;>= 100 distinct users;drops blocked queries;checks the snapshot SnapshotStore object storage,snapshot v412+ checksum, keepsprevious versions 1. Search Service publishes each search 2. SearchLog is archived to object storage 3. DailyAggregateJob reads yesterday's events 4. Daily aggregates, stored in LogArchive, feed IndexBuilder 5. IndexBuilder writes snapshot v412 only if it passes the checks:size within 10% of v411,well-known prefixesreturn full lists SuggestionService host index v411 serving index v412 loaded beside it current 6. Host downloads v412, memory-maps itbeside v411 and verifies the checksum before the swap 7. Host swaps one pointer requests in flightfinish on v411;then it isunmapped, and thefile stays on disk rollout: one canary host, then 10% of hosts at a time,watching errors, latency and the empty-list rate. the not-so-happy paths: the build is bad (half the queries missing): the checks fail, v412 is never published, and hosts keep serving v411.a bad snapshot passes the checks: the canary's empty-list rate jumps, the rollout stops, and hosts point back at v411, still on disk.hosts are on v411 and v412 for the length of the rollout, up to an hour: two keystrokes can be answered by different versions.The availability-over-consistency target allows that.a host restarts: it reloads the last snapshot and blocklist from local disk, and passes its health check only once it holds both.
Between the two batch jobs: daily aggregates in LogArchive LogArchive is object storage with two buckets, one for raw events by day and one for daily aggregates. DailyAggregateJob reads yesterday's raw events from the first bucket and writes yesterday's aggregate to the second, one row per query with a count and a HyperLogLog sketch. IndexBuilder reads the last 30 aggregates from the second bucket and writes the snapshot to SnapshotStore. The two jobs share only what is stored in LogArchive and never call each other. Between the two batch jobs: daily aggregates in LogArchive Step 4 of the previous figure in full. The two jobs share only what is stored in LogArchive: a bucket of raw events by day, and a bucket with one aggregate a day. LogArchive: object storage, one account, two buckets DailyAggregateJob Spark, once a day:reduces a day ofraw events to onerow per query raw events one bucket, by day: 500 GB a day, 15 TB for 30 days yesterday 2 days ago ... 30 days ago daily aggregates a second bucket, one aggregate a day;a row per query: count + HyperLogLog sketch yesterday 2 days ago ... 30 days ago one added a day; IndexBuilder reads all 30 IndexBuilder 30 daily counts -> score(7-day half-life);30 sketches merged ->30-day distinct users;keeps those with >= 100 SnapshotStore object storage 1. DailyAggregateJob reads yesterday's raw events 2. DailyAggregateJob writes yesterday's aggregate 3. IndexBuilder reads the last 30 aggregates 4. IndexBuilder writes the snapshot only if it passes the checks why object storage between the jobs, and not a queue or a database: a failed or wrong day is rerun alone and overwrites that day's aggregate; an append-only queue cannot replace a day.IndexBuilder reads each aggregate whole on 30 consecutive builds and never looks up one row by key,so a database index would go unused. why two jobs, and what orders them: each day's raw events are reduced once; without the aggregates every build would rescan 15 TB.the jobs never call each other: a workflow scheduler (such as Airflow) starts IndexBuilderonce yesterday's aggregate is written.
TRIGGER: "breaking news" / "how fresh are suggestions" / "legal wants a suggestion gone now"

3) Trending and blocked queries: the index is rebuilt once a day, so how does a change show in minutes?

A TRENDING DELTA FROM A STREAM JOB · THE BLOCKLIST IN EVERY HOST'S MEMORY · BOTH APPLIED AT REQUEST TIME
Bad Solution: wait for the daily build
  • 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.
Good Solution: count and build every hour
  • 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.
Great Solution: a trending delta and an in-memory blocklist, applied to each response
  • 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.
  • 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.
  • 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.
Trending and blocked queries: two small things applied to each response SearchLog feeds TrendingJob, which writes the trending delta to SnapshotStore every minute; each SuggestionService host checks for a new delta every 10 s. AdminService inserts a blocked query into Blocklist, and each host polls it every 10 s into an in-memory blocklist set. A request looks its prefix up in the base index and in the trending delta, merges the two lists by score, drops blocked queries and returns the top 10 to the Client. Trending and blocked queries: two small things applied to each response The base index is a day old. The trending delta is replaced every minute and the blocklist is polled every 10 s. SearchLog (Kafka) search search search TrendingJob Flink, 15-minute window,advances every minutetrending: >= 1,000 distinctusers and >= 3x base score(leaves below 2x) SnapshotStore object storage,holds the delta file SuggestionService host: all three in memory base index daily snapshot,score = searches per day trending delta prefix -> trending queries,text + scores, at most 3per prefix, under 20 MB blocklist set hash set in memory q = "ecl", one request: base eclipse glasses 30K eclectic 8Kdelta eclipse live stream 192K (2,000 in 15 min x 96)merged eclipse live stream 192K eclipse glasses 30K eclectic 8K Client Operator AdminService Blocklist (Postgres) source of truth 1. SearchLog feeds TrendingJob 2. TrendingJob writes the delta every minute score = window count x 96 3. Host checks for a new delta every 10 s 4. AdminService inserts the blocked query 5. Host polls every 10 sfor a blocklist change 6. Client sends GET /suggestions?q=ecl 7. Host looks up "ecl" in the base index and in the delta the filter, in step 8 8. Host merges by score, drops blocked queries, returns the top 10 the not-so-happy paths: TrendingJob is down: a host drops a delta older than 5 minutes and serves the base index alone, so old trends are not pinned.a query is in both: the merge matches it by text and keeps the higher score, so it appears once.a blocked query is in the base index: the filter drops it, and the list returns 9 until the next daily build.
TRIGGER: "a request per keystroke?" / "what does the client do" / "can you cache this"

4) Request volume: how do you keep 2.3M suggestion requests a second from all reaching the hosts?

DEBOUNCE AND A CLIENT CACHE · ONE CACHEABLE GET · THE CDN ANSWERS THE HOT PREFIXES FOR 30 SECONDS
Bad Solution: a request on every keystroke, rendered as it arrives
  • 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.
Good Solution: fix the client with debounce, a client cache and a check on each response
  • 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 q equals 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.
Great Solution: one cacheable GET that a CDN answers for 30 seconds
  • 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=0 to 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 Age header, 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.
TRIGGER: "how do you shard the trie" / "add 50 languages" / "10x the queries"

5) Outgrowing one host: the whole index sits in each host's memory, so how do you split it when it no longer fits?

ONE INDEX PER LANGUAGE · SHARDS BY PREFIX RANGE · BOUNDARIES SET FROM MEASURED SUBTREE SIZES · EVERY LOOKUP HITS ONE SHARD
  • 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.
Bad Solution: shard by first character
  • 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.
Good Solution: one index per language
  • 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.
Great Solution: shards by prefix range, with boundaries set from measured subtree sizes, behind a router
  • 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.
DONE WHEN: you have taken two or three dives to their Great answer, said "the top 10 is computed before the request, so a keystroke only reads a list", and said "the index is an immutable snapshot that every host swaps with one pointer".
FLASHCARDS · THE FIVE HARDEST PROBESshow all (interview mode)
You have a trie in memory. Why not walk the subtree and collect the top 10 on each request?
  • 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.
A search just happened. Why not update the index right away?
  • 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 query starts trending at 9 am. How does it show within 5 minutes of passing the trending threshold, and how is its score compared with scores in the base index?
  • 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.
Legal blocks a suggestion. The index is a day old and responses sit in CDN and browser caches. How is it gone within a minute?
  • 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=0 forbids a cache from serving an expired entry when hosts return errors.
  • The next daily build drops the query at the source.
The index no longer fits on one host. How do you shard it, and why not by first character?
  • 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.
STEP 5 OF 5

Final design + what is expected at each level

wrap

Final Design

Typeahead: final design. Rank ahead of time, read from memory A request goes from the Client through the CDN and APIGateway to a SuggestionService host, which answers from its own memory. Each search also goes to the Search Service and into SearchLog; the log is archived, DailyAggregateJob reduces it to daily aggregates kept in LogArchive, IndexBuilder writes a versioned snapshot to SnapshotStore, and hosts download it. TrendingJob reads SearchLog and writes the trending delta to SnapshotStore every minute, and each host checks for a new one every 10 s. AdminService writes the Blocklist, which hosts poll every 10 s and IndexBuilder reads. Typeahead: final design. Rank ahead of time, read from memory Once a request reaches a host, the host calls nothing and does a small, fixed amount of work.Everything it reads was built before the request arrived: the base index, the trending delta and the blocklist. Client debounce,30 s client cache,drops out-of-orderresponses CDN Cache-Control:public, max-age=30,must-revalidate,stale-if-error=0 APIGateway load balancer SuggestionService at least 115 hosts for theglobal peak; the serving sideis repeated in each region.In memory on each host:base index (radix tree, top 10at every node, about 15 GB),trending delta, blocklist set Search Service existing SearchLog (Kafka) at least once search search search TrendingJob Flink, 15-minute window,advances every minute SnapshotStore object storage:versioned snapshots+ checksum, trending delta LogArchive object storage:500 GB a day,daily aggregates DailyAggregateJob Spark, dailycount + distinct-usersketch per query IndexBuilder 30 days, 7-day half-life;>= 100 distinct users;builds the radix tree;checks the snapshot Blocklist (Postgres) source of truth Operator admin console AdminService operator role 1. Client sends GET /suggestions ?q={prefix} 2. CDN forwards a miss a hit is answeredat the edge 3. APIGateway forwards to any host on the host: threein-memory lookups andone merge of at most13 entries 4. Client submits a search 5. Search Service publishes SearchSubmitted 6. SearchLog is archived 7. DailyAggregateJob reads yesterday's events 8. Daily aggregates, stored in LogArchive, feed IndexBuilder 9. IndexBuilder writes a versioned snapshot 10. Hosts download the snapshot,load it beside the currentone, swap one pointer canary host first,then 10% at a time hosts also checkevery 10 s for a newtrending delta 11. SearchLog feeds TrendingJob 12. TrendingJob writes the trending delta every minute 14. Hosts poll theblocklist every 10 s 13. AdminServicewrites the Blocklist 15. IndexBuilder reads the Blocklist and drops blockedqueries from thesnapshot growth: one index and pool per language. Past one host: shards by prefix range, boundaries set from measured subtree sizes,behind a router with a versioned shard map. Every lookup hits one shard. the not-so-happy paths: the daily build is bad: the checks or the canary stop it, and hosts keep the previous snapshot.a dependency is down: running hosts keep serving from memory. Without Kafka or object storage, trends drop out after 5 minutes; without Postgres, no new block lands.a query surges: within 2.5 minutes of passing the trending threshold it shows in suggestions, ahead of base entries with a lower score.a suggestion is blocked: 10 s poll + 30 s cache lifetime = gone within 40 s; the next build drops it at the source.hosts are slow or shed load (503): the CDN serves nothing stale, the client shows no list and pauses for a few seconds, and search still works.
  • 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.
DONE WHEN: you have pointed at the final diagram, named its four parts (the radix tree in each host's memory, the daily snapshot swap, the trending delta and blocklist, the 30-second CDN), and closed on the invariant: "once a request reaches a host, the host calls nothing and does a small, fixed amount of work."