以 steal/no-steal × force/no-force 的矩陣定位各種復原策略，包括 shadow paging。
陳述 ARIES 的三個原則：WAL、redo 時重複歷史、undo 時寫 CLR。
描述 ARIES 的資料結構（ATT、DPT、pageLSN、prevLSN、undoNextLSN）與 fuzzy checkpoint 的內容。
一步步執行 Analysis、Redo、Undo 三個階段，並說明為何復原過程中再次當機仍然正確。
解釋 PostgreSQL 為何沒有 undo 階段、啟動時如何用 與 WAL 重播到一致狀態，以及 PITR 與 timeline。
失效的類型與復原的目標
交易失效：邏輯錯誤、約束違反、死結受害者——只需回滾單筆交易（undo）。
系統當機：程序崩潰、OS panic、斷電——揮發性記憶體（buffer pool、鎖表）全部遺失，磁碟完好。本章主題。
媒體失效：磁碟損毀——需要備份 + 日誌封存（PITR）或複本（第 14 章）。
復原演算法的目標是在系統當機後恢復 原子性（未 commit 的交易效果消失）與持久性（已 commit 的交易效果存在）。
設計空間：steal/no-steal 與 force/no-force
P3.2cm|P4.9cmP4.9cm & No-Steal（未 commit 的髒頁不可寫回） & Steal（可寫回）
Force（commit 時髒頁必須寫回） & 不需 undo、不需 redo。最簡單，但 commit 要等隨機寫入；buffer pool 必須容納交易全部的髒頁。 & 需 undo、不需 redo。
No-Force（commit 不寫回） & 不需 undo、需 redo。 & 需 undo 與 redo。效能最佳（ARIES、多數商用系統）。
Shadow paging（System R 早期、LMDB、SQLite 的 rollback-journal 模式精神相近）是 no-steal/force 的代表： 修改時複製頁面（copy-on-write）到新位置，commit 時原子地切換頁表根指標。優點是不需要日誌與復原程序； 缺點是每次 commit 都要寫出所有頁並 fsync、資料碎片化、頁表切換難以支援高並行。現代系統幾乎都選擇 steal/no-force + WAL。
ARIES 的三個原則
Mohan 等人（1992）的 ARIES（Algorithms for Recovery and Isolation Exploiting Semantics）是幾乎所有現代資料庫復原機制的藍本：
Write-Ahead Logging：第 8 章的兩條規則。
Repeating history during redo：當機後，先把資料庫完整重建到當機那一刻的狀態（包含未 commit 交易的修改），然後才 undo 輸家。 這讓 redo 邏輯極其簡單，也讓細粒度鎖與複雜的頁面結構（B+Tree 分裂）得以正確復原。
Logging changes during undo：undo 的每一步也寫日誌（Compensation Log Record, CLR），所以 undo 進行到一半再當機，不會重複 undo。
資料結構
lP10.6cm 結構 & 內容
日誌記錄 & 、（UPDATE / COMMIT / ABORT / END / CLR / CHECKPOINT）、、（同交易前一筆）、 、位移、before image、after image；CLR 另有 ：下一個要 undo 的記錄。
& 每個資料頁標頭：最後修改它的 LSN。
Transaction Table（ATT） & 每筆活動交易：、狀態（running / committing / aborting）、（最新記錄）。
Dirty Page Table（DPT） & 每個髒頁：、recLSN——第一次把它弄髒的 LSN；該頁磁碟版本保證含 recLSN 之前的所有修改。
Checkpoint & + （含當時的 ATT 與 DPT 快照）；master record 記下最新 BEGIN_CHECKPOINT 的 LSN。 Fuzzy：checkpoint 期間交易照常進行、不寫出髒頁。
三個階段
Analysis
從 master record 指向的最後一次 checkpoint 開始向前掃到日誌尾端，重建當機瞬間的 ATT 與 DPT：
以 checkpoint 中的 ATT、DPT 為起點。
遇到某交易的記錄：加入／更新 ATT 的 ；遇到 ：從 ATT 移除；遇到 ：狀態改為 committing。
遇到修改頁 \(P\) 的記錄且 \(P\) 不在 DPT：加入， = 該 LSN。
結束時，ATT 中的交易就是輸家（loser）（除了 committing 者，它們只需補寫 END）；DPT 中最小的 是 redo 的起點。
Redo
從 \(\min(\text{recLSN})\) 向前掃描，對每一筆 UPDATE 或 CLR 記錄 \(r\)（修改頁 \(P\)）：若以下任一成立則跳過，否則重做並把 pageLSN 設為 \(r\).LSN：
\(P\) 不在 DPT（當機前已寫回）；
\(P\) 在 DPT 但 \(r\).LSN \(<\) recLSN（這個修改已在磁碟上）；
讀入 \(P\) 後發現 pageLSN \(\ge r\).LSN（此修改已存在；這一步需要實際讀頁）。
注意 redo 不區分贏家輸家——這就是「重複歷史」。Redo 結束後，資料庫等同當機瞬間的記憶體狀態。對 committing 的交易寫 END 並移出 ATT。
Undo
把所有輸家的 放進 ToUndo 集合，反覆取出最大的 LSN（確保所有交易的 undo 以 LSN 遞減的順序交錯進行，只需一趟向後掃描）：
若是 UPDATE：套用 before image，寫一筆 CLR（ = 該記錄的 ），把 加入 ToUndo。
若是 CLR：不 undo 它（它描述的 undo 已經生效），把它的 加入 ToUndo。
若 ／ 為 null：該交易完全回復，寫 END。
完整範例
| LSN | 記錄 | prevLSN | 說明 |
|---|---|---|---|
| 10 | BEGIN_CHECKPOINT | ||
| 20 | END_CHECKPOINT | ATT = {}，DPT = {} | |
| 30 | \(T_1\) UPDATE P1 | – | DPT: P1 recLSN 30 |
| 40 | \(T_2\) UPDATE P2 | – | DPT: P2 recLSN 40 |
| 50 | \(T_1\) UPDATE P3 | 30 | DPT: P3 recLSN 50 |
| 60 | \(T_2\) COMMIT | 40 | \(T_2\) 進入 committing |
| 70 | \(T_1\) UPDATE P1 | 50 | P1 已在 DPT，recLSN 不變 |
| 80 | \(T_2\) END | 60 | \(T_2\) 移出 ATT |
| （當機；假設 P2 已被寫回磁碟，P1、P3 未寫回） | |||
| Analysis（從 LSN 10）：ATT = {\(T_1\): lastLSN 70}；DPT = {P1: 30, P2: 40, P3: 50}。輸家 = \(T_1\)。 | |||
| Redo（從 LSN 30）：30 重做 P1；40 讀 P2 發現 pageLSN = 40 跳過；50 重做 P3；70 重做 P1。 | |||
| Undo（ToUndo = {70}）：undo 70 寫 CLR 90（undoNext 50）；undo 50 寫 CLR 100（undoNext 30）；undo 30 寫 CLR 110（undoNext null）；寫 \(T_1\) END 120。 | |||
若在寫完 CLR 100 之後再度當機：下一次 Analysis 會看到 \(T_1\) 仍在 ATT（lastLSN 100）；Redo 會重做 CLR 90、100（它們也是修改頁的記錄）； Undo 取出 100，它是 CLR，直接跳到 = 30，只剩 LSN 30 需要 undo。每一步 undo 最多做一次——冪等。 這就是 CLR 的意義：ARIES 的復原工作量有上界，不會因反覆當機而無限增長。
ARIES 的進階主題
邏輯 undo 與 nested top action：B+Tree 分裂屬於「結構修改」，即使發起的交易最後中止，分裂本身也不該回復（其他交易可能已經用到新頁）。 ARIES 以 nested top action（寫一筆 dummy CLR 跳過整段）讓結構修改在邏輯上立即 commit；索引項目的刪除則以邏輯 undo（重新搜尋鍵再刪除）進行，因為鍵可能已搬到別頁。
部分回滾：savepoint 的實作就是 undo 到某個 LSN 為止。
並行復原：redo 可依頁或依 LSN 範圍切成多個執行緒；PostgreSQL 的 redo 到 18 為止仍是單一 startup process（但可用 預讀頁面）。
媒體復原：還原最近一次完整備份後，從備份開始的 LSN 重播封存的日誌——本質上就是 redo 階段的延伸，這就是 PITR。
PostgreSQL 的復原
PostgreSQL 採 steal/no-force 與 WAL，Analysis 與 Redo 的精神與 ARIES 相同，但沒有 Undo 階段： MVCC 下，中止或未完成交易所寫的 tuple 版本只是不可見（其 XID 在 clog 中不是 committed），不需要物理回復，之後由 VACUUM 清理。 因此 WAL 只含 redo 資訊，也不需要 CLR。代價是中止交易留下的垃圾要靠 VACUUM 處理，以及長交易回滾雖然瞬間完成、但不會釋放空間。
啟動流程（）：
讀 ：若狀態為 則是乾淨關機，不需復原；否則進入 crash recovery（日誌出現 、）。
取最後一次 checkpoint 記錄的 redo point，從該處開始順序重播 WAL（）：每筆記錄依 呼叫對應資源管理器的 ； 有 full-page image 的 block 直接覆蓋；否則比較 pageLSN，只套用更新的記錄（與 ARIES 的條件 3 相同）。
遇到不完整或 CRC 錯誤的記錄視為日誌尾端（）。此時資料庫狀態等同當機瞬間，未 commit 的交易「自動」消失。
建立一個新 checkpoint（end-of-recovery checkpoint，PostgreSQL 15 起較小的 end-of-recovery record），開放連線。
Archive recovery 與 PITR：若存在 ／，startup process 透過 從封存取回段檔持續重播， 直到 指定的位置，然後進入新的 timeline（timeline ID 加一， 檔記錄分支點）， 確保新舊歷史的 WAL 不會混淆。Hot standby（第 14 章）就是永不結束的 archive recovery，並允許唯讀查詢。
會偽造一個乾淨的 checkpoint 讓損壞的叢集啟動——但它丟棄所有未重播的 WAL，資料庫幾乎必然處於不一致狀態（索引與 heap 不符、clog 遺失）。 只在已經有備份、且目的是搶救部分資料並立即 重建時使用。同理， 之後的當機沒有復原可言。
其他系統
InnoDB：接近教科書 ARIES——先從最後 checkpoint 重播 redo log，再以 undo log 回滾未完成交易（回滾在背景進行，啟動後即可服務）。
SQLite：rollback-journal 模式是「先把舊頁備份到 journal、改主檔、commit 時刪 journal」（undo-only）；WAL 模式是 redo-only（第 8 章）。
RocksDB：重播 WAL 重建 memtable，SSTable 本身不可變，不需 undo（第 12 章）。
v4 可二選一：(a) 完整 ARIES——實作 ATT、DPT、CLR 與三階段，是最扎實的練習（也是 CMU 15-445 舊版 Project 的內容）； (b) PostgreSQL 式 redo-only——配合 v5 的 MVCC，只需 Analysis + Redo。 無論哪一種，都要寫一個「隨機時刻 後重啟並驗證不變量」的壓力測試（例如轉帳總額守恆），並重複數百次。
為什麼 ARIES 要「重複歷史」而不是只 redo 贏家？舉一個只 redo 贏家會出錯的例子（提示：兩筆交易修改同一頁的不同 slot，且頁面曾被寫回）。
沿用本章範例，但假設當機前 P1 已被寫回磁碟（pageLSN = 70）。重新執行三個階段並列出每一步。
Fuzzy checkpoint 的 DPT 快照可能包含「其實已經寫回」的頁，或漏掉「checkpoint 期間新弄髒」的頁。這兩種情況為何都不影響正確性？
若 CLR 不記錄 ，而是把 undo 當作一般 UPDATE 記錄，復原中再當機會發生什麼？
PostgreSQL 沒有 undo 階段，代價轉嫁到哪裡？對比 InnoDB，在「10 億列的交易在 99% 時中止」的情境下，兩者的行為差異為何？
（動手）啟動 PostgreSQL 執行一批交易， postmaster 後重啟，閱讀日誌中的復原訊息；再用 比較前後的 checkpoint 位置與狀態欄位。
C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh, P. Schwarz, , ACM TODS 1992： https://cs.stanford.edu/people/chrismre/cs345/rl/aries.pdf
CMU 15-445 Fall 2025 Lecture #20 Database Recovery（ARIES 的教學版推導）。
R. Ramakrishnan, J. Gehrke, Database Management Systems, 3rd ed., Ch. 18 Crash Recovery（最清楚的 ARIES 教科書章節）。
PostgreSQL 文件 Ch. 25 Backup and Restore（含 Continuous Archiving and Point-in-Time Recovery）： https://www.postgresql.org/docs/current/continuous-archiving.html；、 說明頁。
Hironobu Suzuki, The Internals of PostgreSQL, Ch. 9（§9.8 復原流程）、Ch. 10 Base Backup & PITR：https://www.interdb.jp/pg/pgsql10.html
PostgreSQL 原始碼 、（）、。
J. Hellerstein, M. Stonebraker, J. Hamilton, , 2007, §6 Transactions: Concurrency Control and Recovery。
A. Petrov, Database Internals, Ch. 5 Transaction Processing and Recovery。