Microsoft PowerPoint - db03-9.ppt

(1)

データベース論（第

8 回）：

トランザクションと障害時回復

北村泰彦

関西学院大学理工学部情報科学科

トランザクション

(transaction)

データベースに対する

応用プログラムレベルでの一つ

の

原子的作用

原子的

(at

omic)

それ以上分解できないこと

作用

(action)

データの

読み

(read)

，

書き

(write)

応用プログラム

レベル

論理的に意味のある操作レベル

SQL

レベルとは異なる

トランザクションの例

振替送金トランザクション A 氏（依頼人）が自分の口座から C 円（金額）を B 氏（受取人）の口座に振替送金する．もし A 氏の口座残高が C 円未満なら，残高不足であることを A 氏に伝えて終了．残高が C 円以上であれば送金する．トランザクション内の二つのデータベース更新 A 氏の残高から C 円を引き，それを新たな残高とする． B 氏の残高に C 円を加え，それを新たな残高とする．一貫性 (in tegrit y) データベース全体でデータの整合性がとれていること．例：残額の総和は一定．一貫性が保証されるように，トランザクションの原子性を定義する．

トランザクションの実行

トランザクション実行の三つのパターン

COMMIT

：完遂

ROLLBACK

：未遂

DBMS

による

ROLLBAC

K

：異常終了

(2)

トランザクションの状態遷移

ACID

特性

原子性

(Atomicity)

トランザクションは，それが全て行われるか，まったく行われないかのいずれかである．

一貫性

(Consistency)

トランザクションは結果データベースの一貫性を保証する．

隔離性

(Isolatio

n)

各々のトランザクションは他のトランザクションの影響を受けない．

耐久性

(Dur

ability)

コミットしたトランザクションが行ったデータベースの変化は，その後どのような障害が発生しても失われることはない．

障害時回復

目的：データベースの

一貫性

を保つ．

分類

トランザクション障害

(transaction fai

lure)

：

論理の誤

り

による異常終了．ト

ラ

ンザクションの

アボート

．応用

プログラムの

強制終了

．

デッ

ドロック

による強制終了．

システム障害

(system failure)

：

DB

MS,OS

の障害

．

停

電

．ディスク

か

らデータを読み出すことはできる．シス

テムは再起動される．

メディア障害

(media failure)

：

二次記憶装置の障害

．

ディスクからデータの読み出しは不可能．

障害時回復

方法

トランザクション UN DO ：トランザクション障害時，異常終了したトランザクションを UN DO する（データベースに対して行ったすべての作用を取り消す）． ROLLB ACK 処理．全局的 UN DO ：システム障害時，未完の全てのトランザクションを UN DO する．局所的 REDO ：システム障害時， CO MMI T していたが，一時的（二次記憶に転送されていない）状態にあるトランザクションは再起動時に RE DO する．全局的 REDO ：メディア障害時，データベースの保存用ダンプをもとに，障害発生まで CO MMI T された全てのトランザクションを REDO する．

UNDO

および

REDO

はべき等である（何度繰り返しても同

じ結果になる）．

(3)

障害時回復の分類

障害の例

振替送金トランザクション

begin read(A ,x) read(B ,y ) x:=x -C if x < 0 then rollback y:=y+C write(A,x) write(B,y) commit

ケース

1 ：wr

ite(A,x)

の直

後にシステム障害が発生

A の値のみが変更されているので，再起動のときに begin の状態に戻っている必要がある． (U NDO)

ケース

2 ：co

mmit

の直後

にシステム障害が発生

再起動のとき， A, B の値がともに変更されているという commit の状態を保証する必要がある． (R ED O)

階層型記憶アーキテクチャ

データベースの更新は，更新したいデータの入っているページを主記憶の一部であるデータベースバッファに呼び出し，更新し，二次記憶に書き出す．主記憶は揮発性，二次記憶は不揮発性である．プログラムにおける読み書き (read/writ e) と，二次記憶上の読み書き (read-pa ge/wr ite-p age) とは一致していない． write が実行されてバッファ上では書き込みが行われているものの，まだその書き込みがディスクに反映されていないページのことをダーティページ (dirty pa ge) という．ダーティページをディスク上に強制的に書き込むことをフラッシュ (flu sh )という．

ログ法

ログ

(log)

：トラン

