在數(shù)據(jù)庫系統(tǒng)發(fā)展的歷史長河中，故障恢復(fù)問題始終伴隨左右，也深刻影響著數(shù)據(jù)庫結(jié)構(gòu)的發(fā)展變化。通過故障恢復(fù)機制，可以實現(xiàn)數(shù)據(jù)庫的兩個至關(guān)重要的特性：Durability of Updates以及Failure Atomic，也就是我們常說的的ACID中的A和D。磁盤數(shù)據(jù)庫由于其卓越的性價比一直以來都占據(jù)數(shù)據(jù)庫應(yīng)用的主流位置。然而，由于需要協(xié)調(diào)內(nèi)存和磁盤兩種截然不同的存儲介質(zhì)，在處理故障恢復(fù)問題時也增加了很多的復(fù)雜度。隨著學(xué)術(shù)界及工程界的共同努力及硬件本身的變化，磁盤數(shù)據(jù)庫的故障恢復(fù)機制也不斷的迭代更新，尤其近些年來，隨著NVM的浮現(xiàn)，圍繞新硬件的研究也如雨后春筍出現(xiàn)。

本文希望通過分析不同時間點的關(guān)鍵研究成果，來梳理數(shù)據(jù)庫故障恢復(fù)問題的本質(zhì)，其發(fā)展及優(yōu)化方向，以及隨著硬件變化而發(fā)生的變化。文章將首先描述故障恢復(fù)問題本身；然后按照基本的時間順序介紹傳統(tǒng)數(shù)據(jù)庫中故障恢復(fù)機制的演進及優(yōu)化；之后思考新硬件帶來的機遇與挑戰(zhàn)；并引出圍繞新硬件的兩個不同方向的研究成果；最后進行總結(jié)。

問題

數(shù)據(jù)庫系統(tǒng)運行過程中可能遇到的故障類型主要包括，Transaction Failure，Process Failure，System Failure以及Media Failure。其中Transaction Failure可能是應(yīng)用程序的主動回滾，也可能是并發(fā)控制機制發(fā)現(xiàn)沖突后的強制Abort；Process Failure指的是由于各種原因?qū)е碌倪M程退出，進程內(nèi)存內(nèi)容會丟失；System Failure來源于操作系統(tǒng)或硬件故障，同樣會導(dǎo)致內(nèi)存丟失；Media Failure則是存儲介質(zhì)的不可恢復(fù)損壞。數(shù)據(jù)庫系統(tǒng)需要正確合理的處理這些故障，從而保證系統(tǒng)的正確性。為此需要提供兩個特性：

Durability of Updates：已經(jīng)Commit的事務(wù)的修改，故障恢復(fù)后仍然存在；

Failure Atomic：失敗事務(wù)的所有修改都不可見。

因此，故障恢復(fù)的問題描述為：即使在出現(xiàn)故障的情況下，數(shù)據(jù)庫依然能夠通過提供Durability及Atomic特性，保證恢復(fù)后的數(shù)據(jù)庫狀態(tài)正確。然而，要解決這個問題并不是一個簡單的事情，由于內(nèi)存及磁盤不同的數(shù)據(jù)組織方式及性能差異，為了不顯著犧牲數(shù)據(jù)庫性能，長久以來人們對故障恢復(fù)機制進行了一系列的探索。

Shadow Paging

1981年，JIM GRAY等人在《The Recovery Manager of the System R Database Manager》采用了一種非常直觀的解決方式Shadow Paging[1]。System R的磁盤數(shù)據(jù)采用Page為最小的組織單位，一個File由多個Page組成，并通過稱為Direcotry的元數(shù)據(jù)進行索引，每個Directory項紀錄了當(dāng)前文件的Page Table，指向其包含的所有Page。采用Shadow Paging的文件稱為Shadow File，如下圖中的File B所示，這種文件會包含兩個Directory項，Current及Shawing。

