RocksDB : storage engine for TiKV

RocksDB is the embeddable LSM key-value engine under each TiKV store. TiKV builds tikv/rocksdb (branch 8.10.tikv) through rust-rocksdb, and opens two DB instances—kvdb (MVCC column families) and raftdb (Raft HardState + log).

Related: TiKV: Multi-Raft storage.

1. Overview

RocksDB stores sorted string tables on disk and recent updates in memory. A single DB handle exposes Put / Delete / Write / Get / iterators over one or more column families (CFs). Durability comes from an append-only WAL; queryability comes from MemTables plus leveled SST files. Compaction merges SST levels in the background to bound read amplification.

In a TiKV store process, RocksDB is the local disk layer only. Consensus and transaction protocol sit above it (TiKV): Raft commits decide whether a mutation is durable and replicated; RocksDB applies the resulting byte Puts/Deletes into CF files. TiKV’s fork tracks RocksDB 8.10 with TiKV-oriented patches (Titan blob indexes, multi-batch write, flow / IO rate control, ingestion race fixes). It is not a continuous sync of upstream main; upgrades are deliberate pins.

TiKV’s kvdb uses CFs such as default, lock, write (and others for meta). raftdb holds Raft machinery per Region peer. Both are ordinary RocksDB directories with different Options and key encodings.

2. Architecture

A RocksDB DB is one directory on disk and one DBImpl in the process. Physical layout is what survives crash; memory layout is what serves reads and accepts writes until flush. Between them sits the LSM-tree: the organization of MemTables and SST levels that makes durable writes cheap and keeps reads correct.

2.1 Physical layout

Everything for one open engine lives under a single DB path (TiKV’s kvdb and raftdb are two such directories). Files fall into three roles:

SST filenames are global file numbers; which CF and level each belongs to is not encoded only in the path—MANIFEST / Version owns that mapping. TiKV kvdb typically keeps separate LSM trees for lock, write, and default (and meta CFs) inside the same directory and shared WAL.

Crash recovery reads CURRENT → MANIFEST → live SST set, then replays WAL into MemTables. Compaction and flush only become durable after a MANIFEST VersionEdit is appended and synced.

2.2 Memory layout

After DB::Open, the process holds one DBImpl. Shared pieces: VersionSet (current Version per CF, sequence numbers, file numbering), WalManager, write thread / DB mutex, and optional WriteBufferManager. Per column family, ColumnFamilyData owns:

• mem_ — active MemTable (skiplist + arena); writers insert here
• imm_ — immutable MemTable list waiting for / undergoing flush
• super_version_ — a refcounted snapshot of mem + imm + current Version (SST file list), so readers can proceed without holding the DB mutex for the whole Get
• current_ — the CF’s live Version (levels → FileMetaData → SST paths)

Block / blob cache entries are separate heap objects keyed by file+offset; SuperVersion and iterators pin them while a read is in flight.

A multi-CF WriteBatch updates several mem_ instances under one WAL append and one sequence assignment—hence atomicity across lock / default on a single engine.

2.3 Code Structure

RocksDB has no SQL parser; the public DB API (Put, Delete, Write, Get) builds or accepts a WriteBatch—a length-prefixed record stream—and DBImpl executes it. WriteBatchInternal::InsertInto walks those records with a MemTableInserter handler (one PutCF / DeleteCF per record). Reads pin a SuperVersion and delegate to MemTable::Get, then Version::Get via TableCache. Background FlushJob / CompactionJob publish VersionEdit through VersionSet::LogAndApply.

@startuml

struct DB {
  Open()
  Put()
  Delete()
  Write()
  Get()
  NewIterator()
}

struct DBImpl {
  WriteImpl()
  GetImpl()
  mutex_ : InstrumentedMutex
}

struct ColumnFamilyHandle {
  GetID()
  GetComparator()
}

struct ColumnFamilyHandleImpl {
  cfd : ColumnFamilyData
}

struct WriteBatch {
  records : encoded bytes
}

struct WriteBatchHandler {
  PutCF()
  DeleteCF()
}

struct WriteBatchInternal {
  InsertInto()
  SetSequence()
  Count()
}

struct MemTableInserter {
  sequence_ : SequenceNumber
}

struct WriteThread {
  JoinBatchGroup()
}

struct WalManager {
  logs : alive log files
}

struct LogWriter {
  AddRecord()
}

struct ColumnFamilySet {
  cf_list : column families
}

struct ColumnFamilyData {
  mem_ : MemTable
  imm_ : MemTableList
  super_version_ : SuperVersion
  current_ : Version
  table_cache_ : TableCache
}

