The Triad of LSM Engines: Write Path Deep Dive
Every write operation in an LSM-tree database coordinates between three distinct components to provide durability (once the WAL append is synced), high concurrency, and rapid searchability.
The Write Path Coordination
Under the Hood: Component Mechanics
1. The Write-Ahead Log (WAL)
Because the in-memory Memtable is volatile, a server power failure would lose uncommitted writes. Before inserting into the Memtable, the engine appends the operation to the WAL on disk. Because the WAL is append-only, disk throughput reaches hundreds of megabytes per second. Upon recovery, the engine replays the WAL to reconstruct the Memtable.
2. The Memtable (Concurrent SkipList)
The Memtable is an in-memory sorted collection. Balanced trees such as red-black trees need rebalancing that is hard to make lock-free, whereas concurrent skiplists can be updated with atomic compare-and-swap (CAS) on forward pointers. Multiple application threads can write concurrently without mutex contention while maintaining sorted key order.
3. The Sorted String Table (SSTable)
When the Memtable exceeds its threshold (typically 64MB or 128MB), it transitions to an immutable state and a fresh Memtable is allocated. A background thread iterates over the sorted Memtable sequentially, writing it to disk as an SSTable. An SSTable consists of data blocks (typically about 4KB before compression), an index block mapping keys to block offsets, and a Bloom filter.
Worked example: one write, one flush, one crash
put("k17", v)is appended to000123.logand inserted into the active 64 MB memtable (a skiplist).- After roughly 64 MB of writes (about 60,000 records of 1 KB), the memtable becomes immutable and a new memtable and a new log file start.
- A background thread iterates the immutable memtable in key order and writes
000124.sst: data blocks of about 4 KB (before compression), an index block with one entry per data block, a filter block (Bloom filter), and a fixed-size footer pointing to the index. - After the SST is synced and recorded in the MANIFEST,
000123.logcan be deleted. - If the process crashes before step 4, recovery reads the MANIFEST to learn the live SSTs and replays any log files not yet covered, rebuilding the memtable.
Durability knobs
| Mode | What is lost on power failure | Throughput | Example |
|---|---|---|---|
| Sync every write | Nothing acknowledged | Lowest, bounded by flush latency | RocksDB sync=true |
| Group or batch sync | Nothing acknowledged; writes wait for the next group flush | High | Cassandra batch or group commitlog modes |
| Periodic sync | Up to the sync interval | Highest | Cassandra default periodic, 10 s |
| No WAL | Entire memtable | Highest | Bulk loads that can be redone |
Why a skiplist
A skiplist keeps keys sorted with expected O(log n) inserts and is easy to make safe for concurrent readers with a single writer (LevelDB) or concurrent writers using compare-and-swap on forward pointers (RocksDB's concurrent memtable writes). Sorted order is what makes the flush a single sequential pass.
Failure modes
- Write stalls: if flushes cannot keep up, immutable memtables pile up and the engine blocks writers.
- Slow recovery: many large WAL files mean long replay after a crash.
- Torn WAL tail: per-record checksums let recovery stop at the last complete record.