###### tags: `TransactionalInformationSystems`

# 16章 メディアの回復

## 概要

13,14,15章ではクラッシュの際にディスクが無事である前提のアルゴリズムを考えてきた。

ここではディスクを始めとしたメディア自体のデータが障害で失われるケースを考える。1つのメディアに障害が発生しても、そのメディアのデータを復元できるアルゴリズムを考えていく。複数の障害が短期間・複数メディアで発生した場合の復元には追加のオーバヘッドが必要だが、ディスクストレージは基本的に高信頼性を特徴とし、複数の障害が同時に起こることはほぼないので基本的に取り扱わない。

また、ハードウェア障害より広いクラス（バグを含んだソフトウェアの実行や災害など）の「環境障害」にもメディア回復を応用する方法を考える。

メディア回復は基本的にデータの冗長性を利用して復元する手法だが、冗長性の持ち方に種類がある。

- バックアップを定期的に取るログベースの方法。
- 古くなりやすく、commitしたトランザクションが一部失われる。
- 失われたデータをredoするために、拡張されたログ（アーカイブログ）を記録する必要がある。
- ストレージ自体に冗長性を組み込む方法。
- RAIDシステムを構築するとか、ミラーディスクを使うとか。
- ソフトウェアバグや環境障害には弱い。

これらの方法を組み合わせて使うのが普通。

メディア回復手法の効率性の基準は3つ。

1. 可用性。MTTRが短くMTTFが長いほど高い。
2. データの生存レベル＝同時に何個までの障害を回復できるか。ここでは基本的に1とする。
3. 平均データ損失時間(mean time to data loss, MTTDL)＝あるデータが完全に失われ復元できなくなるまでの期待時間。2の生存レベルをより時間方向に定量的に評価した基準で、単一の障害のMTTRに大きく影響される。

## ログベースの手法

はじめにバックアップをメディアにコピーし、そこからアーカイブログを利用して分析パス/redoパス/undoパスを行う。アーカイブログは永続ログをコピーすることで実現できるが、直前のバックアップ以降のエントリを全て保存する必要があるので、障害回復用の永続ログと比べて非常に長くなる。

### バックアップとアーカイブログの取り方

- バックアップが「完全」＝データを全てコピーしている
- バックアップが「増分」＝直前のバックアップから変更されたページのみを保存している

これらの選択は通常動作時と回復時のパフォーマンスのトレードオフでどちらを重視するかによる。

#### バックアップの取り方

バックアップの取り方を考える。

通常動作中にバックグラウンドプロセスとしてバックアップを取ると、現在アクティブなトランザクションによる変更の影響を部分的に受ける。したがってバックアップ単体ではデータの整合性がなく、メディア回復のredoパスにおいて整形する必要がある。

free space management table（空き空間管理テーブル）をスキャンし、これを連続するページにコピーしていくことでバックアップをとる。管理テーブルが持っているフラグで各ページがdirtyかどうか判定できる。ただし、この管理テーブルのフラグ自体も障害で間違った情報になる可能性があり、それは回復の最中に考慮する必要がある。

バックアップを取るのは時間がかかるため、その最中にクラッシュが起きることも考慮する必要がある。チェックポイントログエントリに現在のスキャン位置を保存しておくことで、障害回復からの再開後に無駄なやり直しを避けることができる。

バックアップ開始/終了時にbegin-backup/end-backupログエントリを作成する。

#### アーカイブログの取り方

アーカイブログは、基本的に直前の完全なバックアップ以降の永続ログエントリを全て集める。永続ログを別ディスクに単純に複製するもよし、定期的に永続ログを別個のアーカイブログにコピーするもよし。

このとき、以下のログ切り捨てに関する規則を満たす必要がある。

- begin-backupログエントリ以降のすべてのログエントリは、次の完全なバックアップが完了するまで保存されなければならない。
- これが「直前の完全なバックアップ以降の」ということ。ただしこれだけではなく、もう2つの規則がある。
- バックアップ取得プロセスがキャッシュを無視して誤ったバージョンのページをコピーしたとき、begin-backup時点でのSystemRedoLSNに続くすべてのログエントリが保存されなければならない。SystemRedoLSNが進められてもこのマーカーは不変。
- バックアップが敗者トランザクションによる変更を含んでいることが分かったとき、OldestUndoLSNに続くすべてのログエントリが保存されなければならない。OldestUndoLSNが進められたらその分は必要なくなる。
- バックアッププロセスの間ずっと生きているトランザクションはそうそうないので、アーカイブログの切り捨てに関してはこれはあまり問題にならない。

