關(guān)系數(shù)據(jù)庫中的事務(wù)故障恢復(fù)并不是一個新問題，自70年代關(guān)系數(shù)據(jù)庫誕生之后就一直伴隨著數(shù)據(jù)庫技術(shù)的發(fā)展，并且在分布式數(shù)據(jù)庫的場景下又遇到了一些新的問題。本文將會就事務(wù)故障恢復(fù)這個問題，分別講述單機數(shù)據(jù)庫、分布式數(shù)據(jù)庫中遇到的問題和幾種典型的解決方案，以及 OceanBase 在事務(wù)故障恢復(fù)方面的相關(guān)實踐。

一、從單機數(shù)據(jù)庫說起

大家都知道，數(shù)據(jù)庫中事務(wù)具有四大屬性：ACID，其中和事務(wù)故障恢復(fù)相關(guān)的屬性是 A 和 D：

• 原子性（Atomicity）：事務(wù)內(nèi)的修改要么都生效，要么都不生效；
• 持久性（Durability）：如果數(shù)據(jù)庫宕機，已經(jīng)完成提交的事務(wù)結(jié)果不應(yīng)該丟失

例如在如下圖所示的兩個事務(wù)執(zhí)行過程中：
?

在數(shù)據(jù)庫出現(xiàn)宕機時，Trx1 還沒有執(zhí)行完成，而 Trx2 已經(jīng)完成提交，原子性和持久性要求在宕機恢復(fù)后，Trx1 的所有修改都不生效，且 Trx2 的所有修改都必須被持久化。為了達到這個要求，數(shù)據(jù)庫必須在宕機重啟后執(zhí)行兩個動作：

• 回滾：移除所有未完成以及回滾事務(wù)的修改；
• 重做：重新執(zhí)行已經(jīng)完成提交的事務(wù)的修改，確保持久性；

1.1 Shadow Paging

一種比較簡單的保證事務(wù)原子性和持久性的方法是 Shadow Paging。這個方法非常容易理解，數(shù)據(jù)庫維護兩個獨立的數(shù)據(jù)“版本”，分別稱為 master 和 shadow 版本，寫事務(wù)的所有修改操作寫入在 shadow 版本上（其他事務(wù)讀取僅讀取 master 版本，shadow 版本對讀取不可見），當(dāng)寫事務(wù)提交時，需要在完成提交前將 shadow 版本切換為 master 版本。
?

當(dāng)數(shù)據(jù)庫發(fā)生宕機重啟時，并不需要做對應(yīng)的回滾和重做操作（僅回收可能殘留的 shadow 版本數(shù)據(jù)即可）。
LMDB（Lightning Memory-Mapped Database） 就是一個真正應(yīng)用了 Shadow Paging 方法的數(shù)據(jù)庫例子。LMDB 是一個基于內(nèi)存文件映射的 KV 數(shù)據(jù)庫，事務(wù)修改時采用 Copy-on-write 的方式對 B+tree 索引結(jié)構(gòu)進行修改，當(dāng)寫事務(wù)在修改數(shù)據(jù)時，會對修改部分 Copy 出新的 B+tree，并在事務(wù)提交前，將新的根節(jié)點落盤，讀取事務(wù)總是從當(dāng)前生效的最新根節(jié)點開始執(zhí)行。
?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-769910.html

1.2 數(shù)據(jù)落盤策略

回顧前文，在宕機重啟時，必須要執(zhí)行回滾和重做兩個操作?；貪L的目的是消除磁盤上存在的未提交事務(wù)的修改，但 Shadow Paging 方法在事務(wù)提交前并不會修改 master 版本，所以無需執(zhí)行回滾操作；重做的目的是將已經(jīng)提交但是沒有完成落盤的事務(wù)修改恢復(fù)出來，但 Shadow Paging 方法在事務(wù)提交前一定已經(jīng)將所有修改完成落盤并修改 master 版本，所以也無需執(zhí)行重做操作。
由此可以看出，事務(wù)故障恢復(fù)所需要執(zhí)行的操作和事務(wù)執(zhí)行過程中數(shù)據(jù)落盤的策略是相關(guān)的。
?

數(shù)據(jù)庫領(lǐng)域中將事務(wù)執(zhí)行過程中數(shù)據(jù)落盤的策略歸納描述為兩點：

