###### tags: `TransactionalInformationSystems`

# 14章 オブジェクトモデルにおける障害回復アルゴリズム

## 本章概要

オブジェクトモデルにおける障害回復アルゴリズムを導入する。

はじめに2層のシステムについて、次に一般のオブジェクトモデルスケジュールへ拡張する。

redo-historyアルゴリズムのみ考えることにする。

通常動作中の履歴は常に先頭木削減可能とする。

## redo-historyの概要

オブジェクトモデルに拡張するにあたって新たに考えなければならない問題は、高レベルの操作をどう取り扱うか。具体的には、

1. 勝者トランザクションの高レベル操作をどうやってredoするか
2. 敗者トランザクションの高レベル操作をどうやってundoするか

という問題になる。

redoのやり方には二つの選択肢があり、一つ目としては高レベル操作そのものを完全な形でredoするもの、二つ目としては高レベル操作が引き起こしたページレベル操作をredoすることで実質的にredoするもの。実行コストの観点から、二つ目、ページレベル操作のredoの方が好ましい。

これを踏まえて、3パスアルゴリズムは以下の構成になる。

1. 分析パス：ページモデルと同様。
2. redoパス：全てのページ書き込みをredoする。ページモデルと変わりないので、13章で導入されたページモデル向けの最適化が全て適用可能。
3. undoパス：敗者トランザクションによって行われた高レベル操作の逆操作を逆順に実行する。

高レベル操作のundoを取り扱うにあたって、主に二つの問題がある。
- 高レベル操作はページ操作と違って原子性がない。一部の変更だけ反映されるパターンがありうる。
- 高レベル操作を考えると、敗者トランザクションによる変更の後に勝者トランザクションによる変更がなされたページも存在しうる。これはページモデルのときには存在しなかったケースで、このようなケースの取り扱いはPSNの検証だけでは不可能である。

## 2層システムにおける単純redo-historyアルゴリズム

低レベル$L_0$側の操作と、高レベル$L_1$側の操作を別々のログに分ける。

$L_0$ログは、単に前章で考えてきたページモデル永続ログにおける「トランザクション」を「サブトランザクション」に置き換えたものになる。$L_1$との区別をつけるため、begin,commit,rollbackをsubbegin,subcommit,subrollbackと表記する。

redoはページ単位でしか行わないので、$L_1$側のログにはredo情報は必要なく、undo情報だけ記録する。

- $L_0$ログ：サブトランザクションによるページ書き込みのredo/undoログエントリを記録する。
- $L_1$ログ：トランザクションによる論理的な書き込みのundoログエントリを記録する。

これらのログはそれぞれログバッファと永続ログを持ち、forceするタイミングを連携する必要がある。

### $L_0$と$L_1$のforce規則

- $L_0$ログバッファはundoログ規則を必要とする。つまり、dirtyなページがflushされ、それを参照するログエントリがログバッファに含まれるとき、forceしなければならない。これがないと、不完全に終わったサブトランザクションがundoできず、サブトランザクションの原子性が損なわれる。
- $L_1$ログバッファはredoログ規則を必要とする。つまり、トランザクションのcommitのタイミングでforceしなければならない。commitログエントリはトランザクション単位の終了を示すので、当然$L_1$ログ側に記録される。
- $L_1$ログバッファのforceの前に、$L_0$ログバッファもforceしなければならない。サブトランザクションも含めて全ての操作が永続ログに反映される必要があるため。
- $L_0$ログバッファが永続ログに書き出されるとき、その前に$L_1$ログバッファをforceしなければならない。サブトランザクション途中でクラッシュしても、対応する$L_1$ログエントリが存在することを保証するため。

つまり、トランザクションがcommitされるタイミングでは$L_0 \rightarrow L_1$という順にforce、それ以外の理由(dirtyページのflush・$L_0$ログバッファが一杯)で$L_0$がforceされるタイミングでは$L_1\rightarrow L_0$という順である必要がある。

subcommitのタイミングで$L_0$がforceされる必要が無い事には注意。

### 障害回復手順

回復フェーズにおける主要な手順は以下になる。

- ページレベルの障害回復を$L_0$ログに基づいて行う。3パスredo-historyアルゴリズムを用いて、完了したサブトランザクションのみがデータベースキャッシュに反映される。
- $L_1$ログ上の分析パスで敗者トランザクションを特定し、それらによって引き起こされたサブトランザクションのうち影響が反映されているものをundoしていく。

