LSM Trees and SSTables: How They Work and Why They Dominate Write-Heavy Workloads

You've got a write-heavy workload — time-series metrics, user events, chat messages — and your B-tree starts choking. Writes slow to a crawl, your disk I/O spikes, and the pager goes off at 2 AM. The problem? B-trees do random writes, and spinning disks (even SSDs) hate random writes. LSM Trees solve this by turning every write into a sequential append. That's the entire trick. And it's why every modern write-optimized store — Cassandra, RocksDB, Bigtable — uses them. By the end of this, you'll understand the internals well enough to tune compaction, diagnose write amplification, and know exactly when NOT to use an LSM Tree.

The Write Path: From Memtable to SSTable

Every write hits the memtable — an in-memory sorted structure (usually a skip list or red-black tree). This is fast: O(log n) insert, no disk I/O. When the memtable hits a size threshold (e.g., 64MB in RocksDB), it's frozen and a new memtable takes over. The frozen one is flushed to disk as an SSTable — a sorted, immutable file. This flush is a sequential write, so it's fast even on spinning rust. The key insight: all writes are sequential appends until compaction. No random writes, ever. This is why LSM Trees can absorb 100k+ writes/sec on a single node.

// io.thecodeforge — System Design tutorial

// Simplified memtable flush logic (RocksDB-like)
class Memtable {
    SkipList<String, String> data = new SkipList<>();
    int sizeBytes = 0;
    static final int MAX_SIZE = 64 * 1024 * 1024; // 64MB

    void put(String key, String value) {
        data.insert(key, value);
        sizeBytes += key.length() + value.length();
        if (sizeBytes >= MAX_SIZE) {
            triggerFlush(); // freeze and hand off to flush thread
        }
    }

    void triggerFlush() {
        // Flush thread picks this up, writes sorted data to SSTable
        // This is sequential write — no seeks
    }
}

// SSTable on disk: sorted key-value pairs + index + bloom filter
// File format: [Data Block 1][Data Block 2]...[Index][Bloom Filter][Footer]

The Read Path: Why LSM Trees Can Be Slow (and How Bloom Filters Save You)

Reads are the Achilles' heel. To find a key, you must search the memtable, then all SSTables from newest to oldest. Without optimization, that's O(#SSTables * log N) — terrible. Two things fix this: bloom filters and a multi-level index. Bloom filters tell you 'this key is definitely not in this SSTable' with a configurable false positive rate. The index (a sparse map of key → offset) lets you binary-search within an SSTable. In practice, a point lookup touches 1-2 SSTables on average if bloom filters are tuned right. But range scans still suck — they may need to merge across multiple SSTables.

// io.thecodeforge — System Design tutorial

class SSTable {
    BloomFilter bloom;
    Index index; // key -> offset in data file
    RandomAccessFile dataFile;

    String get(String key) {
        if (!bloom.mightContain(key)) return null; // definitely not here
        long offset = index.lookup(key);
        if (offset == -1) return null;
        // Read block at offset, binary search within block
        return readBlockAndSearch(offset, key);
    }
}

// Read path: check memtable -> check each SSTable in L0 -> check L1 -> ...
// Bloom filter avoids most disk reads. Tune bits_per_key: 10 bits = ~1% false positive.

Compaction: The Background Merge That Keeps Everything Sane

Compaction is the process of merging multiple SSTables into one, discarding overwritten and deleted keys. Without compaction, you'd have thousands of tiny SSTables and reads would be catastrophic. There are two main strategies: size-tiered (Cassandra default) merges SSTables of similar size; leveled (RocksDB, LevelDB) organizes SSTables into levels with exponentially increasing size. Leveled compaction is better for reads (fewer SSTables to check) but causes more write amplification. Size-tiered is simpler and has less write amplification but worse read performance. Choose based on your workload: read-heavy → leveled, write-heavy → size-tiered.

// io.thecodeforge — System Design tutorial

// Leveled compaction: each level is 10x the previous
// L0: files from memtable flushes (overlapping ranges)
// L1: non-overlapping, sorted, 10x size of L0
// L2: 100x L0, etc.
// When L1 exceeds target size, pick a file and merge with overlapping files in L2

class LeveledCompaction {
    static final double LEVEL_MULTIPLIER = 10.0;
    long maxBytesForLevel(int level) {
        return (long)(baseLevelSize * Math.pow(LEVEL_MULTIPLIER, level));
    }

    void maybeCompact(Level[] levels) {
        for (int i = 0; i < levels.length - 1; i++) {
            if (levels[i].totalSize > maxBytesForLevel(i)) {
                // Pick a file from level i, merge with overlapping files in level i+1
                doCompaction(levels[i], levels[i+1]);
            }
        }
    }
}

// Write amplification: each byte written may be rewritten multiple times during compaction.
// Leveled: ~10-30x. Size-tiered: ~3-5x.

When NOT to Use an LSM Tree

LSM Trees are not a silver bullet. If your workload is read-heavy with large range scans (e.g., 'SELECT * FROM orders WHERE user_id = ? ORDER BY timestamp'), a B-tree will crush an LSM Tree because data is stored contiguously on disk. LSM Trees also suffer from space amplification — old versions of keys linger until compaction catches up. If you need strict ACID transactions with point-in-time snapshots, a B-tree with MVCC (like Postgres) is simpler. Also, if your data fits entirely in memory, an LSM Tree adds unnecessary complexity. Use a hash map or a simple sorted array.