###### tags: `TransactionalInformationSystems`

# 12章 障害回復のための正当性

## 概要

ここから障害回復のアルゴリズムについて考えていく。これはトランザクションの不可分性と耐久性を保証するものになる。

サーバに障害が発生してダウンした場合、一時記憶に載っているデータは全て揮発し、二次記憶のストレージから現在の状態まで復帰させる必要が出てくる。そのために、障害時点までにcommitされたトランザクションによる更新を全て反映(redo)し、abortされた/activeだったトランザクションによる更新は巻き戻し(undo)することになる。これは前章のトランザクション復元と似ているが、redo/undoの相互作用についてより注意を払う必要がある点が異なる。

12章-15章では、障害に際して一時記憶のデータのみ失われるソフトクラッシュのみ考えていく。二次記憶のストレージにも影響が出るハードクラッシュは16章で考える。

ソフトクラッシュが起きる原因には主に二つ、(1)電源喪失(2)ソフトウェアエラーがある。(1)に関しては、無停止電源の利用が一般的になったこともあり重要ではない。重要なのは(2)ソフトウェアエラーであり、その中でも特に、複雑なマルチスレッド実行環境などで起こる、再現性が低く追跡も困難なある種「非決定的」バグによって引き起こされるクラッシュが問題となる。

こうした非決定的なバグへ対処する最善の方法は、エラーを検出した瞬間にできるだけ早くシステムをシャットダウンし、再起動して状態の回復を実行すること。再起動すれば同じバグが起こることはほとんどない。

システムの障害回復に関するパフォーマンスの指標は主に二つある。一つ目は可用性

$$\frac{MTTF}{MTTF+MTTR}$$

だが、非決定的バグが存在する以上MTTF(mean time to failure)を長くすることは難しく、したがって可用性を上げるにはMTTR(mean time to repair)を短くする、すなわち高速で障害回復できることが重要になる。

二つ目は、システムが平常動作している際に障害回復アルゴリズムのために使用されるリソースオーバヘッドの大きさである。例えばログファイルのディスク上での大きさなどがあり、あまりリソースを使い過ぎると通常のデータ操作に悪影響を与える。

また、障害から回復している最中に新たな障害が起こる可能性も考慮しなくてはならない。障害回復アルゴリズムは、いついかなる障害であっても回復できることが理想的である。また、障害回復はクリティカルな部分である以上、アルゴリズムはできるだけシンプルで検証が容易な方が望ましい。ただし、ここでもシンプルさとパフォーマンスの間にはトレードオフがあることは避けられない。

## システムアーキテクチャとインタフェース

まず、障害回復のための実際的なシステム構成や必要なインタフェースについて考えていく。これを抽象化して理論を構築するのは次節以降になる。

### コンポーネント

障害回復に関連するシステムのコンポーネントは以下の4つである。

1. 永続データベース：ストレージ(二次記憶)に保存されたページの集まり。
2. データベースキャッシュ：揮発メモリ(一次記憶)に保存された、永続データベースのページコピーの集まり。DBへの変更は、これらのキャッシュを変更した上でキャッシュがストレージに書き戻されることで反映される。データベースキャッシュと、永続データベースのキャッシュされていない部分を合わせて「キャッシュデータベース」になっている。
3. 永続ログ：ストレージに保存された、キャッシュデータベースへの変更履歴を記録するログエントリの集まり。
4. ログバッファ：揮発メモリに保存された、永続ログへ書き込むためのバッファ。ログエントリはいったんログバッファ上に作成され、その後に永続ログに書き出される。

永続ログとログバッファはトランザクションの復元と障害回復の両方を行うために十分な情報を含んでいる。ただし、前者はより速度が重視されるため、メモリの別の位置に復元専用のログエントリが確保されることが多い。

### アクション

障害回復と関係するデータベース上のアクションを以下に列挙する。各アクションには連番が付され、同じページを参照するアクション同士、同じトランザクションを参照するアクション同士で単調増加とする。

1. トランザクションのアクション
- begin(t): トランザクションtの開始。
- commit(t): トランザクションtのcommit。tによる更新が全て永久化され、ソフトクラッシュしても残る。
- rollback(t): トランザクションtが失敗した場合の終了操作。tによる更新が全て無効になり、キャッシュデータベースに残らない。
- save(t): トランザクション内でのセーブポイントを作る。tをロールバックしても、セーブポイント以前の更新は残る。
- restore(t,s): トランザクションtをセーブポイントsまで巻き戻す。
2. データアクション
- read(pageno, t): トランザクションtを代表してpagenoのページを読み込む。
- write(pageno, t): トランザクションtを代表してpagenoのページに書き込む。データベースキャッシュのページを仮想メモリアドレスに固定し、ページの内容を読み込み、変更し、ページ状態をdirtyにした上で固定を外す。
- full-write(pageno, t): ページを読み込まず、ページ全体を同じバイトで埋め尽くすような書き込みを行う。
- exec(op, obj, t): トランザクションtを代表して、オブジェクトobjに対する操作opを行う。必要に応じて他のアクションに展開される。
3. キャッシュアクション
- fetch(pageno): キャッシュされていないページpagenoを、永続データベースからデータベースキャッシュにコピーする。
- flush(pageno): キャッシュされていてdirty(=writeによって変更されている)かつ、安定バージョンよりも新しいページpagenoを永続データベースにコピーする。キャッシュのページ状態をdirtyからcleanに戻す。
4. ログアクション
- force: ログバッファの全ログエントリを永続ログにコピーする。

