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

僕と MySQL と時々 MariaDB

CMU Database Systems をひたすら追っていく ~17 Two-Phase Locking~

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

はじめに

今日は Two-Phase Locking について。

Transaction Locks

ラッチというのは以前にも何度か解説していると思うがこれからはロックの話。
ロックには２つ種類がある。

またトランザクションは以下のようにロックマネージャーを用いて実行・管理される。

  • トランザクションはロックマネージャにロックを要求する
  • ロックマネージャは要求のあったオブジェクトに対するロックの状態に基づいて要求を許可、ブロックする
  • トランザクションはロックを不要になった段階で開放する
  • ロックマネージャは内部のロックテーブルを更新し、待機中のトランザクションにロックを付与する。

Two Phase Locking

Two Phase Locking (2PL) は悲観的な同時実行制御プロトコルであり、トランザクションがその場でDB内のオブジェクトにアクセスできるかどうかを決定する。
トランザクションが競合した場合は、2PL で十分に対応できる。しかし、トランザクションが ABORT し、他のトランザクションをロールバックする必要がある場合は無駄な処理が生まれる。
以下の手順を具体的にはとる。

Phase1: Growing
  • 各トランザクションはロックマネージャから必要なロックを要求する
  • ロックマネージャはロック要求を許可または拒否する。
Phase2 Shrinking

Strict Two-Phase Locking

S2PL ではトランザクションが終了時のみロックを開放する。2PL のように Shrinking、縮小フェーズが存在しない。
トランザクションによって書き込まれた値がそのトランザクションが終了するまで他のトランザクションによって読み取られたり、書き込まれたりしない場合スケジュールが厳密となるため有用となる。
このアプローチではカスケードアボートが発生せず、ABORT された場合はトランザクションの変更を元に戻すだけでよい。

2PL Deadlock Handling

Two-Phase Locking ではデッドロックを解消するために検出する場合と防止する２つの方法がある。

検出するアプローチ

DBMS はノードをトランザクションとし、トランザクションが他のトランザクションがロックを開放するのを待っている場合そのベクトルをエッジとして待機グラフを作成する。
デッドロックが検出されると、いくつかの手法を用いてそれを解消する。

この開放するトランザクション(victim) は以下のように選択される。

  • 最も古い or 新しいタイムスタンプを持つもの
  • 進行状況
  • すでにロックされているアイテムの数。
  • ロールバックする必要のあるトランザクション数
  • 過去に再開された回数

防止するアプローチ

トランザクションがロックを取得しようとしたとき、そのロックが別のトランザクションによって保持されている場合はタイムスタンプによる優先度によってデッドロックを防止する挙動を取る。
これによってロックは待機したあと許可されるのは１つになるためデッドロックが発生しない。
以下の手法で防止する。

  • Wait-Die： T1 の優先度が高い場合は、T1 は T2 を待つ。それ以外の場合は T1 を ABORT する
  • Wound-Wait: T1 の優先度が高い場合は T2 は中止される。それ以外の場合は T1 は待機する

おわりに

次は MVCC