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 804: GC and Compaction Filter

TXN 404 introduced TiKV's MVCC history. When a key is updated, TiKV adds a new committed version instead of immediately overwriting the old one. Older transactions may still need the earlier versions.

Once no permitted transaction can access an old version, retaining it only consumes storage and adds work to RocksDB compaction. This chapter explains how TiKV decides that an MVCC version is no longer needed and how it eventually removes that version from RocksDB.

GC Lifetime and the Safe Point

TiDB begins with a retention policy called the GC lifetime. It calculates a target timestamp by subtracting that lifetime from the current time. Intuitively, versions older than that point have aged out of the normal retention window, so TiDB can begin considering them for removal.

The target is not guaranteed to become the new GC safe point. TiDB can advance it only as far as the oldest active transaction and every registered service safe point allow. A service safe point is a retention boundary registered by a component, such as backup, that still needs older history.

Before publishing the resulting GC safe point to PD, TiDB scans the full key space Region by Region and resolves locks from transactions older than that point. If scanning or resolving fails, the GC run stops.

After lock resolution succeeds, TiDB saves the safe point in the shared record used by TiDB instances to refresh their safe-point caches. It waits for those caches to refresh, then publishes the same timestamp to PD. TiKV uses the PD value as the boundary for reclaiming old MVCC history:

GC lifetime produces a candidate
              |
              v
limit it by active transactions and service safe points
              |
              v
resolve older transaction locks across all Regions
              |
              v
refresh TiDB safe-point caches
              |
              v
publish the GC safe point to PD
              |
              v
TiKV may reclaim obsolete MVCC history

The GC safe point defines the history that TiKV must continue to support:

snapshot_ts < GC safe point   -> historical read is no longer supported
snapshot_ts >= GC safe point  -> read must still return the correct result

The GC lifetime proposes how much history to retain. The actual GC safe point may be earlier when an active transaction or another service still needs older versions.

Which Versions Can Be Removed

For every key, TiKV keeps all committed versions newer than the GC safe point. It then examines the newest Put or Delete at or below the safe point.

If that version is a Put, TiKV must keep it. A supported read may still need its value:

write CF for key k, GC safe point = 60

commit_ts 80 -> Put C   keep: newer than the safe point
commit_ts 50 -> Put B   keep: value visible at timestamp 60
commit_ts 20 -> Put A   remove: hidden by the version at 50

The Put at timestamp 50 is the boundary version. A read at timestamp 60 returns B, so removing that version would change a supported read.

A Delete has a different result:

write CF for key k, GC safe point = 60

commit_ts 80 -> Put C   keep: newer than the safe point
commit_ts 50 -> Delete  remove after older history is gone
commit_ts 20 -> Put A   remove: hidden by the Delete

At timestamp 60, the key does not exist. Once the older Put has also been removed, deleting the Delete record preserves that result: finding no version still means that the key does not exist.

This is the central GC rule:

boundary Put    -> keep it; remove older history
boundary Delete -> remove it after removing all older history

Here, Delete means a TiKV MVCC record in the write CF. It is not a RocksDB deletion marker.

TiKV can apply these rules through two cleanup paths. The traditional path scans keys explicitly. The compaction-filter path, which is enabled by default, removes obsolete versions while RocksDB is already compacting the write CF.

Traditional GC

The direct GC path scans the keys in a Region. For each key, it walks the committed versions in the write CF and applies the rules above.

Removing an old Put may require changes to two column families. The write CF contains the MVCC record. If the value was too large to embed in that record, the actual value is stored in the default CF under the transaction's start_ts:

write CF:   delete (key, commit_ts)
default CF: delete (key, start_ts)   if the value is stored separately

TiKV adds both deletions to the same GC mutation batch. A short value embedded in the write record has no matching default CF entry to remove.

scan Region keys
        |
        v
inspect each key's MVCC history
        |
        v
keep the required boundary Put
and remove obsolete versions
        |
        v
write the corresponding CF deletions

This path deliberately visits the Region's keys and produces writes whose only purpose is cleanup.

GC During Compaction

ROCKSDB 605 described how compaction reads existing SST files and writes their surviving entries into new files. Because compaction is already reading the write CF, TiKV can inspect MVCC versions during the same pass. The component that makes this keep-or-remove decision is a compaction filter.

For each key, the filter keeps every version newer than the GC safe point. When it reaches the first Put at or below the safe point, it keeps that boundary version and removes the older records:

write CF compaction, GC safe point = 60

80 -> Put C   keep
50 -> Put B   keep
20 -> Put A   omit from the compaction output

Compaction processes one column family at a time. When the filter removes a Put whose value is stored in the default CF, it uses the start_ts in that Put to add a deletion for the matching value to a separate write batch. The new write CF SST contains only the surviving write records; the default CF deletion is applied through that batch.

Unlike direct GC, this path does not scan every Region immediately. It removes a version when the SST file containing that version participates in compaction. The cleanup reuses work RocksDB was already doing, but its timing follows compaction.

Removing a Boundary Delete

The compaction filter needs one extra rule for Delete records. Consider a compaction that has reached the boundary Delete but is not working at the bottom of the LSM tree:

current compaction input
  commit_ts 50 -> Delete

deeper level
  commit_ts 20 -> Put A

If the filter removed the Delete while the older Put remained in a deeper level, a later read could find A again. The deleted value would appear to return.

TiKV therefore keeps the boundary Delete until cleanup reaches the bottommost level. At that point there is no deeper level that can still hold an older version. TiKV can arrange a per-key GC pass that removes the Delete, the older write records, and any values they reference in the default CF.

boundary Delete reaches bottommost compaction
                    |
                    v
no older version can remain below it
                    |
                    v
remove the complete deleted history

The GC safe point separates supported history from obsolete history. A boundary Put remains because a supported snapshot may still read its value. A boundary Delete can disappear only together with everything it hides.

Traditional GC finds that history by scanning keys directly. The compaction filter reaches the same result as RocksDB naturally rewrites the write CF. With those rules in place, TiKV can reclaim old MVCC data without changing the result of any supported read.