跳至主要內容
論文精煉 · Transactions

ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging

ARIES 以「重演歷史」再搭配 redo-only 的補償日誌,讓細粒度鎖定下的當機復原同時做到正確與快速。

作者C. Mohan、Don Haderle、Bruce Lindsay、Hamid Pirahesh 等(IBM Almaden Research Center 與 IBM Santa Teresa Laboratory) 發表於ACM Transactions on Database Systems 17(1),1992 年 3 月,第 94-162 頁 年份1992
閱讀原始論文 PDF 所有論文

一口氣講完 — 整篇論文的濃縮

ARIES 是一套以 write-ahead logging 為基礎的復原方法,目標是在記錄層級鎖定、操作式日誌(operation logging)與變動長度記錄並存的環境下,仍能保證當機復原的正確性。它最關鍵、也最違反直覺的一步是:重啟時先重演歷史(repeating history),把所有尚未反映在頁面上的已記錄更新全部 redo,連未提交交易的更新也一併重做,之後才回滾 loser 交易。重演歷史讓每一頁上的 page LSN 重新成為該頁狀態的忠實描述,這正是邏輯 undo 與「只記錄增減量而非前後影像」得以安全成立的前提。回滾過程本身也要寫日誌,寫成 redo-only 的補償日誌記錄(CLR),其 UndoNxtLSN 指標會直接跳過已經 undo 過的記錄,因此無論巢狀回滾或重啟途中再次當機幾次,一筆交易的 undo 成本都有上界。重啟流程就是對日誌做三趟掃描:analysis、redo、undo,並由一種不強制寫出任何髒頁、只記下 dirty pages 表與交易表的 fuzzy checkpoint 來驅動。

在這篇論文之前 — 它所降落的世界

到 1980 年代末,兩條主流的復原技術路線都各有破口。System R 與 SQL/DS 走 shadow page:復原從整個資料庫的 action-consistent 影子版本開始,因此不需要 page LSN、不寫補償記錄,索引與空間管理的變更也完全不記日誌,代價是 checkpoint 極其昂貴、資料實體叢集性被破壞,且相關物件必須同步、鎖步地一起復原。DB2、IMS、Encompass、NonStop SQL 等以 WAL 為基礎的產品雖然採用了 WAL,卻沿用了 System R 的思維,其中最關鍵的就是 selective redo:重啟時只重做已提交與 in-doubt 交易的更新。selective redo 在那些系統中之所以能運作,靠的是頁層級鎖定或位元組範圍的實體式日誌;而它帶來的日誌行為相當病態:DB2 與 Encompass 會去 undo 自己寫的補償記錄,於是重啟過程中反覆當機時,日誌量在最壞情況下呈指數成長。與此同時,客戶要的是記錄層級鎖定、能處理 hot spot 的 increment/decrement 鎖模式、不必離線重組的變動長度記錄,以及快到足以支撐 hot standby 的重啟速度——當時沒有任何一套方法能同時滿足這些需求。

問題 — 當時真正壞掉的地方

  • selective redo 在細粒度鎖定下並不安全:若某個非 loser 交易對某頁的更新在 loser 交易的更新之後被 redo,page LSN 會被推高到超過 loser 的 LSN,undo 階段便再也無法判斷 loser 的更新究竟有沒有落在該頁上。
  • 把兩趟順序對調也救不了:如同 System R 先 undo 再 redo,undo 時寫出的 CLR 會把 page LSN 推高到某個後來已提交更新的 LSN 之上,導致該已提交更新永遠不會被 redo,直接違反持久性。
  • 支撐 increment/decrement 這類語意豐富鎖模式所需的操作式日誌完全不容許模糊:重做一個頁面上已存在的操作,或撤銷一個頁面上根本不存在的操作,都會悄悄破壞資料;這和值式日誌(value logging)不同,後者這類重複動作是幂等的。
  • 既有 WAL 系統記錄回滾動作的方式無法乾淨收斂:DB2、Encompass 與 AS/400 會 undo CLR,於是替補償記錄再寫補償記錄;IMS 則會把同一筆非 CLR 記錄 undo 好幾次。在巢狀回滾或重啟途中反覆當機時,日誌量因此沒有上界。
  • 要有彈性地管理變動長度記錄的儲存空間,就必須能在頁內搬移記錄做垃圾回收,而且搬移既不加鎖也不寫日誌;這直接排除了 IMS、VAX DBMS 與 VAX Rdb/VMS 採用的位元組範圍鎖定與實體式日誌。
  • no-steal 緩衝策略並不是脫身之計:在記錄鎖定下,一個熱門頁面可能永遠含有某筆未提交的更新,因而永遠寫不回磁碟,系統只能在「暫停該頁上的所有活動」與「付出巨大的重啟 redo 成本」之間二選一。