ザクション実行の記録．

ジャーナ

ル

(journal)

と呼ぶこともある．

ログ法

(logging)

：ログを用いる障害回復の

方法．

ログは（ディスクの二重化などの）

安定記

憶

(stable storage)

に格納されることが望

ましい．

(4)

ロギング法

ログレコ

ード

トランザクション

T

の開始

(begi

n)

：[B:

T]

トランザクション

T

による書き込み

(write(A,x))

：

[W:T,A

,Ol

d,New]

ただし

Old

は更新前の値

(before image)

，

Ne

w

は更新

後の値

(after image)

トランザクション

T

による読み出し

(read(A,x))

：[R:T,

A]

トランザクション

T

のコミット

(commit)

：[C:T]

トランザクション

T

のアボート

(abort)

：[A:T]

各ログレコードには

LSN(Lo

g Sequence

Number)

と呼ばれる作成順の識別子が付けられ

るこ

とが多い．

WAL

プロトコル

ロギングの操作：

以下の同期をとる必要がある．

データベース

バッファを介するデータベース

更

新作業

ログバッファ

を介するログ更新作業

ログレコードなしにはディスク中の項目を元の値に戻

すことは不可能である

．

WAL

プロトコル

(Write Ahead Log proto

col)

データベースの更新はそれをまずログファイ

ル

に書き

出してから

行

う．

トランザクションを

COMMIT

する前に，全ての

データ

ベース更新

を

ログファイルに書き出す．

COMMIT

によるトランザクションの終了は，それがログ

ファイルに記録された時点である

．

No-undo/redo

方式

write

操作はログにのみ記録し，コミットするまで二次記

憶中のデータ更新は行わない．

before i

m

age

が二次記

憶に保持されているので，ログレコードに記録する必要

はない．

トランザクションの開始：[B: T] をログ用バッファに書き込む．トランザクションによる書き込み： [W :T, A,Ne w ]をログ用バッファに書き込む．トランザクションのコミット： [C: T] を書いた後，ログ用バッファをフラッシュする．さらにトランザクション中の write 操作を二次記憶に反映させる．トランザクションのアボート： [A:T] をログ用バッファに書き込む．リスタート処理 (REDO) ：[C: T] のあるコミット済みトランザクションを検出する． [W :T ,A ,N ew] として記録されている write 操作をデータベースに反映させる．

Undo/no-redo

方式

コミットするまでに

write

操作に関する二次記憶中のデー

タ更新を行う．

after image

が二次記憶に保持されている

ので，ログレコードに記録する必要はない．

トランザクションの開始：[B: T] をログ用バッファに書き込む．トランザクションによる書き込み： [W :T, A,Old] をログ用バッファに書き込む． WA L プロトコルに従う限り， writ e 操作を二次記憶に反映させてもよい．トランザクションのコミット：トランザクション中の write 操作を二次記憶に反映させる． [C:T] を書いた後，ログ用バッファをフラッシュする．トランザクションのアボート： [A:T] をログ用バッファに書き込む．トランザクション中で write 操作に関して be for e imag e に書き戻す．リスタート処理 (UNDO) ：[C: T] のないアボート済みあるいはアボートすべきトランザクションを検出する． [W :T ,A ,Old] として記録されている write 操作に関して be fore image に二次記憶を書き戻す

(5)

Undo/redo

方式

二次記憶中のデータ更新とコミット処理を独立させる．フラッシングに関する制約が少なく，ディスクアクセスが減少する．トランザクションの開始： [B:T ]をログ用バッファに書き込む．トランザクションによる書き込み：[W:T ,A ,Ol d,N ew] をログ用バッファに書き込む． WAL プロトコルに従う限り， write 操作を二次記憶に反映させてもよい．トランザクションのコミット： [C:T] を書いた後，ログ用バッファをフラッシュする．トランザクションのアボート： [A:T ]をログ用バッファに書き込む．トランザクション中で wr ite 操作に関して UNDO 処理をする．リスタート処理 (U N D O /R ED O )： [C:T ]のあるコミット済みトランザクションと，それがないアボート済みあるいはアボートすべきトランザクションを検出する． [W:T ,A,O ld ,Ne w ]として記録されている write 操作に関して前者に関しては RE DO 処理，後者に対しては UND O 処理を行う．