システムが開始する場合、最初に必ず回復アルゴリズムが走る。つまり直前に障害が起きてダウンした前提で始まる。前回の終了が通常のシャットダウンだという証拠を発見した場合のみこの過程を飛ばす。

## システムのモデル

履歴を拡張する。オブジェクトモデルと似ているが、キャッシュに関する操作が新たに組み込まれている。

---

### 定義：拡張履歴

データサーバの拡張システム履歴とは、アクションの半順序付けされた森で、アクションの集合$A$から成り、以下の条件を満たすものとする。

- 根はトランザクション識別子かキャッシュアクション(fetch/flush)である
- 葉はread/write/full-writeか、トランザクションのアクションのいずれかである
- 内部ノードはexecである
- $<$で表記されるアクション間の順序はtree consistentである(6章参照、葉が全部順序付いてるなら内部ノードどうしにも同じ順序が付く)

---

本章では履歴といったときに拡張システム履歴を前提とする。

---

### 定義：永続ログ

履歴の永続ログとは、履歴内のアクションの全順序部分集合で、履歴の半順序と矛盾しないようなものとする。

永続ログに含まれる各アクションをログエントリと呼ぶ。

---

要は、ログの本質はシステム履歴を一列に並べたものである。

ログバッファも基本的に同じで、永続ログの後に続く、また永続化されていない部分として定義できる。

### 定義：ログバッファ

履歴のログバッファとは、履歴内のアクションの全順序部分集合で、履歴の半順序と矛盾しないようなもので、かつ全てのエントリがその履歴の永続ログの後に続くようなものとする。

---

各アクションがどの順で行われたかの情報を推定できるようにするため、データベースの各ページに、そのページに変更を行った最新のアクションの連番を記録することとする。最新のアクションしか分からないものの、多くの場合それで十分かつ、実装が非常に簡単であるという利点が大きい。ページがfetch/flushされたときに、この値は常にストレージ/メモリ間をコピーされて移動することになる。

このような連番に基づいて、キャッシュデータベースと永続データベースを定義できる。

---

ここで書き込みアクション=writeもしくはfull-writeとする。

### 定義：キャッシュデータベース

キャッシュデータベースとは、システム履歴の全ての書き込みアクションの半順序集合であり、半順序は履歴の半順序の一部で、履歴のページ$p$に対する最大の書き込みアクションがキャッシュデータベースにおいても最大の書き込みアクションであるようなものとする。

日本語にしたら錯綜してしまったが、要は履歴の書き込みアクションのみ抽出し、各ページに最新の書き込みを反映したもの。

---

### 定義：永続データベース

永続データベースとは、システム履歴の全ての書き込みアクションの半順序部分集合であり、各ページ$p$について以下の条件を満たすものとする。

- 履歴における、最新の$flush(p)$よりも前の書き込みアクションは全て永続データベースに含まれる。
- 履歴における、最新の$flush(p)$よりも前の書き込みアクションのうち最新(最大)のアクションは、永続データベースにおいてもやはり最新(最大)である。

要は、flush以前の最新の書き込みアクションを全て反映したもの。

---

ここまででシステムコンポーネントのフォーマルな定義が完了したので、これから障害回復の正当性について考えていく。

### 定義：正当な障害回復

障害回復アルゴリズムが正当とは、システムの障害が起こった後も、キャッシュデータベースが、commitされたトランザクションを(履歴の逐次実行順と同じ順番で)serialに実行したときと等価になることとする。

ここで、障害回復の正当性の定義には永続データベースは全く登場しないことに注意。キャッシュデータベースさえ正しい状態に戻すことができれば、あとはそれを順にflushするだけで永続データベースも正しい状態に戻る。flushの実行タイミングは実装の問題であって正当性には関係ないので、とりあえずキャッシュデータベースを回復することだけ考えればよい。

なお、システムの障害は回復中にも起こりうると仮定するが、有限回に留まるものとする。無限回障害が起こるケースは、データベースというよりもはやシステム全体に深刻な問題がある。

この時点で、永続ログだけから正しく回復できるための必要条件は既に定義できる。これは、**サーバの通常動作中に永続データベースと永続ログの間に成立するべき関係**についての条件であり、回復段階での動作については何も述べていない。

---

### 定義：ログ規則

障害回復アルゴリズムは以下の条件を満たす。

