A search box looks like the simplest product on the web: type some words, get ten links. Behind it sits an index of billions of pages, spread over thousands of machines, and every query has to ask all of them and come back in a fraction of a second. The hard parts are building that index without stopping the world, splitting it so a query stays cheap, and keeping the slowest of thousands of machines from setting everyone's response time.
The web crawler lab ended with billions of fetched pages in object storage. This lab starts there and turns them into answers. It assumes you know what an inverted index and BM25 are; if not, read Elasticsearch and BM25 in one minute first.
The brief
You're building the core of a general web search engine. A user types a query and gets the ten most useful pages, each with a title and a snippet, in well under half a second. New pages from the crawler should show up in results, and news should show up within minutes.
Who uses it?
- Searchers type 2-4 words, often misspelt, and judge the whole product by the first three results and how fast they appear.
- The crawl pipeline delivers pages continuously: about a billion fetches a month, a small fraction of them breaking news.
- The ranking team changes ranking signals every week and needs to test changes safely.
In scope: building and updating the index, partitioning it, answering queries across many machines within a latency budget, ranking in stages, spelling and synonyms, and caching.
Out of scope: crawling (the crawler lab), autocomplete (the typeahead lab), ads, images and video, personalisation, and the details of training ranking models.
Requirements
Functional
- Given a query, return the ten best pages with title, URL and a snippet showing the query words in context.
- Support phrases (
"to be or not to be"), and correct obvious misspellings ("did you mean"). - Let users page through further results, up to a sensible limit.
- Remove pages that are gone (404), duplicated or spam.
Non-functional
- Fast: server time under 200 ms at the median and under 500 ms at p99.
- Fresh: breaking news searchable within about 5 minutes of being crawled; ordinary pages within about a day.
- Highly available: losing a machine, a rack or a data centre degrades results slightly at worst. Search never goes dark.
- Good results: the ranking team can measure quality and roll out changes gradually.
- Cost-aware: the fleet should scale with queries and pages, not with how many machines a single query touches.
Two requirements pull against each other. "Fast" wants small indexes on many machines. "Cheap" wants as few machines per query as possible. Most of the design is about getting both.