恢復(fù)是為了在發(fā)生錯誤時保證數(shù)據(jù)庫的原子性、一致性和持久性。
恢復(fù)包含兩部分：在正常事務(wù)執(zhí)行時進(jìn)行的操作來保證當(dāng)錯誤發(fā)生時能夠恢復(fù)（log）；和在錯誤發(fā)生后進(jìn)行的恢復(fù)保證原子性、一致性和持久性。

最初的針對內(nèi)存數(shù)據(jù)庫的恢復(fù)都是假設(shè)沒有持久性存儲(disk)的，但是這種硬件沒有廣泛使用，所以這里還是用SSD/HDD。

內(nèi)存數(shù)據(jù)庫的恢復(fù)比面向磁盤的數(shù)據(jù)庫簡單，在：恢復(fù)時不需要追蹤臟頁防止崩潰；不需要存undo 記錄，只需要redo；不需要記錄對索引的修改。（這是如何體現(xiàn)的呢）
但內(nèi)存數(shù)據(jù)庫仍受限于disk的同步。

Logging Schemes
一樣有物理日志和邏輯日志——物理日志記錄的是修改，比如存一個屬性被修改前后的值；而邏輯日志記錄的是事務(wù)更高等級的操作，比如可能直接存了一個事物的sql語句。
邏輯日志記的東西少，但是如果有并發(fā)事務(wù)很難用邏輯日志進(jìn)行恢復(fù)：如果隔離水平比較低很難確定查詢修改了哪些數(shù)據(jù)；需要更長的時間因為需要重新執(zhí)行事務(wù)的操作。

Log Flushing
兩種處理方式：1.一次全部flush——事務(wù)完全提交后再將日志記錄寫入磁盤；2.允許在事務(wù)還未提交之前將日志記錄寫入磁盤

批量提交——可以把幾個事務(wù)的日志記錄一起提交（超時或者緩沖池要滿的時候），可以把I/O成本分?jǐn)偟綆讉€事務(wù)上

MVCC中的delta records和物理日志是一樣的，在undo的時候直接可以取出來舊的值。

MSSQL的constant time recovery

把MVCC的time-travel表作為恢復(fù)日志（time-travel table是除了主表之外的表，總是在主表中進(jìn)行數(shù)據(jù)的修改，然后將原來的值放在time-travel表中），在WAL中利用版本的元數(shù)據(jù)來處理undo而不用處理undo記錄?；謴?fù)時間由必須要從磁盤中讀的版本記錄的條數(shù)來定的。

MSSQL.png

持久化版本存儲

1. In-row Versioning: 把對這個元組的小的更新作為一個增量記錄內(nèi)嵌到主表中這條記錄
2. off-row Versioning: 專門有個表來存舊版本，并為并發(fā)插入優(yōu)化；所有表的版本都存到一個表中，要存所有的插入的redo記錄在這張表中(WAL)

MSSQL CTR 恢復(fù)協(xié)議
三階段，分析、redo、undo

1. 分析：確定在log中每個事務(wù)的狀態(tài)——哪些事務(wù)要REDO，哪些要undo
2. Redo：恢復(fù)主表和版本到崩潰時的狀態(tài)
3. Undo: 標(biāo)記尚未提交的事務(wù)為aborted在全局事務(wù)狀態(tài)表中，使得未來的事務(wù)忽略到它們的版本；通過logical revert來逐漸移除舊的版本

logical revert

1. 后臺清理：GC線程掃描所有的塊，溢出要回收的版本；如果主表中最新的版本來自于aborted事務(wù)，它會把已經(jīng)已提交的版本再拿回主表
2. 丟棄版本重寫：如果一個版本來自于aborted事務(wù)，事務(wù)會重寫這個最新的版本(而不再把主表中這個廢棄的版本再像平常一樣存到time-travel表中)

SILO

用的是單版本化OCC和epoch-based GC
SiloR用的是 物理日志+檢查點來保證事務(wù)的持久性（通過并行 日志、檢查點和恢復(fù)保證了高性能）

日志協(xié)議

DBMS假設(shè)每個CPU socket都有存儲設(shè)備（socket就是路，幾路CPU大概就是插了幾塊CPU的意思吧）——假設(shè)每個存儲設(shè)備有一個日志線程，每個CPU socket有若干個worker 線程
當(dāng)worker執(zhí)行一個事務(wù)時，會創(chuàng)建新的日志記錄包含寫入數(shù)據(jù)庫中的值(redo)

每個日志線程都會維護(hù)一個日志緩沖池給worker線程。當(dāng)日志緩沖池滿了，日志線程就flush到磁盤中，嘗試獲得一個新的日志緩沖池，如果沒有新的，stall

日志文件
日志線程要把日志緩沖池中的數(shù)據(jù)寫到磁盤中的文件中，每隔100 epochs創(chuàng)建一個新文件，舊文件用它包含的最大的epoch命名。

日志記錄的格式：
修改記錄的事務(wù)id——Tid
日志三元組——表，關(guān)鍵字，值(修改前后)
值可以使 屬性+值對的形式

