CMU 15-445 Two-Phase Locking Concurrency Control

  • dependency graph はスケジュールを与えられたときにserializeかどうかを判定する方法
  • クエリをserializeに実行するにはどうするか?
    • lock を使う
  • 2 Phase Locking
    • grow phaseとshrink phaseがある
    • 前者ではロックを取ること、後者は開放することしかできない
  • 2PL ではコミットあるいはロールバックの前にロックを開放できる
  • Strict 2 PL
  • 2PLはデッドロックを起こす
    • 解決には2種類ある
    • deadlock detection
    • deadlock prevention
  • deadlock detection
    • dependency graphを作成してループがあればアボートさせる
    • バックグラウンドでDGを作れば即応性はなくなるが、計算コストが下げられる
    • これはトレードオフなのでDBMSはチューニングパラメータを持っている
  • deadlock prevention
    • ロックまちが取れないときに、どちらかを殺す
    • DGを作る必要がない
    • 先に開始したほうを高プライオリティにする
    • ロック順序を一方後にするためのプロトコル
    • wait-die
      • 高プライオリティ側はロックを待てる
      • 低プライオリティは死ぬ
    • wound-wait
      • 高プライオリティはロックを持っている方を殺す
      • 低プライオリティはロックを待つ
  • ロック粒度
    • タプルだけでロックを扱うとたくさんのタプルを扱うとたくさんのロックを取らないといけない
    • ロックを階層化して低階層でのロックの数を減らす
    • Intention-Shared(IS), Intention-Exclusive(IX), Shared+Intention-Exclusive(SIX)を導入する
      • ISは下層で読むときに使う
      • IXは下層で書くときに使う
      • SIXは下層で良い書きするときに使う