本文試圖討論這幾個(gè)問題：

• MySQL的redo log和binlog為什么要用XA?
• MongoDB的oplog是按照什么順序復(fù)制?
• Raft真的只能串行Apply嗎?
• 數(shù)據(jù)庫的復(fù)制和事務(wù)是完全獨(dú)立的兩回事?
• 為什么MySQL不早點(diǎn)做一個(gè)Raft插件，直接用Raft實(shí)現(xiàn)高可用?

本文旨在闡述Fault-Tolerant Transaction的幾種實(shí)現(xiàn)模式。雖然乍一看它們可能都是Raft+KVEngine +Concurrency Control，容易被認(rèn)為是同一類方法，但實(shí)際上的差異很大，在討論時(shí)不應(yīng)該忽視它們之間的差異。

一、基本概念

討論的Fault-Tolerance，指的是通過網(wǎng)絡(luò)通信的多個(gè)計(jì)算機(jī)節(jié)點(diǎn)，在部分節(jié)點(diǎn)發(fā)生Stop Failure的情況下，仍然盡力保證可用性;

不討論具體的Fault-Tolerance方法，默認(rèn)讀者對(duì)Raft等算法有基本理解;

也不討論具體的Concurrency Control方法，默認(rèn)讀者對(duì)其有基本的理解;

會(huì)涉及到Spanner、TiKV、MongoDB等具體的數(shù)據(jù)庫。

1、基于RSM的Fault-Tolerant KV

Replicated State Machine最早應(yīng)該是在『Implementing fault-tolerant services using the state machine approach』提出。它是一種很簡單實(shí)用的實(shí)現(xiàn)容錯(cuò)的方法，核心思想是：幾個(gè)狀態(tài)機(jī)具有相同的初始狀態(tài)，并且按照同樣的順序執(zhí)行了同樣的命令序列，那么它們的最終狀態(tài)也是一樣的。由于狀態(tài)一樣，那么任意一個(gè)狀態(tài)機(jī)宕機(jī)，都可以被其他的代替，因此實(shí)現(xiàn)了Fault Tolerant。

這里提到了幾個(gè)概念，命令、執(zhí)行順序、狀態(tài)機(jī)，它們都是抽象概念，對(duì)應(yīng)到具體的應(yīng)用場景才有實(shí)際意義。在KVEngine的場景下，命令就是Put/Get等操作，狀態(tài)機(jī)就是KVEngine本身，而執(zhí)行序列，則由Replication Log決定。

既然提到了RSM和KV，那么基于RSM的KV也就呼之欲出了。把發(fā)到KVEngine的操作先用Raft復(fù)制一遍，在Apply的時(shí)候扔回到KVEngine執(zhí)行，于是我們就得到了一個(gè)Fault-Tolerant的KVEngine。

看起來很簡單，但我在這里顯然忽略了很多細(xì)節(jié)：

• 串行還是并行Apply：Raft被人詬病的一點(diǎn)是串行Commit、串行Apply，但這并不是Raft的鍋;
• 兩條Log：Raft復(fù)制需要一個(gè)Log，KVEngine也會(huì)有一個(gè)WAL，會(huì)帶來IO放大，能不能合并成一個(gè)呢?
• Checkpoint：為了加速Recovery，需要做Checkpoint;
• 只讀操作需要復(fù)制嗎?
• 命令可以是復(fù)合操作嗎：單行的CAS操作可以嗎，多行的事務(wù)操作可以作為一個(gè)命令嗎?

2、基于RSM的事務(wù)

我們來考慮***一個(gè)問題，RSM中的命令，可以直接是一個(gè)事務(wù)嗎?

既然Raft都是串行Apply了，那么看起來把事務(wù)的所有操作作為一個(gè)命令扔到狀態(tài)機(jī)執(zhí)行并沒有什么問題。

但問題在于，實(shí)際中的事務(wù)是交互式的，也就是包含了if-else等邏輯的，并且邏輯還可能依賴了數(shù)據(jù)庫系統(tǒng)外部的狀態(tài)，所以不能簡單地用Write Batch + Snapshot來實(shí)現(xiàn)一個(gè)事務(wù)，還是要有Concurrency Control的邏輯。

為了解決Concurrency Control的問題，我們?cè)赗aft Leader上，實(shí)現(xiàn)一個(gè)Lock Table和Transaction Manager。拿S2PL方法舉例：

