トランザクション2 : 時刻印方式、障害回復、多版管理

この投稿は大学の期末試験のためのものです。間違い等は悪しからず。

前回（https://qiita.com/s0t00524/items/56c9d95637d1d356a291 ）に引き続き、トランザクションの競合に対する排他制御をみていく。

時刻印（Timestamp）方式

各トランザクションが開始した順番で一意的な時刻印を付与し、その時刻印に従ってSerializabilityを実現する方式。

複数のトランザクションが競合した際、タイムスタンプにより最初に実行されたトランザクションを特定し、これを先実行するよう、一旦、他の全てのトランザクションをロールバックした後、再実行します。

（一貫性／独立性を確保する「排他制御」を理解する (1/2)（https://www.atmarkit.co.jp/ait/articles/1703/01/news196.html) より）

刻印のルール(1)

各項目$X$に二種類の時刻印を持たせる

時刻印	意味
$ts_r(X)$	これまでに$X$にreadを行ったトランザクション（$T$）の時刻印の最大値
$ts_w(X)$	これまでに$X$にwriteを行ったトランザクション（$T$）の時刻印の最大値

刻印のルール(2)

トランザクション$T_i$の時刻印を$ts(T_i)$とする。このとき$T_i$が$X$に対してreadあるいはwriteを行う場合を考える。

$T_i$が$X$をreadする場合
- $ts(T_i) < ts_w(X)$のとき、$X$は$ts_w(X)$の時点ですでに書き換えられてしまっているので、$T_i$をアボートする。
- $ts(T_i) \geq ts_w(X)$のとき、read処理をし、$ts_r(X) \Leftarrow \max (ts_r(X), ts(T_i))$とする。（時刻印の更新）
$T_i$が$X$をwriteする場合
- $ts(T_i) < ts_r(X)$のとき、$X$はすでに後続のトランザクションによってread処理が行われているので、$T_i$をアボート。
- $ts(T_i) \geq ts_r(X)$ かつ $ts(T_i) < ts_w(X)$ のとき、$X$が後続のトランザクションに書き換えられてしまったあとなので、$T_i$をアボート
- $ts(T_i) \geq ts_r(X)$ かつ $ts(T_i) \geq ts_w(X)$ のとき、write処理をし、$ts_w(X) \Leftarrow \max (ts_w(X), ts(T_i))$ とする。

時刻印ロック

更新開始時点の対象データに記録されている最終更新時刻を記憶しておき、更新処理を行う際に再度対象データの最終更新時刻と比較する。もし異なっていたら、他によって内容が更新されてしまったと判断し、更新をあきらめ、同一であれば、対象データ更新とともに処理をした現在の更新時刻を記録する。

