LSM Trees and SSTables: How Write-Heavy Databases Work

Write-heavy databases such as Cassandra, RocksDB, LevelDB, ScyllaDB and HBase are built on two ideas. An SSTable (Sorted String Table) is an immutable file of key-value pairs kept in sorted key order. A log-structured merge tree (LSM tree) is the storage engine that turns a stream of random writes into a handful of sorted SSTables on disk, merging them in the background. Together they trade a bit of read work for very high, steady write throughput.

This is an internals page. Start with database indexing for why sequential writes beat random ones and how B-trees compare.

SSTables

The file-format problem

A storage engine needs a file format for sorted data on disk. A CSV-style file has to be scanned from the top, so lookups are O(n). A random-access format can find single keys quickly but makes range queries and compression awkward. SSTables combine sorted order with a small binary-searchable index, so they're good at both.

The idea comes from Google's Bigtable: store data in immutable, sorted files with sparse indexes. Once written, an SSTable never changes; updates and deletes are handled by writing new SSTables. Immutability makes aggressive caching, compression and concurrent reads easy, with no locking. SSTables are a file format, not a database: Cassandra, RocksDB and LevelDB use them as building blocks inside a larger engine.

SSTable file format

An SSTable has three parts:

• Data section: key-value pairs in lexicographic (sorted) key order, so they can be binary-searched.
• Sparse index: every Nth key with its byte offset in the file. Instead of indexing every key (which would take enormous memory), the engine indexes one key per block, with blocks commonly 4–64 KB depending on the engine. That's enough to jump close to any key.
• Metadata: min and max keys, record count, compression algorithm, Bloom filter data, checksums, creation timestamp and file size.

Reading from an SSTable

A point lookup is a two-step search: binary-search the sparse index to find the block that could hold the key, then search inside that block. That's O(log B) for B blocks plus O(log K) for K keys per block, O(log N) overall, while only the small sparse index has to live in RAM; data blocks are read on demand. Real engines check a Bloom filter first, skipping any SSTable that definitely doesn't contain the key.

Range queries are where the sorted layout pays off: find the start key with the sparse index, then read sequentially until you pass the end key. That makes SSTables a natural fit for analytics workloads that process ranges of data.

import bisect

class SSTableReader:
    """Read-only SSTable: a sorted data section plus a sparse index of every Nth key."""

    def __init__(self, entries, block_size=3):
        self.data = sorted(entries)                                    # data section
        self.sparse_index = [(self.data[i][0], i)                      # (first key, position)
                             for i in range(0, len(self.data), block_size)]
        self.index_keys = [key for key, _ in self.sparse_index]

    def _block(self, key):
        b = max(0, bisect.bisect_right(self.index_keys, key) - 1)     # step 1: sparse index
        start = self.sparse_index[b][1]
        end = self.sparse_index[b + 1][1] if b + 1 < len(self.sparse_index) else len(self.data)
        return start, end

    def get(self, key):
        if not self.data:
            return None
        start, end = self._block(key)
        keys = [k for k, _ in self.data[start:end]]                    # step 2: inside the block
        i = bisect.bisect_left(keys, key)
        return self.data[start + i][1] if i < len(keys) and keys[i] == key else None

    def range(self, lo, hi):
        start, _ = self._block(lo)                                     # find the start once...
        for k, v in self.data[start:]:                                 # ...then scan sequentially
            if k > hi:
                break
            if k >= lo:
                yield k, v

table = SSTableReader([("alice", "data1"), ("bob", "data2"), ("charlie", "data3"),
                       ("david", "data4"), ("eve", "data5"), ("frank", "data6"), ("grace", "data7")])
print(table.sparse_index)               # [('alice', 0), ('david', 3), ('grace', 6)]
print(table.get("charlie"))             # data3
print(list(table.range("bob", "eve")))  # bob, charlie, david, eve

Immutability and its limits

SSTables are immutable by design: there's no way to write to one after it's created. Adding or updating a key means writing a new SSTable with the newer value and relying on the read path to find the most recent version; the engine's compaction later merges files and atomically deletes obsolete ones. That limitation is exactly why LSM trees exist. The upside is that immutable files are ideal for distributed systems: they can be replicated, cached aggressively and read by many readers at once with no coordination, and copied or moved without affecting ongoing operations.

LSM trees