例（

Undo/Redo

方式）

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_],

[W:T

3

_,D,d

1

_,d

2

_{], [C}

:T

2

_]}

例

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_],

[W:T

3

_,D,d

1

_,d

2

_],

[C:

T

2

_]

}

逆方向にスキャンする．

[C

:T

2

_]により

ト

ランザ

クション

T

2

_がコミ

ッ

ト済みであるこ

と

を認識する．

例

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_],

[W:T

3

_,D,d

1

_,d

2

_]

,

[C:

T

2

_]

}

[W:T

3

_,D,d

1

_,d

2

_{]があるトランザクション}

T

3

_はコ

ミット済みで

ない

ので

この

write

操作の

UND

O

処理を行う．

(6)

例

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_],

[W:T

2

_,C,c

1

_,c

2

_]

,

[W:T

3

_,D,d

1

_,d

2

_]

,

[C:T

2

_]

}

[W:T

2

_,C

,c

1

_,c

2

_]はコ

ミ

ッ

ト済みのトランザクショ

ンによるものなのでひとま

ず

読み飛ばす．

例

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_]

,

[W:T

2

_,C,c

1

_,c

2

_]

,

[W:T

3

_,D,d

1

_,d

2

_]

,

[C:T

2

_]

}

[W:T

3

_,B

,b

1

_,b

2

_{]があるトラ}

ン

ザク

シ

ョ

ン

T

3

_はコ

ミット済みで

ない

ので

この

write

操作の

UND

O

処理を行う．

例

ログ

{[B:T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_],

[C:T

1

_],

[B:T

3

_]

,

[W:T

3

_,B

,b

1

_,b

2

_]

,

[W:T

2

_,C,c

1

_,c

2

_]

,

[W:T

3

_,D,d

1

_,d

2

_]

,

[C:

T

2

_]

}

[C:T

1

_]より

T

1

_をコ

ミット済みのトランザクション

に加

える．

例

ログ

{

[B:

T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_{], [B:T}

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_],

[W:T

3

_,D,d

1

_,d

2

_{], [C}

:T

2

_]

}

[W:T

1

_,A,a

1

_,a

2

_{]はコミット済みのトラ}

ンザク

シ

ョ

ン

T

1

_{によるものなのでひとまず読み飛ばす．}

(7)

例

ログ

{

[B:

T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_]

, [B:T

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_],

[W:T

3

_,D,d

1

_,d

2

_{], [C}

:T

2

_]

}

今度はログを先頭から順方向にスキャンする．

コミ

ット済みのトランザクション

T

1

_による

[W:T

1

_,A,a

1

_,a

2

_]に対

する

REDO

操作を行う．

例

ログ

{

[B:

T

1

_{], [W:T}

1

_,A,a

1

_,a

2

_]

, [B:T

2

_{], [C:T}

1

_],

[B:T

3

_],

[W:T

3

_,B

,b

1

_,b

2

_{], [W:T}

2

_,C,c

1

_,c

2

_]

,

[W:T

3

_,D,d

1

_,d

2

_{], [C}

:T

2

_]

}

コミ

ット済みのトランザクション

T

2

_による

[W:T

2

_,C

,c

1

_,c

2

_{]に対する}

REDO

操作を行う．

チェックポイント法

チェッ

ク

ポイント法

(checkpoi

nti

ng)

：障害時回復を能率良

く行うための手法．一定の周期でバッファの内容をフラッ

シュする．

チェッ

ク

ポイントでの作業

実行中のトランザクションの全てを一時停止 (s uspe nd) する．データベースバッファの内容をデータベースに書き出す．チェックポイントレコード（実行中トランザクションリスト）をログファイルに書き出す．中断されていたトランザクションを再開 (resume) する．

チェッ

ク

ポイントを導入すると，チェックポイント以前に終

了している

ト

ランザクションはシステム再スタート時に回

復作業をする必要がないという利点がある．

チェックポイント法

チェックポイントレコードから UNDO ／ REDO をするトランザクションを見つけるアルゴリズム 1.UNDO トランザクションのリストをチェックポイント時に実行中であったトランザクションのリストとする． REDO トランザクションのリストを NIL とする． 2. ログファイルをそのチェックポイントレコードから障害発生時まで順に検査する． 2-1. もし BEGIN TRA N SACTI O N レコードを見つければ，そのトランザクションを UND O リストに追加する． 2-2. もし CO MMIT レコードを見つければ，そのトランザクションを UND O リストから RED O リストに移動する． 2-3. ログファイルの終わりにきたら終了する．

