vault

Log-Structured Merge Trees and Sorted String Tables

19 min read

Log-Structured Merge Trees and Sorted String Tables

This note is about the storage-engine plumbing of a Log-Structured Merge (LSM) engine: the concrete in-memory and on-disk data structures that turn the abstract “batch writes, flush sorted runs, merge later” idea into real bytes. The abstract algorithm — the write path in the abstract, tombstone semantics, complexity, a Python model — lives in LSM Tree and is not repeated here; the compaction theory — write/read/space amplification, leveled-versus-tiered, the RUM conjecture — lives in Compaction and the Amplification Trade-offs. What this note owns is the machinery: the memtable (a concurrent ordered structure, usually a Skip List) fronted by a Write-Ahead Log, and the Sorted String Table (SSTable) — the immutable, block-structured, prefix-compressed, Bloom-filtered, index-terminated file that every LSM engine reads from. The SSTable name and shape come from Google’s Bigtable, which defines it as “a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings” (Chang et al. 2006, §4); the concrete file format we dissect is LevelDB’s and RocksDB’s BlockBasedTable (RocksDB wiki). The whole apparatus exists to honor O’Neil et al.’s original design goal: an algorithm that “defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort” (O’Neil et al. 1996).

Mental Model — A Buffer, a Journal, and a Stack of Frozen Files

Think of an LSM engine as three cooperating parts. A memtable is a small, sorted, mutable buffer in RAM that absorbs every write. A write-ahead log is an append-only journal on disk that mirrors those same writes so a crash cannot lose them. And a growing collection of SSTables are immutable, sorted files on disk, each one a frozen snapshot of a memtable that filled up and was flushed. Writes only ever touch the memtable and the log (both cheap and sequential); reads consult the memtable first and then walk the SSTables newest-to-oldest, using a per-file Bloom Filter to skip files that provably cannot contain the key. The engine never edits an SSTable in place — it only creates new ones and deletes obsolete ones — which is the single design decision that makes everything else (lock-free reads, page-cache friendliness, snapshot isolation) fall out cheaply.

flowchart TD
    W["Client write<br/>put(k,v) / delete(k)"] --> WAL[("WAL / commit log<br/>append-only, sequential")]
    W --> MEM["Active memtable<br/>skip list, sorted, mutable"]
    MEM -->|"fills (write_buffer_size)"| IMM["Immutable memtable<br/>read-only, awaiting flush"]
    IMM -->|"background flush thread"| L0["L0 SSTable<br/>immutable, sorted file<br/>(key ranges may overlap)"]
    L0 -->|"compaction (see sibling note)"| L1["L1..Ln SSTables<br/>non-overlapping per level"]

    R["Client read<br/>get(k)"] -.->|"1. check"| MEM
    R -.->|"2. check"| IMM
    R -.->|"3. newest to oldest,<br/>Bloom-filter gated"| L0
    R -.->|"binary-search index,<br/>one block read"| L1

What this shows and the insight to take. The vertical path is the write path: a write is journaled to the WAL and inserted into the mutable memtable; when the memtable hits write_buffer_size it is sealed (made immutable), a fresh memtable is swapped in, and a background thread serializes the sealed one into a brand-new Level-0 SSTable. The dotted path is the read path, which walks the same structures in the opposite (newest-first) direction. The key insight: writes are confined to two sequential, in-order-friendly structures (log + memtable), while all the on-disk complexity is immutable — so the read path is elaborate but lock-free, and the write path never does random I/O.

Mechanical Walk-through

The write path: WAL first, then memtable

A write enters the engine and does two things. First it is appended to the write-ahead log — in LevelDB a *.log file, in RocksDB a shared WAL, in Cassandra the CommitLog. The log is the durability anchor: because the memtable lives only in volatile RAM, the log is what a restart replays to rebuild it. RocksDB’s overview lists exactly three constructs — an in-memory memtable, a “sequentially-written” log file (WAL), and the on-disk SST file — and states the write flow plainly: new writes are inserted into the active memtable and (optionally) the WAL (RocksDB Overview). Second, the write is inserted into the memtable, which must be an ordered in-memory structure so that a flush emits keys already sorted, with no re-sort. RocksDB’s default is a skip list — “The default implementation of memtable is based on skiplist” — and it exposes pluggable memtable factories: SkipList, HashSkipList, HashLinkList, and Vector, chosen via the memtable_factory option for different access patterns (RocksDB MemTable). Concurrent inserts are enabled by default (allow_concurrent_memtable_write), though only the skip-list memtable supports them — one reason the skip list, not a red-black tree, is the default (a Skip List admits lock-free concurrent insertion far more naturally than a rotation-based balanced tree).

