How Do LSM-Trees Convert Random Writes to Sequential Appends?
Log-Structured Merge-trees, commonly known as LSM-trees, are data structures designed to optimize write-heavy workloads in classical computing databases. Instead of updating records in place on disk, which forces slow random I/O operations, an LSM-tree buffers incoming writes in memory and appends them sequentially to disk logs. Periodically, background compaction processes merge and sort these immutable files to maintain read efficiency and reclaim space.
Why Random Disk Writes Hurt Performance
Traditional database storage engines, such as those based on B-trees, store data in fixed-size pages on disk. When a record is inserted or updated, the database locates the corresponding page and modifies it in place. For workloads with high write throughput and keys distributed across a large keyspace, these updates translate into random disk seeks.
Even on modern Solid State Drives (SSDs), random writes are significantly slower than sequential writes. Random writes cause internal flash page fragmentation, increase write amplification, and accelerate wear on flash memory blocks. On spinning Hard Disk Drives (HDDs), the penalty is even more severe due to mechanical seek times and rotational latency.
The Core Mechanism of LSM-Trees
An LSM-tree avoids in-place updates by decoupling the arrival of a write from its final physical placement on disk. Every mutation—whether an insert, an update, or a delete—is treated as a new append-only record.
1. Write-Ahead Log (WAL) and Memtable
When a write request arrives, the database first appends the operation to an on-disk Write-Ahead Log (WAL). Because the WAL is strictly append-only, this disk write is sequential and fast, providing durability against crashes.
Simultaneously, the database inserts the key-value pair into an in-memory sorted structure called a Memtable, typically implemented as a skip list or a balanced binary search tree. Reads can query the Memtable directly in memory without touching the disk.
2. Flushing to Immutable SSTables
Once the Memtable reaches a configured size threshold, it becomes immutable, and a new active Memtable is allocated to accept incoming writes. The immutable Memtable is then flushed to disk as a Sorted String Table (SSTable).
Because the Memtable is already sorted by key, flushing it to disk requires only a single sequential write pass. Once written, an SSTable is never modified in place. Updates to existing keys are simply written as newer entries in subsequent SSTables, and deletions are recorded as special marker entries called tombstones.
Compaction and Space Reclamation
Over time, flushing Memtables creates many overlapping SSTables on disk. If left unchecked, read operations would need to search through numerous files, degrading read performance and wasting storage on overwritten or deleted keys.
LSM-trees solve this through background compaction. Compaction reads multiple SSTables sequentially, merges their sorted key ranges, discards obsolete values and tombstones, and writes out new, larger SSTables sequentially.
Most implementations organize SSTables into levels (\(L_0, L_1, \dots, L_k\)), where each level has a capacity \(C_i\) that grows exponentially by a size ratio \(T\):
\[C_i = T \cdot C_{i-1}\]
In this leveled architecture, \(L_0\) contains newly flushed SSTables with potentially overlapping key ranges, while deeper levels (\(L_1\) and beyond) partition keys into non-overlapping SSTables.
Trade-offs in Classical Computing
Converting random writes into sequential appends shifts the performance bottleneck from write latency to background I/O and read amplification.
- Write Amplification: A single logical write may be rewritten multiple times during compaction as it moves down the levels.
- Read Amplification: A point lookup may need to check the Memtable and multiple SSTables across levels. Databases mitigate this using per-SSTable Bloom filters in memory, which quickly rule out files that do not contain the target key.
- Space Amplification: Obsolete versions and tombstones occupy disk space until compaction removes them.
By trading a manageable amount of background compaction work and memory for Bloom filters, LSM-trees achieve orders-of-magnitude higher write throughput than in-place update structures, making them the foundation for modern write-heavy databases like RocksDB, LevelDB, and Apache Cassandra.