SSTables give sorted, immutable files but raise a new question: how do you handle a continuous stream of writes without creating thousands of tiny files? B-tree engines suffer write amplification because each small change reads a page, modifies it and writes it back to a random disk location. LSM trees remove that bottleneck by batching writes in memory and turning them into efficient sequential writes of SSTables.

Why batching works

Writing straight into existing sorted files would be catastrophic: adding one key to an existing 1 GB SSTable means reading the whole file, merging in the new entry and writing more than 1 GB back to disk. Patrick O'Neil's 1996 paper on the LSM tree introduced the fix: buffer writes in memory, flush them as sorted runs, and merge those runs when the system has spare I/O capacity. Disk work is deferred until it can be done efficiently, turning random writes into predictable sequential ones.

Core architecture

An LSM tree has three parts: a memtable (an in-memory sorted structure, often a skip list or balanced tree) for recent writes; immutable SSTables on disk, organized into levels; and a write-ahead log (WAL) that records every operation before it's acknowledged, so nothing in the memtable is lost in a crash.

Leveled organization

Frequent flushing without structure would create thousands of tiny files and ruin read performance. LSM trees use a pyramid: fresh data starts at level 0 and older data migrates to deeper, larger levels through background compaction:

1. The memtable fills up and is flushed as a new level-0 file (the newest data).
2. After several flushes, level 0 holds 4–8 separate files whose key ranges may overlap.
3. Background compaction merges the level-0 files into level-1 files.
4. When level 1 grows too large (typically 10× the size of level 0), it compacts into level-2 files.
5. The pattern continues; each deeper level is about 10× larger, and level 0 always holds the newest data.

That bounds lookup cost. Without levels, one lookup might check hundreds of files. With levels, level 0 holds a small, configurable number of overlapping files and each deeper level contributes at most one file per lookup, because files within a level don't overlap. Query latency stays steady even as the database grows to terabytes. Bigtable popularized the pattern; today Cassandra, DynamoDB and RocksDB rely on LSM variants for sustained write throughput. The price is complexity: reads may check several places, and compaction consumes significant I/O bandwidth.

Write path

Writes favor fast acknowledgement over disk efficiency. Each write appends to the WAL, updates the memtable and returns success. When the memtable reaches its size threshold (typically 64–256 MB), it becomes read-only, a fresh memtable takes new writes, and the full one is flushed to disk as a new level-0 SSTable. Because SSTables are immutable, flushing needs no coordination with concurrent readers.

• Fast in-memory insert and a sequential WAL append per write.
• Immediate acknowledgement; flushes never block new writes.
• Background compaction later merges level-0 files (say, 4 of them) into a merged, sorted level-1 SSTable.

The write-ahead log

The memtable lives in memory and vanishes in a crash, along with every write since the last flush. The WAL prevents that loss by recording each operation in an append-only disk file before the write is acknowledged. Entries look like this:

2024-01-15 14:30:25.123 PUT    user:123    "alice"
2024-01-15 14:30:25.456 DELETE user:456
2024-01-15 14:30:25.789 PUT    session:abc "active"

Recovery replays every WAL entry since the last successful flush to rebuild the memtable. Once a memtable's data is safely in an SSTable, its WAL entries are redundant and the log can be truncated. See write-ahead logging.

Updates and deletes: tombstones

LSM trees never modify existing data. An update writes a newer value for the same key. A delete writes a tombstone, a marker meaning "this key is deleted". Reads search from newest to oldest data, so recent entries automatically shadow older ones.

• No in-place edits: SSTables stay immutable, so readers always see consistent snapshots.
• Newer values shadow older ones; immutable files use logical deletion.
• The cost: obsolete values and tombstones keep using disk space until compaction removes them.

Read path

A read may have to look in several places. It checks the memtable first (the newest writes), then the SSTables from newest to oldest, stopping at the first match. Bloom filters answer "definitely not here" for most SSTables without touching disk; sparse indexes and block caches speed up the files that do need checking.

• Best case: the key is in the memtable, a pure memory lookup.
• Worst case: every level must be checked. This extra work is read amplification; compaction reduces it by keeping the number of files and levels small.
• Range scans stream across files in key order (a merge of the sorted inputs) and are cheapest once compaction has merged overlapping ranges.

Compaction

