SSTable & LSM Tree

Metadata

1. Overview

What problem does it solve?

Traditional relational databases (like PostgreSQL) store data in a B-Tree structure on disk. When you insert or update a row, the database has to jump around the hard drive to find the exact spot in the B-Tree, rewrite that block, and potentially split the tree nodes. This is called Random I/O, and it is slow.

If you have a system ingesting 100,000 writes per second (e.g., IoT sensors, clickstream analytics), a B-Tree will physically bottleneck your hard drive.

Log-Structured Merge-Trees (LSM Trees) and SSTables (Sorted String Tables) solve this by turning all Random I/O into Sequential I/O. They NEVER modify existing data on disk. They only append new data in a straight line, making writes blindingly fast.

What breaks without it?

• Write Bottlenecks: Heavy write workloads (like time-series data or logging) will bring a B-Tree database to a crawl as it waits for disk head seeks.

2. Motivation

Google invented the SSTable format for their Bigtable paper (2006) to handle the massive influx of web crawler data. They realized that writing data sequentially to disk is orders of magnitude faster than updating data in place.

This concept was formalized as the Log-Structured Merge-Tree (LSM). It became the foundational storage engine for almost every major NoSQL database designed for high-write workloads, including Cassandra, HBase, LevelDB, and RocksDB.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The LSM Tree Architecture

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef ram fill:#cce5ff,stroke:#007bff,stroke-width:2px;
    classDef disk fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef process fill:#f8d7da,stroke:#dc3545,stroke-width:2px;

    C((Client)):::client --> |"1. WRITE (Bob: 42)"| WAL[(WAL<br/>Disk)]:::disk
    C --> |"1. WRITE (Bob: 42)"| Mem[MemTable<br/>RAM - Sorted Tree]:::ram
    
    Mem -.-> |"2. Reaches 4MB.<br/>Flush to Disk!"| SST1[(SSTable 1<br/>Disk - Immutable)]:::disk
    
    SST1 --> Comp[Compaction<br/>Background Process]:::process
    SST2[(SSTable 2)]:::disk --> Comp
    
    Comp --> |"Merge & Sort"| SST3[(Merged SSTable 3)]:::disk

6. Internal Working

1. The Write Path (Blazing Fast)

1. Write the data to an append-only Write-Ahead Log (WAL) for crash recovery.
2. Insert the data into an in-memory balanced tree (like a Red-Black Tree or Skip List) called the MemTable. Because it's in RAM, it's instantly sorted.
3. Return "Success" to the user.

2. The Flush (SSTable Creation)

When the MemTable gets too big (e.g., 4MB), the database freezes it and creates a new MemTable. A background thread takes the frozen MemTable and dumps it sequentially to disk as an SSTable (Sorted String Table).

• Crucial: SSTables are Immutable. Once written, they are NEVER modified.

3. The Read Path (Slower)

To find "Bob", the database must search:

1. The MemTable (RAM).
2. If not found, search the newest SSTable on disk.
3. If not found, search the next oldest SSTable, and so on.

Because searching multiple disk files is slow, LSM trees use Bloom Filters (Block 008) for every SSTable to instantly know if "Bob" is definitively not in a file, skipping it entirely.

4. Compaction (The Cleanup)

If we just keep flushing MemTables, we will end up with 10,000 SSTables on disk. Reads would take forever. Furthermore, if we updated Bob's score 5 times, there are 5 different records of Bob on disk! Compaction is a background process that takes two or more SSTables, merges them together (like the Merge sort algorithm), keeps only the newest value for each key, and writes a single, clean new SSTable, deleting the old ones.

7. Implementation

Why Python? Python is excellent for mocking out the memory structures (dictionaries/lists) and demonstrating the merge-sort logic required for Compaction.

"""
039 - SSTable & LSM Tree
A simulation of a Log-Structured Merge Tree.
Demonstrates MemTable flushing, immutable SSTables, and background Compaction.
"""
import time

# ── 1. The SSTable (Disk) ──

class SSTable:
    """An immutable, sorted dictionary mocking a file on disk."""
    def __init__(self, data_dict, id):
        self.id = id
        # Sort the data by key before "writing to disk"
        self.data = dict(sorted(data_dict.items()))
        self.timestamp = time.time()
        print(f"  [Disk] 💾 Flushed SSTable-{self.id} with {len(self.data)} keys: {self.data}")

    def read(self, key):
        return self.data.get(key, None)

# ── 2. The LSM Tree (Database Engine) ──