struct SuperVersion {
  mem : MemTable
  imm : MemTableListVersion
  current : Version
}

struct MemTable {
  Add()
  Get()
}

struct MemTableList {
  imm : flushing tables
}

struct MemTableListVersion {
  snapshot : imm list
}

struct VersionSet {
  LogAndApply()
  NewFileNumber()
}

struct Version {
  levels : SST files
  Get()
}

struct VersionEdit {
  add_files : SST refs
  delete_files : SST refs
}

struct TableCache {
  Get()
  NewIterator()
}

struct TableReader {
  blocks : SST pages
}

struct FlushJob {
  edit : VersionEdit
}

struct CompactionJob {
  edit : VersionEdit
}

struct LookupKey {
  key : user key
  seq : sequence
}

WriteBatchHandler <|-- MemTableInserter
DB <|-- DBImpl
ColumnFamilyHandle <|-- ColumnFamilyHandleImpl

DBImpl *-- VersionSet
DBImpl *-- WalManager
DBImpl *-- WriteThread
DBImpl o-- ColumnFamilyHandleImpl

VersionSet *-- ColumnFamilySet
ColumnFamilySet o-- ColumnFamilyData

ColumnFamilyHandleImpl --> ColumnFamilyData
ColumnFamilyData *-- MemTable
ColumnFamilyData *-- MemTableList
ColumnFamilyData *-- SuperVersion
ColumnFamilyData --> Version
ColumnFamilyData *-- TableCache

SuperVersion --> MemTable
SuperVersion --> MemTableListVersion
SuperVersion --> Version

DBImpl ..> WriteBatch
DBImpl ..> WriteBatchInternal
WriteBatch ..> WriteBatchHandler
WriteBatchInternal ..> MemTableInserter
MemTableInserter ..> MemTable
WriteThread ..> WalManager
WalManager ..> LogWriter
WriteThread ..> WriteBatchInternal

DBImpl ..> SuperVersion
DBImpl ..> LookupKey
DBImpl ..> MemTable
DBImpl ..> Version
Version ..> TableCache
TableCache *-- TableReader

FlushJob ..> VersionEdit
CompactionJob ..> VersionEdit
VersionEdit ..> VersionSet
VersionSet ..> SuperVersion

@enduml

Write path. DB::Put wraps one key into a WriteBatch and calls Write. DBImpl::WriteImpl joins the WriteThread queue; the leader appends the batch through WalManager / log::Writer, assigns a sequence number, then WriteBatchInternal::InsertInto drives MemTableInserter into each CF’s mem_. A full MemTable triggers FlushJob, which emits a VersionEdit and VersionSet::LogAndApply.

Read path. DBImpl::GetImpl resolves ColumnFamilyHandleImpl::cfd, pins SuperVersion, builds a LookupKey, probes mem_ and imm_, then Version::Get, which uses TableCache to load TableReader blocks from SST files. Iterators follow the same stack via DBIter over a merging iterator.

Recovery. DB::Open constructs DBImpl, loads VersionSet from MANIFEST, and RecoverLogFiles replays WAL batches through the same InsertInto path into fresh MemTables.

2.4 TiDB tables and indexes in kvdb

TiDB stores rows and secondary indexes in the same kvdb RocksDB instance—the same shared WAL and the same lock / write / default column families as any other TiKV data (TiKV §4.2). There is no separate RocksDB per table or per index.

What differs is the encoded key:

Because _i and _r are different byte prefixes, index keys and row keys sort into different ranges in the global keyspace. Flush and compaction write immutable SST files that each cover a contiguous key interval. An index-only range scan therefore opens SST files whose keys are mostly t42_i…; a primary-key scan opens files whose keys are mostly t42_r…. Same engine, same CF trees—separate on-disk files because the keys are separate.

One INSERT still writes both a record key and each index key in one Raft apply (WriteBatch), so the row and its indexes commit atomically on that Region. MVCC uses the same CF layout for both; only the user-key prefix changes.

Reads. PK lookup Gets t42_r{handle}. A query on an indexed column scans t42_i{index_id}_… (§3.2 Example B), then Gets the record key for each handle.

2.5 LSM-tree

An LSM-tree (log-structured merge-tree) stacks immutable sorted runs (MemTable, SST levels) instead of updating disk pages in place. The same user key may appear in several runs; a read merges them and keeps the newest live version by sequence number. The design trades cheap sequential writes for read amplification that leveling, blooms, and cache must bound.

Sequential writes

RocksDB targets workloads with many small random mutations (TiKV Raft apply and MVCC Puts). A classical B-tree turns each Put into read-modify-write of one or more pages and scattered fsync traffic. An LSM keeps the foreground write path sequential.

