TREE LOCKをdeadlock-freeに保つ5つの条件
TREE系のindexやODBの継承関係をもつテーブル等、木のデータ構造を持つオブジェクトをロックする方法としてTREE LOCKという方法がある
単純にオブジェクト全体をロックするよりも、このロックを使ったほうがパフォーマンスが良い場合がある。
TREE LOCKのプロトコルは以下のルールに従う必要がある。
TREE LOCKが従うべき5つのルール
- 1.要素Xにアクセスする前に必ずxをロックすること
- 2.他のトランザクションがロックしていない時のみXのロックを確認できる
- 3.ロックしたい要素xが木の根でない場合、必ず親の要素をロックすること(根→葉の方向でロックが進む)
- 4.あるトランザクションがXを解放できるのはXに関する処理が全て終わったあとのみ
- 5.あるトランザクションがXを解放後、再びXのロックを確保できない。
TREE LOCKではロック順が必ずroot→reafの順番に進む。例えば上記の図で23の要素が欲しい場合は
al(50) al(17) al(23)
の順番にロックを獲得し、解放する時はその逆で実施する。※al : acess lock
このルールに従った場合、木の中ではdead-lockが発生しなくなる。*1 なぜなら
T1→T2→...→T1
というサイクルが発生したと仮定すると、前のT1ですでにrootのlockが完了しているので、後ろのT1はlock待ちにならないからである。
TLのメリットは2PLよりもロックを早く解放することができることである。ただしこれはトランザクションマネージャーがロック解放対象のノードが不要になったタイミングを検知、通知できる場合のみである。不要確定時の通知が難しい場合、ロックの解放はトランザクションの終了時になる(=S2PL)
参考
- CC本読み会第13回でのディスカッション*2
- Concurrency Control and Recovery in Database Systemsの3.13 TREE LOCKINGより
- 画像の出典:https://bs.wikipedia.org/wiki/Datoteka:AVLtreef.svg
Concurrency Control and Recovery in Database Systems
- 作者: Philip A. Bernstein,Vassos Hadzilacos,Nathan Goodman
- 出版社/メーカー: Addison-Wesley
- 発売日: 1987/02/01
- メディア: ハードカバー
- この商品を含むブログを見る
