AI解説

情報源: ACM TODS 1992 論文本文（自己アーカイブ版 PDF、全69頁）を精読して記述。本文に書かれていない事項は書いていない。

一言で

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）は、細粒度（レコード単位）のロックと部分ロールバックをサポートしながら、Write-Ahead Logging（WAL）で障害から復旧する手法。「履歴を繰り返す（repeating history）」というパラダイムを導入し、再起動時にまずロスト・トランザクション（loser）を含む全ての欠落更新を再現してから、ロールバックを行う。チェックポイントはトランザクション処理を止めずに非同期に取れるfuzzy checkpointであり、IBM の DB2、IMS、Workstation Data Save Facility/VM、Starburst、QuickSilver、University of Wisconsin の EXODUS や Gamma データベースマシンなど、さまざまな度合いで実装されてきた。

背景・問題

トランザクション概念は ACID（原子性・一貫性・独立性・永続性）特性をカプセル化する枠組みとして長く使われてきたが、論文が書かれた時点でも、細粒度のロックと部分ロールバックを効率よく支える回復手法は確立していなかった。論文はまず、System R のようなシャドウページ方式に基づくパラダイムが、WAL の文脈ではそのままでは通用しないことを示す必要があると位置づけている。ARIES はこの問題を、ページ単位のログシーケンス番号（LSN）による状態の相関付けと、ロールバック中に書かれたログレコードを前方処理中のログレコードへ適切に連鎖させる仕組みで解く。

提案手法

基本構造 — ページ LSN による状態の相関

ARIES は各ページにログシーケンス番号（LSN）を持たせ、そのページの状態がログ上のどこまでの更新を反映しているかを対応付ける。トランザクションの全ての更新（ロールバック中に行われるものも含む）がログされ、前方処理中に書かれたログレコードとロールバック中に書かれたログレコードを適切に連鎖させることで、再起動中の繰り返し障害やネストしたロールバックに直面しても、ロールバックにかかるログ量が有界に収まることを保証する。

Transaction Table と Dirty_Pages Table

再起動時の復旧で使う2つの主要な表がある。

• Transaction Table：アクティブなトランザクションの状態を追跡する。各エントリは TransID（トランザクションID）、State（コミット状態。準備済み=’P’／未準備=’U’）、LastLSN（そのトランザクションが書いた最新のログレコードの LSN）、UndoNxtLSN（ロールバック時に次に処理すべきレコードの LSN。直前のログレコードが通常の undo 可能レコードなら LastLSN と同じ値、CLR ならその CLR が持つ UndoNxtLSN の値）を持つ。
• Dirty_Pages Table：バッファ中のダーティページの情報を表す。各エントリは PageID と RecLSN（recovery LSN）を持つ。通常処理中、非ダーティなページを更新目的で初めて fix したとき、バッファマネージャはその時点の「ログ末尾の LSN」（次に書かれるログレコードの LSN）を RecLSN として記録する。これは、そのページに対して不揮発性ストレージにまだ反映されていない可能性のある更新が、ログ上のどの地点から存在しうるかを示す。ページが不揮発性ストレージへ書き戻されると、対応するエントリは表から削除される。

fuzzy checkpoint

チェックポイントは、更新を含むトランザクション処理が進行中でも非同期に取れる。begin_chkpt レコードを書き、続けて通常のトランザクションテーブルと BP dirty-pages テーブルの内容（およびオープン中のファイルマッピング情報）を含む end_chkpt レコードを構築してログへ書く。end_chkpt レコードが安定ストレージへ到達すると、begin_chkpt レコードの LSN がマスターレコードへ記録される。ARIES はチェックポイント中にダーティページを1枚も不揮発性ストレージへ強制的に書き戻すことを要求しない（バッファマネージャがバックグラウンドで継続的にダーティページを書き出している、という前提に立つ）。ダーティページ表の情報を latch を取りながら少しずつ集める場合でも、チェックポイント開始以降に書かれたログレコードも合わせて考慮することで正しさが保たれる。

再起動処理 — Analysis・Redo・Undo の3パス

再起動時の RESTART ルーチンは、マスターレコードが指す最後の完全なチェックポイントの begin_chkpt の LSN を入力として、Analysis・Redo・Undo の3パスをこの順で呼び出す。

