###### tags: `TransactionalInformationSystems`

# 13章-3 ログ切り捨て・チェックポイント・Redo最適化

## 単純3パスアルゴリズムのパフォーマンスに関する問題

1. 分析パスが永続ログの全体を走査する必要がある。これは高コストになりうる。
2. redoパスが永続ログの全体を走査する必要がある。多くの勝者トランザクションは既に永続データベースにflushされているはずなので、全部見るのは無駄が多い。
3. redoパスが、永続データベースからページをフェッチするためのI/O負荷が大きい。PSN検証を行うためにもページが必要なので、結果的にredoが必要なかったページに関しても無駄にフェッチしてしまう。

1つ目に対してはlog truncation（ログ切り捨て）で、

2つ目に対してはcheckpoints（チェックポイント）で、

3つ目に対してはlogging of flush actions（flushロギング）で改善する。

## Log Truncation（ログ切り捨て）

永続ログの中には、既に障害回復に必要ないログエントリが溜まっていく。

- ページ$p$に対するログエントリで、LSNが$s$であるものは、永続データベースのページ$p$のPSNが$s$以上の場合、redoパスにおいて不要である。
- 完了したトランザクションのログエントリは、undoパスにおいて不要である。

redoにもundoにも必要とされなくなったログエントリは、永続ログから削除しても問題ないわけである。これを削除して永続ログを短く保つのがログにおけるガーベジコレクション。

ログエントリの一部を細かく削除していくのはI/Oに負荷をかけるので、もっと単純に、ログのプレフィクスを削除することを考える。こうすれば、単に永続ログの始点を示すマスタレコードを更新するだけで実装できる。新しい始点を定めるにあたっては、不要であることが確定しているエントリだけを可能な限り削りたい。これは以下で定義するSystemRedoLSN、OldestUndoLSNの最小値で求められる。

### SystemRedoLSN

dirty(書き込まれている)な各ページ$p$について、直近のflush操作の直後に行われた書き込み操作のLSNをredo log sequence number(RedoLSN)と定義する。全てのdirtyなキャッシュされているページのRedoLSNのうち最小値をSystemRedoLSNと定義する。

RedoLSNは各ページをredoするための始点であり、それらの最小値がredoパスの始点として最低限必要というわけである。

### OldestUndoLSN

アクティブなトランザクションに属する書き込み操作のうち最も古いLSNをOldestUndoLSNと定義する。undoパスには最悪ここまで巻き戻る必要があるわけである。

### SystemRedoLSN・OldestUndoLSNの実装オーバヘッド

OldestUndoLSNに関しては、各トランザクションについて、beginの実行に際してそのLSNを保存するだけで実現可能。

SystemRedoLSNに関しては、キャッシュ管理機構を少しだけ拡張するだけでよい。具体的には、ページがキャッシュにフェッチされた直後の書き込み操作のLSNを記録するようにすればよい。また、flushされたがキャッシュに残った場合は、RedoLSNをundefinedにセットし直せばよい。

だいたいログ切り捨ては5分～10分ぐらいの間隔で実行するのがよいとのこと。

### ログ切り捨てでうまいこと削れないケース

まず、最初に書き込み操作を行ったトランザクションがクラッシュ時点までずっとアクティブだった場合、一切ログ切り捨てができないことになってしまう。ただ、本当に長い手続きというのは短いトランザクションに分けて実行されるものなので、このような状況はあまり起きない。ということで問題にしない。

次に、dirtyなページが長いことflushされていなかった場合、そのページのRedoLSNが始点となってしまってログ切り捨てがうまくいかない。さすがに何時間もflushされないなんてことはないだろうが、それなりに長くはなりうるので、こういったページはログ切り捨てに際して強制的にflushしてしまうのがよい。

---

### 疑似コード

これらを含めて、ログ切り捨ては以下の手順で実行できる。この手順はガーベジコレクション規則を満たす。

log-truncation():
    OldestUndoLSN := min{i|StableLog[i].TransId is in ActiveTrans};
    SystemRedoLSN := min{DatabaseCache[p].RedoLSN};
    OldestRedoPage := page p s.t. DatabaseCache[p].RedoLSN = SystemRedoLSN;
    NewStartPointer := min{OldestUndoLSN, SystemRedoLSN};
    OldStartPointer := MasterRecord.StartPointer;
    while OldStartPointer - NewStartPointer is not sufficiently large and SystemRedoLSN < OldestUndoLSN do
        flush(OldestRedoPage);
        SystemRedoLSN := min{DatabaseCache[p].RedoLSN};
        OldestRedoPage := page p s.t. DatabaseCache[p].RedoLSN = SystemRedoLSN;
        NewStartPointer := min{OldestUndoLSN, SystemRedoLSN};
    end
    MasterRecord.StartPointer := NewStartPointer;

