Document

3.4 原子動作 Atomic Action
トランザクション transaction
 3.4.1 並行制御
 3.4.2 回復処理
 3.4.3, 3.4.4 原子コミット

 コンセンサスの応用

3.6.3 RAID
トランザクション
T1:
Read(A, X1);
Read(B, Y1);
Y1 := Y1 + 50000;
X1 := X1 – 50000;
Write(A, X1);
Write(B, Y1);
T2:
Read(B, X2);
Read(A, Y2);
Y2 := Y2 + 20000;
X2 := X2 – 20000;
Write(B, X2);
Write(A, Y2);
50000
A 100000
B 100000
20000
Read(A, X1);
Read(B, Y1);
Y1 := Y1 + 50000;
X1 := X1 – 50000;
Write(A, X1);
Write(B, Y1);
50000
A 50000
Read(B, X2);
Read(A, Y2);
Y2 := Y2 + 20000;
X2 := X2 – 20000;
Write(B, X2);
Write(A, Y2);
B 100000
20000
Read(A, X1);
Read(B, Y1);
Read(B, X2);
Read(A, Y2);
Y2 := Y2 + 20000;
X2 := X2 – 20000;
Write(B, X2);
Y1 := Y1 + 50000;
X1 := X1 – 50000;
Write(A, X1);
Write(B, Y1);
Write(A, Y2);
50000
A 120000
B 150000
20000
ACID

原子性 Atomicity
 トランザクションの最後は，コミットかアボート

コミット


データ操作をデータベースに反映
アボート

データ操作を取り消し
一貫性 Consistency
 分離性 Isolation
 持続性 Durability

3.4.1 並行制御

並行実行
 パフォーマンスのため不可欠

分離性 Isolation
 逐次的に実行されたようにみえること．

直列化 Serialization
 分離性を実現すること
現在のモード
2相ロッキング

考えるコマンド
要 SLOCK
求 XLOCK
SLOCK
XLOCK
両立
競合
競合
競合
共有ロック
 XLOCK 排他ロック
 READ
SLOCK，ＸLOCKが必要
 WRITE
XLOCKが必要
 UNLOCK
SLOCK，ＸLOCKが必要
 SLOCK

ルール
 UNLOCK以降は，SLOCK,
XLOCKできない
2相ロッキングにおけるロックの数の
推移
Shrink(T1)
ロックの数
T1
(a)
Shrink(T2)
T2
時間
XLOCK A;
XLOCK B;
Read(A, X1);
Read(B, Y1);
Y1 := Y1 + 50000;
X1 := X1 – 50000;
Write(A, X1);
Write(B, Y1);
UNLOCK B;
XLOCK B;
Read(B, X2);
UNLOCK A;
XLOCK A;
Read(A, Y2);
Y2 := Y2 + 20000;
X2 := X2 – 20000;
Write(B, X2);
Write(A, Y2);
ULOCK B;
ULOCK A;
うまくいく理由

TiとＴjの順序が問題となる場合
 TiとTjが同じデータ項目Aを操作


ただし，READ-READの場合はのぞく
規則により，Aへの操作順は
 Shrink(Ti)
< Shrink(Tj)ならTi, Tjの順
 Shrink(Ti) > Shrink(Tj)ならTj, Tiの順


Ti, Tjの少なくとも一方は，XLOCKが必要な点に注意
結局，Shrinkの順番で逐次的に実行された
のと同じ
２相ロッキングの問題
1.
デッドロック
XLOCK A;
Read(A, X1);
XLOCK B;
Read(B, Y1);
．．．
XLOCK B;
Read(B, X2);
XLOCK A;
Read(A, Y2);
．．．
２相ロッキングの問題
2.
アボートした場合， WRITE後に，UNLOCK
した項目を，他のトランザクションが読み出
している場合がある．

次のトランザクションもアボートしないといけな
い
READ
ロックの数
時間
(a)
厳密２相ロッキング

コミットしてから，UNLOCKする
ロックの数
ロックの数
時間
(a)
時間
(b)
3.4.2 回復処理

故障した場合でも，データベースにトランザク
ションを反映
 Durability

主記憶上のキャッシュの問題
Write
Write
主記憶
主記憶
Data
ディスク
Data
後でディス
クに記録
ディスク
Data
故障→不整合の可能性
Data
低性能
Write
ログ
主記憶
Data
Data
Write
…
…
ディスク
Data
redo, undo
故障→不整合の可能性
コミット済→リドゥ (redo) = 固定化
コミット前→アンドゥ (undo) = 無効化
ログが主記憶に保存された場合
Write
ログ
主記憶
Data
Data
Write
…
…
後でディス
クに記録
ディスク
Data
ログが消えてしまう
WAL(Write Ahead Log)プロトコル
Write
ログ
主記憶
Data
Write
…
…
Data
2
ディスク
Write
…
Data
…
１
ログの先書き
•コミット直前
→ redoのため
•コミット前の書出し
→ undoのため
3.4.3 原子コミット
複数サイト上での同一トランザクションの実行
 全サイトが，コミットかアボートか一致しないと
