それが僕には楽しかったんです。

ミドルウェアとかやってます

CMU Database Systems をひたすら追っていく ~19 Multi-Version Concurrency Control~

この記事は「けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 22 日の記事です。

はじめに

今回は MySQLPostgreSQL でも採用されている MVCC について。

Multi-Version Concurrency Control

これは単に同時実行制御に収まらない広い概念として存在している。過去10年間に実装されたあたらしい DBMS では最も広く利用されているらしい。
これが何かというと、DBMS は DB 内の単一論理オブジェクトにたいして複数の物理バージョンを維持する。
具体的には以下のような処理を行う。

Key Properties

書き込みは読み込みをブロックしない。読み込みも書き込みをブロックしない。
読み取り専用トランザクションはロックを取得せずに一貫したスナップショットを読み取る。
DBMS がスナップショットで実行できるクエリをサポートする。

Version Storage

DBMS が論理オブジェクトの物理バージョンを持つ方法のこと。具体的にはポインタフィールドを使用して論理タプル毎にバージョンチェーンを作成する。
これによって DBMS は実行時に特定のトランザクションから見えるバージョンを見つけることができる。
インデックスは常にチェーンの先頭を指し、スレッドは読み取るべきバージョンを見つけるまでチェーンを検索する。

Append Onky Storage

新しいバージョンは同じテーブルスペースに追加される。

  • Oldest To Newest: 新しいバージョンをチェーンの最後に追加する
  • Newest To Oldest: チェーンの先頭は最新となるため高速に検索できるが、インデックスはバージョンごとに更新する必要がある。
Time Travel Storage

古いバージョンは別のテーブルスペースにコピーされる。

Delta Storage

変更された属性の元の値が別のデルタレコードスペースにコピーされる。

Garbage Collection

DBMS は時間の経過とともに DB から開放可能な物理バージョンを削除する必要がある。
これには2つのアプローチがある。

Tuple Level Garbage Collection
  • Background Vacuuming: 個別のスレッドが定期的にテーブルをスキャンし、開放可能なバージョンを探す
  • Cooperative Cleaning: ワーカスレッドはバージョンチェーンを検索するときに再利用可能なバージョンを検索する
Transaction Level

トランザクションは独自のRWセットを追跡する。トランザクションが完了すると GC は回収するタプルを特定することができる。
DBMS は終了したトランザクションによって作成された全てのバージョンが不可視になるタイミングを決める。

おわりに

次はログ周りだったかな