事務(wù)對文件進行修改時，會獲得新的Page，并加入Current的Page Table，所有的修改都只發(fā)生在Current Directory；事務(wù)Commit時，Current指向的Page刷盤，并通過原子的操作將Current的Page Table合并到Shadow Directory中，之后再返回應(yīng)用Commit成功；事務(wù)Abort時只需要簡單的丟棄Current指向的Page；如果過程中發(fā)生故障，恢復(fù)時只需要恢復(fù)Shadow Directory，相當(dāng)于對所有未提交事務(wù)的回滾操作。Shadow Paging很方便的實現(xiàn)了：

Durability of Updates：事務(wù)完成Commit后，所有修改的Page已經(jīng)落盤，合并到Shadow后，其所有的修改可以在故障后恢復(fù)出來。

Failure Atomic：回滾的事務(wù)由于沒有Commit，從未影響Shadow Directory，因此其所有修改不可見。

雖然Shadow Paging設(shè)計簡單直觀，但它的一些缺點導(dǎo)致其并沒有成為主流，首先不支持Page內(nèi)并發(fā)，一個Commit操作會導(dǎo)致其Page上所有事務(wù)的修改被提交，因此一個Page內(nèi)只能包含一個事務(wù)的修改；其次不斷修改Page的物理位置，導(dǎo)致很難將相關(guān)的頁維護在一起，破壞局部性；另外，對大事務(wù)而言，Commit過程在關(guān)鍵路勁上修改Shadow Directory的開銷可能很大，同時這個操作還必須保證原子；最后，增加了垃圾回收的負擔(dān)，包括對失敗事務(wù)的Current Pages和提交事務(wù)的Old Pages的回收。

WAL

由于傳統(tǒng)磁盤順序訪問性能遠好于隨機訪問的特征，采用Logging的故障恢復(fù)機制意圖利用順序?qū)懙腖og來記錄對數(shù)據(jù)庫的操作，并在故障恢復(fù)后通過Log內(nèi)容將數(shù)據(jù)庫恢復(fù)到正確的狀態(tài)。簡單的說，采用Log機制的數(shù)據(jù)庫需要在每次修改數(shù)據(jù)內(nèi)容前先寫順序?qū)憣?yīng)的Log，同時為了保證恢復(fù)時可以從Log中看到最新的數(shù)據(jù)庫狀態(tài)，要求Log先于對應(yīng)的數(shù)據(jù)內(nèi)容落盤，也就是常說的Write Ahead Log，WAL。除此之外，事務(wù)完成Commit前還需要在Log中記錄對應(yīng)的Commit標(biāo)記，以供恢復(fù)時通過Log了解當(dāng)前的事務(wù)狀態(tài)，因此還需要關(guān)注Commit標(biāo)記和事務(wù)中數(shù)據(jù)內(nèi)容的落盤順序。根據(jù)Log中記錄的內(nèi)容可以分為三類：Undo-Only，Redo-Only，Redo-Undo。

Undo-Only Logging

Undo-Only Logging的Log記錄可以表示未，事務(wù)T修改了X的值，X的舊值是v。事務(wù)提交時，需要通過強制Flush保證Commit標(biāo)記落盤前，對應(yīng)事務(wù)的所有數(shù)據(jù)落盤，即落盤順序為Log記錄->Data->Commit標(biāo)記?；謴?fù)時可以根據(jù)Commit標(biāo)記判斷事務(wù)的狀態(tài)，并通過Undo Log中記錄的舊值將未提交事務(wù)的修改回滾。我們來審視一下Undo-Only對Durability及Atomic的保證：

Durability of Updates：Data強制刷盤保證，已經(jīng)Commit的事務(wù)由于其所有Data都已經(jīng)在Commit標(biāo)記之前落盤，因此會一直存在；

Failure Atomic：Undo Log內(nèi)容保證，失敗事務(wù)的已刷盤的修改會在恢復(fù)階段通過Undo日志回滾，不再可見。

