###### tags: `TransactionalInformationSystems`

# 15章 障害回復における諸問題

## 概要

13章、14章で導入してきた障害回復アルゴリズムを、特定の状況に最適化するための拡張を考えていく。例えばマルチプロセッサでメモリが潤沢なシステムでの稼働など。

- 15.2：B+木やその他の大きいデータオブジェクトのロギングに関する問題。
- 15.3：トランザクション中のセーブポイントと、そこへの部分的なロールバックのサポート。
- 15.4：プロセッサの並列性を利用した高速な障害回復。
- 15.5：全データがメインメモリに収まるケースとデータ共有クラスタにおけるケース。
- 15.6：分散メモリシステム。

## 15.2 インデックス/巨大オブジェクトのロギングと回復

### インデックスのページ分割redoのための論理ログエントリ

B+木のようなインデックスは以下のように取り扱える。

- (key,RID)ペアの挿入や削除に伴って変更されるインデックスページごとにログエントリが作成される。
- 高レベル、すなわち挿入や削除そのものの論理的な操作に関するログエントリも作成される（これが前章における$L_1$に相当する）。直下のページ操作すべてが終わってから作成されるので、実質的にこれがsubcommitログエントリの役割も果たす。

ただし、これを正直にやるとかなりログサイズがデカくなる。インデックスページも大きくなるトレンドにあるので（本書の時には64KB程度）、このオーバヘッドが無視できなくなってくる。

そこで、ノード分割という特殊ケースをページレベルではなく、論理的な操作として高レベルに記録することにする。こうすればログの量は減り、高レベルにしたことによって増えるredoのコストもノード分割がレアケースであることから問題にならない。これを実現するには、キーの挿入とノード分割の相互依存性を切り離す必要がある。

そのために、まずキーの挿入に伴って必要となる木の変形を挿入に付属するものではなく、システムが自動実行するトランザクションで行われるものとする。つまり、Insert操作が空間の不足した葉ページを見つけたときには、いったんその操作をブロックし、ノード分割専用のトランザクションを発行し、終わった後にInsertを再開する。ノード分割操作はredoだけ行われ、undoはされないことに注意。

論理的な操作をログした際、redoに際して問題となりうるのは、分割前の左の葉が新しい状態だが、分割後の右の葉が古い状態のままクラッシュするケース。この場合、上半分の値が失われたことになりもとの状態が復元できない。したがって、このようなケースが起きないようにすればよいので、ノード分割に際して新しい葉に対応するページを先にflushする。親ノードも含めて順番をまとめると、(左の子)→(右の子)→(親)の順にflushする。この手法はcareful replacementと呼ばれる。

このflush順の管理が重い場合には、ノード分割操作をさらに2つのトランザクションに分けることもできる。子をそれぞれflushするトランザクションと、親をflushするトランザクション。後者は単一のページのみ取り扱うので自明に原子性が保証される。前者は、最初にflushするべきページ（右の子）の物理的操作ログも追加で記録することでflush順を守る必要がなくなる。前者の終了後にクラッシュした場合は、親ノードのルーティングエントリだけが無い状況になる。通常動作時にこのような状態を検出したら後者トランザクションを再実行する。

ここで考えてきたノード分割論理ロギングは、葉までのパス上で複数の分割が同時に起きる場合に対応できないことに注意。ただし、この制限はflush順序をよく考えることで緩和できる。

### 巨大オブジェクト操作のための論理ログエントリとflush順序付け

例えば巨大なオブジェクトをコピーする操作copy(a,b)を考えたとき、bに関するredoイメージとundoイメージを両方保持すると非常にデカいログになる。redoイメージの代わりに「aをコピーした」ことを示す論理ログエントリを保持し、redoの際にはaから読むことにすればログサイズは半分に削減できる。

ただし、このためにはコピー元オリジナルのaが読み取れる必要がある。aに変更が加えられて永続データベースに反映されてしまうケースにはこれが問題になる。このようなケースをそもそも起きないようにするために、b→aというflush順を強制する。

このようなflush順グラフをキャッシュ管理機構で管理し、ソースから先にflushすることを考える。

ただし閉路が生じた場合には、閉路内のページを全てアトミックにflushする必要が出てくる。これはコストが大きいので、代わりに閉路内の操作全体をfull-writeの物理ログとして記録し、それらのログをまとめてアトミックに永続ログに出力すればよい。物理ログ、すなわちafterイメージが全て保存されているためflush順について気にする必要がなくなる。

ページ間のflush順は、同じ操作の内部でも起こりうる。これも含めてflush order dependency(flush順依存性)を定義しなおすと、「操作fとgがあって、fのread setとgのwrite setに同じページxが含まれ、fのr(x)がgのw(x)よりも先に起こるとき、flush order dependency $writeset(f)-\{x\} \rightarrow x$ が生じる。」