• Steal/No-Steal：指事務(wù)在執(zhí)行過程中是否允許未提交的事務(wù)修改磁盤上的最新數(shù)據(jù)；
• Force/No-Force：指事務(wù)在提交前是否要求將所有修改落盤；

實現(xiàn)了 Steal 屬性的數(shù)據(jù)庫系統(tǒng)，需要在宕機重啟后做回滾操作以消除未提交事務(wù)的修改；實現(xiàn) No-Force 的數(shù)據(jù)庫系統(tǒng)，需要宕機重啟對已提交事務(wù)做重做操作來恢復(fù)出未落盤的修改。
Shadow Paging 屬于 No-Steal & Force 的系統(tǒng)，所以宕機恢復(fù)的過程非常簡單。但是宕機恢復(fù)過程的簡單是以運行時的復(fù)雜為代價的，No-Steal 要求事務(wù)在提交前都不能落盤，對大事務(wù)不友好；Force 在事務(wù)提交時增加了寫盤壓力和延時。通常來說，Steal & No-Force 對注重運行時表現(xiàn)的系統(tǒng)是比較理想的。

1.3 Logging

那么如何實現(xiàn)一個滿足 Steal & No-Force 的數(shù)據(jù)庫系統(tǒng)呢？接下來我們分析幾種基于日志的實現(xiàn)方法。

1.3.1 Redo 日志

如果在事務(wù)修改過程中生成 Redo（記錄修改后的新值）日志，則在宕機重啟后，系統(tǒng)可以通過回放 Redo 日志進行已提交事務(wù)的重做過程，但是無法做到未提交事務(wù)的回滾，因此，采用 Redo 日志的系統(tǒng)規(guī)則如下：

• 對于每一次修改，產(chǎn)生 Redo 日志記錄（包含修改后的新值）；
• 事務(wù) Commit 前（Commit 日志落盤），事務(wù)的所有修改不能落盤（No-Steal）；
• 事務(wù)提交成功前，事務(wù)的所有日志記錄（非數(shù)據(jù)）必須先落盤 （No-Force）；

RocksDB 是一個典型的使用 Redo 日志的例子（暫不討論 WriteUnprepared），事務(wù)的寫入在提交前不能落盤，緩存在內(nèi)存中事務(wù)專屬的 WriteBatch中，當(dāng)事務(wù)確定提交時，首先生成所有修改的 Redo 日志并落盤，然后才能將 WriteBatch 中的數(shù)據(jù)寫入到 memtable 中。
?

Redo 日志屬于 No-Steal & No-Force 的系統(tǒng)，如前文所述，No-Steal 意味著對大事務(wù)運行不友好。

1.3.2 Undo/Redo 日志

如果在事務(wù)修改過程中同時記錄修改前的舊值作為 Undo 日志（實現(xiàn)中并不一定采用日志形式），在宕機重啟后，系統(tǒng)就擁有了回滾未提交事務(wù)的能力，這種做法稱為 Undo/Redo 日志：

• 對每一次修改，產(chǎn)生日志同時記錄舊值和新值；
• 未提交事務(wù)允許落盤，在修改落盤之前，對應(yīng)的日志記錄必須先落盤（Steal）；
• 事務(wù)提交成功前，事務(wù)的所有日志記錄（非數(shù)據(jù)）必須先落盤 （No-Force）；

大名鼎鼎的 Oracle 數(shù)據(jù)庫就是采用這種模式，事務(wù)的每一次修改都會產(chǎn)生對應(yīng)的 undo record（記錄在 undo block 中）和 redo record，并且在刷臟頁之前，保證臟頁上對應(yīng)的未落盤事務(wù)日志必須先落盤；在事務(wù) commit 前，要保證事務(wù)的所有日志落盤完成。
?

Undo/Redo 日志屬于 Steal & No-Force 系統(tǒng)，目前絕大多數(shù)流行的關(guān)系數(shù)據(jù)庫系統(tǒng)都采用了這樣的思路，例如 Oracle、MySQL、PostgreSQL 等。

1.3.3 日志回收

任何基于日志的系統(tǒng)都會遇到日志回收的問題。雖然我們可以保留所有日志來滿足事務(wù)故障恢復(fù)的需求，但是日志空間不能無限的膨脹下去，并且如果在宕機重啟時總是從整個數(shù)據(jù)庫的第一條日志開始重做，宕機恢復(fù)的速度也無法滿足系統(tǒng)要求。因此，我們需要一種手段來盡可能的減少宕機恢復(fù)依賴的日志數(shù)量，這個手段就是Checkpoint。