然而Undo-Only依然有Page內(nèi)并發(fā)的問題，如果兩個事務(wù)的修改落到一個Page中，一個事務(wù)提交前需要的強制Flush操作會導(dǎo)致同Page所有事務(wù)的Data落盤，可能會早于對應(yīng)的Log項從而損害WAL。同時，Commit前的強制數(shù)據(jù)刷盤會導(dǎo)致關(guān)鍵路徑上過于頻繁的磁盤隨機訪問。

Redo-Only Logging

不同于Undo-Only，采用Redo-Only的Log中記錄的是修改后的新值。對應(yīng)地，Commit時需要保證Log中的Commit標(biāo)記需要在事務(wù)的任何事務(wù)羅盤前落盤，即落盤順序為Log記錄->Commit標(biāo)記->Data。恢復(fù)時同樣根據(jù)Commit標(biāo)記判斷事務(wù)狀態(tài)，并通過Redo Log中記錄的新值將已經(jīng)Commit，但數(shù)據(jù)沒有落盤的事務(wù)修改重放。

Durability of Updates：Redo Log內(nèi)容保證，已提交事務(wù)的未刷盤的修改，利用Redo Log中的內(nèi)容重放，之后可見；

Failure Atomic：阻止Commit前Data落盤保證，失敗事務(wù)的修改不會出現(xiàn)在磁盤上，自然不可見。

Redo-Only同樣有Page內(nèi)并發(fā)的問題，同Page中的多個不同事務(wù)，只要有一個未提交就不能刷盤，這些數(shù)據(jù)全部都需要維護在內(nèi)存中，會造成較大的內(nèi)存壓力。

Redo-Undo Logging

可以看出的只有Undo或Redo的Logging方式的問題主要來自與對Commit標(biāo)記及Data落盤順序的限制，而這種限制歸根結(jié)底來源于Log信息中對新值或舊值的缺失。因此Redo-Undo采用同時記錄新值和舊值的方式來取消對刷盤順序的限制。

Durability of Updates：Redo 內(nèi)容保證，已提交事務(wù)的未刷盤的修改，利用Redo Log中的內(nèi)容重放，之后可見；

Failure Atomic：Undo內(nèi)容保證，失敗事務(wù)的已刷盤的修改會在恢復(fù)階段通過Undo日志回滾，不再可見。

如此一來，同Page的不同事務(wù)提交就變得很簡單。同時可以將連續(xù)的數(shù)據(jù)攢著進行批量的刷盤已利用磁盤較高的順序?qū)懶阅堋?/p>

Force and Steal

從上面看出，Redo和Undo內(nèi)容分別可以保證Durability和Atomic兩個特性，其中一種信息的缺失需要用嚴格的刷盤順序來彌補。這里關(guān)注的刷盤順序包含兩個維度：

Force or No-Force：Commit時是否需要強制刷盤，采用Force的方式由于所有的已提交事務(wù)的數(shù)據(jù)一定已經(jīng)存在與磁盤，自然而然地保證了Durability。

No-Steal or Steal，Commit前數(shù)據(jù)是否可以提前刷盤，采用No-Steal的方式由于保證事務(wù)提交前修改不會出現(xiàn)在磁盤上，自然而然地保證了Atomic

總結(jié)一下，實現(xiàn)Durability可以記錄Redo信息或要求Force刷盤順序，實現(xiàn)Atomic需要記錄Undo信息或要求No-Steal刷盤順序，組合得到如下四種模式，如下圖所示：

ARIES，一統(tǒng)江湖

