# CMU DB 19. Multi-Version Concurrency Control
tags: CMU DB
授業
multi-version concurrency control
multi-version concurrency control(MVCC)とは単なる並行制御プロトコルよりも大きな概念．DBMSのデザインと実装の全ての側面を含む．
DBMSはDB内の単一の論理オブジェクトの複数の物理的なversionを保持している．
- トランザクションがオブジェクトに書き込む時，DBMSはそのオブジェクトの新しいversionを作る
- トランザクションがオブジェクトを読む時，トランザクションが始まった際に存在していた最新のversionを読む
元々のMVCCプロトコルはMITの博士論文で提案された．
｢書き込み側が読み込み側をブロックしないし，読み込み側が書き込み側をブロックしない｣という主な特徴がある．
読み込み専用トランザクションはlockを獲得せずに一貫したsnapshot(the state of a system at a particular point in time.)を読み込むことが可能．timestampsは可視性を決定するのに使われる．
multi-versioned DBMSはsnapshotにおけるDBを読み込むことが可能なクエリに対応可能である．
4つの重要なMVCCの設計決定
- concurrency control protocol(t/o, occ, 2pl)
- version storage
- garbage collection
- index management
version storage
どのようにDBMSが論理オブジェクトを異なる物理versionに保管するか．
DBMSは論理tupleにつきversion chainを作るためにtupleへのポインタを使う．
これはDBMSが特定のトランザクションに見えるversionを探すため．indexは常にchainの先頭．スレッドは見えるversionが見つかるまでchainを走査する．異なるstorage schemeごとにそれぞれのversionでどこに何を保管するを決める．
以下の方法がある．
- append-only storage
- 新しいversionは同じtable空間に付け加えられる
- oldest-to-newest(o2n)
- chainの最後に新しいversionを付け加える．
- 検索には全てのchainの走査が必要
- newest-to-oldest(n2o)
- 上の逆
- time-travel storage
- 古いversionは別個のtable空間にコピーされる
- delta storage
- 変更されたattributeの元々の値は別個のdelta record空間にコピーされる
garbage collection
DBMSは継続的にDBから取り戻せる物理的なversionを取り除く必要がある．
- tuple level garbage collection
- 直接tupleを調べることで古いversionを見つける
- transaction level
- それぞれのトランザクションはそれ自身の読み書きセットを追う．
index management
全てのprimary key(pkey) indexはいつもversion chainの先頭を指す．
感想
実装がめんどくさそうだと思った()
