データベース

第６章トランザクション管理
６．１トランザクションの概念
６．２同時実行制御
６．３障害回復
６．２同時実行制御
１．同時実行制御の必要性
トランザクションを逐次実行すれば問題は生じな
いが、性能が低下してしまう。
並行処理をしながら問題が生じないように管理す
る（同時実行管理）。
同時実行で生じる問題
逐次実行では・・・
【トランザクション1】
begin
read(A)
write(A:=A‐10)
end
T1:
T1:
T2:
T2:
read(A)
write(A:=A‐10)
read(A)
write(A:=A‐20)
DB
【トランザクション2】
begin
read(A)
write(A:=A‐20)
end
T1:A=100
T1:A=90 → DB:A=90
T2:A=90
T2:A=70 → DB:A=70
同時実行で生じる問題
並列実行では・・・
【トランザクション1】
begin
read(A)
write(A:=A‐10)
end
T1:
T2:
T1:
T2:
read(A)
read(A)
write(A:=A‐10)
write(A:=A‐20)
DB
【トランザクション2】
begin
read(A)
write(A:=A‐20)
end
T1:A=100
T2:A=100
T1:A=90 → DB:A=90
T2:A=80 → DB:A=80
両者の比較
並列処理
逐次処理
①T1:A=100
②T2:A=100
③T1:A=90 → DB:A=90
④T2:A=80 → DB:A=80
①T1:A=100
②T1:A=90 → DB:A=90
③T2:A=90
④T2:A=70 → DB:A=70
結果が異なるので隔離性が保たれていない
２.直列化可能性と隔離性のレベル
(a) 直列化可能性
逐次処理の順序で結果が異なるケースもあるが、
これは構わない
（どちらかの結果と等しければ正しい：直列化可能性）。
【トランザクション1】
begin
read(A)
write(A := 2 * A)
end
【トランザクション2】
begin
read(A)
write(A := 2 + 100)
end
T1→T2
T2→T1
T1:A=100 → DB: 200
T2:A=200 → DB: 300
T2:A=100 → DB: 200
T1:A=200 → DB: 400
スケジュールの考え方
① それぞれのトランザクションの基本操作の順序を保存し、
いくつかのトランザクションを並べたものを１列に並べたも
のをスケジュールという。
② 逐次実行するスケジュールを直列スケジュールという。
③ 等価な直列スケジュールが存在するとき直列化可能という。
直列化可能ということ
① 同じデータにアクセスしない複数のトランザクションをどの
ように実行しても直列化可能である。
② 更新を行わないトランザクションの場合、どのように実行し
ても直列化可能である。
③ 同一データを更新する場合、一般には直列化可能でない
が、処理によっては直列化可能な場合がある。
(b) 隔離性のレベル
３種類の異常
① ダーティリード（dirty read）
トランザクション中で更新され、未だコミットして
いないデータ。他のトランザクションが更新した
ダーティデータを読むこと。
異常度合いが高い
② 繰り返し不能リード（unrepeatable read）
トランザクション中で同一タプルデータを複数
回読んだとき、同じ結果が保証されないこと。
③ ファントム（phantom:まぼろし）
トランザクション中で同じ条件の読込みを複数
回行った場合、同一のタプル集合イガイガ読ま
れること。（１回目には読み込まれたタプルが２
回目に存在しない）
異常度合いが低い
SQLの４つの隔離性のレベル
① 未コミットリード
ダーティリードなど上記すべてのリードが起きる可能性がある（読込
みだけのトランザクションでのみ使用）
② コミットリード
ダーティリードは起きないが、繰り返し不能リードがおきる可能性が
ある。
③ 繰り返し可能リード
繰り返し不能リードは起きないが、ファントムが起きる可能性がある。
④ 直列化可能
上記のどの異状も起きず、直列化可能性が保証される。
(c) 競合グラフによる直列化可能性の判定
① 読込みだけのトランザクションではデータベース内容を更新しない
ので、読込み同士の順序が入れ替わっても問題は生じない。
② ２つのトランザクションが書き込みを含む組合せの動作行うと問題
が生じる可能性がある。
この２つの性質を利用した競合グラフ
競合グラフ
① グラフのノードはトランザクションであり、１つのトランザクションを１つの
ノードで表現する。
② 同じ対象に２つのトランザクションが書込みを含む組合せでアクセスする
とき、スケジュールで先にアクセスするトランザクションから他方に有向
エッジ（矢印）を張る。
③ 同一対象に同じトランザクションが複数回アクセスし、アクセス順序が逆
になるケースが生じるときは、逆方向にも有向エッジを張る。
【判定に関する定理】
スケジュールの競合グラフが非巡回（ループがない）ならば、
直列化可能である。
例
【巡回のある競合グラフ】
T1
【巡回のない競合グラフ】
T2
T1
T1
T2
T2
T3
T3
３．ロックによる同時実行制御
(a) ロッキング
【ロッキングの基本プロトコル】
①対象データにアクセスするときはロック（lock:施錠）する。
②他のトランザクションがすでに対象データをロックしていたら、
ロックが解除されるまで待たされる。
③ロックが不要になったらそれを解除（unlock）する。ロックが
解除されたら、待っていたトランザクションのロックが許可さ
れる。
ロックと解除待ち
【トランザクション２】
【トランザクション１】
lock A
②
①
④
Aを処理
unlock A
A
③
⑤
lock A
（待ち状態）
実行再開
Aを処理
unlock A
アクセス後すぐロックを解除するとうまくいかない
T1: lock (A)
T1: read(A)
T1: unlock(A)
A =100（初期値）
T2: lock(A)
T2: read(A)
T2: unlock(A)
T1: lock(A)
T1: write(A := 2 * A)
T1: unlock(A)
A=100（初期値）
A=200
T2: lock(A)
T2: write(A := A + 100)
T2: unlock(A)
A=200
対象データ処理が終わるまでロックを解除しない
T1: lock (A)
T1: read(A)
A =100（初期値）
T2: lock(A)
（ロック解除待ち）
T1: write(A := 2 * A)
T1: unlock(A)
A=200
T2:(実行再開）
T2: read(A)
T2: write(A := A + 100)
T2: unlock(A)
A=200
A=300
対象データが複数の場合，
直列化可能でないケースが生じる
T1:
T1:
T1:
T1:
lock (A)
read(A)
write(A := 2 * A)
unlock(A)
A = 100（初期値）
A = 200
T2:
T2:
T2:
T2:
T2:
T2:
T2:
T1:
T1:
T1:
T1:
lock(B)
read(B)
write(B := 2 * B)
unlock(B)
lock(A)
lock(B)
read(A)
read(B)
write( B := A + B)
unlock(A)
unlock(B)
A = 200
B = 10（初期値）
B = 210
B = 210
B = 420
【保守的ロッキング法】
トランザクション開始時に必要なデータをすべてロックする
T1: lock (A)
T1: lock (B)
T1: read(A)
A = 100（初期値）
T2: lock(A)
T2: lock(B)
T1:
T1:
T1:
T1:
T1:
write(A := 2 * A)
read(B)
write(B := 2 * B)
unlock(A)
unlock(B)
待ち状態
待ち状態
A = 200
B = 10 （初期値）
B = 20
T2:
T2:
T2:
T2:
T2:
T2:
T2:
A待ち状態解除
B待ち状態解除
read(A)
read(B)
write( B := A + B)
unlock(A)
unlock(B)
A = 200
B = 20
B = 220
(b) 2相ロッキング法
保守的ロッキングでは直列化可能性が保証できるが，
ロッキング時間が長くなり並列処理度が低下する。
トランザクションはロックを解除した後は，別の対象デー
タであってもロックを行うことができないものとする。
すなわち，１つのトランザクションで1回だけロック解除
するものとする。これを2相ロッキング法という。
2相ロッキング法の適用例
T1: lock (A)
T1: read(A)
A = 100（初期値）
T2: lock(A)
T1:
T1:
T1:
T1:
T1:
write(A := 2 * A)
lock(B)
read(B)
write(B := 2 * B)
unlock(A, B)
待ち状態
A = 200
B = 10 （初期値）
B = 20
T2:
T2:
T2:
T2:
T2:
T2:
A待ち状態解除
lock(B)
read(A)
read(B)
write( B := A + B)
unlock(A, B)
A = 200
B = 20
B = 220
ロールバックする場合
2相ロッキング法でも問題が生じる
したがって，
ロック解除は，
トランザクションのコミットまたは
ロールバックまで待ってから行う
(c) ロックの種類
読込みだけのトランザクションの場合，
直列化可能性は保証される。
読込み専用のロック（共有ロック：Ｓロック）と
書込み用を含むトランザクション用のロック（占
有ロック：Ｘロック）を分ける。
ロックの両立性
共有ロックがかかっている場合
①他のトランザクションが共有ロックを要求したら許
可する。
②他のトランザクションが占有ロックを要求したら待
たされる。
占有ロックがかかっている場合
いずれのロックも待たされる。
ロッキング単位（粒度）
（データベース内は階層構造になっている）
①小さな単位でロッキングする方が，並列処理度
が向上する。
②小さな単位でロッキングすると，ロッキング回
数が増える。
③上位の単位でのロックと下位の単位でのロック
の両立性が重要である。
(d) デッドロック
以下の例では，T1,T2共に待ち状態になってしまう。
T1: lock(A)
T2: lock(B)
T1: lock(B)
(待ち状態）
T2: lock(A)
(待ち状態）
デッドロック対策
①事後対策法（関連するトランザクションの１つをロール
バックする）
・待ちグラフ法
・タイムアウト法
②予防法（デッドロックが起きないようロッキング法を変
更する）
・ロッキング適用に制限を設ける。
・デッドロックが発生しない保守的ロッキング法を
適用。
・ロックをかける順番を付けておく方法。
・トランザクション開始時刻によってトランザクション
の優先度を管理する方法。
待ちグラフ法
①各トランザクションをノードとするグラフを作る。
②あるトランザクションが待ち状態に入ったら，そ
のトランザクションのノードと相手のトランザク
ションへの有効エッジを追加する。
③上記②の結果，そのグラフに巡回が生じたらデッ
ドロックと判定する。
④デッドロックと判定されたら，巡回している経路
中のいずれかのトランザクションを強制的にロー
ルバックする。
タイムアウト法
トランザクションの待ち時間が一定時間を超えたら
デッドロックと判定する方法。
デッドロックでない場合もデッドロックと判定され
る場合がある。
４．その他の方法
(a) タイムスタンプ法
以下によって直列化可能性が保証される。
①トランザクション開始順に一意的なタイムスタン
プを付ける。
②対象データにreadとwriteのそれぞれに，その
データにアクセスしたトランザクションのタイ
ムスランプの最大値を記録する。
③タイムスタンプの順序が競合し，両立しないアク
セス（たとえばwriteの最大タイムスランプより
トランザクション開始時間が早い場合）を検出
してトランザクションをロールバックする。
(b) 楽観的制御法
データベースの使用環境によっては，
実際には競合がほとんどおきないとき
①トランザクション実行に競合が起きないものと仮
定し自由に行う。
②トランザクション終了時に競合があったかを判定
し，競合がなければ正常終了，あればロール
バックを行う。
③データベースへの書込みを保留し，終了時に実際
の書込みを行う。

Download Report