$L_0$における分析パスは、敗者サブトランザクションのリストだけでなく勝者サブトランザクションのリストも明示的に返す必要がある。$L_1\rightarrow L_0$という順のforce規則があるため、$L_1$側で記録されているサブトランザクションが、$L_0$に記録される前にクラッシュというケースが存在しえる。こういったケースを検出し、$L_0$側にそのサブトランザクションが存在しないことを認識するため、勝者サブトランザクションのリストも必要になる。

各サブトランザクションが勝者かどうかは、subbeginのLSNを対応する$L_1$のログエントリにも記録しておくことで簡単に判定できる。
これを、$L_0$ログにおけるsubbegin操作のLSNのうち最大の値と比較する。

- $L_1$エントリのsubbegin LSNが$L_0$ログにおける最大値よりも大きかったら、そのサブトランザクションは勝者ではない。したがってそのサブトランザクションは以降無視してよい。
- $L_1$エントリのsubbegin LSNが$L_0$ログにおける最大値以下、かつ$L_0$の敗者リストになかったなら、勝者なので$L_1$上のパスでundoされる必要がある。
- $L_1$エントリのsubbegin LSNが$L_0$ログにおける最大値以下、かつ$L_0$の敗者リストに含まれていたら、$L_1$上のパスではundoされてはならない。

---

#### 単純2層回復アルゴリズム

restart():
    L0 analysis pass() returns losers, winners, DirtyPages;
    L0 redo pass();
    L0 undo pass();
    L1 analysis pass();
    L1 undo pass();

---

$L_0$における障害回復手順と$L_1$における分析パスは全て13章の方法で行えるので、ここは$L_1$の分析パスのみを考える。

$L_1$undoパスも相殺ログエントリを生成して後方チェインを作る点はページモデルundoパスと同じであり、大きな違いは各$L_1$ログエントリが勝者サブトランザクションに属するか逐一判定を行う点だけである。

L1-undo-pass():
    ActiveTrans := empty;
    for each t in L1losers do
        ActiveTrans += t;
        ActiveTrans[t].LastSeqNo := losers[t].LastSeqNo;
    end
    while there exists t in losers s.t. losers[t].LastSeqNo <> nil do
        nexttrans := TransNo in losers s.t. losers[nexttrans].LastSeqNo = max{losers[x].LastSeqNo|x in losers};
        nextentry := losers[nexttrans].LastSeqNo;
        // CLEなら後方チェインを辿ってundoできていない最終execエントリまでたどり着く
        if StableLog[nextentry].ActionType = compensation then
            if StableLog[nextentry].CompensatingSubtransId is in L0 winners then
                losers[nexttrans].LastSeqNo := StableLog[nextentry].NextUndoSeqNo;
            else
                losers[nexttrans].LastSeqNo := StableLog[nextentry].PreviousSeqNo;
            end
        end
        // 高レベル操作のundo
        if StableLog[nextentry].ActionType = exec then
            if StableLog[nextentry].SubtransId is in L0winners then
                subbegin();
                newlogentry.LogSeqNo := new sequence number;
                newlogentry.ActionType := compensation;
                newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
                newlogentry.NextUndoSeqNo := nextentry.PreviousSeqNo;
                ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
                LogBuffer += newlogentry;
                execute inverse operation according to StableLog[nextentry].UndoInfo;
                subcommit();
            end
            losers[nexttrans].LastSeqNo := StableLog[nextentry].PreviousSeqNo;
        end
        // beginのundo(rollbackエントリ作成)
        if StableLog[nextentry].ActionType = begin then
            newlogentry.LogSeqNo := new sequence number;
            newlogentry.ActionType := rollback;
            newlogentry.TransId := StableLog[nextentry].TransId;
            newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
            LogBuffer += newlogentry;
            ActiveTrans -= transid;
            losers -= transid;
        end
    end 
    force();

## 2層システムにおける強化redo-historyアルゴリズム

ここまでで導入したアルゴリズムをさらに改善する方法は、$L_0$と$L_1$に分けていたログを一つに統合すること。

この変更によってアルゴリズムは単純化こそすれ、複雑になることはない。単一のファイルに対するシーケンシャルI/Oのみでログを管理できるようになるため効率が上がる。

- subcommit時、$L_0$ログのflush前に$L_1$のflushが必要だったものが必要なくなる。つまり、$L_0$における最後の操作をsubcommitとして解釈できるようになる。
- ログが統合されることで、$L_1$ログエントリ=全て勝者サブトランザクションによるものとなるため、$L_1$ undoパスでの状態検証が必要なくなる。
- $L_0$分析パスで勝者リストを作成しなくていい（敗者リストにないサブトランザクション＝勝者が確定するため）。

また、ログが統合されることでパスの回数を減らせる。

