分布式事務常見實現算法，你知道幾個？
布式事務處理算法是確保分布式架構下跨多個節點或服務的事務保持原子性和一致性的技術特性。本文介紹一些常見的分布式事務算法，包括2PC/3PC、TCC和Saga、CAP和BASE基本理論，以加深了解。
1、2PC
二階段提交2PC是一致性協議算法，可以保證數據的強一致性，該算法能夠解決很多臨時性系統故障（包括進程、網絡節點、通信等故障），被廣泛地使用于關系型數據庫系統中。
1.1 二階段提交過程
2PC協議中系統分為協調者和參與者，整個過程分為兩個階段：
1） 階段1：Prepare請求階段
- 在請求階段，協調者向事務的參與者發起執行操作的CanCommit請求，通知事務參與者準備提交或取消事務，并等待參與者的響應；
- 參與者接到請求后，執行請求中的事務操作，記錄undo/redo日志信息，同時鎖定當前記錄
- 參與者反饋事務的執行結果，如果執行成功則返回YES，如果執行失敗則返回NO
- 當所有的參與者返回操作結果后，系統進入提交階段
2） 階段2：Commit提交階段
- 協調者會根據所有參與者返回的信息向參與者發送DoCommit或DoAbort指令
- 當且僅當所有的參與者返回YES時協調者向所有的參與者發送DoCommit消息提交事務，否則協調者將向所有的參與者發送DoAbort取消事務。此時發送“Yes”的參與者則會根據回滾日志對之前操作進行回滾
- 參與者在接收到協調者發來的消息后向協調者發送“HaveCommitted”消息
- 協調者接收到“HaveCommitted”消息，就意味著整個事務結束
1.2 2PC缺點
2PC協議的優點是原理簡單、實現方便，但也有以下缺點：
- 同步阻塞：在二階段提交的執行過程中，所有參與該事務操作的邏輯都處于阻塞狀態，也就是說，各個參與者在等待其他參與者響應的過程中，將無法進行其他任何操作。
- 單點問題：協調者的角色在整個二階段提交協議中起到了非常重要的作用。一旦協調者出現問題，那么整個二階段提交流程將無法運轉，更為嚴重的是，如果協調者是在階段二中出現問題的話，那么其他參與者將會一直處于鎖定事務資源的狀態中，而無法繼續完成事務操作。
- 數據不一致：在階段二時，當協調者向所有的參與者發送Commit請求之后，發生了局部網絡異?；蛘呤菂f調者尚未發送完Commit請求之前自身發生了崩潰，導致最終只有部分參與者收到了Commit請求。于是，這部分收到了Commit請求的參與者就會進行事務的提交，而其他沒有收到Commit請求的參與者則無法進行事務提交，于是整個分布式系統便出現了數據不一致現象。
- 二階段無法解決的問題：協調者在發出DoCommit消息之后宕機，而唯一接收到這條消息的參與者同時也宕機了。那么即使協調者通過選舉協議產生了新的協調者，這條事務的狀態也是不確定的，沒人知道事務是否被已經提交。
2、3PC
為了解決2PC過程中同步阻塞和數據不一致的問題，3PC協議在協調者和參與者中都引入超時機制，并且把兩階段提交協議的第一個階段拆分成了兩步：詢問，然后再鎖資源，最后真正提交，包括CanCommit、PreCommit和doCommit三個階段。
2.1 3PC提交過程
1）CanCommit階段3PC的CanCommit階段和2PC的準備階段很像。協調者向參與者發送commit請求，參與者如果可以提交就返回Yes響應，否則返回No響應。
2）PreCommit階段
協調者根據參與者的反應情況來決定是否可以繼續事務的PreCommit操作。根據響應情況，有以下兩種可能。
- 假如協調者從所有的參與者獲得的反饋都是Yes響應，那么就會進行事務的預執行：
發送預提交請求。協調者向參與者發送PreCommit請求，并進入Prepared階段。
事務預提交。參與者接收到PreCommit請求后，會執行事務操作，并將undo和redo信息記錄到事務日志中。
響應反饋。如果參與者成功的執行了事務操作，則返回ACK響應，同時開始等待最終指令。
- 假如有任何一個參與者向協調者發送了No響應，或者等待超時之后，協調者都沒有接到參與者的響應，那么就中斷事務：
- 發送中斷請求。協調者向所有參與者發送abort請求。
- 中斷事務。參與者收到來自協調者的abort請求之后（或超時之后，仍未收到Cohort的請求），執行事務的中斷。
3）DoCommit階段
該階段進行真正的事務提交，也可以分為以下兩種情況:
- 執行提交
發送提交請求。協調者接收到參與者發送的ACK響應，那么他將從預提交狀態進入到提交狀態。并向所有參與者發送doCommit請求。
事務提交。參與者接收到doCommit請求之后，執行正式的事務提交。并在完成事務提交之后釋放所有事務資源。
響應反饋。事務提交完之后，向協調者發送ACK響應。
完成事務。協調者接收到所有參與者的ACK響應之后，完成事務。
- 中斷事務
- 協調者沒有接收到參與者發送的ACK響應（可能是接受者發送的不是ACK響應，也可能響應超時），那么就會執行中斷事務。
2.2 3PC優缺點
- 三階段優點：
降低了二階段的同步阻塞范圍（在第二階段，只要參與者收到preCommit請求，就會執行事務，此后，不管能不能收到協調者的doCommit請求,都會執行事務提交，不會出現阻塞問題）
解決單點問題：進入階段三會出現兩種情況： 1：協調者出現問題； 2：協調者與參與者之間出現網絡故障； 都導致參與者無法收到doCommit請求，但參與者在超時之后都會提交事務
- 三階段缺點：
- 數據不一致：參與者收到preCommit請求，此時如果出現網絡分區，協調者與參與者之間無法進行正常網絡通信，參與者在超時之后還是會進行事務提交，就會出現數據不一致。
3、Saga模式
Saga模式屬于長事務解決方案，其核心思想把一個分布式事務拆分為多個本地事務，每個本地事務都有相應的執行模塊和補償模塊，當Saga事務中任意一個本地事務出錯時，可以通過調用相關的補償方法恢復之前的事務，達到事務最終一致性。Saga模式由三部分組成：
- LLT（Long Live Transaction）：由一個個本地事務組成的事務鏈。
- 本地事務：事務鏈由一個個子事務（本地事務）組成，LLT = T1+T2+T3+…+Ti。
- 補償：每個本地事務 Ti 有對應的補償 Ci。
在業務流程中，正常情況下每個參與者都在一階段提交本地事務，按照T1->T2->T3->…->Ti的順序執行。當出現異常時，則會發起補償，將之前提交的事務回滾，執行順序變成T1->T2->T3->C3->C2->C1。如下圖所示：
Saga模式的恢復其實有兩種：向后恢復（Backward Recovery）和向前恢復（Forward Recovery）
- 向后恢復（Backward Recovery）：撤銷掉之前所有成功子事務。如果任意本地子事務失敗，則補償已完成的事務。如異常情況的執行順序T1,T2,T3,…Ti,Ci,…C3,C2,C1。
- 向前恢復（Forward Recovery）：即重試失敗的事務，適用于必須要成功的場景，該情況下不需要Ci。執行順序：T1,T2,…,Tj（失?。?Tj（重試）,…,Ti。
Saga模式滿足事務的ACD三個特性：
- 原子性：Saga協調器協調事務鏈中的本地事務要么全部提交，要么全部回滾
- 一致性：Saga事務可以實現最終一致性
- 持久性：基于本地事務，所以這個特性可以很好實現
但是缺乏隔離性會引發臟讀、幻讀和不可重復讀等問題，因此需要在業務設計上去解決這個問題，通常在應用層面通過邏輯鎖或者串行化操作來確保讀取數據的準確性。
實現Saga的注意事項：
(1) Ti和Ci必須是冪等的。如向后恢復和向前恢復時候如果不是冪等操作會導致數據不一致。
(2) Ci必須是能夠成功的，如果無法成功則需要人工介入。
(3) Ti->Ci和Ci->Ti的執行結果必須是一樣的。4、TCC模式
TCC（Try-Confirm-Cancel）的概念，最早是由Pat Helland于2007年發表的論文《Life beyond Distributed Transactions:an Apostate’s Opinion》中提出。TCC采用補償機制，其核心思想是針對每個操作，都要注冊一個與其對應的確認和補償，通過對資源的預留盡早釋放對資源的加鎖，提交則完成資源的確認，回滾則釋放預留資源。TCC要求應用的每個服務提供 try、confirm、cancel三個接口，這些完全由業務實現，對業務侵入較大。
- Try階段：嘗試執行，完成所有業務檢查（一致性）, 預留必須業務資源（準隔離性）
- Confirm階段：確認執行業務，不作任何業務檢查，只使用Try階段預留的業務資源Confirm操作要求具備冪等設計，Confirm失敗后需要進行重試。
- Cancel階段：取消執行，釋放Try階段預留的業務資源。Cancel階段的異常和Confirm階段異常處理方案基本上一致，要求滿足冪等設計。
TCC模式處理流程如上圖所示，包括三部分：
- 主業務程序：負責發起并完成整個業務活動，在圖中由它向TM注冊TCC事務并開啟分布式事務，執行業務
- 分支服務：整個業務活動的參與方，實現Try、Confirm和Cancel動作，供主業務程序調用。對應圖中的微服務A和微服務B，執行Try執行，并根據TM返回的結果執行Confirm或Cancel
- 事務管理器：管理整個業務活動，包括記錄事務狀態，調用分支服務的Confirm/Cancel 操作
TCC模式相較于Saga模式來說應用可以自定義數據操作的粒度，降低了鎖沖突，提升業務并發度；但是對應用侵入較強，開發量較大，需要提供Try/Confirm/Cancel接口。
5、不同分布式事務算法對比
上述四種分布式事務的方案，在事務一致性、實現復雜性、對業務的侵入性、使用局限性、性能和維護成本等角度，總結如下表：
屬性 | 2PC | 3PC | TCC | Saga |
事務一致性 | 強 | 強 | 弱 | 弱 |
復雜性 | 低 | 中 | 中 | 高 |
業務侵入性 | 小 | 小 | 小 | 大 |
使用局限性 | 中 | 中 | 中 | 高 |
性能 | 低 | 中 | 高 | 中 |
維護成本 | 低 | 中 | 中 | 高 |
不同模式有不同的的使用場景，如下所示：
- 2PC/3PC：依賴于數據庫，能夠很好的提供強一致性和強事務性，但延遲比較高，比較適合傳統的單體應用，在同一個方法中存在跨庫操作的情況，不適合高并發和高性能要求的場景
- Saga模式：由于Saga事務不能保證隔離性，需要在業務層控制并發，適合于業務場景事務并發操作同一資源較少的情況。Saga由于缺少預提交動作，導致補償動作的實現比較麻煩，例如業務是發送短信，補償動作則得再發送一次短信說明撤銷，用戶體驗比較差。所以，Saga事務較適用于補償動作容易處理的場景。
- TCC：適用于執行時間確定且較短，實時性要求高，對數據一致性要求高，比如金融類交易和支付類業務
6、CAP理論
CAP理論是計算機科學家Eric Brewer在2000年提出的理論猜想，在2002年被證明并成為分布式計算領域公認的定理，其理論的基本觀念是，在分布式系統中不可能同時滿足以下三個特性：
- C：consistency一致性，指系統在執行某些操作后仍處于一致狀態；
- A：Availability可用性，指所有的操作在合理的時間內都得到響應；
- P：Partition Tolerance分區容錯性，指在網絡分區故障時，系統仍能繼續提供服務。
6.1 Consistency一致性
CAP理論中的一致性指的是Serializability可線性化的意思，也就是非常特殊的強一致性，但是這里的Consistency和ACID中的一致性是兩回事，事務中的一致性包含了對狀態的后續處理而CAP定理并不涉及到狀態的后續處理。因此CAP中的一致性指"all nodes see the same data at the same time"，即更新操作成功后，所有節點在同一時間的數據完全一致。對于一致性的理解，可以從客戶端和服務端兩個不同的視角來分析。
- 從客戶端來看，一致性主要指的是多并發請求時更新過的數據如何獲取的問題。如果更新過的數據需要立刻被后續的請求獲取到就是強一致性，如果能容忍后續的請求部分或者全部訪問不到則是弱一致性，如果經過一段時間后要求能訪問到更新后的數據則是最終一致性。
- 從服務端來看，一致性則是數據更新后如何同步到整個分布式系統，以保證數據最終一致性。
一致性一般在并發讀寫的時候才出現這個問題，需要結合并發讀寫的場景考慮
- 如上左圖所示，客戶端向節點N1更新數據V0->V1，在接下來讀操作過程中，從N1節點讀取的是V1，N2節點讀取的是V0，對于單節點沒有問題，但是在分布式系統中N1節點和N2節點讀取的結果就不一致了
- 如上右圖所示，客戶端在向N1發起寫操作時，N1節點向N2節點發起了同步操作，將兩個節點的值都修改為V1，這時客戶端從N1和N2節點獲取到的值都是V1，保證了一致性
上述例子用可線性化解釋就是
如果B操作在成功完成A操作之后，那么整個系統對B操作來說必須表現為A操作已經完成了或者更新的狀態。
如果系統內部發生了故障從而導致系統的節點無法發生一致性變化，比如N2節點無法同步N1節點的數據。這也意味著客戶端查詢最新數據的時候，部分節點很可能會看到舊數據，或者說獲取到不同版本的數據。此時，為了保證分布式系統對外的數據一致性，于是選擇不返回任何數據。
6.2 Availability可用性
可用性指"reads and writes always succeed"，即要求系統內的節點們接收到了無論是寫請求還是讀請求，都要能處理并給回響應結果。同時有幾點必須滿足的條件：
- 返回結果必須在合理的時間以內，這個合理的時間是根據業務來定的，如果超過業務規定的返回時間這個系統也就不滿足可用性；
- 系統能所有能正常接收請求的節點都能返回結果，如果節點宕機了不能正常接收請求但是其它節點可以正常返回，可以說系統依然是可用的，不影響可用性指標。如果所有節點都能返回，但是返回的數據不一致，其中一個節點是1天前的數據，另一個是1s前的，也稱為系統可用的。
一般在描述一個系統可用性時，通過停機時間來計算，比如某某系統可用性可以達到5個9，意思就是說該系統的可用水平是99.999%，即全年停機時間不超過(1-0.99999)36524*60 = 5.256min，這是一個極高的要求。
6.3 Partition tolerance分區容錯性
分布式系統架構下會有多個節點，這些節點之間通過網絡進行通信，但是當網絡故障或其它原因節點之間通信出現異常，當前的分布式系統就出現了分區。分區容錯性指"the system continues to operate despite arbitrary message loss or failure of part of the system"，即分布式系統在遇到某節點或網絡分區故障的時候，仍然能夠對外提供滿足一致性和可用性的服務。
6.4 CAP之間權衡
根據CAP理論，在分布式系統中無法同時滿足一致性、可用性和分區容錯性，在實際應用中又如何來進行取舍。
6.4.1 CA模型
舍棄分區容錯性意味著將所有的服務器搬到一個網絡節點內，顯然不滿足分布式系統的可伸縮性擴展要求。因此在分布式系統中P是一個基本要求，不選 P，一旦發生分區錯誤，整個分布式系統就完全無法使用了，這是不符合實際需要的。所以，對于分布式系統，我們只能能考慮當發生分區錯誤時，如何選擇一致性和可用性。CA模型常見的例子包括單站點數據庫、集群數據庫、LDAP和XFS文件系統等，通常是通過兩階段提交和緩存驗證協議實現的。
6.4.2 CP模型
舍棄A保證Consistency，不同節點之間需要保證數據的一致性，但是因為網絡分區的不穩定，可能出現其它節點的數據沒有及時更新。如果一個分布式系統不要求強的可用性，即允許系統停機或者長時間無響應的話，就可以在CAP三者中保障CP而舍棄A。這樣的分布式系統一旦發生網絡故障或者消息丟失等情況，就要犧牲用戶體驗，等數據一致后再讓用戶訪問系統。CP模型下典型的場景是分布式數據庫，通過悲觀鎖機制或少數分區不可用來優先保證數據一致性。像分布式緩存Redis、分布式協調中心Zookeeper，滿足分布式系統下的數據一致性是最基本的要求。
6.4.3 AP模型
AP模型是在保證高可用和分區容錯性的同時，舍棄數據一致性。為了保證高可用性，分布式系統下的不同節點需要立即返回結果給客戶端，這樣可能會出現不同節點之間的數據不一致，也就是會出現全局數據的不一致。也可以說是舍棄了數據的強一致性，保證的是數據的最終一致性（BASE理論）。AP模型使用的場景非常多，在一些高并發的系統中利用排隊和樂觀鎖機制優先保證系統的可用性，避免造成系統的阻塞。
7、BASE理論
在分布式系統中，面對CAP權衡時，通常的做法會選擇AP舍棄C（舍棄強一致性但保證最終一致性），這其實也是分布式領域的另外一個理論，叫BASE理論。BASE是指基本可用（Basically Available）、軟狀態（ Soft State）、最終一致性（ Eventual Consistency）。BASE理論是對CAP理論的延伸，其核心思想是：
即使無法做到強一致性（Strong consistency），但每個應用都可以根據自身的業務特點，采用適當的方式來使系統達到最終一致性（Eventual consistency）
7.1 基本可用（Basically Available）
基本可用是指分布式系統在出現故障時，允許損失部分可用性，即保證核心可用。
- 響應時間上的損失：正常情況下的客戶端請求0.5s即返回給用戶結果，而基本可用的情況下可以在1秒甚至2s返回結果，超過一定閾值用戶就接受不了
- 功能上的損失：在一個購物網站上，正常情況下，用戶可以順利完成每一筆訂單，但是到了促銷活動期間，為了保障購物系統的穩定性，部分消費者可能會被引導到一個服務降級頁面。
7.2 軟狀態（Soft State）
軟狀態是相對原子性來說的
- 原子性（硬狀態）：要求多個節點的數據副本都是一致的，這是一種"硬狀態"
- 軟狀態（弱狀態）：允許系統中的數據存在中間狀態，并認為該狀態不影響系統的整體可用性，即允許系統在多個不同節點的數據副本存在數據延遲
比如在分布式數據庫MySQL的復制中一般一份數據會有多個副本，允許不同節點間副本同步的延時就是軟狀態的體現。
7.3 最終一致性（Eventual Consistency）
系統不可能一直是軟狀態，必須有個時間期限。在期限過后，應當保證所有副本保持數據一致性，從而達到數據的最終一致性。這個時間期限取決于網絡延時，系統負載，數據復制方案設計等等因素。最終一致性是弱一致性的特定形式，官方的定義是：
系統能夠保證在沒有其他新的更新操作的情況下，數據最終一定能夠達到一致的狀態，因此所有客戶端對系統的數據訪問最終都能夠獲取到最新的值。
