Search Engine

What the interviewer is asking

"Design a search engine" comes in several forms: web search, search over a social app's posts, the search box of a shop. Under all of them sits the same core: a huge collection of documents, a few words typed by a user, and the 10 best matches back in a fraction of a second. The interviewer wants to see the inverted index, how a search is answered from it, how matches are ranked, and how an index too big for one machine is split. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Search by words: type a few words, get the 10 most relevant documents, with more pages on request.
• Fast: about 200 ms, out of a collection of 1 billion documents.
• Fresh: a new document is searchable within minutes.

Name the rest and park it: spelling correction, autocomplete (a design of its own), image search, personalized results and ads.

2. Data: documents and the inverted index

Each document is a record: an id, its URL, its text and a quality score. A search goes from a word to the documents that contain it, so the key structure is an inverted index: for each word, the sorted ids of the documents that contain it, its posting list. Each entry also keeps how often the word appears there (for ranking) and where (for phrase searches). Five tiny documents and their index:

id   text
1    red car
2    blue car
3    red apple
4    fast car
5    red car wash

word    posting list
red     1, 3, 5
car     1, 2, 4, 5
blue    2
apple   3
fast    4
wash    5

It's the index at the back of a book: a lookup instead of a scan. Without it, every search reads every document, 1 billion × about 1,000 words, a trillion words per search. An index from each document to its words doesn't help: that answers "what's in document 3?", not "which documents contain car?".

3. The API: one call

GET /search?q=red+car&page=1
  → 200 OK
{"results": [
   {"title": "Red car guide",
    "url": "example.com/red-car",
    "snippet": "…a red car…"},
   … 9 more],
 "next": "page=2"}

A page is ten results, each with a title, a URL and a snippet. Don't send every match (car is on millions of documents) or full texts (the user chooses from the snippets). Deep pages cost more than they look: page 5 shows results 41 to 50, so every shard must send its best 50, and it's common to cap how far users can page.

4. The busy path: one search

1. The query service gets GET /search?q=red+car.
2. It splits the search into words: red, car.
3. It looks up each word's posting list.
4. It keeps the ids on both lists: the documents with both words.
5. It scores those documents and keeps the 10 best.
6. It answers with their titles, URLs and snippets.

Look up, intersect, rank, return, within about 200 ms.

5. The numbers

From the interviewer: 1 billion documents of about 1,000 words each, and 10,000 searches a second at busy hours. Count one index entry per word of each document, about 4 bytes compressed.

• Index size: 1 billion × 1,000 = 1 trillion entries × 4 bytes = 4 TB.
• Servers: say one server keeps about 100 GB of index in memory: 4 TB ÷ 100 GB = 40 servers, 25 million documents each.
• New pages: a crawler fetching 1 billion pages a month delivers about 400 a second (1 billion ÷ 2.6 million seconds).

The size decides the design: 4 TB can't live on one server, so the index must be split.

6. Services: the indexer and the query service

• Indexer: reads each new page from the crawler's page store, splits its text into words and adds the page's id to each word's posting list.
• Query service: splits the search into words, intersects the posting lists, ranks the matches and returns a page of results.

One side writes about 400 pages a second, the other reads 10,000 searches a second, so each grows on its own. Both must split text by the same rules (lowercase, punctuation), or a search for "Car" would miss "car".

7. Scale: split the index by document, cache the repeats

• By document: each shard indexes its own 25 million documents and answers for them: it looks up, intersects and ranks, then returns its top 10. The query service sends each search to all 40 shards and merges their 40 × 10 = 400 results into the final 10, a scatter-gather.
• By word: each word's whole posting list lives on one shard. A two-word search asks only 2 shards, but shards holding common words get far more searches than the rest, and long lists must cross the network: a word on 10 million documents is about 40 MB of ids, 40 ms of one server's 1 GB a second, for one search.

Most large search systems split by document: each shard's work needs no other shard, and more documents just means more shards. Full copies don't solve the size problem: each would still be 4 TB.

Searches also repeat: when news breaks, thousands of people type the same words. A result cache keyed by the search words and the page number answers repeats from memory, so only the misses reach the shards. Keep each result about a minute: a day-long cache would hide this morning's news from the most popular searches.

8. Deep dive: building and intersecting the index

