セマンティクスを活用した回復と分離のアルゴリズム

コンピュータサイエンスにおいて、セマンティクスを活用した回復および分離アルゴリズム（ARIES）は、強制のないデータベース窃盗アプローチで動作するように設計された回復アルゴリズムであり、 IBM Db2、Microsoft SQL Server、その他多くのデータベースシステムで使用されています。^[1] IBMフェローのC. Mohan博士は、ARIESアルゴリズムファミリーの主な発明者です。^[2]

ARIES の背後には 3 つの主要な原則があります。

• 先行書き込みログ: オブジェクトへの変更はまずログに記録され、オブジェクトへの変更がディスクに書き込まれる前に、ログが安定したストレージに書き込まれる必要があります。
• やり直し中に履歴を繰り返す: クラッシュ後の再起動時に、ARIES はクラッシュ前のデータベースのアクションを再度トレースし、システムをクラッシュ前の正確な状態に戻します。次に、クラッシュ時にまだアクティブだったトランザクションを元に戻します。
• 元に戻す操作中の変更のログ記録: トランザクションを元に戻す操作中にデータベースに加えられた変更はログに記録され、再起動を繰り返しても同様のアクションが繰り返されないようにします。

ARIES アルゴリズムは、すべてのデータベース操作を昇順のシーケンス番号でログに記録することに依存しています。通常、結果のログファイルは、クラッシュやハードウェア障害に耐えられると想定されるストレージ メディアである、いわゆる「安定したストレージ」に保存されます。

ログに必要な情報を収集するには、ダーティ ページ テーブル (DPT) とトランザクション テーブル (TT) という 2 つのデータ構造を維持する必要があります。

ダーティ ページ テーブルには、変更されてまだディスクに書き込まれていないすべてのページと、そのページがダーティになった最初のシーケンス番号が記録されます。トランザクション テーブルには、現在実行中のすべてのトランザクションと、それらが作成した最後のログ エントリのシーケンス番号が含まれます。

ログ レコードは、(シーケンス番号、トランザクション ID、ページ ID、やり直し、元に戻す、前のシーケンス番号) の形式で作成されます。やり直しフィールドと元に戻すフィールドには、このログ レコードに保存された変更とその元に戻す方法に関する情報が保持されます。前のシーケンス番号は、このトランザクションに対して作成された前のログ レコードへの参照です。トランザクションが中止された場合、前のシーケンス番号を使用してログ ファイルを逆順に走査し、特定のトランザクション内で実行されたすべてのアクションを元に戻すことが可能です。

すべてのトランザクションは、指定されたトランザクション ID の最初の「更新」タイプのエントリで暗黙的に開始され、トランザクションの「ログの終了」(EOL) エントリでコミットされます。

回復中、または中止されたトランザクションのアクションを元に戻すときに、アクションがすでに元に戻されたことを記録するために、特別な種類のログ レコードである補正ログ レコード (CLR) が書き込まれます。CLR の形式は (シーケンス番号、トランザクション ID、ページ ID、やり直し、前のシーケンス番号、次の元に戻すシーケンス番号) です。やり直しフィールドには、元に戻されたアクションの元に戻すフィールドの適用が含まれ、CLR が元に戻されることはないため、元に戻すフィールドは省略されます。

リカバリは 3 つのフェーズで行われます。最初のフェーズである分析では、ログファイルから必要な情報をすべて計算します。やり直しフェーズでは、その時点で実行されていたコミットされていないトランザクションのすべての変更を含め、データベースをクラッシュ時の正確な状態に復元します。その後、元に戻すフェーズでコミットされていない変更をすべて元に戻し、データベースを一貫した状態にします。

分析フェーズでは、DPT と TT をクラッシュ時の状態に復元します。

ログファイル全体 (先頭または最後のチェックポイントから) を実行し、Begin Transaction エントリに遭遇したすべてのトランザクションを TT に追加します。End Log エントリが見つかると、対応するトランザクションが削除されます。各トランザクションの最後のシーケンス番号も保持されます。

同じ実行中に、変更されていてまだ DPT にないページが見つかるたびに、新しいエントリを追加してダーティ ページ テーブルを埋めます。ただし、実際のデータベース ファイルでページがストレージに書き戻されたかどうかはチェックされないため、クラッシュ時のすべてのダーティ ページのスーパーセットのみが計算されます。

DPT から、ダーティ ページの最小シーケンス番号を計算できます。そこから、アクションがまだ保存されていない場合は、クラッシュするまでアクションをやり直す必要があります。

ログ ファイルを実行して、各エントリについて、エントリの変更されたページ P が DPT に存在するかどうかを確認します。存在しない場合、データはディスク上に保持されるため、このエントリの再実行について心配する必要はありません。ページ P が DPT テーブルに存在する場合は、DPT のシーケンス番号がログ レコードのシーケンス番号より小さいかどうか (つまり、ログの変更が保持された最後のバージョンより新しいかどうか) を確認します。そうでない場合は、変更がすでに存在するため、エントリを再実行しません。新しい場合は、データベース ストレージからページを取得し、ページに格納されているシーケンス番号をログ レコードのシーケンス番号と比較します。前者が後者より小さい場合は、ページをディスクに書き込む必要があります。このチェックが必要なのは、回復された DPT が、実際に変更を再適用する必要があるページの保守的なスーパーセットにすぎないためです。最後に、上記のすべてのチェックが完了して失敗した場合、やり直しアクションを再適用し、新しいシーケンス番号をページに保存します。やり直しは同じページに 2 回適用されないため、やり直しフェーズ中のクラッシュからの回復にも重要です。

やり直しフェーズの後、データベースはクラッシュ時の正確な状態を反映します。ただし、データベースを一貫した状態に復元するには、コミットされていないトランザクションの変更を元に戻す必要があります。

そのために、レコード内の前のシーケンス番号フィールドを使用して、TT 内の各トランザクションのログを逆順に実行します (もちろん、これらの実行は 1 つにまとめることができます)。各レコードに対して、変更を元に戻し (元に戻すフィールドの情報を使用)、補正ログ レコードをログ ファイルに書き込みます。開始トランザクション レコードに遭遇した場合は、そのトランザクションの終了ログ レコードを書き込みます。

補正ログ レコードにより、回復フェーズ中にクラッシュが発生した場合でも回復が可能になります。回復フェーズにかなり時間がかかる可能性があるため、これはそれほど珍しいことではありません。CLR は分析フェーズ中に読み取られ、やり直しフェーズ中に再実行されます。

分析フェーズ中にログファイル全体を再スキャンするのを避けるために、DPT と TT を定期的にログファイルに保存してチェックポイントを形成することをお勧めします。ファイル全体を実行する代わりに、チェックポイントが見つかるまで逆方向に実行するだけで済みます。その時点から、ログファイルを再度前方に読み取ることで、クラッシュ時の DPT と TT を復元できます。その後、通常どおりにやり直しと元に戻すことができます。

チェックポイントを作成する単純な方法では、チェックポイントの作成中に DPT と TT が変更されないように、データベース全体をロックします。ファジー ログは、2 つのログ レコードを書き込むことでこれを回避します。1 つは「Fuzzy Log Starts Here」レコードで、もう 1 つはチェックポイント データの準備後の実際のチェックポイントです。2 つのレコードの間には、他のログ レコードを作成できます。リカバリ中に、有効なチェックポイントを取得するには、両方のレコードを見つける必要があります。

• ARIES ファミリーのロックおよびリカバリアルゴリズムの影響 - C. Mohan、2012-08-19 にオリジナルからアーカイブ、2013-09-18 に取得