Phase 10Advanced11 of 12 in Bloom Filters

System Design with Bloom Filters

FAANG-style designs: a Google-scale web crawler, a billion-user membership service and product catalogue, malware and global blocklists, a distributed object-existence check, an LSM storage engine, and the full Bloom + Redis + Kafka capstone with anti-patterns.

Every design here follows the reasoning chain: requirement → exact or approximate → can false positives be tolerated → can false negatives be tolerated → dataset size and growth → target FPR → memory → hashing → deletes → variant → source of truth → updates → rebuilds → distribution → failure behaviour → observability → security → trade-offs.

0/5 · 0%

5 topics ~41 min 7 code blocks & diagrams

Start with the first topic

10.1

Designing a Web Crawler's Visited-URL Filter

A crawler must skip URLs it has already fetched across billions of URLs and thousands of workers. Canonicalise URLs, partition the URL space by host across crawler workers, keep a Bloom filter of visited URLs per partition, and accept that a false positive means an unvisited URL is occasionally skipped, which is usually fine for a crawler.

9 min 1 diagram 1 code practice

10.2

Billion-User Membership Service and a 2-Billion Product Catalogue

For 1B users at 100K queries/sec, a local filter per API node answers most "does this user exist?" checks in microseconds, Redis caches hot records, and the database stays authoritative. For a 2B-ID catalogue where most requests are invalid, a filter is the cheapest membership accelerator: ~2.4 GB at 1%.

8 min 1 diagram practice

10.3

Malware Hashes and Global Blocklists

For 1B known-malicious file hashes, a local filter says "definitely not known-bad" for almost every upload in microseconds; "maybe" is confirmed against the authoritative store. A 5B-entry global blocklist with sub-millisecond checks uses local static filters per node, updated via versioned snapshots and deltas, with a fail-closed or quarantine policy.

8 min 1 diagram practice

10.4

Distributed Object Existence and an LSM Storage Engine

For 10B stored objects, fast existence checks use per-shard filters (co-located with storage nodes), local filters for hot namespaces, and a shared filter only where query rates allow; deletes push toward cuckoo filters or rebuilds. In an LSM engine, the same idea appears as one filter per SSTable, built at flush time.

7 min 1 diagram practice

10.5

Capstone: Bloom + Redis + Kafka + Database, and the Anti-Patterns

The full architecture: clients → rate limiter → application with a Bloom filter → "absent" rejected, "maybe" → Redis → database; database changes → outbox/CDC → Kafka → Bloom updater → versioned filters; snapshots, rebuilds, metrics and failure plans. Plus the list of when not to use a Bloom filter at all.