Web search: crawl, index, rank

A large fraction of the web is duplicated. The same article is syndicated across a dozen sites, the same product page exists under printable, mobile and tracking-parameter variants, and entire sites are mirrored. An index that stores every copy wastes space and, far worse, returns ten results that are the same page, which is a bad result set no ranking improvement can rescue.

Exact duplicates are cheap to detect: hash the normalised content and compare. That catches mirrors and identical variants and misses everything interesting, because most duplication is near-duplication with a different header, an inserted advertisement or a changed date.

Near-duplicate detection is where the technique gets specific. Shingling breaks the document into overlapping word sequences and compares the sets, and comparing every pair is quadratic, so a fingerprinting scheme is used instead: MinHash estimates set similarity from a small signature, and SimHash produces a hash where similar documents differ in few bits, making near-duplicates findable by looking for hashes within a small Hamming distance. Both turn an impossible comparison into an index lookup.

Choosing which copy to keep is a ranking problem in itself. The canonical should be the version most likely to be wanted: the original publisher rather than the syndicator, the version without tracking parameters, the one with the most inbound links. Publishers can state a preference with a canonical link element, which is a hint from an interested party and therefore treated as evidence rather than as instruction.

The consequence for the results page is diversity. Even after canonicalisation, ten results from one domain about the same topic is a worse answer than a mix, so the final ranking applies clustering and per-site limits. That is a deliberate reduction in per-result relevance for a large increase in the usefulness of the page as a whole, which is a trade worth recognising because it appears in every ranked list of anything.

The index is inverted: each term points at the list of documents containing it, with positions so that phrases can be matched. At web scale those posting lists are enormous, so they are compressed aggressively, using delta encoding of document identifiers and variable-length integers, because the index is read constantly and every byte saved is bandwidth and cache.

It cannot live on one machine, so it is sharded, and the choice of how is consequential. Sharding by document means each shard holds a slice of the corpus and a query goes to every shard, which is more network traffic and balances naturally. Sharding by term means a query touches only the shards holding its terms, which sounds efficient and produces terrible skew, because a common term's posting list is vast and multi-term queries need intersections across machines. Document sharding wins in practice, and the fan-out that follows is the defining property of search serving.

Documents are assigned identifiers in an order that makes compression effective, typically by clustering similar or related documents so that posting lists contain runs of nearby identifiers. That is an unglamorous decision that changes index size by a large factor, and it illustrates a general point: the encoding and the ordering are as much of the design as the structure.

Tiering is the other lever. Not every document deserves the same treatment, so an index is split into a small tier of high-quality documents held in memory and larger tiers on cheaper storage. Most queries are answered from the top tier, and the lower tiers are consulted only when the top does not produce enough good results, which is what makes the economics work at all.

Updates make this harder than a static structure. Posting lists are expensive to modify in place, so new documents accumulate in a small fresh index and are merged into the main one periodically, with deletions handled by a separate list of identifiers to suppress. That is the same design as a log-structured merge tree, arrived at independently for the same reason, which is that sequential writes and periodic merges beat random updates at scale.

A query arrives, is parsed and expanded with synonyms and spelling corrections, and is sent to every shard. Each shard finds its candidates, scores them cheaply, and returns its best few. A root node merges those, applies expensive scoring to the small combined set, adds diversity rules and returns the page. The whole thing has a budget measured in a few hundred milliseconds.

The dominant problem is tail latency, and it is arithmetic rather than bad luck. If a query touches a thousand shards and each has a one per cent chance of taking longer than a second, the chance that at least one does is essentially certain, so the median shard's latency is irrelevant and the request is as slow as its slowest participant. Dean and Barroso's tail at scale paper is the canonical treatment, and the numbers are why every large fan-out system takes the mitigations seriously.

The mitigations are specific. Hedged requests: send a duplicate to a second replica after a short delay and take whichever answers first, which costs a few per cent more work and removes most of the tail. Tied requests, where the two replicas coordinate so the loser drops its copy. Micro-partitioning so slow shards can be rebalanced. And returning early with what has arrived, because a slightly incomplete result page delivered on time is better than a complete one that missed the budget.

Caching helps less than intuition suggests and still matters. Query popularity is a long tail, so a cache of full result pages hits on the head of the distribution and misses on most of the traffic. Caching posting list intersections and per-shard partial results is more effective, and the freshness of everything cached has to be bounded because the index behind it keeps changing.

The design principle underneath is that a request touching a thousand machines cannot depend on all of them behaving. It must be able to answer with most of them, cut off the ones that are late, and degrade the result rather than the deadline. That is the same shed-load-deliberately argument as anywhere else, applied at the level of a single query.

For years the index was rebuilt in batches. Google's pre-Caffeine pipeline ran crawled documents through roughly a hundred sequential MapReduce stages, and a document took two to three days to travel from being crawled to being searchable. That was acceptable when the web changed slowly and unacceptable once it did not.

The reason batch was chosen first is worth stating plainly, because it is the same trade everywhere: batch processing is simple, restartable and efficient per document, and it is inherently latent, because a stage cannot start until the previous one has finished with everything. Adding one new document meant waiting for the next full pass.

Caffeine, the indexing system Google moved to in 2010, replaced that with incremental processing built on Percolator, which added transactions and change notifications on top of the storage layer so that a single document could be updated in place and trigger the work that depends on it. The published result is precise: the same number of documents processed per day, the median document moving through more than a hundred times faster, and the average age of a document in results cut by half.

The cost of that is real and worth naming: incremental processing runs many small distributed transactions instead of a few enormous batch jobs, so the system uses substantially more resources per document and is far more complex to operate. Google's own paper is explicit that the trade was made for latency rather than efficiency, which is the honest way to describe most moves from batch to streaming.

The general lesson generalises well beyond search. Batch is the correct default because it is simple and cheap; incremental is what you buy when the age of the data is a product problem rather than an engineering preference. And the way to know which you are in is to ask what changes when the data is two days old, which for a search engine in a world with breaking news is quite a lot.

Matching produces thousands of documents and the page shows ten, so ranking is the product. The signals fall into three groups: how well the document matches the query, how good the document is independent of any query, and what the person is likely to want given their language, location and context.

Query-independent quality is the idea that made web search work. PageRank treated a link as a vote and weighted votes by the authority of the linking page, which gave a way to tell an authoritative page from a keyword-stuffed one at a time when text matching alone could not. It is one signal among hundreds now, and the principle it established, that the structure of the graph carries information the documents do not, long outlived the specific formula.

Modern ranking is a learned function over those signals, trained on labelled judgements and behavioural data, and the interesting engineering is the pipeline shape rather than the model. Cheap scoring runs on every candidate in every shard, and expensive scoring runs only on the small set the root has already merged, because the expensive model cannot be run on a million documents inside the latency budget. That two-stage retrieve-then-rerank pattern is now the standard shape for search and recommendation systems generally.

Adversaries are a permanent part of the problem, which is unusual among ranked systems. Every published signal becomes a target, so link farms, keyword stuffing, cloaking and generated content all exist because ranking exists. That is why signals are numerous, partly undisclosed and constantly adjusted, and it is why a search team spends as much effort on defending the ranking as on improving it.

Knowing whether a change helped is the hardest part and is entirely a measurement problem. Human raters give labelled judgements against published guidelines, offline metrics compare rankings against those labels, and online experiments measure what people actually did. Both are needed because they answer different questions: the offline number says the ranking matches expert judgement, and the experiment says it changed behaviour, and a change can move one without the other.