これらのうち最小値がアーカイブログをガーベジコレクションするための基準点となる。これをMediaRecoveryLSNと表記する。

### メディア回復手順

以下の疑似コードに示されるように、回復手順はシンプル。分析パスは敗者トランザクションリストを作るだけなので、undoパスの直前でよく、また直近のチェックポイントから開始してよい。

restore(pageset):
    for each page in pageset do
        identify the most recent backup that contains a copy of the page;
        copy the page onto the replaced disk;
    end
    perform redo pass on the archive log using the redo-history algorithm,
        starting from MediaRecoveryLSN and
        ignoring all log entries that do not refer to pages in pageset;
    perform analysis pass on the log, starting from most recent checkpoint,
        to identify loser transactions;
    perform undo pass on the log for loser transactions;

バックアップに裏でredoを適用して最新に近いshadow database（シャドウデータベース）を保持したり、ログ分割をしたりしてredoパスを高速にできるが、それでも回復には数十分から一時間単位の時間がかかる。これだけだと力不足なので、さらにストレージの冗長化を考えていくわけだが、ログベースの方法にはディスク障害以外のソフトウェアによるバグなどに対処できる利点があるので、結局どちらも併用するのが肝要。

データの生存レベルはバックアップとアーカイブログの複製数に依存する。m個の複製を保持していれば、同時にm件の障害に耐えうる。

ここで単一のバックアップしか保持しない場合、平均データ損失時間は

$$MTTDL = \frac{MTTF}{3}\cdot \frac{MTTF}{2(MTTR_{rec}+MTTR_{back})}$$

これはマルコフ連鎖から導かれる。

MTTRが1時間なら、典型的なディスクはMTTFおよそ50年程度なので、MTTDLはおよそ1250万年程度と計算され、まず問題ない値になる。

## ストレージの冗長化

冗長化には2つのクラスがある。

- データを複数のディスクにミラーする。
- 誤り訂正符号(ECC)を保持する。

これらの良い特徴は、ダウンする時間が無いということ。つまり可用性100%。障害を起こしたディスクに代わり、既にストレージコントローラに接続されたホットスタンバイのスペアディスクにデータを復旧することでこれを実現する。

### ミラーリングに基づく冗長化

単純に2つのディスクにミラーリングを行う場合、MTTDLは

$$MTTDL_{\text{simple mirroring}} = \frac{MTTF}{2} \cdot \frac{MTTF}{MTTR_{\text{simple mirroring}}}$$

(ディスクのどちらかに障害が起こる確率が$\frac{2}{MTTF}$、障害回復中にもう一方のディスクに障害が起こって復旧不可能になる確率が$\frac{MTTR_{\text{simple mirroring}}}{MTTF}$、この積の逆数が平均データ損失時間)

ミラーリングされたペアを合計$N$個持つシステムでは、この$N$倍がMTTDLになるというわけ。

#### 分散ミラーリング

単純に2つのディスクに全く同じ内容をミラーリングすると、障害が一方に起こった際にもう一方のディスクへの負荷が2倍になり、パフォーマンスに悪影響を及ぼす。よって、$G$個1単位のグループの各ディスクを2つの領域に分割し、一方では自身のディスクの内容を保持、もう一方でグループ内の他ディスクのブロック群をラウンドロビン的にミラーリングする。あるディスクで障害が起こったとき、そのディスクの内容は残り$G-1$個のディスクが分散して持っているので、回復のためにかかる負荷もこれら$G-1$個に分散される。

分散ミラーリングの利点は回復時のパフォーマンス低下を避けられること、MTTRを短くすること。欠点は障害が2つのディスクに発生するだけでデータが失われてしまうこと。よって$G$の選択は難しい。なお、MTTDLは

$$MTTDL_{\text{declustered mirroring}} = \frac{MTTF}{G} \cdot \frac{MTTF}{(G-1)\cdot MTTR_{\text{declustered mirroring}}}$$

ここから分かるように、MTTDLは$G$の2乗に反比例して減少してしまう。$G=4$から$16$ぐらいが妥協点になる。

### 誤り訂正に基づく冗長化

いくつかのブロックから計算したパリティブロックを誤り訂正用に保存するというアイディア。RAIDアーキテクチャはこれに基づく。なお、パリティのブロック数を1にした特別ケースは単純にブロックをミラーリングすることに等しい（＝RAID-1）。

#### RAID-4

