Multi-version Concurrency control における GC の話

データベース・システム系 Advent Calendar 2023 の 5 日目の記事です。あたりまえのように遅れてしまいました。すみません。

本記事では MVCC (Multi-version Concurrency Control) 向けの GC (Garbage collection) 技術の紹介をします。

概要

MVCC とは、ひとつのデータ単位(ここでは Record とよぶことにします)につき、内部的に複数の版 (Multi-version) を管理することで、同一 Record への並行アクセスの機会を増やして並行性を高める技術です。内部的に単一の Version しか持たない Single-version CC (SVCC) よりも、並行性を高めることが可能です。ただし、MVCC においても外部からは単一の Version しか存在していないように見えることを想定します。

MVCC ではデータを更新するたびにどんどん Version が増えていくので、In-Memory DBMS では、放っておくと外部から見たデータ量が増えていなくてもメモリが枯渇してしまいます。そこで、使わなくなった Version を消す操作、すなわち GC が必要となります。

Disk-based DBMS の話も後で少ししますが、本記事では主に In-Memory DBMS での GC の話をします。In-Memory DBMS では永続化のため(要するに WAL)の Disk I/O を CC とはほぼ切り離せるので、トランザクション処理スループットを大きくすることができ、そのため GC への要求もよりシビアになります。要するにさっさと消さないといけないということです。

基本的な考え方

オリジナルの出典はどこか分かりませんが、後述する Cicada 論文に基本的な考え方が示されています。それを私なりに説明します。

各 Version にタイムスタンプ¹ がつけられている前提を置きます。Version $v$ のタイムスタンプを $ts(v)$ と置きます。過去から未来に生成される全ての Version 集合を $V_{all}$ と置きます。ある時刻 $t$ ² において動作中、または、$t$ 以降に開始される、どのトランザクションからもアクセスされない Version 集合を $V_t^{inactive}$ と置きます。また、そのとき各 Record について、最新のタイムスタンプがついている Version の集合を $V_t^{latest}$ と置きます。また、$t_{gc} < t$ であるような $t_{gc}$ を考え、$V_{gc} := \{v \in V_{all} \setminus V_t^{latest} \mid ts(v) < t_{gc} \}$ と置きます。このとき、$V_{gc} \subset V_t^{inactive}$ であることを保証できる、出来るだけ大きな $t_{gc}$ を使って、対応する $V_{gc}$ を GC 対象とする、というのが基本的な考え方です。$t$ が進む度に、$t_{gc}$ および $V_{gc}$ のサイズも単調増加することが想定されます。つまり、各 Version につけるタイムスタンプは、多少実時間の順序と前後しても問題ないですが、そこから著しく逸脱し、$t_{gc}$ や $V_{gc}$ のサイズが時間と共に単調増加しないような系では期待通りに動かないということです。各 Version の状態(Committed か Aborted か、それに至る途中の状態か)などの細かいことを考慮しはじめると説明がどんどん細かくなってしまうので、ばっさり省略しました。詳細を考える必要のある方はそのあたりをよしなに補完してください。後述する Steam 論文において、$t_{gc}$ は Watermark として機能します。

現実のシステムにおいて、$V_t^{inactive}$ を正確に把握することは困難か、可能だとしてもオーバーヘッドが大きすぎて現実的ではありません。一方で、(妥協が入った) $t_{gc}$ を求めることは可能であり、そのオーバーヘッドも大したものではないため、それを使って GC しましょう、ということです。

この、基本的な考え方に沿った上で、現実的に残る問題は、各 $t$ の時点においてできるだけ大きい $t_{gc}$ をいかに把握するかということです。また、$t_{gc}$ を更新する頻度も重要です。$t_{gc}$ が実際よりも小さかったり、その把握する頻度が小さければ、本来であればその場で GC できた Version を先送りすることになってしまい、メモリを圧迫する要因となります。

Cicada

Cicada: Dependably Fast Multi-Core In-Memory Transactions. (2017) ACM Digital Library