(https://ja.wikipedia.org/wiki/%E6%99%82%E5%88%BB%E5%8D%B0%E3%83%AD%E3%83%83%E3%82%AF )

Wait-DieとWound-Wait

どちらを選択してもデッドロックが発生しないことが保証できる。

Wait-Die方式

$ts(T_i) < ts(T_j)$ならば、$T_i$は$T_j$がロックを解放するまでまつ。
$ts(T_i) > ts(T_j)$ならば、$T_i$はアボートする。

この方式では、自分より先に開始されたトランザクションを待つことはない。

Wound-Wait方式

$ts(T_i) < ts(T_j)$ならば、$T_j$をアボートさせるように試みる。
$ts(T_i) > ts(T_j)$ならば、$T_i$は$T_j$がロックを解放するまで待つ。

この方式では、自分より後に開始されたトランザクションを待つことは無い。

二つの方式において、アボートさせられたトランザクションは同じ時刻印を持って再実行すればよい。（いずれはアボートされることなく実行されることが保証されている）

障害回復

ACID特性の一つであるトランザクションの耐久性を確保するため、DBMSには、障害回復機能が備わっています。(耐久性を確保する「障害回復機能」を理解する https://www.atmarkit.co.jp/ait/articles/1703/01/news198.html より)

データベースシステムはデータベースバッファ（主メモリ）+ 磁気ディスクで構成されることを前提とする。このとき、障害は以下の3つに分類される。

障害の種類	説明
トランザクション障害	トランザクションが、自主的あるいはデッドロックのためにアボートするなどして、コミット前に異常終了すること。このとき、トランザクションに関する全てのデータは保存される。
システム障害	システムは停止するが不揮発性記憶上のデータは残る場合。主メモリ上に置かれていたデータは消失する。
メディア障害	データを記憶した不揮発性記憶に障害が発生し、データが読み出せなくなる場合。他の不揮発性記憶にデータを保存しておかない限り全て消失。

以下ではこの障害に対する回復の方法について考える。

ログを用いた障害回復

トランザクションの基本操作の履歴をログとして出力し、障害発生時にこれを用いてリストアする。

ログの処理

ログ	記録内容
$begin(T_i)$	トランザクション$T_i$の開始
$write(T_i, X, V_{old}, V_{new})$	$T_i$によるデータ$X$の書き込み
$read(T_i, X)$	$T_i$によるデータ$X$の読み出し
$commit(T_i)$	$T_i$のコミット
$abort(T_i)$	$T_i$のアボート
$checkpoint([T_a, ..., T_b])$	チェックポイントの情報

ログを残す際のお約束ごとに**WAL(Write Ahead Logging)**が存在する。これは、実際のデータベースに書き込む前にログに履歴を残すというものである。これによりデータベースの更新中に障害が起きた場合にも耐えうるDBが可能になる。

RedoとUndo

Do : Old State -> New State + Log
Redo : Old State + Log -> New State
Undo : New State + Log -> Old State

チェックポイント

DBMSでは処理速度を高めるため、トランザクション処理結果をその都度ディスクには書き込まず、データ更新情報をメモリ上で管理します。そしてチェックポイントのタイミングで、最終的なデータの更新結果をディスク上に反映させ同期をとります。チェックポイントは**一定間隔や任意の処理のタイミングで自動実行するように設定しますが、必要に応じてコマンドで手動実行することもできます。

これにより障害回復の時間を短縮させることができる。

(https://gihyo.jp/dev/serial/01/db-academy/000202 より)

コミット時にいきなりデータファイルを更新すると、コストがとても大きいのでユーザを待たせてしまう。

障害発生時のトランザクション状態と回復処理

今、時刻Tmにて障害が起こったとする。再起動によって各トランザクション$T_i$の挙動はどうなるだろうか？

トランザクション$T_1$は何の問題もなく結果が保証される。（Tnのチェックポイントで結果を保存済みのため）

トランザクション$T_3, T_5$については、再起動時にアボートにより「なかったこと」になる。ユーザが手動で再実行する必要がある。

トランザクション$T_2, T_4$については、障害前にトランザクションが終了しているので結果は保証の対象となる。しかし$T_1$との違いはチェックポイント後もトランザクションを実行していることであり、これは再起動時にロールフォワードが必要になる。

以上をまとめると以下のようになる。

トランザクション	挙動
$T_1$	データベースの状態はディスク上に反映済み -> 回復処理不要
$T_2$	チェックポイントからコミット時点までRedoが必要
$T_3$	原子性を保つためアボート -> $T_3$開始時までUndo
$T_4$	開始時点からコミット時点までRedoが必要
$T_5$	原子性を保つためアボート -> $T_5$開始時までUndo

以上をまとめて障害回復アルゴリズムは以下のようになる。

障害回復アルゴリズム

Undo用とRedo用の２つのトランザクションリスト $L_{undo}, L_{redo}$を用意
最新の $checkpoint([T_a, ..., T_b])$ の中のトランザクションを $L_{undo}$に入れ、$L_{redo}$を空にする
最新のチェックポイントからログを時間軸に沿って読み込む
- $begin(T_i)$ 　検出 : $T_i$を$L_{undo}$に加える
- $commit(T_i)$ 検出 : $T_i$を$L_{undo}$から取り出し、$L_{redo}$に加える
- $abort(T_i)$ 　検出 : 読み飛ばす
ログの最後までいくと、UndoとRedoのリストが出来る
ログを時間軸と逆に読みながら、$L_{undo}$ にあるトランザクション処理の取り消しを行う
再度ログを時間軸方向に読みながら、$L_{redo}$にあるトランザクション処理の再実行を行う

メディア障害対策

<参考>
https://www.ibm.com/support/knowledgecenter/ja/SSEPGG_10.5.0/com.ibm.db2.luw.admin.ha.doc/doc/c0005966.html

メディア障害 とは、ハード・ディスク・ドライブなどのストレージ・デバイスの読み取り/書き込みインターフェースにおける障害によって生じたエラーです。このタイプの障害は検知して防ぐのが難しいことがあるため、障害が生じた場合に備えてその影響を軽減する措置を講じる必要があります。

ソフトウェア的対策
- ダンプ : ディスク内容をテープ等に定期的に吸い上げておく
- リプリケーション : 別のディスクに同じデータを格納しておく
ハードウェア的対策
- ディスクの耐故障化 : RAID(Level 1-6)

RAID

Redundant Array of Independent Disksの略であり、複数台のハードディスクを組み合わせることで仮想的な1台のハードディスクとして運用し冗長性を向上させる技術。

参考

https://www.atmarkit.co.jp/ait/articles/1703/01/news196.html
https://ja.wikipedia.org/wiki/%E6%99%82%E5%88%BB%E5%8D%B0%E3%83%AD%E3%83%83%E3%82%AF
https://www.atmarkit.co.jp/ait/articles/1703/01/news198.html
https://gihyo.jp/dev/serial/01/db-academy/000202