一個特殊的日志線程會track當(dāng)前的持久化epoch(pepoch)，特殊的日志文件也會維護(hù)所有的日志線程的最新的持久化的epoch

一個事物在epoch e執(zhí)行，只有在pepoch持久化到了磁盤才能釋放其結(jié)果。

SILOR 恢復(fù)協(xié)議

兩階段
1.加載上一個檢查點：把上一個檢查點的東西全部取出，所有的索引也需要由檢查點重建
2.Log replay：逆向執(zhí)行日志來重構(gòu)上一個版本的元組；執(zhí)行時產(chǎn)生的事務(wù)id可以保證恢復(fù)的串行化順序

Log replay
檢查pepoch文件來決定最近的持久化epoch，在pepoch之后的日志記錄統(tǒng)統(tǒng)忽略。

日志文件從新到舊進(jìn)行處理：

• 值logging可以按任意順序（什么 是value logging）;
• 對于每條日志記錄，線程都需要檢查它對應(yīng)的元組是不是存在，如果不存在就根據(jù)這條記錄中的值創(chuàng)建，如果存在看這條記錄的Tid與已經(jīng)存在的這個元組的Tid大小比較，如果日志記錄的Tid更新，那么修改。

內(nèi)存數(shù)據(jù)庫的檢查點協(xié)議

檢查點的實現(xiàn)與并發(fā)控制協(xié)議是息息相關(guān)的
檢查點線程會掃描每個表，然后把數(shù)據(jù)異步寫入磁盤。

Ideal 檢查點協(xié)議：不會降低一般事務(wù)處理速度；不導(dǎo)致大延遲；不能有過度的內(nèi)存開銷。

實現(xiàn)

1. 一致性檢查點：數(shù)據(jù)庫在某個時刻的一致性快照——no uncommited changes，恢復(fù)的時候按照檢查點恢復(fù)就好，無需額外操作
2. 模糊檢查點：可能包含一些尚未提交的事務(wù)修改過的記錄，必須做額外的處理把這些修改先給清理掉

檢查點可以由DBMS創(chuàng)建，也可以用OS fork snapshots，fork一個子進(jìn)程讓它把數(shù)據(jù)庫的內(nèi)容(everything)寫到磁盤上，但是需要清理uncommited changes（如果有非活躍事務(wù)可以對其進(jìn)行一致性檢查，否則用內(nèi)存中的undo log回滾事務(wù)到子進(jìn)程）

檢查點的內(nèi)容

1. Complete Checkpoint 把每個表的每個元組都記錄下來，無論上個檢查點以來是否做了修改
2. Dleta Checkpoint 只把上個檢查點以來修改的元組記錄下來，后臺可以把多個檢查點合并

設(shè)立檢查點的頻率

1. 基于時間：在上個檢查點完成后等待固定的時間設(shè)立新檢查點
2. 基于日志文件大?。涸谌罩疚募袑懥俗銐虻臄?shù)據(jù)后設(shè)立檢查點
3. 在DBA關(guān)閉系統(tǒng)時（強(qiáng)制性的）

Restart Protocol

DBMS不是所有重啟都是因為崩潰，也可能是因為更新系統(tǒng)、硬件和DBMS，所以需要一種方式快速的重啟而不用從磁盤中重新讀整個數(shù)據(jù)庫

其中FaceBook SCUBA的做法是，把數(shù)據(jù)庫的內(nèi)存生命周期和進(jìn)程周期分開，把數(shù)據(jù)庫存在共享內(nèi)存中，DBMS進(jìn)程重啟時內(nèi)存中的內(nèi)容還在就不需要reload了。

FaceBook SCUBA是一個分布式內(nèi)存數(shù)據(jù)庫，進(jìn)行時間序列事件分析和異常檢測。
分葉子節(jié)點和聚合節(jié)點，葉子節(jié)點執(zhí)行查詢，聚合節(jié)點把從葉子節(jié)點的查詢結(jié)果進(jìn)行聚合。

共享內(nèi)存重啟
實現(xiàn)方法

1. 共享內(nèi)存堆：正常操作時所有的數(shù)據(jù)都分配在共享內(nèi)存中；需要自定義分配器來細(xì)化內(nèi)存段實現(xiàn)線程安全和可擴(kuò)展性；不能延遲分配備份頁
2. 正常操作時所有數(shù)據(jù)都分配在本地內(nèi)存；shutdown時把數(shù)據(jù)從本地內(nèi)存堆中復(fù)制到共享內(nèi)存

restart流程如下：
當(dāng)管理員啟動重啟，節(jié)點停止更新；DBMS開始把數(shù)據(jù)從堆內(nèi)存復(fù)制到共享內(nèi)存（每個block復(fù)制成功后就從堆中刪除）；快照復(fù)制結(jié)束，DBMS重啟。
重啟時首先檢查共享內(nèi)存中是否有合法的數(shù)據(jù)庫如果有就復(fù)制到堆中，沒有的話需要從磁盤中重啟。

物理日志是通用的選擇，因為它支持所有的并發(fā)控制模式。

MVCC用Copy-on-update檢查點