# CMU DB 18. Timestamp Ordering Concurrency Control
tags: CMU DB
授業
timestamp ordering concurrency control
timestamp ordering(t/o)とは楽観的な並行制御プロトコルのクラス.DBMSはトランザクションの衝突が稀だと仮定する.
timestampを利用して,直列性を決定する.
各トランザクションは単調に増加する一意な固定のtimestampを割り当てられる.
複数のtimestamp割り当て実装の戦略として
- system clock
- logical coutner
- hybrid
がある.
basic timestamp ordering(basic t/o)
read/write timestampで全てのDBのオブジェクトはタグ付けされる.
optimistic concurrency control(occ)
もし,トランザクションの衝突がまれならばそうでない場合を最適化した方が良いでしょうというのがこの考え方です.
DBMSは各トランザクションにprivate workspaceを作る
- 全ての変更はworkspaceに適用される
- どんな読まれたオブジェクトもworkspaceにコピーされる
- 他のどんなトランザクションも,private workspace内の別のトランザクションによって作られた変化を読むことは出来ない
トランザクションが終わった際,DBMSはトランザクションのworkspaceのwrite setと他のトランザクションが衝突していないかを比較する.もし,衝突がなければ,write setはglobal DBへとインストールされる.
OCCトランザクションの段階
- read phase
- トランザクションのread/write setを追い,private workspace内のwritesを保管する
- validation phase
- write phase
- validationに成功した際,private changesをDBに適用する.そうでなければトランザクションを中断し,再開する.
問題として以下のようなものがある.
partition-based t/o
トランザクションがOCCで終了した時,全ての並行しているトランザクションと衝突していないかを調べるのは遅く,代替手段がある.
DBをバラバラな部分集合にすることをpartitions(shardsとも言う)と呼ぶ.同じpartition内で走っているトランザクションについてだけ調べる.
単一のlockによってpartitionは保護されている.
問題としては以下のようなものがある.
- 早いための条件は以下の通り
- プロトコルが働く条件は以下の通り
感想
トランザクションを高速にするには色々と工夫が必要なのだなぁ〜