• 讀數(shù)據(jù)之前加讀鎖，寫數(shù)據(jù)之前加寫鎖;讀操作通過Raft讀數(shù)據(jù)，寫操作Buffer在本地;
• 在用戶決定事務(wù)提交時(shí)，即可釋放讀鎖;通過Raft寫一條事務(wù)日志，包含所有寫操作;
• 在Raft Apply事務(wù)日志時(shí)，把寫操作應(yīng)用到KVEngine，并且釋放寫鎖。

這里舉的例子是S2PL，但對(duì)于其他的并發(fā)控制方法也基本通用。例如Snapshot Isolation，事務(wù)開始時(shí)獲得KV的Snapshot，讀操作都走Snapshot，寫操作獲得寫鎖，數(shù)據(jù)Buffer在本地，事務(wù)提交時(shí)檢查[begin, end]之間有沒有寫沖突，沒有的話則通過Raft寫事務(wù)日志，在Apply事務(wù)日志之后，把寫操作應(yīng)用到KVEngine，***釋放寫鎖。

這種方法接近Spanner的做法，它具有幾個(gè)特點(diǎn)：

• 只有Leader需要維護(hù)Lock Table、Transaction Manager，事務(wù)并發(fā)控制基本在Leader節(jié)點(diǎn)完成;
• 從RSM的角度來看，這里的Lock Table起到了命令定序的作用，保證所有State Machine按照同樣的順序執(zhí)行命令;
• 加鎖操作不走復(fù)制協(xié)議，解鎖操作在復(fù)制協(xié)議Apply之后完成，鎖會(huì)在復(fù)制的開始到Commit一直持有：也就意味著，復(fù)制協(xié)議的Commit即是事務(wù)的Commit，在Commit之前發(fā)生Failover，事務(wù)都會(huì)Abort;
• Raft所復(fù)制的，即是事務(wù)的REDO。

3、基于共享存儲(chǔ)的事務(wù)

重新看一下上面這個(gè)模型，復(fù)制協(xié)議所做的事情非常簡單，和其他模塊的耦合也很小，僅僅是維護(hù)一個(gè)有序的Log，因此，我們可以把它從share-nothing推廣到share-storage的模型中。

也就是說，我們把普通的單機(jī)事務(wù)引擎，放到一個(gè)高可用的存儲(chǔ)上，就得到了基本可用的Fault-Tolerant 事務(wù)引擎了，連復(fù)制協(xié)議也不需要實(shí)現(xiàn)的。

不過事情顯然不會(huì)這么簡單：

• 如何實(shí)現(xiàn)只讀節(jié)點(diǎn)，提供讀擴(kuò)展的能力;
• 計(jì)算節(jié)點(diǎn)如何更快地Failover;
• 如何把更多的操作下推到存儲(chǔ)節(jié)點(diǎn)。

4、基于高可用KV的事務(wù)

回到一開始的***種方案，在一個(gè)節(jié)點(diǎn)實(shí)現(xiàn)了KV、Raft、Lock Table、Transaction Manager，看起來耦合度比較大了，我們能不能對(duì)其進(jìn)行分層，進(jìn)一步簡化呢?例如Google的經(jīng)典做法，基于GFS實(shí)現(xiàn)Bigtable，基于Bigtable實(shí)現(xiàn)Percolator，Layered設(shè)計(jì)易于迭代、易于開發(fā)、易于調(diào)試。

因此我們可以考慮把KV層單獨(dú)抽離出來，基于KV去實(shí)現(xiàn)Lock Table、Txn Manager：

• Lock Table：在原本的KV中增加一列，變成Key => {Value, Lock};
• Txn Manager: 從事務(wù)修改的所有Key中選出一個(gè)Primary Key，用來記錄事務(wù)狀態(tài)，因此KV進(jìn)一步變成 Key => {Value, Lock, TxnStatus};
• MVCC：甚至我們不甘心于Single Version，還想用Multi Version的并發(fā)控制，那么KV就變成{Key, Version} => {Value, Lock, TxnStatus}。

看過Percolator、TiKV設(shè)計(jì)的應(yīng)該會(huì)比較熟悉，它們就是基于一個(gè)高可用的KV，把事務(wù)的狀態(tài)都下沉到KV中。這種設(shè)計(jì)很容易拓展到分布式事務(wù)的場景，如果KV能夠scale，那么上層的事務(wù)也能夠scale了。

5、基于單機(jī)事務(wù)引擎實(shí)現(xiàn)高可用事務(wù)

