LSM-Tree Compaction Strategies

The storage engine is the heart of every high-performance NoSQL database (Cassandra, RocksDB, ScyllaDB). LSM-trees maximize write throughput by transforming random writes into sequential appends.

1. The LSM-Tree Core Mechanics

1. Memtable: Writes are buffered in an in-memory balanced tree (SkipList).
2. Commit Log: Writes are simultaneously appended to a sequential file on disk for durability.
3. SSTable: Once the Memtable is full, it is flushed to disk as an immutable Sorted String Table.

2. Compaction: The Merging Process

Because LSM-trees generate many small files, they must be merged.

• Size-Tiered Compaction (STCS): Merges SSTables of similar sizes. Excellent write throughput but high read amplification.
• Leveled Compaction (LCS): Organizes files into levels. Files at L1 and L2 are disjoint (no overlapping keys). Excellent read performance, but high write amplification due to constant file movement.

3. Trade-offs

• Write-Heavy: Use Size-Tiered.
• Read-Heavy: Use Leveled.