5.1 LSM-Tree Write, SSTables, and Read Merge

The Log-Structured Merge Tree (LSM-Tree) first writes online updates to a Write-Ahead Log (WAL) and a memory-resident sorted structure. Ordered runs are then flushed to persistent storage. This reduces foreground random page updates. Flushes, compaction, metadata updates, and garbage collection still consume resources in the background; the work has changed shifts.

Learning Objectives

• Describe the state transitions of WAL, mutable/immutable memtables, and SSTables;
• Explain the roles of sequence numbers, tombstones, and snapshot visibility;
• Understand the responsibilities of block index, Bloom filter, and block cache;
• Analyze why both point lookup and range scan require merging;
• Avoid the misconception that "all I/O in LSM is sequential write".

Writing Pipeline

A simplified flow:

write batch
  -> append WAL record
  -> insert internal entries into mutable memtable
  -> acknowledge according to durability option

mutable memtable reaches threshold
  -> freeze as immutable memtable
  -> create a new mutable memtable
  -> background flush immutable memtable to SSTable
  -> install new file through version/manifest metadata
  -> retire WAL segments no longer needed for recovery

Different engines have varying contracts regarding WAL sync, batching, memtable implementation, file installation, and atomicity. You cannot automatically infer that data is power-loss durable just because a Put operation returns; you must examine the write options and the underlying storage stack.

Front-end writes do not guarantee non-blocking behavior

If immutable memtables or Level 0 files accumulate, the engine must slow down or halt writes, otherwise, memory and read costs will grow without bound. LSM structures improve burst absorption, but they cannot sustain a long-term logical write rate beyond what the storage layer can achieve through flushes and compactions.

Internal key: Beyond the user key lies versioning

The same user key can be updated multiple times. Since SSTables are immutable and old values cannot be overwritten in place, the engine typically uses a structured ordering scheme like:

(user_key ascending, sequence_number descending, value_type)

The sequence number establishes a global or local update order, while the value type distinguishes between values, deletions, and other operations. When reading a snapshot S, only the most recently visible entry for sequence <= S is considered.

This is a conceptual model; the actual encoding and snapshot semantics are determined by the engine.

Delete is a tombstone

Put(k, v1) at seq=10
Delete(k)  at seq=20

A delete writes a tombstone because it cannot immediately erase k from every old SSTable. A snapshot with S >= 20 must honor the tombstone and cannot return the value at seq=10. An older snapshot with 10 <= S < 20 still reads v1, because the deletion is not yet visible.

A tombstone can be removed only when compaction proves that the older version is no longer needed by a snapshot, a lower level, or a replication/backup boundary. Removing it too early could cause old values to "come back to life."

Range tombstone, merge operator, and column-family drop will introduce more complex coverage rules.

MemTable

The memtable must support ordered insertions and lookups, typically implemented using skip lists, trees, or hash structures with an ordered variant. It resides in memory, but allocation overhead, key/value data, and version metadata all consume space. Capacity cannot be estimated from user payload alone.

After freezing, the immutable memtable no longer accepts updates and is flushed to disk in key order. The system may maintain multiple immutable memtables simultaneously; an increase in their count is a direct indicator that flush operations are falling behind write throughput.

SSTable is an immutable sorted run

A typical block-based SSTable:

data blocks
index block: separator/last key -> block handle
filter block or partitioned filters
properties/metadata
metaindex
footer: locating top-level metadata

Implementations may also include compression dictionaries, range-deletion blocks, checksums, and partitioned indexes or filters. SSTable is not a fixed standard format; LevelDB, RocksDB, Cassandra/ScyllaDB, and others cannot interoperate in reading.

Data block

Entries are sorted by internal key. To compress repeated key prefixes, the block may periodically store restart points; subsequent entries store the shared-prefix length plus unshared bytes. This allows lookups to first locate the restart region, then perform localized decoding, rather than reconstructing all keys from the beginning of the block.

Block index

