ROCKSDB 605: RocksDB LSM Tree

ROCKSDB 403 introduced RocksDB as TiKV's local key-value store. This chapter explains how it keeps writes recoverable and organizes data on disk so that reads can still find keys efficiently.

The write path is:

write
  |
  v
WAL -> active memtable -> flush -> L0 SST file
                                      |
                                      v
                        compaction -> SST files in L1 through L6

SST files are organized into levels, and compaction moves data through the deeper levels in the background.

WAL and Memtable

A completed write must survive a crash, and it must also become available quickly. RocksDB handles these two needs separately.

It first appends the write to the write-ahead log, or WAL. The WAL is an on-disk, append-only log. Appending is sequential and inexpensive. If RocksDB crashes after the WAL append but before the write reaches the memtable, it replays the WAL during restart to rebuild the missing in-memory state.

RocksDB then inserts the write into the active memtable. Think of a memtable as an in-memory key-value map. Unlike a hash map, it keeps keys in sorted order, so it can serve both point lookups and range scans.

put("name", "Alice")
        |
        v
append to WAL
        |
        v
insert into the active memtable

For TiKV's usual default and write column families, the active memtable has a 128 MiB size threshold. When it reaches that threshold, it becomes immutable: RocksDB stops adding new writes to it, creates a new active memtable, and flushes the immutable one in the background.

WAL                         memtables
--- write 1 ----------->    active: write 1, write 2, ...
--- write 2 ----------->

active reaches its size threshold
        |
        v
immutable memtable --------> background flush
new active memtable --------> accepts new writes

SST Files

A flush turns an immutable memtable into an SST file, short for Sorted String Table. An SST file is immutable and stores its keys in sorted order on disk.

An SST contains several kinds of blocks. Its key-value data is stored in data blocks. Each data block contains a consecutive range of sorted entries and can be compressed. Near the end of the file, index blocks map separator keys to the locations of data blocks. A footer locates the index and metadata blocks. RocksDB also keeps per-file metadata such as the smallest and largest keys.

SST file

data blocks
  block 1: [a ... f]
  block 2: [g ... n]
  block 3: [o ... z]

index blocks
  f -> block 1
  n -> block 2
  z -> block 3

footer: points to the index and metadata

To find k, RocksDB binary-searches the relevant index block to select a data block, then binary-searches within that block. The sorted layout makes both steps efficient. Range scans can start at the matching block and continue through later blocks.

SST Levels

RocksDB organizes SST files into levels. This arrangement is called a log-structured merge tree, or LSM tree.

Every flush creates an SST file in L0. L0 files can overlap in key range. This is intentional: each flush reflects whatever keys happened to be written while that memtable was active, and different memtables may contain updates to the same keys.

The deeper levels, L1 through L6 in TiKV's default layout, keep non-overlapping key ranges within each level:

L0: [a, h)       [e, n)       [m, z)     <- overlaps allowed

L1: [a, g) [g, p) [p, z)                    <- no overlap
L2: [a, n)        [n, z)                    <- no overlap

This is important for reads. A point lookup may need to check several overlapping L0 files, but it needs to check at most one SST file in each deeper level. RocksDB also checks the active and immutable memtables before the SST files.

Compaction

Compaction is the background process that reorganizes SST files and moves their data toward the bottom of the LSM tree. It chooses files from one level, includes the files with overlapping key ranges in the next level, merges their sorted entries, and writes new SST files to that deeper level.

L0:        [a, h) [e, n) [m, z)
                         |
                         v
L1:  [a, g) [g, p) [p, z)

During this merge, RocksDB can discard overwritten entries and deletion markers when no snapshot or lower level still needs them. The details of those rules matter for TiKV MVCC and return in ROCKSDB 804: GC and Compaction Filter.

Compaction does not stop reads or new writes. RocksDB first creates the output SST files, then atomically switches the current file list to use them in place of the compaction inputs. A flush or compaction therefore cannot expose a half-installed result.

Existing reads, iterators, or background work may still reference the replaced SST files. RocksDB waits until those references are gone before the files become eligible for deletion. Physical deletion can happen later.

RocksDB chooses compaction work from levels under pressure. In L0, the pressure is the number of files: TiKV starts L0 compaction at four files by default. In deeper levels, the pressure comes from a level exceeding its target size.

For an L1+ level, RocksDB chooses a key range, then includes every file in the next level whose range overlaps it. It merges those files together and replaces them with new files in the next level. This keeps that next level non-overlapping after the compaction.

Dynamic Level Sizes

Without dynamic level sizing, compaction would move data through every level from L0 to L6. For a small database, carrying the same data through mostly empty intermediate levels creates unnecessary compaction work.

TiKV enables dynamic level bytes to skip those empty levels. The first active level below L0 is called the base level. When the database is small, L6 is the base level, so data can compact directly from L0 to L6:

small database:  L0 -> L6
growing database: L0 -> L5 -> L6
larger database:  L0 -> L4 -> L5 -> L6

As the database grows, the base level moves upward and more intermediate levels become active.

For the usual default and write column families, the base level has a 512 MiB target. Each deeper level is about ten times larger. If L4 is the base level, the targets are roughly:

L4: 512 MiB
L5:   5 GiB
L6:  50 GiB

This avoids unnecessary compaction work while preserving the same read structure: overlapping L0 files, followed by non-overlapping deeper levels.

This completes the core LSM mechanism. The remaining RocksDB details are implementation and tuning topics.

At this level, keep the complete picture in mind:

WAL makes in-memory writes recoverable
memtables keep recent writes ordered in memory
flush creates sorted SST files
levels organize SST files for reads
compaction keeps the levels under control

ROCKSDB 704: RocksDB Details will return to flow control and the more detailed mechanics: concurrent writes, prefix seeks, compaction selection, parallelism, and output-file boundaries.