一種最為簡單的 Checkpoint 方法流程如下：

• 停止所有事務(wù)執(zhí)行（暫停新開啟事務(wù)并結(jié)束運行中的事務(wù)）；
• 將當(dāng)前內(nèi)存中所有未落盤的修改落盤；
• 記錄當(dāng)前點為一次生效的 checkpoint；
• 恢復(fù)事務(wù)執(zhí)行；

這個方法的正確性也很容易理解，因為在第二步之后，磁盤上已經(jīng)有了完整的數(shù)據(jù)，不再需要任何日志。但這個方法的問題也很明顯，就是要停止所有事務(wù)執(zhí)行，這幾乎是無法接受的。

有很多不同的 Checkpoint 方法可以避免這個問題，我們以 Oracle 中的 Media recovery checkpoint 舉例，其過程為：

• 取當(dāng)前 SCN（Redo point）；
• 通知 dbwr 將當(dāng)前所有臟頁落盤；
• 完成后將 SCN 作為 checkpoint 點更新到元信息中；
  ?

整個過程中不影響正常事務(wù)的執(zhí)行，其正確性的關(guān)鍵在于完成臟頁落盤后，Redo point 前日志對應(yīng)的修改都完全落盤了，不再需要依賴日志回放來進行故障恢復(fù)。

二、分布式數(shù)據(jù)庫帶來的問題

在分布式數(shù)據(jù)庫中，事務(wù)故障恢復(fù)的目的仍然是要保證事務(wù)的原子性和持久性。和單機數(shù)據(jù)庫的不同在于，在分布式數(shù)據(jù)庫中，數(shù)據(jù)的修改位于不同的節(jié)點。
?

比如在這個例子中，事務(wù)的修改涉及到3個不同的節(jié)點，當(dāng)事務(wù)要提交時，必須保證3個節(jié)點上的數(shù)據(jù)同時提交，而不能部分提交、部分回滾。

2.1 Saga

Saga 是1887年提出的一種把長事務(wù)拆小并保證整體事務(wù)原子性的方法，也可以用來解決分布式事務(wù)的問題。其核心思路是對每個子事務(wù)產(chǎn)生對應(yīng)的“補償事務(wù)”，當(dāng)分布式事務(wù)整體提交時，依次提交各個節(jié)點上的子事務(wù)，如果過程中遭遇失敗，則對已經(jīng)提交的節(jié)點上的子事務(wù)執(zhí)行補償事務(wù)回滾已提交的修改。
?

如上圖例中，事務(wù)在3個節(jié)點上各自產(chǎn)生一個子事務(wù)，在分布式事務(wù)提交時提交各個子事務(wù)，在第3個節(jié)點上提交子事務(wù)失敗，需要對另外兩個成功提交的子事務(wù)執(zhí)行補償事務(wù)完成回滾操作。
這種方法的優(yōu)點在于正常提交流程處理簡單，而缺點在于補償回滾過程邏輯處理復(fù)雜。

2.2 兩階段提交

兩階段提交可能是最為知名的分布式事務(wù)原子性解決方案了。兩階段提交，顧名思義，整個事務(wù)提交流程分為兩階段來執(zhí)行：

• Prepare：協(xié)調(diào)者通知參與者 Prepare，參與者寫 Prepare 日志成功后回復(fù)協(xié)調(diào)者 Prepare ok；
• Commit：協(xié)調(diào)者收到所有參與者 Prepare 成功應(yīng)答后通知參與者 Commit；

每個節(jié)點都需要將每個階段的結(jié)果記錄在持久化的日志中，用以恢復(fù)自身狀態(tài)。
?

協(xié)議流程本身很簡單，兩階段提交協(xié)議的核心在于協(xié)議應(yīng)對宕機時的處理：當(dāng)參與者發(fā)生宕機時，如果參與者還沒有回復(fù)過協(xié)調(diào)者 Prepare ok，則協(xié)調(diào)者假定參與者決定回滾；當(dāng)協(xié)調(diào)者發(fā)生宕機時，參與者會按照自己的狀態(tài)決定下一步動作。
?

