崩潰恢復

恢復算法是一種確保數據庫ACID的技術，數據庫崩潰后， 所有已經提交但未刷新到磁盤的數據都有丟失的風險， 崩潰恢復算法就是為了防止數據庫崩潰后數據丟失的情況。

緩沖池管理策略

DBMS需要以下確保以下保證：

• 一旦DBMS告知某人該事務已經提交， 則該事務的更改都是持久的。

• 如果事務終止， 則任何部分更改都不會持久， 即回滾。

為了實現這兩個保證， 數據庫要做兩件事： undo和redo。

undo就是移除未完成的事務的影響或者更改； 重做就是對于已經提交的事務， 我們要確保系統重啟之后， 能夠保留所有更改。

竊取策略

決定了某個事務提交時， 他能否將另一個活躍事務未提交更改寫入磁盤。比如對于事務T1和T2. 他們都修改了同一個元組里面的不同字段A和B。 T2已經提交， 但是T1回滾了。

如果采用了竊取策略， 那么就允許T2在T1尚未提交的情況下將提交寫入磁盤， 即Andy所說的驅逐頁面。 這樣能夠減少內存的使用， 讓BufferPool中的frame更靈活。 如果不適用竊取， 那么就不允許提交， 也就是說所做的所有更改在未提交之前都要留在內存中，占用的內存就會更多。

強制策略

強制規定了DBMS是否允許事務在未提交時將已經做的更改提現到非易失性存儲中。

強制策略使回復變得容易， 因為所做的所有更改都已經體現到了磁盤中， 但是這會導致性能變差。

NO-STEAL-FORCE

NO-STEAL-FORCE是一種使用強制策略時因為沖突而使用的策略。 就比如還是這個例子：對于事務T1和T2. 他們都修改了同一個元組里面的不同字段A和B。 T2已經提交， 但是T1回滾了。 T2修改了B， T1修改了A。 此時如果是強制策略， 那么應該寫回，因為T2提交了。 但是又因為T1沒提交， 而且沒采用竊取，所以不應該提交。

這里采用的方法是將T2所做的更改復制成一個新的元組，這個元組中不包含T1所做的更改。然后將這個新數據寫回磁盤。

最容易實現的就是NO-STEAL-FORCE， 因為DBMS無需undo已經中止的事務所做的更改，因為已經中止的事務沒有將數據提現到磁盤； 同時DBMS不需要redo已經提交事務的更改， 因為已經提交的事務所做的更改已經提現到磁盤。

但是會有大量的額外開銷，因為要復制新的元組。

影子分頁

影子分頁就是事務在對數據進行更改時， 對數據所在頁進行復制， 即NO-STEAL-FORCE。

• master是已經提交的數據所在的原數據庫。
• 分頁是包含事務未提交的正在更改的臨時數據庫。

更新只在影子分頁中進行， 當事務提交后， 影子分頁變成master頁， 原master頁被垃圾回收。

執行

內存中和磁盤中都有一個頁表。

如果此時來了一個讀寫事務， 那么首先就要復制一個影子分頁表。

這個影子分頁表在執行事務過程中， 如果有數據被更改， 那么他的內存到磁盤的映射就會改變位置。

影子頁表新映射的位置儲存的就是新的數據。 然后如果又來一組事務進行讀取， 讀取的仍然是主頁表的映射。 但是如果第一個事務提交后， 那么影子頁表就要替換成主頁表。

恢復

• undo：刪除影子頁面，如果事務沒有提交， 只需要刪除影子頁面， 垃圾回收即可。
• redo：不需要， 因為事務只要提交后， 如果有更改，主頁表就已經被替換成為最新的。磁盤中的數據就是最新的數據。

缺點

• 復制頁表的成本高。 提交的成本高（TODO， 這里不理解為什么， 如果提交只是切換主表和分表， 那么交換指針即可。）

• 會導致數據存儲隨機化， 如同上面的演示， 原本是順序存儲， 但是使用影子分表復制后， 再提交事務， 那么數據就變得不再順序。這樣導致磁盤IO的速度降低， 因為磁盤不支持隨機讀寫。

• 一次僅支持一個寫入事務和批量事務。對于一次寫入批量事務， 會導致對于一個執行一毫秒的事務， 和一個執行一秒的事務， 兩個事務為一組的話， 那么一毫秒的事務必須等待一秒的事務結束后才能一起提交。 更不用說一次寫入一個事務速度會更低。

日志文件

SQLite之前做過類似影子分頁， 但不全是的工作。 影子分頁是指向修改后的數據， 而SQLite用過的日志文件是指向修改前的數據。

當要修改一個數據， 他要先把這個數據的原始版本寫入磁盤的一個日志文件（影子分頁是將修改后版本復制到磁盤）。 當事務崩潰了， 那么他就要讀取日志文件中的數據， 然后覆蓋掉已經磁盤中的已經修改的一些數據， 防止事務提交了一半到磁盤， 一半留在內存丟失。 這是用來redo。 而不是undo。 這個的一個缺點也是要進行隨機讀寫， 因為恢復的時候要從磁盤中找出那些被更新過的數據。

預寫日志（WAL）

