DISTRIBUTED SYSTEMS · STORAGE ENGINE INTERNALS

LSM-Tree, Write-Ahead Log & Compaction Engine

Understand how write-heavy storage engines transform random disk mutations into sequential NVMe appends via WAL and SkipList MemTables, while taming read and write amplification with Bloom filters and leveled K-way compaction.

Sequential WAL Append In-Memory SkipList Bloom Filter Gate K-Way Leveled Merge
Act I · Scope, Workload & Back-of-the-Envelope Math

Durability Guarantees & NVMe Storage Envelope

Step 1 of 5
Functional & Durability Goals
Core Engine
  • Sequential Write Path: Convert random key mutations into fast sequential WAL appends plus in-memory ordered SkipList inserts.
  • Crash-Safe WAL Recovery: Verify CRC32 checksums on reboot and replay uncommitted LSN records to reconstruct the active MemTable with 0% loss.
  • Tombstone Deletes & Range Scans: Record deletes as immutable 0x02 TOMBSTONE markers and support ordered prefix/range iterators across sorted SSTable runs.
  • Zero-Downtime Compaction: Merge overlapping L0/L1 files in background threads and switch active reader views atomically via a versioned MANIFEST.
Non-Functional Constraints
Hardware Limits
  • NVMe Sequential vs. Random IOPS: Batch sequential writes via group commit to saturate NVMe bandwidth while avoiding random 4KB in-place page rewrites.
  • 10x Write Amplification Ceiling: Bound background compaction rewrites so SSD wear-leveling and foreground throughput stay sustainable over years.
  • Bounded L0 File Count: Trigger compaction at 4 L0 files and apply backpressure (write stall) at 8 L0 files so point reads never scan dozens of overlapping tables.
  • Predictable P99 Tail Latency: Keep P99 writes < 1.5 ms and eliminate unnecessary disk seeks on absent keys using in-RAM Bloom filters (≤1.0% FPR).
Peak Write Throughput
150K WPS

~150 MB/s sequential WAL append at 1 KB/record using group-commit batching.

Active MemTable Cap
64 MB

Freezes & flushes to L0 SSTable ~every 0.4s under sustained 150 MB/s peak load.

Bloom Filter Budget
10 bits / key

~1.0% False Positive Rate (7 hashes) → only ~1.2 MB RAM per 1M keys.

Leveled Tier Ratio
10x Ratio

L1: 640 MB → L2: 6.4 GB → L3: 64 GB → L4: 640 GB deterministic capacity.

Act II · On-Disk Binary Formats & Storage Contracts

WAL Record Framing, SSTable Blocks & Atomic MANIFEST

Step 2 of 5
WAL Record Frame & MemTable Entry
Group-Commit Batching: Concurrent writer goroutines append their frames to a shared buffer and ride a single fdatasync() NVMe barrier, multiplying write throughput by 8–10x.
SSTable Block Layout & Atomic MANIFEST
Act III · Interactive LSM-Tree Engine & Chaos Switchboard

Write Path, Bloom Gate, Leveled Compaction & Crash Recovery

