Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

ROCKSDB 705: Titan

ROCKSDB 605 showed that compaction repeatedly moves key-value data through the LSM tree. When a value is large, moving it with every compaction consumes much more I/O than moving its key.

Titan reduces this cost by separating large values from the LSM tree.

The Cost of Large Values

Suppose the default CF contains a 1 MiB value:

(order:1001, start_ts) -> 1 MiB value

Without Titan, a flush writes both the key and the full value into an L0 SST file. Later compactions read the value from one level and write it again at another:

memtable
   |
   | flush: write the 1 MiB value
   v
L0 SST
   |
   | compaction: read and write the 1 MiB value again
   v
deeper SST levels

There is no fixed number of rewrites. It depends on the database size, the active levels, and future compactions. Even if the value never changes, it may be rewritten as the surrounding SST data moves toward the bottom level.

This repeated I/O is part of write amplification: the storage engine writes more bytes to disk than the application originally submitted.

Separating the Value

Titan is a RocksDB plugin for key-value separation. It stores large values in separate blob files and keeps small references to them in SST files.

The separation does not happen when TiKV first writes the value. The normal write path remains unchanged: RocksDB appends the full value to the WAL, then inserts it into the memtable.

Titan makes the decision when RocksDB builds an SST file during flush or compaction:

write
  |
  v
WAL -> memtable
          |
          | flush
          v
     value below threshold ------> key + value in SST

     value at or above threshold -> key + BlobIndex in SST
                                      |
                                      v
                                  value in blob file

A BlobIndex contains the blob file number and the location and length of the value inside that file. It is much smaller than the value itself.

Once a value has been separated, ordinary compaction can carry the key and BlobIndex through the LSM levels without rewriting the full value. The large value stays in its blob file.

TiKV uses Titan mainly for the default CF, where it stores transactional values that are too large to keep in the write CF record. By default, a newly created RaftKv cluster enables Titan and separates default CF values of 32 KiB or larger. The write and lock CFs do not create new blob records in the usual configuration.

Reading a Separated Value

A read still begins with the ordinary RocksDB lookup. The LSM tree tells Titan whether the selected entry contains the value itself or a BlobIndex:

look up key in the LSM tree
            |
            v
        BlobIndex
            |
            v
read the value from the blob file

The RocksDB snapshot still determines which LSM entries are visible. If the selected entry contains a BlobIndex, Titan follows it to the corresponding blob record.

Point reads can benefit from the smaller LSM tree, which leaves more cache space for SST indexes and filters. Range scans are different: after the iterator finds each key in an SST, it must fetch each separated value from a blob file instead of reading it from the SST's sequential data blocks. Separating more values can therefore increase range-scan latency.

Obsolete Blob Records

Titan writes records sequentially while building a blob file. Once the file is published, it is immutable: Titan does not overwrite or remove one record in place.

Suppose an SST entry initially points to value A and later points to value B:

SST entry -> BlobIndex(file 7, offset 100, length 1 MiB)
                              |
                              v
                         blob value A

later:

SST entry -> BlobIndex(file 12, offset 200, length 1 MiB)
                               |
                               v
                          blob value B

Once compaction removes the old BlobIndex, the record for value A is discardable. In TiKV's transaction data, the same thing happens after transaction GC deletes an old default CF entry and compaction removes its BlobIndex.

The space is not immediately returned to the filesystem. A blob file may contain both live and discardable records, and Titan cannot remove the file while any live record or RocksDB snapshot still needs it.

blob file 7

live records          40 MiB
discardable records   60 MiB

Titan tracks how much data in each blob file is still live. The fraction that is no longer live is its discardable ratio.

Blob Garbage Collection

When enough space in one or more blob files is discardable, Titan can select them for blob garbage collection, or blob GC. The default discardable-ratio threshold is 50%, although Titan may wait to collect enough files for a worthwhile GC batch.

Blob GC keeps the live records and removes the dead space:

select blob files with enough discardable data
                    |
                    v
identify their live records
                    |
                    v
copy live values into new blob files
                    |
                    v
replace their BlobIndexes in the LSM tree
                    |
                    v
retire the old blob files

Before replacing a BlobIndex, Titan verifies that the current LSM entry still points to the old blob record. If another write has updated the key in the meantime, GC leaves the newer value alone.

The old blob files become obsolete only after the new files are installed and the live LSM references have been updated. Their physical deletion can wait until no active RocksDB snapshot still references them.

The Tradeoff

Titan changes where the repeated work happens:

without Titan:
  compaction repeatedly rewrites keys and large values

with Titan:
  compaction rewrites keys and small BlobIndexes
  blob GC occasionally rewrites the remaining live values

The benefit is lower compaction write amplification for large values. The costs are slower range scans when many values are separated, blob-file space that is reclaimed later, and background I/O when blob GC runs.

The central idea is simple: keep the ordered keys in the LSM tree, move large values into blob files, and reclaim those files when enough of their data becomes obsolete. ROCKSDB 804 will return to the transaction GC and compaction-filter side of this lifecycle.