Devices deliver far higher throughput for large sequential transfers than for many tiny random writes. WAL + MemTable batching converts a random update stream into sequential appends on the critical path.

Order-of-magnitude write throughput factor (small random writes vs large sequential writes of similar total bytes; device-dependent):

The LSM write bet is strongest when many mutations share a WAL sync and Flush writes multi-MB SSTs: foreground time tracks sequential bandwidth, while update-in-place stays on random IOPS x RMW. On TiKV’s typical SSD/NVMe stores, expect several x hot-path write throughput from the sequential shape—not HDD’s hundredfold—unless sync policy collapses both designs to fsync latency.

That choice drives the rest of the LSM shape on the write side:

RocksDB’s default is a leveled LSM per column family: MemTable(s) above SST levels L0 … Ln.

Read performance

Writes defer sorting and merging; a point Get must search every generation that might hold the key, newest first: mem_ → imm_ → L0 SSTs → one candidate file per lower level. That is read amplification: more disk work per lookup than a B-tree that walks a fixed tree height.

A leveled LSM caps depth below L0: a cold Get touches roughly O(L0 files + num_levels) SST blocks, not the whole database. Compaction and flush tuning that keep L0 small are therefore read-latency tuning as much as write smoothing. TiKV MVCC adds engine snapshots on top; RocksDB itself filters by sequence number at each layer.

Write vs read tradeoff. Sequential writes buy throughput at the cost of write amplification (compaction rewrites data) and read amplification (multi-layer search). Leveled compaction, bloom filters, and block cache are the main levers that pull read cost back toward B-tree-like behavior while keeping the append write path. RocksDB also offers universal compaction for write-heavy shapes that accept higher read amp; TiKV engines typically stay on leveled defaults tuned per CF.

2.6 Version set

VersionSet / Version record which SST files belong to which level. Compaction and flush publish **VersionEdit**s through LogAndApply: update in-memory Version, append to MANIFEST, fsync, then install a new SuperVersion. The global DB mutex serializes much of that path; contention on LogAndApply is a known hotspot at large SST counts—TiKV’s operational history includes mutex-side optimizations and careful flush/compaction tuning.

3. Examples

The examples below follow one employees table from SQL through TiKV apply into kvdb, then a range query. Raft replication and full MVCC rules live in the TiKV post; SQL compile and Region locate live in TiDB architecture. Here the focus is what RocksDB stores and how a range scan walks the LSM.

3.1 Multi-column table: writes in kvdb

SQL schema (table_id = 42; column ids: id=1, dept_id=2, name=3, salary=4, created_date=5; index idx_hired on created_date has index_id = 1):

CREATE TABLE employees (
  id           BIGINT PRIMARY KEY,
  dept_id      BIGINT NOT NULL,
  name         VARCHAR(64) NOT NULL,
  salary       INT NOT NULL,
  created_date DATE NOT NULL,
  KEY idx_hired (created_date)
);

INSERT INTO employees (id, dept_id, name, salary, created_date) VALUES
  (1001, 10, 'Ada',   120000, '2024-01-15'),
  (1002, 20, 'Grace', 110000, '2024-03-20'),
  (1003, 10, 'Lin',    95000, '2024-02-10');

TiDB encodes each row as a record key plus a row value (column id / value pairs). Non-primary-key columns also get index keys when indexed:

After commit at commitTS = 500 (simplified), kvdb holds record and index entries (same MVCC CFs):

Prewrite would have briefly held lock CF rows at each startTS; Commit Deletes those locks and Puts the write rows above. TiKV applies the Commit batch as one WriteBatch on kvdb, so all CF updates for that command succeed or fail together—RocksDB’s per-batch atomicity.

On disk inside one CF, keys sort lexicographically: t42_r1001@400, t42_r1001@500, t42_r1002@401, …—the LSM property that makes range scans efficient.

TiDB INSERT … COMMIT
  → client 2PC (Prewrite / Commit) on Region leader
  → Raft replicate + apply
  → ApplyFsm WriteBatch on kvdb (per row):
       Put(write/default, t42_r1001@…, row bytes)
       Put(write/default, t42_i1_{2024-01-15}@…, →1001)
       Delete(lock CF, …)
       … (record + index keys for 1002, 1003)
  → DBImpl::WriteImpl: WAL append + mem_ insert per CF
  → later Flush → L0 SST; compaction merges levels

3.2 Range queries