- 2つの分析パスは1つに統合できる（これらは結局同じログファイルを読んでいるため）。
- 2つのundoパスも1つに統合できる。ログエントリがどちらの層のものかを判定して該当するundoを行う。$L_1$操作のundoはそれ用のサブトランザクションを開始し、こちらの場合も$L_0$のCLEが生成されていくことになる。

---

### 定理14.1

3パスで構成された強化2層redo-history障害回復アルゴリズムは正当である。

---

強化undoパスの実装として、NextUndoSeqNoの後方チェインを以下のように拡張する。

- $L_0$の書き込み操作のNextUndoSeqNoは、原則として同サブトランザクションにおける直前の$L_0$書き込み操作を指す。ただし、サブトランザクションの最初の$L_0$書き込み操作のNextUndoSeqNoは、同トランザクションの直前の$L_1$ログエントリを指す。
- $L_1$の書き込み操作のNextUndoSeqNoは、同トランザクションの直前の$L_1$ログエントリを指す。
- CLEのNextUndoSeqNoは、それが相殺するログエントリの、後方チェインにおける直前のログエントリを指す。これは$L_0$でも$L_1$でも共通。

この統合後方チェインを加えたundoステップを疑似コードで示すと以下。

undo-pass():
    ActiveTrans := empty;
    for each t in losers do
        ActiveTrans += t;
        ActiveTrans[t].LastSeqNo := losers[t].LastSeqNo;
    end
    while there exists t in losers s.t. losers[t].LastSeqNo <> nil do
        nexttrans = TransNo in losers s.t. losers[nexttrans].LastSeqNo = max{losers[x].LastSeqNo|x in losers};
        nextentry := losers[nexttrans].LastSeqNo;
        if StableLog[nextentry].ActionType = compensation then
            losers[nexttrans].LastSeqNo := StableLog[nextentry].NextUndoSeqNo;
        end
        if StableLog[nextentry].ActionType = write or full-write then
            pageno := StableLog[nextentry].PageNo;
            fetch(pageno);
            if DatabaseCache[pageno].PageSeqNo >= nextentry.LogSeqNo then
                newlogentry.LogSeqNo := new sequence number;
                newlogentry.ActionType := compensation;
                newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
                newlogentry.NextUndoSeqNo := nextentry.PreviousSeqNo;
                newlogentry.RedoInfo := inverse action of the action in nextentry;
                ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
                LogBuffer += newlogentry;
                read-and-write(StableLog[nextentry].PageNo) according to StableLog[nextentry].UndoInfo;
                DatabaseCache[pageno].PageSeqNo := newlogentry.LogSeqNo;
            end
            losers[nexttrans].LastSeqNo := StableLog[nextentry].NextUndoSeqNo;
        end
        if StableLog[nextentry].ActionType = exec then
            subbegin();
            execute inverse operation according to StableLog[nextentry].UndoInfo;
            newlogentry.LogSeqNo := new sequence number;
            newlogentry.ActionType := compensation;
            newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
            newlogentry.NextUndoSeqNo := nextentry.NextUndoSeqNo;
            ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
            LogBuffer += newlogentry;
            subcommit();
            losers[nexttrans].LastSeqNo := StableLog[nextentry].NextUndoSeqNo;
        end
        if StableLog[nextentry].ActionType = begin then
            newlogentry.LogSeqNo := new sequence number;
            newlogentry.ActionType := rollback;
            newlogentry.TransId := StableLog[nextentry].TransId;
            newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
            LogBuffer += newlogentry;
            ActiveTrans -= transid;
            losers -= transid;
        end
    end
    force();

## 一般オブジェクトモデルにおけるredo-historyアルゴリズム

一般のオブジェクトモデルでは、undoパスにおいて、どのレベルの逆操作を実行すればいいのか分からなくなるという問題があるため、実行中にその情報を追跡するundoスタックを用いて管理することにする。

- exec操作や書き込み操作のたび、対応する逆操作の情報がスタックに積まれる。
- subcommitのたび、そのサブトランザクションの逆操作がトップに現れるまでスタックをポップする。したがって、その子孫に相当するサブトランザクションの逆操作は実行する必要が無いため除外という動作が実現できている。

全アクティブトランザクション用のundoスタックを全て保持するのは効率的ではないので、NextUndoSeqによる後方チェインを用いてこの動作をエミュレートする。実際これは可能。

NextUndoSeqは以下の規則で記録することにする。

- 操作が最初の子でないなら、直前の兄弟を指す。
- 最初の子なら、その親の直前の兄弟を指す。それが無ければ根を指す。
- CLEなら、それが相殺する操作の直前の操作（上2項目の意味で）を指す。