Without maintenance, flushes would pile up hundreds of small SSTables. Compaction periodically merges overlapping files into larger ones: pick the overlapping files, stream them in sorted key order (a priority-queue merge), and write a new SSTable with only the most recent version of each key. Sequence numbers decide which version is newest; tombstones override older live values (and a tombstone itself can be dropped once it reaches the bottom level, where no older copy of the key can remain). The new file gets fresh metadata, Bloom filters and checksums, and only after it is safely on disk does the engine update its manifest to swap out the input files.

Write amplification is the fundamental trade-off: each byte is rewritten several times as it moves down the levels. Depending on workload and configuration, RocksDB can see write amplification of 10× or more. The cost is amortized over many operations and runs in background threads, so it doesn't block user requests.

Production systems tune level sizes, fan-out ratios and compaction concurrency to balance these trade-offs.

Running LSM storage in production

• Compaction debt: heavy write bursts, node repairs or failed compactions leave many overlapping level-0 files. Reads still work but check more Bloom filters and disk blocks, so tail latency rises. Operators throttle writes or add resources until compaction catches up. Monitor level-0 file counts and pending compaction bytes as an early warning.
• Hot partitions: one partition key receiving most of the writes can saturate a single shard's WAL and memtable. Spread hot keys across partitions or shed load adaptively before compaction debt builds. See hot partitions.
• Tuning: level size ratios, target file sizes and the compaction strategy matter. Files that are too small cause constant rewrites; files that are too large slow recovery and reads. Watch write amplification together with read latency percentiles.

When to use LSM trees

The choice comes down to whether your bottleneck is write throughput or read efficiency.

A tiny LSM tree you can run

This demo shows every mechanism above: writes go to a WAL and memtable, full memtables flush into sorted runs, too many runs at a level trigger compaction into the next level, deletes are tombstones, and reads search newest to oldest.

class LSMTree:
    TOMBSTONE = None

    def __init__(self, memtable_limit=4, fanout=2):
        self.memtable, self.wal = {}, []
        self.levels = []                    # levels[i] = list of sorted runs, newest first
        self.memtable_limit, self.fanout = memtable_limit, fanout

    def put(self, key, value):
        self._write(key, value)

    def delete(self, key):
        self._write(key, self.TOMBSTONE)    # a delete is just a newer "tombstone" entry

    def _write(self, key, value):
        self.wal.append((key, value))       # 1. durability first
        self.memtable[key] = value          # 2. fast in-memory update
        if len(self.memtable) >= self.memtable_limit:
            self._flush()

    def _flush(self):
        self._add_run(0, dict(sorted(self.memtable.items())))   # immutable sorted run
        self.memtable, self.wal = {}, []    # data is on "disk": the WAL can be truncated

    def _add_run(self, level, run):
        while len(self.levels) <= level:
            self.levels.append([])
        self.levels[level].insert(0, run)
        if len(self.levels[level]) > self.fanout:
            self._compact(level)

    def _compact(self, level):
        merged = {}
        for run in reversed(self.levels[level]):  # oldest first, so newer values overwrite
            merged.update(run)
        self.levels[level] = []
        if not any(self.levels[level + 1:]):      # nothing older below: tombstones can go
            merged = {k: v for k, v in merged.items() if v is not self.TOMBSTONE}
        self._add_run(level + 1, dict(sorted(merged.items())))

    def get(self, key):
        if key in self.memtable:                  # newest data first
            return self.memtable[key]
        for runs in self.levels:                  # level 0, then deeper levels
            for run in runs:                      # newest to oldest (real engines: Bloom filter first)
                if key in run:
                    return run[key]               # a tombstone reads as "not found"
        return None

    def recover(self, wal_entries):
        for key, value in wal_entries:            # after a crash: replay the WAL
            self.memtable[key] = value

db = LSMTree(memtable_limit=2, fanout=2)
db.put("user:1", "alice"); db.put("user:2", "bob")          # flush -> level-0 run
db.put("user:1", "alice-v2"); db.delete("user:2")           # flush -> newer level-0 run
print(db.get("user:1"), db.get("user:2"))                   # alice-v2 None
db.put("user:3", "carol"); db.put("user:4", "dan")          # 3rd run -> compaction into level 1
print([len(runs) for runs in db.levels])                    # [0, 1]
print(db.levels[1][0])   # {'user:1': 'alice-v2', 'user:3': 'carol', 'user:4': 'dan'}

Writes batch in memory, flushes create sorted runs, compaction merges overlapping data (dropping user:2 because its tombstone reached the bottom level), and no existing run is ever modified in place.