Type two words into a search box and ten good links come back before you have lifted your
finger. Behind that box sit ten billion documents. In under two hundred milliseconds the
system has to find every document containing your words, score them, and return the best ten.
You cannot read ten billion documents in two hundred milliseconds. You cannot even stream them
off disk. Everything on this page exists to avoid looking at almost all of them. Watch one query
go through.
Ask. A query arrives at the front end, which parses it and fixes the spelling.
A few words come up all through this page:
The corpus is the whole collection of documents being searched, here ten billion web pages.
A term is a word after cleaning: lowercased, and cut down to its stem, so "Searching" and
"searched" both become "search".
An inverted index is the index at the back of a textbook. Instead of each page listing its
words, each word lists its pages. The list of documents for one word is its posting list,
and one entry in it is a posting.
A shard is one machine's slice of the index. A leaf is a machine holding one shard, and
the root aggregator is the machine that asks all the leaves and combines their answers.
p99 is the time 99 out of 100 queries beat. (Percentiles, quickly
explains why we care about it more than the average.)
The real Google Search
This page builds the part of a web search engine like Google Search that finds matching pages fast: an inverted index split across many machines, answering in under 200ms. The numbers are interview assumptions. Google says its own index holds hundreds of billions of pages, far more than the ten billion used here. Ranking is left to "another team", so nothing here describes how Google orders its results.
The documents themselves come from a crawler, which has its own page.
This page starts where the crawler stops: pages are stored, and now they have to be searchable.
The full problem is a decade of work, and the interviewer knows it. So this is the question
where cutting scope earns the most points. These six questions decide what you build.
You ask
They say
What it settles
How big is the corpus, and how many queries a second?
Ten billion documents, tens of thousands of queries a second.
That you cannot look at the corpus. Everything on this page exists to avoid touching all but a tiny fraction of it per query.
What is the latency budget?
200ms at p99, end to end.
A fan out (one request copied to many machines) to a thousand shards, where the slowest one decides your latency. It is also why the deadline is a query parameter rather than a constant.
How fresh does the index have to be?
News in minutes, everything else in hours.
Two indexing paths, not one. A small fast path for recent documents and a slow bulk path for the rest, merged at query time.
Are we building ranking, or retrieval?
Retrieval, with simple scoring. Ranking quality is a separate team.
The biggest cut on the page. Say it early: you are designing the system that finds candidate documents fast, and leaving what order they finally appear in to a layer above.
Do queries need phrases and boolean operators?
Phrases yes, complex boolean no.
To match "new delhi" as a phrase, the index must remember where in a document each word sits, not only that it is there. Those position lists are big, so they are stored separately from the posting lists.
Personalised results?
No.
Results are cacheable. Without personalisation the same query returns the same top ten for everyone, and a cache absorbs a large share of traffic that would otherwise fan out.
One worked line first. Ten billion documents with 500 distinct terms each means ten billion
times 500 postings: five trillion. At three bytes a posting that is 15 TB, and a machine with
512 GB of memory holds about half a terabyte, so you need around thirty machines just to hold
the index. Move the sliders to see how fast that grows. (The method is in
back of the envelope.)
Index size
10 billion
500
3
Total postings10B x 500 = 5.0 trillion
Index size compressed5.0T x 3B = 15 TB
Machines to hold it in memory at 512GB30
Postings scanned for a two word queryup to hundreds of millions
30 machines
just to hold the index in memory, before serving a single query
Three bytes per posting is not an accident, it is the whole reason this is affordable. Document ids are stored as gaps from the previous id (delta encoding) and then in as few bytes as each gap needs (variable byte encoding), so dense posting lists compress far below a raw 8 byte id. Doubling that number doubles your fleet. The widget in Step 2 shows the trick on a real list.
15 TB of index5 trillion postings x 3 bytesabout 30 machines at 512 GB eachjust to hold it