Bloom Filters: How Databases Skip Disk Reads They Don't Need

An earlier post on this blog covers how LSM-tree databases like RocksDB and Cassandra trade read speed for write speed: a lookup has to check the in-memory memtable, then potentially every on-disk SSTable, newest to oldest, until it finds the key or runs out of places to look. For a key that genuinely exists, that is a bounded, if annoying, cost. For a key that does not exist - which is a large fraction of real lookups, since applications check caches and dedupe sets constantly - it looks like the worst case every time: check every SSTable, find nothing, and only then report “not found.”

Bloom filters exist to make that specific case cheap. They cannot make a positive lookup faster, but they can make most negative lookups skip disk entirely.

The one guarantee a bloom filter makes

A bloom filter answers exactly one question about a set: is this item definitely not in the set, or maybe in the set. That asymmetry is the entire design:

• If the filter says “definitely not present,” that is always true. No false negatives, ever.
• If the filter says “maybe present,” it might be wrong. That is the false positive, and it is the price paid for the compact representation.

A filter that could produce false negatives would be useless for what databases need it for: ruling out an SSTable without opening it. A false negative would mean skipping a file that actually contains the key, silently returning the wrong answer. A false positive just costs an unnecessary disk read that comes back empty - correctness is preserved, only a probabilistic amount of performance is lost.

What it actually is

The structure is a fixed-size bit array of length m, all zeros to start, plus k independent hash functions that each map an item to one position in that array.

Inserting an item runs it through all k hash functions and sets every resulting bit to 1:

flowchart TB
    subgraph insert[add user:42]
        direction TB
        X[user:42] --> H1[hash 1] --> P1((bit 2))
        X --> H2[hash 2] --> P2((bit 5))
        X --> H3[hash 3] --> P3((bit 7))
    end
    insert ~~~ bits

    subgraph bits[bit array]
        direction LR
        B0["0"]:::z --- B1["0"]:::z --- B2["1"]:::hit --- B3["0"]:::z --- B4["0"]:::z --- B5["1"]:::hit --- B6["0"]:::z --- B7["1"]:::hit
    end

    classDef z fill:#1e293b,stroke:#475569,color:#94a3b8
    classDef hit fill:#b45309,stroke:#f59e0b,stroke-width:2px,color:#fff

Checking an item hashes it the same way and looks at those same k positions. If every one of them is a 1, the filter reports “maybe present.” If even one is a 0, the item was never inserted, because inserting it would have set that bit:

flowchart LR
    subgraph miss[contains user:999]
        direction LR
        Y[user:999] --> G1[hash 1] --> Q1((bit 4))
        Y --> G2[hash 2] --> Q2((bit 7))
        G2 -.->|bit is 0, stop| R[definitely absent]
    end

    classDef stop fill:#7f1d1d,stroke:#ef4444,color:#fff
    class R stop

A real check short-circuits on the first zero bit it finds, which is also why a negative answer is usually the cheap path: most lookups for absent keys never touch all k positions.

The false positive comes from bit reuse: with enough items inserted, some other combination of items can happen to set all k bits an absent item would also hash to. There is no way to tell that apart from a genuine membership at check time - the bit array only stores 1s and 0s, not which item set them.

The math behind the false positive rate

For n items inserted into an m-bit array with k hash functions, the expected false positive rate is approximately:

(1 - e^(-kn/m)) ^ k

which is the standard result covered on the Wikipedia bloom filter page. Two consequences follow directly from that formula, and they are what every real system’s defaults are built around:

• More bits per item lowers the false positive rate, with diminishing returns. Widely cited (and confirmed on the same page): fewer than 10 bits per element gets you under a 1% false positive rate, independent of how many items are in the set. RocksDB’s own Bloom filter documentation puts a number on that trade directly - “9.9 bits per key (1% false positive rate) is 99% as effective as 100 bits per key” - which is why RocksDB recommends roughly 10 bits per key rather than something larger.
• For a fixed bit budget, there is an optimal number of hash functions, k = (m/n) * ln(2). Too few hash functions under-uses the array; too many sets bits faster than necessary and saturates it early. Most production implementations compute k from the target false positive rate rather than hardcoding it.

None of this changes the one-directional guarantee. It only changes how often “maybe present” is a lie.

Where real systems actually use this