核心概念 — 主要貢獻,以及它們為何成立

先重演歷史,再進行 undo

ARIES 的 redo 階段會把所有在磁碟頁面上缺席的已記錄更新全部重新套用,完全不看寫入這筆更新的交易究竟是提交、中止,或當機當下仍在執行。這等於把資料庫還原到系統失效那一瞬間的精確狀態,包含 loser 交易的未提交更新,也包含當機時正在進行中的回滾所寫下的補償記錄。這一步之所以重要,是因為它讓 page LSN 重新成為頁面狀態的誠實描述,於是 undo 階段根本不必再判斷某筆更新是否存在,只要沿著交易的反向鏈無條件撤銷即可。論文自己的說法是:不重演歷史,page LSN 就不再是頁面當前狀態的真實指標——這正是 selective redo 在記錄鎖定下失效的根本原因。

以單一 page LSN 作為狀態變數

每個資料庫頁面只帶一個欄位 page LSN,內容是描述該頁最近一次更新的那筆日誌記錄的 LSN,而所有日誌記錄的 LSN 都是單調遞增的。這一個值就是日誌與資料實體狀態之間的全部關聯機制,也正是它讓 redo 具備幂等性,同時不對資料本身施加任何限制。對照之下,Encompass 與 NonStop SQL 要求每筆記錄都有唯一鍵,才能偵測出誤套用的 undo;DB2 則在把索引葉頁切成 minipage 時,必須為每個 minipage 額外維護一個 LSN。ARIES 刻意不採用每物件一個 LSN 的做法,因為那會浪費並切碎頁內空間,而且無法妥善處理已刪除物件與變動長度物件。

redo-only 的 CLR 以 UndoNxtLSN 串接

回滾期間執行的每一次更新——不論是一般回滾、回到 savepoint 的部分回滾,還是重啟時的 undo——本身都要寫成補償日誌記錄。ARIES 的 CLR 永遠不會被 undo,因此只需要帶 redo 資訊,並且帶一個 UndoNxtLSN 指標,指向它剛剛補償掉的那筆記錄的 PrevLSN。日後回滾時沿著這個指標走,就會直接跳過所有已經撤銷的內容,於是同一筆非 CLR 記錄不會被 undo 兩次,CLR 也永遠不會被補償。其結果是日誌量有了硬性上界:一筆被回滾的交易所寫的 CLR 數量,恰好等於它在正向處理時寫下的可撤銷記錄數量,中間夾了多少層巢狀回滾或幾次重啟當機都不影響。

頁面導向的 redo 搭配邏輯 undo

ARIES 的 redo 一律是頁面導向的:日誌記錄指名了頁面,就把那一頁取進來處理,資料庫中其他任何東西——目錄描述子、索引走訪——一概不需碰。undo 則相反,允許是邏輯的,甚至可以動到與原始更新不同的頁面。最典型的例子是:某未提交交易在 B-tree 的第 10 頁插入一個鍵,另一個交易分裂該葉頁把這個鍵搬到第 20 頁;第一個交易回滾時會重新走訪索引樹,從第 20 頁刪除該鍵,並寫下描述這次刪除的 CLR。因為 CLR 描述的是「實際發生了什麼」,而不是原始動作的反向操作,所產生的狀態仍然可以用頁面導向的方式 redo——這正是高並行度與頁面間復原獨立性的來源。

fuzzy checkpoint 與 dirty pages 表

