2.15 LSM

1. What It Is

• Log-Structured Merge-Tree
• A data structure used for write-heavy scenarios

2. Why LSM Is Suitable for More Writes and Fewer Reads

• It uses the fact that sequential disk writes are faster than random disk writes

3. Data Structures

3.1. SSTables

• Sorted String Table
  • The data structure used to persist data to disk is SSTables
• Split into multiple files called segments
  • Each segment consists of key-value pairs sorted by key
  • 

3.2. B+Tree

MySQL Index Underlying Implementation

3.3. Sparse Index

Sparse Index.md

3.4. BloomFilter

BloomFilter.md

4. Operations

4.1. Write

• First write into an ordered data structure in memory. When it grows to a certain size, flush it to SSTables on disk
  • 
• To avoid data loss, it is also first written to a WAL file.
• The in-memory data structure is flushed to disk periodically or when it reaches a fixed size. These disk files are not modified

4.2. Read

• Use BloomFilter to filter out nonexistent data; for data that may exist, use the sparse index and binary search
  • 

4.3. Compaction

• As more files accumulate on disk, merge operations are performed periodically to remove redundant data and reduce the number of files.
• Multiple segments are merged into one segment
  • 

4.4. Delete

Mark the record as deleted; it is removed during compaction.

5. B-Tree vs LSM-Tree

• LSM is suitable for more writes, while B-Tree is suitable for more reads
• Sequential writes are usually much faster than random writes, so SSTable write performance is generally relatively good.
• Because SSTable compaction and cleanup threads exist, storage overhead is usually lower. But compaction and disk cleanup compete with normal requests for disk resources, reducing throughput.
• Since SSTables may contain multiple copies of the same key, tree indexes perform better in scenarios such as transactions that have higher consistency requirements.

6. Summary

The core idea of LSM Tree is to obtain higher write performance through memory writes and subsequent sequential disk writes, avoiding random writes. At the same time, it sacrifices read performance because the value of the same key may exist in multiple SSTables. Bloom Filter and compaction can be used to improve read performance.

7. References

• How do LSM Trees work?
• Understanding Time-Series Databases in Ten Minutes: Storage
• Understanding LSM-Tree in Depth - Tencent Cloud