When the active memtable reaches its size bound it is sealed. In RocksDB that bound is write_buffer_size, whose default is 64 MB (as of the RocksDB wiki, mid-2026), and up to max_write_buffer_number memtables (default 2) may exist at once — one active plus immutable ones queued for flush (RocksDB MemTable). LevelDB uses a smaller buffer: its *.log file “is converted to a sorted table” once it reaches “approximately 4MB by default” (LevelDB impl). Sealing swaps in a fresh memtable so writes never block, marks the old one immutable, and hands it to a background thread that writes it out as a new SSTable at Level 0. Crucially, once that immutable memtable is durably flushed, the WAL segment that backed it can be discarded: “When the memtable fills up, it is flushed to a sstfile on storage and the corresponding logfile can be safely deleted” (RocksDB Overview). This is why the WAL never grows without bound — it only needs to cover memtables not yet on disk.

The SSTable on-disk format (the heart of the note)

An SSTable is a self-describing, immutable file read from its tail inward. The BlockBasedTable layout, shared in spirit by LevelDB and RocksDB, is a sequence of data blocks, then several meta blocks, then a metaindex block, an index block, and a fixed-size footer (RocksDB BlockBasedTable; LevelDB table_format):

[ data block 1 ]          <- sorted key/value entries, prefix-compressed
[ data block 2 ]
      ...
[ data block N ]
[ meta: filter block ]    <- Bloom (or ribbon/partitioned) filter over the keys
[ meta: index block ]     <- one entry per data block -> its BlockHandle
[ meta: compression dict ]
[ meta: range deletion ]  <- range tombstones (kTypeRangeDeletion)
[ meta: properties/stats ]
[ metaindex block ]       <- name -> BlockHandle for each meta block
[ index block ]           <- binary-search structure over data blocks
[ Footer ]                <- fixed size; offsets to metaindex & index + magic

The atom of I/O is the data block, whose default size is 4 KB (4096 bytes) in both engines (RocksDB BlockBasedTable). Inside a block, keys are stored in sorted order and prefix-compressed against the previous key to save space: each entry records the number of shared prefix bytes it has in common with its predecessor, the number of unshared (new) bytes, the value length, then the unshared key bytes and the value. To keep the block searchable despite this delta encoding, the block plants restart points — every block_restart_interval entries (default 16) it stores a full key rather than a delta, and it keeps an array of the byte offsets of these restart points. A lookup binary-searches the restart-point array (each of which is a complete key), then scans forward through at most 16 delta-encoded entries. This is the mechanism that lets a 4 KB block hold many keys yet still be searched in roughly log time. Each block is independently compressed (Snappy/LZ4/Zstd) and carries a trailer of 1 byte of compression/checksum type plus a 4-byte checksum — CRC32c by default (RocksDB BlockBasedTable).

Every internal pointer in the file is a BlockHandle: an (offset, size) pair, each a varint64. The index block contains “one entry per data block,” whose key is (in LevelDB’s precise wording) “a string >= last key in that data block and before the first key in the successive data block,” and whose value is the BlockHandle of that data block (LevelDB table_format). This index is small enough to live in RAM once the file is opened; RocksDB additionally supports a partitioned (two-level) index so that giant files do not require a single huge index block in memory. The filter block holds a Bloom Filter (or a partitioned filter, or the deprecated block-based filter, or a ribbon filter) over the SSTable’s keys; the metaindex maps the name filter.<Name> — where <Name> is the filter policy’s identifier — to the filter’s BlockHandle (LevelDB table_format). The metaindex block is just a directory: one entry per meta block, mapping its name to its BlockHandle.

