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

Why Bitcask cannot give you ranges

If you want both fast writes and ordered reads on more keys than fit in RAM, neither a hash-in-RAM (Bitcask) nor a B-tree on disk wins — and that gap is the entire reason an LSM (Log-Structured Merge-tree, the engine inside LevelDB / RocksDB / Cassandra) exists.

Scene 01

Why Bitcask cannot give you ranges

  1. Watch
  2. Try it
  3. Predict
  4. Capture
WORKLOADput random keys — 50/tick · randomness 100%ticks: 0Bitcask0 keysRAM · keydirRAM budgetB-tree on disk0/srootseekseeks/sec0 / 200?next scene?fast point reads, hot keys in cacheevery key is a row in RAMordered reads, range scansone seek per random-key insertgood at: ?next scenes fill this inBoth work at small scale. The brief is to keep both alive when the workload grows.
What to watch for

One workload of random-key writes drives three panels. Watch the first two panels die in turn — first on cardinality, then on write rate. The third panel is the empty slot we fill next.

Continue unlocks when the animation finishes.
Implementation

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

The brief — pseudocode
what the next scenes will satisfy
# we want a single store that satisfies all of these:
store.put(key, value)               # at memory speed
store.get(key)                      # bounded latency
store.scan(from_key, to_key)        # ordered range
 
# subject to:
#   key_count > RAM_BUDGET / row_overhead
#   write_rate > disk_random_seeks_per_sec
 
# Bitcask fails the first constraint (RAM ceiling).
# B-tree fails the second (seek per random write).
Sources

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

Scene 01 of 11, in the The brief act — Why Bitcask cannot give you ranges.. Bitcask died on cardinality, the B-tree died on write rate. The brief LSM is built to satisfy: ordered reads, more keys than fit in RAM, no seek per write.

Up next. Bitcask died on cardinality, the B-tree died on write rate. The fix LSM (Log-Structured Merge-tree) takes is hiding in plain sight: write to RAM at memory speed AND append to a disk log for crash safety. Two structures, one truth — and we'll name them next scene.

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