Deduplication by hashing
Spotting repeats of URLs, events or files with fingerprints.
01The intuition
The problem it solves
A teacher collects 1,000 homework sheets and wants to know whether any two are copies. Comparing every pair is 1,000 × 999 / 2, almost half a million comparisons, each a full read of two sheets. For a web crawler that sees 10 billion pages, or an event pipeline that receives the same click twice because a phone retried, pairwise comparison is impossible and keeping the full content of everything seen is too expensive.
The trick the teacher could use: ask each student to write the word count, the first word and the last word on the cover. Two sheets with different covers cannot be copies; only sheets with identical covers need a full read. A hash does this with far more precision. It turns any content, a URL, a file, a click event, into a short fixed-size fingerprint, say 16 bytes, such that equal content always gives the same fingerprint and different content almost never does. Deduplication then becomes "have I seen this fingerprint before", a set lookup.
Build it one piece at a time
Step 1: fingerprint the thing. Run the content through a hash function such as SHA-256, or a faster non-cryptographic one like xxHash when nobody is trying to trick you. A 10 KB page becomes 32 bytes; a URL becomes 16 bytes.
Step 2: a set of fingerprints. Keep every fingerprint seen in a set. Before processing an item, look it up; if present, skip; otherwise process and insert. For 10 billion URLs at 16 bytes that is 160 GB, which spreads over a few machines by hashing the fingerprint itself to pick a shard.
| Item | Fingerprint (shortened) | In set? | Action |
|---|---|---|---|
| https://a.com/x | 3f9a | no | fetch, insert 3f9a |
| https://a.com/x | 3f9a | yes | skip |
| https://a.com/x?utm=1 | 7c21 | no | fetch, insert 7c21 (a near-duplicate slips through) |
Step 3: normalise before hashing. The third row shows the weakness: two URLs that lead to the same page have different fingerprints. So canonicalise first: lowercase the host, drop tracking parameters, resolve .., sort query keys. For events, hash only the fields that define identity (user, action, item, client timestamp), not the arrival time.
Step 4: near-duplicates. Two pages that differ by a date in the footer are, for a search engine, the same page. Exact hashing cannot see that. SimHash and MinHash produce fingerprints where similar content gives similar fingerprints: SimHash of two pages that share 95 percent of their words differ in only a few bits, so "nearly equal fingerprint" can be checked by comparing bit positions, and candidates are found by indexing chunks of the fingerprint.
Step 5: bound the memory with time or with a Bloom filter. Clicks only need dedup within the retry window, so keep fingerprints for an hour in a store with a TTL. For the crawler's billions, a Bloom filter at 10 bits per URL holds 10 billion URLs in about 12 GB with a 1 percent false positive rate, where a false positive means an unseen page is wrongly skipped, which a crawler can tolerate.
Why it works, with the numbers
Two different inputs colliding on a 128-bit hash happens with probability about 2−128 per pair. By the birthday argument, you need around 264 items, 18 billion billion, before a collision is likely:
P(collision among n items) ≈ n2 / 2129; for n = 1010 that is about 10−19
So the set lookup, which is O(1), replaces half a million pairwise reads with one hash per item. The guarantee is: equal content is always detected. The failure modes are normalisation gaps (same thing, different bytes), choosing the wrong identity fields for events (a legitimate second click counted as a duplicate), and a dedup window shorter than the client's retry window.
The trade-off you must say out loud
Exact dedup costs memory proportional to items seen; approximate dedup (Bloom filter, TTL window) costs a small, stated error. Say what identity means for your item, how long you remember fingerprints, and which way the error goes when you are wrong. The follow-up is "what about pages that are almost the same", and the answer is SimHash with a bit-distance threshold.
Where it shows up in the 100 Google problems
- Web crawler: URL dedup before fetching, content dedup after, and SimHash for near-duplicate pages.
- A/B experimentation platform: duplicate exposure events are collapsed by event ID before statistics are computed.
- Ad click aggregation: each click's ID is checked against a one-hour set so retries are not billed.
- Google Drive: chunks are named by their hash so a file uploaded twice is stored once.