Stackbook Logo
data-stateestablished · low operational burden

Bloom Filter

Also known as: probabilistic-membership-filter

Intent

Cheaply answer whether an item is definitely absent or possibly present, avoiding expensive lookups for misses.

Problem

Checking disk, a remote cache or another service for keys that mostly do not exist wastes time and I/O. Holding every key in memory is too costly. A small structure that rules out most misses would save the expensive lookup.

Forces

  • •Misses are common and expensive to confirm
  • •Memory for the filter must be small
  • •False positives are tolerable but false negatives are not
  • •Elements cannot be removed from a basic filter

Solution

Overview

A Bloom filter is a probabilistic set. It answers "definitely not present" or "maybe present". Databases like Cassandra, HBase and RocksDB keep one per data file so reads skip files that cannot hold the key.

How it works

Adding and testing with three hash functions.

bits: 0 0 0 0 0 0 0 0 0 0
add "alice": h1=1 h2=4 h3=8 -> bits 1,4,8 set
test "bob":  h1=2 -> bit is 0 -> definitely absent
test "carol": bits all 1 (set by others) -> maybe present

false positive rate ~ (1 - e^(-kn/m))^k

The optimal number of hashes is about (m/n) times ln 2.

Variants address the limits. Counting Bloom filters replace bits with small counters so items can be removed. Cuckoo filters support deletion and often use less space at low error rates. Scalable Bloom filters add new filter layers as the set grows. In an LSM engine, each SSTable has its own filter built at flush time, and because SSTables are immutable the filter never needs deletion. A filter in front of a cache can stop requests for nonexistent keys from reaching the database, which blocks a common abuse pattern.

Pitfalls

  • Undersizing the filter, which silently pushes the false-positive rate toward 100 percent.
  • Using weak or correlated hash functions.
  • Expecting to delete items; use a counting or cuckoo filter if you need removal.
  • Putting the filter in front of data where most lookups are hits, so it only adds cost.

Key takeaways

  • No false negatives, tunable false positives.
  • Use it to skip expensive misses, never as the final answer.
  • Size it from expected item count and target error rate.
  • Rebuild when the set grows past the design size.

✓ When to Use

  • •Skipping SSTables or partitions that cannot contain a key
  • •Cache-penetration protection for nonexistent keys
  • •Deduplication checks over very large key sets

✗ When Not to Use

  • •Cases where a false positive is unacceptable and not rechecked
  • •Sets needing deletion without a counting or cuckoo variant
  • •Small sets that fit in a normal hash set

Pros

  • +Tiny memory footprint compared with storing keys
  • +Constant-time add and test
  • +No false negatives

Cons

  • −False positives at a tunable rate
  • −No deletion in the basic form
  • −Must be sized in advance or rebuilt as it fills

Cost Profile

Infrastructure

Low - a few bits per element

Operational

Low - rebuild periodically

Cognitive

Medium - probabilistic reasoning

Failure Modes

  • Filter saturates as items exceed design size and false positives climb

  • Treating a positive as proof of existence and skipping the real check

  • Deleted keys remain set, so stale positives persist until rebuild

Real-World Examples

Alternatives

    Related Patterns

    • caching
    • lsm-tree-storage

    Competency Domains

    data stateeconomics evolution