The indexer reads documents in id order and adds each id to the end of its words' lists, so every list stays sorted without being sorted. Lists are stored as gaps between ids (car's 1, 2, 4, 5 becomes 1, 1, 2, 1), small numbers that compress well.

A search for red car needs the documents on both lists. Both are sorted, so walk them together: compare the two ids, keep a match, step past the smaller one.

step   red   car   then
1      1     1     equal: keep 1, move both
2      3     2     2 is smaller: move car
3      3     4     3 is smaller: move red
4      5     4     4 is smaller: move car
5      5     5     equal: keep 5, both done

Documents 1 and 5, in 5 comparisons. The walk takes at most as many steps as the two lists hold (3 + 4 = 7), never one per pair (3 × 4 = 12): for two lists of a million ids, 2 million steps instead of a trillion. Real engines also start from the shortest list and jump ahead in the longer ones.

9. Deep dive: ranking

TF-IDF scores how well a document matches: the term frequency (how often each word appears in it) times the inverse document frequency, a weight that grows the rarer the word is, the log of all documents ÷ documents with the word. Say car is on 1 in 100 documents (weight 2) and red on 1 in 1,000 (weight 3); a word on every page, like "the", weighs 0.

page   red   car   TF-IDF score
A      1     7     1×3 + 7×2 = 17
B      4     3     4×3 + 3×2 = 18
C      5     1     5×3 + 1×2 = 17

B wins: A has the most matching words but mostly the common one, C the most reds but almost no cars. Real engines use refinements such as BM25, which gives less and less for each extra repeat of a word.

Words are easy to fake: a spam page that repeats "red car" 25 times scores 25×3 + 25×2 = 125. So each document also has a quality score from the links pointing to it, since other sites link to pages worth reading. PageRank is the best-known version: a link counts more when it comes from a page that ranks high itself, so a spammer's own junk pages add little.

Each shard mixes relevance and quality into one score and keeps its best 10 in a small min-heap: each match is compared with the worst of the 10 kept and replaces it only if it's better, the Top K pattern. The query service merges the 400 it gets back.

10. Deep dive: copies and the slowest shard

Every search that misses the cache goes to every shard. Say the cache answers about 30% of searches and one shard server answers about 1,000 searches a second: 70% of 10,000 = 7,000 searches a second reach each shard, so each shard needs 7 copies, 40 × 7 = 280 servers. The copies also keep a shard answering when one of its servers fails.

Say each shard answers within 50 ms 99 times in 100 (its p99 is 50 ms). A search has 40 chances to meet a slow reply: 1 − 0.99⁴⁰ is about 33%, so about 1 search in 3 waits longer than 50 ms. The slowest shard sets the time of the whole search: that's tail latency, and why you watch each shard's p99, not its average. Common fixes: send a slow request to a second copy and take the first answer, and answer with the shards that replied by a deadline.

11. Deep dive: freshness

About 400 new pages arrive a second, 10 a second on each shard, while each shard's main index is built in big batches: long posting lists, sorted and packed tight. Rebuilding it every few minutes would reread 25 million documents to add about 3,000 new ones (10 a second for 5 minutes), and inserting ids into packed lists that searches read all the time is slow.

Instead, each shard keeps a small fresh index in memory for new pages. A search asks both indexes and merges the results, and in the background the fresh index is merged into the main one and a new one starts. A deleted page is commonly marked as deleted and filtered out of results until the next merge.

What breaks first

• A breaking-news search: the result cache takes the repeats; its one-minute life keeps results fresh.
• A slow or dead shard server: its copies take over; ask a second copy when one is slow.
• Very common words: huge lists that weigh near 0; some engines skip them, others keep them for phrase searches.
• The collection growing: add shards and move some documents to them.

Summary: the order to follow

1. Scope: the 10 best of 1 billion documents in about 200 ms, new ones within minutes.
2. Data: documents, and an inverted index: word → sorted posting list.
3. API: GET /search?q=…&page=…, 10 results a page.
4. Busy path: look up, intersect, rank, return.
5. Numbers: a 4 TB index, 40 servers to hold it, 10,000 searches a second.
6. Services: the indexer writes, the query service reads.
7. Scale: shards by document with scatter-gather, and a result cache.
8. Deep dives: sorted posting lists intersected in one walk; TF-IDF and quality from links, a top 10 heap per shard; 7 copies of each shard and the slowest shard; a small fresh index merged in.

The same steps work for any "design X" question.