Cicada 論文には Rapid garbage collection (Rapid GC と呼びます) という提案が含まれています。Rapid GC は $t_{gc}$ の更新をできるだけ高頻度に行うことが主な内容になっています。Cicada は MVTO ベースのプロトコルであり、各トランザクションにタイムスタンプを割り当て、トランザクションが書く Version にも同じタイムスタンプを割り当てます。各ワーカースレッドは単調増加でトランザクションにタイムスタンプを割り当て、各スレッド毎に完了したトランザクションタイムスタンプの最大値を管理しています。これらのタイムスタンプの中で最小のものを $t_{gc}$ として、頻繁に再計算することにより、出来るだけ GC の実行が先送りされる Version を減らす戦略です。この再計算のための構造は、CPU キャッシュの特性を考慮しており、オーバーヘッドが出来るだけ小さくなるように配慮されています。

Rapid GC は基本的な考え方を踏襲した手法であるため、$t_{gc}$ よりも新しい領域の Version は GC 対象として最初から考慮されません。たとえば、寿命の長いトランザクションがひとりいるだけで、$t_{gc}$ が更新できなくなってしまい、そのトランザクションが生きている間 GC がまったく動かない状況が発生し得るのです。その詳細については、CCBench 論文その他で言及されています。

An analysis of concurrency control protocols for in-memory databases with CCBench. (2020) PVLDB

Steam

Scalable Garbage Collection for In-Memory MVCC Systems. (2019) PVLDB

この論文で提案されている Steam という手法は、より積極的に不要な Version を GC していくアプローチをとっています。Snapshot isolation や MVTO などの特定の MVCC を前提として動作します。具体的には、動作中のトランザクション達はそれぞれひとつの Snapshot (Record ひとつに対してひとつの Version が対応)しか読まない性質を利用します³。Snapshot isolation や MVTO は読むべき Snapshot を最初に決めてしまう(Snapshot に対応するタイムスタンプを割り当てます)性質を持っています。読まれる対象の Snapshot を表すタイムスタンプのリストを管理し、Snapshot と Snapshot の間に存在する Version $v$ は、$t_{gc} < ts(v)$ であっても積極的に GC します。これらのプロトコルを前提とすると、最早誰にも読まれないという点で $v \in V_t^{inactive}$ であることが保証できるからです。

その他の関連論文

上記で紹介した論文達から辿った、最近の In-Memory DBMS 向けもしくは関連する GC の研究をいくつか貼っておきます。今のところ私はさらっと眺めただけですが、興味のある方は読んでみてください。

• MV-RLU: Scaling Read-Log-Update with Multi-Versioning. (2019) ACM Digital Library
  • DBMS ではありませんが、Read-Log-Update (RLU) 構造を Mutli-version 化するという手法で、その GC についても提案手法に含まれています。
  • さらっと眺めた限り、GC のアプローチは「基本的な考え方」と同様に見えました。
• Multiversion Concurrency with Bounded Delay and Precise Garbage Collection. (2019) ACM Digitgal Library
  • こちらも DBMS ではないですが、Reference counting を使って正確な GC を行うというアプローチです。これまで紹介してきた GC アプローチに対して、Reference counting により、不要になった直後に遅延なく解放できるメリットと、CPU キャッシュが汚れるデメリットのトレードオフがあると考えられますが、果たして……。
• Long-lived Transactions Made Less Harmful. (2020) ACM Digital Library
  • Steam のような積極的な GC を、Disk-based DBMS に対して行うための仕組み vDriver を提案しています。刈り込みの仕組みはさらっと眺めた限りでは同じようですが、Disk 上の構造を工夫し、不要な Version 達をまとめて GC できるようにすることで性能向上を図っていると思われます。
• NWR: Rethinking Thomas Write Rule for Omittable Write Operations. (2020) arXiv
  • 今時の In-Memory CC に Thomas Write Rule を適用するとどうなるか、という論文です。Thomas Write Rule とは、読まれないなら書かなきゃいいじゃない、というコンセプトで、一定の条件を満たした Write 操作を省略する手法です。MVCC の文脈では、Version をそもそも作らないということになります。理論面では、Blind write (同一 Record を先だって読まずに上書きする操作) が存在することが必要条件になりますので、SQL を前提とする DBMS では採用しづらいのですが、可能性を感じます。