上圖是兩階段提交參與者的狀態(tài)機，如果參與者已經(jīng)回復(fù)過 Prepare ok（處于 Prepared 狀態(tài)），則參與者必須依賴協(xié)調(diào)者的消息通知才能決定最終事務(wù)狀態(tài)，我們稱參與者的這個狀態(tài)為“事務(wù)未決”。如果此時協(xié)調(diào)者發(fā)生宕機，則兩階段提交流程會阻塞。這也是所有應(yīng)用兩階段提交協(xié)議的系統(tǒng)所必須要解決的問題。
應(yīng)用兩階段提交協(xié)議的系統(tǒng)很多，我們以 PG-XC 為例，PG-XC 的數(shù)據(jù)存儲在不同的 Data Node 上，在分布式事務(wù)提交時，通過 Coordinator 執(zhí)行兩階段提交協(xié)議保證多個 Data Node 上事務(wù)修改的原子性。
?

另外，近幾年比較流行的 Percolator 協(xié)議，可以看做是兩階段提交協(xié)議的變種（Percolator 包含了一套完整的分布式事務(wù)解決方案，本文聚焦在其中事務(wù)原子性的部分）。Percolator 是 Google 提出的，在僅支持行級事務(wù)的Bigtable 基礎(chǔ)上將單行事務(wù)“組合”成多行事務(wù)的方案。

當(dāng)多行事務(wù)發(fā)起提交時：

• 選定其中一行作為"Primary record"，將該行寫入到 Bigtable 中，Primary record 上會記錄整個事務(wù)的狀態(tài)，此時為未提交狀態(tài)；
• 將其他行作為“Secondary record”分別寫入到 Bigtable 中，其中都包含了 Primary record 的位置信息，通過查詢 Primary record 上的事務(wù)狀態(tài)來決定自身狀態(tài)；
• 修改 Primary record 上的事務(wù)狀態(tài)為已提交；
• 異步清理 Secondary record 上的狀態(tài)；
  ?

從兩階段提交協(xié)議的角度分析 Percolator，其每行上的事務(wù)都是整個分布式事務(wù)的參與者，Primary record 相當(dāng)于協(xié)調(diào)者，當(dāng)所有參與者都持久化成功后，修改 Primary record 上事務(wù)狀態(tài)的過程也就等價于協(xié)調(diào)者寫的 commit 日志。

三、OceanBase 事務(wù)故障恢復(fù)

OceanBase 采用 share-nothing 架構(gòu)，數(shù)據(jù)按照分片規(guī)則分布在各個節(jié)點上，每個節(jié)點均有自己的存儲引擎，各自管理不同的數(shù)據(jù)分區(qū)，每個分區(qū)通過 Paxos 同步日志實現(xiàn)高可用，當(dāng)事務(wù)操作一個單獨的數(shù)據(jù)分片時，執(zhí)行的是單機事務(wù)，當(dāng)事務(wù)操作不同數(shù)據(jù)分片時，執(zhí)行的是分布式事務(wù)，會遇到分布式事務(wù)的原子性問題。

3.1 單機事務(wù)故障恢復(fù)

OceanBase 采用基于 MVCC 的事務(wù)并發(fā)控制，這意味著事務(wù)修改會保留多個數(shù)據(jù)版本，并且單個數(shù)據(jù)分片上的存儲引擎基于 LSM-tree 結(jié)構(gòu)，會定期進行轉(zhuǎn)儲（compaction）操作。

如下圖所示，事務(wù)的修改會以新版本數(shù)據(jù)的形式寫入到內(nèi)存中最新的活躍 memtable 上，當(dāng) memtable 內(nèi)存使用達到一定量時，memtable 凍結(jié)并生成新的活躍 memtable，被凍結(jié)的 memtable 會執(zhí)行轉(zhuǎn)儲轉(zhuǎn)變?yōu)榇疟P上的 sstable。數(shù)據(jù)的讀取通過讀取所有的 sstable 和 memtable 上的多版本進行合并來得到所需要的版本數(shù)據(jù)。
?

單機事務(wù)故障恢復(fù)采用了 Undo/Redo 日志的思路實現(xiàn)。事務(wù)在寫入時會生成 Redo 日志，借助 MVCC 機制的舊版本數(shù)據(jù)作為 Undo 信息，實現(xiàn)了 Steal & No-Force 的數(shù)據(jù)落盤策略。在事務(wù)宕機恢復(fù)過程中，通過 Redo日志進行重做恢復(fù)出已提交未落盤的事務(wù)，并通過恢復(fù)保存的舊版本數(shù)據(jù)來回滾已經(jīng)落盤的未提交事務(wù)修改。