---

ちなみに、勝者トランザクションによるfull-writeがあった場合、そのページに対するそれ以前のログエントリは全く必要ないので削除しても問題ない。これをさらに発展し、redoステップを極めて効率的にするdatabase safeなる概念が研究されているそう。ただし、redoログに後イメージが必須で、かつundoログを別個に保存する必要がある。

そこまで極端にやらなくても、ログ管理機構側で定期的に後イメージを保存することで、ページをflushすることなくそれ以前のログエントリを不要にするハイブリッドなアプローチが可能。

## Checkpoints（チェックポイント）

redoパスと分析パスを十分に短くするため、チェックポイントという概念を導入し、定期的に作成できるようにする。なお、チェックポイントは**単にパフォーマンスを改善するための概念であり、あろうとなかろうと正当性には一切影響しない**ことに注意。

### Heavyweight checkpoint（重チェックポイント）

全てのdirtyなページを強制的にflushすることもでき、この時点をheavyweight checkpoint(重チェックポイント)と呼ぶ。重なのは、あとでより軽量なチェックポイントの概念が出てくるため。

これの良さは、redoパスがチェックポイント以前を参照する必要がなくなること。最新のチェックポイントを即座に特定するため、チェックポイント作成後にそれ用のログエントリを永続ログに記録し、また最新のチェックポイントログのLSN(LastCP)をマスタレコードに保存しておく。

これによってredoパスは効率化し、undoパスもそれほど長くならないことが期待されるので、今度は分析パスがボトルネックになる。これを、チェックポイント作成時にさらに情報を付加することで改善する。

チェックポイント作成時にアクティブなトランザクションのリストを、ついでにログに記録しておく。アクティブなトランザクション＝潜在的な敗者なので、最新のチェックポイントから分析パスを始めてcommitログエントリが存在したトランザクションを削除していくことで、効率的に分析パスを完了できる。

ただし、分析パスで作成する敗者トランザクションのリストには、それぞれの最後の操作のLSNも必要であることに注意。そのため、アクティブなトランザクションのリストに加えて、それらのトランザクションの最後の操作に対応するLSNを保存しておく必要がある。

---
#### 重チェックポイントの疑似コード

checkpoint():
    for each p in DatabaseCache do
        if DatabaseCache[p].Status = dirty then
            flush(p);
        end
    end
    logentry.ActionType := checkpoint;
    logentry.ActiveTrans := ActiveTrans (as maintained in memory);
    logentry.LogSeqNo := new sequence number;
    LogBuffer += logentry;
    force();
    MasterRecord.LastCP := logentry.LogSeqNo;
    
analysis-pass() returns losers;
    cp := MasterRecord.LastCP;
    losers := StableLog[cp].ActiveTrans;
    max := LogSeqNo of most recent log entry in StableLog;
    for i := cp to max do
        case StableLog[i].ActionType:
            // 省略
        end
    end
    
redo-pass():
    cp := MasterRecord.LastCP;
    max := LogSeqNo of most recent log entry in StableLog;
    for i := cp to max do
        // 省略
    end

---
結局、全てのページをflushするI/O負荷がデカすぎるので、より動作の軽いチェックポイントの概念に移ることにする。

### Lightweight checkpoint（軽チェックポイント）

分析パスとundoパスについては重チェックポイントと全く同じ効果が、redoパスについては重チェックポイントほど短縮できないがログ切り捨てと同程度の効果がある「軽チェックポイント」を導入する。

チェックポイント作成時に、ページをflushする代わりに以下の情報を記録する。

- その時点でキャッシュされているdirtyなページ
- dirtyな各ページについて、直近のflush操作の直後に行われた書き込みのLSN

これらの書き込みLSNの最小値がredoパスの始点となる。これはログ切り捨てと同様。

また、これらの値を持っておくことで、redoパスの際、チェックポイント以前の勝者による書き込みが永続データベースに反映されているかをフェッチすることなく判定することができ、redoパスのパフォーマンスも改善する。

---
#### 軽チェックポイントの疑似コード

checkpoint():
    DirtyPages := empty;
    for each p in DatabaseCache do
        if DatabaseCache[p].Status = dirty then
            DirtyPages += p;
            DirtyPages[p].RedoSeqNo := DatabaseCache[p].RedoLSN;
        end
    end
    logentry.ActionType := checkpoint;
    logentry.ActiveTrans := ActiveTrans (as maintained in memory);
    logentry.DirtyPages := DirtyPages;
    logentry.LogSeqNo := new sequence number;
    LogBuffer += logentry;
    force();
    MasterRecord.LastCP := logentry.LogSeqNo;

