データベース

Transaction Management / Distributed Database Management
データベース論
トランザクション・分散データベース編
森下真一
平成１４年度夏学期
Transaction Management / Distributed Database Management
トランザクション管理
参考文献
Jeffrey D. Ullman: Principles of Database and Knowledge-base Systems
Volume I, Computer Science Press, 1988. ISBN 0-7167-8158-1
Chapter 9 Transaction Management
Transaction Management / Distributed Database Management
トランザクション
データの読み出しや書き込みからなる処理の単位
並列に実行される
トランザクション管理の重要性
更新が必要なデータベース
座席予約システム
ダブルブッキングの回避
高速な処理時間よりもデータ更新の安全性を確保したい
読み出すことが中心のデータベース
統計データベース
WWWデータベース
並列な読み出し要求を数多く処理したい
Transaction Management / Distributed Database Management
例題
普通預金口座 A
T1: 1000円を振り込む
トランザクション
T2: 1000円を引き出す
トランザクション
READ A;
A := A + 1000;
WRITE A;
READ A;
A := A - 1000;
WRITE A;
スケジュール：時間軸に沿ってステートメントを並べた列
A
4000
T1:
T1:
T2:
T2:
READ A
WRITE A
READ A
WRITE A
5000
4000
順番に実行する
スケジュール
A
4000
T1:
T2:
T1:
T2:
READ A
READ A
WRITE A
WRITE A
5000
3000
Transaction Management / Distributed Database Management
例題
普通預金口座 A, B
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
READ A;
IF A >= 2000
A := A - 2000;
WRITE A;
READ A;
A := A + 5000;
WRITE A;
READ B;
IF B >= 5000
B := B - 5000;
WRITE B;
READ B;
B := B + 2000;
WRITE B;
実行スケジュール例
T1
T1
T2
T2
A
4000
2000
B
4000
6000
7000
1000
T2
T1
T1
T2
A
4000
9000
7000
B
4000
6000
1000
T2
T1
T2
A
4000
9000
7000
B
4000
abort
T2の影響を
元に戻す必要あり
Transaction Management / Distributed Database Management
トランザクションの原子性（Atomicity）の保証
整列スケジュールでは各トランザクションを
原子のような塊として実行する。
原子性を保証するとは、
各トランザクションを並列に実行するとき、最終結果が、
ある整列スケジュールの
結果と一致することを保証すること。
例
A
4000
9000
7000
B
4000
T2
T1
T2
abort
T2復帰 7000-5000
=2000
T1
6000
T1
T1
A
4000
2000
B
4000
6000
整列スケジュール
Transaction Management / Distributed Database Management
Lock
Transaction Management / Distributed Database Management
データベースの更新単位をアイテム、
アイテムの大きさを粒度（granularity）と呼ぶ
アイテムへのアクセスはロックにより管理
排他的なロックのかかっているアイテムには
他のトランザクションのアクセスを禁止
アイテムの粒度が大きい場合、
ロック管理システムの負担は軽くなるが、
同時に実行できるトランザクション数は減る
粒度の選択は典型的トランザクションを考えてきめる
預金口座のように小さい単位でトランザクションが
実行される場合は粒度は小さくする
Transaction Management / Distributed Database Management
ロックは様々な種類があるが当面は一種類とし、
アイテムAに対するロックを LOCK A と記述
• トランザクション T はアイテム A に
READ/WRITEする前に LOCK A を
ロックマネージャーに要求
• ロックマネージャーはアイテム A
にロックがかかっていない場合に T
が LOCK Aすることを許可
• Aがロックされている間は他のトラ
ンザクションはAにアクセスできない
• TはAに対する処理を終了したら、
ロックマネージャーに UNLOCK A を
要求し、ロックマネージャーはアイテム
Aに対するロックを解除
トランザクションT
LOCK A
要求
許可
UNLOCK A
ロックマネージャー
アイテムA
例題
Transaction Management / Distributed Database Management
普通預金口座
A
T1: 1000円を振り込む
トランザクション
T2: 1000円を引き出す
トランザクション
LOCK A;
READ A;
A := A + 1000;
WRITE A;
UNLOCK A;
LOCK A;
READ A;
A := A - 1000;
WRITE A;
UNLOCK A;
A
4000
T1:
T1:
T1:
T1:
LOCK A
READ A
WRITE A
UNLOCK A
T2:
T2:
T2:
T2:
LOCK A
READ A
WRITE A
UNLOCK A
5000
4000
A
4000
T2:
T2:
T2:
T2:
LOCK A
READ A
WRITE A
UNLOCK A
T1:
T1:
T1:
T1:
LOCK A
READ A
WRITE A
UNLOCK A
3000
4000
A
4000
T1: LOCK A
T1: READ A
T2: READ A
Transaction Management / Distributed Database Management
各トランザクションは
一つのアイテムに高々一回だけLOCKをかける
T
LOCK A;
A := A+1;
UNLOCK A;
LOCK B;
LOCK A;
B := B+A;
UNLOCK A;
UNLOCK B;
T
LOCK A;
A := A+1;
LOCK B;
B := B+A;
UNLOCK A;
UNLOCK B;
Transaction Management / Distributed Database Management
Livelock
T1が最初にAをロック
T2, T3 が LOCK A を要求
トランザクション Ti
T1が UNLOCK A
LOCK A;
READ A;
A := A + i ;
WRITE A;
UNLOCK A;
ロックマネージャーが
T3にロックを許可
T2 に順番が回らない Livelock
T4 が LOCK A を要求
T3が UNLOCK A
ロックマネージャーが
T4にロックを許可
簡単な回避方法 (First-come-first-served strategy)
LOCK A を要求するトランザクションに
要求順にロックを許可
Transaction Management / Distributed Database Management
Deadlock
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
LOCK B;
LOCK A;
READ A;
IF A >= 2000
A := A - 2000;
WRITE A;
READ B;
B := B + 2000;
WRITE B;
READ A;
A := A + 5000;
WRITE B;
READ B;
IF B >= 5000
B := B - 5000;
WRITE B;
UNLOCK A;
UNLOCK B;
UNLOCK B;
UNLOCK A;
T1: LOCK A; 許可
T2: LOCK B; 許可
T1: LOCK B; 不許可
T2: LOCK A; 不許可
T1とT2は永遠に
待ちつづける
Transaction Management / Distributed Database Management
プロトコルを工夫してDeadlock を起こさない手法１
各トランザクションは同時にすべてのロック要求を出す
ロックマネージャーは、この全要求を許可するか、全てを不許可
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
READ A;
IF A >= 2000
A := A - 2000;
WRITE A;
READ B;
B := B + 2000;
WRITE B;
UNLOCK A;
UNLOCK B;
LOCK B;
LOCK A;
READ A;
A := A + 5000;
WRITE B;
READ B;
IF B >= 5000
B := B - 5000;
WRITE B;
UNLOCK B;
UNLOCK A;
T1: LOCK A 許可
T1: LOCK B 許可
T1: UNLOCK A
T1: UNLOCK B
T2: LOCK B 許可
T2: LOCK A 許可
Transaction Management / Distributed Database Management
プロトコルを工夫してDeadlock を起こさない手法２
A ＞ B
• アイテムに順序を導入
• 各トランザクションは
順序の大きい順に
アイテムをロック
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
：
LOCK B;
LOCK A;
：
T1の実行後にT2が処理される
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
：
Transaction Management / Distributed Database Management
アイテムに順序を入れる方法がDeadlock を起こさない理由
背理法： Deadlock 状態のトランザクション集合があると仮定
前処理：アイテムをロックしていないトランザクションを
除いても、集合は依然として Deadlock状態
観察：各トランザクション Ti は他のトランザクション Ti+1 が
ロックしているアイテム Ai の開放を待っている
Ti
Ti+1
Ai
注意
Ti は Ai より順序の
大きいアイテムをロック
Ti
Ti+1
Ti+2
LOCK Ai
LOCK Ai
LOCK Ai+1
LOCK Ai+1
LOCK Ai+2
Ai+1 ＞ Ai+2
Ai ＞ Ai+1
Transaction Management / Distributed Database Management
ある T1 を選択して、鎖を構成
T1
A1
T2
A2
A1 ＞ A 2
T3
＞……. ＞An-1
ループしない有限の下降鎖
Ti
Ti+1
LOCK Ai
LOCK Ai
LOCK Ai+1
Ai ＞ Ai+1
An-1
Tn
Tn は,いつか An-1を
UNLOCK.
アイテムをロック
していない Tn が必ず
存在し、矛盾
Ti+2
LOCK Ai+1
LOCK Ai+2
Ai+1 ＞ Ai+2
Transaction Management / Distributed Database Management
スケジューラーがDeadlock を検知して abort 等で対処する方法
Waits-for Graph
トランザクションがノード
T1がロックしているアイテムA
のUNLOCKをT2が待っている
とき、「T1の次はT2」を表現する
ためT1からT2へ有向辺を引き
Aをラベルとしてつける
閉路の存在は Deadlock
を意味する
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
：
UNLOCK A;
UNLOCK B;
LOCK B;
LOCK A;
：
UNLOCK B;
UNLOCK A;
T1: LOCK A; 許可
T2: LOCK B; 許可
A
T1
T2
B
Transaction Management / Distributed Database Management
整列化可能性
(Serializability)
Transaction Management / Distributed Database Management
トランザクションの集合をある順序で整列化した列を
T1 T2 …… Tk
i=1,2,…,k の順番で Ti のステートメントを実行する
スケジュールを整列スケジュール (serial schedule) と呼ぶ
トランザクションをプログラムしたときのユーザの心境は
各トランザクションの実行を他のトランザクションが
邪魔しないことを仮定している
つまりトランザクション全体がある整列スケジュールとして
実行されることを思ってプログラムする
Transaction Management / Distributed Database Management
しかしシステムは効率を重視してトランザクションの
順番を入れ替えて実行するかもしれない
入れ替えをしても、その実行結果は
ある整列スケジュールの実行結果と一致してほしい
スケジュールが整列化可能とは、実行結果が
ある整列スケジュールの実行結果と一致することと定義する
この概念をどのように定式化するか？
Transaction Management / Distributed Database Management
T1: Aのx倍を
Bへ振り込む
T2: Bのx倍を
Aへ振り込む
LOCK A;
LOCK B;
READ A;
READ B;
B := B+A＊x;
WRITE B;
UNLOCK A;
UNLOCK B;
LOCK B;
READ B;
UNLOCK B;
LOCK A;
READ A;
A := A+B＊x;
WRITE A;
UNLOCK A;
整列スケジュール
T2: LOCK B;
T2: READ B;
T2: UNLOCK B;
T1:
T1:
T1:
T1:
LOCK A; LOCK B;
READ A; READ B;
B := B+A＊x; WRITE B;
UNLOCK A; UNLOCK B;
T2:
T2:
T2:
T2:
T2:
LOCK A;
READ A;
A := A+B＊x;
WRITE A;
UNLOCK A;
T1 B:=B+A*x
T2 A:=A+B*x
T2 A:=A+B*x
T1 B:=B+A*x
A=B=1000
x=2
T1: B=3000
T2: A=7000
T2: A=3000
T1: B=7000
T2: B=1000
T1: B=3000
T2: A=3000
整列化不可能
A=0
B=1000
x=2
T1: B=1000
T2: A=2000
T2: A=2000
T1: B=5000
T2: B=1000
T1: B=1000
T2: A=2000
整列化可能？
Transaction Management / Distributed Database Management
スケジュール S1 が整列化可能とは、
ある整列スケジュール S2 が存在して
任意の初期状態に対して、
S1と S2 の実行結果が一致することと定義した場合：
初期状態の候補は無限にあり、有限ステップでチェックできるか？
帰納的関数がある場合、２つの帰納的関数の等価性は一般に
決定不能
スケジュール S1 が整列化可能とは、
ある整列スケジュール S2 が存在して
任意の初期状態に対して、
LOCKとUNLOCK以外は任意をステートメントを許す場合に
S1と S2 の実行結果が一致することと定義する
Transaction Management / Distributed Database Management
LOCK A と UNLOCK A
のペアに対して
新しい関数 f を割当てる
f の引数は UNLOCK A
の前にトランザクション中で
ロックされる全ての
アイテムの値
T1: Aのx倍を
Bへ振り込む
T2: Bのx倍を
Aへ振り込む
LOCK A;
LOCK B;
READ A;
READ B;
B := B+A＊x;
WRITE B;
UNLOCK A;
UNLOCK B;
LOCK B;
READ B;
UNLOCK B;
LOCK A;
READ A;
A := A+B＊x;
WRITE A;
UNLOCK A;
A
a
f1(A, B)
g1(A, B)
B
b
g2(b)
T2: LOCK B;
T2: UNLOCK B;
g2(B)
T1:
T1:
T1:
T1:
LOCK A;
LOCK B;
UNLOCK A;
UNLOCK B;
f1(A,B)
g1(A,B)
f1(a, g2(b))
T2: LOCK A;
T2: UNLOCK A;
f2(A,B)
f2(f1(a,g2(b)),
g1(f1(a, g2(b)), g2(b)))
g1(f1(a, g2(b)), g2(b))
g2(B)
f2(A, B)
Transaction Management / Distributed Database Management
T1: Aのx倍を
Bへ振り込む
T2: Bのx倍を
Aへ振り込む
LOCK A;
LOCK B;
READ A;
READ B;
B := B+A＊x;
WRITE B;
UNLOCK A;
UNLOCK B;
f1(A, B)
g1(A, B)
LOCK B;
READ B;
UNLOCK B;
LOCK A;
READ A;
A := A+B＊x;
WRITE A;
UNLOCK A;
A
a
B
b
g2(B)
f2(A, B)
整列スケジュール１
T1:
T1:
T1:
T1:
T2:
T2:
T2:
T2:
LOCK A;
LOCK B;
UNLOCK
UNLOCK
LOCK B;
UNLOCK
LOCK A;
UNLOCK
A;
B;
B;
A;
f1(a,b)
g1(f1(a,b), b)
g2(g1(f1(a,b), b))
f2(f1(a,b),
g2(g1(f1(a,b), b)))
Transaction Management / Distributed Database Management
T1: Aのx倍を
Bへ振り込む
T2: Bのx倍を
Aへ振り込む
LOCK A;
LOCK B;
READ A;
READ B;
B := B+A＊x;
WRITE B;
UNLOCK A;
UNLOCK B;
LOCK B;
READ B;
UNLOCK B;
LOCK A;
READ A;
A := A+B＊x;
WRITE A;
UNLOCK A;
f1(A, B)
g1(A, B)
g2(B)
f2(A, B)
整列スケジュール２
T2:
T2:
T2:
T2:
T1:
T1:
T1:
T1:
LOCK B;
UNLOCK
LOCK A;
UNLOCK
LOCK A;
LOCK B;
UNLOCK
UNLOCK
A
a
B;
B
b
g2(b)
A;
f2(a, g2(b))
A;
B;
f1(f2(a,g2(b)), g2(b))
g1( f1(f2(a,g2(b))), g2(b))
Transaction Management / Distributed Database Management
３つのスケジュールの最終結果
A
B
f2(f1(a,g2(b)),
g1(f1(a, g2(b)), g2(b)))
g1(f1(a, g2(b)), g2(b))
整列スケジュール１ f2(f1(a,b),
g2(g1(f1(a,b), b))
g2(g1(f1(a,b), b)))
整列スケジュール２ f1(f2(a,g2(b)), g2(b))
g1( f1(f2(a,g2(b))), g2(b))
記号列として異なる場合、最終結果が異なるように
初期状態とステートメントをつくれる
記号列はUNLOCKの実行履歴を表現している
Transaction Management / Distributed Database Management
整列化可能性を判定する
アルゴリズム
Transaction Management / Distributed Database Management
スケジュールの整列化可能性を判定するアルゴリズム
スケジュールは T: LOCK A または T: UNLOCK A
の形をしたステートメントの列 a1, a2, …, an とする
整列化可能性判定グラフの構成
各 a i =T p: UNLOCK Am について aj = Tq: LOCK Am (p≠q)
となる j > i が存在する場合、最小の j を選択し有向辺を張る
Tp
Am
Tq
整列化可能な場合に対応する
整列スケジュール中で T p は T q の前にある
T p を始点としAmをラベルにもつ有向辺は高々１つ
定理グラフに閉路がなければ整列化可能、あれば不可能
Transaction Management / Distributed Database Management
整列化可能性判定グラフ
閉路がない場合
T2: LOCK A
T2: UNLOCK A
T3: LOCK A
T3: UNLOCK A
T1: LOCK B
T1: UNLOCK B
T1
B
引かない
B
T2
T2: LOCK B
T2: UNLOCK B
T3: LOCK B
T3: UNLOCK B
B
T3
A
この関係は
考慮しない
任意の始点から出る有向辺で
同一ラベルをもつ辺は高々一つ
Transaction Management / Distributed Database Management
与えられた
スケジュール
T1: LOCK A
T1: UNLOCK A
:
T2: LOCK A
T2: UNLOCK A
T3:
T3:
T4:
T4:
:
LOCK A
UNLOCK A
:
LOCK A
UNLOCK A
:
T5: LOCK A
T5: UNLOCK A
整列化可能性判定グラフ
閉路がない場合
A
T1
T2
T3
T4
T5
閉路のないグラフでは、
同一アイテムをラベルに
もつ有向辺は、連続した
列をつくる
Transaction Management / Distributed Database Management
一般には複数の
アイテムに対する
列が交差する
Transaction Management / Distributed Database Management
整列化可能性判定グラフ G の位相ソート
閉路がない場合には
Gにはいかなる有向辺の終点でないノード v が存在する
存在しないと仮定すれば、あるノードから有向辺を逆に
辿る列をつくると、ノード数が有限なので、いつかは
自分に戻る閉路ができる
v と v を始点とする有向辺を G から除く
このステップを繰返し、除かれたノード（トランザクション）列
T1 T2 …… Tk を位相ソート列と呼ぶ
位相ソート列を使って整列スケジュールを作る
Transaction Management / Distributed Database Management
与えられたスケジュール
整列化可能性判定グラフ
T2: LOCK A
T2: UNLOCK A
T3: LOCK A
T3: UNLOCK A
T1: LOCK B
T1: UNLOCK B
整列スケジュール
T1: LOCK B
T1: UNLOCK B
T1
B
B
T2
T3
T2: LOCK B
T2: UNLOCK B
A
T3: LOCK B
T3: UNLOCK B
位相ソート列 T1, T2, T3
T2:
T2:
T2:
T2:
LOCK A
UNLOCK A
LOCK B
UNLOCK B
T3:
T3:
T3:
T3:
LOCK A
UNLOCK A
LOCK B
UNLOCK B
Transaction Management / Distributed Database Management
与えられた
スケジュール
T1: LOCK A
T1: UNLOCK A
:
T2: LOCK A
T2: UNLOCK A
T3:
T3:
T4:
T4:
:
LOCK A
UNLOCK A
:
LOCK A
UNLOCK A
:
T5: LOCK A
T5: UNLOCK A
整列化可能性判定グラフ
閉路がない場合
A
T1
T2
T3
T4
T5
位相ソートから
得られる整列
スケジュール内で
アイテムAに対する
ロックは
T1, T2, T3, T4, T5
の順序で起こる
Transaction Management / Distributed Database Management
定理前半
スケジュール S の整列化可能性判定グラフ G が閉路を含まな
い場合、位相ソートでつくった整列スケジュール R は S と等価
準備
0
0
0
ノード N の深さ d(N)
N を終点とする有向辺
の始点を N の隣接点
1
1
N
:
M1
Mk
2
2
1
d(N) = 0
Nに隣接点がない
= max{ d(M) | M は隣接点}+1
Transaction Management / Distributed Database Management
スケジュール S と R で、同じトランザクションは
同一のアイテムに関して同じ値を読むことを証明
深さに関する帰納法
深さ０のとき、各アイテムの値は初期状態だから、OK
深さｋ未満
T’
S, R で T がアイテム A を
LOCKする直前に A を UNLOCK
するトランザクションをT’とする
A
帰納法の仮定でS と R は
T’ で A に同一の値を読み込む
T
深さｋ
S と R は T でも A に
同一の値を読み込む
Transaction Management / Distributed Database Management
整列化可能性判定グラフ
閉路がある場合
T2: LOCK B;
T2: UNLOCK B;
T1:
T1:
T1:
T1:
LOCK A;
LOCK B;
UNLOCK A;
UNLOCK B;
T3: LOCK A;
T3: UNLOCK A;
T2: LOCK A
T2: UNLOCK A
T1
B
A
T3
T2
A
Transaction Management / Distributed Database Management
T1
定理後半スケジュール S の整列化可能性判定
グラフが閉路を含む場合、Sは整列化不可能
仮に等価な整列スケジュール R があるとする
T2
Ti (i=1,…k)の中で Tp が R に最初に現れるとする
R
S
Tp-1
Tp
Tp-1: UNLOCK A g(…)
Tp: LOCK A
:
Tp: UNLOCK A
f(…)
Tp: LOCK A
:
Tp: UNLOCK A
f(…)
R では f(…) に g(…) は出現しない. Sでは出現.
Tk
R と S は等価でないので矛盾
Transaction Management / Distributed Database Management
T1
もう一つ例
T2
S
R
Tp: LOCK A
Tp-1
Tp
Tp-1: LOCK B
Tp-1: UNLOCK B g(B)
Tp: LOCK B
:
Tp: UNLOCK A
f(A,B)
Tp: LOCK A
Tp: LOCK B
:
Tp: UNLOCK A
f(A,B)
R では f(…) に g(…) は出現しない. Sでは出現.
Tk
R と S は等価でないので矛盾
Transaction Management / Distributed Database Management
整列化可能性判定グラフ
整列スケジュール
T2: LOCK B;
T2: UNLOCK B;
T1:
T1:
T1:
T1:
LOCK A;
LOCK B;
UNLOCK A;
UNLOCK B;
T3: LOCK A;
T3: UNLOCK A;
T2: LOCK A
T2: UNLOCK A
T3: LOCK A
T3: UNLOCK A
:
g(…)
T1
f(…)
B
A
T3
T2
A
f(…)
Transaction Management / Distributed Database Management
２相ロックプロトコル
(Two-phase Locking Protocol)
Transaction Management / Distributed Database Management
２相ロックプロトコル
各トランザクションにおいて、すべてのLOCK文は、
すべてのUNLOCK文の前に実行する
定理
２相ロックプロトコルに従ってできた
スケジュール S は、必ず整列化可能
Transaction Management / Distributed Database Management
２相ロックの正当性の証明
背理法
整列化不可能な場合、整列化可能性判定グラフには閉路あり
T1 の UNLOCK 後に T2 の LOCK
T1
Tk
T2 の UNLOCK 後に T3 の LOCK
T2
:
Tk の UNLOCK 後に T1 の LOCK
T5
T3
T4
T1はUNLOCK後にLOCKしており
２相ロックプロトコルに従うことに矛盾
Transaction Management / Distributed Database Management
２相ロックプロトコルの最適性
条件は少しでも緩めると整列化可能性は失われる
T1 は２相ロックプロトコルに従わないとする
T1
LOCK A
:
UNLOCK A
:
LOCK B
:
UNLOCK B
:
T2
LOCK A
LOCK B
UNLOCK A
UNLOCK B
T1: LOCK A
:
T1: UNLOCK A
T2:
T2:
T2:
T2:
LOCK A
LOCK B
UNLOCK A
UNLOCK B
T1: LOCK B
:
T1: UNLOCK B
T1
A
B
T2
Transaction Management / Distributed Database Management
注意２相ロックプロトコルで
Deadlock を回避できるわけではない
T1: AからBへ
２０００円送金
T2: BからAへ
５０００円送金
LOCK A;
LOCK B;
LOCK B;
LOCK A;
READ A;
IF A >= 2000
A := A - 2000;
WRITE A;
READ B;
B := B + 2000;
WRITE B;
READ A;
A := A + 5000;
WRITE B;
READ B;
IF B >= 5000
B := B - 5000;
WRITE B;
UNLOCK A;
UNLOCK B;
UNLOCK B;
UNLOCK A;
T1: LOCK A; 許可
T2: LOCK B; 許可
T1: LOCK B; 不許可
T2: LOCK A; 不許可
T1とT2は永遠に
待ちつづける
Transaction Management / Distributed Database Management
ここまでのまとめ
• 整列化可能性の概念を定義
• 整列化可能であることと
整列化可能性判定グラフが閉路を含まないことは同値
• ２相ロックプロトコルは整列化可能の十分条件
課題
• いろいろなＬＯＣＫに対して整列化可能性判定グラフの
技法をどこまで拡張して適用できるのか？
• ２相ロックプロトコルはどこまで有効か？
Transaction Management / Distributed Database Management
Read Only Lock / Write Lock
を使うモデル
Transaction Management / Distributed Database Management
Read Lock (RLOCKと記述)
• 読み込むだけのデータにかける鍵
• 他のトランザクションがWrite Lock してないデータにかけられる
Write Lock (WLOCK)
• 読み書きするデータにかける鍵
• 他のトランザクションがRead LockもWrite Lock もしていない
データにかけられる
Read Lockがかかっているデータに
Read Lockは可能だが、Write Lock は不可能
Write Lockがかかっているデータに
Read LockもWrite Lock も不可能
Transaction Management / Distributed Database Management
スケジュールの整列化可能性
スケジュール
T1
RLOCK A
:
UNLOCK A
T2
RLOCK A
:
UNLOCK A
RLOCK 間の関係から
トランザクションに順序を
定義しなくても構わない点が
違うだけ。
他の場合は以前と同様。
対応する整列スケジュール
T1
RLOCK A
:
UNLOCK A
T2
RLOCK A
:
UNLOCK A
T1
RLOCK A
:
UNLOCK A
T2
RLOCK A
:
UNLOCK A
Transaction Management / Distributed Database Management
RLOCK / WLOCK の場合の整列化可能性判定グラフの構成
ケース１
Ti
Tm
RLOCK A
(or WLOCK A)
:
UNLOCK A
WLOCK A
Ti
Tm
Ti : UNLOCK A と Tm : WLOCK A の間で
WLOCK A は出現しない
Transaction Management / Distributed Database Management
Ti
Tj
Tk
Tm
WLOCK A
:
UNLOCK A
RLOCK A
:
UNLOCK A
Ti
RLOCK A
:
UNLOCK A
Tj
Tm
Tk
WLOCK A
Transaction Management / Distributed Database Management
ケース２
Ti
Tm
Tn
WLOCK A
:
UNLOCK A
RLOCK A
RLOCK A
Ti
Tm
Tn
Ti: UNLOCK A と各 RLOCK A の間で
WLOCK A は出現しない
Transaction Management / Distributed Database Management
WLOCK A を中心に考えるとわかりやすい
複数のRLOCK A
単一のWLOCK A
・・
Tm: WLOCK A
Tm
・・
複数のRLOCK A
単一のWLOCK A
Transaction Management / Distributed Database Management
T1
T2
T3
T4
WLOCK A
RLOCK B
UNLOCK A
RLOCK A
UNLOCK B
WLOCK B
RLOCK A
UNLOCK B
WLOCK B
UNLOCK A
UNLOCK A
WLOCK A
UNLOCK B
RLOCK B
UNLOCK A
UNLOCK B
T1
T2
T4
T3
Transaction Management / Distributed Database Management
T1
T2
T3
T4
WLOCK A
RLOCK B
UNLOCK A
RLOCK A
UNLOCK B
WLOCK B
RLOCK A
UNLOCK B
WLOCK B
UNLOCK A
UNLOCK A
WLOCK A
UNLOCK B
RLOCK B
UNLOCK A
UNLOCK B
T1
T2
T4
T3
Transaction Management / Distributed Database Management
T1
T2
T3
T4
WLOCK A
RLOCK B
UNLOCK A
RLOCK A
UNLOCK B
WLOCK B
RLOCK A
UNLOCK B
WLOCK B
UNLOCK A
UNLOCK A
WLOCK A
UNLOCK B
RLOCK B
UNLOCK A
UNLOCK B
T1
T2
T4
T3
Transaction Management / Distributed Database Management
T1
T2
T3
T4
WLOCK A
RLOCK B
UNLOCK A
RLOCK A
UNLOCK B
WLOCK B
RLOCK A
UNLOCK B
WLOCK B
UNLOCK A
UNLOCK A
WLOCK A
UNLOCK B
RLOCK B
UNLOCK A
UNLOCK B
T1
T2
T4
T3
Transaction Management / Distributed Database Management
T1
T2
T3
T4
WLOCK A
RLOCK B
UNLOCK A
RLOCK A
UNLOCK B
WLOCK B
RLOCK A
UNLOCK B
WLOCK B
UNLOCK A
UNLOCK A
WLOCK A
UNLOCK B
RLOCK B
UNLOCK A
UNLOCK B
T1
T2
T4
T3
Transaction Management / Distributed Database Management
定理
整列化可能性判定グラフが閉路をもてば、
スケジュールは整列化不可能
閉路がないグラフであれば、
位相ソートを使ってトランザクションを整列化し、
等価な整列スケジュールを生成できる
証明はLOCK－UNLOCKの場合の考え方と同様
Transaction Management / Distributed Database Management
２相ロックプロトコル
トランザクションは、
RLOCKとWLOCK要求を全て実行した後にUNLOCKを行う
定理
２相ロックプロトコルを使う場合、整列化可能性は保証される
証明はLOCK－UNLOCKの場合の考え方と同様
Transaction Management / Distributed Database Management
木構造をしたデータ・アイテムを
扱うプロトコル
Transaction Management / Distributed Database Management
木構造をしたデータ構造
• HTML, XML
• B-tree
• データベース
全体→各関係→ファイル→レコード
Transaction Management / Distributed Database Management
木プロコトル (tree protocol)
A
各トランザクションは以下の規則に
従ってアイテムをロックをかける.
1. アイテムをロックできるのは、
親アイテムをロックしているとき。
最初にロックするアイテムはこの条件を満たさな
くてよい。
また最初にロックするアイテムは根ノードである
必要がなく、任意のアイテムを選択できる。
2. １つのアイテムを複数回ロックし
ない。
C
B
E
D
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
T3
A
LOCK B
C
B
LOCK E
UNLOCK D
LOCK F
UNLOCK A
E
D
LOCK G
UNLOCK C
LOCK E
UNLOCK B
UNLOCK E
UNLOCK E
UNLOCK F
UNLOCK G
F
G
Transaction Management / Distributed Database Management
A
A
C
B
E
D
E
D
F
G
A
E
F
G
F
C
B
D
E
D
E
D
A
C
C
B
G
F
A
B
C
B
G
F
A
E
D
G
C
B
F
G
Transaction Management / Distributed Database Management
木プロトコルは２相ロックプロトコルではない
T1
LOCK A
LOCK B
LOCK D
UNLOCK B
LOCK C
T2
LOCK B
しかし木プロトコルに従うスケジュールは整列化可能である
Abraham Silberschatz and Zvi Kedem: “Consistency in
Hierachical Database Systems.” Journal of the ACM, Vol.27,
No.1, Jan. 1980, pp.72-80.
Transaction Management / Distributed Database Management
証明の概略
トランザクション T が最初にロックするアイテムを FIRST(T)
２つのトランザクション Ta , Tb について
FIRST(Ta) FIRST(Tb) が先祖と子孫の関係にない場合：
Ta と Tb が共通のアイテムをロックすることはない
FIRST(Ta)
FIRST(Tb )
Transaction Management / Distributed Database Management
FIRST(Ta) FIRST(Tb) が先祖と子孫の関係にある場合
補題 Ta とTb が少なくとも1つの共通するアイテムをロック。
共通するすべてのアイテムを先に Ta もしくは Tb がロック。
共通してロックするアイテムは木構造を成す
最も根ノードに近いノードを X とする
X を Ta が先にロックすると仮定
Transaction Management / Distributed Database Management
背理法：Tb がTa より先にロックするアイテム Y が存在すると仮定
X
Ta が先
• Ta はいつか Y をロック
• Tb もいつか X をロック
P
• ある Z と親ノード P で矛盾
矛盾
Z
Tb が先
Y
Transaction Management / Distributed Database Management
木プロトコルに従うスケジュールは整列化可能である
深さに関する帰納法
一般の場合
(1) 根ノードをロックする
トランザクションは
整列化可能
(2) 各部分木のアイテ
ムだけロックするトラン
ザクションは整列化可能
(3) 補題より (1)の整
列に (2) の整列を各々
独立に融合することが可
根ノードだけの場合
Transaction Management / Distributed Database Management
トランザクションの abort
COMMITMENT
Cascading Rollback
Transaction Management / Distributed Database Management
いままではトランザクションが必ず完了するケースを扱ってきた
しかし現実には完了しないまま abort するケースが多い
• スケジューラがdeadlockを検知し,abortでdeadlock 回避
• 個々のトランザクションが自ら abort する
ユーザの割り込み、０による割り算、権限のないアクセス
• 整列性を保証するためにトランザクションの abort を強制する
プロトコルを使う場合
• システムダウン
Transaction Management / Distributed Database Management
トランザクションの２つの計算状態
• 計算実行中 (active)
• 計算完了 (completed)
あとはアイテムに結果を書くだけ
T1
T2
LOCK A
READ A
A := A-1
WRITE A
LOCK B
UNLOCK A
READ B
B := B/A
WRITE B
UNLOCK B
LOCK A
READ A
A := A+2
WRITE A
UNLOCK A
計算実行中
計算完了
計算実行中
計算完了
Transaction Management / Distributed Database Management
計算の完了を宣言する文
COMMIT
T1
T2
LOCK A
READ A
A := A-1
WRITE A
LOCK B
UNLOCK A
READ B
B := B/A
LOCK A
READ A
A := A+2
COMMIT
WRITE B
UNLOCK B
COMMIT
WRITE A
UNLOCK A
Transaction Management / Distributed Database Management
T1
T2
LOCK A
READ A
A := A-1
WRITE A
LOCK B
UNLOCK A
LOCK A
READ A
A := A＋2
READ B
COMMIT
WRITE A
UNLOCK A
B := B/A
COMMIT
WRITE B
UNLOCK B
A=1, B=1
A := 0
T1 が abort し
たので、Aの値を
T1 の実行以前
の状態に戻す必
要がある
A := 2
すると、ここでの
更新も戻す
必要がある
B := 1/0
この時点で T1 の
abort が発生
Cascading rollback
（なだれ的な巻き戻し）
Transaction Management / Distributed Database Management
T1
T2
LOCK A
READ A
A := A-1
WRITE A
LOCK B
UNLOCK A
LOCK A
READ A
A := A＋2
READ B
COMMIT
WRITE A
UNLOCK A
B := B/A
COMMIT
WRITE B
UNLOCK B
A=1, B=1
Dirty Read
A:=0
A:=2
B := 1/0
T2: READ A は T1 の
計算が完了する以前
（T1:COMMITの前）に
T1: WRITE A が書き
出した値を読んでいる
T1 はその後 abort し、
T2 が読んだ A の値は
無効になり cascading
rollback
を生む
Transaction Management / Distributed Database Management
２つの課題
• Dirty Read の回避
• Cascading rollback の回避
COMMIT, WRITE の位置を工夫して解決
Transaction Management / Distributed Database Management
Dirty Read の回避
COMMIT つまり
計算の完了を宣言してから
WRITE を実行する
T1
T1
LOCK A
READ A
A := A-1
WRITE A
LOCK B
UNLOCK A
READ B
B := B/A
LOCK A
READ A
A := A-1
COMMIT
COMMIT
WRITE B
UNLOCK B
WRITE A
UNLOCK A
WRITE B
UNLOCK B
LOCK B
READ B
B := B/A
T1
LOCK A
READ A
A := A-1
LOCK B
READ B
B := B/A
COMMIT
WRITE A
UNLOCK A
WRITE B
UNLOCK B
Transaction Management / Distributed Database Management
T2
LOCK A
READ A
A := A+2
COMMIT
WRITE A
UNLOCK A
• T2:READ A はもはや
Dirty Read ではない
（計算が完了 COMMIT した
あとの WRITE A の値を読んでる）
• しかし、T1: WRITE B
で abort すれば、
Cascading Rollback が発生
Transaction Management / Distributed Database Management
Cascading Rollback
の回避
すべての WRITE
が完了するまで
UNLOCK を実行し
ない
あるアイテムの値を
読むとき、その値を
書き出したトランザ
クションが abort す
ることはない
T1
LOCK A
READ A
A := A-1
LOCK B
READ B
B := B/A
COMMIT
WRITE A
WRITE B
UNLOCK A
UNLOCK B
T2
LOCK A
READ A
A := A+2
COMMIT
WRITE A
UNLOCK A
Transaction Management / Distributed Database Management
強２相ロックプロトコル
(strict two-phase locking protocol)
• WRITEの実行はCOMMIT の後
• すべての WRITE が完了するまでUNLOCK
を実行しない
Transaction Management / Distributed Database Management
障害発生時の
データベース修復
Transaction Management / Distributed Database Management
記憶媒体の信頼性
主記憶
揮発性記憶装置
電源障害時にデータが消える
system failure
二次ディスク
テープ
永続的記憶装置
ヘッドクラッシュなど深刻な障害
(media failure) の時以外は
データが残る
Transaction Management / Distributed Database Management
System failure 発生時のデータベース修復
修復に備えデータベース更新履歴をとる
ログ(log) ジャーナル(journal)
• トランザクション T の起動
(T, begin)
• T がアイテム A の値が w のとき、値 v を書き込む
(T, A, w, v)
• T がコミットしたとき
(T, commit)
• T がアボートしたとき
(T, abort)
Transaction Management / Distributed Database Management
再実行プロトコル (Redo Protocol)
A
ログを生成する強２相ロックプロトコル
w
トランザクション T が COMMIT 文に達したとき、
以下の処理を実行
T
v
• トランザクション T が、値が w のアイテム A に値 v
を書き出すとき、T 内の順番に従って
(T, A, w, v)
をログに書き込む。ただし、COMMIT 以前に A に対して
w は計算された値であること。
• (T, commit) をログに書き込む
ログは新たな書き込みが起こるたびに二次記憶装置に書き込む
Transaction Management / Distributed Database Management
トランザクション T
ログの内容
A=10, B=20 のとき
LOCK A
LOCK B
(T, begin)
A := A+1
B := B+1
(T, A, 10, 11)
(T, B, 20, 21)
COMMIT
(T, commit)
WRITE A
WRITE B
UNLOCK A
UNLOCK B
続いて
データベースに
書きこむ
ログにまず
書きこむ
Transaction Management / Distributed Database Management
ログを使ったデータベース修復の手順
• 障害発生時に各トランザクションが握るロックは開放させる
• 各トランザクションに対して最新の (T, commit) を見つける
(T, begin)
(T, A1, w1, v1)
:
この順番で書き込みを再実行
(T, An, wn, vn)
(T, commit)
• トランザクション T について、(T, commit) がない場合、
強２相ロックプロトコルなので、T の WRITE 文は実行されない
• (T, abort) がある場合、T の更新履歴はすべて破棄する
Transaction Management / Distributed Database Management
System Failure の
際に値を戻す手順
計算も未完了で
アイテムの値を
WRITE
していないので
なにもしない
COMMIT直後以
降は計算が完了し
ているので、
A に 11、B に 21
を書き出す
既に正しい値であ
る場合でも書く
トランザクション T
ログの内容
A=10, B=20
LOCK A
LOCK B
(T, begin)
A := A+1
B := B+1
(T, A, 10, 11)
(T, B, 20, 21)
COMMIT
(T, commit)
WRITE A
WRITE B
UNLOCK A
UNLOCK B
Transaction Management / Distributed Database Management
Abort の場合、トランザクション実行前の状態に戻す
A=10
A=11
トランザクション T
ログの内容
A=10, B=20
LOCK A
LOCK B
(T, begin)
A := A+1
B := B+1
(T, A, 10, 11)
(T, B, 20, 21)
COMMIT
(T, commit)
B=20
B=21
WRITE A
WRITE B
UNLOCK A
UNLOCK B
Transaction Management / Distributed Database Management
チェックポイント処理 (checkpointing)
主記憶にあるデータ更新の履歴を
二次記憶装置へ書き込む操作
abort や system failure が発生しても
チェックポイント実行前の状態に戻さない
そこで各トランザクションの COMMIT 以降の状態を保存する
• すべてのトランザクションの実行要求を禁止する
• 実行中のトランザクションが abort するか、
もしくは終了するまで待つ
• 二次記憶への書き出しが済んでいない主記憶中のブロック
を書き出す
• ログの最後に checkpoint が済んだことを書きこむ
Transaction Management / Distributed Database Management
Media failure への対処
• system failure への対処方法は二次記憶の信頼性に
完全に依存している
• ディスクヘッドが故障したり、子供が磁石でディスクをなでたり、
天変地異がおこったりなど、 media failure に完全には
対応できない
• 基本的には、定期的にバックアップをとる
• 更新の頻度は、夜間に一回から連続的まで様々
Transaction Management / Distributed Database Management
タイムスタンプ方式の
並列実行制御
Transaction Management / Distributed Database Management
整列化可能性 (serializability) を LOCK により実現してきた
他に現実システムで使われている手法：タイムスタンプ方式
• 各トランザクションは実行を開始するときスケジューラを呼ぶ
• スケジューラは実行開始時間をタイムスタンプとして与える
• 複数のトランザクションはタイムスタンプの順番で整列化する
• タイムスタンプ方式は積極的プロトコルの例で、不具合が
生じた時点で abort 等により不整合を修復
• ロックを使ったスケジュールから導かれる整列化した順序
とは必ずしも一致しない
Transaction Management / Distributed Database Management
T1
READ A
WRITE C
T2
READ B
WRITE C
タイムスタンプ方式
2
T1
READ A
WRITE C
1
T2
READ B
WRITE C
T2 → T1
ロック方式
WLOCK が読み書き両方
のロックの場合
T1
T2
:
WLOCK C
WRITE C
UNLOCK C
:
WLOCK C
WRITE C
UNLOCK C
T1 → T2
Transaction Management / Distributed Database Management
タイムスタンプの発行
• トランザクションの数をカウントし、
次の番号をタイムスタンプとして与える
• 時計の時間を与える
Transaction Management / Distributed Database Management
タイムスタンプを使ったトランザクションの整列化
各アイテムごとに、read time と write time を管理
• Read Time (RT)
現在をふくめ現在に最も近い時刻に
アイテムを読み出したトランザクションのタイムスタンプ
• Write Time (WT)
現在をふくめ現在に最も近い時刻に
アイテムを書き出したトランザクションのタイムスタンプ
Transaction Management / Distributed Database Management
ﾀｲﾑｽﾀﾝﾌﾟ
T1
T2
A
150
160
RT=0
WT=0
READ A
A:=A+1
WRITE A
READ A
A:=A+1
WRITE A
RT=150
RT=160
WT=160
WT=150 ??
対応する整列スケジュール T1 → T2
Transaction Management / Distributed Database Management
各アイテムに対する読み書き時間による整列化可能性チェック
• 未来に書き込まれるアイテムの値を、現在は読めない
t1 < t2 をタイムスタンプとするとき、
t2 のトランザクションが書いたアイテム (WT=t2) を
t1 のトランザクションは読めない
• 未来に読み込まれるアイテムの値を、現在上書きできない
t1 < t2 をタイムスタンプとするとき、
RT=t2 のアイテムに t1 のトランザクションは書きこめない
どちらの場合も、t1 のトランザクションを abort し、
新しいタイムスタンプで再実行
Transaction Management / Distributed Database Management
ﾀｲﾑｽﾀﾝﾌﾟ
T1
T2
A
150
160
RT=0
WT=0
READ A
A:=A+1
WRITE A
READ A
A:=A+1
WRITE A
RT=150
RT=160
WT=160
WT=150
RT=160 > 150 なので T1 は abort
Transaction Management / Distributed Database Management
READ-READ の場合
ﾀｲﾑｽﾀﾝﾌﾟ
(t1 < t2)
T1
T2
A
t1
t2
RT=0
READ A
RT=t2
RT=t2
READ A
RT=t2 > t1 でも読み込んで不具合が生じない
RT=t2 はそのまま (RT=t1 としない）
Transaction Management / Distributed Database Management
WRITE-WRITE の場合
ﾀｲﾑｽﾀﾝﾌﾟ
(t1 < t2)
T1
T2
A
t1
t2
WT=0
WRITE A
WT=t2
WT=t2
WRITE A
WT=t2 > t1 のとき、A に何も書き出さない
未来に書き出される値に過去の値を上書きできない
整列スケジュールでは T1 のあと T2 を実行し、
T1 の WRITE A の値を T2 が上書き
WT=t2 はそのまま (WT=t1 としない）
Transaction Management / Distributed Database Management
T1
T2
T3
A
200
150
175
RT=0 RT=0 RT=0
WT=0 WT=0 WT=0
READ B
WRITE B
WRITE A
READ A
WRITE C
abort
READ C
WRITE A
書き出さない
B
C
RT=200
RT=150
RT=175
WT=200
WT=200
WT=150
WT=175
Transaction Management / Distributed Database Management
タイムスタンプを使った整列化可能性チェックのまとめ
アイテム A (RT = rt, WT = wt) に
タイムスタンプ t のトランザクションが
操作 X (= READ or WRITE) を行うとき
• X=READ かつ t < wt ならば abort
• X=WRITE かつ t < rt ならば abort
• X=WRITE かつ t≧rt かつ t<wt ならば書き出さない
• X=READ かつ t≧wt ならば実行し RT:=t
• X=WRITE かつ t≧rt かつ t≧wt ならば実行し WT:=t
正常な場合
Transaction Management / Distributed Database Management
タイムスタンプ方式は積極的プロトコルの例
• 同一アイテムの読み書きが競合する
可能性のない場合に有効
• 不具合が生じたところで
トランザクションを abort して対処
Transaction Management / Distributed Database Management
タイムスタンプの管理
• ロックで管理する場合はロックしているアイテムだけを
表に登録すればよい
• タイムスタンプの場合、各アイテムごとに RT, WT を管理
• アイテム数が多い場合、管理表が大きくなる
Transaction Management / Distributed Database Management
解決案
• 実行中のトランザクションのタイムスタンプの最小値を M
M は生きている最も古いトランザクションのタイムスタンプ
• M より小さいタイムスタンプは全て -∞ にしても
整列化可能性のチェックは同様に実行できる
新しく実行されるトランザクションのタイムスタンプは
必ず M より大きいから
• RT=WT= -∞ となるトランザクションは管理表から外す
Transaction Management / Distributed Database Management
タイムスタンプ方式での
障害発生時の
データベース修復
Transaction Management / Distributed Database Management
Abort および障害発生時の対応
• タイムスタンプ方式での同時実行制御は積極的プロトコル
• abort 時や障害発生時のデータベース修復に手間
• Dirty Read と Cascading Rollback に弱い
• ログの管理による対処
• COMMIT の利用
Transaction Management / Distributed Database Management
Cascading Rollback の例
T1
T2
T3
A
200
150
175
RT=0 RT=0 RT=0
WT=0 WT=0 WT=0
READ B
READ A
WRITE A
READ A abort
WRITE B
WRITE A
WRITE C
abort
READ C
B
C
RT=200
RT=150
WT=150
RT=175
RT=200
WT=200
WT=200
WT=150
Transaction Management / Distributed Database Management
タイムスタンプ方式での COMMIT の利用
• すべての計算を完了した時点で COMMIT を宣言
• すべての更新したアイテムの値を書き出す
注意点
T
(timestamp=t)
• トランザクション T のタイムスタンプを t
:
• T が WRITE するアイテムの RT を rt
COMMIT
• t < rt ならば abort
WRITE A
• t < rt の確認を commit 以前に行えば、データベースに
影響を与えずにトランザクションを abort できる
Dirty Read の回避
A
RT=rt
Transaction Management / Distributed Database Management
例
• T のタイムスタンプを 100
T (timestamp=100)
:
COMMIT
WRITE A
• T は最後に WRITE A と
WT:=100 を実行
ロックをつかった abort 回避
• A の RT < 100 であること
を確認して T は計算を開始
RT をチェック後、 WT:=100
を実行し A をロックする
• A の値をタイムスタンプ 110
のトランザクション T’ が読み、
RT := 110 とする
T’ が A の値を読み出すこと
を禁止
• T は commit 直前に A の
RT を読み、 RT=110 であるこ
とを知り abort
WRITE A を実行
RT のチェックは既に行ってい
るので不要
Transaction Management / Distributed Database Management
ロックを使い abort を回避する方法１
• WRITE A をするトランザクション T (タイムスタンプ t) は、
- 計算開始時に A に対して WT=t として、A をロック
- 計算途中で abort した場合、 A のロックを開放し、
A の WT を元に戻す
• commit に到達したら、ログに T の計算した値を書き出す
• (T, commit) をログに追加
• データベースに T の計算した値を書き出す
• アイテムのロックを開放
• 長時間アイテムをロックする傾向にあるが、前ページの
abort は回避できる
Transaction Management / Distributed Database Management
T
100
（実行開始）
：
：
COMMIT
WRITE A
T
100
（実行開始）
WLOCK A
：
：
COMMIT
WRITE A
UNLOCK A
T’
110
A
READ A
RT=110
100 < RT=110
T’
110
A
RLOCK A
READ A
RT=90
RT=90
WT=100
RT=100
abort
Transaction Management / Distributed Database Management
ロックを使い abort を回避する方法2
楽観的方法 (Optimistic Method)
• T が commit する直前に、T が読み書きするすべての
アイテムをロックし、タイムスタンプの整合性をチェックし、
abort か commit を判断
- abort の場合、A のロックを開放し、
A の WT を元に戻す
•
•
•
•
commit の場合、ログに T の計算した値を書き出す
(T, commit) をログに追加
データベースに T の計算した値を書き出す
アイテムのロックを開放
• 最初のステップでは、トランザクション実行中に RT が更新される
アイテムがないと楽観的に考えている
Transaction Management / Distributed Database Management
T
100
（実行開始）
：
：
WLOCK A
UNLOCK A
COMMIT
WRITE A
T’
110
T
100
（実行開始）
：
：
T’
110
A
READ A
RT=110
100 < RT=110
WLOCK A
UNLOCK A
COMMIT
WRITE A
A
RT=90
RT=90 < 100
READ A
no problem
WT=100
RT=110
RT=90
abort
Transaction Management / Distributed Database Management
複数バーション法
• トランザクション T がアイテム A に書くとき A の新バーション
Ai をつくり、WT を T のタイムスタンプとする (例外を後述)
• タイムスタンプ t のトランザクション T の READ A は、
t 以下で t に最も近い WT のバーション Aj の値を読む
T1
T2
A0
100
200
RT=0
WT=0
READ A
READ B
READ A
WRITE B
A1
RT=100
RT=200
B0
B1
RT=0
WT=0
WT=200
RT=100
T1: READ B はバーション B0 の値を読む
Transaction Management / Distributed Database Management
複数バーションをもたない場合
T1
T2
A
B
100
200
RT=0
WT=0
RT=0
WT=0
READ A
READ B
abort
READ A
WRITE B
RT=100
RT=200
WT=200
RT=100
複数バーションをもち、すこし古い値に
アクセスを許すことで、上のような abort を回避できる
しかしバーション管理は余分な記憶スペースを必要とする
Transaction Management / Distributed Database Management
新バーションを生成できずに abort する場合
• タイムスタンプ t のトランザクション T がアイテム A
に書くとき、 WT < t < RT となる A のバージョンが存在する
T1
T2
A0
150
160
RT=0
WT=0
READ A
A:=A+1
WRITE A
abort
READ A
A:=A+1
WRITE A
A1
RT=150
RT=160
WT=160
A0 は時刻 0 から少なくとも 160 までは生きている
T1: WRITE A は時刻 150 で A の値を変更するので abort
Transaction Management / Distributed Database Management
• 何もしない素朴な方法
問題が起こったら abort で対処
• ロックを使って abort を回避
ロックする時間が長くなる
• COMMIT 前に瞬間的にロック
また abort の危険性がでる
• 複数バージョン法
素朴な方法に比べ abort する頻度は減る
バージョン管理にスペースを食う
Transaction Management / Distributed Database Management
難しい場合：対立するトランザクションによる abort の繰返し
T1
T2
T1
T2
A
B
100
110
120
130
RT=0
WT=0
RT=0
WT=0
WRITE B
READ A
abort
WRITE A
再実行
READ B
abort
WT=110
RT=100
WRITE B
再実行
READ A
abort
WT=100
WT=120
RT=110
WRITE A
WT=130
RT=120
abort の繰返しを回避する効果的な方法はあまりない
再実行のタイミングをランダムにずらすことで対立を多少緩和
Transaction Management / Distributed Database Management
分散データベース管理
参考文献
Jeffrey D. Ullman: Principles of Database and Knowledge-base Systems
Volume I, Computer Science Press, 1988. ISBN 0-7167-8158-1
Chapter 10 Distributed Database Management
Transaction Management / Distributed Database Management
• 前回までは単一計算機に格納されたデータベースへの
トランザクション処理を解説
• 複数計算機上に分散して存在するデータベースへの
トランザクション処理は多少複雑化
- ２相ロックプロトコル
- 分散 deadlock 検知と回避
- 分散コミットメント２相コミットプロトコル
Transaction Management / Distributed Database Management
ノード
（サイト）
CPU + Disk
ネットワーク
ノード
（サイト）
CPU + Disk
リンク
LAN
専用電話回線
etc.
ノード
（サイト）
CPU + Disk
Transaction Management / Distributed Database Management
ネットワークの故障・障害
• ノードの故障、リンクの故障
分散データベースの resiliency (弾力性)
• 複数のアクセスパスをもつネットワークの形態で補強
リングメッシュハイパーキューブ
• データの複製により補強
アイテムの値のコピーを、必要なノードに配布
Transaction Management / Distributed Database Management
データの複製をもつ場合の注意点
• アイテム A の値を変更するとき、 A の全コピーの値を変更
• 一つのまとまった原子的な操作に見せかける
障害発生時
• A のコピーをもつノード N が停止
• A の値を知りたいトランザクションは N 以外のノードから
値を入手
• N が復活したとき、 A に最新の値をセット
Transaction Management / Distributed Database Management
グローバルトランザクション T
口座 A から 10000円を引き落とし
口座 B へ 10000円振込み
N1
コピーA
N2
コピー A
N3
コピー A
N4
コピー B
N5
コピー B
• 各ノードごとにコピーＡから
10000円減額する「ローカルサブトランザクション」を実行
• 全コピーの更新をするか否か
• あるノードでトランザクションがabort したら
全更新を無効にする
Transaction Management / Distributed Database Management
各ノードにおけるロックマネージャーの動作
トランザクション
WLOCK A
要求
許可または拒否
ロックマネージャー
アイテム
A
B
C
:
アイテムに複数のコピーがある場合
複数のコピーのロックを同時に取る
WLOCK ?
Y
N
Y
:
Transaction Management / Distributed Database Management
Write-Locks-All
Read-Locks-One
• WLOCK A (書きこみ専用ロック) を実行するには
A のすべてのコピーを WLOCK A すればよい
• RLOCK A (読取り専用ロック) を実行するには
A の一つのコピーを RLOCK A すればよい
• A のコピーをもつ各ノードでは
- WLOCK がかかっていなければ RLOCK を許可
（複数の RLOCK を許可）
- RLOCK と WLOCK いずれもかかってなければ
WLOCK を許可
Transaction Management / Distributed Database Management
アイテム A にロックをかけようとする
任意のトランザクションを T1, T2
• T1, T2 は同時に A に WLOCK をかけられない
• T1 は WLOCK、T2 は RLOCK を同時にかけられない
• 唯一可能なのは T1 と T2 が同時に RLOCK すること
T1: WLOCK A
T2:RLOCK A
Transaction Management / Distributed Database Management
Write-Locks-All のメッセージ数
WLOCK A
１回のWLOCK A
N0
A
2n 個の制御メッセージ
(WLOCK A、承認)
n 個の更新データ
承認
更新データ
N1
A
…
Ni
A
…
A のコピーは n 個
Nn
A
Transaction Management / Distributed Database Management
Read-Locks-One のメッセージ数
• A のコピーを持つあるノード N にRLOCK A を要求
• N が RLOCK A を許さない場合、
他のノードに要求すべきか？
• RLOCK A の許可が下りないのは
WLOCK A が実行されている場合
• 他のサイトも RLOCK A は拒否するので、
少し待って RLOCK A
Transaction Management / Distributed Database Management
過半数ロック戦略
• WLOCK A (書きこみ専用ロック) を実行するには
A のコピーの過半数を WLOCK A すればよい
• RLOCK A (読取り専用ロック) を実行するには
A のコピーの過半数を RLOCK A すればよい
• A のコピーをもつ各ノードでは
- WLOCK がかかっていなければ RLOCK を許可
- RLOCK と WLOCK いずれもかかってなければ
WLOCK を許可
Transaction Management / Distributed Database Management
アイテム A にロックをかけようとする
任意のトランザクションを T1, T2
• T1, T2 は同時に A に WLOCK をかけられない
• T1 は RLOCK、T2 は WLOCK を同時にかけられない
• 唯一可能なのは T1 と T2 が同時に RLOCK すること
T1
T2
Transaction Management / Distributed Database Management
過半数ロック戦略のメッセージ数
• アイテム A のコピーが n 個ある場合
• (n+1)/2 以上のノードに WLOCK (or RLOCK) A を要求
• ロックと承認あわせて n+1 個以上のメッセージを送信
Transaction Management / Distributed Database Management
制御メッセージ数
WLOCK
RLOCK
Write-Locks-All
2n
2
過半数ロック戦略
n+1 以上
n+1 以上
トランザクションが２つの場合
Write-Locks-All deadlock する可能性大
過半数ロック戦略
どちらかは WLOCK を取れる
トランザクションが３つ以上の場合
過半数ロック戦略でも deadlock する可能性あり
Transaction Management / Distributed Database Management
過半数ロック戦略の一般化 k-of-n 戦略 (n/2 < k ≦ n)
• WLOCK A (書きこみ専用ロック) を実行するには
A のk 個のコピーを WLOCK A すればよい
• RLOCK A (読取り専用ロック) を実行するには
A の (n-k)+1 個のコピーを RLOCK A すればよい
T1: WLOCK A
k個
Write-Locks-All
過半数ロック戦略
T2: RLOCK A
(n-k)+1 個
n-of-n 戦略
(n+1)/2-of-n 戦略
Transaction Management / Distributed Database Management
分散２相ロック
Transaction Management / Distributed Database Management
アイテム A のサイト S1, S2 でのコピーを A1, A2
T
T1
WLOCK A1
UNLOCK A1
T2
WLOCK A2
UNLOCK A2
U
U1
WLOCK A1
UNLOCK A1
U2
WLOCK A2
UNLOCK A2
Write-locks-all で各コピーをロック
（同時にコピーを更新できない例）
T1
S1
U1
T2
U2
WLOCK A1
UNLOCK A1
WLOCK A1
UNLOCK A1
T1 → U1
WLOCK A2
UNLOCK A2
WLOCK A2
UNLOCK A2
U2 → T2
S2
Transaction Management / Distributed Database Management
サブトランザクション (例えば T1, T2) の同期が必要
• サブトランザクション全体での２相ロックプロトコルを考える
必要がある
• すべてのサブトランザクションが必要なアイテムを LOCK
した後に、UNLOCK を開始するように制御したい
• 分散合意問題 (distributed agreement problem)
• COMMIT を使った強２相ロックプロトコル方式による解法
Transaction Management / Distributed Database Management
COMIMIT を使った強２相ロックプロトコル方式による解法
T
U
T1
T2
U1
U2
WLOCK A1
COMMIT
UNLOCK A1
WLOCK A2
COMMIT
UNLOCK A2
WLOCK A1
COMMIT
UNLOCK A1
WLOCK A2
COMMIT
UNLOCK A2
• すべてのサブトランザクションが COMMIT に達した時点で、
トランザクション全体がコミットしたと考える
• 分散コミットメント（後に説明）により全サブトランザクション
の合意を確認
Transaction Management / Distributed Database Management
強２相ロックプロトコル方式での deadlock 問題
（アイテム A, B はコピー持たないものの deadlock が起こる）
T
T1
WLOCK A
COMMIT
UNLOCK A
T2
WLOCK B
COMMIT
UNLOCK B
T1
U1
U
U1
WLOCK A
COMMIT
UNLOCK A
T2
WLOCK A
COMMIT
UNLOCK A
U2
WLOCK B
COMMIT
UNLOCK B
U2
WLOCK B
COMMIT
WLOCK A
COMMIT
UNLOCK A
WLOCK B
COMMIT
UNLOCK B
deadlock
UNLOCK B 状態
Transaction Management / Distributed Database Management
分散データベース環境での deadlock 回避
アイテムへの全順序の導入
• アイテムに全順序を入れる
• トランザクションは、すべてのサブトランザクションが全
順序に従ってアイテムにロックをかけるように調整
Transaction Management / Distributed Database Management
T
T1
WLOCK A
T2
COMMIT
UNLOCK A
WLOCK B
COMMIT
UNLOCK B
T1
U1
WLOCK A
COMMIT
UNLOCK A
WLOCK A
COMMIT
UNLOCK A
U
U1
WLOCK A
COMMIT
UNLOCK A
T2
U2
WLOCK B
COMMIT
UNLOCK B
U2
WLOCK B
COMMIT
UNLOCK B
WLOCK B
COMMIT
UNLOCK B
Transaction Management / Distributed Database Management
分散データベース環境での deadlock 回避
時間切れ方式
• 待ち時間に上限値を設け、時間切れしたトランザクション
は abort
• 待ち時間の上限値の調節
- deadlock 状態にあるトランザクションが不必要に
アイテムをロックし続けない程度に短くする
- deadlock 状態にないトランザクションを不必要に
abort させない程度に長くする
• 制御メッセージの通信を伴わない
Transaction Management / Distributed Database Management
分散データベース環境での deadlock 回避
Waits-for-Graphs
T1
U1
T2
U2
WLOCK A
COMMIT
UNLOCK A
T
WLOCK B
COMMIT
WLOCK A
COMMIT
UNLOCK A
WLOCK B
COMMIT
UNLOCK B
U
T
T
U
deadlock
UNLOCK B 状態
U
Transaction Management / Distributed Database Management
分散コミットメント
Transaction Management / Distributed Database Management
分散データベースでのトランザクション
分散した計算機上で動作する
複数の部分トランザクションにより実行される
部分トランザクションの中から調整役 (coordinator)
を選ぶ
その他を参加者 (participants) と呼ぶ
Transaction Management / Distributed Database Management
全参加者がコミットを表明する場合、全体としてもコミット
ある参加者がアボートを表明する場合、全体としてもアボート
参加者は
参加者 i
• vote-commit
(コミットの表明)
または
投票
決定
• vote-abort
(アボートの表明)
を調整役に送信
調整役
調整役は
• 全参加者が
vote-commit の場合は
全参加者に commit を
送信し、全体としてコミット
することを伝える
• ある参加者が
vote-abort の場合は
全参加者に abort を
送信し、全体としてアボート
することを伝える
投票の後に決定を下す２つの相からなるので
２相コミット (two-phase commit) とよぶ
Transaction Management / Distributed Database Management
vote-commit 送信
参
加
者
初期状態
vote-abort 送信
または
abort 受信
すべての参加者から
vote-commit を受信
調
整
役
コミット
宣言中
commit 受信
コミット
終了
abort 受信
アボート
終了
コミット
処理中
commit 送信
コミット
終了
初期状態
ある参加者から
vote-abort を受信
アボート
処理中
abort 送信
アボート
終了
Transaction Management / Distributed Database Management
vote-commit 送信
参
加
者
コミット
宣言中
コミット
終了
abort 受信
初期状態
vote-abort 送信
または
abort 受信
commit 受信
アボート
終了
ブロック状態
参加者 T がコミット宣言中に調整役から commit, abort
いずれのメッセージも受信しない状態。
通信路の信頼性に対する不安
勝手に先に進むと問題が発生。
Transaction Management / Distributed Database Management
参加者 T がブロック状態で勝手に先に進むと微妙な問題が発生
勝手にコミット終了へ進むとき
•
•
•
•
T はコミット後に、アイテム A の値を更新
T が更新した A の値を、ある参加者 T’ が読む
他の参加者がアボートを宣言し、全体がアボート
T’ はアイテム A を Dirty Read したことになる
vote-commit 送信
コミット
宣言中
Ｔ以外は
abort 受信
初期状態
vote-abort 送信
または
abort 受信
Ｔは勝手に進む
アボート
終了
コミット
終了
T が A へ書きこみ
T’ がDirty Read
Transaction Management / Distributed Database Management
勝手にアボート終了に進むとき
• 調整役が全参加者から vote_commit の受信を確認後に、
T と調整役の通信が切断されたと仮定
• 調整役からの commit は T 以外の参加者には送信され、
これらの参加者は A のローカルコピー値を更新
• しかし T だけは commit の知らせが入らず、
勝手にアボートするので、 A を更新しない
• T とその他の参加者で A のローカルコピー値が
同一でなくなる
vote-commit 送信
初期状態
vote-abort 送信
または
abort 受信
コミット
宣言中
Ｔ以外は
commit 受信
T は勝手に進む
アボート
終了
コミット
終了
Transaction Management / Distributed Database Management
コミット宣言中の参加者 T がブロック状態から抜け出るには
調整役ではなく、他の参加者に助けを求める (help-me 送信)
• コミット終了状態の参加者は、全体がコミットしたことを知る
T に commit を送信
• アボート終了状態の参加者は、全体がアボートしたことを知る
T に abort を送信
• 初期状態にある参加者は、アボートすることで、全体を
アボートさせ、ブロック状態から抜け出る状況をつくれる
調整役には vote-abort を送信
T には abort を送信
• コミット宣言状態の参加者は、同じブロック状態にあり、
状況を変えられない
Transaction Management / Distributed Database Management
参加者
vote-commit 送信
初期状態
vote-abort 送信
または
abort 受信
commit 受信
コミット
宣言中
abort 受信
アボート
終了
abort 受信
時間切れ
コミット
終了
ブロック
状態
help-me 送信
救助を
待つ
commit 受信
Transaction Management / Distributed Database Management
help-me を送信した参加者は矛盾した情報を受信しない
• 調整役が最終的に abort を送信する場合、
commit を受信しない
仮に commit を受信すれば、全体がコミットしたことを知る参加
者から受信するので矛盾
• 調整役が最終的に commit を送信する場合、
abort を受信しない
仮に abort を受信すれば、全体のアボートを知る参加者から
の受信か、初期状態の参加者 T’ が abort を決断した場合。
後者の場合、調整役は初期状態ののち、T’ から abort を受信し、
最終的に abort を送信。矛盾。
• commit と abort を同時に受信しない
Transaction Management / Distributed Database Management
その他の修正
• help-me を使う場合、各参加者が
助けを求める参加者リストを知る必要がある
•初期状態の前に参加者リストを知らせる begin-vote
メッセージを全参加者に送信
調整役
すべての参加者から
vote-commit を受信
begin-vote
送信
初期状態
コミット
処理中
commit 送信
コミット
終了
待ち状態
時間切れ
または
ある参加者から
vote-abort を受信
アボート
処理中
abort 送信
アボート
終了
Transaction Management / Distributed Database Management
その他の修正
• ２相コミット開始時に、参加者と調整役との通信が
確立しない場合はアボートする
• 参加者の場合 begin-vote の受信が時間切れになると
アボートする
• 調整役の場合、参加者から vote の受信が時間切れに
なるとアボートする
vote-commit 送信
考察中
Begin-vote
受信
vote-abort 送信
または
abort 受信
初期状態
時間切れ
参加者
commit 受信
コミット
宣言中
コミット
終了
時間切れ
abort 受信
ブロック
状態
アボート
終了
help-me 送信
abort 受信
救助を
待つ
commit 受信
Transaction Management / Distributed Database Management
vote-commit 送信
考察中
Begin-vote
受信
vote-abort 送信
または
abort 受信
初期状態
時間切れ
参加者
commit 受信
コミット
宣言中
コミット
終了
時間切れ
abort 受信
ブロック
状態
アボート
終了
help-me 送信
abort 受信
救助を
待つ
commit 受信
ここでブロック状態に陥るケース
Transaction Management / Distributed Database Management
調整役
vote-commit を送信
直後に回線が切断
commit 送信
この参加者は
commit の先に
進み、データ
ベースを更新して
よいのか？
調整役
commit を受信しない.
help-me を出しても
ブロック状態から抜けない
一部の参加者だけが commit を知る状況
Transaction Management / Distributed Database Management
３相コミット
• ２相コミットはデータベース製品で普及しているが、
ブロック状態に陥る可能性が残っている
• ２相コミットは、全参加者が vote-commit した後は、
commit するプロトコル
• ３相コミットは、全参加者が vote-commit した後に、
全参加者が「全参加者が vote-commit したこと」
を知ったのち commit するプロトコル
• メッセージ通信コストが高く、現実には殆ど使われていない

Download Report