この一般化された手法に基づけば、B+木で複数のノード分割がパス上で起こる場合も取り扱える。

## 15.3 セーブポイント、及びネストされたトランザクション

トランザクション内でセーブポイントを宣言し、部分的なロールバックができるようにしたい。具体的には以下をサポートしたい。

- save(t) でトランザクションt内のセーブポイントを作成し、セーブポイント識別子sを返す。
- restore(t,s) でトランザクションtをセーブポイントsに復元する。

これがあれば、アプリケーション側で処理の分岐に便利だし、またデッドロックを解消するためにサーバ側で利用することもできる。部分的なロールバックによるロックの解放と進捗の再実行をアプリケーションに透過的に行う。

セーブポイントを実装するには、とりあえずセーブポイント作成時にsavepointログエントリを作ることにする。このログエントリのLSNがセーブポイント識別子の機能を果たす。部分的ロールバックの実行時には、このLSNに辿り着くまでNextUndoSeqNoの後方チェインを辿りながらそこまでの操作をundoし、CLEを生成していけばよい。ロールバックの完了時にrestoreログエントリを作る。こうすれば、ここまでで考えてきた回復アルゴリズムの枠組みの中で容易に取り扱える。ネストされたロールバックでも問題が起こらない。

---

セーブポイントの疑似コード

savepoint(transid):
    newlogentry.LogSeqNo := new sequence number;
    newlogentry.ActionType := savepoint;
    newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
    newlogentry.NextUndoSeqNo := ActiveTrans[transid].LastSeqNo;
    ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
    LogBuffer += newlogentry;

部分的ロールバックの疑似コード

restore(transid, s):
    logentry := ActiveTrans[transid].LastSeqNo;
    while logentry != s do 
        // CLEを生成しつつwrite/full-writeをundo
        if logentry.ActionType = write or full-write then
            newlogentry.LogSeqNo := new sequence number;
            newlogentry.ActionType := compensation;
            newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
            newlogentry.RedoInfo := inverse action of the action in logentry;
            newlogentry.NextUndoSeqNo := logentry.PreviousSeqNo;
            ActiveTrans[transid].LastSeqNo := newlogentry.LogSeqNo;
            LogBuffer += newlogentry;
            write(logentry.PageNo) according to logentry.UndoInfo;
            logentry := logentry.PreviousSeqNo;
        end
        // restoreログエントリは飛ばす
        if logentry.ActionType = restore then
            logentry := logentry.NextUndoSeqNo;
        end
    end
    newlogentry.LogSeqNo := new sequence number;
    newlogentry.ActionType := restore;
    newlogentry.TransId := transid;
    newlogentry.PreviousSeqNo := ActiveTrans[transid].LastSeqNo;
    newlogentry.NextUndoSeqNo := s.NextUndoSeqNo;
    LogBuffer += newlogentry;

---

NextUndoSeqNoチェインを利用することで、デッドロックの解消のためにシステムが部分的ロールバックを行ってロックを解放することも許容される。実際、ロックの再取得後に部分的ロールバックによるCLEを再実行することがないため、結果として履歴は先頭削減可能になる。

トランザクション内にネストされたトランザクションを、セーブポイントを用いて実現することができる。つまり、サブトランザクション開始時にセーブポイントを作成し、abortしたいときにはrestoreすることで。記憶する必要があるセーブポイントは、現在アクティブなサブトランザクションから根までのパス上の全サブトランザクション開始時のセーブポイントリストである。

ただし、同一トランザクション内サブトランザクションの並列実行を許可すると問題は複雑になる。この場合、NextUndoSeqNoを一般オブジェクトモデルにおけるものと同様に拡張し、それを辿りながらサブトランザクション直下の操作を全てundoする方法が必要になる。

## 15.4 並列性を利用した再起動の高速化

- ログスキャンを並列化する。
- このためにはログを複数ファイルに分ける必要がある。ページ番号のハッシュ関数値に応じてログエントリを各ファイルに割り振る。
- LSNはファイルをまたいで通用する必要がある
- チェックポイントなどの特殊なログエントリは全てのファイルに存在する必要がある
- 書き込みログエントリは単一ページを指す物理(physical/physiological)ログエントリである必要がある
- こうすれば、同じページに対する書き込みは同じログファイル内に全てあるので、redoパスも完全に並列に実行できる
- undoパスは、各敗者トランザクションごとにundoスレッドを生成して並列実行する
- 複数のページを読む=複数ログファイルを読む必要があるのでそれらのストリームを持つ必要がある