analysis-pass() returns losers, DirtyPages:
    cp := MasterRecord.LastCP;
    losers := StableLog[cp].DirtyPages;
    max := LogSeqNo of most recent log entry in StableLog;
    for i := cp to max do
        case StableLog[i].ActionType:
            // 省略
        end
        if StableLog[i].ActionType = write or full-write and StableLog[i].PageNo not in DirtyPages then
            DirtyPages += StableLog[i].PageNo;
            DirtyPages[StableLog[i].PageNo].RedoSeqNo := i;
        end
    end

redo-pass():
    cp := MasterRecord.LastCP;
    SystemRedoLSN := min{cp.DirtyPages[p].RedoSeqNo};
    max := LogSeqNo of most recent log entry in StableLog;
    for i := SystemRedoLSN to max do
        if StableLog[i].ActionType = write or full-write and StableLog[i].TransId not in losers then
            pageno := StableLog[i].PageNo;
            if pageno in DirtyPages and i >= DirtyPages[pageno].RedoSeqNo then
                fetch(pageno);
                if DatabaseCache[pageno].PageSeqNo < i then
                    read-and-write(pageno) according to StableLog[i].RedoInfo;
                    DatabaseCache[pageno].PageSeqNo := i;
                else
                    DirtyPages[pageno].RedoSeqNo := DatabaseCache[pageno].PageSeqNo + 1;
                end
            end
        end
    end

---

## Flush Log Entries（flushロギング）

redoパスに際して、既に書き込みが反映されているのに無駄なページフェッチを行ってしまうケースが発生する。

直近のチェックポイントの後にflushが実行されたページでそのようなケースが起こる。このようなページをredoパスの最中にフェッチしてしまうのを防止するため、flush操作でもログエントリを作成し、分析パスの最中にflushログエントリを発見したらそのページをdirtyリストから削除する。

### 疑似コード

analysis-pass() returns losers, DirtyPages:
    cp := MasterRecord.LastCP;
    losers := StableLog[cp].ActiveTrans;
    DirtyPages := StableLog[cp].DirtyPages;
    max := LogSeqNo of most recent log entry in StableLog;
    for i := cp to max do
        case StableLog[i].ActionType:
            // 省略
        end
        if StableLog[i].ActionType = write or full-write and StableLog[i].PageNo not in DirtyPages then
            DirtyPages += StableLog[i].PageNo;
            DirtyPages[StableLog[i].PageNo].RedoSeqNo := i;
        end
        // 追加部分。flushログを発見したらそのページをDirtyPagesから除外
        if StableLog[i].ActionType = flush then
            DirtyPages -= StableLog[i].PageNo;
        end
    end

### 定理13.4 正当性の維持

単純3パスアルゴリズムをログ切り捨て・重/軽チェックポイント・flushロギングで拡張しても、正当に障害回復できる。

#### 証明

ログ切り捨てはガーベジコレクション規則を満たしているので正当性を維持する。

チェックポイントとflushロギングについては、直近のチェックポイント以後のログについてのみ考えればよい（それ以前のログについては単純3パスの分析パスでも全く同じ動作をするため）。

チェックポイント及びflushロギングを用いたredoパスの最中には以下の不変条件が成立する。

$$\forall \text{ pages } p:
\\ \forall \text{ operations } o\in \text{stable log}:
\\ (o \text{ refers to } p \land (p \notin \text{DirtyPages } \lor o < \text{DirtyPages[p].RedoSeqNo }))
\\ \Rightarrow o\in \text{stable database }$$

$\square$

## 完全なアルゴリズム（Abortの取り扱い+Undo済みログエントリの追加）

### Abortの組み込み

これまで考慮してこなかった、「通常動作中にabortされロールバックされたトランザクション」の取り扱いを組み込んでいく。

ロールバックが既に完了済みということは、言い換えれば、結果的に「何の操作もせずにcommitされた勝者トランザクション」として取り扱えるということである。障害回復において、このようなトランザクションによる影響が最終的に反映されなければよい。

具体的には、ロールバックに際して、逆操作のログも順操作と同様にログに記録し、障害回復の際これらを区別なく取り扱うことでロールバック済みのトランザクションも勝者として取り扱える。逆操作のログエントリは便宜的に相殺ログエントリ(compensation log entry, CLE)と呼ぶことにする。ロールバックの終了時点でログのforceが必要なことに注意（なぜなら、ロールバックがcommitに相当するため、redoログ規則を満たす必要がある）。

この取り扱い方をすると、ロールバック中にクラッシュが発生した場合に単に敗者トランザクションとして取り扱われるので非常にシンプルになる。

