WTF is an LSM Tree? The Secret Sauce Behind Modern Databases

1
// Simplified MemTable structure (conceptual)
2
class MemTable {
3
private:
4
    std::map data;  // Often a skip list in practice
5
    std::atomic size;
6
    
7
public:
8
    void put(const Key& key, const Value& value) {
9
        data[key] = value;
10
        size += key.size() + value.size();
11
        
12
        if (size > threshold) {
13
            flushToDisk();  // Trigger SSTable creation
14
        }
15
    }
16
    
17
    optional get(const Key& key) {
18
        auto it = data.find(key);
19
        return it != data.end() ? it->second : nullopt;
20
    }
21
};

1
# Conceptual SSTable structure
2
class SSTable:
3
    def __init__(self, data):
4
        self.data_blocks = self._create_data_blocks(data)
5
        self.index = self._build_index()
6
        self.bloom_filter = self._build_bloom_filter()
7
        self.metadata = {
8
            'min_key': min(data.keys()),
9
            'max_key': max(data.keys()),
10
            'num_entries': len(data),
11
            'timestamp': time.time()
12
        }
13
    
14
    def get(self, key):
15
        # Quick rejection using bloom filter
16
        if not self.bloom_filter.might_contain(key):
17
            return None
18
            
19
        # Quick rejection using metadata
20
        if key < self.metadata['min_key'] or key > self.metadata['max_key']:
21
            return None
22
            
23
        # Binary search in index to find block
24
        block_offset = self._binary_search_index(key)
25
        
26
        # Read only the relevant block
27
        block = self._read_block(block_offset)
28
        return block.get(key)

1
# Simplified leveled compaction logic
2
class LeveledCompaction:
3
    def __init__(self):
4
        self.levels = [[] for _ in range(7)]  # L0 to L6
5
        self.level_max_bytes = [
6
            10 * MB,      # L0: 10MB
7
            100 * MB,     # L1: 100MB  
8
            1 * GB,       # L2: 1GB
9
            10 * GB,      # L3: 10GB
10
            100 * GB,     # L4: 100GB
11
            1 * TB,       # L5: 1TB
12
            10 * TB       # L6: 10TB
13
        ]
14
    
15
    def compact(self, level):
16
        if self.get_level_size(level) > self.level_max_bytes[level]:
17
            # Pick overlapping SSTables from level and level+1
18
            files_to_compact = self.pick_compaction_files(level)
19
            
20
            # Merge sort all entries, removing duplicates
21
            merged_data = self.merge_sort_files(files_to_compact)
22
            
23
            # Write new SSTables to level+1
24
            new_sstables = self.write_sstables(merged_data, level + 1)
25
            
26
            # Delete old files
27
            self.delete_files(files_to_compact)

1
# Simplified size-tiered compaction
2
class SizeTieredCompaction:
3
    def __init__(self):
4
        self.min_threshold = 4  # Minimum files of similar size
5
        self.max_threshold = 32 # Maximum files to compact at once
6
        
7
    def find_compaction_candidates(self, sstables):
8
        # Group SSTables by size (within 50% of each other)
9
        buckets = self.bucket_by_size(sstables)
10
        
11
        for bucket in buckets:
12
            if self.min_threshold <= len(bucket) <= self.max_threshold:
13
                return bucket[:self.max_threshold]
14
        
15
        return None
16
    
17
    def compact(self):
18
        candidates = self.find_compaction_candidates(self.all_sstables)
19
        if candidates:
20
            merged = self.merge_sstables(candidates)
21
            self.write_new_sstable(merged)
22
            self.delete_old_sstables(candidates)

1
# Time-window compaction for time-series data
2
class TimeWindowCompaction:
3
    def __init__(self, window_size=timedelta(hours=1)):
4
        self.window_size = window_size
5
        
6
    def compact(self):
7
        # Group SSTables by time window
8
        windows = defaultdict(list)
9
        for sstable in self.all_sstables:
10
            window = self.get_time_window(sstable.min_timestamp)
11
            windows[window].append(sstable)
12
        
13
        # Compact each window separately
14
        for window, sstables in windows.items():
15
            if self.should_compact_window(window, sstables):
16
                self.compact_window(sstables)

1
// Using RocksDB (C++)
2
#include 
3
 
4
rocksdb::DB* db;
5
rocksdb::Options options;
6
options.create_if_missing = true;
7
 
8
// Tune for write-heavy workload
9
options.write_buffer_size = 64 * 1024 * 1024;  // 64MB MemTable
10
options.max_write_buffer_number = 3;            // 3 MemTables
11
options.level0_file_num_compaction_trigger = 4; // Compact after 4 files
12
 
13
rocksdb::Status status = rocksdb::DB::Open(options, "/tmp/testdb", &db);
14
 
15
// Writes are fast
16
db->Put(rocksdb::WriteOptions(), "key1", "value1");
17
 
18
// Reads check multiple places
19
std::string value;
20
db->Get(rocksdb::ReadOptions(), "key1", &value);

