In this article
Before you start
This page belongs to the system design interview learning path. It uses quick sizing arithmetic and the idea of a database index.
Why interviewers ask this
A search system forces you to combine storage layout, distributed fan-out and freshness in one design, so the prompt tests whether you can reason about all three. Candidates have reported prompts such as a distributed search system for a billion documents and a million queries per second, an inverted index over a stream of posts, and a typeahead (autocomplete) system; these are candidate reports, not confirmed company practice.
A weak answer says "put the documents in a database and run a substring match on every row," which scans the whole table. A strong answer names the inverted index, explains how queries and writes reach shards, and sizes the cluster from stated assumptions. A Staff-level answer adds what the fan-out does to tail latency, why new documents appear after a delay, and why typeahead is its own path with its own data structure.
Search backend from first principles
- Postings list
- A postings list is the sorted list of document numbers, one list per term, stored inside an inverted index. Each entry may also hold the term's count or positions in that document, which ranking and phrase queries use.
- Scatter-gather
- Scatter-gather is a query pattern in which a coordinator sends one search to every shard, then merges the shards' best results into one final list. The slowest shard decides when the coordinator can answer.
In plain words
Think of the index at the back of a textbook. You do not read the book to find "photosynthesis"; you look up the word and get page numbers. A search backend builds that back-of-book index for every document, then keeps it fresh and spreads it over many machines. The analogy breaks in one place. A book index lists each word once, while a search index must also rank pages, merge several words and accept new pages every second.
In one precise sentence, a search backend stores a term-to-documents map, splits it by document across shards, runs each query on every shard, and merges the results.
Step 1: Analyze documents and build an inverted index
Analysis turns each document's text into terms: split on word boundaries, lower-case, drop very common words and reduce words to a root form. Each term then gets a postings list of the documents that contain it, kept sorted by document number, as in the textbook by Manning, Raghavan and Schütze (2008). For a query about "red shoes," the engine fetches two sorted lists and intersects them in one pass.
Input: raw documents. Output: a dictionary of terms and a postings list per term. A substring-match query on a table must read every row, while this lookup reads only the lists for the query's terms. You now know the data structure; the next step uses it to answer one query on one machine.
Step 2: Answer a query on one shard
A shard receives the query terms, fetches each term's postings list, and intersects the lists to keep documents that contain every word (an AND query). Each surviving document gets a relevance score. A common scoring family combines how often a term appears in a document with how rare the term is across the corpus, as in term frequency (TF) with inverse document frequency (IDF), called TF-IDF, and Best Matching 25 (BM25); the shard keeps only its top few results.
Input: query terms. Output: that shard's top results with scores. Keeping only a short top list matters, because sending every match upstream would swamp the network. A shard answers alone, so correctness of the merge in step 3 depends on each shard returning enough candidates. Each shard computes IDF from its own documents, so scores are not directly comparable across shards unless statistics are shared. To return a deep page, each shard must return the page offset plus the page size in candidates, which makes deep pagination expensive.
Step 3: Scatter-gather makes the slowest shard set the latency
When the index is too big or too busy for one machine, you split it by document into shards. A coordinator receives the query, scatters it to one copy of every shard, gathers each shard's top results and merges them into the final list. A second round then fetches the stored fields, such as the title, for only the winning documents.
Input: one user query. Output: one merged result list. The catch is tail latency: the coordinator waits for the slowest shard, so a rare slow reply on any shard becomes a slow query. If each shard is slow on one query in a hundred (illustrative), a query touching sixteen shards is slow about 14.85% of the time.1 You now see why shard count is a cost, not just a capacity knob.
How does a new document reach the right shard?
A new document reaches its shard through a write path that is separate from the query path. The source-of-truth database, where documents live, emits each change onto a queue or log. Indexer workers read that log, analyze each document into terms and route it by a hash of the document ID modulo the shard count to one primary shard, which then copies the change to that shard's replicas.
Each shard turns its writes into segments, as the next step shows. A full reindex builds a complete new index beside the old one from the source of truth, and readers switch over only when it is finished. Because routing depends on the shard count, changing that count later means reindexing, so choose it with room to grow.
Step 4: Keep the index fresh with segments, refresh and merge
A segment is an immutable, searchable slice of an index written from a batch of new documents; it is never edited, only replaced. New documents wait in an in-memory buffer, and the step called refresh writes that buffer to a new segment and opens it for search. Elastic's documentation states that by default Elasticsearch refreshes every second, but only on indices that received a search in the last 30 seconds, which is why its search is called near real-time.
Frequent refreshes create many small segments, and a query must check each one. A background process merges small segments into larger ones and drops deleted documents. At a one-second refresh an active shard could create 3,600 segments in an hour if nothing merged them (illustrative).1
Step 5: Serve typeahead from a separate prefix store
Typeahead is the feature that suggests completions while a user types, and it is a different path from full search. A full query intersects postings lists and scores documents, which is too slow and too broad for every keystroke. Instead, you precompute the best few suggestions for each prefix from query logs and store them in a prefix structure, such as a trie (a tree keyed by characters) or a finite-state transducer (FST), an in-memory structure that compresses shared prefixes.
Input: the characters typed so far. Output: a short list of suggestions. Rebuild the table on a schedule from recent query counts, and let it lag the logs. Store the top few completions at each trie node, so a lookup is a walk down the prefix with no scoring, and debounce requests on the client to stay inside a per-keystroke latency budget. The suggestion lists alone take at most about 6 GB for ten million popular queries, which fits in memory (illustrative).1
Step-by-step description
- Documents become an inverted index.
- A shard intersects postings lists.
- A coordinator scatters to every shard and merges.
- New segments make documents searchable.
- Query logs build the prefix store.
- An inverted index maps each term to the documents that contain it.
- A coordinator merges the best results returned by every shard.
- A refresh writes new segments that become searchable.
- Typeahead reads a separate prefix store.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Size a search backend for a billion documents and a million queries per second, the scale in a prompt candidates have reported. The inputs are assumptions, not measurements: 200 distinct terms per document, 2 bytes per compressed postings entry, 25 GB per shard and 1,000 queries per second (QPS) per shard copy, all illustrative.1 See back-of-the-envelope estimation for the method.
The index holds 200,000,000,000 postings entries, or 400 GB, so 16 shards of 25 GB cover it.1 Every query visits every shard, so each shard must absorb the full million queries per second. At 1,000 QPS per copy, that is 1,000 copies of each shard, or 16,000 shard copies in total.1 If a result cache absorbs half of the queries (an illustrative hit rate), 500,000 queries reach the index, which needs 500 copies per shard, or 8,000 in total.1
| Quantity | Value (computed from illustrative inputs) |
|---|---|
| Postings entries for 1,000,000,000 documents | 200,000,000,000 |
| Index size at 2 bytes per entry | 400 GB |
| Shards at 25 GB each | 16 |
| Shard copies, no cache, 1,000,000 QPS | 16,000 |
| Shard copies, half the queries cached | 8,000 |
| Queries touching a slow shard, 1 shard | 1% |
| Queries touching a slow shard, 16 shards | 14.85% |
| Queries touching a slow shard, 64 shards | 47.44% |
Text description of the diagram
- Each shard is slow on one query in a hundred, an illustrative assumption.
- With sixteen shards about 14.85% of queries touch a slow shard.
- With sixty-four shards about 47.44% of queries touch a slow shard.
The slow-query share is one minus 0.99 raised to the number of shards, assuming independent shards that are each slow on one query in a hundred (illustrative).1 With sixty-four shards, about 47.44% of queries touch a slow shard.1 The chart shows why a design avoids needless shards and hedges slow replies by sending a second request to another copy, a technique described by Dean and Barroso (2013).
Trade-offs and edge cases
Partitioning by document is the usual choice, because each shard can answer fully for its own documents and a lost shard loses only its documents. The alternative, partitioning by term, sends a query only to the machines holding its terms, but multi-word queries must ship long postings lists between machines and popular terms create hot spots.
Text description of the diagram
- Partitioning by document sends every query to every shard.
- Partitioning by term sends a query only to the machines holding its terms but moves long postings lists.
Edge cases to name: a new or deleted document is visible only after the next refresh, so say "near real-time," not "real-time." Ranking quality and speed pull apart, since a deeper scoring pass on the top candidates costs more per query. A hot query, such as a trending term, is best served from a result cache, much as a distributed cache absorbs hot keys.
A streaming ingest path that updates the index from a feed has the same shape as an event aggregation pipeline. For large language model (LLM) features that sit beside search, such as answer generation, keep them in a separate service so their latency does not enter the retrieval path; reported prompts mix the two, so state that boundary.
How to answer it in an interview
How would you design a search backend?
I would build an inverted index: each term maps to a sorted list of documents, so a query reads only its own terms' lists. I split the index by document into shards, send each query to one copy of every shard, and have a coordinator merge the top results. I would size it from assumptions I state out loud. The trade-off is that the slowest shard sets the latency, so I cap shard count, cache hot queries and hedge slow replies. Writes are routed by a hash of the document ID. Typeahead gets its own prefix store, rebuilt from query logs.
The spoken structure: say the index, then the sharding and merge, then the sizing, then the latency trade-off, then typeahead.
Common mistakes
- "I would store documents in a database and run a substring match." (wrong) That scans every row. (right) "I would build an inverted index so a query reads only the lists for its terms."
- "Search is real-time." (wrong) New documents appear after a refresh. (right) "It is near real-time: by default Elasticsearch refreshes every second on an index that is being searched, so a write is visible within about that time."
- "More shards always means faster." (wrong) Every query visits every shard, so more shards add tail latency and coordination. (right) "I pick the fewest shards that fit the size target and cache hot queries."
- "Typeahead is just search on each keystroke." (wrong) A full query is too heavy for every keystroke. (right) "Typeahead reads a precomputed prefix-to-suggestions store."
- "I need no numbers." (wrong) The prompt names a scale. (right) "I state the assumptions, then derive shard count and copies."
Follow-up questions
How does a search engine fetch and show search results?
A web search engine crawls pages, builds an index from them, and serves each query from that index. The serving half is the shard lookup and merge described above; the crawling half is a separate pipeline that feeds new documents in.
How would you scale the search architecture?
Add shards when the index outgrows a machine, add replicas of each shard when query volume grows, and put a result cache in front for hot queries. Watch the fan-out, because more shards raise tail latency. See the backend interview questions for neighboring scaling topics.
How do you design typeahead and a search backend together?
Treat them as two read paths over different data: full search reads the inverted index, while typeahead reads a prefix store of precomputed suggestions rebuilt from query logs. They share ingestion and logging but not the serving structure.
How do new documents become searchable?
A write goes into an in-memory buffer, and the next refresh turns the buffer into a new searchable segment. Elasticsearch documents a default of one second; background merging keeps the segment count down.
Should you shard by document or by term?
Shard by document in most designs: shards stay independent and failures stay local, at the price of a fan-out on every query. Sharding by term avoids the fan-out but moves long postings lists between machines.
How do you protect the search service under load?
Limit callers at the edge with a distributed rate limiter, cache hot queries, and shed or degrade expensive queries before they reach the shards.
- An inverted index maps each term to a sorted postings list, so a query reads only its own terms' lists.
- Split the index by document into shards; a coordinator scatters each query and merges the top results.
- The slowest shard sets query latency, so shard count has a cost.
- Route each write by a hash of the document ID to one primary shard, then copy it to that shard's replicas.
- New documents appear after a refresh, which makes search near real-time.
- Typeahead uses a separate precomputed prefix store, not the full search path.
Sources
- Near real-time search (Elasticsearch documentation) — Elastic (page read 2026-10-26), 26 Oct 2026
- The Tail at Scale — Google Research (Dean and Barroso, Communications of the ACM 2013), 1 Feb 2013
- Introduction to Information Retrieval — Cambridge University Press (Manning, Raghavan, Schütze), 7 Apr 2008