abort(transid):
    logentry := ActiveTrans[transid].LastSeqNo;
    while logentry is not nil and logentry.ActionType = write or full-write do
        newlogentry.LogSeqNo := new sequence number;
        newlogentry.ActionType := compensation;
        newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
        newlogentry.RedoInfo := inverse action of the action in logentry;
        newlogentry.UndoInfo := inverse action of the inverse action of the action in logentry;
        ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
        LogBuffer += newlogentry;
        write(logentry.PageNo) according to logentry.UndoInfo;
        logentry := logentry.PreviousSeqNo;
    end
    newlogentry.LogSeqNo := new sequence number;
    newlogentry.ActionType := rollback;
    newlogentry.TransId := transid;
    newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
    LogBuffer += newlogentry;
    ActiveTrans -= transid;
    force();

#### 定理13.5

ロールバック取り扱い拡張は3パスアルゴリズムの正当性を維持する。

##### 証明

ロールバックが完了した際は勝者として、途中でクラッシュした場合は敗者として取り扱われる。

ロールバックが完了して勝者として取り扱われた場合、永続ログに順操作と逆操作が全て記録されている。もとの履歴がconflict serializableかつログ復元可能という仮定から、これらを再実行することで、他のトランザクションに影響を与えずにもとのトランザクションをやり直すことができる。もとの履歴は先頭削減可能なので、これは空トランザクションが実行されたのと等しく、障害回復は正しく実行される。

ロールバック途中にクラッシュした場合、既に永続データベースに影響を与えている書き込み操作に関してはすべて永続ログに記録されている。トランザクションを敗者として扱うので、これらの操作は逆順にundoされる。これは実質的に通常の敗者トランザクションをundoしているのと等価であり、障害回復完了後に改めてロールバックの完了操作まで実行された時点で、影響が空トランザクションと等価になる。もとの履歴がCSRかつLRCなので、これは他のトランザクションに影響を与えない。$\square$

### Undo済みログの作成

これまでは、3パスの終了後、全てのdirtyなページをflushするという前提の下でアルゴリズムを考えてきた。ただし、これは障害回復の直後にI/Oに重大な負荷を引き起こすので、やめたい。

ただ、回復後のflushを完全にやめてしまうと、アクティブなトランザクションによって変更されたdirtyなページが残ってしまいやすくなり、これはログ切り捨てに悪影響を及ぼす。

そこで、敗者トランザクションによる変更があったページのみを最後（undoパスの後）にflushすることにし、それが完了したら各敗者トランザクションに関するundo-completeログエントリを作成することにする。

こうすれば、敗者トランザクションのundoが間違いなく永続データベースに反映され、またそれらを二度と行う必要が無いことが永続ログに明示される。以降、undo-completeログエントリを持つトランザクションは完全に無視される（＝削除しても問題ない）ことになる。

通常動作中にロールバックされたトランザクションが勝者として扱われ、クラッシュ時にアクティブだったトランザクションがこのように完全に無視されるという取り扱いの非対称性が気になるが、これはredo-winnersパラダイムを取り扱う以上仕方ない問題とのこと。次に導入されるredo-historyパラダイムならこれらのトランザクションが全く等価なものとして一様に取り扱える。

---

#### 疑似コード

undo-pass():
    FlushList := empty;
    while there exists t in losers s.t. losers[t].LastSeqNo <> nil do
        nexttrans := TransNo in losers s.t. losers[TransNo].LastSeqNo = max{losers[x].LastSeqNo|x in losers};
        nextentry := losers[nexttrans].LastSeqNo;
        if StableLog[nextentry].ActionType = write then
            pageno := StableLog[nextentry].PageNo;
            fetch(pageno);
            if DatabaseCache[pageno].PageSeqNo >= nextentry.LogSeqNo then
                read-and-write(StableLog[nextentry].PageNo) according to StableLog[nextentry].UndoInfo;
                DatabaseCache[pageno].PageSeqNo := nextentry.LogSeqNo - 1;
                FlushList += pageno;
            end
            losers[nexttrans].LastSeqNo := StableLog[nextentry].PreviousSeqNo;
        end
    end
    for each p in FlushList do
        flush(p);
    end
    for each t in losers do
        newlogentry.LogSeqNo := new sequence number;
        newlogentry.ActionType := undo-complete;
        newlogentry.TransId := losers[t].TransId;
        LogBuffer += newlogentry;
    end
    force();

---

#### 定理13.6

障害回復ステップの終了後全dirtyページをflushせずとも、loserのみflushし、undo-completeログエントリを作成することで、3パスアルゴリズムの正当性は維持される。