36.8 How do you de-duplicate with Bloom filters?

Two kinds of duplicates waste a crawler's effort:

Duplicate URLs. The same page under different spellings: HTTPS://Shop.Example:443/books/42?utm_source=x&b=2&a=1#reviews and https://shop.example/books/42?a=1&b=2. Normalise every URL before using it: lowercase scheme and host, remove default ports, sort query parameters, drop tracking parameters and #fragments. In the chapter's code, three spellings of one book page collapse to one URL.

Then check "have we seen this URL?" With 10 billion URLs, an exact set is large; a Bloom filter (Chapter 20) at 1% false positives needs about 9.6 bits per URL, about 12 GB for 10 billion. In the chapter's code, a filter of 50,000 URLs never misses a seen URL and wrongly says "seen" about 1% of the time for new ones. A false positive means skipping a page we haven't really crawled, which is acceptable for a crawler; important pages also arrive through sitemaps and the re-crawl scheduler.

Duplicate content. Mirrors, printer-friendly versions, and the same article on several URLs. Hash the page's normalised text; if the hash was seen, store a pointer instead of the page. For near-duplicates (the same article with a different ad or date), use similarity hashes like SimHash or MinHash, which give similar fingerprints to similar documents.

Interviewer pushback:

• "Doesn't the Bloom filter fill up?" → It's sized for the expected number of URLs; monitor its fill and rebuild a bigger one from url_state when needed (Chapter 20's overfill warning).

Memory code: "Normalise the address, ask the Bloom filter, hash the content."