Log-Structured Merge Tree (LSM) Simulator

Deep Dive

Log-Structured Merge Trees (LSM) trade read amplification and background compaction I/O to achieve unrivaled write throughput by turning random mutations into sequential disk writes.

🔬LSM Tree Write & Compaction Simulator

Live State Simulator

See how Log-Structured Merge Trees turn random application writes into sequential disk I/O, using in-memory MemTables, Write-Ahead Logs, and multi-level SSTable Compaction with Bloom filters.

Engine initialized. MemTable has 2 keys. WAL is synchronized to disk.

🧠 In-Memory Tier (RAM)Volatile / Fast

MemTable (SkipList): 2/4 keys

usr:101Alice

usr:103Charlie

💾 Persistent Tier (Disk / SSD)Immutable SSTables

Write-Ahead Log (WAL) — Sequential append

2 uncommitted log records

SSTable Files (Sorted String Tables)

sst_01 (Level 0)Bloom Filter: OK

Keys: [usr:090, usr:095]

sst_02 (Level 1)Bloom Filter: OK

Keys: [usr:010, usr:050, usr:080]

---

Anatomy of an LSM Tree

An LSM-based storage engine consists of three core layers:

1. MemTable (RAM): A concurrent in-memory sorted index (typically a SkipList or Red-Black Tree). All incoming PUT and DELETE (tombstone) requests enter the MemTable immediately.
2. Write-Ahead Log (WAL): An append-only sequential file on disk. Before updating the MemTable, writes are appended to the WAL to provide durability across system crashes.
3. Sorted String Tables (SSTables on Disk): Immutable files divided into sorted key-value blocks. When a MemTable reaches capacity (e.g. 64MB), it is frozen and flushed as a Level 0 SSTable.
4. Bloom Filters: A compact probabilistic bit array prepended to each SSTable. It guarantees zero false negatives: if the Bloom filter reports a key is absent, the engine safely skips reading that SSTable from disk!