RAID-4は、実際のデータを保持するディスク数を$N$としたとき、それにパリティディスクを加えた$N+1$個を1単位として運用する。

ディスク内のアドレス空間を複数のブロックに分ける。$N$個のディスクの同じアドレスにあるブロックをまとめてパリティグループと呼ぶことにし、各パリティグループから計算したパリティブロックを$N+1$個目のパリティディスクに保存する。

パリティは$N$個のブロックのXORとする。こうすることで、あるブロックに変更が加えられたとき、対応するパリティブロックの更新は (パリティブロック)$\oplus$(変更前のブロック)$\oplus$(変更後のブロック) で行える。この更新にかかるオーバヘッドは古いブロック内容の読み込みとパリティブロックの読み込みという追加2回の読み込みである。RAIDアーキテクチャではこのオーバヘッドはsmall-write penaltyと呼ばれる。同じパリティグループのブロックに一気に書き込む場合にはパリティブロックを読み込むオーバヘッドの割合が小さくなるが、そういう工夫がしづらい細かい書き込みを多用するケースではコストがRAIDを使用しない場合の2倍以下程度になる。

RAID-4では単一のパリティディスクに負荷が集中した場合に問題となるので、さらにパリティの分散を考慮したRAID-5が導入される。

#### RAID-5

$N+1$個のディスクを1単位としてパリティブロックを用意するところまではRAID-4と同じであるが、$k$番目のパリティブロックを $(k-1)\mod(N+1)+1$ 番目のディスクに配置するように変更したものがRAID-5。これにより、パリティを計算するための負荷は各ディスクに均等に分散される。

MTTDLは

$$MTTDL_{\text{RAID-5}} = \frac{MTTF}{N+1} \cdot \frac{MTTF}{N\cdot MTTR_{\text{RAID-5}}}$$

さらにI/Oコストを減らすために、パリティブロックの配置をラウンドロビンですらなく動的に割り当てる(floating parity)方法もある。

また、ディスクが非揮発性のRAMキャッシュを備えていれば、変更されたパリティブロックを一時的に保存して、専用のログ領域に一気に書き込む方法(parity logging)もある。ログ領域は全ディスクに分散され、I/O負荷をバランスする。当時最もsmall-write penaltyを軽減できる手法だったとのこと。

パリティブロックをさらに$N+1<C$を満たす$C$個のディスクに分散し、さらに負荷を減らすdeclustered parity block(=clustered RAID)なる方法も可能。

#### RAID-6

RAID-4もRAID-5も生存レベルは1である。パリティをリードソロモン符号のような2個以上の誤りを訂正できる符号に置き換えることで、生存レベルを2以上にしたRAID-6を考えることができる。ただしI/Oコストは増加する。

### 再構築アルゴリズム

障害により失われたディスク内容の再構築は単に他ディスクからのXORを計算することでも可能だが、もう少し効率の良い方法も探ってみる。

一つは、再構築作業の最中にも、完了したブロックに関しては通常トランザクションからの読み込みを許すこと。再構築の進捗を追跡する必要がある。

もう一つは、再構築用のディスクI/Oをうまくスケジューリングすること。優先度を低くしてバックグラウンドプロセスとして動かす。読み込み要求が来たブロックを積極的に再構築してRAMに残し、十分にそのようなブロックが溜まった時点で一気にディスクに書き込む。

## 災害からの回復

ログベースの手法は、災害からの回復にも応用できる。バックアップとアーカイブログを遠隔のデータセンターに保存し、これらを高速な回線でつなぐことで局地的な災害発生時にはデータの損失を防げる。

単純にログを第二センターに送る(log shipping)場合は、二か所のセンターのログの内容にラグが発生する。これは全トランザクションを分散システムにおけるトランザクションとして走らせれば防げるが、これには第4部で示されるように追加のコストが伴う。ここではlog shippingを考えていく。

ラグが多少発生するのは仕方ないにしても、少なくともcommitされたトランザクションの情報を受け取ったとき、そのトランザクションに関するログエントリは漏れなく&serialization順に受け取っている必要がある。

一部のcommitされるトランザクションの情報が失われるのを恐れず、かつlog shippingに多少ラグがあってもいいのなら、redoログエントリだけ、つまり勝者トランザクションに関するログエントリだけを送るとパフォーマンスが大きく改善する。

ミッションクリティカルな状況では、第二センターの方をホットスタンバイにする（バックアップに送られてきたアーカイブログを常に適用し続け、リアルタイムにシャドウデータベースを維持する）方法が必要になりうる。