Writes, memtables and SSTables

An LSM tree never updates a file in place. A write goes to two places at once: a log on disk, so a crash cannot lose it, and an in-memory sorted buffer. When the buffer fills, it is frozen and written out as a new sorted file. Nothing on disk is ever modified after it is written.

The three parts

1. Memtable. An in-memory sorted structure, usually a skip list in LevelDB and RocksDB, that takes every write. RocksDB's default write_buffer_size is 64 MB.
2. Write-ahead log. Each write is appended to the log before it enters the memtable. The log is discarded once its memtable is safely flushed.
3. SSTables. When the memtable is full, it becomes immutable, a fresh memtable takes over, and a background thread writes the frozen one to disk as a sorted file.

Updates do not overwrite anything. Writing user:42 → v2 adds a newer entry. The old v1 stays in an older file until compaction removes it. The newest version wins on read.

Walking through it: a tiny LSM

This sketch leaves out the WAL, Bloom filters and levels, but keeps the shape: writes go to a memtable, a full memtable flushes to a sorted run, and reads check the newest data first.

import bisect

class TinyLSM:
    def __init__(self, memtable_limit=4):
        self.memtable = {}                    # real engines use a skip list
        self.sstables = []                    # newest first; each is sorted (key, value)
        self.limit = memtable_limit

    def put(self, key, value):
        self.memtable[key] = value            # real engines append to a WAL first
        if len(self.memtable) >= self.limit:
            self.flush()

    def flush(self):
        self.sstables.insert(0, sorted(self.memtable.items()))  # one sequential write
        self.memtable = {}

    def get(self, key):
        if key in self.memtable:
            return self.memtable[key]
        for run in self.sstables:             # newest to oldest
            i = bisect.bisect_left(run, (key,))
            if i < len(run) and run[i][0] == key:
                return run[i][1]
        return None

lsm = TinyLSM(memtable_limit=2)
lsm.put("user:1", "ana")
lsm.put("user:2", "ben")      # memtable reaches 2 entries and flushes
lsm.put("user:1", "anna")     # newer version shadows the one in the SSTable
print(lsm.get("user:1"))
print(lsm.get("user:2"))

anna
ben

The second put fills the memtable, so both keys flush into one sorted run. The third put writes user:1 to the new memtable. get("user:1") finds it there first. get("user:2") misses the memtable, so it binary-searches the flushed run and finds ben.

Inside an SSTable

A real SSTable is more than a sorted list. A RocksDB block-based table contains:

• Data blocks of sorted key-value pairs, about 4 KB each by default. They are usually compressed, with LZ4 or Zstd, and share key prefixes.
• An index block that maps the last key of each data block to its offset. A lookup binary-searches the index, then reads one data block.
• A filter block holding a Bloom filter (or the more compact Ribbon filter) over the file's keys. See the next page.
• Properties and a footer.

Because files are immutable, they compress well and can be cached without invalidation. They can also be copied for backups and replication. They never need the torn-page protection that in-place B-trees need.

Common mistakes

• Assuming the memtable is durable on its own. It lives in RAM. The WAL is what survives a crash.
• Thinking an update touches the old value. It adds a newer entry, and the old one lingers until compaction.
• Expecting cheap range scans out of the box. Data for one key range sits in many files, so a scan must merge them.

Check yourself

• Why is a flush a sequential write? The memtable is already sorted, so the whole file is written in one pass, from start to end.
• What happens to the old version of user:1 after the update? It stays in an older SSTable until compaction removes it. Reads never see it, because the newer version is found first.

Key takeaways

• Every write goes to a WAL and a memtable. The disk only sees sequential appends and whole-file flushes.
• A full memtable becomes an immutable, sorted SSTable.
• Updates and deletes add entries. Nothing on disk is overwritten.
• Data blocks, an index and a Bloom filter make each SSTable searchable without reading all of it.

Further learning

Next, see how reads find the newest value across many files, and how deletes work, in reads, deletes and Bloom filters.

The CMU 15-445 lecture on log-structured storage covers LSM trees in the context of a full database course.