ARIES 的 checkpoint 先寫一筆 begin-chkpt 記錄,再寫一筆 end-chkpt 記錄,內含交易表與緩衝池的 dirty pages 表,最後把 begin-chkpt 的 LSN 存進 master record;全程不強制寫出任何髒頁。dirty pages 表的每筆條目由頁面識別碼與 RecLSN 組成,RecLSN 是該乾淨頁面首次被以修改意圖 fix 住那一刻的 end-of-log LSN,用來界定該頁最早可能從哪裡開始有更新尚未落到磁碟。整張表 RecLSN 的最小值就是 RedoLSN,也就是 redo 階段的起點;這張表同時也用來篩選 redo 究竟需要碰哪些頁面。因為 checkpoint 是模糊的,這張表可以分批(例如每次取 latch 檢查 100 筆)蒐集,資訊略微過期也無妨,因為 analysis 階段還會把 begin-chkpt 之後寫下的所有日誌記錄一併納入計算。

以 dummy CLR 實作 nested top action

有些更新——最典型的是檔案擴充,其新增空間會立刻被其他交易使用——即使外層交易中止也必須保留下來,但它本身仍要具備原子性。ARIES 不需要為此另起一個獨立交易(那要付出強制寫日誌的成本,還可能與自己的父交易發生鎖衝突)。做法是:交易先記住自己最後一筆日誌記錄的 LSN,接著用一般的 undo-redo 日誌記錄執行這串動作,完成時寫下一筆 dummy CLR,其 UndoNxtLSN 指回先前記住的那個 LSN。日後外層交易回滾時,沿著 dummy CLR 的指標就直接跳過整段動作;而若在 dummy CLR 寫出之前當機,留下的就是一般可撤銷記錄,會被正常回滾掉。這個技巧成立的前提,就是重演歷史。

運作方式 — 具體的機制

日誌記錄格式與頁面結構

一筆日誌記錄帶有自己的 LSN、Type(update、compensation、prepare、rollback、end、OSfile-return)、TransID、指向同一交易前一筆日誌記錄的 PrevLSN、update 與 compensation 記錄才有的 PageID,以及 redo 與/或 undo 的 Data。交易的第一筆記錄其 PrevLSN 為零,因此不需要額外的 begin transaction 記錄。UndoNxtLSN 只出現在 CLR 中,內容是被補償記錄的 PrevLSN,若已無記錄需要撤銷則為零。Data 可以是邏輯性的:只需記錄變動的欄位,頁內可推導的資訊(如剩餘空間量)完全不必記,increment/decrement 類操作只要記操作型別與增減量,不需要前後影像。每個頁面只有一個 page LSN,內容是最近套用其上的更新或 CLR 的 LSN。

正常更新路徑

要更新一筆記錄,交易依序:鎖住該記錄、把頁面 fix 進緩衝池、以 X 模式加 latch、執行更新、把日誌記錄 append 到日誌、把該日誌記錄的 LSN 寫進 page LSN 與交易表,最後 unlatch 並 unfix。呼叫 logger 期間 latch 是刻意持有的,這樣同一頁面的日誌順序才會與該頁上實際的更新順序一致;在重演歷史的前提下,這是衍生欄位能安全做實體 redo 的關鍵。提供頁面實體一致性的是 latch 而非鎖,且同時最多只持有兩個頁面 latch,因此交易不會在死結環路中等待 latch。有些情況(例如 insert)要先檢視頁面才知道記錄識別碼,此時會在持有 latch 的狀態下以 conditional 方式請求鎖;若未立即取得,就先釋放 latch、改以 unconditional 方式請求鎖,取得後重新加 latch,並重新檢查先前已驗證過的條件。

savepoint、回滾與 CLR 鏈

建立 savepoint 只是把 SaveLSN(交易最近一筆日誌記錄的 LSN)記在虛擬記憶體中;DB2 一類系統會在每個可能更新資料的 SQL 敘述前建立一個,用以提供敘述層級的原子性。ROLLBACK 例程接收 SaveLSN 與 TransID 後反向走訪:遇到非 CLR 就撤銷它,並寫下 UndoNxtLSN 等於該記錄 PrevLSN 的 CLR,再從 PrevLSN 繼續;途中遇到 CLR 則不撤銷,直接從其 UndoNxtLSN 繼續;redo-only 記錄一律略過。回滾期間完全不取鎖、只取 latch,因此正在回滾的交易不可能成為死結犧牲者。又因為某個物件的第一筆更新只會被撤銷一次,該 CLR 一寫出就能立刻釋放該物件的鎖,這讓「以部分回滾而非整筆回滾來化解死結」成為可行選項。

