Building Log-Structured Merge Trees from Scratch

Log-Structured Merge (LSM) trees are fascinating data structures that power some of the most performant databases in the world. If you've used RocksDB, Cassandra, or LevelDB, you've benefited from LSM tree optimization. In this post, we'll explore how they work and build one from scratch in Rust.

Why LSM Trees?

Traditional B-trees optimize for random access patterns, but they're write-heavy in practice due to frequent rebalancing. LSM trees flip this on its head: they optimize for sequential writes.

Here's how different data structures compare:

Architecture Overview

An LSM tree consists of multiple levels, each storing increasingly large sorted tables:

Key Components

1. MemTable

The MemTable is an in-memory sorted data structure (typically a skiplist or BTreeMap in Rust). When it reaches a size threshold, it's flushed to disk as an SSTable.

use std::collections::BTreeMap;

pub struct MemTable {
    data: BTreeMap<Vec<u8>, Vec<u8>>,
    size_bytes: usize,
}

impl MemTable {
    pub fn put(&mut self, key: Vec<u8>, value: Vec<u8>) {
        self.size_bytes += key.len() + value.len();
        self.data.insert(key, value);
    }

    pub fn get(&self, key: &[u8]) -> Option<&Vec<u8>> {
        self.data.get(key)
    }
}

2. SSTable (Sorted String Table)

SSTables are immutable files on disk containing key-value pairs in sorted order. They include:

• Data block: The actual key-value pairs
• Index block: Pointers to data blocks for faster lookups
• Footer: Metadata and index block location

3. Compaction

Compaction merges overlapping SSTables from one level to the next, removing duplicates and tombstones.

Lookup Process

When reading a key:

1. Check the MemTable first (highest priority, newest writes)
2. Search Level 0 SSTables (reverse order by timestamp)
3. Search Level 1 SSTables (using bloom filters for speed)
4. Continue through higher levels
5. Return "not found" if key doesn't exist

This is why LSM trees can tolerate slow storage. Most lookups find data in early levels.

Performance Characteristics

Real-World Considerations

When building an LSM tree implementation, remember:

• Bloom filters reduce unnecessary disk reads
• Compression saves disk space (trade-off: CPU vs I/O)
• Concurrent access requires careful synchronization
• Crash recovery needs a write-ahead log (WAL)

Conclusion

LSM trees aren't magic. They're carefully designed to match how modern hardware works. Sequential I/O is fast, and LSM trees exploit this ruthlessly. If you're building a write-heavy system, they're worth understanding deeply.

---

Ready to dive deeper? Start by implementing a simple MemTable, then add SSTable serialization, and finally tackle compaction logic. The learning curve is steep, but the rewards (understanding how real databases work) are immense.