The footer is what makes the file bootstrappable, and it is fixed-size so a reader can seek straight to file_size - sizeof(Footer) and parse it. LevelDB’s footer is 48 bytes: a metaindex BlockHandle, an index BlockHandle, zero padding out to 40 bytes (40 == 2 * BlockHandle::kMaxEncodedLength), and an 8-byte little-endian magic number 0xdb4775248b80fb57 (LevelDB table_format). RocksDB’s versioned footer is 53 bytes (it adds a checksum-type byte and a format_version; format_version=5 since RocksDB 6.6 selects the optimized Bloom implementation) and uses a different magic, 0x88e241b785f4cff7 (RocksDB BlockBasedTable). To open an SSTable the engine reads the footer, follows the index BlockHandle to load the index into memory, follows the metaindex to find the filter, and is then ready to serve lookups.

This layout is essentially the one Bigtable described in 2006: “each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory” (Bigtable §4). Note Bigtable’s default block was 64 KB where LevelDB/RocksDB use 4 KB — the same shape, tuned differently for GFS versus local SSD.

Immutability and why it buys so much

Once written, an SSTable is never modified — it is only read, and eventually deleted after compaction makes its contents redundant. Cassandra states it flatly: “SSTables are immutable, and never written to again after the memtable is flushed” (Cassandra Storage Engine). Immutability is the quiet workhorse of the design. Because a file’s bytes never change, reads need no locking against writers — a reader holding an open SSTable sees a stable file forever. The OS page cache caches SSTable blocks perfectly, since cached pages can never go stale. Snapshot isolation (see Multiversion Concurrency Control) becomes reference counting: a snapshot pins the set of SSTables live at its creation, and compaction simply must not delete a file a snapshot still references. And crash consistency is trivial for the data files: a half-written SSTable during a flush is just discarded and re-flushed from the still-present memtable/WAL, because no existing file was mutated. Engines layer a block cache — RocksDB’s is an “LRU cache for blocks” (RocksDB Overview) — on top of the OS page cache; the block cache holds decompressed, ready-to-search blocks, avoiding repeated decompression, while the page cache holds raw compressed file pages.

The read path plumbing

A point lookup consults sources newest-to-oldest and stops at the first hit (which, being newest, is authoritative). The order is: active memtable → immutable memtable(s) → SSTables from L0 (newest first) down through the deeper levels (RocksDB Overview). For each candidate SSTable, the engine first asks its Bloom filter “could this key be here?”; if the filter says no, the file is skipped with zero disk I/O (the filter’s math and false-positive behavior are covered in Bloom Filter and are not re-derived here). If the filter says “maybe,” the engine binary-searches the in-RAM index block to find the one data block that could contain the key, reads that block (or hits it in the block cache), and scans it via its restart points. So a hot point read costs one Bloom check per candidate file plus, at the level where the key lives, at most one block read — the property that makes LSM point reads viable.

Range scans behave differently and Bloom filters do not help them (a Bloom filter answers point membership only). A scan opens a merging iterator over the memtable and every SSTable whose key range overlaps the requested [lo, hi], and performs a k-way merge, emitting each key once with the newest version winning. Bigtable makes the elegance of this explicit: “Since the SSTables and the memtable are lexicographically sorted data structures, the merged view can be formed efficiently” (Bigtable §5.3). The cost of a scan therefore grows with how many SSTables overlap the range — which is exactly what compaction organization controls.

Level organization

Flushed SSTables land at Level 0, and L0 is special: because it receives raw memtable flushes, its files’ key ranges can overlap each other, so a read may have to check every L0 file. Levels below L0 are kept non-overlapping within each level by compaction. LevelDB states the invariant directly: “Files in the young level [L0] may contain overlapping keys. However files in other levels have distinct non-overlapping key ranges” (LevelDB impl). A read at any level ≥ 1 therefore touches at most one file (binary search picks it), while L0 may cost several probes — which is why engines cap the number of L0 files and stall writes when it is exceeded. The two dominant ways to organize the deeper levels — leveled (one sorted run per level, the LevelDB/RocksDB default per the RocksDB Overview) versus size-tiered (a bag of similarly sized runs per level) — are introduced here only as the two shapes; their amplification trade-offs belong to Compaction and the Amplification Trade-offs.

A Concrete, Annotated SSTable Byte Layout

