ARIES リカバリアルゴリズム

ARIES が解く問題

クラッシュ直後のディスクは、ページごとに「いつまでの変更が反映されているか」がバラバラです。あるページにはコミット前の更新まで書かれ、別のページにはコミット済みの更新がまだ書かれていない、という状態が普通に起こります。原因は実用 DBMS が No-Force / Steal を採るからです。No-Force はコミット時にデータページの書き戻しを強制しない（だから redo が要る）、Steal は未コミットの汚れたページもバッファ都合で書き戻してよい（だから undo が要る）。

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）は、この混沌としたディスクを WAL（先行書き込みログ） だけを手がかりに、決定的かつ冪等に修復するアルゴリズムです。設計原理は3本柱にまとめられます。

LSN とページの自己記述

各ログレコードには単調増加する LSN（Log Sequence Number）が振られます。LSN は実質的にログ上の書き込み位置（オフセット）であり、順序と位置を同時に表します。ARIES の正しさは、いくつかの LSN を要所に埋め込むことで成立しています。

• pageLSN: 各データページのヘッダに記録される「そのページに最後に適用された変更の LSN」。これがあるおかげで redo は冪等になります。あるログレコード（LSN = L）を redo しようとするとき、対象ページの pageLSN >= L なら「その変更はすでに反映済み」と判断してスキップできる。だからリカバリが途中でまた落ちて最初からやり直しても、同じ正しい結果に収束します。
• prevLSN: 同一トランザクションが直前に書いたログの LSN。各トランザクションのログがリンクリストとして逆順にたどれ、undo はこれを伝って自分の変更だけを巻き戻します。
• recLSN: あるページが「いつ汚れ始めたか」の最古の LSN（後述の Dirty Page Table が持つ）。redo の開始点を決めます。

Dirty Page Table と Transaction Table

リカバリの再構築起点を与えるのが、平常時にメモリ上で維持される2つの表です。

• Dirty Page Table（DPT）: バッファ上で変更され、まだディスクへ書き戻していないページの集合。各エントリは (ページID, recLSN) を持つ。recLSN は「そのページを最初に汚した変更の LSN」で、redo の開始点を決める鍵になります。
• Transaction Table（TT）: 実行中トランザクションの集合。各エントリは (トランザクションID, 状態, lastLSN) を持ち、lastLSN はそのトランザクションが最後に書いたログの LSN。undo の出発点になります。

これらは fuzzy checkpoint（ファジーチェックポイント）の際にログへ書き出されます。ファジーとは「全ダーティページの書き戻し完了を待たずにチェックポイントを進める」方式で、平常時の I/O を止めません。チェックポイントは DPT と TT のスナップショットをログに記録するだけで、ページ書き戻しはバックグラウンドに任せます（バッファプールとページ置換 のバックグラウンド書き出しを参照）。

3フェーズの全体像

リカバリは最後に完了したチェックポイントを足がかりに、Analysis → Redo → Undo の順で進みます。

Analysis フェーズ

最後のチェックポイントが記録した DPT と TT を初期値として読み込み、そこからログを前方へスキャンします。更新ログを見たら、そのページが DPT になければ追加し、トランザクションを TT に反映する。コミット／アボートの完了ログを見たら、そのトランザクションを TT から除く。スキャンを終えた時点で、TT に残っているのが loser（クラッシュ時に未コミットだったトランザクション＝Undo 対象）、DPT に残っているのが「ディスク未着地かもしれないページ」です。Redo の開始点 redoLSN は、DPT 中の recLSN の最小値になります。それより前のページ変更はすでに全てディスクに着地しているからです。

Redo フェーズ

redoLSN からログを前方へスキャンし、再適用すべきか1件ずつ判定します。ここが Repeating History の核心で、loser の変更も含めて再適用します。判定は次の通りです。

各更新ログレコード（LSN = L, 対象ページ = P）について:
  if P が DPT に無い:           skip   # そのページは既にディスクに着地済み
  elif L < DPT[P].recLSN:       skip   # この変更より後から汚れ始めた → 着地済み
  else:
      P をバッファに読み込む
      if P.pageLSN >= L:        skip   # 既に反映済み（redo の冪等判定）
      else:                     L を再適用し P.pageLSN = L に更新

3段階の枝刈り（DPT 不在・recLSN 未満・pageLSN 以上）で、ディスク読み込みと再適用を必要最小限に抑えます。Redo を終えると、ディスクの論理状態はクラッシュが起きなかったかのように、直前の全履歴が反映された状態になります。

Undo フェーズと CLR

Redo 完了後、TT に残った loser たちの変更を後方へ取り消します。各 loser の lastLSN を起点に、prevLSN のリンクをたどって自分の更新ログだけを逆順に巻き戻します。複数の loser がある場合は、全 loser の未処理 LSN のうち最大のものを毎回選んで進めると、効率よく一括処理できます。

ここで決定的に重要なのが CLR（Compensation Log Record、補償ログレコード）です。ある更新を取り消すたびに、「取り消したという事実」を CLR としてログに追記します。CLR は redo 可能（redo-only）で、undoNextLSN という特別なフィールドを持ちます。これは「次に取り消すべき LSN」、すなわち取り消した更新の prevLSN を指します。

ログ:  ... U1(prev=-)  U2(prev=U1)  U3(prev=U2)  [クラッシュ]
Undo:  U3 を取り消し → CLR3(undoNext=U2 の LSN) を記録
       U2 を取り消し → CLR2(undoNext=U1 の LSN) を記録
       Undo 中に再クラッシュ
再Redo: CLR3, CLR2 を再適用（取り消し効果が復元される）
再Undo: 最後の CLR2 の undoNext=U1 から再開 → U1 だけ取り消す（U2,U3 は二度やらない）

並行制御との接点

ARIES の正しさは、適切なロックの上に成り立ちます。Undo が他トランザクションを巻き込まずに自分の変更だけを巻き戻せるのは、更新したレコードをコミットまで排他ロックで保持する（Strict 2PL 相当の）前提があるからです。これがあるからこそ、redo は physiological に、undo は論理的に整合します。詳しくは ロックと MVCC を参照してください。

なお ARIES はインデックス（B+Tree）の高並行な構造変更まで扱う ARIES/IM や ARIES/KVL などの拡張系を持ち、ページ単位の物理 undo と、操作単位の論理 undo を組み合わせて、構造が変わっても整合する復旧を実現します。

まとめ

ARIES は「WAL・Repeating History・Undo 中もログを取る」という3原理から、Analysis・Redo・Undo の3フェーズを導きます。Analysis が DPT・TT を再構築して範囲を決め、Redo が pageLSN を見て履歴を冪等に完全再現し、Undo が CLR と undoNextLSN を使って未コミット分だけを冪等に取り消す。これにより No-Force / Steal の自由を保ちながら、何度クラッシュしても同じ正しい状態に収束する復旧が成立します。

物理層で永続性を支える基盤は WAL の仕組み、ダーティページとチェックポイントの実体は バッファプールとページ置換、復旧が守ろうとする原子性・永続性の定義は トランザクションとは何か、任意時点復元まで含めた運用面は バックアップとリカバリ を合わせて読むと、リカバリの全体像が立体的に見えてきます。