RocksDB attaches a bloom filter to every SSTable file at write time. A lookup checks each candidate file’s filter before opening it; a “definitely not present” result means that file is skipped without a single block read from disk. The RocksDB wiki frames the entire feature around exactly this: “when the filter policy is set, every newly created SST file will contain a Bloom filter, which is used to determine if the file may contain the key we’re looking for.” This is the missing piece from the LSM-tree read path: without it, “check every SSTable” would mean a disk read per file; with it, most of those become an in-memory bit-array check instead.

Apache Cassandra does the same thing per SSTable, and exposes the trade-off as a per-table knob. Its current documentation states the defaults plainly: bloom_filter_fp_chance defaults to 0.1 for tables using LeveledCompactionStrategy and 0.01 for everything else - a table owner who reads mostly by scanning full partitions can raise that number and trade a higher false positive rate for a smaller filter held in memory.

PostgreSQL’s BRIN indexes support a bloom operator class for exactly this purpose on columns with poor natural ordering, where a plain BRIN range summary would not help. Per the current PostgreSQL documentation, the false_positive_rate parameter “defines the desired false positive rate used by BRIN bloom indexes for sizing of the Bloom filter… The default value is 0.01, which is 1% false positive rate” - the same order of magnitude every other system above converges on, because the underlying math is the same regardless of what is being filtered.

The pattern across all three: a bloom filter never replaces the real lookup. It sits in front of one, and its only job is to make the common “not here” case skip the expensive part.

Building one

Here is a working, dependency-free bloom filter in Go. It uses the standard library’s hash/fnv to get two independent hashes, then derives k hash values from those two using the Kirsch-Mitzenmacher technique (h1 + i*h2) instead of running k separate hash functions - a well-known trick for cutting the per-insert hashing cost without hurting the false positive rate in practice.

package main

import (
	"fmt"
	"hash/fnv"
	"math"
)

type bloomFilter struct {
	bits []bool
	k    int
}

func newBloomFilter(expectedItems int, targetFPRate float64) *bloomFilter {
	m := int(math.Ceil(-float64(expectedItems) * math.Log(targetFPRate) / (math.Ln2 * math.Ln2)))
	k := int(math.Round(float64(m) / float64(expectedItems) * math.Ln2))
	if k < 1 {
		k = 1
	}
	return &bloomFilter{bits: make([]bool, m), k: k}
}

func (b *bloomFilter) hashPair(item string) (uint64, uint64) {
	h1 := fnv.New64a()
	h1.Write([]byte(item))

	h2 := fnv.New64()
	h2.Write([]byte(item))

	return h1.Sum64(), h2.Sum64()
}

func (b *bloomFilter) positions(item string) []int {
	h1, h2 := b.hashPair(item)
	positions := make([]int, b.k)
	for i := 0; i < b.k; i++ {
		combined := h1 + uint64(i)*h2
		positions[i] = int(combined % uint64(len(b.bits)))
	}
	return positions
}

func (b *bloomFilter) add(item string) {
	for _, pos := range b.positions(item) {
		b.bits[pos] = true
	}
}

func (b *bloomFilter) mightContain(item string) bool {
	for _, pos := range b.positions(item) {
		if !b.bits[pos] {
			return false
		}
	}
	return true
}

func main() {
	bf := newBloomFilter(1000, 0.01)

	present := []string{"user:42", "user:7", "user:100"}
	for _, item := range present {
		bf.add(item)
	}

	absent := []string{"user:999", "user:1000"}
	for _, item := range append(present, absent...) {
		fmt.Printf("%-10s -> might contain: %v\n", item, bf.mightContain(item))
	}
}

present items always report true - the filter never produces a false negative. Run it against a much larger absent set and, at k and m sized for a 1% target rate, you should see roughly 1% of absent items misreported as true, the same shape of trade-off RocksDB, Cassandra, and Postgres all make at production scale.

When it is the wrong tool

A bloom filter has no way to remove an item: clearing the bits an item set could also clear bits shared by something else that hashed to the same positions. Systems that need deletion use a counting bloom filter, which replaces each bit with a small counter, incremented on insert and decremented on delete - more memory per slot in exchange for that capability.

It also cannot tell you what is in the set, only whether a specific item you already have in hand might be. It is a membership test, not an index, and not a substitute for one - which is exactly why every system above pairs it with a real lookup structure rather than using it alone. The filter’s whole value is deciding, cheaply, when that real lookup is worth doing at all.