今天來聊兩個問題：

• 如果緩沖池（buffer pool）滿了，哪些數(shù)據(jù)頁（page）要刷盤，哪些數(shù)據(jù)頁不刷盤？
• 數(shù)據(jù)庫崩了，怎么利用檢查點（checkpoint）與預寫日志恢復數(shù)據(jù)？

問題一：緩沖池滿時的刷盤策略

首先來回顧一下《預寫日志W(wǎng)AL的核心思路...》中相關的一些知識點：

• 檢查點記錄了某一個時刻，緩沖池中所有數(shù)據(jù)頁的狀態(tài)信息；
• 預寫日志（write-ahead logging，WAL）中記錄了，事務在執(zhí)行過程中，對數(shù)據(jù)庫進行的所有寫操作；
• 日志序列號（log sequence number，LSN），可以標識所有操作序列時序的依據(jù)；

再來介紹兩個新的知識點：

其一，在數(shù)據(jù)庫中，需要存儲一個信息：flushed-LSN：預寫日志已刷盤的最大LSN。

畫外音：這是日志刷盤。

其二，每個數(shù)據(jù)頁X，還要包含兩個信息：

• page-LSN：最近修改數(shù)據(jù)頁的LSN。畫外音：每一頁數(shù)據(jù)，都會存儲這個LSN。
• rec-LSN：上次刷盤以來，最早修改數(shù)據(jù)頁的LSN。畫外音：每一頁數(shù)據(jù)，也會存儲這個LSN。

這是兩個邊界LSN。

也就是說，在[rec-LSN, page-LSN]之間的所有操作，都將這一頁數(shù)據(jù)變成了臟數(shù)據(jù)。

畫外音：這是數(shù)據(jù)頁刷盤。

如果flushed-LSN >= page-LSN(X)

說明：我們可以將頁面X刷到磁盤上，因為在那之前的所有日志，都已經(jīng)刷到了磁盤上。

畫外音：這是WAL原則，先刷日志，才能刷數(shù)據(jù)。

反之，如果flushed-LSN =< page-LSN(X)

說明：有些對數(shù)據(jù)頁X的操作，還沒有被刷到預寫日志磁盤上，此時我們不能將數(shù)據(jù)頁X刷到磁盤。

如上圖例子所示，共有四個事務：

• T1，將A由1改為2；
• T2，將A由2改為3；
• T3，將A由3改為4；
• T4，將A由4改為9；

對于預寫日志來說：

• LSN 001-010都已經(jīng)刷到磁盤上
• LSN 011-013都還在WAL buffer里

對于數(shù)據(jù)庫來說：

• flushed-LSN=10
• 這是預寫日志已刷盤的最大LSN。

對于數(shù)據(jù)頁X來說：

• page-LSN(X)=12
• 數(shù)據(jù)buffer里，T4已經(jīng)將A由4改為了9。

此時，flushed-LSN =< page-LSN(X)

于是，我們不能將數(shù)據(jù)頁X刷到磁盤，因為預寫日志還沒有完成。我們只能刷盤其他數(shù)據(jù)頁，來騰出緩沖池的內存空間哈。

問題二：數(shù)據(jù)庫崩潰時的數(shù)據(jù)恢復算法

數(shù)據(jù)庫崩潰后，所有內存buffer（WAL buffer以及buffer pool）中的數(shù)據(jù)都會丟失，我們如何利用檢查點與預寫日志，對數(shù)據(jù)進行恢復呢？

最常見故障恢復（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>記錄，修改檢查點中對應的數(shù)據(jù)頁X，將對應的數(shù)據(jù)進行修改，如此一來，就恢復到了數(shù)據(jù)庫崩潰前的緩沖池數(shù)據(jù)頁鏡像。

這些數(shù)據(jù)頁能全部刷盤嗎？

不能，沒有提交的事務的操作，必須進行回滾。

階段三，Undo階段：對于沒有提交的事務，恢復這些事務對數(shù)據(jù)頁的修改。

從flushed-LSN開始，從后往前逆向掃描預寫日志，直到檢查點LSN：

遇到<Ti, update>記錄，如果Ti在undo-Tx集合中，就將對應的數(shù)據(jù)頁進行回滾修改，如此一來，所有未提交事務的修改，就進行了回滾。

ARIES算法是數(shù)據(jù)恢復的典型算法，很多消息系統(tǒng)，存儲系統(tǒng)，事務系統(tǒng)對算法進行過效率改良，但其內核，萬變不離其宗。思路，比結論更重要。