Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)
Scene 05

Definitely-not-here, in one bitmap — Bloom filters on every SSTable

Each SSTable carries a tiny bitmap that, for any key, answers 'definitely not in this file' or 'maybe' — so missing-key reads skip almost every file without touching disk, making the newest-first walk tolerable even with many files.

Previously

Walking every file on every miss is the cliff. The way out is a tiny per-file structure that says 'definitely not here' before we touch disk — and is small enough to keep in RAM for every file.

Scene 05

Definitely-not-here, in one bitmap

  1. Watch
  2. Try it
  3. Predict
  4. Capture
QUERYworkload: mixedGET —probes every SSTable's bloom →BLOOM TUNINGBITS / KEY10FALSE-POSITIVE RATE1.0%rule of thumb: 10 b/k ≈ 1%BLOOM000007[a … h]idleBLOOM000006[i … p]idleBLOOM000005[q … z]idleBLOOM000004[a … z]idleBLOOM000003[b … y]idleDISK READS THIS QUERY0/ 5 files5 skipped by bloomFive SSTables; each carries a tiny bitmap. Idle.
What to watch for

Five SSTables, each topped with a bloom bitmap. Watch a missing-key GET (most files reply 'definitely no') and a present-key GET (one file replies 'hit'). Disk reads counter shows how many files we ACTUALLY had to read.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

Bloom-aware get
skip files whose bloom says 'definitely no'
def get(key):
    if key in memtable: return memtable[key]
    for sst in sstables_newest_first():
        if not sst.bloom.maybe_contains(key):
            continue                       # skip — no disk read
        v = sst.read(key)                  # 'maybe' → block read
        if v is FOUND: return v            # may be tombstone
    return not_found
Bits-per-key rule of thumb
linear RAM, exponential FP-rate decay
# bloom filter: per-file bitmap of m bits set by k hash functions
# false-positive rate ≈ (1 - e^(-kn/m))^k
# practical:
#   1.5 bits/key  →  ~50%   FP   (almost useless)
#  10   bits/key  →   ~1%   FP   (canonical default)
#  15.5 bits/key  →   ~0.1% FP   (diminishing returns)
# RAM grows linearly with bits/key. Pick 10 unless …
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 05 of 11, in the Read side act — Newest wins; bloom filters skip the misses.. Each SSTable carries a bloom filter that says 'definitely no' or 'maybe' — eliminating disk reads on misses, not on hits.

Up next. Bloom filters bound the cost of looking; they don't bound the number of files. Flushes keep adding files and disk grows. Sooner or later we have to merge them — that's the GC of the LSM world.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes