Internals · LSMbloom filterprobabilisticfalse positivehashpoint read

Bloom Filters: Skipping Files That Cannot Contain the Key

A point read in an LSM tree may have to consult ten files, and most of them do not hold the key. A bloom filter answers "definitely not here" from a few bits per key, with no false negatives and a tunable false-positive rate — turning ten block reads into one.

▶ Interactive Interview question

Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

Problem
A GET for a key that exists in one of ten SSTables — or in none — must not read a data block from every file. We need a cheap way to say "do not bother opening this file".
↓
Naive solution
Check the file's min/max key range. If the key is outside the range, skip the file.
↓
Why it breaks
Level-0 files each cover nearly the whole key space, so the range check almost never excludes anything. A full set of the file's keys in memory would work, but for a million 20-byte keys that is 20 MB per file — hundreds of megabytes for an open store.
↓
Better idea
We do not need the keys, only a yes/no on membership — and we can tolerate an occasional wrong "yes" as long as "no" is never wrong. That relaxation lets us use hashing into a fixed bit array instead of storing keys.
↓
Internal mechanism
A bit array of m bits and k hash functions. Insert: set the k bits h₁(key)…hₖ(key). Query: if any of the k bits is 0 the key was never inserted; if all are 1 it probably was. With m/n ≈ 10 bits per key and k ≈ 7, the false-positive rate is about 1%.
↓
Trade-offs
Ten bits per key instead of 160 — and 99% of the files that do not contain the key are skipped with zero data I/O. The 1% false positives cost an index lookup and one block read. The filter cannot answer range queries, and cannot delete keys — fine for immutable files.
↓
Real database
Every SSTable in RocksDB, LevelDB, Cassandra, HBase and ScyllaDB carries a bloom filter (RocksDB uses a cache-line-local "ribbon"/blocked variant). PostgreSQL offers a bloom index type; Cassandra exposes bloom_filter_fp_chance per table.

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

A no that is always right

A bloom filter is a very small summary of a set that can answer one question: "is this key definitely absent?" When it says no, the key is not there. When it says maybe, you have to look. For an LSM engine that is exactly the right question, because most of the files a read would check do not hold the key.

The filter for a million keys is about a megabyte; the keys themselves would be twenty. That is why every SSTable can afford one and keep it in memory.

The question a point read asks

By the time a read reaches disk it has a list of candidate files: every level-0 file, plus one file per deeper level whose range covers the key. For a store with four L0 files and three deeper levels that is seven candidates, and at most one of them holds the newest version — often none, when the key does not exist or lives in the memtable. Reading a block from each candidate would make read cost proportional to file count, which grows with ingest rate. The engine needs a way to reject candidates without I/O.

Min/max ranges reject little at level 0, where every flush covers the whole key space. A complete in-memory key set per file would be as large as the keys. What we actually need is much less: a fast, approximate, memory-cheap membership test whose only allowed error is a wasted read, never a missed key.

Bit array plus k hash functions

The structure is a bit array of m bits, all 0 initially, and k hash functions that each map a key to a position in [0, m). To insert a key, set the k bits it hashes to. To query, check the same k bits: if any is 0, the key was never inserted — a 1 bit can only have been set by an insert, so an inserted key's bits are all 1. If all are 1, the key was probably inserted, but the bits might have been set by other keys in combination: a false positive.

This is the Bloom Filter from the DSA layer, placed exactly where it earns its keep. Two properties make it fit SSTables: the file is immutable, so the filter is built once from the exact key set and never needs deletion (which a plain bloom filter cannot do); and the read path only needs to skip files, so a false positive costs one wasted block read rather than a wrong answer.

m = 32 bits, k = 3, after inserting apple and mango

bit    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
       0 0 1 0 0 1 0 0 0 0  0  1  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0
apple  → bits 2, 14, 27      all set → "maybe"   (true positive)
mango  → bits 5, 11, 20      all set → "maybe"   (true positive)
kiwi   → bits 2, 9, 20       bit 9 is 0 → "definitely not"   (true negative, no I/O)
grape  → bits 5, 14, 27      all set → "maybe"   (FALSE POSITIVE: index + block read for nothing)

Sizing: bits per key and the false-positive rate

After inserting n keys with k hashes into m bits, the probability that a given bit is still 0 is (1 − 1/m)^(kn) ≈ e^(−kn/m). A false positive needs all k probed bits to be 1, so FP ≈ (1 − e^(−kn/m))^k. For a fixed m/n the best k is (m/n)·ln 2 ≈ 0.69·(m/n). The numbers engineers remember: 10 bits per key, k = 7 → ≈ 1%; 8 bits/key → ≈ 2%; 16 bits/key → ≈ 0.05%; 4 bits/key → ≈ 15% and barely worth having.