analysis 階段

重啟先讀 master record 找到最後一次完整 checkpoint 的 begin-chkpt,然後往前掃到日誌結尾。它以 end-chkpt 記錄初始化交易表與 dirty pages 表,接著逐筆處理後續記錄:更新該交易的 LastLSN 與 UndoNxtLSN;若頁面尚未出現在 dirty pages 表中,就以當前 LSN 作為 RecLSN 插入;遇 prepare 記錄把狀態設為 prepared,遇 rollback 記錄設回 unprepared;遇 end 記錄刪除該筆條目;遇 OSfile-return 記錄則把該檔案的所有頁面從表中移除。掃描結束後,狀態為 unprepared 且 UndoNxtLSN 為零的交易,代表當機前已完全回滾卻缺少 end 記錄,analysis 會補寫一筆並移除該條目。這一趟輸出 loser 清單、dirty pages 表,以及等於表中最小 RecLSN 的 RedoLSN;若表為空,redo 階段可整個略過。analysis 是最佳化而非必要,OS/2 Extended Edition 的 ARIES 實作就完全沒有 analysis 階段。

redo 階段

從 RedoLSN 開始往前掃描日誌。一筆可 redo 的 update 或 compensation 記錄,只有在其 PageID 出現在 dirty pages 表中、且其 LSN 大於等於該條目的 RecLSN 時才是候選,否則連 I/O 都不必做就跳過——RecLSN 就是靠這點限制需要讀入的頁面數量。對候選記錄,把頁面 fix 住並加 X latch,比較 page LSN 與日誌記錄的 LSN:若 page LSN 較小就套用更新並把 page LSN 設為該日誌記錄的 LSN;若不小,則把該條目的 RecLSN 前推為 page LSN 加一,因為這代表該頁在 checkpoint 之後確實已寫回磁碟。redo 期間完全不寫日誌,這正是它能大幅平行化的原因:系統可依據 dirty pages 表預先對所有需要的頁面發出非同步讀取,並把日誌記錄依頁面分成多個佇列交給不同行程處理;跨頁面的順序被打亂無妨,只要同一頁面的更新仍依日誌順序重新套用即可。

undo 階段

undo 階段以單次反向掃描回滾所有 loser:不斷從尚未撤銷完成的 unprepared 交易中挑出 UndoNxtLSN 最大者,處理該筆記錄。此階段不查 dirty pages 表,也不比較 page LSN,因為歷史已經重演過,該更新確定存在於頁面上。撤銷一筆更新時會寫下 CLR,把 CLR 的 LSN 蓋進頁面與 LastLSN,並把該交易的 UndoNxtLSN 設為被撤銷記錄的 PrevLSN;當 PrevLSN 為零就代表該交易已完全撤銷,於是寫下 end 記錄並移除表中條目。掃描途中遇到 CLR,只取用它的 UndoNxtLSN。undo 可以平行化,但由於 UndoNxtLSN 的鏈接關係,單一交易必須完整由同一個行程處理;undo 完成後,系統為 prepared 交易重新取得鎖,並做一次 checkpoint。

重啟期間的 checkpoint 與媒體復原

ARIES 允許在重啟過程中做 checkpoint,藉此限制「復原途中再次當機」的損失。analysis 之後的 checkpoint 直接記下當時的兩張表;redo 期間,緩衝管理員會把寫出頁面的 RecLSN 更新為「所有日誌記錄都已處理到的那個 LSN」;undo 開始時,重啟用的 dirty pages 表轉為緩衝池的表,清掉已不在緩衝區的頁面,之後就以正常運作方式維護。媒體復原使用 fuzzy image copy:直接從非揮發性儲存複製,可與更新並行進行,因此複本中可能含有未提交資料,並標記上最近一次完整 checkpoint 的 begin-chkpt。媒體復原的 redo 起點,是該實體在該 checkpoint 中髒頁 RecLSN 的最小值與 begin-chkpt LSN 兩者取小;復原時重新載入複本、自該點往前 redo,再撤銷所有動過該實體的進行中交易。由於每個頁面的變更都各自記錄日誌,單一毀損頁面可以只從 image copy 取出並單獨向前 roll forward;DB2 也用同樣的想法修復被異常終止行程弄壞的頁面,這種毀損靠頁首一個在加 latch 更新期間被設為 1 的位元來偵測。

