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

Blocks, cache, and the CPU/disk dial

An SSTable is a sequence of fixed-size blocks (default 4 KB), each optionally compressed; an in-RAM block cache holds recently-read decompressed blocks, so a hot working set never touches disk and the compression choice is a pure CPU-vs-disk-bytes dial.

Previously

Reads, writes, deletes, and bounded levels are all sorted out. But every read so far has touched a whole SSTable. Real systems read BLOCKS, cache them, and squeeze them with compression.

Scene 10

Blocks, cache, and the CPU/disk dial

  1. Watch
  2. Try it
  3. Predict
  4. Capture
RAMmemtablej = 9BLOCK CACHE32 MBhit 0%DISKSSTable shelfL1L1/000005.sst[a … z]immutableBLOCKS · 4 KBindexa→0j→8Kp→16Kb0b1b2b3b4b5OPERATIONidle — no operation in flightAn SSTable is a strip of 4 KB blocks. Block index says first-key-of-each-block → byteoffset.
What to watch for

Watch one GET land on one block (not the whole file), and a second GET in the same block hit the cache. Hot reads stay in RAM.

Continue unlocks when the animation finishes.
Implementation

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

Block-aware read
block index → 1 block → cache
def read_value(sst, key):
    block_offset = sst.block_index.lookup(key)  # binary search in RAM
    if (sst.id, block_offset) in block_cache:
        block = block_cache.get(sst.id, block_offset)  # RAM hit
    else:
        raw = disk.pread(sst.id, block_offset, block_size)
        block = decompress(raw)                  # CPU work
        block_cache.put(sst.id, block_offset, block)
    return scan_block(block, key)
Compression: pure CPU↔disk
correctness unchanged; bytes and CPU move
# compression presets:
#   none → 1.0× disk, 1.0× CPU   (fastest reads, biggest disk)
#   lz4  → 0.55× disk, 1.4× CPU  (LSM default)
#   zstd → 0.40× disk, 2.6× CPU  (best ratio, slowest decode)
# the choice is a workload knob, not a correctness knob.
Sources

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

Scene 10 of 11, in the Sharp edges act — Tombstones, blocks, and the canvas.. SSTables are blocks; the block cache holds hot decompressed blocks; compression trades CPU for disk bytes with no effect on correctness.

Up next. All ten knobs are on the table. The capstone scene asks: given a workload, which ones do you turn — and which scene's insight justifies each turn?

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