Design a web search engine: the system design interview walkthrough

Design a web search engine: the system design interview walkthrough

The request to design a web search engine sounds impossibly large — "build Google" — and that size is exactly the trap. The sentence hides three separate systems: a crawler that discovers pages, an indexer that turns them into something searchable, and a serving layer that answers a query in the blink of an eye. A strong candidate says that out loud in the first minute, scopes the crawler to its own problem, and names what this round is really about: given a corpus that has already been crawled, how do you answer a text query against billions of documents in well under a second and return the best results, not just the matching ones. That reframe — search engine system design is a top-K retrieval problem, not a crawling problem — is the move that turns an unanswerable prompt into a 45-minute design.

Underneath the reframe is one data structure and one hard operation. The data structure is the inverted index: instead of asking "what words does this document contain," you flip it to "what documents contain this word," so a query becomes a lookup, not a scan. The hard operation is doing that lookup across an index far too big for one machine, which forces you to shard by document and answer every query as a scatter-gather — fan the query out to every shard in parallel, let each return its local best, and merge. Get that spine — an offline pipeline builds an inverted index, the index is sharded by document and queried by scatter-gather, and a ranking function decides the order — and the rest of the system design interview is deciding how the index is built, how the fan-out stays fast, and how you rank two matching pages against each other. This walkthrough follows the path a strong candidate draws on the whiteboard — requirements, estimate, API and data model, high-level design, then the deep dives — naming the follow-up the interviewer uses at each step to tell a memorised answer from real understanding.

How the web search round is actually run

A web search round runs about 45 minutes on a shared canvas — you draw the boxes and arrows while you talk, and the interviewer interrupts. It is a favourite because the one-line problem is so obviously too big that it immediately tests whether you can scope: the candidates who try to design the crawler, the ranking machine-learning model, and the serving layer all at once run out of clock with nothing finished. The ones who score say "three systems; I'll scope the crawler out and design indexing and serving," and spend their minutes where the depth is.

The interviewer rarely lets "I'd build an index and search it" stand. "Your corpus is a hundred billion documents and the index is tens of terabytes — it cannot live on one machine. How do you split it, and how does a single query still come back in under a second?" That question — retrieval at a scale no single node can hold — is the one a copied answer can never rehearse, and the one this round is really testing.

The rounds here are modelled on how the loop runs, not scraped from any candidate's recall. What matters for prep is the shape: a blank canvas, a prompt too big to take literally, and a follow-up after every decision you make.

The five-step framework for any HLD round

Every high-level design answer fits the same spine. Say it out loud at the start so the interviewer knows you have a plan, then walk it:

1. Clarify requirements — functional and non-functional, and what you are explicitly not building.
2. Estimate — corpus size and query volume, to justify why the index must be sharded and the query fanned out.
3. High-level design — the boxes and arrows: the offline indexing pipeline, the document-sharded query servers, the coordinator, and ranking.
4. Deep dive — the two or three decisions that actually decide this system.
5. Follow-ups — bottlenecks, failure modes, and what you would change at ten times the scale.

What the debrief measures

The score is not "right or wrong design." A good HLD debrief reads on four dimensions, and every move below maps to one: problem solving (did you reframe it as top-K retrieval over an inverted index and scope the crawler out), communication (did you say in one sentence why document-sharding beats term-sharding, and why retrieval and ranking are two separate phases), technical execution (an offline pipeline producing an inverted index, document shards with replicas, a coordinator merging per-shard top-K, and a ranker), and time management (did you spend your 45 minutes on the index, serving and ranking, not on the crawler or the search box UI). Reading a walkthrough teaches the design; it does not teach you to deliver it on the clock while someone pushes back.

Step 1 — Requirements: what a web search engine must do

Spend the first few minutes here. Jumping to boxes before you have scoped the problem is the fastest way to design the wrong system — and for this prompt, scoping is the first scored move.

The sentence that earns points: "This is really three systems — crawl, index, serve — and this round is the serve half. Assume a crawled corpus; I'll design an inverted index, document-sharded query serving, and ranking, and treat the crawler as a separate problem." Say that and you have framed the entire design — and shown judgement — before drawing a box.

Step 2 — Capacity estimation (back of the envelope)

Estimation here is about proving two things: the index is far too big for one machine, and the query rate is far too high to recompute anything per request — so the index must be partitioned and the popular results cached.

