今天來(lái)聊兩個(gè)問(wèn)題：

• 如果緩沖池（buffer pool）滿(mǎn)了，哪些數(shù)據(jù)頁(yè)（page）要刷盤(pán)，哪些數(shù)據(jù)頁(yè)不刷盤(pán)？
• 數(shù)據(jù)庫(kù)崩了，怎么利用檢查點(diǎn)（checkpoint）與預(yù)寫(xiě)日志恢復(fù)數(shù)據(jù)？

問(wèn)題一：緩沖池滿(mǎn)時(shí)的刷盤(pán)策略

首先來(lái)回顧一下《預(yù)寫(xiě)日志W(wǎng)AL的核心思路...》中相關(guān)的一些知識(shí)點(diǎn)：

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

再來(lái)介紹兩個(gè)新的知識(shí)點(diǎn)：

其一，在數(shù)據(jù)庫(kù)中，需要存儲(chǔ)一個(gè)信息：flushed-LSN：預(yù)寫(xiě)日志已刷盤(pán)的最大LSN。

畫(huà)外音：這是日志刷盤(pán)。

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

• page-LSN：最近修改數(shù)據(jù)頁(yè)的LSN。畫(huà)外音：每一頁(yè)數(shù)據(jù)，都會(huì)存儲(chǔ)這個(gè)LSN。
• rec-LSN：上次刷盤(pán)以來(lái)，最早修改數(shù)據(jù)頁(yè)的LSN。畫(huà)外音：每一頁(yè)數(shù)據(jù)，也會(huì)存儲(chǔ)這個(gè)LSN。

這是兩個(gè)邊界LSN。

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

畫(huà)外音：這是數(shù)據(jù)頁(yè)刷盤(pán)。

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

說(shuō)明：我們可以將頁(yè)面X刷到磁盤(pán)上，因?yàn)樵谀侵暗乃腥罩?，都已?jīng)刷到了磁盤(pán)上。

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

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

說(shuō)明：有些對(duì)數(shù)據(jù)頁(yè)X的操作，還沒(méi)有被刷到預(yù)寫(xiě)日志磁盤(pán)上，此時(shí)我們不能將數(shù)據(jù)頁(yè)X刷到磁盤(pán)。

如上圖例子所示，共有四個(gè)事務(wù)：

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

對(duì)于預(yù)寫(xiě)日志來(lái)說(shuō)：

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

對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)：

• flushed-LSN=10
• 這是預(yù)寫(xiě)日志已刷盤(pán)的最大LSN。

對(duì)于數(shù)據(jù)頁(yè)X來(lái)說(shuō)：

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

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

于是，我們不能將數(shù)據(jù)頁(yè)X刷到磁盤(pán)，因?yàn)轭A(yù)寫(xiě)日志還沒(méi)有完成。我們只能刷盤(pán)其他數(shù)據(jù)頁(yè)，來(lái)騰出緩沖池的內(nèi)存空間哈。

問(wèn)題二：數(shù)據(jù)庫(kù)崩潰時(shí)的數(shù)據(jù)恢復(fù)算法

數(shù)據(jù)庫(kù)崩潰后，所有內(nèi)存buffer（WAL buffer以及buffer pool）中的數(shù)據(jù)都會(huì)丟失，我們?nèi)绾卫脵z查點(diǎn)與預(yù)寫(xiě)日志，對(duì)數(shù)據(jù)進(jìn)行恢復(fù)呢？

最常見(jiàn)故障恢復(fù)（crash recovery）算法是ARIES，Algorithms for Recovery and Isolation Exploiting Semantics，語(yǔ)義恢復(fù)與隔離算法。

這個(gè)算法的核心包含三個(gè)階段：

階段一，分析階段：分析預(yù)寫(xiě)日志，對(duì)事務(wù)進(jìn)行分類(lèi)。

分析哪些預(yù)寫(xiě)日志？

假設(shè)刷新檢查點(diǎn)日志的時(shí)刻是LSN，需要分析所有檢查點(diǎn)LSN之后的預(yù)寫(xiě)日志。

如何對(duì)事務(wù)進(jìn)行分類(lèi)？

從檢查點(diǎn)LSN開(kāi)始，從前往后掃描預(yù)寫(xiě)日志：

• 每條日志記錄對(duì)應(yīng)事務(wù)Tx，將Tx加入undo-Tx集合；
• 遇到<Ti, Commit>記錄，將Ti移出undo-Tx集合；

階段二，Redo階段：重做檢查點(diǎn)LSN之后，預(yù)寫(xiě)日志中的所有操作。

從檢查點(diǎn)LSN開(kāi)始，從前往后掃描預(yù)寫(xiě)日志：

遇到<Ti, update>記錄，修改檢查點(diǎn)中對(duì)應(yīng)的數(shù)據(jù)頁(yè)X，將對(duì)應(yīng)的數(shù)據(jù)進(jìn)行修改，如此一來(lái)，就恢復(fù)到了數(shù)據(jù)庫(kù)崩潰前的緩沖池?cái)?shù)據(jù)頁(yè)鏡像。

這些數(shù)據(jù)頁(yè)能全部刷盤(pán)嗎？

不能，沒(méi)有提交的事務(wù)的操作，必須進(jìn)行回滾。

階段三，Undo階段：對(duì)于沒(méi)有提交的事務(wù)，恢復(fù)這些事務(wù)對(duì)數(shù)據(jù)頁(yè)的修改。

從flushed-LSN開(kāi)始，從后往前逆向掃描預(yù)寫(xiě)日志，直到檢查點(diǎn)LSN：

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

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