このブログは、siddontangの"How We Optimize RocksDB in TiKV — MVCC GC Optimization"の抄訳です。翻訳はGeminiの翻訳をベースに、@bohnenが担当しました。
TiKVは、GoogleのPercolatorモデルに基づいて分散トランザクションを実装しています。
すべてのデータは複数のバージョンを持つ可能性があり、TiKVは、グローバルに一意で単調増加するタイムスタンプを生成する集中型タイムスタンプオラクル（TSO）を使用してタイムスタンプを割り当てます。これらのタイムスタンプは、クラスタ全体でのMVCCの読み取りと書き込みのバージョン識別子として機能します。
これらのMVCCバージョンをRocksDB内に保存するために、TiKVはタイムスタンプをキー自体にエンコードし、レコードのバージョンごとに一意のキーと値のペアを作成します。
現在のRocksDBは、独自のMVCCメカニズムを活用するためにキーごとのタイムスタンプの提供をサポートしていますが、TiKVが最初に設計されたときにはこれを利用できませんでした。そして現在でも、TiKVのMVCC形式を変更することはリスクが高く、不必要です。そのため、TiKVはRocksDBとは独立して独自のMVCC形式を維持し続けています。
これにより、運用上の大きな課題が生じます。
TiKVはどのようにして古いMVCCバージョンを効率的にガベージコレクション（GC）できるのでしょうか？
GCが以前どのように機能していたか、なぜそれが問題になったのか、そしてRocksDBのコンパクションフィルタを使用してどのように解決したか（そして、後のTiDB Xでの新しいアプローチ）について見ていきましょう。
古いGCモデル：ブルートフォーススキャン（力任せのスキャン）
歴史的に、TiKVは各TiKVノード内で実行されるGCスレッドに依存していました。
- PD（Placement Driver）がGCセーフポイントのタイムスタンプをブロードキャストします
- 各TiKVノードがキースペース全体をスキャンします
- セーフポイントより古いすべてのバージョンが削除されます
これは正しく単純な方法でしたが、いくつかの深刻な問題を引き起こしました。
1. バッチスキャンがRocksDBに負荷をかける
大量のデータブロックをスキャンして削除すると、重い読み取り/書き込み負荷が発生し、レイテンシのスパイク（急上昇）を引き起こして、最前線のワークロードに影響を与える可能性があります。
2. 小さなバッチは負荷を軽減するが、ゴミが蓄積する
影響を軽減するために、GCは小さなバッチで実行されますが、これにより以下の問題が発生します。
- 古いバージョンが長期間残存する
- ディスク使用量が不必要に増加する
- RocksDBが多くの古いMVCCエントリをスキップしなければならないため、読み取りが遅くなる
3. GCがフォアグラウンドI/Oと競合する
実際のワークロードへの干渉を避けるためにGCタスクを抑制（スロットリング）する必要があり、これによりクリーンアップがさらに遅れます。
TiKV内部でのブルートフォースGCはコストがかかりすぎることが明らかになりました。
そこで、私たちはRocksDBに助けを求めました。
RocksDBコンパクションフィルタの使用
RocksDBはコンパクションフィルタと呼ばれるメカニズムを公開しており、これによりアプリケーションはコンパクション中にキーと値のペアを保持するか破棄するかを決定できます。
これはMVCCに最適です。
- データがコンパクションされるにつれて、古いバージョンは自然に下のレベルに移動します
- コンパクションがSSTを書き換えるとき、GCセーフポイントより古いバージョンを削除できます
- GC作業は増分的かつ自動的になり、RocksDBのI/Oスケジュールに合わせて行われます
しかし、このアプローチには厄介な正確性の問題があります。
最下層（Bottommost-Level）の問題
TiKVはRocksDBをレベルコンパクションモードで使用しています。これは以下のことを意味します。
- 上位レイヤーは下位レイヤーにコンパクションされます
- 初期のコンパクションでは、キーのすべてのバージョンが見えるわけではありません
- 古いバージョンがより深いSSTにまだ存在している可能性があります
したがって、あるバージョンがGCセーフポイントより古いことがわかっていても、上位レベルのコンパクション中にそれを安全に削除することはできません。
もしバージョンを早く削除しすぎてしまい、より古いバージョンが下位レベルに存在している場合、将来の読み取りが不正確になる可能性があります。
これを解決するために、TiKVとRocksDBは以下を導入しました：is_bottommost_level フラグです。
PR: https://github.com/tikv/rocksdb/pull/374
この追加機能は、現在のコンパクションがLSMツリーの最下層で行われているかどうかをコンパクションフィルタに伝えます。
TiKVでの使用方法
-
is_bottommost_level = trueの場合 → 下位に古いデータが存在しないため、tomestone（削除マーカー）と古いMVCCバージョンを安全に削除します -
is_bottommost_level = falseの場合 → 将来のコンパクションでの正確性を保証するために、古いバージョンを保持する必要があります
この単純に見えるフラグが、重要な最適化を可能にします。
MVCC GCは、キースペース全体をスキャンすることなく、分散型でインクリメンタル、かつ低負荷なものになります。
TiDB X：新しいMVCC GCアーキテクチャ
TiDB X（次世代のTiDBアーキテクチャ）では、クラウドネイティブなインフラストラクチャにより適合するようにMVCCストレージを再設計しています。
重要なアイデアは以下の通りです。
最新バージョンを履歴バージョンから分離する。
次のようなイメージです。
- キーが更新されると → TiKVは新しいバージョンをメインのLSMツリーに書き込みます → 古いバージョンは別の「履歴スペース」に移動されます
- 履歴データはオブジェクトストレージ（S3）に保存されます：安価で耐久性があります
- リモートGCワーカーが定期的に履歴スペースを非同期でクリーンアップし、稼働中のワークロードに干渉しません
このモデルは、LSMツリーレベルのGCの複雑さを完全に回避します。理由は以下の通りです。
- フォアグラウンドの書き込みは最新バージョンのみを扱います
- 履歴データは分離され、整理されており、クリーンアップが安価にできます
- GCはS3上で事実上無制限のI/O帯域幅を持っています
- TiKVのLSMツリーはコンパクトで効率的な状態を保ちます
この設計により、MVCC管理が劇的に簡素化され、クラウドワークロードに対してGCがはるかにスケーラブルになります。
さらに詳しく知りたい方のために
RocksDBレベルのGCフィルタリング、最下層検出、そしてTiDB XのクラウドネイティブMVCC設計といったこれらの最適化はすべて、大規模スケールに合わせてRocksDBを適応させてきたTiKVの長い道のりを反映しています。
実際にどのようなものか興味がある方は、TiDB Cloudを無料で試してみてください。
数分でTiDBクラスタを実行し、システムを直接体験することができます。