上面的方案看起來都比較簡單，不過有一個(gè)細(xì)節(jié)不容忽視：鎖基本都是在復(fù)制協(xié)議提交之后才會(huì)釋放，換句話說事務(wù)持有的鎖會(huì)從事務(wù)開始直到多個(gè)節(jié)點(diǎn)寫完日志，經(jīng)歷多次網(wǎng)絡(luò)延遲、IO延遲，并且在擁塞情況下會(huì)面臨排隊(duì)延遲的風(fēng)險(xiǎn)。而鎖意味著互斥，互斥意味著事務(wù)吞吐降低。

翻譯一下：

• 并發(fā)且有沖突的事務(wù)，其提交順序由Lock Table決定，并且和復(fù)制協(xié)議的Log順序一致;
• 事務(wù)的Serialization Order，和RSM 中的Order一致。

不過這里存在一個(gè)問題：

• 鎖一定要在復(fù)制協(xié)議提交之后才能釋放嗎?
• 提前釋放會(huì)破壞Order的一致性嗎?
• RSM的Order一定要和事務(wù)的Serialization Order一致嗎?

暫且不做回答，我們?cè)倏?**一種方案，基于單機(jī)事務(wù)引擎的高可用事務(wù)。

在正常的單機(jī)事務(wù)流程中，增加一個(gè)復(fù)制的環(huán)節(jié)：本地事務(wù)提交之后不是立即返回用戶，而是寫binlog，等待binlog復(fù)制到其他節(jié)點(diǎn)之后再返回用戶。

這種方式的事務(wù)延遲，看起來還是本地事務(wù)的延遲，加上復(fù)制日志的延遲;但相比于之前的方案，本地事務(wù)可以先提交，鎖可以提交釋放，總體的事務(wù)吞吐相比之下會(huì)有所提升。

看起來甚至比之前的方案更加簡單，事務(wù)和復(fù)制模塊得到了***的分離，但這里忽略了一個(gè)復(fù)雜的問題：

• 基于哪個(gè)日志來復(fù)制，基于數(shù)據(jù)庫的Journal，還是再寫一個(gè)binlog?
• 基于什么順序進(jìn)行復(fù)制，如果是基于Journal復(fù)制可以用Journal順序，如果基于binlog，順序又是什么?
• 如果有兩個(gè)日志，兩個(gè)日志其實(shí)意味著Transaction Serialization Order和RSM的State Machine Order不一樣，會(huì)不會(huì)產(chǎn)生事務(wù)的并發(fā)異常，或者導(dǎo)致State Machine不一致?

由于直接復(fù)制Journal會(huì)引起一系列復(fù)雜的耦合問題，大部分?jǐn)?shù)據(jù)庫都選擇單獨(dú)寫一個(gè)binlog/oplog來實(shí)現(xiàn)復(fù)制，不過在實(shí)現(xiàn)時(shí)可以做優(yōu)化，因?yàn)槿绻娴膶憙蓚€(gè)log會(huì)有原子性的問題(一個(gè)寫成功了另一個(gè)沒寫成功)以及IO放大的問題。

這里的設(shè)計(jì)空間比較龐大，不做詳細(xì)討論，僅僅考慮在簡化的模型下復(fù)制順序的問題。

對(duì)于并發(fā)執(zhí)行的事務(wù)，為了確定復(fù)制順序，這里維護(hù)一個(gè)稱之為OpTime的自增ID。后續(xù)的復(fù)制會(huì)按照OpTime的順序，OpTime小的先復(fù)制。如果OpTime僅僅是在事務(wù)的開始和結(jié)束之間分配，會(huì)帶來問題：

• 有沖突且并發(fā)的事務(wù)T1先Commit，具有較大的OpTime，也就意味會(huì)被后復(fù)制;
• 后Commit的事務(wù)T2先Replication Commit，而先Commit的事務(wù)T1可能因?yàn)閺?fù)制失敗而Rollback;
• 對(duì)于事務(wù)來說，這種場景下出現(xiàn)的異常類似Read-Uncommitted，事務(wù)T2讀到了未Commit的數(shù)據(jù)。

因此，OpTime的分配需要有更強(qiáng)的限制：對(duì)于并發(fā)且有沖突的事務(wù)，OpTime的順序要和事務(wù)的Serialization Order一樣：

在S2PL的場景中，我們把OpTime分配放到Lock之后Commit之前，即可滿足這個(gè)要求。因?yàn)榘凑誗2PL的調(diào)度，事務(wù)的Commit-Point就是Lock完成和Unlock之間。對(duì)照上面的例子，事務(wù)T2的OpTime被推遲到T1之后，復(fù)制的順序也會(huì)相應(yīng)改變，不會(huì)發(fā)生先前的異常了。

