The MemTable and WAL Lifecycle
When data arrives, it is first written to an append-only Write-Ahead Log (WAL) for durability and then inserted into an in-memory structure known as a MemTable. The MemTable, typically implemented as a skip list or balanced tree, keeps entries sorted by key. Once the MemTable reaches a size threshold, it becomes immutable and is flushed to disk as a Sorted String Table (SSTable). This process ensures that disk writes are always sequential, maximizing the utilization of mechanical hard drives and keeping SSD write wear predictable.
Compaction Strategies and Merge Dynamics
SSTables are immutable, which creates a challenge: how to handle updates and deletions? The answer lies in background compaction. Compaction processes periodically merge multiple SSTables, discarding outdated versions, resolving tombstones (entries marked for deletion), and maintaining key order. These compaction strategies vary significantly by system design:
Size-Tiered Compaction: Groups SSTables of similar sizes and merges them into larger ones, prioritizing write throughput but increasing read latency due to the number of files checked.
Leveled Compaction: Organizes SSTables into fixed-size levels where each level has a stricter range constraint, significantly improving read performance at the cost of higher write amplification.
Trade-offs and Operational Reality
The efficiency of LSM-trees relies on balancing read amplification, write amplification, and space amplification. Write amplification occurs when data is rewritten multiple times during compaction. Read amplification happens because a query might need to scan several SSTables to find the latest key version. Bloom filters are frequently employed to mitigate this, allowing the system to skip SSTables that statistically cannot contain the target key. Understanding these mechanics is essential for engineers tuning database parameters, as the choice between throughput-optimized or read-optimized compaction can dictate the scalability of a production storage system.