ENGINE NOMINAL
Step 1 / 6
LSM-Tree Engine Lab · Write Path & MemTable Flush
WAL APPEND
terminal Client Engine API PUT / GET / DEL PUT k42 (LSN #143) edit_document Append-Only WAL NVMe Sequential Log [141] [142] [143] CRC32 OK · GROUP SYNC memory Active MemTable (RAM) SkipList · 42 / 64 MB IMMUTABLE FREEZE SLOT STANDBY · READY filter_alt Block Cache & Bloom Gate 10 bits/key · ~1.0% FPR 1 0 1 1 0 1 0 1 BLOOM ARMED · CACHE WARM hard_drive Leveled SSTables (NVMe Disk) Immutable Sorted Runs · 10x Size Ratio MANIFEST v14 L0 Overlap SST-01 SST-02 SST-03 SST-04 2 / 4 L0 RUNS L1 Disjoint [A - G] · 210 MB [H - N] · 215 MB [O - Z] · 215 MB L2 Archive 6.4 GB Partitioned Runs · Bottom-Level Tombstone GC
WAL APPEND

Loading engine simulator...

Invariant active
Live Engine Event Console
Live Telemetry HUD
Real-Time
P99 Write Latency
0.9 ms
Group commit active
Read Amplification
1.2x
Bloom filter active
Write Amplification
10.4x
Leveled 10x tiering
MemTable / L0 Runs
42 MB / 2 L0
Cap 64 MB · Stall @ 8
Chaos Switchboard
0 Active
Act IV · Zero-Dependency Go Blueprints & Production Stack Mapping

Idiomatic Go Engine Primitives & Real-World Mapping

Auto-Synced to Simulator
Production Stack Mapping Strip 6 Core Primitives
Agnostic Primitive Production Storage Systems Implementation Detail
Append-Only WAL RocksDB / Pebble / Cassandra CommitLog Sequential CRC32-framed log with group-commit fdatasync
Ordered MemTable RocksDB InlineSkipList / Pebble Arena Lock-free concurrent SkipList backed by fixed 64 MB arena RAM
Immutable SSTables LevelDB / Bigtable / RocksDB .sst 4KB prefix-compressed blocks with sparse index & magic footer
Bloom Filters RocksDB Ribbon / Cassandra BloomFilter 10 bits/key (~1% FPR) skipping absent SSTables in O(1) RAM
Leveled / Tiered Compaction CockroachDB Pebble / ScyllaDB ICS / TiKV Background K-way merge bounding read, write, and space amp
Atomic MANIFEST RocksDB MANIFEST + CURRENT / Pebble Append-only version edit log atomically swapping live SSTable sets
Act V · Architectural Tradeoffs & Production SLOs

RUM Conjecture Tradeoffs & Storage SLOs

Step 5 of 5
Tradeoff 01 Engine Architecture

LSM-Tree vs. B+Tree

LSM-Tree (Write-Optimized)

Sequential WAL + SSTable flushes deliver 5–10x higher write throughput and high block compression with zero page fragmentation.

B+Tree (Read-Optimized)

Single authoritative page per key gives predictable O(log B) reads, but random in-place 4–16KB page rewrites cause write stalls and fragmentation.

Verdict Pick LSM-Tree for write-heavy telemetry, messaging, and distributed KV (RocksDB/TiKV); pick B+Tree for point-read-heavy OLTP.
Tradeoff 02 Compaction Strategy

Size-Tiered vs. Leveled Compaction

Leveled (RocksDB Default)

Caps space amplification at ~1.11x and guarantees disjoint key ranges per level for predictable reads, at ~10–15x write amplification.

Size-Tiered (STCS)

Lower write amplification (~4–6x) for pure ingest workloads, but requires up to 2x free disk space during major compactions and increases read amp.

Verdict Use Leveled Compaction for general-purpose SSD workloads where disk cost and P99 read predictability matter most.
Tradeoff 03 Delete Semantics

Tombstone Accumulation & Space Amplification

Bottom-Level GC

Keeping 0x02 TOMBSTONE markers until the bottommost level ensures deleted keys never resurrect from older cold SSTables.

Range-Delete Overhead

Heavy delete/TTL churn piles up tombstones that slow range scans until compaction reaches Lmax; requires range-tombstone optimizations.

Verdict Deletes in LSM engines write data; monitor tombstone ratio and schedule periodic compaction for high-churn queues.
Tradeoff 04 Durability vs. IOPS

Group Commit vs. Strict Per-Write fsync

Group Commit

Batches concurrent writers arriving within ~200µs into 1 NVMe fdatasync barrier—delivering 10x higher WPS while remaining 100% crash-durable.

Strict Per-Write fsync

Serializes every single PUT behind its own NVMe flush barrier, capping throughput and spiking P99 write latency to 7–10 ms.

Verdict Always enable Group Commit: you get strict post-ACK durability with sequential batch throughput.
Production Observability SLOs
Storage Engine Targets
P99 Write Latency < 1.5 ms Group-commit NVMe append
Bloom Filter FPR ≤ 1.0% 10 bits / key bitset
L0 Write Stall < 0.05% Proactive L0->L1 pacing
Crash Recovery Loss 0% CRC32 + WAL LSN replay