• EPO-R: An Efficient Garbage Collection Scheme for Long-Term Transactions. (2022) IEEE Xplore
  • EPO-R は Steam の派生手法で、Steam が Record write 時、すなわち Version を追加するときに GC をトリガするのに対し、Record read 時に GC をトリガする点が異なります。
• In-Page Shadowing and Two-Version Timestamp Ordering for Mobile DBMSs. (2022) PVLDB
  • MVCC ではありますが、Version 保持数を 2 つに制限することで GC の必要性を回避している点が特徴的です。

Disk-based の話

MySQL InnoDB などは、Multi-version が Disk 上でメンテナンスされていて、古い Version は Undo log として機能するらしいんですね。このあたりを読む限りでは、そう読めます。Multi-version なので、新しい Version は古い Version とは別に確保され、トランザクションが Commit するまでは古い Version が永続化状態で存在する必要があります。トランザクションが Abort (Rollback) する可能性が残っている間は、古い Version への参照を指し直す(Undo)ことができる必要があるからです。

それとは別に、(MySQL InnoDB の) Repeatable read における Snapshot を提供するためにも古い Version は使われます。これは、In-Memory DBMS においても同じなので、GC 事情も同じです。つまり、今動いている、もしくは未来に動くトランザクションが読まないことが確定している Version は不要であるということです。

このように、古い Version には Undo log としての役割と Snapshot の部品としての役割のふたつがあるので、ふたつの役割をどちらも終えた時点で GC 対象になるわけです。GC のロジックは多少複雑になれど、Cicada がやっていることと同様だと思います。

Steam や EPO-R のように、Snapshot の合間でもう読まれることはない Version を消すことも理論的には可能でしょうけれど、素直にやろうとすると、永続化されている状態で同様の操作を行う難易度は上がるということと、細粒度の Disk 領域の再利用を頑張るのが割に合わない気がするので割に合わない……と思っていましたが、この記事を書くにあたり vDriver 論文の存在を知りました。vDriver は、割に合うように Disk 側のデータのまとめ方を工夫したものだと理解しています。

まとめと感想

本記事では主に最近の In-Memory DBMS での MVCC 向けの GC 技術の紹介をしました。MVCC は理論的には無限の Version を保持できる仮定の元で議論されることが多く、Version の GC は各プロトコルの設計に任されることが多いのですが、アカデミアでは Multi-version であることによるスケジュール空間の広さを享受しつつも Version の生成やアクセスのオーバーヘッドをどう減らすかに注目している研究が多かったところに、GC を焦点として取り上げる研究は徐々に増えてきた印象です。まず GC のことを考えない CC プロトコルがあって、その上で GC を考える、という態度では In-Memory DBMS の MVCC は実用しづらいと思います。スケジュール空間の広さとメモリ使用量のバランスを取る視点を持ち、踏み込んだ GC を行う CC プロトコルを考えるアプローチが現実的だと思います。具体的には、アクセスする Version を制限することが考えられますが、紹介した 2VTO が正解かどうかは、議論の余地があるとは思います。また、NWR のようにもっと積極的に Version を減らすアプローチも存在します。個人的には、In-Memory DBMS においては、Reference counting が意外と悪くないのではないかと考えてはいます。それではみなさんごきげんよう。

1. 物理、論理どちらでも良いですが、同一 Record についての Version が全順序となるようなものです。物理時刻を使う系もあるでしょうし、カウンタを使う系もあるでしょう。 ↩

2. 簡単のため物理時刻とタイムスタンプは対応関係があるものとして同一視していることに注意してください。 ↩

3. MVTO の場合、Snapshot だと思って対象 Record のとある Version を読んだ後に、新しい Version が挿入されることで、読むべきだった Snapshot が更新されてしまうことがあります。その場合、時刻に関係なく、Snapshot に対応するひとつの Version が存在するとはいいづらいですが、Version 挿入前後で、それぞれ対応するひとつの Version が存在する、とはいえます。GC の観点で大きな問題はありません。 ↩