當(dāng)前位置：首頁 > 科技 > 軟件

ARIES，數(shù)據(jù)恢復(fù)算法，萬變不離其宗...

來源：責(zé)編：時間：2024-07-05 09:07:16 1115觀看

導(dǎo)讀今天來聊兩個問題：如果緩沖池（buffer pool）滿了，哪些數(shù)據(jù)頁（page）要刷盤，哪些數(shù)據(jù)頁不刷盤？數(shù)據(jù)庫崩了，怎么利用檢查點(diǎn)（checkpoint）與預(yù)寫日志恢復(fù)數(shù)據(jù)？問題一：緩沖池滿時的刷盤策略首先來回顧一下《預(yù)寫日志W(wǎng)AL的核心思路...》中

今天來聊兩個問題：

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

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

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

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

再來介紹兩個新的知識點(diǎn)：

其一，在數(shù)據(jù)庫中，需要存儲一個信息：flushed-LSN：預(yù)寫日志已刷盤的最大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刷到磁盤上，因?yàn)樵谀侵暗乃腥罩荆家呀?jīng)刷到了磁盤上。

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

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

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

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

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

對于預(yù)寫日志來說：

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

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

flushed-LSN=10
這是預(yù)寫日志已刷盤的最大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刷到磁盤，因?yàn)轭A(yù)寫日志還沒有完成。我們只能刷盤其他數(shù)據(jù)頁，來騰出緩沖池的內(nèi)存空間哈。

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

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

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

這個算法的核心包含三個階段：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文鏈接：http://www.www897cc.com/showinfo-26-98869-0.htmlARIES，數(shù)據(jù)恢復(fù)算法，萬變不離其宗...

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇：為金融數(shù)字化轉(zhuǎn)型保駕護(hù)航，Testin云測助力金融科技升級

下一篇：你應(yīng)該知道的主要軟件設(shè)計(jì)原則

標(biāo)簽：

熱門焦點(diǎn)

Redmi Buds 4開箱簡評：才199還有降噪可以無腦入

在上個月舉辦的Redmi Note11T Pro系列新機(jī)發(fā)布會上，除了兩款手機(jī)新品之外，Redmi還帶來了兩款TWS真無線藍(lán)牙耳機(jī)產(chǎn)品，Redmi Buds 4和Redmi Buds 4 Pro，此前我們在Redmi Note11T
三言兩語說透設(shè)計(jì)模式的藝術(shù)-簡單工廠模式

一、寫在前面工廠模式是最常見的一種創(chuàng)建型設(shè)計(jì)模式，通常說的工廠模式指的是工廠方法模式，是使用頻率最高的工廠模式。簡單工廠模式又稱為靜態(tài)工廠方法模式，不屬于GoF 23種設(shè)計(jì)
多線程開發(fā)帶來的問題與解決方法

使用多線程主要會帶來以下幾個問題：（一）線程安全問題　　線程安全問題指的是在某一線程從開始訪問到結(jié)束訪問某一數(shù)據(jù)期間，該數(shù)據(jù)被其他的線程所修改，那么對于當(dāng)前線程而言，該線程
小紅書1周漲粉49W+，我總結(jié)了小白可以用的N條漲粉筆記

作者：黃河懂運(yùn)營一條性教育視頻，被54萬人“珍藏”是什么體驗(yàn)？最近，情感博主@公主是用鮮花做的，火了！僅僅憑借一條視頻，光小紅書就有超過128萬人，為她瘋狂點(diǎn)贊！更瘋狂的是，這
騰訊VS網(wǎng)易，最卷游戲暑期檔，誰能笑到最后？

作者：無銹缽來源：財(cái)經(jīng)無忌7月16日晚，上海1862時尚藝術(shù)中心。伴隨著幻象的精準(zhǔn)命中，碩大的熒幕之上，比分被定格在了14：12，被寄予厚望的EDG戰(zhàn)隊(duì)以絕對的優(yōu)勢戰(zhàn)勝了BLG戰(zhàn)隊(duì)，拿下了總決
滴滴違法違規(guī)被罰80.26億共存在16項(xiàng)違法事實(shí)

滴滴違法違規(guī)被罰80.26億存在16項(xiàng)違法事實(shí)開始于2121年7月，歷經(jīng)一年時間，網(wǎng)絡(luò)安全審查辦公室對“滴滴出行”網(wǎng)絡(luò)安全審查終于有了一個暫時的結(jié)束。據(jù)“網(wǎng)信
由于成本持續(xù)增加，筆記本產(chǎn)品價格預(yù)計(jì)將明顯上漲

根據(jù)知情人士透露，由于材料、物流等成本持續(xù)增加，筆記本產(chǎn)品價格預(yù)計(jì)將在2021年下半年有明顯上漲。進(jìn)入6月下旬以來，全球半導(dǎo)體芯片缺貨情況加劇，顯卡、處理器
外交部：美方應(yīng)停止在網(wǎng)絡(luò)安全問題上不負(fù)責(zé)任地指責(zé)他國

　中國外交部今天（16日）舉行例行記者會。會上，有記者問，美國情報官員稱，他們正在阻攔來自中國以及其他國家的黑客獲取相關(guān)科研成果。中方對此有何評論？對此
中關(guān)村論壇11月25日開幕，15位諾獎級大咖將發(fā)表演講

11月18日，記者從2022中關(guān)村論壇新聞發(fā)布會上獲悉，中關(guān)村論壇將于11月25至30日在京舉行。本屆中關(guān)村論壇由科學(xué)技術(shù)部、國家發(fā)展改革委、工業(yè)和信息化部、國務(wù)

日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

ARIES，數(shù)據(jù)恢復(fù)算法，萬變不離其宗...

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

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

Redmi Buds 4開箱簡評：才199還有降噪可以無腦入

三言兩語說透設(shè)計(jì)模式的藝術(shù)-簡單工廠模式

多線程開發(fā)帶來的問題與解決方法

小紅書1周漲粉49W+，我總結(jié)了小白可以用的N條漲粉筆記

騰訊VS網(wǎng)易，最卷游戲暑期檔，誰能笑到最后？

滴滴違法違規(guī)被罰80.26億共存在16項(xiàng)違法事實(shí)

由于成本持續(xù)增加，筆記本產(chǎn)品價格預(yù)計(jì)將明顯上漲

外交部：美方應(yīng)停止在網(wǎng)絡(luò)安全問題上不負(fù)責(zé)任地指責(zé)他國

中關(guān)村論壇11月25日開幕，15位諾獎級大咖將發(fā)表演講

最新推薦

猜你喜歡

熱門推薦

相關(guān)資訊