(8)

コミット

コンシ

ス

テントチェックポイント法

(commit consis

tent checkpointing)

手順

1.

新たなトランザクショ

ンの開始を禁止する．

2.

アクティブ

な

トランザ

クションが

す

べてコミ

ット

かアボートするまで処理を続ける．

3.

ログ用バッファ

と

データ用バッファ

をこ

の順に

フラッシュ

す

る．

4.

ログ用バッファ

に

ログレコード

[CHEC

KPOINT]

を書き込んだ後フラッシュす

る．

コミット

コンシ

ス

テントチェックポイント法

(commit consis

tent checkpointing)

特徴

チェックポイントをとるた

めにはアクテ

ィブなト

ランザクションがない状態に入らなければな

らな

い．

長時間続くトランザクションが存在する場合

には多くの処理要求を長時間にわた

って待

たせること

に

なる．

フラッシュ時のデータ書き

込みに多くの時間

を

必要とする．

キャッシュコンシステントチェックポイント

法

(cache consi

stent checkpointing)

手順

1.

新たな基本操作の開始を禁止する．

2.

処理中の基本操作の終了を待つ．

3.

ログ用バッファ

と

データ用バッファ

をこ

の順に

フラッシュ

す

る．

4.

ログ用バッファ

に

ログレコード

[CHECKPOINT:TL]

を書き

込

んだ後フラッ

シュする．

た

だ

し

，

TL

は現在アクティブ

なトラ

ンザクショ

ン

の集合である．

キャッシュコンシステントチェックポイント

法

(cache consi

stent checkpointing)

特徴

リスタート処理では最新のログレコード

[CHECKPOINT:TL]

までの範囲ではなく，

TL

の中にアボート済みあるいはアボートすべき

トランザクションがあった場合には，

そ

の

トラ

ンザクショ

ン

の開始時点までログをさかのぼ

る必要がある．

(9)

例

ログ

{[B:T 1_], [W :T 1_,A ,a 1_,a 2_], [ B: T 2_], [ C: T 1_], [B: T 3_], [W :T 3_,B, b 1_,b 2_], [CHECK POINT,{ T 2_,T 3_{}], [W:T} 2_,C ,c 1_,c 2_{], [} W :T 3_,D, d 1_,d 2_], [C:T 2_]} ログを逆方向にスキャンする． [C: T 2_]より T 2_{をコミット済} みトランザクションに加える． [W: T 3_,D, d 1_,d 2_{]に対する} UN DO 処理を行う． [W: T 2_,C ,c 1_,c 2_{]を読み飛} ばす． [CHECK POINT,{ T 2_,T 3_}] に達しても T 3_はアボートすべきなのでさらにスキャンを続ける． [W: T 3_,B ,b 1_,b 2_{]に対する} UN DO 処理を行う． [B:T 3_]でスキャンを終了する． [CHECK POINT,{ T 2_,T 3_}] から順方向にスキャンする．コミット済み T 2_による [W :T 2_,C, c 1_,c 2_{]に対する} REDO 処理を行い終了する．

シャドーページ法

ディスク中のページをページテーブルというアドレス変換テーブルを介して間接的にアクセスする．トランザクションの開始：カレントページテーブルというトランザクション用のページテーブル領域を確保する．元のページテーブルはシャドーページテーブルと呼ぶ．その位置を示すポインタをシャドーページテーブルポインタという．カレントページテーブル読み書きのためのバッファをページテーブル用バッファという．トランザクションによる書き込み：ページテーブル中の i番目のページ P(i) の更新を行うとする．それが P( i)に対する最初の更新であれば，ディスク中の空ページ P' を確保して P(i) の内容をコピーし，カレントページテーブル i番目のエントリが指すページを P' に変更する．その後，データ用バッファ上の P' を更新する．トランザクションのコミット：データ用バッファをフラッシュした後，ページテーブル用バッファをフラッシュする．さらにディスク中のシャドーページテーブルポインタをカレントページテーブルを指すようにする．トランザクションのアボート：カレントページを廃棄する．