1
// Cassandra's distributed LSM model
2
public class CassandraLSM {
3
    // Each node has its own LSM tree for its partition range
4
    private final Map, LSMTree> localTrees;
5
    
6
    public void write(PartitionKey key, Row row) {
7
        Token token = partitioner.getToken(key);
8
        Node coordinator = getCoordinator(token);
9
        
10
        if (coordinator.equals(localNode)) {
11
            // Write to local LSM tree
12
            LSMTree tree = localTrees.get(getRangeForToken(token));
13
            tree.write(key, row);
14
            
15
            // Replicate to other nodes
16
            for (Node replica : getReplicaNodes(token)) {
17
                replica.replicateWrite(key, row);
18
            }
19
        }
20
    }
21
}

1
// Your browser is running an LSM tree right now!
2
const request = indexedDB.open("MyDatabase", 1);
3
 
4
request.onsuccess = (event) => {
5
    const db = event.target.result;
6
    const transaction = db.transaction(["users"], "readwrite");
7
    const store = transaction.objectStore("users");
8
    
9
    // This write goes into LevelDB's MemTable
10
    store.put({ id: 1, name: "Alice", email: "alice@example.com" });
11
    
12
    // This read might check MemTable + multiple SSTables
13
    const getRequest = store.get(1);
14
};

1
# Benchmark comparison (conceptual)
2
class DatabaseBenchmark:
3
    def __init__(self):
4
        self.lsm_db = RocksDB()
5
        self.btree_db = PostgreSQL()
6
        
7
    def benchmark_writes(self, num_records=1_000_000):
8
        # LSM Tree: ~500,000 writes/second
9
        start = time.time()
10
        for i in range(num_records):
11
            self.lsm_db.put(f"key_{i}", f"value_{i}")
12
        lsm_time = time.time() - start
13
        
14
        # B-Tree: ~50,000 writes/second (with durability)
15
        start = time.time()
16
        for i in range(num_records):
17
            self.btree_db.insert("table", {"key": f"key_{i}", "value": f"value_{i}"})
18
        btree_time = time.time() - start
19
        
20
        print(f"LSM writes/sec: {num_records / lsm_time:,.0f}")
21
        print(f"B-tree writes/sec: {num_records / btree_time:,.0f}")
22
        
23
    def benchmark_reads(self, num_reads=100_000):
24
        # LSM Tree: ~200,000 reads/second (with bloom filters)
25
        # B-Tree: ~300,000 reads/second (direct index lookup)
26
        pass

1
# IoT sensor data, metrics, logs
2
sensor_data = {
3
    "timestamp": 1699564800,
4
    "sensor_id": "temp_sensor_42",
5
    "temperature": 23.5,
6
    "humidity": 45.2
7
}
8
# Append-only pattern = LSM heaven
9
tsdb.write(sensor_data)

1
// Message queue backed by LSM tree
2
public class HighThroughputQueue {
3
    private final RocksDB db;
4
    private final AtomicLong writeCounter = new AtomicLong();
5
    
6
    public void enqueue(Message message) {
7
        long id = writeCounter.incrementAndGet();
8
        byte[] key = ByteBuffer.allocate(8).putLong(id).array();
9
        db.put(key, serialize(message));
10
        // Can handle millions of messages per second
11
    }
12
}

1
-- This query pattern is painful for LSM trees
2
SELECT * FROM users WHERE user_id = ? -- Random key lookup
3
-- LSM tree might check 5-10 SSTables
4
-- B-tree goes directly to the leaf page

1
# LSM trees don't update in place
2
# This creates multiple versions
3
for _ in range(1000):
4
    db.put("hot_key", new_value)  # Creates 1000 versions!
5
    # All versions exist until compaction

1
class LSMTuning:
2
    def __init__(self):
3
        # Larger MemTable = fewer SSTables = better reads, worse memory usage
4
        self.memtable_size = 256 * MB
5
        
6
        # More levels = better read performance, worse write amplification
7
        self.num_levels = 7
8
        
9
        # Aggressive compaction = better reads, worse writes
10
        self.compaction_style = "leveled"  # or "tiered" for write-optimized
11
        
12
        # Bloom filter tuning
13
        self.bloom_bits_per_key = 10  # ~1% false positive rate

1
# Cassandra tuning for write-heavy workload
2
compaction:
3
  class: SizeTieredCompactionStrategy
4
  min_threshold: 4
5
  max_threshold: 32
6
 
7
memtable_flush_writers: 4
8
memtable_heap_space_in_mb: 2048
9
memtable_offheap_space_in_mb: 2048
10
 
11
# RocksDB tuning for read-heavy workload
12
rocksdb_options:
13
  level_compaction_dynamic_level_bytes: true
14
  max_bytes_for_level_base: 512MB
15
  target_file_size_base: 64MB
16
  block_cache_size: 8GB
17
  bloom_locality: 1

1
// TiDB uses LSM tree for recent data, B-tree for historical
2
class HybridStorage {
3
    LSMTree recent_data;    // Last 24 hours
4
    BTree historical_data;  // Older than 24 hours
5
    
6
    void write(Key k, Value v) {
7
        recent_data.put(k, v);
8
        // Background job moves to B-tree after 24 hours
9
    }
10
};

1
# Instead of checking bloom filters, use ML model
2
class LearnedLSM:
3
    def __init__(self):
4
        self.model = train_key_distribution_model()
5
        
6
    def read(self, key):
7
        # Model predicts which SSTable likely contains the key
8
        predicted_sstable = self.model.predict(key)
9
        
10
        # Check predicted SSTable first
11
        if result := predicted_sstable.get(key):
12
            return result
13
            
14
        # Fall back to regular search
15
        return self.regular_search(key)