論文證明了什麼 — 量測數據與證明

  • 回滾日誌量有界:一筆被回滾的交易所寫的 CLR 數量,恰好等於它正向處理時寫下的可撤銷日誌記錄數量,且在巢狀回滾與重啟途中反覆當機的情況下依然成立。論文指出,會 undo CLR 的 Encompass 與 DB2,在重啟反覆失敗時最壞情況下日誌量呈指數成長;IMS 與 Schwarz 的操作式日誌方法則呈線性成長。
  • 由於 CLR 永遠不會被撤銷,它只需要帶 redo 資訊,因此平均而言,回滾一筆交易所消耗的日誌空間只有其正向處理所消耗空間的一半。
  • 非揮發性儲存的永久空間額外開銷只有每頁一個 LSN,別無其他;相對地,DB2 在使用者把索引葉頁切成 2 到 16 個 minipage 時,必須為每個 minipage 額外維護一個 LSN,導致可存放鍵值的空間被切碎。
  • 在無競爭的情況下,取得與釋放一個 latch 只需數十個指令,而鎖需要數百個指令;一筆交易同時最多只持有兩到三個 latch、最多兩個頁面 latch;又因為回滾期間完全不取任何鎖,正在回滾的交易絕不可能捲入死結。
  • 重啟只需要對日誌做一次反向走訪(undo 階段),媒體復原也只需要一次正向走訪;當部分日誌存放在磁帶這類慢速媒體上時,這點格外重要。redo 階段只會讀取 dirty pages 表中、且 RecLSN 不大於日誌記錄 LSN 的那些頁面。
  • 作者引用的一項 ARIES 模擬研究指出,即使 checkpoint 間隔很長,復原仍然很快;並指出交易的平均回應時間,與「該交易獨自在永不失效系統中執行」的平均耗時之間差距小到可忽略,顯示這套復原方法與細粒度鎖定搭配得相當好。

限制與取捨 — 論文自承的,以及後來被發現的

  • 論文自承:重演歷史會把 loser 交易那些馬上就要被撤銷的更新也一併 redo,因此有一部分 redo 工作與頁面弄髒是可證明為多餘的;作者也指出後續研究已在探討如何限制對 loser 重演歷史的範圍。
  • 論文自承:當某個 loser 交易需要對離線物件做邏輯 undo 時,延後式或選擇式重啟就會失靈,因為受影響的頁面無法預測;對 ARIES/IM 這類高並行索引方法,甚至無法事先判斷頁面導向的 undo 是否足夠,這類交易只能被「停住」、持續持有鎖,等日後再完成回滾。
  • 論文自承:空間保留問題(讓未提交刪除所釋出的空間不被其他交易佔用)被明確留給另一篇論文處理;此外 undo 的平行度也受限,因為 UndoNxtLSN 鏈接迫使單一交易必須完整由一個行程處理。
  • 論文自承:全文只處理單一站台的日誌,不涉及訊息的日誌與復原;而巢狀交易模型、shared-disk 資料共享、索引專屬的並行控制,都需要另外的後續論文,並非從 ARIES 直接推導而得。
  • 後續研究揭露的限制:ARIES 把復原綁定在「原地更新加上 undo 日誌」之上,對於把舊版本保存在資料本身的多版本引擎並不合適。例如 PostgreSQL 採用 ARIES 式的 physiological WAL 與每頁 LSN,卻完全沒有 undo 階段,改以 MVCC 可見性與 vacuum 取代。

它後來變成什麼 — 繼承這個想法的系統