3.2 分布式事務(wù)故障恢復(fù)

當(dāng)事務(wù)操作多個數(shù)據(jù)分片時，OceanBase 通過兩階段提交來保證分布式事務(wù)的原子性。

?

如上圖所示，當(dāng)分布式事務(wù)提交時，會選擇其中的一個數(shù)據(jù)分片作為協(xié)調(diào)者在所有數(shù)據(jù)分片上執(zhí)行兩階段提交協(xié)議。還記得前文提到過的協(xié)調(diào)者宕機問題么？在 OceanBase 中，由于所有數(shù)據(jù)分片都是通過 Paxos 復(fù)制日志實現(xiàn)多副本高可用的，當(dāng)主副本發(fā)生宕機后，會由同一數(shù)據(jù)分片的備副本轉(zhuǎn)換為新的主副本繼續(xù)提供服務(wù)，所以可以認(rèn)為在 OceanBase 中，參與者和協(xié)調(diào)者都是保證高可用不宕機的（多數(shù)派存活），繞開了協(xié)調(diào)者宕機的問題。
在參與者高可用的實現(xiàn)前提下，OceanBase 對協(xié)調(diào)者進行了“無狀態(tài)”的優(yōu)化。在標(biāo)準(zhǔn)的兩階段提交中，協(xié)調(diào)者要通過記錄日志的方法持久化自己的狀態(tài)，否則如果協(xié)調(diào)者和參與者同時宕機，協(xié)調(diào)者恢復(fù)后可能會導(dǎo)致事務(wù)提交狀態(tài)不一致。但是如果我們認(rèn)為參與者不會宕機，那么協(xié)調(diào)者并不需要寫日志記錄自己的狀態(tài)。
?

上圖是兩階段提交協(xié)議協(xié)調(diào)者的狀態(tài)機，在協(xié)調(diào)者不寫日志的前提下，協(xié)調(diào)者如果發(fā)生切主或宕機恢復(fù)，它并不知道自己之前的狀態(tài)是 Abort 還是 Commit。那么，協(xié)調(diào)者可以通過詢問參與者來恢復(fù)自己的狀態(tài)，因為參與者是高可用的，所以一定可以恢復(fù)出整個分布式事務(wù)的狀態(tài)。
除此之外，OceanBase 還對兩階段提交協(xié)議的時延進行了優(yōu)化，將事務(wù)提交回應(yīng)客戶端的時機提前到 Prepare 階段完成后（標(biāo)準(zhǔn)兩階段提交協(xié)議中為 Commit 階段完成后）。
?

在上圖中（綠色部分表示寫日志的動作），左側(cè)為標(biāo)準(zhǔn)兩階段提交協(xié)議，用戶感知到的提交時延是4次寫日志耗時以及2次 RPC 的往返耗時；右側(cè)圖中 OceanBase 的兩階段提交實現(xiàn)，由于少了協(xié)調(diào)者的寫日志耗時以及提前了應(yīng)答客戶端的時機，用戶感知到的提交時延是1次寫日志耗時以及1次 RPC 的往返耗時。

四、總結(jié)

關(guān)系數(shù)據(jù)庫領(lǐng)域雖然歷史悠久，但是仍然充滿了活力。這些年來，隨著硬件的發(fā)展，新的技術(shù)和思路也不斷的涌現(xiàn)出來，從本文描述的單機數(shù)據(jù)庫到分布式數(shù)據(jù)庫中事務(wù)故障恢復(fù)的的方案，相信大家也都能感受到這些年來數(shù)據(jù)庫技術(shù)的發(fā)展是如何一步步適應(yīng)著硬件的發(fā)展趨勢。未來又會怎樣？更大的內(nèi)存、更快速的網(wǎng)絡(luò)、更廉價的硬盤、甚至是非易失性內(nèi)存的普及，這些變化會給數(shù)據(jù)庫技術(shù)帶來怎樣的可能性？讓我們一起拭目以待。（迫不及待的同學(xué)，歡迎加入 OceanBase 團隊，一起創(chuàng)造數(shù)據(jù)庫技術(shù)的未來！）
?

?

到了這里，關(guān)于分布式數(shù)據(jù)庫事務(wù)故障恢復(fù)的原理與實踐的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！