Engineering Atlas › System Design Fundamentals

Bloom filters: cheap membership checks

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The structure

Start with m bits, all zero, and k hash functions that each map a key to a position in [0, m). To add a key, set the k bits it maps to. To query, check those k bits: if any is zero, the key was never added; if all are one, the key was probably added, or other keys happened to set every one of those bits.

That asymmetry is the whole point. A false negative is impossible because adding a key only ever sets bits, so a key's bits stay set. A false positive happens when other keys collectively cover all k of a new key's positions.

The math you actually use

After inserting n keys, the chance that a given bit is still zero is about e^(-kn/m). A query for an absent key returns "yes" only if all k probed bits are one, so the false-positive rate is about (1 - e^(-kn/m))^k.

For a fixed memory budget, that rate is lowest when k = (m/n) ln 2, at which point about half the bits are set. Solving for m at a target rate p gives m = -n ln p / (ln 2)^2, which is where 1.44 * log2(1/p) bits per key comes from. Useful anchors: 1 million keys at 1% need about 9.6 million bits (1.2 MB) and 7 hash functions; 0.1% needs 14.4 bits and 10 hashes (Redis docs). Each extra 4.8 bits per key cuts the rate by ten.

Two consequences matter in practice. The filter's size depends only on the count and the rate, not on whether keys are 8-byte ids or 2 KB URLs. And the rate is a function of n: insert twice the planned keys into a 1% filter and it climbs to about 15%.

Where it earns its keep

The pattern is always "a cheap, probably-correct no in front of an expensive, definitely-correct check". This is the finding things fast problem shape:

Variants

A counting Bloom filter replaces each bit with a small counter, so deletes become decrements. Four-bit counters are enough in practice, but memory grows fourfold (Fan et al.). A scalable Bloom filter chains new, larger sub-filters, each with its error rate multiplied by a tightening ratio (0.8 to 0.9 works well), so the total rate stays bounded without knowing n in advance (Almeida et al.). A blocked Bloom filter puts all k probes for a key in one cache line, trading a slightly higher rate for one memory miss per lookup. A cuckoo filter (its own lesson) stores fingerprints, supports deletes and beats Bloom on space below about 3%.

Down the stack

Layer 1The contract

For any key that was added and not removed, might_contain returns true: no false negatives, ever, including after a merge by bitwise OR of two filters with the same m, k and hash functions. For a key never added, the probability of true is about (1 - e^(-kn/m))^k where n is the number of keys actually inserted, assuming hashes behave like independent uniform functions. There is no enumeration, no count, and, for the plain form, no delete. A counting filter adds delete, but only for keys that were actually added: removing a key that was never added can create false negatives for others.

Layer 2The mechanism

Real implementations do not run k independent hash functions. Kirsch and Mitzenmacher showed that two hashes are enough: probe h1 + i * h2 mod m for i from 0 to k - 1, with no asymptotic loss in accuracy (Kirsch and Mitzenmacher). RocksDB computes one 64-bit hash per key and derives every probe from it.

RocksDB's full filter, in the implementation used from format_version=5 (RocksDB 6.6) onward, confines all of a key's probes to one 64-byte cache line. Its documentation works through the cost: at 10 bits per key and 6 probes, the cache-local filter has about a 0.95% false-positive rate against 0.84% for an unconstrained one, a factor of 1.13, accepted for one cache miss per lookup instead of six. Since 6.15 RocksDB also offers Ribbon filters, which reach 1% at about 7 bits per key instead of 10, at 3 to 4 times the construction CPU (RocksDB wiki). Ribbon solves a small linear system over the keys instead of setting bits, so it suits filters built once per file (Dillinger and Walzer).

Cassandra exposes the rate directly as bloom_filter_fp_chance per table, defaulting to 0.01, or 0.1 for tables using leveled compaction, where each read touches fewer SSTables. The filters live off-heap, and a changed setting applies only to SSTables written afterwards, so existing files keep the old filter until compaction or nodetool upgradesstables -a (Cassandra docs). Redis's BF.RESERVE key error_rate capacity builds a scalable filter: when it fills, it adds a sub-filter with twice the capacity (the EXPANSION default) and more hash functions, and lookups check every sub-filter. NONSCALING saves one hash function but lets the rate climb past capacity. These commands were the RedisBloom module until Redis 8, which builds them into the server and sets defaults such as bf-error-rate 0.01 in redis.conf (Redis docs).

Layer 3The machine