- redoログ規則：履歴に$commit(t)$が含まれるようなトランザクション$t$に対し、$t$でのデータアクションが全て永続ログもしくは永続データベースに含まれる。
- undoログ規則：$commit(t)$も$rollback(t)$も履歴に含まれないようなトランザクション$t$のデータアクション$p$について、$p$が永続データベースに含まれる時には永続ログにも含まれる。
- ガーベジコレクション規則：履歴内の全てのトランザクション$t$のデータアクション$p$に対し、$p$が永続ログに存在しない$\Longrightarrow$(履歴に$commit(t)$が含まれる$\Longleftrightarrow$ $p$が永続データベースに含まれる)

---

実装の観点から言うと、これらの条件は

- redoログ規則は、commitした時点でredo情報が全て永続ログに書き出されることを強制する。一般的にはこの規則が守られるので、トランザクションがcommitされている=commitログエントリが永続ログに存在することとして扱われる。
- undoログ規則は、undo情報が永続データベースにflushされる前に永続ログに書き出されることを強制する。
- ガーベジコレクション規則は、永続ログの各エントリについて、回復に必要なくなれば削除しても良いことを意味する。ログが小さいことはスペース的にも実行時間的にも重要。

## アルゴリズムの分類

3つのログ規則は、キャッシュデータベースについては何も述べていない。

キャッシュデータベースと永続データベース、永続ログの間の関係をどのように捉えるかによって、複数の障害回復アルゴリズムが考えうる。それらは以下の4つのカテゴリに大別できる。

No-undo/no-redoアルゴリズム
: 永続データベースが、commitされたトランザクションのアクションだけをちょうど全て含むことを保証するアルゴリズム。常にそれが保証されるので、システムの再開に伴って何もする必要がない。その代わり、サーバの通常動作中に追加の作業が必要になる。
: フォーマルには、2つの不変条件「永続データベースがトランザクション$t$のデータ操作$p$を含むとき、永続ログが$commit(t)$を含む」「永続ログが$commit(t)$を含むとき、永続データベースが$t$のデータ操作を全て含む」を常に満たす。
: 1つ目の条件を保証するためには、commitされていないトランザクションによって変更されているページが永続データベースにflushされないことが必要。(no-steal性) no-stealなる命名の理由は、もっとも安直な実装がキャッシュマネージャが勝手にそういうページをキャッシュから除いてflushしてしまうことを禁止するものだから。deferred update(更新延期)アルゴリズムとも。
: 2つ目の条件を保証するには、commitの時点で変更されたページを全てflushすることが必要。(force property)

No-undo/with-redoアルゴリズム
: No-undo/no-redoの1つ目の不変条件「永続データベースがトランザクション$t$のデータ操作$p$を含むとき、永続ログが$commit(t)$を含む」を常に満たすアルゴリズム。no-stealアルゴリズムとも呼ばれる。
: システム再開の際、redoステップが必要になる。

With-undo/no-redoアルゴリズム
: No-undo/no-redoの2つ目の不変条件「永続ログが$commit(t)$を含むとき、永続データベースが$t$のデータ操作を全て含む」を常に満たすアルゴリズム。forceアルゴリズムとも呼ばれる。
: システム再開の際、undoステップが必要になる。

With-undo/with-redoアルゴリズム
: ログ規則だけ守り、他に不変条件を課さないアルゴリズム。no-steal no-forceアルゴリズムとも。
: システム再開の際、redoステップとundoステップの両方が必要になる。

no-undoアルゴリズム(=更新延期アルゴリズム)は、トランザクションがcommitされるまでページのflushを延期する必要がある。この実現方法には複数考えられる。

シャドーイング
: 永続ログ内のcommitされていないトランザクションによる更新を、アトミックな方法でデータベースに反映する方法。比較的簡単な方法としては、データベースのページアドレステーブルを2つ持ち、commitの段階でマスターポインタを切り替える方法がある。

バージョニング
: 永続ログが、データベースオブジェクトのバージョンを差分ファイルとして保存する方法。commitされていないトランザクションでは新しいバージョンが作成され、commitの段階でそれがキャッシュデータベースに導入される。

障害回復にかかる時間だけ考えるなら、no-undo/no-redoアルゴリズムが最善である。ただし、これは通常動作を2倍以上重くするため、全体のパフォーマンスで見るとそれほど優れていない。

no-undo性のための更新延期は、シャドーイングを用いればまだマシなオーバヘッドで実行できるが、その場合ページ粒度での同時実行制御しかできない問題が発生する。バージョニングを用いた場合は、粒度は自由だが、新しいバージョンのコピーに多大なオーバヘッドが発生し、ディスクI/Oが2倍以上になる。

no-redo性のためのforceは、さらにパフォーマンスを悪化させる。commitの際に変更したページを全てflushするので、ディスクI/Oに著しい負荷がかかる。10倍のレベル。

結局のところ、通常動作時のパフォーマンスが最も軽く、また障害回復時にはredo/undoを実行する必要があるものの現実的な時間で収まるwith-undo/with-redoアルゴリズムが最善の選択肢であり、商用システムには基本的にこれが用いられている。また、ページモデルから他のモデルへの一般化がしやすいアルゴリズムという利点も備えている。

次章以降では、with-undo/with-redoアルゴリズムに的を絞って考えていく。