今天來聊兩個問題：

• 如果緩沖池（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算法是數據恢復的典型算法，很多消息系統，存儲系統，事務系統對算法進行過效率改良，但其內核，萬變不離其宗。思路，比結論更重要。