Type a query, get ten good results out of billions of pages, in a fraction of a second. The magic is not one clever trick but three ideas layered together: a data structure that flips the problem inside out, a way to spread it across thousands of machines, and a ranking pass that runs on only what survives.
The core problem
You cannot scan the web per query. There are billions of documents, and reading even a tiny fraction of them for every search is hopeless. The insight is to do the expensive work ahead of time, when pages are crawled, and leave only cheap work for query time. That precomputed structure is the inverted index.
The inverted index
A normal index maps a document to the words it contains. That is the wrong direction for search, because a query gives you words and wants documents. So you invert it: for each word, store the list of documents that contain it. This list is called a postings list. The word "database" points to every document that mentions it, "sharding" points to its own list, and so on.
Now a query for "database sharding" becomes a set operation: take the postings list for "database", take the list for "sharding", and intersect them to find documents containing both. Intersecting two sorted lists is fast, and because the lists are sorted by document ID you can walk them together in linear time. The heavy lifting, building these lists, happened at crawl time. Query time is reduced to reading and intersecting a handful of precomputed lists.
Postings lists are also where you store extra signal: how often a word appears in a document, where it appears (title versus body), which feeds ranking later. And because these lists are enormous, they are compressed aggressively, since a shorter list means fewer bytes read from disk or memory per query.
Scatter-gather across shards
One machine cannot hold an index of the whole web. So the index is partitioned across thousands of servers, usually by document: each shard holds the full index for its own slice of the pages. This is document partitioning, and it has a nice property, every shard can answer a query independently against its own documents.
At query time you scatter the query to every shard in parallel. Each shard intersects its postings lists, ranks its own local candidates, and returns its best few. Then you gather those partial results and merge them into a global top ten. Because the shards work in parallel, total latency is set by the slowest shard, not the sum, so adding documents means adding shards without slowing queries. Each shard is also replicated many times for both throughput and fault tolerance, so one dead machine never loses a slice of the web.
Two-phase ranking
Retrieval gives you candidates, maybe thousands of documents that match the words. Ranking decides the order, and it is too expensive to run on all of them, so it splits in two.
The first phase is cheap scoring inside each shard, using signals available in the index like term frequency and a classic relevance formula. This trims thousands of matches down to a few hundred promising ones per shard. The second phase, run after gathering, applies a much richer and more expensive ranking model to that small survivor set, weighing hundreds of signals: the query's meaning, page quality, freshness, the user's context. This is the same two-stage funnel that shows up in recommendation systems, and for the same reason: run the cheap filter over everything, run the expensive model over only what survives.
The trade-off
The whole design front-loads cost. Crawling, parsing, and building the inverted index is enormously expensive and continuous, but it turns query time into a fast read. The price is freshness and storage: a newly published page is invisible until it is crawled and indexed, and the index itself is gigantic and must be kept in memory across a fleet to hit sub-second latency. You trade storage and indexing cost for query speed, which is exactly the right trade when queries vastly outnumber updates.
How the real systems do it
Google, Bing, and open-source engines like Elasticsearch and Solr (both built on Lucene) all sit on an inverted index, shard it across machines, and use scatter-gather with two-phase ranking. The specifics of the ranking model differ enormously, but the retrieval skeleton is remarkably universal.
I wrote the full breakdown, with diagrams and the data model, here: https://www.systemdesign.academy/interview/design-google-search
Top comments (0)