Modern Databases: LSM Trees — Part 2

In the previous post, we have looked at the design of a hypothetical database.

The below design addresses some of the earlier limitations such as memory constraints for storing all (key, offset) pairs and no support for range queries and which will eventually lead us to nothing but LSM Trees.

Key Components of LSM Trees

1. Memtable:

• An in-memory data structure (typically a balanced tree or skip list) that stores recent writes.
• Provides fast writes and reads for the most recent data.

2. Write-Ahead Log (WAL):

• An append-only log on disk that records all writes before they are applied to the memtable.
• Ensures data durability and crash recovery.

3. Immutable Memtable:

• When the current memtable is full, it is marked as immutable and a new memtable is created.
• The immutable memtable is then flushed to disk as an SSTable.

4. SSTables (Sorted String Tables):

• Immutable, sorted files on disk created from immutable memtables.
• They store key-value pairs in a sorted order to facilitate efficient lookups.

5. Sparse Index:

• An in-memory index that maps a subset of keys to their respective offsets within SSTables.
• Reduces the memory footprint while enabling fast access to data blocks in SSTables.

Writing Data in LSM Trees

1. Write to Memtable and WAL

• Data is first written to the memtable and simultaneously logged to the WAL for durability.
• Writes to the WAL are typically synchronous, ensuring that data is safely recorded before acknowledging the write operation.

2. Memtable Full

• When the memtable reaches its capacity, it is marked as immutable.
• A new memtable is created to handle subsequent writes.

3. Flush to SSTable:

• The immutable memtable is flushed to disk as an SSTable.
• A sparse index is created during this process, mapping sampled keys to their offsets in the SSTable.

4. Update Metadata:

• System metadata is updated to include the new SSTable.
• The WAL may be truncated or reset as its contents are now safely stored in the SSTable.

Reading Data in LSM Trees

• The read operation first checks the memtable for the requested key. If found, the value is returned.
• If the key is not found in the current memtable, the search proceeds to the immutable memtables.
• If the key is not found in any in-memory memtables, the sparse index is consulted.
• The sparse index helps identify the SSTable and the approximate offset where the key might be located.
• Using the offset from the sparse index, the search jumps to the relevant block in the SSTable.
• A sequential search search from the offset within the block locates the exact key.

Sparse Index

Instead of storing all the keys of a segment in-memory, a sparse index stores only few keys and their offsets.

Consider a sparse index that samples every 100th key in an SSTable

Suppose we need to get value of key key0250. We know it falls between key0200 and key0300. We take the offset of key0200 and scan from it in the segment to find the key0250. So if we sample a key for evey 1kb of a segment, we only need to scan 1kb of data to find our key’s position in the segment.

Compaction and Merging

• Periodic processes that merge and compact SSTables to remove redundant data and maintain read performance.
• Helps in reducing the number of SSTables, thereby minimizing the number of files to search during read operations.

LSM Trees efficiently manage high write and read throughput by leveraging a combination of in-memory and on-disk data structures. The memtable, WAL, immutable memtables, and SSTables work together to provide fast write performance, while the sparse index accelerates read operations. This intricate design allows LSM Trees to offer both high performance and reliability in handling large-scale data.