Scale & distribution
Bloom filters
A tiny probabilistic set that answers 'definitely not seen' or 'probably seen' using a few bits per item.
Checking billions of items (URLs a crawler has visited, usernames taken) against a database is slow. A Bloom filter hashes each item to a few bit positions; if any bit is unset, the item was never added. False positives are possible, false negatives are not.
See it in action
Play with the idea, then follow it through a real architecture.
Try it: add and check URLs
Each URL sets 3 bits. A lookup is 'definitely new' if any of its bits is 0, otherwise 'probably seen'.
Bits for this URL (amber): 4, 19, 16.
Added so far: example.com/a · example.com/b · news.site/today
1/3For each link, the filter is checked first. 'Definitely not seen' is the common answer — no database call at all.
- Link extractor
- — Finds 50 links per page
- Bloom filter
- — In memory, ~10 bits per URL
- URL store
- — Exact record of every URL
- URL frontier
- — Pages still to crawl
How it works
- k hash functions set k bits per inserted item.
- Lookups check the same k bits; all set means 'probably present'.
- Size the bit array for the expected item count and acceptable false-positive rate (~10 bits per item ≈ 1%).
Trade-offs
- Can't delete items (use counting Bloom filters) and never gives a definite 'yes'.