class LSMTree:
    def __init__(self, memtable_threshold=3):
        self.memtable = {}
        self.sstables = [] # List of SSTable objects (Index 0 is newest)
        self.memtable_threshold = memtable_threshold
        self.next_sstable_id = 1

    def write(self, key, value):
        """The Write Path: Inserts into RAM."""
        print(f"[Write] {key} -> {value}")
        self.memtable[key] = value
        
        # If RAM gets too full, flush to disk!
        if len(self.memtable) >= self.memtable_threshold:
            self._flush_memtable()

    def _flush_memtable(self):
        # Create an Immutable SSTable and prepend it (so it's the newest)
        new_sstable = SSTable(self.memtable, self.next_sstable_id)
        self.sstables.insert(0, new_sstable)
        self.next_sstable_id += 1
        
        # Clear the RAM
        self.memtable = {}
        
        # Trigger background compaction if we have too many files on disk
        if len(self.sstables) >= 2:
            self._compact()

    def read(self, key):
        """The Read Path: RAM -> Newest Disk -> Oldest Disk"""
        print(f"[Read]  Searching for '{key}'...")
        
        # 1. Check RAM first (Most recent updates)
        if key in self.memtable:
            print("        Found in MemTable (RAM)!")
            return self.memtable[key]

        # 2. Check Disk files (Newest to Oldest)
        for sstable in self.sstables:
            result = sstable.read(key)
            if result is not None:
                print(f"        Found in SSTable-{sstable.id} (Disk)!")
                return result

        print("        Not Found.")
        return None

    def _compact(self):
        """
        Background Compaction: Merges all SSTables into one.
        Resolves conflicts by keeping the value from the NEWER SSTable.
        """
        print("\n  [Background] 🔄 Compaction Triggered! Merging SSTables...")
        merged_data = {}
        
        # Iterate from Oldest to Newest. 
        # Newer values will naturally overwrite older values in the dict.
        for sstable in reversed(self.sstables):
            for k, v in sstable.data.items():
                merged_data[k] = v
                
        # Write the brand new merged file
        merged_sstable = SSTable(merged_data, self.next_sstable_id)
        self.next_sstable_id += 1
        
        # Delete the old fragmented files, keep the new one
        self.sstables = [merged_sstable]
        print("  [Background] ✅ Compaction Complete.\n")

# ── 3. Test Harness ──

if __name__ == "__main__":
    db = LSMTree(memtable_threshold=3)

    # 1. First batch of writes
    db.write("alice", 10)
    db.write("bob", 20)
    db.write("charlie", 30) # Triggers Flush (SSTable-1)

    # 2. Second batch of writes (Including an UPDATE to bob)
    db.write("dave", 40)
    db.write("bob", 99)     # Bob is updated!
    db.write("eve", 50)     # Triggers Flush (SSTable-2), then Compaction (SSTable-3)

    # 3. Read requests
    print("\n--- Testing Reads ---")
    
    # Charlie was in the first batch
    result = db.read("charlie")
    print(f"Result: {result}\n")
    
    # Bob was updated. The Compaction should have kept '99' and discarded '20'
    result = db.read("bob")
    print(f"Result: {result}\n")
    
    # Frank doesn't exist
    result = db.read("frank")
    print(f"Result: {result}")

Sample Output

[Write] alice -> 10
[Write] bob -> 20
[Write] charlie -> 30
  [Disk] 💾 Flushed SSTable-1 with 3 keys: {'alice': 10, 'bob': 20, 'charlie': 30}
[Write] dave -> 40
[Write] bob -> 99
[Write] eve -> 50
  [Disk] 💾 Flushed SSTable-2 with 3 keys: {'bob': 99, 'dave': 40, 'eve': 50}

  [Background] 🔄 Compaction Triggered! Merging SSTables...
  [Disk] 💾 Flushed SSTable-3 with 5 keys: {'alice': 10, 'bob': 99, 'charlie': 30, 'dave': 40, 'eve': 50}
  [Background] ✅ Compaction Complete.


--- Testing Reads ---
[Read]  Searching for 'charlie'...
        Found in SSTable-3 (Disk)!
Result: 30

[Read]  Searching for 'bob'...
        Found in SSTable-3 (Disk)!
Result: 99

[Read]  Searching for 'frank'...
        Not Found.
Result: None

Notice how Compaction successfully deduplicated Bob, keeping the newest value (99) and throwing away the old value (20).

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Why do databases like Cassandra have such high write throughput compared to Postgres? Hint: Cassandra uses an LSM tree, meaning all writes go directly to an in-memory MemTable and an append-only WAL. It completely avoids Random Disk I/O.

2. What is an SSTable? Hint: A Sorted String Table. It is an immutable file on disk containing a sorted sequence of Key-Value pairs.

3. What is the purpose of Compaction? Hint: To merge multiple fragmented SSTables into a single file, discarding deleted data (tombstones) and older, overwritten versions of data to save space and speed up reads.

4. How are deletes handled in an LSM Tree? Hint: Because SSTables are immutable, you cannot delete in-place. You insert a "Tombstone" record. Reads see the Tombstone and pretend the data is gone. Compaction eventually cleans it up physically.

13. Used By (Downstream Blocks)

• 040 Vector Clocks & CRDTs — AP databases like Cassandra and Dynamo (which use LSM trees) rely heavily on CRDTs and Vector Clocks to resolve conflicting writes during Compaction.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement Tombstones (Deletes)

Add a delete(key) method to the LSMTree. It should insert a special marker (e.g., __DELETED__) into the MemTable. Update the read() method to return None if it encounters this marker. Finally, update _compact() to completely drop the key from the merged SSTable if the value is the deleted marker.

Exercise 2: Add a WAL

Integrate the Python code with the concept from Block 038. Before updating the memtable, the write function should append the raw command to a wal.log file. When _flush_memtable is called, it should truncate/delete the wal.log file.

Website Metadata