ARIES，數據恢復算法，萬變不離其宗...
今天來聊兩個問題：
- 如果緩沖池（buffer pool）滿了，哪些數據頁（page）要刷盤，哪些數據頁不刷盤？
- 數據庫崩了，怎么利用檢查點（checkpoint）與預寫日志恢復數據？
問題一：緩沖池滿時的刷盤策略
首先來回顧一下《預寫日志WAL的核心思路...》中相關的一些知識點：
- 檢查點記錄了某一個時刻，緩沖池中所有數據頁的狀態信息；
- 預寫日志（write-ahead logging，WAL）中記錄了，事務在執行過程中，對數據庫進行的所有寫操作；
- 日志序列號（log sequence number，LSN），可以標識所有操作序列時序的依據；
再來介紹兩個新的知識點：
其一，在數據庫中，需要存儲一個信息：flushed-LSN：預寫日志已刷盤的最大LSN。
畫外音：這是日志刷盤。
其二，每個數據頁X，還要包含兩個信息：
- page-LSN：最近修改數據頁的LSN。畫外音：每一頁數據，都會存儲這個LSN。
- rec-LSN：上次刷盤以來，最早修改數據頁的LSN。畫外音：每一頁數據，也會存儲這個LSN。
這是兩個邊界LSN。
也就是說，在[rec-LSN, page-LSN]之間的所有操作，都將這一頁數據變成了臟數據。
畫外音：這是數據頁刷盤。
如果flushed-LSN >= page-LSN(X)
說明：我們可以將頁面X刷到磁盤上，因為在那之前的所有日志，都已經刷到了磁盤上。
畫外音：這是WAL原則，先刷日志，才能刷數據。
反之，如果flushed-LSN =< page-LSN(X)
說明：有些對數據頁X的操作，還沒有被刷到預寫日志磁盤上，此時我們不能將數據頁X刷到磁盤。
如上圖例子所示，共有四個事務：
- T1，將A由1改為2；
- T2，將A由2改為3；
- T3，將A由3改為4；
- T4，將A由4改為9；
對于預寫日志來說：
- LSN 001-010都已經刷到磁盤上
- LSN 011-013都還在WAL buffer里
對于數據庫來說：
- flushed-LSN=10
- 這是預寫日志已刷盤的最大LSN。
對于數據頁X來說：
- page-LSN(X)=12
- 數據buffer里，T4已經將A由4改為了9。
此時，flushed-LSN =< page-LSN(X)
于是，我們不能將數據頁X刷到磁盤，因為預寫日志還沒有完成。我們只能刷盤其他數據頁，來騰出緩沖池的內存空間哈。
問題二：數據庫崩潰時的數據恢復算法
數據庫崩潰后，所有內存buffer（WAL buffer以及buffer pool）中的數據都會丟失，我們如何利用檢查點與預寫日志，對數據進行恢復呢？
最常見故障恢復（crash recovery）算法是ARIES，Algorithms for Recovery and Isolation Exploiting Semantics，語義恢復與隔離算法。
這個算法的核心包含三個階段：
階段一，分析階段：分析預寫日志，對事務進行分類。
分析哪些預寫日志？
假設刷新檢查點日志的時刻是LSN，需要分析所有檢查點LSN之后的預寫日志。
如何對事務進行分類？
從檢查點LSN開始，從前往后掃描預寫日志：
- 每條日志記錄對應事務Tx，將Tx加入undo-Tx集合；
- 遇到<Ti, Commit>記錄，將Ti移出undo-Tx集合；
階段二，Redo階段：重做檢查點LSN之后，預寫日志中的所有操作。
從檢查點LSN開始，從前往后掃描預寫日志：
遇到<Ti, update>記錄，修改檢查點中對應的數據頁X，將對應的數據進行修改，如此一來，就恢復到了數據庫崩潰前的緩沖池數據頁鏡像。
這些數據頁能全部刷盤嗎？
不能，沒有提交的事務的操作，必須進行回滾。
階段三，Undo階段：對于沒有提交的事務，恢復這些事務對數據頁的修改。
從flushed-LSN開始，從后往前逆向掃描預寫日志，直到檢查點LSN：
遇到<Ti, update>記錄，如果Ti在undo-Tx集合中，就將對應的數據頁進行回滾修改，如此一來，所有未提交事務的修改，就進行了回滾。
ARIES算法是數據恢復的典型算法，很多消息系統，存儲系統，事務系統對算法進行過效率改良，但其內核，萬變不離其宗。思路，比結論更重要。