Two conclusions fall out, and you should say both out loud. First, there are two regimes that barely touch: offline indexing is a throughput problem (process the whole corpus into an index), while online serving is a latency problem (answer one query fast) — design them separately. Second, because no machine can hold the index and no request can afford a scan, the system is defined by partitioning the index by document and fanning each query out in parallel to all partitions. You have now pointed the interview at the real deep dives — building the index, serving the query across shards, and ranking — before anyone asked.

Step 3 — API and data model

The external API is tiny — one endpoint. The interesting model is internal: the inverted index and the document store.

The data model has three parts. The inverted index is the heart; the document store holds what you show the user; the query cache is an optimisation:

Step 4 — High-level design: indexing pipeline, query serving and ranking

Now the boxes. Split the picture into the offline path that builds the index and the online path that serves a query:

• Indexing pipeline (offline, batch): reads the crawled corpus, tokenises and normalises each document, and builds the inverted index. It is a throughput job (MapReduce-style) that produces an immutable index shipped out to the query servers.
• Query servers, sharded by document: the index is split into shards, each holding the full inverted index over a slice of the corpus. Every shard is replicated for throughput and availability.
• Coordinator / aggregator: receives the parsed query, scatter-gathers it to every shard in parallel, collects each shard's local top-K, and merges them into a global top-K.
• Ranking: a cheap retrieve inside each shard, then an expensive rerank of the merged candidates using text relevance plus query-independent authority.
• Query cache: sits in front of the coordinator and returns the stored ranked page for popular queries without touching the shards.
• Document store: holds url/title/snippet/authority for rendering results and for ranking.

Say explicitly that the document is the unit of partitioning: each shard can answer a whole query over its slice by itself, so the coordinator never ships posting lists between nodes — it only merges small top-K lists. Naming that — an offline-built inverted index, document-sharded and queried by scatter-gather, then reranked and cached — is a signal the interviewer is listening for.

Deep dive: building the inverted index

This is the structure the whole system is built on, so expect the interviewer to make you build it from a raw document. The follow-up is concrete: you have the text of a page — walk me from that to something a query can hit in milliseconds.

The answer is a pipeline that flips documents into terms. For each crawled document:

• Tokenise: split the text into terms (words), handling punctuation and case.
• Normalise: lowercase, stem (so "running" and "run" match), and drop very common stopwords — so queries match regardless of surface form.
• Emit postings: for each term, record a posting (doc_id, positions, term_frequency). Positions are what later let you answer a phrase query ("brown fox" as an ordered pair, not two separate words).
• Group by term: invert and collect every posting for a term into its posting list. The result is the inverted index: term -> [posting, posting, ...].

Two properties decide how you operate it. First, this is an offline batch job — a throughput problem over the whole corpus, naturally a MapReduce-style map (document to postings) and reduce (group by term). Second, the built index is treated as immutable: you do not edit posting lists in place under live queries. Freshness comes from building incremental segments — small indexes over new or changed pages — and merging them into the query path, so a query reads the main index plus the recent segments. State the trade-off plainly: a bigger batch cadence is cheaper but staler; incremental segments buy freshness at the cost of more merge work and more segments to search.

"How do you keep the index fresh without rebuilding it from scratch every time a page changes?" You don't rebuild. The main index is immutable and built in batch; new and changed pages are indexed into small incremental segments that are merged into the serving path, so a query reads the big index plus a handful of recent segments. Periodically the segments are compacted back into the main index. Freshness is a cadence-versus-cost dial, not a live edit.

System Design
HLD · Search & discovery · 45 min
Build the inverted index out loud, with follow-ups

Practise on Zynter →

Deep dive: query serving at scale (document sharding and scatter-gather)

This is the decision the scale follow-up forces. The probe: the index is sharded across a thousand machines — how does one query use all of them and still return in under a second?

