Where Bloom Filters Live in Real Systems

Real production uses of Bloom filters:

Databases

• LevelDB, RocksDB: Per-SSTable Bloom of all keys in that SSTable. A GET first asks every SSTable's Bloom; only SSTables that say MAYBE get a disk read. Read amplification drops from "scan every SSTable" to roughly "scan the ones that contain the key" — order-of-magnitude wins on cold reads.
• Cassandra: Per-SSTable Bloom for the same reason. Configurable false-positive rate in cassandra.yaml.
• HBase: Per-StoreFile Blooms; same pattern.
• BigTable (the paper): the original Bloom-per-SSTable design.

Caches and CDNs

• Squid: Cache digests — each cache exposes a Bloom of its contents to peers. A peer can skip a useless cache-peer request when the Bloom says NO.
• Varnish / CloudFront-style edge caches: Bloom of recently-invalidated URLs avoids unnecessary origin reads.

Browsers

• Chrome Safe Browsing (legacy): A few-MB Bloom of known-malicious URL prefixes shipped to the browser. CHECK before navigation; on MAYBE, a privacy-preserving remote lookup. Modern Safe Browsing uses sharded prefix databases, but the design principle is identical.

Cryptocurrency

• Bitcoin BIP 37 SPV: Lightweight clients send a Bloom of their wallet addresses to a full node; the full node returns blocks with matching transactions. Privacy via Bloom noise (later proved weaker than hoped; BIP 157/158 "compact filters" superseded it).

Networking

• CDN cache invalidation: When content is invalidated at the origin, push a Bloom of invalidated URLs to all edges. Edges treat MAYBE as "force a recheck"; CACHED reads stay fast.
• Network routers: Some routing protocols use Bloom filters to summarize reachable destinations between peers.

In this exercise

You'll implement the CDN cache-invalidation pattern: an INVALIDATE op adds a URL to the Bloom; CHECK_CACHE returns INVALIDATED (recheck) if Bloom says MAYBE, else CACHED (use). False positives waste a recheck; false negatives would serve stale data, which is the unacceptable failure mode this pattern explicitly prevents.