Extraction and Deduplication

In one line: the design's deduplication is correct for the case it handles and blind to the case that matters more. The design even states the blindness and reads it as a strength.

The extractor

Extractor: Parses the web page to extract URLs and content. It sends URLs to the scheduler and content to the Document Input Stream (DIS) (e.g. Redis) for processing. Once verified as unique, content is stored in the blob store.

Two dedup passes on two different things — and both are necessary

The design deduplicates twice, and the pairing is the interesting part:

Neither subsumes the other, and the design explains why with a good example:

By using URL redirection, the new URL can pass through the URL dedup test. But the second stage of document dedup wouldn't allow content duplication in the blob storage.

So a redirect chain, a mirror site, or the same article on two domains all produce different URLs and identical content. URL dedup misses them; document dedup catches them.

The ordering matters too. URL dedup runs before fetching — it saves the request entirely. Document dedup runs after fetching — the bandwidth is already spent, and it only saves storage.

Deduplicate as early as the information allows. URL dedup is cheap and prevents the expensive operation; document dedup is a backstop that runs when you could not have known in advance.

The blindness

By changing just one byte in a document, the checksum of the modified document is going to come out different than the original one.

The design frames this as robustness — it is the central weakness

Read the framing: the passage lists this under things the design "can be made robust against." But it is not robustness. It is the exact-match property, and on the web it is a serious limitation.

A checksum answers "are these byte-identical?" The web's duplication is overwhelmingly not byte-identical:

Same article, different ad served          -> different checksum
Same page, timestamp in the footer         -> different checksum
Same content, session ID in a comment      -> different checksum
Same page, different navigation highlight  -> different checksum
Syndicated article on 200 news sites       -> 200 different checksums

Every one of those is a duplicate in any sense a search engine cares about, and every one passes the checksum test as unique. They get stored separately, indexed separately, and later ranked as distinct documents.

Near-duplication is not a corner case — it is the dominant form of duplication on the web. Templated pages, syndicated content, printer-friendly variants, and pagination all produce near-identical documents at scale.

The real mechanism is similarity hashing rather than exact hashing:

The design property that makes checksums attractive — a tiny change produces a completely different hash — is precisely what makes them useless for detecting near-duplicates. That property is a virtue for integrity checking and a defect for similarity detection.

A hash designed so small changes produce large output changes cannot tell you that two things are almost the same. Saying that plainly is the strongest thing you can offer on this section.

The checksum stores are on the hot path, and nobody sizes them

Lesson 3 noted this omission. Here is why it matters.

Every URL extracted and every document fetched requires a lookup against these stores. At Lesson 3's scale:

5 billion URL checksums    x 8 bytes = 40 GB
5 billion document checksums x 8 bytes = 40 GB
                                        ------
                                        80 GB of pure lookup structure

And the URL store is queried more often than pages are fetched, because every page yields many extracted links, each needing a check.

That makes it one of the highest-traffic components in the system, and it has properties worth naming:

It must be fast. A slow lookup here throttles the whole crawl, since it gates both fetching and storing.

It grows monotonically. Nothing is ever removed — you must remember every URL you have seen, forever.

It tolerates false positives better than false negatives, which is exactly the shape that suggests a Bloom filter in front of it: a compact probabilistic structure that answers "definitely new" or "possibly seen," with a real lookup only on the "possibly seen" path. A Bloom filter for 5 billion URLs at a 1% false-positive rate is a few gigabytes rather than forty.

The cost is that a false positive silently drops a URL you have never crawled — which is acceptable for a crawler that will never see the whole web anyway, and unacceptable if completeness matters. Design the approximation so its failure mode matches what you can tolerate.

The Document Input Stream exists so two components can read one fetch

Content goes to the Document Input Stream (DIS) (e.g. Redis) for processing.

Lesson 4 flagged that this is not really a cache. Here is what it does: a fetched document is consumed by two components — the extractor pulls URLs and content out of it, and the duplicate eliminator checksums it.

Without a shared buffer, you would either fetch twice or pass megabytes between services. With one, the document is parked once and both components work against a reference.

Two things worth adding:

It decouples the pipeline stages. The fetcher can move on to the next URL without waiting for extraction and dedup to finish.

It is ephemeral by design. Once dedup passes and content is written to the blob store, the DIS entry is dead. So the store should be memory-resident with short TTLs, which is exactly why Redis is named.

A buffer between pipeline stages converts a synchronous chain into an asynchronous one — the same reason the Uber and Twitter chapters put queues between their stages.

Two different problems that get conflated. A Bloom filter is the right shape for URL membership because the failure mode is safe in one direction: a false positive skips a page you have not crawled, which is a small loss, while a false negative — recrawling — cannot happen.

Content deduplication needs a similarity hash rather than an equality one, because the same article behind two URLs differs in a timestamp or an ad slot and a cryptographic hash sees two unrelated documents.

Next: the end-to-end workflow.