The whole design, in writing
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
The big idea
What is a search engine?
Type a few words and get the ten best pages from billions, ranked by relevance, in a few hundred milliseconds. Two hard problems hide inside: finding the matching documents fast, and ordering them so the most useful is first.
Flip the data around with an inverted index (term → documents) so matching is a list lookup, not a scan. Then rank the matches by relevance and authority, shard the index for scale, and cache the popular queries.
What the new pieces do
- Userclient
- Wants the ten most relevant pages out of billions, in a few hundred milliseconds. Relevance and speed together are the whole product.
Step 1 · The skeleton
Query in, matches out
Given a query, you must return documents containing those words. Scanning every page for every query is hopeless at web scale — you’d need to read the entire internet on each search.
Return docs containing the query words, from billions of pages, in ~100ms. How do you store the data?
Reading the entire web on every search is hopeless — billions of docs per query. You must precompute where each word lives, not search at query time.
Doc → words answers "what’s in this page?", the wrong question. You’d still scan every doc’s word list to find a term. You need the inverse.
Term → docs turns a query into looking up each word’s postings list and intersecting them — a handful of list ops instead of scanning the web. The single most important idea here.
Stand up a Query Service backed by an Inverted Index: instead of “which words are in this doc?”, store “which docs contain this word?”. A query becomes looking up each term’s document list and intersecting them.
Why this piece earns its place
The decision this step really makes is what rides in the postings, not that you invert the data. Doc ids alone give the smallest possible index and answer “which pages contain this word” and nothing else. Add each term’s frequency and you can score how well a document matches, which is what the ranker later needs. Add positions and you can answer a phrase query, but positions are stored per occurrence rather than per document, so they usually become the single largest thing in the index. That is the knob. I would keep frequencies everywhere, because ordering is the product and you cannot add them retroactively without rebuilding, and treat positions as a per-field choice: carried for titles and body text where phrases matter, dropped for boilerplate and anchor fields where they do not. Going too lean is a ceiling you cannot lift later. Going too rich pushes the hot postings out of memory, and the moment a common term’s list has to be read off disk, the tidy story about intersecting a few lists quietly becomes a story about disk seeks.
What the new pieces do
- Query Servicebackend
- Receives the query, coordinates parsing, retrieval and ranking, and returns the results page. The conductor of the read path.
- Inverted Indexindex
- The core structure: for each term, the list of documents containing it (a postings list). Finding matches becomes intersecting a few lists, not scanning the web.
Back of the envelope
- query = intersect postings lists
- a few list ops, not a web scan
- term → sorted doc-id list
- precomputed once at index time
- + positions & frequencies
- enable phrase match and relevance scoring
Step 2 · Match the right forms
Parse the query
A user types “Running Shoes” but the index stored “run” and “shoe”. Case, punctuation, stop words and word forms all cause misses unless the query is processed the same way the documents were.
A user types "Running Shoes" but the index stored "run" and "shoe". How do you make them match?
Enumerating every case/tense/plural for every word explodes the index and still misses forms you didn’t list. Normalize both sides instead of expanding one.
Tokenize, lowercase, strip stop words and stem the query exactly as the documents were, so "Running" and "run" resolve to the same postings list. Symmetry of analysis is the fix.
Substring matching can’t use the postings lists (slow) and is wrong (matches "run" inside "errand"). The principled fix is identical normalization, not fuzzy scanning.
A Query Parser tokenizes, lowercases, strips stop words and stems terms — applying the exact pipeline used at index time. Now “Running” and “run” resolve to the same postings list, so matching actually works.
Why this piece earns its place
Worth saying out loud what this pipeline destroys, because none of it is recoverable at query time. Stemming conflates words that are genuinely different — an aggressive stemmer will fold university and universe onto one root — and stop-word removal deletes exactly the queries that are made of stop words: “The Who”, “to be or not to be”. Both fail silently; the user gets results, just not theirs. So I would stem toward the milder end, and keep stop words in the index with their positions rather than dropping them, skipping them only when scoring, so a phrase query can still use them. The second consequence is operational. Symmetry of analysis means the analyzer is part of the index’s schema, not a service you redeploy independently: change the stemmer and every posting written under the old rules is unreachable by the new query forms, with nothing to show for it but a drop in matches. That makes an analyzer change a corpus-wide rebuild, so the analyzer carries a version and that version travels with the index built from it.
What the new pieces do
- Query Parserservice
- Lowercases, tokenizes, removes stop words and stems the query (“running” → “run”) so it matches the same forms used when the index was built.
Step 3 · Build the index
From pages to postings
The inverted index doesn’t appear by magic — it has to be built from the crawler’s billions of pages, and rebuilt as new pages arrive. Doing that inline with queries would be impossible.
The inverted index must be built from billions of crawled pages and kept current. Where does that happen?
Indexing a document is heavy work; doing it in the query path would make every search wait on parsing pages. Build and serve are opposite workloads — separate them.
The indexer reads crawled docs, runs the same analysis, and writes postings in the background. Separating write-heavy indexing from read-heavy querying lets each scale independently.
Rebuilding billions of postings for each new page is absurdly wasteful. Indexing is incremental — append/merge new postings into segments — not a full rebuild per change.
An offline Indexer pipeline reads crawled documents, runs the same analysis, and writes each term’s postings (doc ids, positions, frequencies) into the index. It runs continuously in the background, separate from serving queries.
Why this piece earns its place
Separating build from serve buys the two scaling stories, and it also introduces a queue between the crawler and the indexer that nobody draws at the whiteboard. That queue’s depth is the freshness of the product. The number I would put on a dashboard is not documents indexed per second, it is the age of the oldest thing still waiting — how long it takes a fetched page to become searchable. It matters because the failure here is never an outage. Indexing capacity that keeps up on average falls behind during a crawl burst and drains afterwards, and the only symptom anyone can see is that results are a little older than they were. Nothing errors, so nothing pages anyone. That also argues against draining the queue in arrival order. Some lag is unavoidable, so I would rather choose where it lands: a news page or a high-authority site jumps the queue while a rarely-changing page in the long tail waits, because the same hour of delay is worth wildly different amounts on those two documents.
What the new pieces do
- Crawlersource
- Supplies the raw documents to search over (see the web-crawler design). The index is only as fresh and complete as what the crawler delivers.
- Indexerworker
- Parses crawled pages, extracts terms, and writes postings into the inverted index — the offline pipeline that turns documents into searchable structure.
Step 4 · Which ten first?
Ranking
A common query matches millions of documents. Returning them in index order is useless — the user only looks at the first few, so the order is the entire value of the product.
A common query matches millions of docs. Returning them in index order is useless. How do you order them?
Raw term frequency rewards keyword-stuffed and long pages and ignores authority — a spam page repeating the word wins. You need match quality and trustworthiness.
Authority without textual relevance returns famous pages that barely match the query. A trusted page on the wrong topic isn’t a good result — you need relevance too.
BM25 asks "does this match the words well?", PageRank asks "is this page trustworthy?". Combining them (plus freshness, quality) is why search beats a keyword grep. The Doc Store then supplies titles/snippets for the winners.
A Ranker scores candidates by textual relevance (TF-IDF/BM25 — how well the terms fit the doc) and authority (PageRank — how important the page is), plus signals like freshness. The Doc Store then supplies titles and snippets for the winners.
Why this piece earns its place
Relevance scoring is not one formula, it is a formula with dials, and the interesting question is how you set them. BM25’s length normalization decides how hard a document is penalized for being long: turn it all the way up and a thorough, genuinely comprehensive page loses to a short one that happens to be on topic; turn it off and long pages win by accumulating terms, which is the stuffing failure we just rejected. Its saturation term decides when repeating a word stops helping, which is why a page that says the query one more time than its neighbour does not simply out-rank it. Neither of those, and neither the weight between relevance and authority, is something to argue about from first principles. I would set them by measurement: a held-out set of queries with human relevance judgments to catch regressions, and interleaving two rankers on live traffic to see which one people actually prefer. The design contribution here is making ranking a scored function with parameters you can move, so it becomes an experiment you run rather than an opinion you defend.
- BM25text relevance
- PageRankauthority
- top 10shown
What the new pieces do
- Rankerservice
- Scores candidate documents by textual relevance (BM25/TF-IDF) and authority (PageRank), then orders them so the best result lands at the top.
- Doc Storestore
- Holds document metadata and content used to build the title, URL and snippet shown for each result after ranking selects the winners.
Step 5 · Too big for one box
Shard & scatter-gather
The index for the whole web is far too large for a single machine’s memory or disk, and one server can’t evaluate a query against billions of documents in time.
The whole-web index is far too big for one machine. How do you search billions of docs in time?
Term-sharding creates hotspots on common words and uneven load, and the postings for a popular term still won’t fit one box. Document-sharding spreads work evenly.
Each shard searches its slice in parallel; the retriever fans out (scatter), each returns its local top results, and they’re merged (gather). You wait for the slowest shard, not the sum — latency stays bounded as the corpus grows.
Replicas add throughput but every replica still can’t fit or evaluate the whole-web index in time. You must partition the index across machines, then replicate each shard.
Shard the index by document across many machines. A Retriever sends the query to every shard in parallel (scatter), each returns its local top candidates, and the retriever gathers and merges them for ranking. Latency stays bounded as the corpus grows.
Why this piece earns its place
Scatter-gather quietly assumes each shard can pick its own best candidates alone, and the ranking from the previous step breaks that assumption. Inverse document frequency — the part that makes a rare word count for more than a common one — is a property of the whole corpus, not of a slice. If every shard computes it from the documents it happens to hold, the same document scores differently depending on which machine it landed on, and the merge is then comparing numbers that were never on the same scale. The rare, meaning-carrying terms are precisely where the slices disagree most, so the error lands on the queries that matter. Two defenses, and I would use both. Assign documents to shards by a hash rather than by host or crawl order, so each slice is a fair sample of the corpus and local statistics approximately agree. And compute term statistics globally on a slow cycle, then push that table to every shard so they all score against one view of the corpus. This is also the reason shard assignment is not a free choice.
- by-documentsharding
- parallelshard search
- mergetop results
What the new pieces do
- Retrieverservice
- Fans a query out to every index shard in parallel, gathers each shard’s top candidates, and merges them — the pattern that makes billions of docs searchable.
Back of the envelope
- shard by document
- each shard searches a slice in parallel
- latency = slowest shard
- not the sum — bounded as the corpus grows
- + replicate each shard
- adds throughput and fault tolerance
Step 6 · The same searches
Cache hot queries
A huge share of searches are the same popular queries repeated endlessly. Re-running the full parse → scatter-gather → rank pipeline for each identical query wastes enormous compute.
A huge share of searches are the same popular queries repeated endlessly. How do you save that compute?
Scaling the fleet to re-run identical popular queries burns compute on work you already did. When the same input repeats, recompute is the waste to eliminate, not to scale.
Postings caching helps retrieval but still re-runs parse → scatter-gather → rank → merge for every repeat of a head query. You can skip the whole pipeline by caching the finished result.
Search traffic follows a steep power law, so a modest result cache answers a large fraction of queries in ~1ms, sparing the index and ranking fleet for the rare, novel long-tail queries.
Cache the result pages for popular queries. Search traffic follows a steep power law, so a modest Result Cache answers a large fraction of queries in a millisecond, sparing the index and ranking fleet for the long tail.
Why this piece earns its place
The thing to get right here is what the key actually is, because a result page is not a pure function of the query string. The same words asked from another country, in another language, or with different content settings should not always return the same page. Key on the query alone and the cache serves one region’s results to everyone, which looks like a ranking bug and is really a caching bug. Fold the individual user in and the skew that justified the cache evaporates, because the repetition lives in the part of the request that people share — every dimension added splits the head into smaller heads. So I would key on the query plus the small set of things that genuinely change results, and simply not cache anything personalized. The other half is expiry. An entry is a snapshot of an index that keeps moving underneath it, so its lifetime is set by the freshness promise rather than by the hit rate I would like to report: a head query is exactly the one where a newly indexed page most needs to show up.
What the new pieces do
- Result Cachecache
- Caches the result pages for popular queries. Search traffic is highly skewed, so a small cache serves a large share of queries instantly.
Back of the envelope
- head queries ≫ tail
- a steep power law in search traffic
- small cache ⇒ big hit rate
- a large share of queries answered in ~1ms
- miss ⇒ full pipeline
- spend retrieval budget on novel queries
Step 7 · Stay current
Freshness & the sharp edges
News breaks and pages change constantly, but rebuilding a web-scale index takes time. Users also expect spelling correction, synonyms, and protection from spam pages gaming the ranking.
Run a small, fast fresh index for recent content merged with the big base index at query time. Layer query understanding (spell-correct, synonyms) before retrieval, and add spam/quality signals to ranking so manipulated pages don’t win.
Why this piece earns its place
The uncomfortable part of this layer is where its training data comes from. Spelling correction weighted by query logs, synonyms learned from click data, and the behaviour signals feeding quality scoring are all learned from what this engine already chose to show people. A document the ranker never surfaces earns no clicks, and that absence then confirms it should not be surfaced. The loop closes, and the system loses the ability to discover that it is wrong. Spam defences inherit the same blindness, because a page suppressed for a bad reason looks identical in the logs to one suppressed for a good one. So part of the design is deliberately not being greedy with the ranking: hold out a slice of traffic where the ordering is perturbed, and keep some exploration in the lower positions, so there is data about documents the current model does not favour. Alongside it, keep an evaluation set built from human judgments rather than from clicks, because it is the one measurement the feedback loop cannot quietly move.
You did it
You just designed a search engine.
Everything you assembled, in order
- An inverted index turns search from a scan into term-list lookups.
- Query parsing applies the same analysis as indexing so terms actually match.
- An offline indexer builds postings from crawled pages, separate from serving.
- Ranking combines text relevance (BM25) with authority (PageRank).
- Document-sharding plus scatter-gather retrieval scales to billions of docs.
- A result cache exploits skewed traffic to answer head queries instantly.
- A fresh index, query understanding and spam signals keep results current and clean.