いけない

トランザクション
コミットかアボートを決定
P1
コミットかアボートを決定
P2
コミットかアボートを決定
P3
原子コミット
プロセス={P1, P2, …}
 Pi (i=1,2,..): propose(vi), vi = Yes or No
 Pi (i=1,2,..): decide(wi), wi = Commit or Abort
 条件

 停止性
 一律合意:
wi = w j
 正当性: wi = Commit ⇒ 全Piでvi = Yes
 義務: 故障がないとき，全Piでvi = Yes⇒ wi = Commit
 義務（非同期）:故障が推測されなかったとき，全Piでvi
= Yes⇒ wi = Commit
2相コミット
すべてYes → コミット
それ以外 → アボート
トランザクション
投票要求
コミットかアボートを決定
P1
Yes or No
P2
P3
Yes or No
Phase 1
Phase 2
故障の場合１
トランザクション
P1
P2
P3
!
No abort
!
No abort
タイムアウトしてアボート
故障の場合２
トランザクション
投票要求
P1
Yes or No
!
アボートを決定
P2
abort
P3
abort
Phase 1
Phase 2
故障の場合3
トランザクション
投票要求
コミットかアボートを決定
P1
Yes or No
P2
P3
commit/abort
!
Yes
Phase 1
Phase 2
コミット?
アボート?
P2に聞きに行くことが必要
ブロックされる場合
コミットかアボートを決定
投票要求
P1
Yes/No
P2
P3
P4
P5
Yes
?
Yes
?
Yes
停止性がみたされない
?
非ブロッキング原子コミット

3相コミットプロトコル (by D. Skeen)
 複雑

コンセンサスを用いたプロトコル
 コンセンサス問題を解くアルゴリズムがあると仮
定
コンセンサスを用いたプロトコル
Yes/Noを全プロセ
スに送信
P1
コンセンサス問題を
解く
Commit/Abort
P2
Commit/Abort
P3
Commit/Abort
Yes or No
a. Noを受信，もしくは故障を推測
• propose(アボート)
b. すべてYes
• propose(コミット)
Yes/Noを全プロセ
スに送信
P1
コンセンサス問題を
解く
Commit/Abort
P2
Commit/Abort
P3
Commit/Abort
Yes or No
a. Noを受信，もしくは故障を推測
• propose(アボート)
b. すべてYes
• propose(コミット)
• 停止性
• 一律合意: wi = wj
• 正当性: wi = Commit ⇒ 全Piでvi = Yes
• 義務（非同期）:故障が推測されなかったと
き，全Piでvi = Yes⇒ wi = Commit
停止性：故障状況1
Yes/Noを全プロセ
スに送信
P1
コンセンサス問題を
解く
Commit/Abort
P2
Commit/Abort
P3
Commit/Abort
Yes or No
コンセンサス問題を
解くアルゴリズムが
うまく動けばＯＫ
a. Noを受信，もしくは故障を推測
• propose(アボート)
b. すべてYes
• propose(コミット)
停止性：故障状況2
Yes/Noを全プロセ
スに送信
P1
!
コンセンサス問題を
解く
Commit/Abort
propose
(アボート)
P2
P3
Yes or No
propose
(コミット)
Commit/Abort
Commit/Abort
a. Noを受信，もしくは故障を推測
故障を(まちがっても
• propose(アボート)
よいので)推測できれ
b. すべてYes
ばよい
• propose(コミット)
3.6.3 RAID (Redundant Array of
Inexpensive Disks)

Striping
記憶領域をStripeに分割し，複数のディスクに分散
させること
 負荷の分散
 低いコストでのFault Toleranceの実現
RAID-0 Striping
Controller
D0
D3

D1
D4
D2
D5
長所
 アクセスの並列化による性能の向上

短所
 Non-Fault

Tolerance
Usable Storage Capacity Percentage = 100%
RAID-1 Mirroring
Controller
D0
D1
D0
D1
同一のデータをN台のディスクで保持

長所
 高いFault

tolerance (N-1台のfailure)，高速な読み出し
短所
 低い利用効率，低速な書き込み

Usable Storage Capacity Percentage = 100/N %
RAID-4
Controller
D0
D3
D1
D4
D2
D5
P0~2
P3~5
N

長所
 高い利用効率，高速な読み出し,

Disk 1台のfaultをmask
短所
Parityディスクへのアクセスの集中による書き込みの低速化

Usable Storage Capacity Percentage
= 100*(N-1)/N %
RAID 5
Controller
D0
D3
D1
D4
D2
P3~5
P0~2
D5
パリティを全ディスクに分散

長所
 高い利用効率，高速な読み出し・書き込み,
faultをmask

Usable Storage Capacity Percentage
= 100*(N-1)/N %
Disk 1台の

Download Report