1992年，IBM的研究員們發(fā)表了《ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging》[2]，其中提出的ARIES逐步成為磁盤數(shù)據(jù)庫實現(xiàn)故障恢復(fù)的標(biāo)配，ARIES本質(zhì)是一種Redo-Undo的WAL實現(xiàn)。Normal過程：修改數(shù)據(jù)之前先追加Log記錄，Log內(nèi)容同時包括Redo和Undo信息，每個日志記錄產(chǎn)生一個標(biāo)記其在日志中位置的遞增LSN（Log Sequence Number）；數(shù)據(jù)Page中記錄最后修改的日志項LSN，以此來判斷Page中的內(nèi)容的新舊程度，實現(xiàn)冪等。故障恢復(fù)階段需要通過Log中的內(nèi)容恢復(fù)數(shù)據(jù)庫狀態(tài)，為了減少恢復(fù)時需要處理的日志量，ARIES會在正常運行期間周期性的生成Checkpoint，Checkpoint中除了當(dāng)前的日志LSN之外，還需要記錄當(dāng)前活躍事務(wù)的最新LSN，以及所有臟頁，供恢復(fù)時決定重放Redo的開始位置。需要注意的是，由于生成Checkpoint時數(shù)據(jù)庫還在正常提供服務(wù)（Fuzzy Checkpoint），其中記錄的活躍事務(wù)及Dirty Page信息并不一定準(zhǔn)確，因此需要Recovery階段通過Log內(nèi)容進行修正。

Recover過程：故障恢復(fù)包含三個階段：Analysis，Redo和Undo。Analysis階段的任務(wù)主要是利用Checkpoint及Log中的信息確認后續(xù)Redo和Undo階段的操作范圍，通過Log修正Checkpoint中記錄的Dirty Page集合信息，并用其中涉及最小的LSN位置作為下一步Redo的開始位置RedoLSN。同時修正Checkpoint中記錄的活躍事務(wù)集合（未提交事務(wù)），作為Undo過程的回滾對象；Redo階段從Analysis獲得的RedoLSN出發(fā)，重放所有的Log中的Redo內(nèi)容，注意這里也包含了未Commit事務(wù)；最后Undo階段對所有未提交事務(wù)利用Undo信息進行回滾，通過Log的PrevLSN可以順序找到事務(wù)所有需要回滾的修改。

除此之外，ARIES還包含了許多優(yōu)化設(shè)計，例如通過特殊的日志記錄類型CLRs避免嵌套Recovery帶來的日志膨脹，支持細粒度鎖，并發(fā)Recovery等。[3]認為，ARIES有兩個主要的設(shè)計目標(biāo)：

Feature：提供豐富靈活的實現(xiàn)事務(wù)的接口：包括提供靈活的存儲方式、提供細粒度的鎖、支持基于Savepoint的事務(wù)部分回滾、通過Logical Undo以獲得更高的并發(fā)、通過Page-Oriented Redo實現(xiàn)簡單的可并發(fā)的Recovery過程。

Performance：充分利用內(nèi)存和磁盤介質(zhì)特性，獲得極致的性能：采用No-Force避免大量同步的磁盤隨機寫、采用Steal及時重用寶貴的內(nèi)存資源、基于Page來簡化恢復(fù)和緩存管理。

NVM帶來的機遇與挑戰(zhàn)

從Shadow Paging到WAL，再到ARIES，一直圍繞著兩個主題：減少同步寫以及盡量用順序?qū)懘骐S機寫。而這些正是由于磁盤性能遠小于內(nèi)存，且磁盤順序訪問遠好于隨機訪問。然而隨著NVM磁盤的出現(xiàn)以及對其成為主流的預(yù)期，使得我們必須要重新審視我們所做的一切。相對于傳統(tǒng)的HDD及SSD，NVM最大的優(yōu)勢在于：

接近內(nèi)存的高性能

順序訪問和隨機訪問差距不大

按字節(jié)尋址而不是Block

在這種情況下，再來看ARIES的實現(xiàn)：

No-force and Steal：同時維護Redo， Undo和數(shù)據(jù)造成的三倍寫放大，來換取磁盤順序?qū)懙男阅?，但在NVM上這種取舍變得很不劃算；

Pages：為了遷就磁盤基于Block的訪問接口，采用Page的存儲管理方式，而內(nèi)存本身是按字節(jié)尋址的，因此，這種適配也帶來很大的復(fù)雜度。在同樣按字節(jié)尋址的NVM上可以消除。

