建站
咨詢
售后
建站咨詢
新聞中心
本文試圖討論這幾個問題：
網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了柳城免費建站歡迎大家使用！
- MySQL的redo log和binlog為什么要用XA?
- MongoDB的oplog是按照什么順序復制?
- Raft真的只能串行Apply嗎?
- 數(shù)據(jù)庫的復制和事務(wù)是完全獨立的兩回事?
- 為什么MySQL不早點做一個Raft插件，直接用Raft實現(xiàn)高可用?
本文旨在闡述Fault-Tolerant Transaction的幾種實現(xiàn)模式。雖然乍一看它們可能都是Raft+KVEngine +Concurrency Control，容易被認為是同一類方法，但實際上的差異很大，在討論時不應(yīng)該忽視它們之間的差異。
一、基本概念
討論的Fault-Tolerance，指的是通過網(wǎng)絡(luò)通信的多個計算機節(jié)點，在部分節(jié)點發(fā)生Stop Failure的情況下，仍然盡力保證可用性;
不討論具體的Fault-Tolerance方法，默認讀者對Raft等算法有基本理解;
也不討論具體的Concurrency Control方法，默認讀者對其有基本的理解;
會涉及到Spanner、TiKV、MongoDB等具體的數(shù)據(jù)庫。
1、基于RSM的Fault-Tolerant KV
Replicated State Machine最早應(yīng)該是在『Implementing fault-tolerant services using the state machine approach』提出。它是一種很簡單實用的實現(xiàn)容錯的方法，核心思想是：幾個狀態(tài)機具有相同的初始狀態(tài)，并且按照同樣的順序執(zhí)行了同樣的命令序列，那么它們的最終狀態(tài)也是一樣的。由于狀態(tài)一樣，那么任意一個狀態(tài)機宕機，都可以被其他的代替，因此實現(xiàn)了Fault Tolerant。
這里提到了幾個概念，命令、執(zhí)行順序、狀態(tài)機，它們都是抽象概念，對應(yīng)到具體的應(yīng)用場景才有實際意義。在KVEngine的場景下，命令就是Put/Get等操作，狀態(tài)機就是KVEngine本身，而執(zhí)行序列，則由Replication Log決定。
既然提到了RSM和KV，那么基于RSM的KV也就呼之欲出了。把發(fā)到KVEngine的操作先用Raft復制一遍，在Apply的時候扔回到KVEngine執(zhí)行，于是我們就得到了一個Fault-Tolerant的KVEngine。
看起來很簡單，但我在這里顯然忽略了很多細節(jié)：
- 串行還是并行Apply：Raft被人詬病的一點是串行Commit、串行Apply，但這并不是Raft的鍋;
- 兩條Log：Raft復制需要一個Log，KVEngine也會有一個WAL，會帶來IO放大，能不能合并成一個呢?
- Checkpoint：為了加速Recovery，需要做Checkpoint;
- 只讀操作需要復制嗎?
- 命令可以是復合操作嗎：單行的CAS操作可以嗎，多行的事務(wù)操作可以作為一個命令嗎?
2、基于RSM的事務(wù)
我們來考慮***一個問題，RSM中的命令，可以直接是一個事務(wù)嗎?
既然Raft都是串行Apply了，那么看起來把事務(wù)的所有操作作為一個命令扔到狀態(tài)機執(zhí)行并沒有什么問題。
但問題在于，實際中的事務(wù)是交互式的，也就是包含了if-else等邏輯的，并且邏輯還可能依賴了數(shù)據(jù)庫系統(tǒng)外部的狀態(tài)，所以不能簡單地用Write Batch + Snapshot來實現(xiàn)一個事務(wù)，還是要有Concurrency Control的邏輯。
為了解決Concurrency Control的問題，我們在Raft Leader上，實現(xiàn)一個Lock Table和Transaction Manager。拿S2PL方法舉例：
- 讀數(shù)據(jù)之前加讀鎖，寫數(shù)據(jù)之前加寫鎖;讀操作通過Raft讀數(shù)據(jù)，寫操作Buffer在本地;
- 在用戶決定事務(wù)提交時，即可釋放讀鎖;通過Raft寫一條事務(wù)日志，包含所有寫操作;
- 在Raft Apply事務(wù)日志時，把寫操作應(yīng)用到KVEngine，并且釋放寫鎖。
這里舉的例子是S2PL，但對于其他的并發(fā)控制方法也基本通用。例如Snapshot Isolation，事務(wù)開始時獲得KV的Snapshot，讀操作都走Snapshot，寫操作獲得寫鎖，數(shù)據(jù)Buffer在本地，事務(wù)提交時檢查[begin, end]之間有沒有寫沖突，沒有的話則通過Raft寫事務(wù)日志，在Apply事務(wù)日志之后，把寫操作應(yīng)用到KVEngine，***釋放寫鎖。
這種方法接近Spanner的做法，它具有幾個特點：
- 只有Leader需要維護Lock Table、Transaction Manager，事務(wù)并發(fā)控制基本在Leader節(jié)點完成;
- 從RSM的角度來看，這里的Lock Table起到了命令定序的作用，保證所有State Machine按照同樣的順序執(zhí)行命令;
- 加鎖操作不走復制協(xié)議，解鎖操作在復制協(xié)議Apply之后完成，鎖會在復制的開始到Commit一直持有：也就意味著，復制協(xié)議的Commit即是事務(wù)的Commit，在Commit之前發(fā)生Failover，事務(wù)都會Abort;
- Raft所復制的，即是事務(wù)的REDO。
3、基于共享存儲的事務(wù)
重新看一下上面這個模型，復制協(xié)議所做的事情非常簡單，和其他模塊的耦合也很小，僅僅是維護一個有序的Log，因此，我們可以把它從share-nothing推廣到share-storage的模型中。
也就是說，我們把普通的單機事務(wù)引擎，放到一個高可用的存儲上，就得到了基本可用的Fault-Tolerant 事務(wù)引擎了，連復制協(xié)議也不需要實現(xiàn)的。
不過事情顯然不會這么簡單：
- 如何實現(xiàn)只讀節(jié)點，提供讀擴展的能力;
- 計算節(jié)點如何更快地Failover;
- 如何把更多的操作下推到存儲節(jié)點。
4、基于高可用KV的事務(wù)
回到一開始的***種方案，在一個節(jié)點實現(xiàn)了KV、Raft、Lock Table、Transaction Manager，看起來耦合度比較大了，我們能不能對其進行分層，進一步簡化呢?例如Google的經(jīng)典做法，基于GFS實現(xiàn)Bigtable，基于Bigtable實現(xiàn)Percolator，Layered設(shè)計易于迭代、易于開發(fā)、易于調(diào)試。
因此我們可以考慮把KV層單獨抽離出來，基于KV去實現(xiàn)Lock Table、Txn Manager：
- Lock Table：在原本的KV中增加一列，變成Key => {Value, Lock};
- Txn Manager: 從事務(wù)修改的所有Key中選出一個Primary Key，用來記錄事務(wù)狀態(tài)，因此KV進一步變成 Key => {Value, Lock, TxnStatus};
- MVCC：甚至我們不甘心于Single Version，還想用Multi Version的并發(fā)控制，那么KV就變成{Key, Version} => {Value, Lock, TxnStatus}。
看過Percolator、TiKV設(shè)計的應(yīng)該會比較熟悉，它們就是基于一個高可用的KV，把事務(wù)的狀態(tài)都下沉到KV中。這種設(shè)計很容易拓展到分布式事務(wù)的場景，如果KV能夠scale，那么上層的事務(wù)也能夠scale了。
5、基于單機事務(wù)引擎實現(xiàn)高可用事務(wù)
上面的方案看起來都比較簡單，不過有一個細節(jié)不容忽視：鎖基本都是在復制協(xié)議提交之后才會釋放，換句話說事務(wù)持有的鎖會從事務(wù)開始直到多個節(jié)點寫完日志，經(jīng)歷多次網(wǎng)絡(luò)延遲、IO延遲，并且在擁塞情況下會面臨排隊延遲的風險。而鎖意味著互斥，互斥意味著事務(wù)吞吐降低。
翻譯一下：
- 并發(fā)且有沖突的事務(wù)，其提交順序由Lock Table決定，并且和復制協(xié)議的Log順序一致;
- 事務(wù)的Serialization Order，和RSM 中的Order一致。
不過這里存在一個問題：
- 鎖一定要在復制協(xié)議提交之后才能釋放嗎?
- 提前釋放會破壞Order的一致性嗎?
- RSM的Order一定要和事務(wù)的Serialization Order一致嗎?
暫且不做回答，我們再看***一種方案，基于單機事務(wù)引擎的高可用事務(wù)。
在正常的單機事務(wù)流程中，增加一個復制的環(huán)節(jié)：本地事務(wù)提交之后不是立即返回用戶，而是寫binlog，等待binlog復制到其他節(jié)點之后再返回用戶。
這種方式的事務(wù)延遲，看起來還是本地事務(wù)的延遲，加上復制日志的延遲;但相比于之前的方案，本地事務(wù)可以先提交，鎖可以提交釋放，總體的事務(wù)吞吐相比之下會有所提升。
看起來甚至比之前的方案更加簡單，事務(wù)和復制模塊得到了***的分離，但這里忽略了一個復雜的問題：
- 基于哪個日志來復制，基于數(shù)據(jù)庫的Journal，還是再寫一個binlog?
- 基于什么順序進行復制，如果是基于Journal復制可以用Journal順序，如果基于binlog，順序又是什么?
- 如果有兩個日志，兩個日志其實意味著Transaction Serialization Order和RSM的State Machine Order不一樣，會不會產(chǎn)生事務(wù)的并發(fā)異常，或者導致State Machine不一致?
由于直接復制Journal會引起一系列復雜的耦合問題，大部分數(shù)據(jù)庫都選擇單獨寫一個binlog/oplog來實現(xiàn)復制，不過在實現(xiàn)時可以做優(yōu)化，因為如果真的寫兩個log會有原子性的問題(一個寫成功了另一個沒寫成功)以及IO放大的問題。
這里的設(shè)計空間比較龐大，不做詳細討論，僅僅考慮在簡化的模型下復制順序的問題。
對于并發(fā)執(zhí)行的事務(wù)，為了確定復制順序，這里維護一個稱之為OpTime的自增ID。后續(xù)的復制會按照OpTime的順序，OpTime小的先復制。如果OpTime僅僅是在事務(wù)的開始和結(jié)束之間分配，會帶來問題：
- 有沖突且并發(fā)的事務(wù)T1先Commit，具有較大的OpTime，也就意味會被后復制;
- 后Commit的事務(wù)T2先Replication Commit，而先Commit的事務(wù)T1可能因為復制失敗而Rollback;
- 對于事務(wù)來說，這種場景下出現(xiàn)的異常類似Read-Uncommitted，事務(wù)T2讀到了未Commit的數(shù)據(jù)。
因此，OpTime的分配需要有更強的限制：對于并發(fā)且有沖突的事務(wù)，OpTime的順序要和事務(wù)的Serialization Order一樣：
在S2PL的場景中，我們把OpTime分配放到Lock之后Commit之前，即可滿足這個要求。因為按照S2PL的調(diào)度，事務(wù)的Commit-Point就是Lock完成和Unlock之間。對照上面的例子，事務(wù)T2的OpTime被推遲到T1之后，復制的順序也會相應(yīng)改變，不會發(fā)生先前的異常了。
推廣到其他的并發(fā)控制方法也是類似，例如上面的Snapshot Isolation。提交之前會檢查[begin, end]是否有沖突，有沖突直接重啟事務(wù)。相當于在[begin, end]區(qū)間內(nèi)分配OpTime即可。
這種方法通過OpTime，保留了Transaction Serialization Order和RSM的Order之間的關(guān)系：
- 并發(fā)且有沖突的事務(wù)，其OpTime的順序和事務(wù)Serialization Order一樣;
- 并發(fā)但沒有沖突的事務(wù)，其OpTime順序不確定，因為誰先提交都不會影響正確性;
- 有先于關(guān)系的事務(wù)，OpTime也一定滿足這個先于關(guān)系。
不過這里留下了一個問題，留待讀者思考：
如何按照OpTime復制，因為有事務(wù)Abort的情況，OpTime做不到連續(xù)自增，僅僅是單調(diào)自增。
二、對比
***種其實是Spanner，第二種是TiKV、Percolator，第三種是MySQL、MongoDB。
它們在復制上的區(qū)別：
- ***種方案，復制了事務(wù)的REDO，事務(wù)的提交順序由Raft Log的順序確定，F(xiàn)ailover等機制完全按照RSM的模型來即可;
- 第二種方案，Raft僅僅用于復制KV，事務(wù)的順序和Raft Log的順序沒有關(guān)系，KV層的Failover和事務(wù)的Recovery完全獨立;
- 第三種方案，已經(jīng)區(qū)別于傳統(tǒng)的RSM模型，因為它其實是先Apply，再Replication、Commit，可以實現(xiàn)并發(fā)Apply。
從復雜度來看：
- 第二種最簡單清晰，從Raft，到Raft KV，再到Transactional KV，分層良好;
- 其次是***種，在Leader節(jié)點會額外實現(xiàn)Lock Table、Transaction Manager，這個和Raft是緊密結(jié)合的，但是事務(wù)提交的順序就是Raft Log的提交順序，不會造成混淆;
- 最復雜的是第三種，由于事務(wù)提交順序和Optime順序不一致，對復制、讀寫等各種流程都會造成影響，看似簡單但實則耦合。
從事務(wù)并發(fā)的角度來看：
- 第三種方案可以***支持并發(fā)，且持有鎖的時間較短，僅僅是寫一次本地日志;
- ***二種方案持有鎖的時間更長，***在Apply時理論上可以做到并發(fā)，如果沒有其他約束。
從讀寫開銷的角度來看：
- ***種***，Replication Log和Engine Log可以合并，每條事務(wù)只要復制一次Raft Log;
- 其次是第二種，通常會把binlog和存儲引擎的journal獨立，需要寫兩遍;不過oplog可以寫到存儲引擎里，一次IO即可提交(MongoDB的做法);
- ***是第二種，在KV中增加了更多的數(shù)據(jù)，放大較多。
不過這僅僅是理論上的分析，實際的復雜度、性能，很大程度上取決于實現(xiàn)而非理論。
三、總結(jié)
如果我們從很粗的層面來看，會覺得這些系統(tǒng)不過都是幾個技術(shù)點的組合，而每一個技術(shù)點看起來都很簡單，進而覺得事務(wù)系統(tǒng)不過是如此。
但實際上事務(wù)系統(tǒng)絕非簡單的KV+Raft+Snapshot Isolation，它們之間不同的組合方式，會最終造就不同的系統(tǒng)。
本文留下了很多問題，RSM的Order往往認為是全序的，而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)系是什么?
當前題目：事務(wù)系統(tǒng)實現(xiàn)模式很簡單？你確定沒忽視這些差異？
鏈接分享：http://www.dlmjj.cn/article/dppepcg.html
