13. 同時実行制御

13. 同時実行制御
講師：大川昌弘
[email protected]
更新日: 2014/07/06
1
トランザクション処理
• データベースに対する処理（参照・更新等）を
確定する、あるいは取り消す
– 例：別の銀行口座へ10,000円振り込む処理
1. 振り込み元の口座から10,000円を引く
2. 振り込み先の口座に10,000円を足す
3. 確定する、あるいは取り消す
• 上記の処理1と2は、両方とも確定されるか、
取り消される。そういった、まとまった処理を
作業単位(Unit Of Work: UOW)、または、
トランザクションと呼ぶ
2
トランザクション処理で必要とされる
4つの特性
• ACID特性
– 原子性(Atomicity)
• 個々のトランザクションは、全体として実行される（確定する）か、実行されな
い（取り消す）かのどちらか
– 一貫性(Consistency)
• 整合性がとれたデータベースに対して実行されたトランザクション実行後の
データベースの状態は、再び整合性がとれたものとなる
– 分離性、独立性、隔離性(Isolation)
• 複数のトランザクションを並行処理しても、それぞれのトランザクションは他の
トランザクションの影響を受けず、その結果はトランザクションを何等かの順
序で処理した場合と一致する
• 分離レベル(Isolation Level)の設定ができ、それにより動きが変わる
– 永続性(Durability)
• 確定されたデータは、失われることのない永続的なものとしてデータベースに
記録される
（とは言っても、記録されている媒体（ハードディスク等）に障害が発生したら
失ってしまうため、定期的なバックアップが必要となる）
3
トランザクション
• トランザクションの確定(コミット:commit)
– COMMIT文によるCOMMIT処理
• 「トランザクションをコミットする」という
• トランザクションの取り消し(アボート:abort)
– ROLLBACK文によるROLLBACK処理
• トランザクションの開始状態に戻すこと
• 「トランザクションをアボートする」、「アボートしてロールバッ
ク処理を行う」、「ロールバックする」などという
• 誤った値を確定してしまった場合
– 正しい値で再度更新する
• 補償トランザクション(compensating transaction)
4
同時実行制御
• データベースに対して複数のユーザーがアク
セスすることができる
– 複数のトランザクションが同時に実行される
– 複数のトランザクションが同じレコードを更新する
ケースもある
– うまく制御しないとさまざまな異常が発生し得る
5
トランザクション処理の異常
• 遺失更新異常(lost update anomaly)
– 更新内容が失われる
• 不整合検索異常(inconsistent retrieval anomaly)
– 一貫性のないデータの取得により発生
• ちなみに
– 異常と言えば、悪い設計のデータベースで発生する異常
もある（「4. リレーショナルモデルと正規化」で説明）
• 更新異常 (update anomaly)
• 削除異常 (deletion anomaly)
• 挿入異常 (insertion anomaly)
6
遺失更新異常
(lost update anomaly)
例：サークルで使用している銀行口座Aに100,000円あった。
そこから、ほぼ同時に、部員のXさんが20,000円引き出し(T1)、
部員のYさんが30,000円引き出す(T2)
トランザクションT1
トランザクション
トランザクションT2
トランザクション
A=100,000 R1(A) (T1がデータAをRead)
R2(A)
A=100,000
A := A - 30,000
A=70,000
W2(A)
A=70,000
A=80,000 A := A - 20,000
A=80,000 W1(A) (T1がデータAをWrite)
C1 (T1がCOMMIT)
C2
上記の例では、100,000円から50,000円(20,000+30,000) 引き出したのにもかかわらず、
残金が70,0000となる（T1の処理が反映されていない）
7
不整合検索異常
(inconsistent retrieval anomaly)
例：サークルで用途別に銀行口座AとBの2つを管理しており、それぞれ
50,000円あった。そこから、XさんがAからBに20,000円転送し(T1)、
YさんはAとBの合計金額をチェック(T2)
トランザクションT1
トランザクション
トランザクションT2
トランザクション
A=50,000 R1(A) (T1がデータAをRead)
B=50,000 R1(B)
A=30,000 W1(A := A – 20,000)
R2(A)
A=30,000
R2(B)
B=50,000
C=80,000
C := A + B
B=120,000 W1(B := B + 20,000)
上記の例では、銀行口座AとBの合計金額は100,000円であるのにもかかわらず、
T2が得た合計金額は 80,000円となる
8
直列可能性
• 前ページで述べた異常は、以下のように行うと
発生しない
– T1のすべての処理を先に行い、その後T2を行う
– あるいは、その逆
• 異常が発生しないための1つの基準
– トランザクションT1, …, Tn を並列処理したときの実行
結果が、それらを何等かの順序で逐次処理したとき
の実行結果と一致すること
直列可能性
9
スケジュール
• 各トランザクションの処理順序を定義
– 例:
トランザクションT1
トランザクション
トランザクションT2
トランザクション
R1(A) (T1がデータAをRead)
R2(A)
A := A - 20,000
A := A - 30,000
W1(A) (T1がデータAをWrite)
W2(A)
C1 (T1がCOMMIT)
C2
– 上記のスケジュールは、以下のように表される
• R1(A)R2(A)W1(A)W2(A)C1C2
– ROLLBACKはA (Abort) で表す。T2がアボートした場合、A2
10
アボート時の回復
• 回復可能
– Wj(x)によって書かれた値をRi(x)で読む場合、Cj
がCiに先行する場合、回復可能であるという
• 例:
– S: W1(A)R2(A)C2A1
• T2は、T1によって書かれた値を読んでコミットしている
が、その後、T1はアボートしている。つまり、T2はア
ボートされた値を使用してコミットしている
• 通常、処理結果に応じて、コミットかアボートを行うの
で、両方のケースを考慮する必要がある
19
ロックを用いた同時実行制御
• 他のトランザクションのアクセスをブロックする
• 2種類のロック
– 共有ロック（S(Shared)ロック、読み出しロック）
• データをREADする際にかけるロック
• このロック中、
– 他のトランザクションで同じデータをREADしても問題ない
– 他のトランザクションで同じデータをWRITEする場合、ロック解除
待ち
• ロック解除のタイミングは分離レベルに応じて変わる
– 専有ロック（X(eXclusive)ロック、書き込みロック）
• データをWRITEした場合、COMMITかROLLBACKするまで、他
のトランザクションからのアクセスをブロック
24
共有(S)ロックと専有(X)ロック
• データをREADする際、Sロックをかける
– 既にSロックがかかっていてもOK
– 既にXロックがかかっていたら、アンロック待ち
• データをWRITEする際、Xロックをかける
– 既にSロックやXロックがかかっていたら、アンロック待ち
ロックをかける時点の状態
ロックをかける
種類
なし
共有(S)
共有
専有(X)
専有
共有(S)
共有
○
○
×
専有(X)
専有
○
×
×
○: ロックをかけて次の処理に進む
×: 既にかかっているロックの解除待ち
25
共有ロックと専有ロックの例
T1
T2
Aの値
の値,
の値ロック
100
W1(A=200)
Bの値
の値,
の値ロック
500
200, X1
R2(A)
ロック待ち
C1
200, S2
ロック待ち解除
R1(B)
500, S1
W1(A=300)
ロック待ち
C2
ロック待ち解除
26
分離レベル(隔離性水準)
– ＲＥＡＤＵＮＣＯＭＭＩＴＴＥＤ
• データを読む際にロックしない
• コミットされていないデータも読み取られる（汚読/ダーティーリード）
– ＲＥＡＤＣＯＭＭＩＴＴＥＤ
• コミット済みのデータを読みとる
– 他のトランザクションにより更新中のデータは、そのトランザクションがコ
ミットかアボートするのを待つ、あるいは、更新前にコミットされていた
データを読み取る
• 再度同じデータを読むと変更されているケースが発生（反復不可能読み取
り）
– ＲＥＰＥＡＴＡＢＬＥＲＥＡＤ
• 一度読み取ったデータは、再度読み取っても同じ値となる
• 他のトランザクションが追加したデータが、再度読み取った際に現れるケース
が発生（幻像読み取り/ファントムリード)
– ＳＥＲＩＡＬＩＺＡＢＬＥ
• 一度読み取ったデータは、再度読み取っても同じ値になり、かつ、幻像読み
取りも発生しない
27
分離レベルと発生し得る現象
分離レベル
現象汚読
(ダーティーリード）
ダーティーリード）
反復不可能
読み取り
幻像読み取り
(ファントムリード
ファントムリード)
ファントムリード
READ UNCOMMITTED
○
○
○
READ COMMITTED
×
○
○
REPEATABLE READ
×
×
○
SERIALIZABLE
×
×
×
○: 発生し得る
×: 発生しない
28
ロックの粒度
• ロックの粒度
– ロックの対象となる項目の大きさ
• 例:
– 表単位でロック
– レコード（行）単位でロック
• 特徴
– ロックの粒度を細かくすれば、
• 並列処理されるトランザクション同士の不必要な競合を減らすこ
とができる
• 大量のデータをアクセスする場合、大量のロック操作が必要
29
複数のロックの粒度を許す場合
• 一般的なリレーショナルデータベースの例
– ロックの粒度
• 表単位とレコード（行）単位
– トランザクションT1が表1のレコードR1を専有ロックしている場合、
トランザクションT2が表1の専有ロックを要求しても、認めること
はできない
トランザクションT2が表1に対して専有ロック要求
表1
R1
トランザクションT1が専有ロック(XL1)
– 表の1つ以上のレコードにロックがかけられている情報を、表の
ロック情報として保持
• インテンションロック(intention lock)
30
インテンションロック
• 共有インテンションロック(ISロック)
– 下位の項目を共有ロックする可能性を表すロック
• 専有インテンションロック(IXロック)
– 下位の項目を専有ロックする可能性を表すロック
• 共有・専有インテンションロック(SIXロック)
– 自身を共有ロックするとともに、下位の項目を専
有ロックする可能性を表すロック
31
デッドロック
T1
T2
Aの値
の値,
の値ロック
100
W1(A=200)
Bの値
の値,
の値ロック
500
200, X1
R2(A)
ロック待ち
C1
200, S2
ロック待ち解除
R1(B)
500, S1
W1(A=300)
ロック待ち
W2(B=800)
ロック待ち
デッドロック
T1とT2が共にロック待ちで身動きがとれない
32
デッドロック
• デッドロックが発生するスケジュールの例
– S: XL1(A)W1(A)XL2(B)W2(B)XL2(A)W2(A)XL1(B)W1(B)
• デッドロックの検出方法
– 待ちグラフによる方法
• TiがTjのロック解除待ちの時、有向エッジN(Ti)→N(Tj)
• 待ちグラフがサイクルを持つかどうかで判定
T1
T2
– タイムアウトによる方法
• タイムアウトしたら、デッドロックかどうかわからないが、アボートさ
せる
33
デッドロックを回避させる方法
• 一括ロックする
• データを順序付ける
– トランザクションを順序付ける
34
デッドロックを回避させる方法
• 一括ロックする
– トランザクション開始時に、必要のあるロックをす
べて行う
– 1つでもロックがかけれらなかったら、すべての
ロックを取りやめ、しばらく待って、再度トライ
– 保守的二相ロッキングプロトコルと呼ばれる
35
デッドロックを回避させる方法
• データを順序付ける
• デッドロックが発生するスケジュール
T2がT1のロック解除待ち
– S: XL1(A)W1(A)XL2(B)W2(B)XL2(A)W2(A)XL1(B)W1(B)
• 上記を順序付けた場合
T1がT2のロック解除待ち
– 各トランザクションはA, Bの順にロックをかける
– S: XL1(A)W1(A) XL2(A)W2(A) XL2(B)W2(B)XL1(B)W1(B) …
UL1(A)UL1(B)UL2(A)UL2(B)
36
デッドロックを回避させる方法
– トランザクションを順序付ける
• トランザクション開始時刻TS(Tx)が早いものを優先。遅いものは、
必要に応じてアボート
– 2つの方式 (Ti が Tj によってロック待ちになった場合)
• ウェイト・ダイ (wait-die) 方式
– TS(Ti) < TS(Tj) のとき: TiはTjがロックを解くまで待つ
– TS(Ti) > TS(Tj) のとき: Tiは既にTjにロックされていたらアボートする
• ワウンド・ウェイト (wound-wait) 方式
– TS(Ti) < TS(Tj) のとき: Tiは既にTjにロックされていたら、Tjをアボートさ
せる
– TS(Ti) > TS(Tj) のとき: TiはTjがロックを解くまで待つ
37
トランザクションの順序付けによる
デッドロックの回避例
– スケジュール
T2がT1のロック解除待ち
• S: XL1(A)W1(A)XL2(B)W2(B)XL2(A)W2(A)XL1(B)W1(B)
• トランザクションの順序付け
– T1 の開始がT2より早いので、T1 を優先
T1がT2のロック解除待ち
• ウェイト・ダイ (wait-die) 方式
– T2 が T1 のロック解除待ち → T2がアボートする
• ワウンド・ウェイト (wound-wait) 方式
– T2 が T1 のロック解除待ち → そのままロック待ちする
– T1 が T2 のロック解除待ち → T2をアボートさせる
38
時刻印を用いた同時実行制御
• 時刻印方式
– トランザクションの時刻印(開始時刻)
– 各データの時刻印
• RTS(x)
– これまでにxのreadを行ったトランザクションの時刻印のうち最大値
• WTS(x)
– これまでにxのwriteを行ったトランザクションの時刻印のうち最大値
– Readの場合
• TS(Ti) < WTS(x)
– 本来Tiが読みだすべきxは、writeにより失われているので、Tiはアボート
• それ以外
– Readして、RTS(x)=max(RTS(x), TS(Ti))
– Writeの場合
• TS(Ti) < RTS(x)
– 後のトランザクションが既にreadしているので、Tiはアボート
• TS(Ti) ≧RTS(x) かつ TS(Ti) < WTS(x)
– 後のトランザクションが既にwriteしているのでTiはアボード
• それ以外
– Writeして、WTS(x)=max(WTS(x), TS(Ti))
39
多版同時実行制御
• 各データの最新の値だけでなく、過去の値の変遷（履歴）を維持管
理
• データxの版xiが維持管理され、それぞれ次の時刻印を持つ
– RTS(xj)
• これまでにxjのreadを行ったトランザクションの時刻印のうち最大値
– WTS(xj)
• xjのwriteを行ったトランザクションの時刻印
• Ti の Read
– Tiはxの値として、WTS(xj)≦ TS(Ti) を満たす最大のWTS(xj)をもつxを
readし、RTS(xj)=max(RTS(xj),TS(Ti)) とする
• Ti の Write
– xjを WTS(xj)≦ TS(Ti) を満たす最大のWTS(xj)をもつxの版とする
• RTS(xj) ≦ TS(Ti)
– writeして新たな版xkを生成し、RTS(xk)=WTS(xk)=TS(Ti)
• RTS(xj) > TS(Ti)
– 後のトランザクションが既にwriteしているのでTiはアボート
40
多版同時実行制御の例
WTS(xj)≦ TS(Ti) を満たす最大のWTS(xj)
時間
T1
Aの値
の値,
の値 RTS, WTS
T2
版:A1
版:A2
版:A1(値=100)
RTS(A1)=5
WTS(A1)=5
6
TS(T1)=6
7
TS(T2)=7
8
R2(A) (値=100)
9
A=200
10
W2(A)
11
R1(A)
(値:100)
12
A=300
13
14
版:A2(値=200)
RTS(A2)=7
WTS(A2)=7
RTS(A1)=max(RTS(A1),
TS(T1))=7
版:A1
(RTS<=TS)
版:A1
版:A2
R2(A) (値=200)
W1(A)
版:A1
RTS(A1)=7
アボート
版:A1
(RTS>TS)
41
END
42

Download Report