Both examples use read_ts = 600. TiDB compiles a predicate into a half-open kv.KeyRange, locates Regions, and sends a Coprocessor scan to the leader. RocksDB sees only sorted byte keys in write / default CFs; MVCC and decoding sit above the engine (TiKV §4.2).

How a range scan walks the LSM

A range query is not one Get per row. TiKV opens a Iterator on a column family with ReadOptions::iterate_lower_bound = start and iterate_upper_bound = end, pins a SuperVersion (mem_ + imm_ + current Version), then:

Iterator::Seek(start)     -- first key >= start in global sort order
loop Iterator::Next()       -- advance in byte order
  until !Valid() or key >= end

RocksDB implements that as a MergingIterator: it k-way merges the active mem_, each table in imm_, every L0 SST whose key range overlaps [start, end), and at most one SST per level on L1…Ln whose file range overlaps the interval. The client sees a single sorted stream; internally each Next() may pull the next entry from whichever source currently has the smallest key.

So read cost for a range is roughly: (number of keys emitted in [start,end)) × (cost to merge versions across layers) plus sequential block reads as the iterator walks forward—not a random Get per row from scratch, but also not “one page” like a B-tree range scan on a single tree.

On write CF, keys include @ commitTS, so the iterator may emit several byte keys per user key (one per MVCC version). TiKV’s scanner groups by user key, picks the version visible at read_ts, then may Get default CF for row bytes. Example A emits six engine keys for three employees; Example B’s index scan emits fewer index keys, then one record Get per match.

Example A — range on primary key (id / table handle)

SQL:

SELECT id, dept_id, name, salary, created_date
FROM employees
WHERE id >= 1001 AND id < 1004;

The planner uses a TableScan on record keys (_r prefix) for table_id = 42:

start = encode_row_key(42, 1001)   -- t42_r1001
end   = encode_row_key(42, 1004)   -- t42_r1004  (exclusive)

Coprocessor TableScan [t42_r1001, t42_r1004)
  → Iterator over record keys in range (sorted by handle)
  → per key: MVCC Get on write/default → decode row columns
  → return rows to TiDB

LSM walk (Example A). Coprocessor bounds write CF to [t42_r1001, t42_r1004). Seek(t42_r1001) positions the merging iterator at the first key in range—possibly in mem_ if recent commits are not flushed, else in an L0/L1 SST holding employee rows. Each Next() moves forward in byte order through t42_r1001@…, t42_r1002@…, t42_r1003@… (multiple timestamps per handle), stopping before t42_r1004. Keys outside the prefix (t42_i1_…, other tables) never enter the merge because they fall outside [start, end). MVCC collapses versions → three logical rows; default CF Gets fetch column payloads.

Example B — range on index column (created_date)

SQL:

SELECT id, dept_id, name, salary, created_date
FROM employees
WHERE created_date >= '2024-02-01' AND created_date < '2024-03-01';

There is no record-key order by created_date. TiDB picks idx_hired (index_id = 1) and builds a range on index keys (_i prefix):

start = encode_index_seek_key(42, 1, encode('2024-02-01'))  -- t42_i1_{2024-02-01}
end   = encode_index_seek_key(42, 1, encode('2024-03-01'))  -- t42_i1_{2024-03-01}  (exclusive)

Index entries sort by encoded date, then handle. Only 2024-02-10 (Lin) falls in [2024-02-01, 2024-03-01):

Coprocessor IndexScan [t42_i1_{2024-02-01}, t42_i1_{2024-03-01})
  → Iterator on write CF with index bounds (same LSM walk as above)
  → per index key: MVCC → read index value (handle 1003)
  → IndexLookup: point Get record t42_r1003 (mem → L0 → L1… per §2.5)
  → return one row to TiDB

LSM walk (Example B). Phase 1 is the same Seek / Next loop, but bounds are on t42_i1_* keys. Seek(t42_i1_{2024-02-01}) merges mem_, imm_, and every overlapping SST; Next() walks index keys in date order. Only t42_i1_{2024-02-10} lies in [2024-02-01, 2024-03-01)—Ada and Grace index keys sort outside the interval and are never emitted. Phase 2 is a **point Get on record t42_r1003: that lookup walks mem_ → imm_ → L0 → L1… for a single key (point-read path in §2.5), not another full range scan.

Compare A vs B

Uncommitted rows at read_ts still follow the same lock / write rules as in Example A.

3.3 Crash and recovery (same example)

If the store process dies after WAL records the Commit WriteBatch but before Flush, DB::Open replays WAL into MemTables; the three employees rows remain visible after recovery because batch atomicity replays all CF Puts together. If apply never reached kvdb (Raft not committed), neither SQL nor RocksDB shows the rows—consensus sits above the engine.