WAL中包含了一些事務的記錄信息， 比如時間戳， 校驗和等等以及最基本的那個事務進行了更改， 更改了什么， 更改前的值（用于undo）， 更改后的值（用于redo）。

一但通知了外層系統， 當前事務已經提交， 那么就必須保證當前事務對數據庫所做的所有更改已經都記錄到了磁盤上的日志文件中。 即， 在將緩沖池中的任何臟頁寫入磁盤前， 必須先將使該頁面變臟的日志記錄刷新到磁盤。

這樣當BufferPool驅逐頁面時， 他就可以根據日志記錄看一下這個記錄， 在磁盤上是安全的， 這個記錄在磁盤上是不安全的。

他應用的使STEAL + NO-FORCE。 這里的STEAL就是未提交事務的日志記錄已經寫入到了磁盤， 我們就允許這些未提交的事務所產生的臟頁被刷新到磁盤。 NO-FORCE意味著我們不必在提交的時候就把臟頁刷新到磁盤。只需要確保日志記錄刷新到磁盤。

執行

一開始， 我們開啟一個事務， 在WAL Buffer中記錄這條事務已經開始。

然后， 對A進行修改， 這個時候要在日志中添加一條記錄， 里面包含了修改誰， 被修改前的值， 被修改后的值。

然后， 接下來就可以將內存中的數據修改， 變成臟頁：

然后W(B)同理， 最后COMMIT的時候要將WAL Buffer寫入磁盤。

當寫入成功后， 就可以告知外部系統此時事務已經提交。 此時Buffer Pool中的臟頁驅逐與否已經不重要，現在程序崩潰：

但是我們需要的所有信息已經在磁盤上， 我們重新執行一遍WAL Buffer即可， 就相當于重新執行一遍事務。

上面的所有都是順序IO， 因為我們只是寫入了WAL Buffer。 而且如果我們更改了10億個頁面， 我們的WAL Buffer就相當于有10組事務記錄。 相比十億個復制頁面， 十億組事務記錄小的多得多。

然后對于組提交， 組提交可以支持多個WAL Buffer。 同時設置一個系統時間，類似時間戳， 規定每超時一次時間戳， 那么就將WAL Buffer里面的數據寫入一次磁盤。 同時， 如果WAL Buffer 被寫滿了， 也要寫入磁盤。也就是不必等到COMMIT的時候才刷新到磁盤了。 同時多WAL Buffer， 比如雙WAL Buffer。 類似雙緩沖， 這樣就可以輪流記錄事務記錄了。

首先，T1BEGIN

然后T1寫A， 寫B：

然后T2BEGIN， 寫C， 此時WAL Buffer 滿了：

滿了后就要刷新到磁盤了。

然后開始向下一個WAL Buffer寫入：

如果在某個時刻， T1和T2因為某些原因暫停了。 經過了5s，假如系統設置的時間戳也是5s，那么就超時了。 就需要寫入磁盤：

此時第一個WAL Buffer已經寫入， 可以讓第一個WAL Buffer回來接收下面的記錄， 該記錄去寫入磁盤。

緩沖池策略

對比性能， 對于影子分頁， 采用了FORCE， NOSTEAL， 所以它的恢復非常快， 因為他不需要redo，只需要undo直接丟棄。 但是運行時很慢， 因為他要盲目的復制整個頁面。 開銷極大。

對于預寫日志， 采用了NO-FORCE， STEAL。 這樣它的恢復比較慢，因為他要去日志中查記錄，然后相當于重新執行了一遍事務。 但是運行時非常快， 因為他只是記錄了事務的記錄。有幾條事務， 就有幾組日志記錄。

大多數DBMS都采用NO-FORCE + STEAL策略， 因為它比FORCE + NO-STEAL策略更具有出色的運行時性能。 然而， 在恢復階段， NO-FORCE策略需要數據庫進行reco， 而STEAL策略需要數據庫進行undo（undo什么？ 這里不理解為什么STEAL需要undo。TODO）， 這使得其恢復時間比FORCE + NO-STEAL策略更慢。

日志方案

三種方案：

• Physical Logging

• Logical Logging

• Physiological Logging

物理日志基本上是進行字節級別的差異比較， 記錄頁面修改前后的內容。

邏輯日志不記錄底層的數據修改， 而是記錄我執行的查詢語句。

生理日志介于兩者之間， 類似于物理日志記錄， 他會追蹤事務對哪些頁面進行了修改。但他不會告訴在這個頁面上進行修改的具體偏移量。在恢復時，自行選擇在哪里進行恢復。

Physical記錄了Page也好， Offset具體偏移量； Logical記錄了整個sql； Physiological記錄了Page頁號， Slot則記錄了槽號。

檢查點

對于預寫日志， 如果不限制， 那么這個WAL Buffer會無限增長， 比如運行了10年的數據庫， 掛掉了。 然后恢復很明顯不能恢復10年的WAL。 所以就要添加一些檢查點。 比如定期要將所有的臟頁刷新到磁盤， 然后在WAL Buffer中添加檢查點， 以后就從檢查點開始向后恢復， 而不是從頭開始恢復了。