推廣到其他的并發(fā)控制方法也是類似，例如上面的Snapshot Isolation。提交之前會(huì)檢查[begin, end]是否有沖突，有沖突直接重啟事務(wù)。相當(dāng)于在[begin, end]區(qū)間內(nèi)分配OpTime即可。

這種方法通過OpTime，保留了Transaction Serialization Order和RSM的Order之間的關(guān)系：

• 并發(fā)且有沖突的事務(wù)，其OpTime的順序和事務(wù)Serialization Order一樣;
• 并發(fā)但沒有沖突的事務(wù)，其OpTime順序不確定，因?yàn)檎l先提交都不會(huì)影響正確性;
• 有先于關(guān)系的事務(wù)，OpTime也一定滿足這個(gè)先于關(guān)系。

不過這里留下了一個(gè)問題，留待讀者思考：

如何按照OpTime復(fù)制，因?yàn)橛惺聞?wù)Abort的情況，OpTime做不到連續(xù)自增，僅僅是單調(diào)自增。

二、對(duì)比

***種其實(shí)是Spanner，第二種是TiKV、Percolator，第三種是MySQL、MongoDB。

它們?cè)趶?fù)制上的區(qū)別：

• ***種方案，復(fù)制了事務(wù)的REDO，事務(wù)的提交順序由Raft Log的順序確定，F(xiàn)ailover等機(jī)制完全按照RSM的模型來即可;
• 第二種方案，Raft僅僅用于復(fù)制KV，事務(wù)的順序和Raft Log的順序沒有關(guān)系，KV層的Failover和事務(wù)的Recovery完全獨(dú)立;
• 第三種方案，已經(jīng)區(qū)別于傳統(tǒng)的RSM模型，因?yàn)樗鋵?shí)是先Apply，再Replication、Commit，可以實(shí)現(xiàn)并發(fā)Apply。

從復(fù)雜度來看：

• 第二種最簡單清晰，從Raft，到Raft KV，再到Transactional KV，分層良好;
• 其次是***種，在Leader節(jié)點(diǎn)會(huì)額外實(shí)現(xiàn)Lock Table、Transaction Manager，這個(gè)和Raft是緊密結(jié)合的，但是事務(wù)提交的順序就是Raft Log的提交順序，不會(huì)造成混淆;
• 最復(fù)雜的是第三種，由于事務(wù)提交順序和Optime順序不一致，對(duì)復(fù)制、讀寫等各種流程都會(huì)造成影響，看似簡單但實(shí)則耦合。

從事務(wù)并發(fā)的角度來看：

• 第三種方案可以***支持并發(fā)，且持有鎖的時(shí)間較短，僅僅是寫一次本地日志;
• ***二種方案持有鎖的時(shí)間更長，***在Apply時(shí)理論上可以做到并發(fā)，如果沒有其他約束。

從讀寫開銷的角度來看：

• ***種***，Replication Log和Engine Log可以合并，每條事務(wù)只要復(fù)制一次Raft Log;
• 其次是第二種，通常會(huì)把binlog和存儲(chǔ)引擎的journal獨(dú)立，需要寫兩遍;不過oplog可以寫到存儲(chǔ)引擎里，一次IO即可提交(MongoDB的做法);
• ***是第二種，在KV中增加了更多的數(shù)據(jù)，放大較多。

不過這僅僅是理論上的分析，實(shí)際的復(fù)雜度、性能，很大程度上取決于實(shí)現(xiàn)而非理論。

三、總結(jié)

如果我們從很粗的層面來看，會(huì)覺得這些系統(tǒng)不過都是幾個(gè)技術(shù)點(diǎn)的組合，而每一個(gè)技術(shù)點(diǎn)看起來都很簡單，進(jìn)而覺得事務(wù)系統(tǒng)不過是如此。

但實(shí)際上事務(wù)系統(tǒng)絕非簡單的KV+Raft+Snapshot Isolation，它們之間不同的組合方式，會(huì)最終造就不同的系統(tǒng)。

本文留下了很多問題，RSM的Order往往認(rèn)為是全序的，而Transaction 的Serialization Order是偏序的(偏序關(guān)系由事務(wù)沖突定義)，它們之間如何統(tǒng)一?

RSM的Checkpoint和Transaction Checkpoint的統(tǒng)一?RSM的Recovery和Transaction Recovery的關(guān)系?寫兩條日志的系統(tǒng)(journal和binlog)兩條日志之間的關(guān)系是什么?