RocksDB
An embedded LSM key-value engine built for flash and in-memory workloads.
RocksDB is an embedded persistent key-value store derived from LevelDB and tuned for fast storage. Writes append to a WAL and a memtable; flushes produce immutable SST runs; background compaction merges them by level. It is a library, not a server: the process embedding it owns persistence and recovery.
Log-structured storage
Every write lands in a WAL and the active memtable. Full memtables are flushed as sorted string tables (SSTs); existing files are never edited in place.
Column families
Keyspaces are grouped into column families, each with its own memtables and SST trees but sharing the WAL — independent write workloads without cross-family interference.
Tunable everything
Write buffer sizes, level counts, compaction style, block cache, and bloom-filter bits per key are configuration, which is why RocksDB anchors so many storage products.
Single-writer MVCC
Writes serialize through one write thread by default; readers see consistent memtable/SST state via sequence numbers. A transaction API adds optimistic and pessimistic modes.
The write path is an append
A put appends one record to the WAL and one entry to the active memtable, then returns. The memtable is a skiplist keyed by user key with a sequence number, so repeated puts to the same key coalesce in memory and only the newest version eventually survives compaction.
When the memtable reaches its write-buffer size it becomes immutable, a new memtable takes over, and a background flush sorts it into an L0 SST file. Flushes never rewrite existing files — immutability is what makes recovery and concurrency simple.
# rocksdb write path, conceptually
put(key, value):
wal.append(seq, key, value)
memtable.insert(seq, key, value)
if memtable.full(): schedule_flush()
The read path pays for that
A get consults, in order: the active memtable, immutable memtables awaiting flush, L0 files newest-first, then each lower level. The first version of the key found wins; a tombstone stops the search with "not found". Bloom filters per SST skip files that cannot contain the key.
This newest-first chain is LSM read amplification: a lookup may touch many structures. Compaction exists to bound it — lower levels hold fewer, larger runs covering disjoint key ranges.
Compaction: the LSM bargain
Leveled compaction merges overlapping L0 files plus a key range of the next level, dropping shadowed versions and expired tombstones, and rewriting the result as new files. The cost shows up as write amplification: one logical write may be rewritten several times across levels.
The walkthrough below traces one key through memtable, flush, tombstone, and compaction end to end. Distinguish this embedded engine from a database server: RocksDB has no query language, no network protocol, and no replica logic of its own — engines like Cassandra and (historically) CockroachDB embed it or its ideas.
Diagrams
static storyboard — WebGPU animates when available
A live WebGPU particle field tinted to this exhibit. Plays only with WebGPU and no reduced-motion preference; a static storyboard renders for everyone else.
[caption] Embedded engine model: no server, no query layer — the host process calls put/get directly.
Every write appends to the WAL and the memtable; full memtables become immutable L0 SST runs. Nothing on disk is ever edited in place.
| puts | 2 |
| deletes | 1 (tombstone) |
| flushes | 2 |
| compaction dropped | c = 7 (shadowed) + expired tombstone |
| lookup(c) after compaction | 2 structures, not found |
All steps
- put(c = 5) — The write appends to the WAL (durability) and lands in the in-memory memtable. No disk read, no index update — this is why LSM writes are fast.
- put(c = 7) overwrites in memory — The overwrite coalesces in the memtable: the older c = 5 never reaches storage. One WAL record per put, though — the log keeps both.
- Flush → immutable run R3 — When the memtable fills it is flushed as a sorted, immutable run. Writes go to a new file; nothing in place is ever mutated.
- lookup(c) — memtable hit — The lookup checks the memtable first: c = 7 found after touching one structure. Recency is checked first because newer values shadow older ones.
- lookup(d) — miss, miss, hit — Memtable miss → R3 (newest run) miss → R2 hit, d = 4. Lookups may touch every level — the LSM read-amplification tradeoff.
- delete(c) — tombstone in memtable — A delete writes a tombstone marker, not an edit: LSM parts are immutable, so deletes must shadow older versions until compaction removes them.
- Flush → run R4 (tombstone) — The tombstone flushes into run R4. On disk now: R4 {c = ⊥}, R3 {c = 7}, R2, R1 — newest first.
- lookup(c) — tombstone wins — Memtable miss → R4 has the tombstone: stop. “Not found (deleted)” — the older c = 7 in R3 is shadowed and never read.
- Compact L0 + L1 — Compaction merges R1–R4 with L1 in one key-sorted pass: c = 3 and c = 7 are dropped (a newer tombstone shadows them), and the tombstone itself is dropped because no older run below can hold another c.
- Result — Lookup cost returns to 2 structures; disk holds one version per key. Compaction trades write amplification for read speed — the LSM bargain.
LSM write path, newest-first lookup, a delete via tombstone, and a compaction. Teaching model: RocksDB-flavored memtable + L0 runs + one merged L1 run; real engines compact by level with size ratios and keep tombstones until they cannot shadow anything older.
Teaching model: RocksDB-flavored memtable + L0 runs + one merged L1 run. Real level counts, compaction triggers, and tombstone GC timing are configuration-dependent.
[caption] Teaching model: RocksDB-flavored memtable + L0 runs + one merged L1 run. Real level counts, compaction triggers, and tombstone GC timing are configuration-dependent.
Watch one key family move through memtable, immutable runs, newest-first lookups, a tombstone delete, and a compaction that drops shadowed values.
| bit array | 24 bits, k=3 hashes |
| inserted | 3 elements → 9 bits set |
| false positives | possible (example: id 14) |
| false negatives | impossible — set bits are never cleared |
| FPR formula | (1 − e^(−kn/m))^k |
All steps
- insert(1) — set 3 bits — Three hash functions map 1 to bits {8, 18, 4}. No element is ever stored — only the bit pattern. Writes touch exactly k=3 bits regardless of how many elements are in the filter.
- insert(4) — set 3 bits — Three hash functions map 4 to bits {23, 3, 7}. No element is ever stored — only the bit pattern. Writes touch exactly k=3 bits regardless of how many elements are in the filter.
- insert(6) — set 3 bits — Three hash functions map 6 to bits {9, 1, 17}. No element is ever stored — only the bit pattern. Writes touch exactly k=3 bits regardless of how many elements are in the filter.
- lookup(4) — all bits set: possibly present — Hashes to {23, 3, 7} — every bit is 1, so the filter says "possibly present". The data file is opened and checked for real. This one IS present (inserted earlier).
- lookup(7) — a zero bit: definitely absent — Hashes to {14, 12, 10} — bit 14 is 0, and a set bit can never be cleared by an insert. The filter answers "definitely NOT present" with certainty: no disk read happens at all.
- lookup(14) — false positive: never inserted, all bits set — Every hashed bit happens to be 1 from OTHER elements — a false positive. The engine pays one unnecessary read. This is the bloom filter's only error mode: it never misses a present element, but it sometimes says "maybe" for absent ones.
- Result: the tradeoff in numbers — With n=3 elements, k=3 hashes, m=24 bits: false-positive rate ≈ 3.1%. Size the bit array up and the rate falls exponentially — which is why RocksDB picks 10 bits per key (~1%) by default.
A Bloom filter: k hash functions over a fixed bit array. Insertions set bits; lookups check bits. Absence is certain, presence is probabilistic — the visible false positive is the entire tradeoff. RocksDB keeps one per SST file so reads skip whole files that cannot contain the key.
Teaching model: 24 bits, k=3 display-friendly hashes. RocksDB uses ~10 bits per key with blocked bloom filters tuned per level.
[caption] Teaching model: 24 bits, k=3 display-friendly hashes. RocksDB uses ~10 bits per key with blocked bloom filters tuned per level.
Insert three keys into a 24-bit bloom filter, then look up a true hit, a certain absence, and a genuine false positive — the exact tradeoff RocksDB makes per SST file.
Level sizes grow by a fanout ratio per level; L0 holds the few overlapping files straight from flushes.
[caption] Illustrative shape for a leveled tree with a size ratio of 10 — L0 files overlap; levels below hold disjoint ranges. Actual level counts are configuration.
Level sizes grow by a fanout ratio per level; L0 holds the few overlapping files straight from flushes.