近年來，眾多的研究嘗試為NVM量身定制更合理的故障恢復(fù)機制，我們這幾介紹其中兩種比較有代表性的研究成果，MARS希望充分利用NVM并發(fā)及內(nèi)部帶寬的優(yōu)勢，將更多的任務(wù)交給硬件實現(xiàn)；而WBL則嘗試重構(gòu)當(dāng)前的Log方式。

MARS

發(fā)表在2013年的SOSP上的《"From ARIES to MARS: Transaction support for next-generation, solid-state drives." 》提出了一種盡量保留ARIES特性，但更適合NVM的故障恢復(fù)算法MARS[3]。MARS取消了Undo Log，保留的Redo Log也不同于傳統(tǒng)的Append-Only，而是可以隨機訪問的。如下圖所示，每個事務(wù)會占有一個唯一的TID，對應(yīng)的Metadata中記錄了Log和Data的位置。

正常訪問時，所有的數(shù)據(jù)修改都在對應(yīng)的Redo Log中進行，不影響真實數(shù)據(jù)，由于沒有Undo Log，需要采用No-Steal的方式，阻止Commit前的數(shù)據(jù)寫回；Commit時會先設(shè)置事務(wù)狀態(tài)為COMMITTED，之后利用NVM的內(nèi)部帶寬將Redo中的所有內(nèi)容并發(fā)拷貝回Metadata中記錄的數(shù)據(jù)位置。如果在COMMITED標(biāo)記設(shè)置后發(fā)生故障，恢復(fù)時可以根據(jù)Redo Log中的內(nèi)容重放。其本質(zhì)是一種Redo加No-Steal的實現(xiàn)方式：

Durability of Updates： Redo實現(xiàn)，故障后重放Redo；

Failure Atomic：未Commit事務(wù)的修改只存在于Redo Log，重啟后會被直接丟棄。

可以看出，MARS的Redo雖然稱之為Log，但其實已經(jīng)不同于傳統(tǒng)意義上的順序?qū)懳募试S隨機訪問，更像是一種臨時的存儲空間，類似于Shadow的東西。之所以在Commit時進行數(shù)據(jù)拷貝而不是像Shadow Paging一樣的元信息修改，筆者認為是為了保持數(shù)據(jù)的局部性，并且得益于硬件優(yōu)異的內(nèi)部帶寬。

WBL

不同于MARS保留Redo信息的思路，2016年VLDB上的《 "Write Behind Logging" 》只保留了Undo信息。筆者認為這篇論文中關(guān)于WBL的介紹里，用大量筆墨介紹了算法上的優(yōu)化部分，為了抓住其本質(zhì)，這里先介紹最基本的WBL算法，WBL去掉了傳統(tǒng)的Append Only的Redo和Undo日志，但仍然需要保留Undo信息用來回滾未提交事務(wù)。事務(wù)Commit前需要將其所有的修改強制刷盤，之后在Log中記錄Commit標(biāo)記，也就是這里說的Write Behind Log?；謴?fù)過程中通過分析Commit標(biāo)記將為提交的事務(wù)通過Undo信息回滾?？梢钥闯鯳BL算法本身非常簡單，在這個基礎(chǔ)上，WBL做了如下優(yōu)化：

Group Commit：周期性的檢查內(nèi)存中的修改，同樣先將所有修改刷盤后寫Log，Log項中記錄最新Commit并落盤的最大事務(wù)TimeStamp cp，保證早于cp的所有事務(wù)修改都已經(jīng)落盤；同時記錄當(dāng)前分配出去的最大TimeStamp cd；也就是說此時所有有修改但未提交的事務(wù)Timestamp都落在cp和cd之間。Reovery的時候只需對這部分數(shù)據(jù)進行回滾；

針對多版本數(shù)據(jù)庫，多版本信息已經(jīng)起到了undo的作用，因此不需要再額外記錄undo信息；