Analysis パスは、チェックポイントのレコードからトランザクションテーブルとダーティページ表を初期化し、begin_chkpt 以降のログレコードを解析してこれらを最新状態へ更新する。ダーティページ表に未登録のページを指すログレコードに出会うと、そのレコードの LSN を RecLSN として新規登録する。Analysis パスの終了時点における ダーティページ表の RecLSN の最小値が RedoLSN、すなわち Redo パスの開始位置になる。ARIES の実装（OS/2 Extended Edition Database Manager）では Analysis パスを省略する構成もあり、その場合 RedoLSN は min(min(end_chkpt のダーティページ表のRecLSN), LSN(begin_chkpt レコード)) として計算される。

Redo パスは RedoLSN からログをスキャンし、redo 可能なログレコードでそのページがダーティページ表にあり LSN が RecLSN 以上のものについて、実際にページを読み、ページの page_LSN がログレコードの LSN より小さければ更新を再適用する。ここで重要なのは、loser トランザクションによる更新も含め、コミット状態にかかわらず全ての欠落更新を無条件に redo するという「履歴を繰り返す」原則である。これにより、Undo パスは各トランザクションが loser かどうかだけを気にすればよく、redo 側は loser／non-loser の区別を必要としない（DB2 のように in-doubt トランザクションのロックをログレコードから推測して再獲得する方式とは対照的）。

Undo パスは、State='U' の loser トランザクションの中で UndoNxtLSN が最大のものを繰り返し選び、そのログレコードを1回のログスキャンで逆時系列に処理していく。undo 可能なレコードには Compensation Log Record（CLR） を書き、ページと Transaction Table の両方にその CLR の LSN を記録する。redo パスで既に履歴が繰り返された後なので、undo パスではページの LSN とログレコードの LSN を比較する必要がない（undo は無条件に行われる）。

Fig. 5. ARIES’ technique for avoiding compensating compensations and duplicate compensations.

CLR チェーンによる有界なロールバック

CLR はそれ自体が undo されることのない redo-only なレコードで、UndoNxtLSN フィールドを通じて「次に undo すべき、まだ補償されていない元のログレコード」を指す。これにより、あるトランザクションのロールバックが再起動中の障害で何度中断されても、既に CLR が書かれた更新を再び補償し直すことがなく（補償の補償を避ける）、ロールバックにかかるログ量に上限を持たせられる。

数式・アルゴリズム

論文は Analysis・Redo・Undo の各パスを擬似コードで与えている。Redo パスの核となる条件は次の通りである。

IF LogRec.Type = ('update' | 'compensation') & LogRec is redoable
   & LogRec.PageID IN Dirty_Pages
   & LogRec.LSN >= Dirty_Pages[LogRec.PageID].RecLSN
THEN
   Page := fix&latch(LogRec.PageID, 'X')
   IF Page.LSN < LogRec.LSN THEN
      Redo_Update(Page, LogRec)     -- 実際に redo するのはページLSNがまだ古い場合だけ
      Page.LSN := LogRec.LSN

Undo パスは、loser トランザクションの中から UndoNxtLSN が最大のものを選び続けることで、複数トランザクションの undo を単一のログスキャンで逆時系列に処理する。

WHILE EXISTS (Trans with State='U' in Trans_Table) DO
   UndoLSN := maximum(UndoNxtLSN) from Trans_Table entries with State='U'
   LogRec := Log_Read(UndoLSN)
   -- undo可能なら Undo_Update を行い、compensation ログレコードを書く
   -- UndoNxtLSN が 0 になったトランザクションは end レコードを書いて完了

関連研究との関係（メモ）

• SiloR（cite key zheng2014silor）：SiloR は関連研究の節で ARIES を「データベースのログとチェックポイントの黄金律」と位置づけ、ARIES が undo ログと redo ログの両方を組み合わせて不整合なチェックポイントから復旧する必要があるのは、ARIES がコミット前のデータをチェックポイント相当の状態へフラッシュしうるためだと説明している。SiloR は楽観的並行性制御（OCC）を使うためコミット前のデータがチェックポイントに現れることがなく、redo ログだけで足りるとしている。両者の対比は、チェックポイントの一貫性保証の強さと、undo ログを要するかどうかが表裏一体であることを示している。
• 分野横断的な位置づけは アプリケーションレベルのチェックポイント の §3.4 を参照。

Q&A

（自分がAIに実際に質問したことだけをQ/A形式で残す。まだなし。）

自分のコメント

（ここは自分で都度書く欄。）