###### tags: `TransactionalInformationSystems`

# 13章-1 基本的なデータ構造

## 概要

with-redo/with-undoアルゴリズムであることは前提とする。

したがって回復ステップにはredoおよびundoに相当する操作を実行する必要があるが、それには2種類のアプローチがある。

- redo-winnersパラダイム：redoステップで反映しなおす操作を、commitされたトランザクションのもののみ、つまり勝者(winner)のトランザクションのみに限定する。
- redo-historyパラダイム：commitされたかどうかに関わらず、履歴にある全ての操作を反映しなおす。

どちらのパラダイムを使うにせよ、共通して議論しなければならない問題が以下に挙げられる。

- redoステップのために、ログを時間方向にスキャンしながら操作をやり直していく必要がある。この際に、パフォーマンスを改善するための様々な最適化が考えられ、例えばチェックポイント作成などがある。
- undoステップは逆方向のログスキャンを必要とする。
- 恒等でない書き込み操作(partial write)は、2回以上実行されないように注意深く回復を行う必要がある。基本的には、ページごとにタイムスタンプのような連番を付与し、それを確認することで重複を回避する。
- 通常の動作中にabortされ、障害発生時には既に完全にロールバック済みのトランザクションにも特別な注意を要する。

### 回復アルゴリズム導出の道筋 (振り返って後付け)

まずredo-winners

- 書き込みをfull-writeに限定した単純な3パスアルゴリズム
- Page state testingに基づいた一回のみのredo/undo保証→一般のwriteも組み込んだ3パスアルゴリズムを得る
- 永続ログが長くなるので要らない部分を削除したい→ログ切り捨て
- 分析パス・redoパスを短くしたい→チェックポイント
- redoパスの無駄なページフェッチを無くしたい→flushロギング
- 通常動作中のロールバックも取り扱いたい・回復後の全ページflushをなくしたい→完全形

次にredo-history

- 全書き込みをredoし、undoパスは通常のロールバックと等価に取り扱う
- チェックポイントなどの技術はこちらでもそのまま使える

## データ構造

まず、永続ログは末尾に順次ログエントリを付加していくファイルを想定する。各ログエントリは、時間に関して単調増加なlog sequence number(LSN)でタグ付けして実行時刻を区別する。同様にして、各ページにもpage sequence number(PSN)を持たせることで、各操作がページに反映されているかどうかの判定を行えるようにする。

各ログエントリが持つ要素は、そのエントリのLSN、操作の種類、操作したページの番号、その操作の属するトランザクション、そしてそのトランザクションにおける直前の操作のLSNである。直前の操作のLSNも保持することで、各トランザクションについて逆方向への連結リスト的な探索が可能になる。

### 疑似コード

// ページ
type Page: record of
    PageNo: identifier;
    PageSeqNo: identifier;
    Status: (clean, dirty);
    Contents: array [PageSize] of char;
end;

// 永続データベース
persistent var StableDatabase:
    set of Page indexed by PageNo;

// データベースキャッシュ
var DatabaseCache:
    set of Page indexed by PageNo;

// ログエントリ
type LogEntry: record of
    LogSeqNo: identifier;
    TransId: identifier;
    PageNo: identifier;
    ActionType: (write, full-write, begin, commit, rollback);
    UndoInfo: array of char;
    RedoInfo: array of char;
    PreviousSeqNo: identifier;
end;

// 永続ログ
persistent var StableLog:
    ordered set of LogEntry indexed by LogSeqNo;
    
// ログバッファ
var LogBuffer:
    ordered set of LogEntry indexed by LogSeqNo;

// トランザクション情報
type TransInfo: record of
    TransId: identifier;
    LastSeqNo: identifier;
end;

// アクティブなトランザクション
var ActiveTrans:
    set of TransInfo indexed by TransId;

### full-write用ログ

full-write、つまりページ全体の書き込みを行う操作のログは、before image(前イメージ)とafter image(後イメージ)のそれぞれを保持することでredoとundoを可能にする。

### partial write用ログ

partial writeのログは、full-writeとは異なる形で記録しうる。例えばシフト操作を行ったのなら、どこのバイトをどれだけシフトしたか+前イメージだけ記録しておけば十分である。ただし、このような操作は単一のページにしか影響を与えてはならず、すなわちページをまたぐような操作は許されない。このような操作は必ずしも恒等でないことに注意。

### データ構造と抽象モデルの対応

上記疑似コードで定義したデータ構造と抽象モデルの間に取れていてほしい対応：

- sequence numberが$s$である操作が永続ログに含まれる $\Leftrightarrow$ LSN $s$がStableLogに含まれる
- sequence numberが$s$である、ページ$p$に対するwrite/full-write操作が永続データベースに含まれる$\Leftrightarrow$
$$StableDatabase[p].PageSeqNo \geq s$$
- sequence numberが$s$である、ページ$p$に対するwrite/full-write操作がキャッシュデータベースに含まれる$\Leftrightarrow$ $p$がDatabaseCacheに含まれ、かつ $$DatabaseCache[p].PageSeqNo\geq s$$ もしくは $$StableDatabase[p].PageSeqNo \geq s$$ を満たす。

これらを保証するために最も採用されている方法は、PSNを、「そのページを参照するログエントリのLSNのうち最大値」として定義すること。実装が簡単。

$$DatabaseCache[p].PageSeqNo := \max \{s.LogSeqNo \mid \\ s \text{ is a log entry, in the log buffer or in the stable log, with } s.PageNo = p\}$$