本文根據 OceanBaseDev Meetup#1 上海站分享整理，本次活動針對分布式資料庫的分布式事務以及落地實踐展開具體分享。
本期分享視訊以及 PPT 檢視位址見文末。
本文作者：孔繁宇（景嚴），螞蟻集團技術專家，2016年加入 OceanBase 事務組，參與了 OceanBase 1.0 及 OceanBase 2.0 版本的設計開發工作，目前主要負責 OceanBase 資料轉儲和當機恢複相關的工作。
關系資料庫中的事務故障恢複并不是一個新問題，自70年代關系資料庫誕生之後就一直伴随着資料庫技術的發展，并且在分布式資料庫的場景下又遇到了一些新的問題。本文将會就事務故障恢複這個問題，分别講述單機資料庫、分布式資料庫中遇到的問題和幾種典型的解決方案，以及 OceanBase 在事務故障恢複方面的相關實踐。
從單機資料庫說起
大家都知道，資料庫中事務具有四大屬性：ACID，其中和事務故障恢複相關的屬性是 A 和 D：
原子性（Atomicity）：事務内的修改要麼都生效，要麼都不生效；
持久性（Durability）：如果資料庫當機，已經完成送出的事務結果不應該丢失；
例如在如下圖所示的兩個事務執行過程中：
在資料庫出現當機時，Trx1 還沒有執行完成，而 Trx2 已經完成送出，原子性和持久性要求在當機恢複後，Trx1 的所有修改都不生效，且 Trx2 的所有修改都必須被持久化。為了達到這個要求，資料庫必須在當機重新開機後執行兩個動作：
復原：移除所有未完成以及復原事務的修改；
重做：重新執行已經完成送出的事務的修改，確定持久性；
Shadow Paging
一種比較簡單的保證事務原子性和持久性的方法是 Shadow Paging。這個方法非常容易了解，資料庫維護兩個獨立的資料“版本”，分别稱為 master 和 shadow 版本，寫事務的所有修改操作寫入在 shadow 版本上（其他事務讀取僅讀取 master 版本，shadow 版本對讀取不可見），當寫事務送出時，需要在完成送出前将 shadow 版本切換為 master 版本。
當資料庫發生當機重新開機時，并不需要做對應的復原和重做操作（僅回收可能殘留的 shadow 版本資料即可）。
LMDB（Lightning Memory-Mapped Database） 就是一個真正應用了 Shadow Paging 方法的資料庫例子。LMDB 是一個基于記憶體檔案映射的 KV 資料庫，事務修改時采用 Copy-on-write 的方式對 B+tree 索引結構進行修改，當寫事務在修改資料時，會對修改部分 Copy 出新的 B+tree，并在事務送出前，将新的根節點落盤，讀取事務總是從目前生效的最新根節點開始執行。
資料落盤政策
回顧前文，在當機重新開機時，必須要執行復原和重做兩個操作。復原的目的是消除磁盤上存在的未送出事務的修改，但 Shadow Paging 方法在事務送出前并不會修改 master 版本，是以無需執行復原操作；重做的目的是将已經送出但是沒有完成落盤的事務修改恢複出來，但 Shadow Paging 方法在事務送出前一定已經将所有修改完成落盤并修改 master 版本，是以也無需執行重做操作。
由此可以看出，事務故障恢複所需要執行的操作和事務執行過程中資料落盤的政策是相關的。
資料庫領域中将事務執行過程中資料落盤的政策歸納描述為兩點：
Steal/No-Steal：指事務在執行過程中是否允許未送出的事務修改磁盤上的最新資料；
Force/No-Force：指事務在送出前是否要求将所有修改落盤；
實作了 Steal 屬性的資料庫系統，需要在當機重新開機後做復原操作以消除未送出事務的修改；實作 No-Force 的資料庫系統，需要當機重新開機對已送出事務做重做操作來恢複出未落盤的修改。
Shadow Paging 屬于 No-Steal & Force 的系統，是以當機恢複的過程非常簡單。但是當機恢複過程的簡單是以運作時的複雜為代價的，No-Steal 要求事務在送出前都不能落盤，對大事務不友好；Force 在事務送出時增加了寫盤壓力和延時。通常來說，Steal & No-Force 對注重運作時表現的系統是比較理想的。
Logging
那麼如何實作一個滿足 Steal & No-Force 的資料庫系統呢？接下來我們分析幾種基于日志的實作方法。
Redo 日志
如果在事務修改過程中生成 Redo（記錄修改後的新值）日志，則在當機重新開機後，系統可以通過回放 Redo 日志進行已送出事務的重做過程，但是無法做到未送出事務的復原，是以，采用 Redo 日志的系統規則如下：
對于每一次修改，産生 Redo 日志記錄（包含修改後的新值）；
事務 Commit 前（Commit 日志落盤），事務的所有修改不能落盤（No-Steal）；
事務送出成功前，事務的所有日志記錄（非資料）必須先落盤 （No-Force）；
RocksDB 是一個典型的使用 Redo 日志的例子（暫不讨論 WriteUnprepared），事務的寫入在送出前不能落盤，緩存在記憶體中事務專屬的 WriteBatch中，當事務确定送出時，首先生成所有修改的 Redo 日志并落盤，然後才能将 WriteBatch 中的資料寫入到 memtable 中。
Redo 日志屬于 No-Steal & No-Force 的系統，如前文所述，No-Steal 意味着對大事務運作不友好。
Undo/Redo 日志
如果在事務修改過程中同時記錄修改前的舊值作為 Undo 日志（實作中并不一定采用日志形式），在當機重新開機後，系統就擁有了復原未送出事務的能力，這種做法稱為 Undo/Redo 日志：
對每一次修改，産生日志同時記錄舊值和新值；
未送出事務允許落盤，在修改落盤之前，對應的日志記錄必須先落盤（Steal）；
大名鼎鼎的 Oracle 資料庫就是采用這種模式，事務的每一次修改都會産生對應的 undo record（記錄在 undo block 中）和 redo record，并且在刷髒頁之前，保證髒頁上對應的未落盤事務日志必須先落盤；在事務 commit 前，要保證事務的所有日志落盤完成。
Undo/Redo 日志屬于 Steal & No-Force 系統，目前絕大多數流行的關系資料庫系統都采用了這樣的思路，例如 Oracle、MySQL、PostgreSQL 等。
日志回收
任何基于日志的系統都會遇到日志回收的問題。雖然我們可以保留所有日志來滿足事務故障恢複的需求，但是日志空間不能無限的膨脹下去，并且如果在當機重新開機時總是從整個資料庫的第一條日志開始重做，當機恢複的速度也無法滿足系統要求。是以，我們需要一種手段來盡可能的減少當機恢複依賴的日志數量，這個手段就是 Checkpoint。
一種最為簡單的 Checkpoint 方法流程如下：
停止所有事務執行（暫停新開啟事務并結束運作中的事務）；
将目前記憶體中所有未落盤的修改落盤；
記錄目前點為一次生效的 checkpoint；
恢複事務執行；
這個方法的正确性也很容易了解，因為在第二步之後，磁盤上已經有了完整的資料，不再需要任何日志。但這個方法的問題也很明顯，就是要停止所有事務執行，這幾乎是無法接受的。
有很多不同的 Checkpoint 方法可以避免這個問題，我們以 Oracle 中的 Media recovery checkpoint 舉例，其過程為：
取目前 SCN（Redo point）；
通知 dbwr 将目前所有髒頁落盤；
完成後将 SCN 作為 checkpoint 點更新到元資訊中；
整個過程中不影響正常事務的執行，其正确性的關鍵在于完成髒頁落盤後，Redo point 前日志對應的修改都完全落盤了，不再需要依賴日志回放來進行故障恢複。
分布式資料庫帶來的問題
在分布式資料庫中，事務故障恢複的目的仍然是要保證事務的原子性和持久性。和單機資料庫的不同在于，在分布式資料庫中，資料的修改位于不同的節點。
比如在這個例子中，事務的修改涉及到3個不同的節點，當事務要送出時，必須保證3個節點上的資料同時送出，而不能部分送出、部分復原。
Saga
Saga 是1887年提出的一種把長事務拆小并保證整體事務原子性的方法，也可以用來解決分布式事務的問題。其核心思路是對每個子事務産生對應的“補償事務”，當分布式事務整體送出時，依次送出各個節點上的子事務，如果過程中遭遇失敗，則對已經送出的節點上的子事務執行補償事務復原已送出的修改。
如上圖例中，事務在3個節點上各自産生一個子事務，在分布式事務送出時送出各個子事務，在第3個節點上送出子事務失敗，需要對另外兩個成功送出的子事務執行補償事務完成復原操作。
這種方法的優點在于正常送出流程處理簡單，而缺點在于補償復原過程邏輯處理複雜。
兩階段送出
兩階段送出可能是最為知名的分布式事務原子性解決方案了。兩階段送出，顧名思義，整個事務送出流程分為兩階段來執行：
Prepare：協調者通知參與者 Prepare，參與者寫 Prepare 日志成功後回複協調者 Prepare ok；
Commit：協調者收到所有參與者 Prepare 成功應答後通知參與者 Commit；
每個節點都需要将每個階段的結果記錄在持久化的日志中，用以恢複自身狀态。
協定流程本身很簡單，兩階段送出協定的核心在于協定應對當機時的處理：當參與者發生當機時，如果參與者還沒有回複過協調者 Prepare ok，則協調者假定參與者決定復原；當協調者發生當機時，參與者會按照自己的狀态決定下一步動作。
上圖是兩階段送出參與者的狀态機，如果參與者已經回複過 Prepare ok（處于 Prepared 狀态），則參與者必須依賴協調者的消息通知才能決定最終事務狀态，我們稱參與者的這個狀态為“事務未決”。如果此時協調者發生當機，則兩階段送出流程會阻塞。這也是所有應用兩階段送出協定的系統所必須要解決的問題。
應用兩階段送出協定的系統很多，我們以 PG-XC 為例，PG-XC 的資料存儲在不同的 Data Node 上，在分布式事務送出時，通過 Coordinator 執行兩階段送出協定保證多個 Data Node 上事務修改的原子性。
另外，近幾年比較流行的 Percolator 協定，可以看做是兩階段送出協定的變種（Percolator 包含了一套完整的分布式事務解決方案，本文聚焦在其中事務原子性的部分）。Percolator 是 Google 提出的，在僅支援行級事務的 Bigtable 基礎上将單行事務“組合”成多行事務的方案。
當多行事務發起送出時：
標明其中一行作為"Primary record"，将該行寫入到 Bigtable 中，Primary record 上會記錄整個事務的狀态，此時為未送出狀态；
将其他行作為“Secondary record”分别寫入到 Bigtable 中，其中都包含了 Primary record 的位置資訊，通過查詢 Primary record 上的事務狀态來決定自身狀态；
修改 Primary record 上的事務狀态為已送出；
異步清理 Secondary record 上的狀态；
從兩階段送出協定的角度分析 Percolator，其每行上的事務都是整個分布式事務的參與者，Primary record 相當于協調者，當所有參與者都持久化成功後，修改 Primary record 上事務狀态的過程也就等價于協調者寫的 commit 日志。
OceanBase 事務故障恢複
OceanBase 采用 share-nothing 架構，資料按照分片規則分布在各個節點上，每個節點均有自己的存儲引擎，各自管理不同的資料分區，每個分區通過 Paxos 同步日志實作高可用，當事務操作一個單獨的資料分片時，執行的是單機事務，當事務操作不同資料分片時，執行的是分布式事務，會遇到分布式事務的原子性問題。
單機事務故障恢複
OceanBase 采用基于 MVCC 的事務并發控制，這意味着事務修改會保留多個資料版本，并且單個資料分片上的存儲引擎基于 LSM-tree 結構，會定期進行轉儲（compaction）操作。
如下圖所示，事務的修改會以新版本資料的形式寫入到記憶體中最新的活躍 memtable 上，當 memtable 記憶體使用達到一定量時，memtable 當機并生成新的活躍 memtable，被當機的 memtable 會執行轉儲轉變為磁盤上的 sstable。資料的讀取通過讀取所有的 sstable 和 memtable 上的多版本進行合并來得到所需要的版本資料。
單機事務故障恢複采用了 Undo/Redo 日志的思路實作。事務在寫入時會生成 Redo 日志，借助 MVCC 機制的舊版本資料作為 Undo 資訊，實作了 Steal & No-Force 的資料落盤政策。在事務當機恢複過程中，通過 Redo日志進行重做恢複出已送出未落盤的事務，并通過恢複儲存的舊版本資料來復原已經落盤的未送出事務修改。
分布式事務故障恢複
當事務操作多個資料分片時，OceanBase 通過兩階段送出來保證分布式事務的原子性。
如上圖所示，當分布式事務送出時，會選擇其中的一個資料分片作為協調者在所有資料分片上執行兩階段送出協定。還記得前文提到過的協調者當機問題麼？在 OceanBase 中，由于所有資料分片都是通過 Paxos 複制日志實作多副本高可用的，當主副本發生當機後，會由同一資料分片的備副本轉換為新的主副本繼續提供服務，是以可以認為在 OceanBase 中，參與者和協調者都是保證高可用不當機的（多數派存活），繞開了協調者當機的問題。
在參與者高可用的實作前提下，OceanBase 對協調者進行了“無狀态”的優化。在标準的兩階段送出中，協調者要通過記錄日志的方法持久化自己的狀态，否則如果協調者和參與者同時當機，協調者恢複後可能會導緻事務送出狀态不一緻。但是如果我們認為參與者不會當機，那麼協調者并不需要寫日志記錄自己的狀态。
上圖是兩階段送出協定協調者的狀态機，在協調者不寫日志的前提下，協調者如果發生切主或當機恢複，它并不知道自己之前的狀态是 Abort 還是 Commit。那麼，協調者可以通過詢問參與者來恢複自己的狀态，因為參與者是高可用的，是以一定可以恢複出整個分布式事務的狀态。
除此之外，OceanBase 還對兩階段送出協定的時延進行了優化，将事務送出回應用戶端的時機提前到 Prepare 階段完成後（标準兩階段送出協定中為 Commit 階段完成後）。
在上圖中（綠色部分表示寫日志的動作），左側為标準兩階段送出協定，使用者感覺到的送出時延是4次寫日志耗時以及2次 RPC 的往返耗時；右側圖中 OceanBase 的兩階段送出實作，由于少了協調者的寫日志耗時以及提前了應答用戶端的時機，使用者感覺到的送出時延是1次寫日志耗時以及1次 RPC 的往返耗時。
總結
關系資料庫領域雖然曆史悠久，但是仍然充滿了活力。這些年來，随着硬體的發展，新的技術和思路也不斷的湧現出來，從本文描述的單機資料庫到分布式資料庫中事務故障恢複的的方案，相信大家也都能感受到這些年來資料庫技術的發展是如何一步步适應着硬體的發展趨勢。未來又會怎樣？更大的記憶體、更快速的網絡、更廉價的硬碟、甚至是非易失性記憶體的普及，這些變化會給資料庫技術帶來怎樣的可能性？讓我們一起拭目以待。（迫不及待的同學，歡迎加入 OceanBase 團隊，一起創造資料庫技術的未來！）
回顧資料
關于本次分享歡迎留下您的建議：
http://oceanbasedev.mikecrm.com/w77l9yx視訊回顧：
https://www.bilibili.com/video/BV1Rk4y1k7VfPPT 檢視位址：
https://tech.antfin.com/community/activities/1283/review/1011OceanBaseDev Meetup 是以城市站展開的資料庫技術交流活動，旨在為關注分布式資料庫技術的同學提供技術交流、分享、探讨的空間與平台。如果你相信「分布式」是未來，如果你覺得「資料庫」也很酷，歡迎加入 OceanBase Developer 社群，與志趣相投的朋友一起做點有意思的事。