この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 22 日の記事です。
はじめに
今回は MySQL や PostgreSQL でも採用されている 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 から開放可能な物理バージョンを削除する必要がある。
これには２つのアプローチがある。
Tuple Level Garbage Collection
- Background Vacuuming: 個別のスレッドが定期的にテーブルをスキャンし、開放可能なバージョンを探す
- Cooperative Cleaning: ワーカスレッドはバージョンチェーンを検索するときに再利用可能なバージョンを検索する
おわりに
次はログ周りだったかな