Start with how a single query works on one index. Parse it into terms; for each term, fetch its posting list; then intersect the lists (for an AND query, keep only documents that appear in every term's list) to get the candidate set. Now scale it:

• Shard by document: split the corpus into slices and give each shard the full inverted index over its slice. Crucially, a shard can answer the whole multi-term query over its own documents with no help from other shards.
• Scatter-gather: the coordinator sends the query to every shard in parallel. Each shard retrieves its candidates, ranks them locally, and returns only its local top-K (say, its best 100). The coordinator merges the per-shard top-Ks into the global top-K.
• Replicate each shard: multiple replicas per shard serve the QPS and provide availability; the coordinator can send hedged requests so one slow replica doesn't drag the whole query.
• Why document-sharding, not term-sharding: if you instead split by term (each node owns some terms' posting lists), a multi-term query must ship huge posting lists between nodes to intersect them, and popular terms turn their node into a hotspot. Document-sharding keeps every query local to each shard, makes fan-out uniform, and lets you grow by simply adding shards.

The point to state plainly: the coordinator never moves posting lists around — it only fans out the query and merges small top-K lists, so the network cost per query is tiny and constant. The latency is set by the slowest shard, which is why replicas and hedging matter. This is the same scatter-gather shape behind most large search and analytics systems.

"A query has to touch every shard — how is that fast?" Because every shard works in parallel and each only returns its local top-K — a few hundred bytes — not raw posting lists. The coordinator fans out once, waits for the shards (hedging around slow replicas), and merges small sorted lists into the global top results. Fan-out is parallel, the per-shard work is bounded by top-K, and the network payload is tiny; the tail latency is the slowest shard, so we replicate and hedge.

System Design
HLD · Search & discovery · 45 min
Defend the scatter-gather sharding out loud

Practise on Zynter →

Deep dive: ranking, relevance and caching

Retrieval finds the documents that match; ranking decides which comes first — and this is where "which one is at the top, and why" is decided. The follow-up is the comparison: two pages both contain every query word — how do you order them?

The answer is a score that blends what the query says with what the corpus and the web say about each document:

• Text relevance (query-dependent): a function of how well the document matches the query terms — TF-IDF or BM25: a term counts for more when it appears often in this document (term frequency) and is rare across the corpus (inverse document frequency), with BM25 adding length normalisation so long documents don't win by sheer size.
• Authority and quality (query-independent): signals computed ahead of time — a link-based authority score (the PageRank-style idea that a page linked to by many good pages is itself good), freshness, and quality signals. These are stored per document and don't depend on the query.
• Two-phase retrieve-then-rerank: each shard does a cheap retrieve to a few thousand candidates using a simple score; the coordinator then reranks the merged top candidates with the expensive full feature set (including authority and, in a real system, learned ranking). You only pay the expensive model on a small, promising set.
• Caching: because the query distribution is heavy-tailed, cache the ranked results of popular queries so they skip the shards entirely. Age the cache against a freshness budget — the trade-off is serving a slightly stale top result cheaply versus recomputing for freshness.

The point to state plainly: matching and ordering are two different problems. Retrieval is about correctness (did we find every candidate) and is cheap and parallel; ranking is about quality (is the best one first) and is where the expensive signals live, applied late to a small set. Say that split out loud and the follow-up about ordering answers itself.

"Two documents both match every word — which one is first, and why?" The one with the higher combined score. Text relevance (BM25 — the query terms are frequent in the document and rare across the corpus, normalised for length) says how well it matches; query-independent authority (a PageRank-like link score) and freshness say how much to trust it. We retrieve cheaply to a few thousand candidates per shard, merge, then rerank the top of that merged set with the full, expensive signals — so the ordering reflects both the match and the document's standing, without scoring billions of pages.

The follow-ups that decide the web search round

Scan the probes from each deep dive and they rhyme. Master these five and you are ready for a version of the question that is not drawn exactly like this one.

• "Isn't this just building Google? Where do you start?" → It's three systems — crawl, index, serve. Scope the crawler out as its own problem and design the serve half: an inverted index, built offline, sharded by document, queried by scatter-gather, then ranked. (problem solving)
• "The index is tens of terabytes — how do you split it?" → Shard by document: each shard holds the full inverted index over a slice of the corpus, so it can answer any query locally; replicate each shard for QPS and availability. (technical execution)
• "A query touches every shard — how is that fast?" → Parallel scatter-gather; each shard returns only its local top-K, and the coordinator merges small sorted lists — tiny network payload. Tail latency is the slowest shard, so we hedge across replicas. (technical execution)
• "Why document sharding and not term sharding?" → Term sharding forces multi-term queries to ship big posting lists between nodes and turns popular terms into hotspots; document sharding keeps every query local to each shard and scales by adding shards. (communication)
• "Two pages both match — which ranks first?" → The higher combined score: BM25 text relevance plus query-independent authority (PageRank-like) and freshness, applied as a cheap retrieve then an expensive rerank of the merged top candidates. (problem solving)

Each maps to a debrief dimension. Reading this list teaches you the answers; it does not teach you to deliver them while someone interrupts — that only comes from saying them out loud.

How to prepare: a one-week plan

You do not need fifty systems. You need this one cold and the framework automatic, so the next "design X" is just new nouns in the same five steps.

• Days 1–2: Learn the five-step framework until it is reflex. Do the web search engine end to end on paper — requirements (scope the crawler out), estimate, API, data model, and the indexing/serving/ranking boxes.
• Days 3–4: Drill the inverted index: tokenise, normalise, postings with positions, offline batch build, immutable index plus incremental segments for freshness. Say each step in one sentence.
• Days 5–6: Own serving and ranking — document sharding, scatter-gather with per-shard top-K, why document beats term sharding, and BM25 + authority with two-phase retrieve-then-rerank and a query cache. Answer each of the five follow-ups out loud.
• Day 7: A full timed 45-minute round, narrating the whole way, with someone (or something) interrupting. This is the rep that counts.

This post is the deep walkthrough behind one row of the broader Top 25 system design interview questions — once the web search engine is automatic, the same spine carries the rest of the list.

Frequently asked questions

How do I design a web search engine step by step?

Follow the five-step HLD framework. Clarify requirements (accept a text query and return a ranked list of relevant documents with url, title and snippet, support multi-term and phrase queries, stay reasonably fresh — and explicitly scope the crawler out as a separate system); estimate to show the index is far too big for one machine and the query rate too high to recompute per request, so the index is sharded by document and popular results are cached; define the small API (search(query, page)) over an inverted-index and document-store model; draw the design (an offline indexing pipeline building an immutable inverted index, document-sharded query servers with replicas, a coordinator that scatter-gathers and merges per-shard top-K, a ranking phase, and a query cache); then deep-dive building the inverted index, query serving across shards, and ranking. Finish on the follow-ups about scale, fan-out and ordering.

What is an inverted index?

An inverted index is the core data structure of a search engine. Instead of mapping each document to the words it contains, it maps each word (term) to the list of documents that contain it — the term's posting list, where each posting records a document id, the positions of the term in that document, and its term frequency. Positions let the engine answer phrase and proximity queries; term frequency feeds ranking. It is called "inverted" because it flips the natural document-to-terms relationship into terms-to-documents, which turns a query into a fast lookup and intersection of posting lists instead of a scan of every document.

How does a search engine serve a query across billions of documents?

It shards the index by document — each shard holds the full inverted index over a slice of the corpus — and answers every query as a scatter-gather. A coordinator parses the query, fans it out to all shards in parallel, and each shard retrieves and ranks its own candidates and returns only its local top-K. The coordinator merges those small per-shard top-K lists into the global top results, reranks them with the full scoring signals, and returns a page. Each shard is replicated for throughput and availability, and the coordinator hedges requests so one slow replica doesn't set the latency. Popular queries are served from a result cache without touching the shards at all.

Document sharding vs term sharding — which and why?

Document sharding. If you split the index by document, every shard can answer a whole multi-term query over its own slice locally, so the coordinator only merges small top-K lists and never ships posting lists between machines; fan-out is uniform and you scale by adding shards. If you split by term instead (each node owns some terms' posting lists), a multi-term query has to transfer large posting lists across the network to intersect them, and a popular term turns its node into a hotspot. Term partitioning can save some disk I/O for single-term queries, but for a general multi-term web search, document sharding is the standard choice.

How are search results ranked?

By a score that combines query-dependent and query-independent signals. The query-dependent part is text relevance — TF-IDF or BM25 — which rewards query terms that are frequent in the document and rare across the corpus, with length normalisation. The query-independent part is computed ahead of time per document: a link-based authority score (the PageRank idea that a page linked by many good pages is trustworthy), freshness, and quality signals. Serving is two-phase: each shard cheaply retrieves a few thousand candidates, the coordinator merges them, and only then does an expensive rerank with the full feature set run on the small merged set — so the best result rises to the top without scoring billions of pages per query.

How do I practise a system design interview out loud?

Reading a walkthrough is not the same as defending a design while someone interrupts. On Zynter, the HLD track runs live voice rounds modelled on how real system design loops run — you talk through a shared design on the canvas, and a voice interviewer pushes with the follow-ups above one at a time, then gives you a debrief on problem solving, communication, technical execution, and time management. The score is a practice signal, not a hiring decision.

Practise it on Zynter

You can read what an inverted index is. The round is won on defending the scatter-gather out loud.

Pick the Web Search Engine round, draw the indexing pipeline, document-sharded serving and ranking on the canvas, and defend it out loud to a voice interviewer that keeps asking "the index is a hundred billion documents — how do you shard it?" and "two pages both match — which is first, and why?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies including the HLD system design track (Sep 2026).

Practise the Web Search Engine round →
Browse all interview tracks