- 回復アルゴリズムの完了前に、通常トランザクションから安全な部分のデータへのアクセスを可能にする。
- 先頭削減可能性を維持するため、どのデータが安全なのか判定する必要がある。
- 敗者トランザクションをundoするために必要な排他ロックを全て獲得し終わった時点で、通常トランザクションの実行開始を許可する方法。
- クラッシュ前のロック状態に戻してから通常動作に戻ることを意味する。
- ロックの再獲得はかなり大きいオーバヘッドを要する。
- 粗い粒度のロックだけ再獲得することにするのもあり。オーバヘッドは少ないし、通常トランザクションがブロックされやすくなるがundoパスが全部終わってから再開されるよりはマシ。
- DirtyPagesリストになく、かつOldestUndoLSNよりもLSNが古いページがもう安全、ということを利用し、それらを新しいトランザクションへ使用許可する方法。

## 15.5 メインメモリデータサーバでの運用

主記憶のみにデータベース全体が格納でき、ディスクI/Oが必要ない状況でのデータベース（メインメモリデータベース）を考える。

こうなると、各トランザクションの実行が高速になるというだけでなく、インデックスの構造がページ指向である必要がなくなる。そもそも、ページの概念をより大きい「セグメント」に置き換えることができる。

また、障害回復アルゴリズムも再考を要する。ここまで見てきたredo-historyを採用する場合も、いくつか見直すべき点がある。書き込みのログエントリを全てphysicalにし、そのafterイメージを読んでいくことでデータベースを復元できるようにする。このとき、ディスクにある永続データベースはもはやただのデータベースバックアップでしかない。というか無くてもいい。実質的に永続ログのafterイメージ群が永続データベースの役割を果たす。

メインメモリデータベースを利用する場合、高可用性が要件であることが多いので、そういった場合には回復ステップの完了前に通常トランザクション実行を開始するのが重要になってくる。これを前節よりもさらにドラスティックな方法でやる。つまり、分析パスが終了した時点で通常トランザクション実行を再開してしまう。通常トランザクションがあるデータアイテムを要求した時点で、そのアイテムに関するredoとundoを遅延評価的に行う。それとは別に、通常のredoパスをバックグラウンド実行する。

undoに関しては、もはやundo情報を永続ログに書き出す必要もない。データベースが常にキャッシュのみから構成されているため。

## 15.6 データ共有クラスタでの運用

複数のプロセッサが、各自のディスクを高速なインターコネクトで相互接続したコンピュータ群をクラスタと呼ぶことにする。メモリは各サーバが独自のものを持つ。

このようなシステムでは障害回復が高速になる。クラッシュしたサーバの分の負荷を他のサーバが請け負い、クラッシュしたサーバのディスク内のデータを読み込むことで通常動作を続行する。

各トランザクションは、ラウンドロビンなどの方法でサーバの一つに割り当てられて実行される。アクセスしたいページがcleanなら共有ディスクからフェッチしてきて、dirtyならメモリにキャッシュを持っている他のサーバから持ってくる（data shipping）。データの局所性を利用するために、トランザクションの操作を別サーバに分配するfunction shippingという概念もあるが、あまり利用されない。

複数のサーバが同じページのキャッシュを持っていて別の変更を加えると、データに不整合が生じる。これを防ぐため、クラスタでは、サーバ間のデータの整合性を維持するメッセージベースの「一貫性制御プロトコル（coherency control protocol）」が必要になる。これは18章で深く踏み込むが、この章で重要なのは、ページ指向の一貫性制御は以下の不変条件を保証する必要がある点。

- 最新バージョンのページに関するキャッシュは、それに変更がなされない限り複数のサーバが持つことができる。
- あるサーバのキャッシュに変更が加えられたら、そのキャッシュのみが唯一許されるものになる（他のサーバの古いキャッシュは無効になる）。

クラスタの性質を利用するため、永続ログはサーバごとに持つことにする。（ログファイルを15.4のようにページ単位で割り振った場合、サーバ間でのデータのやり取りが大きくなり、インターコネクトがボトルネックになる。）こうすると、あるページに対する操作のログエントリが複数のログファイルに分散することになり、これらの順序を明確にすることが必要になる。

複数のサーバ間で通用するLSNが必要になるわけだが、ここで各LSNが同じページに対する操作内でのみ単調増加であればよいという点に着目する（undoはCLEの利用によってLSN検証を必要としないので、redoのみがLSN検証を要する）。そこで、ページ $p$ のpage sequence numberを

$$\max\{\text{current sequnce number in the page header of } p, \\
\text{largest local LSN used so far}\}+1$$

と定義しなおす。

ここまで考えてきた永続ログは他サーバからもアクセス可能なので、クラッシュしたら、そのサーバが再起動する前に他サーバが障害回復ステップを代理実行してしまう（failover）ことで回復が効率化される。

なお、ページキャッシュがサーバ間移動するときにflushもバックグラウンドで強制することにすれば、redoパスの際にも自サーバの永続ログしか読む必要がなくなるのだが、複数ログファイルを読むことのオーバヘッドはそれほど大きくないのでどちらでもよい感がある。