Log-Structured Merge-Tree (LSM Tree)

The memtable is a mutable, in-memory data structure (typically a balanced tree like a Red-Black Tree or a skip list) that serves as the primary write buffer. All incoming writes (inserts, updates, deletes) are first appended to a write-ahead log (WAL) for durability and then applied to the memtable. When the memtable reaches a configured size threshold, it becomes immutable and is flushed to disk as a Sorted String Table (SSTable). This design allows for extremely high write throughput, as writes are sequential appends to the WAL and in-memory updates.

An SSTable is an immutable, sorted file on disk that stores key-value pairs. It is the persistent representation of a flushed memtable. Key characteristics include:

• Sorted by Key: Enables efficient range queries and merging.
• Immutable: Once written, it is never modified in place.
• Indexed: Contains a sparse in-memory index (e.g., a Bloom filter and block offsets) for fast point lookups.
• Compressed: Often compressed to reduce storage footprint. SSTables are organized into levels (L0, L1, L2...), with each level having a size limit. Newer data resides in smaller, higher levels (like L0), and older data is gradually merged into larger, lower levels.

Compaction is the background process that merges multiple SSTables from one level into a new, larger SSTable at the next level. It is the core mechanism for:

• Space Reclamation: Removing obsolete or deleted values (tombstones).
• Read Optimization: Reducing the number of files that must be checked for a read.
• Write Amplification Control: Managing the cost of rewriting data. Common compaction strategies include Leveled Compaction (strict size tiers, better read performance) and Size-Tiered Compaction (merging similarly sized files, better write performance). The choice involves a trade-off between write amplification and read amplification.

The Write-Ahead Log (WAL) is a sequential, append-only log file on persistent storage. Every write operation is durably written to the WAL before being applied to the memtable. This provides crash consistency: if the system fails, the memtable can be reconstructed by replaying the WAL. Once a memtable is successfully flushed to an SSTable, its corresponding WAL segments can be safely deleted. The WAL is critical for the durability guarantee of the LSM Tree, ensuring no acknowledged writes are lost.

A Bloom filter is a probabilistic, memory-efficient data structure used to accelerate point reads. Each SSTable has an associated Bloom filter in memory. When checking for a key, the Bloom filter can definitively say "key is definitely not present" or "key is probably present" with a very low, configurable false-positive rate. This prevents expensive disk I/O for the vast majority of queries seeking non-existent keys. For example, a 1% false-positive rate means only 1 in 100 negative lookups will incur an unnecessary disk seek, dramatically improving read performance for workloads with many misses.

The manifest file is a persistent metadata log that tracks the schema of the LSM Tree. It records:

• The sequence of SSTable files.
• The level to which each SSTable belongs.
• Key range boundaries for each SSTable.
• Compaction history and status. This file is essential for recovery and consistency. When a database starts, it reads the manifest to reconstruct its in-memory view of the SSTable hierarchy. The manifest is updated atomically during major events like flushes and compactions to maintain a consistent view of the storage state.

A durability guarantee protocol where all data modifications are first written to a persistent, append-only log file before being applied to the main database structure. This ensures crash recovery by allowing the system to replay the log to reconstruct the latest committed state.

• Core Mechanism: Acts as a single source of truth for recent writes.
• Relation to LSM Trees: Often used in conjunction with an LSM Tree's memtable; writes are logged to the WAL before being inserted into the in-memory memtable, guaranteeing no data loss if the process crashes before a memtable is flushed to disk.

A predetermined algorithm that determines which items to remove from a cache when it reaches its capacity limit. These policies are critical for optimizing the performance of in-memory components like an LSM Tree's memtable or a block cache.

• Common Algorithms: Least Recently Used (LRU), Least Frequently Used (LFU), and Time-To-Live (TTL).
• System Impact: The choice of policy directly affects cache hit rates, latency, and overall system throughput. In LSM Trees, the memtable acts as a write cache with its own implicit eviction policy: flush to disk when full.

A storage optimization technique where data modifications are written only to a fast cache (e.g., memory) initially. Updates to the slower, persistent backing store are deferred until the cached data is evicted or explicitly flushed.

• Performance vs. Durability Trade-off: Maximizes write throughput but introduces a window where data is volatile. A crash before the flush results in data loss unless paired with a WAL.
• LSM Tree Parallel: The LSM Tree's memtable is a canonical write-back cache for disk. All writes first go to the memtable; the merge and flush to Sorted String Tables (SSTables) is the deferred write-back operation.

A probabilistic, memory-efficient data structure used to test whether an element is a member of a set. It returns either 'possibly in set' or 'definitely not in set,' with a tunable false-positive rate.

• Key Use Case in LSM Trees: Placed in front of on-disk SSTable files. Before performing a potentially expensive disk read to check for a key, the system queries the Bloom filter. If it returns 'definitely not present,' the read is avoided entirely, dramatically improving read performance for non-existent keys.
• Space Efficiency: A Bloom filter's small size (often a few MB per GB of data) makes this optimization highly cost-effective.

A database isolation technique that allows multiple transactions to read and write concurrently by maintaining multiple timestamped versions of data items. Readers see a consistent snapshot from a specific point in time, preventing conflicts with concurrent writers.

• Consistency Model: Enables snapshot isolation and repeatable reads.
• Relation to LSM Updates: LSM Trees naturally support MVCC-like semantics. When a key is updated, the new value is written as a new entry. Older values in immutable SSTables remain until garbage-collected during a merge. This allows for historical queries and consistent reads during compaction.

In the context of LSM Trees, garbage collection is the process of merging and rewriting SSTable files to reclaim space occupied by obsolete or deleted data (tombstones). This is performed by the compaction process.

• Mechanism: As SSTables are merged, only the most recent version of a key is kept in the new output file. Deleted keys marked with tombstones are discarded once they are known to have propagated through all relevant levels.
• Critical Function: Prevents unbounded disk space growth and read amplification by consolidating data and removing redundancy. Different compaction strategies (e.g., Leveled, Tiered) trade off write and read amplification.