延遲回滾：Recovery后不急于對未提交事務(wù)進行回滾，而是直接提供服務(wù)，一組(cp, cd)稱為一個gap，每一次故障恢復(fù)都可能引入新的gap，通過對比事務(wù)Timestamp和gap集合，來判斷數(shù)據(jù)的可見性，需要依靠后臺垃圾回收線程真正的進行回滾和對gap的清理，如下圖所示

可以看出，WBL本質(zhì)并沒有什么新穎，是一個Force加Undo的實現(xiàn)方式，其正確性保證如下：

Durability of Updates：Commit事務(wù)的數(shù)據(jù)刷盤后才進行Commit，因此Commit事務(wù)的數(shù)據(jù)一定在Recovery后存在

Failure Atomic：通過記錄的Undo信息或多版本時的歷史版本信息，在Recovery后依靠后臺垃圾回收線程進行回滾。

總結(jié)

數(shù)據(jù)庫故障恢復(fù)問題本質(zhì)是要在容忍故障發(fā)生的情況下保證數(shù)據(jù)庫的正確性，而這種正確性需要通過提供Durability of Updates和Failure Atomic來保證。其中Duribility of Update要保證Commit事務(wù)數(shù)據(jù)在恢復(fù)后存在，可以通過Force機制或者通過Redo信息回放來保證；對應(yīng)的，F(xiàn)ailure Atomic需要保證未Commit事務(wù)的修改再恢復(fù)后消失，可以通過No-Steal機制或者通過Undo信息回滾來保證?？梢员ＷCDurability和Atomic的方式，對本文提到的算法進行分類，如下：

Shadow Paging可以看做是采用了Force加No-Steal的方式，沒有Log信息，在Commit時，通過原子的修改Directory元信息完成數(shù)據(jù)的持久化更新，但由于其對Page內(nèi)并發(fā)的限制，以及對數(shù)據(jù)局部性的破壞等原因，沒有成為主流；

Logging的實現(xiàn)方式增加了Redo或Undo日志，記錄恢復(fù)需要的信息，從而放松Force或No-Steal機制對刷盤順序的限制，從而盡量用磁盤順序?qū)懘骐S機寫獲得較好的性能。ARIES算法是在這一方向上的集大成者，其對上層應(yīng)用提供了豐富靈活的接口，采用了No-Force加Steal機制，將傳統(tǒng)磁盤上的性能發(fā)揮到極致，從而成為傳統(tǒng)磁盤數(shù)據(jù)故障恢復(fù)問題的標(biāo)準(zhǔn)解決方案；

隨著NVM設(shè)備的逐步出現(xiàn)，其接近內(nèi)存的性能、同樣優(yōu)異的順序訪問和隨機訪問性能，以及基于字節(jié)的尋址方式，促使人們開始重新審視數(shù)據(jù)庫故障恢復(fù)的實現(xiàn)。其核心思路在于充分利用NVM硬件特性，減少Log機制導(dǎo)致的寫放大以及設(shè)計較復(fù)雜的問題；

MARS作為其中的佼佼者之一，在NVM上維護可以隨機訪問的Redo日志，同時采用Force加Steal的緩存策略，充分利用NVM優(yōu)異的隨機寫性能和內(nèi)部帶寬。

WBL從另一個方向進行改造，保留Undo信息，采用No-Force加No-Steal的緩存策略，并通過Group Commit及延遲回滾等優(yōu)化，減少日志信息，縮短恢復(fù)時間。

本文介紹了磁盤數(shù)據(jù)庫一路走來的核心發(fā)展思路，但距離真正的實現(xiàn)還有巨大的距離和眾多的設(shè)計細節(jié)，如對Logical Log或Physical Log的選擇、并發(fā)Recovery、Fuzzy Checkpoing、Nested Top Actions等，之后會用單獨的文章以InnoDB為例來深入探究其設(shè)計和實現(xiàn)細節(jié)。