The cost side: a filter for one million keys at 10 bits/key is 1.25 MB, roughly 2% of a 64 MB file, and it lives in memory for every open file. Cassandra defaults bloom_filter_fp_chance to 0.01 for size-tiered and 0.1 for leveled compaction — leveled has fewer candidate files per read, so it can afford a worse filter per file.

FP ≈ (1 − e^(−kn/m))^k with the optimal k

bits per key (m/n)	optimal k	false-positive rate	filter for 1M keys
4	3	≈ 14.7%	0.5 MB
8	6	≈ 2.2%	1.0 MB
10	7	≈ 0.8%	1.25 MB
12	8	≈ 0.3%	1.5 MB
16	11	≈ 0.05%	2.0 MB

The read path across levels

The full point-read algorithm is: check the memtable; then for each candidate file in newest-first order, check range, check bloom filter, and only on "maybe" search the index and read one block; stop at the first version found. The expected number of block reads for a key that exists in the deepest level is about 1 + (candidates − 1) × FP: with seven candidates and 1% filters, ≈ 1.06. For a key that exists nowhere it is candidates × FP ≈ 0.07 — negative lookups become almost free, which matters for "insert if absent" workloads.

This is why the LSM read path is acceptable in practice despite the multiple-file design, and why the bloom filter belongs in the Write, Read and Space Amplification read-amplification formula rather than as a footnote. It is also why a filter that does not fit in memory is a disaster: a filter read from disk costs as much as the block read it was supposed to save.

GET across the levels

1get(key):
2  if key in memtable:            return memtable[key]        # value or tombstone
3  for file in L0 files newest→oldest, then one file per level L1, L2, …:
4      if key < file.min or key > file.max:  continue          # metadata only
5      if not file.bloom.might_contain(key): continue          # ~99% of non-holders skipped, 0 I/O
6      hit = search(file.index, key) → read block → scan       # 1 block read
7      if hit: return hit                                      # newest version wins
8  return ABSENT

Variants engines actually ship

A textbook filter with k = 7 touches seven random memory locations per query, and on a modern CPU that is seven cache misses — often more expensive than the hashing. Blocked bloom filters hash the key to one 64-byte block first, then set k bits inside that block: one cache miss, slightly worse FP for the same bits. RocksDB's ribbon filter encodes membership as the solution of a linear system and matches the FP rate of a bloom filter with about 30% fewer bits, at higher build cost — a good trade for files written once and read many times.

The limitation that no variant removes: a hash-based filter cannot answer "is any key in [a, b] present?". Prefix bloom filters help for prefix-bounded ranges; for everything else, range reads must open every overlapping file.

Key points

A bloom filter answers "definitely not in this file" from ~10 bits per key; "maybe" means read the index and one block.
No false negatives ever; false positives at a rate ≈ (1 − e^(−kn/m))^k — about 1% at 10 bits/key with k = 7.
Point reads consult every candidate file's filter; expected block reads drop from the number of files to ≈ 1 + (files − 1) × FP.
Negative lookups become nearly free — the reason "insert if absent" is cheap in LSM engines.
Filters must stay in memory; blocked and ribbon variants reduce cache misses and bits.
Hash filters cannot prune range scans.

Bloom filter

Bloom filter: 'definitely not here' in a handful of bits

Add keys and watch which bits they set; query keys that were never added and find the false positive. No false negatives, ever — a 0 bit is proof of absence.

101

110

120

131

140

150

160

170

181

190

200

211

220

230

240

250

260

271

280

290

300

311

key

in filter:

kiwi → bits 25, 10, 19. At least one bit (25, 19) is 0, so the filter answers definitely not. This answer is never wrong: an inserted key would have set that bit.

keys (n)

bits set

8/32 (25%)

bits per key

10.7

optimal k

7 = (m/n)·ln 2

theoretical FP (1 − e^(−kn/m))^k1.5%

measured FP (400 absent probes)2.3%

Sizing rule: ~10 bits per key with k ≈ 7 gives ≈ 1% false positives; 16 bits per key ≈ 0.05%. With 32 bits and 3 keys you have 10.7 bits per key. Push the slider down or add keys until the filter saturates — a filter with every bit set says "maybe" to everything and is worth nothing.

m bits32k hashes3

Hashes are FNV-1a with 3 different seeds; the measured rate probes 400 keys that were never added.

When to use — and when not

Use it when

This mechanism fits any read path that must check several immutable stores for a key: LSM levels, cache tiers, distributed lookups.
It fits when memory per key is scarce and a small false-positive rate is acceptable.

Avoid it when

This mechanism does not fit range predicates or prefix queries beyond a fixed prefix.
It does not fit mutable sets that need deletions (use a counting filter or rebuild).
It does not fit stores with one or two files, where a range check is enough.

Failure modes

Filters evicted from memory under pressure: every lookup now pays a filter read plus a block read.
Bits-per-key set too low to save memory: 15% false positives quietly double read I/O.
Expecting the filter to help BETWEEN queries.
Rebuilding a filter after deletes without realising a plain bloom filter cannot unset bits.