Library
35 min read

Design Google Search

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.

UserQuery front endResult cacheRoot aggregatorLeaf shards x1,000SegmentsFresh indexDocument storeCrawlerIndexerMerger

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.

Step 1: Understand the problem#

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 askThey sayWhat 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.

What you are building#

Functional requirements
What the system does.
  • Answer a multi word query from a corpus of billions of documents. Boolean intersection first, then relevance ranking.
  • Return the top ten by relevance in under 200ms. End to end, at p99, including ranking.
  • Ingest new and updated documents continuously. Fresh content within minutes, not a nightly rebuild.
  • Serve tens of thousands of queries per second. With a heavy head of repeated popular queries.
Non-functional requirements
How well it has to do it. The numbers you commit to.
  • 10 billion documents, average 500 useful terms each.
  • 50,000 queries per second at peak.
  • p99 under 200ms including ranking.
  • A machine failure must not lose documents from results.
Out of scope
What you cut, and say so out loud.
  • Crawling. It feeds this and has its own page.
  • The ranking model itself. Assume a scorer exists and focus on how the system feeds and budgets it.
  • Query understanding, spelling correction and synonyms. Real, large, and separable.
  • Personalisation, which changes the caching story enough to deserve its own discussion.

Back of the envelope#

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.