The index maps key ranges to data block offsets or handles. The index itself may reside in memory or in a block cache, or it may be partitioned to avoid a single monolithic index consuming all available memory in large databases.

The Accuracy Boundary of Bloom Filters

Bloom filters for keys introduced at build time:

• A negative result means the key is definitely not present;
• A positive result means the key may be present;
• A false positive can cause an extra read of a file or block;
• Correct implementations must avoid false negatives.

However, this last condition depends on several assumptions: the filter must cover the correct key domain, queries must use the same prefix extractor, comparator, and configuration, and files must remain uncorrupted. Prefix Bloom filters only answer prefix-based queries; if the configuration changes or incompatible extractors are used, the filter will not function as expected.

There is a mathematical relationship between bits per key and the false-positive rate, but actual performance gains also depend on hash and probe counts, cache behavior, query mix, and CPU usage. It's incorrect to state that "10 bits guarantees filtering 99% of SSTables."

A whole-key Bloom filter answers whether one key might exist; it cannot directly prove that an arbitrary range is empty. A prefix filter can skip files that lack the requested prefix, but its usefulness depends on the extractor and query boundaries. It is not a general range index.

Point lookup

Conceptual path:

1. mutable memtable
2. immutable memtables, newest first
3. overlapping Level 0 files, newest relevant first
4. lower levels / runs according to compaction layout
5. stop when newest visible value/tombstone has been resolved

Each candidate file can first be narrowed using key range, filter, and index before reading the data block. Block cache hits, filter and index residency, checksums, and compression all impact latency.

"Read one file per level" is not a universal rule:

• Level 0 files often have overlapping ranges, which may require checking multiple files;
• In leveled lower levels, ranges within the same level typically do not overlap, allowing resolution to at most one relevant file;
• In tiered or universal layouts, the same key range may span multiple runs;
• Tombstone, snapshot, or merge operand conditions might require continuing to search older entries;
• Negative filters can avoid data reads, but still incur filter and index processing overhead.

Range scan is multi-way merging

Each memtable or SSTable provides an ordered iterator; a heap or loser tree merges their entries:

iterator(memtable) ---\
iterator(L0 file A) ----\
iterator(L0 file B) -----> merge by user key/version -> visibility -> output
iterator(L1 file) ------/

For the same user key, only the most recent valid value from a snapshot is output; tombstones and older versions are suppressed. When the number of active iterators is large or files overlap significantly, CPU usage, cache misses, and I/O operations all increase.

Range queries represent a significant cost in LSM design and cannot be fully justified by the point-lookup advantages of Bloom filters alone.

WAL and SSTable Installation

After a flush generates a new SSTable, the engine cannot simply claim persistence by "renaming a file." It must atomically and recoverably update the current version metadata and ensure that both file contents and directory/manifest ordering satisfy the crash contract.

RocksDB uses mechanisms like MANIFEST and version edits to manage live files. Isolated .sst files may not belong to the current database version, so the number of files in the directory cannot be used to infer the visible data.

Cache Layers

An LSM engine may simultaneously maintain:

• memtables;
• an uncompressed block cache;
• a compressed cache or OS cache;
• table reader/index/filter metadata;
• row cache;
• application cache.

Adding memory to the block cache can squeeze the memtable, leading to more frequent flushes; allocating excessive memory to the memtable can increase the size of recovery, WAL, and flush bursts. Allocate memory across these caches and buffers as one budget.

Lesson Summary

LSM-tree expresses updates as versioned immutable runs. The WAL and memtable handle incoming writes in real time, while SSTables provide an ordered, persistent structure. Reads are resolved through filter/indexing and multi-way merging to retrieve the most recent visible version. The next lesson covers how compaction manages file count and old versions, balancing trade-offs among read performance, write latency, storage usage, and tail latency.

Official Resources

• RocksDB Wiki
• RocksDB Block-Based Table Format
• RocksDB MemTable
• RocksDB Bloom Filter
• RocksDB Prefix Seek