ARIES 成為關聯式引擎處理當機復原的預設答案;論文本身就列出它在 IBM 的 OS/2 Extended Edition Database Manager、DB2、Workstation Data Save Facility/VM、Starburst 與 QuickSilver,以及威斯康辛大學的 EXODUS 與 Gamma 資料庫機器上的實作。同一團隊後續把它延伸成 ARIES/KVL 與 ARIES/IM(處理 B-tree 的鍵值與索引管理並行控制)以及 ARIES/LHS(處理雜湊式儲存結構),邏輯 undo 的機制在這些場景中真正發揮價值。Microsoft SQL Server 直接實作 ARIES,其 analysis、redo、undo 三個階段連名稱都照用,後來的 constant-time recovery 也建立在同一套結構之上。MySQL 的 InnoDB 承襲了核心機制:每頁一個 LSN、帶 checkpoint LSN 的 write-ahead redo 日誌、fuzzy checkpoint,以及供回滾使用的獨立 undo 資訊。PostgreSQL 則採納了 physiological WAL 與每頁 LSN,卻刻意捨棄 undo 階段,改用 MVCC 與 vacuum,這是這套設計邊界最清楚的證據。論文所創造的詞彙——LSN、page LSN、CLR、RecLSN、dirty pages 表、repeating history、fuzzy checkpoint——如今已是教科書談復原的標準語言;而以日誌為中心的雲端設計,例如把 redo log 直接視為資料庫、只傳日誌記錄而不傳頁面的 Amazon Aurora,也明顯是 ARIES「日誌而非資料頁才是歷史的權威記錄」這一主張的後裔。

論文原文 — 逐字引用

“We introduce the paradigm of repeating history to redo all missing updates before performing the rollbacks of the loser transactions during restart after a system failure.”

摘要

“By not repeating history, the page LSN is no longer a true indicator of the current state of the page.”

§10.1

“In brief, ARIES accomplishes the goals that we set out with by logging all updates on a per-page basis, using an LSN on every page for tracking page state, repeating history during restart recovery before undoing the loser transactions, and chaining the CLRs to the predecessors of the log records that they compensated.”

§13

術語 — 依本篇論文的用法

LSN(log sequence number)
每筆日誌記錄在附加到日誌時被指派的單調遞增識別碼,通常就是該記錄在不斷成長的日誌位址空間中的邏輯位址。它是排序,以及把日誌位置與頁面狀態關聯起來的通用貨幣。
page LSN
每個資料庫頁面中的一個欄位,存放描述該頁最近一次更新的日誌記錄的 LSN,不論那是一般更新記錄還是 CLR。ARIES 就是靠它與日誌記錄 LSN 的比較,判斷某筆更新是否已反映在頁面上。
CLR(compensation log record,補償日誌記錄)
用來描述回滾期間所執行更新的日誌記錄。在 ARIES 中 CLR 是 redo-only 且永遠不會被撤銷,因此不需要帶前影像,也永遠不會引發針對自己的補償。
UndoNxtLSN
只存在於 CLR 中的欄位,內容是該 CLR 所補償記錄的 PrevLSN,也就是該交易下一筆仍待撤銷的記錄位置。日後回滾時沿著它走,就能跳過所有已撤銷的內容。
RecLSN(recovery LSN)
當一個乾淨頁面首次以修改意圖被 fix 住時,記入 dirty pages 表的值,等於當下的 end-of-log LSN。它標示出該頁面的更新最早可能從日誌的哪個位置開始尚未落到非揮發性儲存上。
Repeating history(重演歷史)
ARIES 的重啟原則:在任何回滾開始之前,先把所有在頁面上缺席的已記錄更新全部 redo,包含從未提交的交易的更新。這讓資料庫回到失效當下的精確狀態,使 undo 可以無條件進行。
Loser 交易
系統失效時既未提交、也未進入 two-phase commit 之 in-doubt 狀態的交易。loser 的更新在 redo 階段和其他交易一樣被重做,之後才在 undo 階段被回滾掉。
Nested top action
交易中的一段動作子序列,一旦完成就不得被撤銷,即使外層交易回滾也一樣,但它本身仍必須具備原子性。ARIES 的實作方式是在序列結尾寫一筆 dummy CLR,其 UndoNxtLSN 指回序列開始之前的位置。
Latch
類似 semaphore 的輕量原語,用來在讀取或修改頁面期間保證頁面的實體一致性;相對地,鎖保證的是資料的邏輯一致性。latch 持有時間很短,不納入死結偵測器追蹤,且其請求方式被設計成永遠不會參與死結。

在時間軸上的位置 — 這篇論文在整段故事中的座標

在時間軸上查看