Suppose a memtable flush produces an SSTable holding three keys with a common prefix user:100. One 4 KB data block encodes them with prefix compression and a restart point at the first key:

=== DATA BLOCK 0 (offset 0) ==============================================
entry 0  [RESTART POINT]  shared=0  unshared=9  vlen=5  "user:1001" "alice"
entry 1                   shared=8  unshared=1  vlen=3  "2"         "bob"
entry 2                   shared=8  unshared=1  vlen=5  "3"         "carol"
...
restart_offsets = [0]      # byte offset of entry 0 within the block
num_restarts    = 1        # 4-byte trailer field
block trailer:   type=1B (e.g. Snappy)  checksum=4B (CRC32c)
=== FILTER BLOCK =========================================================
Bloom bits over {"user:1001","user:1002","user:1003"}   # gates point reads
=== INDEX BLOCK ==========================================================
entry: key="user:1004"  value=BlockHandle(offset=0, size=<block0 len>)
       # a separator >= last key of block0, < first key of the next block
=== METAINDEX BLOCK ======================================================
"filter.rocksdb.BuiltinBloomFilter" -> BlockHandle(off, size)
=== FOOTER (48 B LevelDB / 53 B RocksDB) =================================
metaindex_handle = varint(off), varint(size)
index_handle     = varint(off), varint(size)
padding          = 0x00 ... (out to 40 bytes)
magic            = 0xdb4775248b80fb57   # LevelDB (little-endian on disk)
                 = 0x88e241b785f4cff7   # RocksDB
==========================================================================

Reading this walks tail-first. The engine seeks to file_size - 48 (LevelDB) or - 53 (RocksDB), reads the footer, checks the magic, follows index_handle to load the index, and follows metaindex_handle to find filter.<Name> and load the Bloom filter. To answer get("user:1002"): the Bloom filter says “maybe,” the index’s single entry ("user:1004" -> block0) says the key sorts into block 0, block 0 is read (one I/O), its restart array [0] puts a binary search at entry 0’s full key "user:1001", and a forward scan reconstructs "user:100"+"2" = "user:1002" -> "bob". Line by line: shared=8 means “reuse the first 8 bytes of the previous key,” unshared=1 supplies the differing byte "2", and vlen=3 bounds the value — the delta encoding that makes prefix compression concrete.

Engines in the Wild (dated)

Bigtable (Google, internal since ~2004; the OSDI paper is 2006) is the origin of the term SSTable and the source of the “commit log + memtable + SSTable” write path we still use: “Updates are committed to a commit log… recently committed ones are stored in memory in a sorted buffer called a memtable; the older updates are stored in a sequence of SSTables”; when the memtable hits a threshold it is “frozen… converted to an SSTable and written to GFS” (Bigtable §5.3–5.4). LevelDB (Google, open-sourced 2011; Dean & Ghemawat) is the compact reference implementation and the source of the BlockBasedTable/.ldb format, the MANIFEST (which “lists the set of sorted tables that make up each level, the corresponding key ranges”) and the CURRENT file (a “text file that contains the name of the latest MANIFEST file”) (LevelDB impl). RocksDB (Meta’s fork of LevelDB, current as of 2026-07) adds column families — each with its own memtable and SST files but sharing a common WAL, enabling atomic cross-family WriteBatch writes (RocksDB Overview) — plus pluggable memtables, partitioned index/filter, and ribbon filters. Apache Cassandra and ScyllaDB run a per-replica local LSM: a CommitLog for durability, one memtable per table, and SSTables materialized as a set of component files — Data.db (“the contents of rows”), Index.db, Summary.db (“a sampling of (by default) every 128th entry in the Index.db”), Filter.db (“a Bloom Filter of the partition keys”), Statistics.db, CompressionInfo.db, Digest.crc32, and TOC.txt (the list of components); Cassandra 5.0’s BTI format replaces Index.db with Partitions.db/Rows.db (Cassandra Storage Engine). HBase stores its SSTable equivalent as the HFile on HDFS. WiredTiger (MongoDB’s default engine) is the interesting outlier: its default table type is a B-tree, and an LSM tree is opt-in, created explicitly with type=lsm — session->create(session, "table:bucket", "type=lsm,key_format=S,value_format=S") — after which an in-memory btree chunk is synced to disk once it hits chunk_size, Bloom filters are built during merges, and a background thread merges chunks (WiredTiger LSM). WiredTiger’s own guidance: “If you have a workload that requires a high write throughput LSM is the best choice… If you don’t require extreme write throughput btree is likely to be a better choice. Read throughput is better” (WiredTiger Btree vs LSM).

Uncertain

Verify: (1) that WiredTiger’s default schema type is btree (not merely that LSM is created “much the same way as a btree file”); the LSM doc I fetched implies this but does not state “btree is the default” verbatim, and the “default” phrasing came from a search snippet. (2) That MongoDB actually exposes/uses the WiredTiger LSM option in production — MongoDB ships WiredTiger btree by default, but whether the LSM table type is user-selectable or effectively unused/removed in current MongoDB is not confirmed against a MongoDB primary source. Reason: no directly-fetched MongoDB doc; WiredTiger “default” wording indirect. To resolve: check current MongoDB storage-engine docs and WiredTiger WT_SESSION::create reference for the default type. uncertain

Failure Modes

WAL not fsynced loses “durable” writes. If the engine acknowledges a write after only buffering the WAL record (not fsync-ing it), an OS or power crash loses those records even though the memtable had them — the SSTables are fine, but the recent tail is gone. The WAL exists precisely so recovery can “reconstruct the memtable from the logs” (RocksDB WAL Format); if it was never on stable storage there is nothing to replay. The trade is throughput versus durability, softened by group commit (batching many records into one fsync). Note the WAL’s own robustness comes from its framing: it is a sequence of 32 KB blocks, each record prefixed by a 7-byte header (4-byte CRC32c, 2-byte length, 1-byte type), with a record that spans blocks split into kFirstType/kMiddleType/kLastType fragments — so a torn tail record is detected by checksum and truncated rather than silently misread (RocksDB WAL Format).

L0 file pile-up and write stalls. Because L0 files can overlap, an ingest burst that flushes memtables faster than compaction can drain them makes reads consult more and more overlapping L0 files, and CPU saturates on compaction. Engines defend by stalling writes once L0 exceeds a watermark (LevelDB compacts once “the number of young files exceeds a certain threshold (currently four)” (LevelDB impl)). The application sees latency spikes; the fix is tuning compaction concurrency against ingest rate — the details, being amplification trade-offs, live in Compaction and the Amplification Trade-offs.

Cold block cache and cold page cache. Right after startup both the block cache and the OS page cache are empty, so every index/data-block access is a disk read and tail latency is far worse than steady state. Because SSTables are immutable, warming is safe and easy — replay recent files into cache — which is why immutability pays off operationally, not just for correctness.

Wrong filter or hash on read. The filter block is only useful if the reader reconstructs the exact filter policy the writer used; the metaindex therefore names it filter.<Name>. A version mismatch that misreads the policy would degrade to reading every file (a performance failure, not a correctness one, since the authoritative check always follows the filter — see Bloom Filter).

Tombstone-heavy reads. Deletes are writes (tombstone records), and a range scan over a region full of not-yet-collected tombstones must read and skip them all. Diagnosing and tuning tombstone reclamation is a compaction concern and is covered in Compaction and the Amplification Trade-offs and LSM Tree, not here.

Alternatives and When to Choose Them

The natural foil is the B+tree storage engine (PostgreSQL, InnoDB, SQLite, WiredTiger’s default): it updates pages in place, giving excellent read locality and low read/space amplification, at the cost of random writes. The LSM engine inverts this — sequential writes and cheap ingest, at the cost of a multi-file read path and compaction overhead — which is why WiredTiger’s own advice reduces to “LSM for high write throughput, btree for better read throughput” (WiredTiger Btree vs LSM). The B+tree page is mutable and uses a slotted-page layout with an in-page slot directory that is rewritten on every update; the SSTable block is immutable and prefix-compressed, written once and never touched — the sharpest structural contrast between the two engine families. For an OLAP scan-heavy workload, neither row-oriented engine is ideal; a column store wins there. The choice among these is exactly the “B-tree or LSM?” decision framed in the Database Internals MOC.

See Also

Graph View

Backlinks