A filter for a billion keys at 1% is about 1.2 GB, far beyond the last-level cache, so each random probe is a DRAM access of roughly 80 to 100 ns. A classic filter with k = 7 touches up to seven cache lines; a negative lookup usually stops at the first zero bit, but a positive one pays for all seven. A blocked filter pays one miss, then tests bits within a 512-bit line with shifts and masks. Hashing a short key costs 10 to 20 ns.

Those nanoseconds are free next to what they save: an NVMe random read costs about 100 µs and a cloud block-storage read 0.5 to 2 ms. The constraint that bites is memory: filters must stay resident, or the lookup itself starts missing the block cache and hitting disk.

Why it's built this way

  1. Exact membership needs space proportional to the keys themselves, and keys can be large, so a fixed number of bits per key buys a bounded error instead.
  2. Bits are only ever set, so no false negatives are possible; the price is that a bit cannot be cleared without risking another key's answer, hence no delete.
  3. Independent hash functions are expensive, so two hashes are combined into k probes.
  4. Random probes into a large array miss cache, so modern filters confine probes to one cache line and accept a slightly higher rate.
  5. The filter's value is the expensive operation it skips, so the rate is chosen by comparing false-positive cost against memory cost, not by a rule of thumb.

Diagram

flowchart LR
    K["key: user:42"] --> H["hash once, derive k probes"]
    H --> P1["bit 17"]
    H --> P2["bit 203"]
    H --> P3["bit 911"]
    P1 --> T{"all probed bits set?"}
    P2 --> T
    P3 --> T
    T -->|no| N["definitely absent: skip disk read"]
    T -->|yes| Y["maybe present: read SSTable block"]
    Y --> R{"key in block?"}
    R -->|yes| F["found"]
    R -->|no| FP["false positive: one wasted read"]

Worked example

An edge cache sees 50 million distinct URLs a day, and logs show about 70% of them are requested exactly once. Caching those wastes disk writes and evicts content that would have been reused. The fix: admit an object to cache only if its URL is already in a "seen" filter; otherwise just add it.

Sizing at p = 1%: m = 50,000,000 * 9.585 ≈ 479 million bits, about 60 MB, with k = 7. Because a plain filter cannot delete, the server keeps two: current receives new URLs and previous holds yesterday's; a lookup checks both, and at midnight previous is dropped and current takes its place. Memory is 120 MB, small next to a multi-terabyte disk cache.

The effect: of 50 million first requests, 35 million one-hit objects are never written to disk. False positives admit 1% of first requests anyway, about 500,000 extra writes a day, which is negligible. If traffic doubles to 100 million URLs without resizing, the rate climbs to about 15% and 7.5 million extra writes appear, so the filter should be sized from peak traffic with headroom, or replaced with a scalable filter.

In a storage engine the same arithmetic sets the RAM bill. An LSM store with 2 billion keys across 7 levels needs 2.5 GB for 10-bit-per-key filters; a missing-key lookup then expects 0.07 wasted block reads instead of up to 7. Halving to 5 bits per key saves 1.25 GB but raises the rate to about 9%, or 0.6 wasted reads per miss.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Classic BloomSimple, mergeable by OR, inserts never failNo delete, k cache misses per positive lookupAppend-only sets of known size
Blocked BloomOne cache miss per lookupSlightly higher rate at the same memoryLarge in-memory filters on hot read paths
Counting BloomSupports deleteAbout 4x memory, counter overflow must be handledSets with churn, where memory is cheap
Scalable BloomNo need to know n up frontLookups check every sub-filter, more memory overallSets that grow unpredictably
Cuckoo filterDelete, less memory below about 3%Inserts can fail near fullLow target rates with deletes
Ribbon filterAbout 30% smaller than Bloom at the same rateSlower to build, immutableWrite-once filters such as SSTables

Pitfalls in production

Leadership lens

Check yourself

  1. A 1% filter sized for 10 million keys now holds 20 million. Roughly what is its false-positive rate, and why?

    Show answer

    About 15%. With the same m and k, doubling n doubles kn/m, so far more bits are set and the chance that all seven probes hit set bits rises sharply.

  2. Why can a plain Bloom filter never return a false negative?

    Show answer

    Adding a key only sets bits and nothing ever clears them, so every bit a key set on insert is still set when it is queried.

  3. Why do RocksDB's filters confine probes to one cache line even though it raises the false-positive rate?

    Show answer

    A large filter lives in DRAM, and each random probe costs a cache miss. One miss per lookup instead of six is worth a rate increase of about 1.13x.

  4. When would you pick a counting Bloom filter over a cuckoo filter?

    Show answer

    When the target rate is relatively high, memory is not tight and you want inserts that never fail; cuckoo filters win on space at low rates but can reject inserts near full.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →