分佈式事務之底層原理揭祕

作者 | 妖道

出品 | 遠赴星辰

導言

分佈式事務是分佈式系統必不可少的組成部分，基本上只要實現一個分佈式系統就逃不開對分佈式事務的支持。本文從分佈式事務這個概念切入，嘗試對分佈式事務以及分佈式系統最核心的底層原理逐一進行剖析，內容包括但不限於 BASE 原則、兩階段原子提交協議、三階段原子提交協議、Paxos/Multi-Paxos 分佈式共識算法的原理與證明、Raft 分佈式共識算法和分佈式事務的併發控制等內容。

事務

_事務_是訪問並可能更新各種數據項的一個程序執行單元 (unit)。事務由一個或多個步驟組成，一般使用形如 begin transaction 和 end transaction 語句或者函數調用作爲事務界限，事務內的所有步驟必須作爲一個單一的、不可分割的單元去執行，因此事務的結果只有兩種：1. 全部步驟都執行完成，2. 任一步驟執行失敗則整個事務回滾。

事務最早由數據庫管理系統 (database management system，DBMS) 引入並實現，數據庫事務是數據庫管理系統執行過程中的一個邏輯單位，由一個有限的數據庫操作序列構成。數據庫事務嚴格遵循 ACID 原則，屬於剛性事務，一開始數據庫事務僅限於對單一數據庫資源對象的訪問控制，這一類事務稱之爲本地事務 (Local Transaction)，後來隨着分佈式系統的出現，數據的存儲也不可避免地走向了分佈式，分佈式事務（Distributed Transaction）便應運而生。

剛性事務

剛性事務（如單一數據庫事務）完全遵循 ACID 規範，即數據庫事務的四大基本特性：

剛性事務也能夠以分佈式 CAP 理論中的 CP 事務來作爲定義。

柔性事務

在電商領域等互聯網場景下，傳統的事務在數據庫性能和處理能力上都遇到了瓶頸。因此，柔性事務被提了出來，柔性事務基於分佈式 CAP 理論以及延伸出來的 BASE 理論，相較於數據庫事務這一類完全遵循 ACID 的剛性事務來說，柔性事務保證的是 “基本可用，最終一致”，CAP 原理相信大家都很熟悉了，這裏我們講一下 BASE 原則：

柔性事務（如分佈式事務）爲了滿足可用性、性能與降級服務的需要，降低一致性（Consistency）與隔離性（Isolation）的要求，遵循 BASE 理論，傳統的 ACID 事務對隔離性的要求非常高，在事務執行過程中，必須將所有的資源對象鎖定，因此對併發事務的執行極度不友好，柔性事務（比如分佈式事務）的理念則是將鎖資源對象操作從本地資源對象層面上移至業務邏輯層面，再通過放寬對強一致性要求，以換取系統吞吐量的提升。

此外，雖然柔性事務遵循的是 BASE 理論，但是還需要遵循部分 ACID 規範：

本地事務

本地事務（Local Transaction）指的是僅僅對單一節點 / 數據庫資源對象進行訪問 / 更新的事務，在這種事務模式下，BASE 理論派不上用場，事務完全遵循 ACID 規範，確保事務爲剛性事務。

分佈式事務

在分佈式架構成爲主流的當下，系統對資源對象的訪問不能還侷限於單節點，多服務器、多節點的資源對象訪問成爲剛需，因此，本地事務無法滿足分佈式架構的系統的要求，分佈式事務應運而生。

訪問 / 更新由多個服務器管理的資源對象的平面事務或者嵌套事務稱之爲分佈式事務（Distributed Transaction），分佈式事務是相對於本地事務來說的。

平面事務：單一事務，訪問多個服務器節點的資源對象，一個平面事務完成一次請求之後才能發起下一個請求。

嵌套事務：多事務組成，頂層事務可以不斷創建子事務，子事務又可以進一步地以任意深度嵌套子事務。

對於分佈式事務來說，有兩個最核心的問題：

  1. 如何管理分佈式事務的提交 / 放棄決定？如果事務中的一個節點在執行自己的本地事務過程中遇到錯誤，希望放棄整個分佈式事務，與此同時其他節點則在事務執行過程中一切順利，希望提交這個分佈式事務，此時我們應該如何做決策？

  2. 如何保證併發事務在涉及多個節點上資源對象訪問的可串行性（規避分佈式死鎖）？如果事務 T 對某一個服務器節點上的資源對象 S 的併發訪問在事務 U 之前，那麼我們需要保證在所有服務器節點上對 S 和其他資源對象的衝突訪問，T 始終在 U 之前。

問題 1 的解決需要引入一類分佈式原子提交協議的算法如兩階段提交協議等，來對分佈式事務過程中的提交或放棄決策進行管理，並確保分佈式提交的原子性。而問題 2 則由分佈式事務的併發控制機制來處理。

原子提交協議

原子性是分佈式事務的前置性約束，沒有原子性則分佈式事務毫無意義。

原子性約束要求在分佈式事務結束之時，它的所有操作要麼全部執行，要麼全部不執行。以分佈式事務的原子性來分析，客戶端請求訪問 / 更新多個服務器節點上的資源對象，在客戶端提交或放棄該事務從而結束事務之後，多個服務器節點的最終狀態要麼是該事務裏的所有步驟都執行成功之後的狀態，要麼恢復到事務開始前的狀態，不存在中間狀態。滿足這種約束的分佈式事務協議則稱之爲原子提交協議。

當一個分佈式事務結束時，事務的原子特性要求所有參與該事務的服務器節點必須全部提交或者全部放棄該事務，爲了實現這一點，必須引入一個協調者（Coordinator）的角色，從參與事務的所有服務器節點中挑選一個作爲協調者，由它來保證在所有服務器節點上最終獲得同樣的結果。協調者的工作原理取決於分佈式事務選用的協議。

一般來說，分佈式事務中包含的兩個最基礎的角色就是：

單階段原子提交協議

單階段原子提交協議（one-phase atomic commit protocol, 1APC）是最簡單的一種原子提交協議，它通過設置一個協調者並讓它不斷地向所有參與者發送提交（commit）或放棄（abort）事務的請求，直到所有參與者確認已執行完相應的操作。

1APC 協議的優點是簡單易用，對一些事務不復雜的場景比較合適，但在複雜事務場景則顯得捉襟見肘，因爲該協議不允許任何服務器節點單方面放棄事務，事務的放棄必須由協調者來發起，這個設計會導致很多問題：首先因爲只有一次通信，協調者並不會收集所有參與者的本地事務執行的情況，所以協調者決定提交還是放棄事務只基於自己的判斷，在參與者執行事務期間可能會遇到錯誤從而導致最終事務未能真正提交，錯誤一般與事務的併發控制有關，比如事務執行期間對資源對象加鎖，遇到死鎖，需要放棄事務從而解開死鎖，而協調者並不知道，因此在發起下一個請求之前，客戶端完全不知道事務已被放棄。另一種情況就是利用樂觀併發控制機制訪問資源對象，某一個服務器節點的驗證失敗將導致事務被放棄，而協調者完全不知情。

兩階段提交協議

兩階段提交協議（two-phase commit protocol, 2PC）的設計初衷是爲了解決 1APC 不允許任意一個服務器節點自行放棄它自己的那部分本地事務的痛點，2PC 允許任何一個參與者自行決定要不要放棄它的本地事務，而由於原子提交協議的約束，任意一個本地事務被放棄將導致整個分佈式事務也必須放棄掉。

兩階段提交協議基於以下幾個假設：

原理

兩階段提交協議，顧名思義整個過程需要分爲兩個階段：

  1. 準備階段（Prepare Phase）

  2. 提交階段（Commit Phase）

在進行兩階段提交的過程中，協調者會在以下四種狀態間流轉：

  1. init

  2. preparing

  3. committed

  4. aborted

而參與者則會在以下三種狀態間流轉：

  1. working

  2. prepared

  3. committed

階段 I（投票表決階段）

  1. 任意一個參與者發起分佈式事務 T 並執行本地事務成功，接着將一條 <ready T> 記錄追加到本地日誌 buffer 中並 flush 到可靠性存儲設備如磁盤上，從 working 狀態進入 prepared 狀態，然後向協調者發送 prepare T 消息；

  2. 收到參與者發來的 prepare T 消息後，協調者將一條 <prepare T> 記錄追加到日誌中，然後從 init 狀態進入 preparing 狀態，緊接着向分佈式事務的其他參與者發出 canCommit? 消息，發起事務表決過程；

  3. 當參與者收到 canCommit? 請求後，除了發起事務的那一個之外，其他還在 working 狀態的參與者會先嚐試執行本地事務，如果本地事務執行成功，則會往本地日誌 buffer 寫入一條 <ready T> 記錄並 flush 到可靠性存儲中，但不提交事務，進入 prepared 狀態，然後回覆一條 ready T 消息對此事務投 YES 票；如果本地事務執行失敗，則參與者會往本地日誌 buffer 寫入一條 <don't commit T> 記錄並 flush 到可靠性存儲中，然後回覆一條 don't commit T 消息投 NO 票。

階段 II（收集投票結果完成事務）

  1. 協調者收集所有的投票（包括它自己的投票）；

    (a) 如果所有的投票都是 ready T，則表示沒有故障發生，那麼協調者決定提交該事務，首先它會在其本地日誌中追加一條 <commit T> 記錄，從 preparing 狀態進入 committed 狀態，然後向所有的參與者發送 doCommit 請求消息，要求參與者提交它們的本地事務；

    (b) 如果有任一個投票是 No，則協調者決定放棄掉該事務，首先它會往本地日誌中追加一條記錄，從 preparing 狀態進入 aborted 狀態，然後發送 doAbort 請求消息給所有的參與者，通知它們回滾各自的本地事務。

  2. 投了 YES 票的參與者阻塞等待協調者給它發來 doCommit 或 doAbort 消息，如果接收到的是 doCommit 消息則提交本地事務並在此過程中記錄日誌 <commit T>，然後進入 committed 狀態，最後回覆一個 haveCommitted 的消息通知協調者本地事務已經成功提交；反之，如果收到的是 doAbort 消息則回滾本地事務並寫入日誌 <abort T>，然後進入 aborted狀態。

上面的過程是一種更通用的流程，即由任意的參與者發起一個分佈式事務，而在實踐中一般把分佈式事務的發起交給協調者來做，減少事務發起者確認該事務已被提交所需等待的網絡消息延遲：

性能

網絡 I/O 開銷

假設兩階段提交過程一切運行正常，即協調者和參與者都不出現崩潰和重啓，網絡通信也都正常。那麼假設有一個協調者和 N 個參與者，兩階段提交過程中將會發送如下的消息：

所以，事務發起者在經過 4 條網絡消息延遲之後確認該分佈式事務已被提交，而整個過程共計發送 3N - 1 條網絡消息（因爲 haveCommitted 在 2PC 僅僅是用於最後通知協調者而已，屬於可有可無的一次網絡消息，2PC 在該消息缺省的情況下也能正常運行，因此 haveCommitted 一般不計入網絡延遲成本中）。

前面我們提到，在實踐中一般是由協調者來發起事務，如果考慮這種情況的話，事務發起者 -- 協調者在經過 3 條網絡消息延遲之後確認該分佈式事務已經被提交，而整個過程實際發送的網絡消息則變成 3N 條。

總而言之，兩階段提交協議的網絡通信開銷和集羣節點的數量成 3 倍正比。

本地存儲設備 I/O 開銷

基於前文中敘述的兩階段提交協議的基本假設之一：每個節點會通過日誌來記錄在本地執行的操作，以便在節點發生故障並重啓節點之後能利用日誌恢復到故障前的狀態，因此兩階段提交過程中除了網絡 I/O 的開銷之外，還有本地存儲設備 I/O 的開銷：

所以事務發起者在經過 3 次本地存儲設備 I/O 延遲之後確認該事務已被提交，整個過程總計有 N + 1 次本地存儲設備 I/O，而如果由協調者來發起事務的話，則還是需要 N + 1 次本地存儲設備 I/O，但是隻需要經過 2 次本地存儲設備 I/O 延遲即可確認事務已被提交。

恢復

在分佈式事務中，所有的參與者節點都可能發生故障，所以我們需要保證在該故障節點恢復時發生的一切都和分佈式事務 T 的全局決策保持一致。節點在恢復的時候會讀取 T 的最後一個本地日誌記錄並作出相應的操作：

  1. 如果 T 的最後一條日誌記錄是 <commit T>，那麼說明協調者在節點發生故障時的全局決策是提交 T，根據本地事務所使用的日誌方式，在該節點上可能需要執行 redo T。

  2. 如果 T 的最後一條日誌記錄是 <abort T>，那麼說明協調者在節點發生故障時的全局決策是中止 T，根據本地事務所使用的日誌方式，在該節點上可能需要執行 undo T。

  3. 如果 T 的最後一條日誌記錄是 <don't commit T>，則和第 2 中情況類似，執行 undo T。

  4. 如果 T 的最後一條日誌記錄是 <ready T>，這種情況比較麻煩，因爲恢復節點無法確認在它故障之後協調者發出的最終全局決策是什麼，因此它必須要和集羣中其餘至少一個節點取得聯繫，詢問 T 的最終結果是什麼：恢復節點先嚐試詢問協調者，如果此時協調者正在工作，則告知恢復節點 T 的最終結果，如果是提交就執行 redo T，中止就執行 undo T；如果協調者因故不在工作，則恢復節點可以要求其他某一個參與者節點去查看本地日誌以找出 T 的最終結果並告知恢復節點。在最壞的情況下，恢復節點無法和集羣中其他所有節點取得聯繫，這時恢復節點只能阻塞等待，直至得知 T 的最終結果是提交還是中止。

  5. 如果本地日誌中沒有記錄任何關於 T 在兩階段提交過程中的操作，那麼根據前面的兩階段提交流程可知恢復節點還沒來得及回覆協調者的 canCommit? 請求消息就發生了故障，因此根據兩階段算法，恢復節點只能執行 undo T。

缺陷

  1. 同步阻塞：兩階段提交協議是一個阻塞的協議，在第二階段期間，參與者在事務未提交之前會一直鎖定其佔有的本地資源對象，直到接收到來自協調者的 doCommit 或 doAbort 消息。

  2. 單點故障：兩階段提交協議中只有一個協調者，而由於在第二階段中參與者在收到協調者的進一步指示之前會一直鎖住本地資源對象，如果唯一的協調者此時出現故障而崩潰掉之後，那麼所有參與者都將無限期地阻塞下去，也就是一直鎖住本地資源對象而導致其他進程無法使用。

  3. 數據不一致：如果在兩階段提交協議的第二階段中，協調者向所有參與者發送 doCommit 消息之後，發生了局部網絡抖動或者異常，抑或是協調者在只發送了部分消息之後就崩潰了，那麼就只會有部分參與者接收到了 doCommit 消息並提交了本地事務；其他未收到 doCommit 消息的參與者則不會提交本地事務，因而導致了數據不一致問題。

XA 標準接口

2PC 兩階段提交協議本身只是一個通用協議，不提供具體的工程實現的規範和標準，在工程實踐中爲了統一標準，減少行業內不必要的對接成本，需要制定標準化的處理模型及接口標準，國際開放標準組織 Open Group 定義了分佈式事務處理模型 DTP（Distributed Transaction Processing）Model，現在 XA 已經成爲 2PC 分佈式事務提交的事實標準，很多主流數據庫如 Oracle、MySQL 等都已經實現 XA。

兩階段事務提交採用的是 X/OPEN 組織所定義的 DTP Model 所抽象的 AP（應用程序）, TM（事務管理器）和 RM（資源管理器） 概念來保證分佈式事務的強一致性。其中 TM 與 RM 間採用 XA 的協議進行雙向通信。與傳統的本地事務相比，XA 事務增加了準備階段，數據庫除了被動接受提交指令外，還可以反向通知調用方事務是否可以被提交。TM 可以收集所有分支事務的準備結果，並於最後進行原子提交，以保證事務的強一致性。

Java 通過定義 JTA 接口實現了 XA 模型，JTA 接口中的 ResourceManager 需要數據庫廠商提供 XA 驅動實現， TransactionManager 則需要事務管理器的廠商實現，傳統的事務管理器需要同應用服務器綁定，因此使用的成本很高。而嵌入式的事務管器可以以 jar 包的形式提供服務，同 Apache ShardingSphere 集成後，可保證分片後跨庫事務強一致性。

通常，只有使用了事務管理器廠商所提供的 XA 事務連接池，才能支持 XA 的事務。Apache ShardingSphere 在整合 XA 事務時，採用分離 XA 事務管理和連接池管理的方式，做到對應用程序的零侵入。

三階段提交協議

由於前文提到的兩階段提交協議的種種弊端，研究者們後來又提出了一種新的分佈式原子提交協議：三階段提交協議（three-phase commit protocol, 3PC）。

三階段提交協議是對兩階段提交協議的擴展，它在特定假設下避免了同步阻塞的問題。該協議基於以下兩個假設：

  1. 集羣不發生網絡分區；

  2. 故障節點數不超過 K 個（K 是預先設定的一個數值）。

基於這兩個假設，三階段提交協議通過引入_**超時機制**_和一個_**額外的階段**_來解決阻塞問題，三階段提交協議把兩階段提交協議的第一個階段拆分成了兩步：1) 評估，2) 資源對象加鎖，最後才真正提交：

  1. CanCommit 階段：協調者發送 CanCommit 請求消息，詢問各個參與者節點，參與者節點各自評估本地事務是否可以執行並回復消息（可以執行則回覆 YES，否則回覆 NO），此階段不執行事務，只做判斷；

  2. PreCommit 階段：協調者根據上一階段收集的反饋決定通知各個參與者節點執行（但不提交）或中止本地事務；有兩種可能：1) 所有回覆都是 YES，則發送 PreCommit 請求消息，要求所有參與者執行事務並追加記錄到 undo 和 redo 日誌，如果事務執行成功則參與者回覆 ACK 響應消息，並等待下一階段的指令；2) 反饋消息中只要有一個 NO，或者等待超時之後協調者都沒有收到參與者的回覆，那麼協調者會中止事務，發送 Abort 請求消息給所有參與者，參與者收到該請求後中止本地事務，或者參與者超時等待仍未收到協調者的消息，同樣也中止當前本地事務。

  3. DoCommit 階段：協調者根據上一階段收集到的反饋決定通知各個參與者節點提交或回滾本地事務，分三種情況：1) 協調者收到全部參與者回覆的 ACK，則向所有參與者節點廣播 DoCommit 請求消息，各個參與者節點收到協調者的消息之後決定提交事務，然後釋放資源對象上的鎖，成功之後向協調者回復 ACK，協調者接收到所有參與者的 ACK 之後，將該分佈式事務標記爲 committed；2) 協調者沒有收到全部參與者回覆的 ACK（可能參與者回覆的不是 ACK，也可能是消息丟失導致超時），那麼協調者就會中止事務，首先向所有參與者節點廣播 Abort 請求消息，各個參與者收到該消息後利用上一階段的 undo 日誌進行事務的回滾，釋放佔用的資源對象，然後回覆協調者 ACK 消息，協調者收到參與者的 ACK 消息後將該分佈式事務標記爲 aborted；3) 參與者一直沒有收到協調者的消息，等待超時之後會直接提交事務。

事實上，在最後階段，協調者不是通過追加本地日誌的方式記錄提交決定的，而是首先保證讓至少 K 個參與者節點知道它決定提交該分佈式事務。如果協調者發生故障了，那麼剩下的參與者節點會重新選舉一個新的協調者，這個新的協調者就可以在集羣中不超過 K 個參與者節點故障的情況下學習到舊協調者之前是否已經決定要提交分佈式事務，若是，則重新開始協議的第三階段，否則就中止該事務，重新發起分佈式事務。

在最後的 DoCommit 階段，如果參與者一直沒有收到協調者的 DoCommit 或者 Abort 請求消息時，會在等待超時之後，直接提交事務。這個決策機制是基於概率學的：當已經進入第三階段之後，說明參與者在第二階段已經收到了 PreCommit 請求消息，而協調者發出 PreCommit 請求的前提條件是它在第二階段開頭收集到的第一階段向所有參與者發出的 CanCommit 請求消息的反饋消息都是 YES。所以參與者可以根據自己收到了 PreCommit 請求消息這一既定事實得出這樣的一個結論：其他所有參與者都同意了進行這次的事務執行，因此當前的參與者節點有理由相信，進入第三階段後，其他參與者節點的本地事務最後成功提交的概率很大，而自己遲遲沒有收到 DoCommit 或 Abort 消息可能僅僅是因爲網絡抖動或異常，因此直接提交自己的本地事務是一個比較合理的選擇。

三階段提交協議主要着重於解決兩階段提交協議中因爲協調者單點故障而引發的同步阻塞問題，雖然相較於兩階段提交協議有所優化，但還是沒解決可能發生的數據不一致問題，比如由於網絡異常導致部分參與者節點沒有收到協調者的 Abort 請求消息，超時之後這部分參與者會直接提交事務，從而導致集羣中的數據不一致，另外三階段提交協議也無法解決腦裂問題，同時也因爲這個協議的網絡開銷問題，導致它並沒有被廣泛地使用，有關該協議的具體細節可以參閱本文最後的延伸閱讀一節中的文獻進一步瞭解，這裏不再深入。

共識算法

共識（Consensus），很多時候會見到與一致性（Consistency）術語放在一起討論。嚴謹地講，兩者的含義並不完全相同。

一致性的含義比共識寬泛，在不同場景（基於事務的數據庫、分佈式系統等）下意義不同。具體到分佈式系統場景下，一致性指的是多個副本對外呈現的狀態。如前面提到的順序一致性、線性一致性，描述了多節點對數據狀態的共同維護能力。而共識，則特指在分佈式系統中多個節點之間對某個事情（例如多個事務請求，先執行誰？）達成一致意見的過程。因此，達成某種共識並不意味着就保障了一致性。

實踐中，要保證系統滿足不同程度的一致性，往往需要通過共識算法來達成。

共識算法解決的是分佈式系統對某個提案（Proposal），大部分節點達成一致意見的過程。提案的含義在分佈式系統中十分寬泛，如多個事件發生的順序、某個鍵對應的值、誰是主節點…… 等等。可以認爲任何可以達成一致的信息都是一個提案。

對於分佈式系統來講，各個節點通常都是相同的確定性狀態機模型（又稱爲狀態機複製問題，State-Machine Replication），從相同初始狀態開始接收相同順序的指令，則可以保證相同的結果狀態。因此，系統中多個節點最關鍵的是對多個事件的順序進行共識，即排序。

算法共識 / 一致性算法有兩個最核心的約束：1) 安全性（Safety），2) 存活性（Liveness）：

Paxos

Google Chubby 的作者 Mike Burrows 說過， there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.

意即世上只有一種共識算法，那就是 Paxos，其他所有的共識算法都只是 Paxos 算法的殘缺版本。雖然有點武斷，但是自從 Paxos 問世以來，它便幾乎成爲了分佈式共識算法的代名詞，後來的許多應用廣泛的分佈式共識算法如 Raft、Zab 等的原理和思想都可以溯源至 Paxos 算法。

Paxos 是由 Leslie Lamport (LaTeX 發明者，圖靈獎得主，分佈式領域的世界級大師) 在 1990 年的論文《The PartTime Parliament》裏提出的，Lamport 在論文中以一個古希臘的 Paxos 小島上的議會制訂法律的故事切入，引出了 Paxos 分佈式共識算法。

Basic Paxos

業界一般將 Lamport 論文裏最初提出分佈式算法稱之爲 Basic Paxos，這是 Paxos 最基礎的算法思想。

Basic Paxos 算法的最終目標是通過嚴謹和可靠的流程來使得集羣基於某個提案（Proposal）達到最終的共識。

基礎概念

Proposal 中的 Value 就是在 Paxos 算法完成之後需要達成共識的值。

Paxos 算法中有三個核心角色：

在具體的工程實踐中，一個節點往往會充當多種角色，比如一個節點可以既是 Proposer 又是 Acceptor，甚至還是 Learner。

算法流程

相較於直接給出 Paxos 算法的流程，我想沿襲 Lamport 大師的經典 Paxos 論文《Paxos Made Simple》中的思路：通過循序漸進的方式推導出 Paxos 算法。

首先需要了解 Paxos 算法中的兩個重要的約束：

C1. 一個 Acceptor 必須接受它收到的第一個提案。

C2. 只有當超過半數的 Acceptors 接受某一個提案，才能最終選定該提案。

C2 其實有一個隱含的推論：一個 Acceptor 可以接受多個提案，這也是爲什麼我們需要給每一個提案生成一個編號的原因，用來給提案排序。

我們前面提到過 Paxos 的最終目標是通過嚴謹和可靠的流程來使得集羣基於某個提案（Proposal）達到最終的共識，也就是說基於某一個提案發起的一次 Paxos 流程，最終目的是希望集羣對該提案達成一致的意見，而爲了實現並維持集羣中的這種一致性，前提是 Paxos 算法必須具有冪等性：一旦提案（Proposal）中的值（Value）被選定（Chosen），那麼只要還在此次 Paxos 流程中，就算不斷按照 Paxos 的規則重複步驟，未來被 Chosen 的 Value 都會是同一個。如果不滿足這種冪等性，將可能導致不一致的問題。

因此，我們可以把 Paxos 的基本命題提煉出來：

P1. 在一次 Paxos 流程中，如果一個值（Value）爲 v 的提案（Proposal）被選定（Chosen）了，那麼後續任何被最終選定的帶有更大編號（Number）的提案中的 Value 也必須是 v。

提案在被最終選定之前必須先被 Acceptor 接受，於是我們可以再進一步總結一個具有更強約束的命題：

P2. 在一次 Paxos 流程中，如果一個值（Value）爲 v 的提案（Proposal）被選定（Chosen）了，那麼後續任何被 Acceptor 接受的帶有更大編號（Number）的提案中的 Value 也必須是 v。

這還不是具備最強約束的命題，因爲提案在被 Acceptor 接受之前必須先由 Proposer 提出，因此還可以繼續強化命題：

P3. 在一次 Paxos 流程中，如果一個值（Value）爲 v 的提案（Proposal）被選定（Chosen）了，那麼後續任何 Proposer 提議的帶有更大編號（Number）的提案中的 Value 也必須是 v。

從上述的三個命題，我們可以很容易地看出來，P3 可以推導出 P2，進而推導出 P1，也就是說這是一個歸約的過程，因此只要 P3 成立則 P1 成立，也就是 Paxos 算法的正確性得到保證。

那麼要如何實現呢 P3 呢？只需滿足如下約束：

C3. 對於一個被 Proposer 提議的提案中任意的 v 和 n，存在一個數量超過半數 Acceptors 的集合 S，滿足以下兩個條件中的任意一個：

  • S 中的任何一個 Acceptor 都沒有接受過編號小於 n 的提案。

  • S 中所有的 Acceptors 接受過的最大編號的提案的 Value 爲 v。

爲了滿足 C3 從而實現 P3，需要引入一條約束：Proposer 每次生成自己的 n 之後，發起提案之前，必須要先去『學習』那個已經被選定或者將要被選定的小於 n 的提案，如果有這個提案的話則把那個提案的 v 作爲自己的此次提案的 Value，沒有的話纔可以自己指定一個 Value，這樣的話 Proposer 側就可以保證更高編號的提案的值只會是已選定的 v 了，但是 Acceptor 側還無法保證，因爲 Acceptor 有可能還會接受其他的 Proposers 的提案值，於是我們需要對 Acceptor 也加一條約束，讓它承諾在收到編號爲 n 的 v 之後，不會再接受新的編號小於 n 的提案值。

所以我們可以得到一個 Paxos 在 Proposer 側的算法流程：

  1. Proposer 生成一個新的提案編號 n 然後發送一個 prepare 請求給超過半數的 Acceptors 集合，要求集合中的每一個 Acceptor 做出如下響應：

    (a) 向 Proposer 承諾在收到該消息之後就不再接受編號小於 n 的提案。

    (b) 如果 Acceptor 在收到該消息之前已經接受過其他提案，則把當前接受的編號最大的提案回覆給 Proposer。

  2. 如果 Proposer 收到了超過半數的 Acceptors 的回覆，那麼就可以生成 (n, v) 的提案，這裏 v 是所有 Acceptors 回覆中編號最大的那個提案裏的值，如果所有 Acceptors 回覆中都沒有附帶上提案的話，則可以由 Proposer 自己選擇一個 v。

  3. Proposer 將上面生成的提案通過一個 accept 請求發送給一個超過半數的 Acceptors 集合。（需要注意的是這個集合不一定和第二步中的那個集合是同一個。）

Paxos 在 Proposer 側的算法流程已經確定了，接下來我們需要從 Acceptor 的視角來完成剩下的算法推導。前面我們提到過，Acceptor 是可以接受多個 Proposers 的多個提案的，但是在收到一個 Proposer 的 prepare 消息後會承諾不再接受編號小於 n 的新提案，也就是說 Acceptor 也是可以忽略掉其他 Proposers 消息（包括 prepare 和 accept）而不會破壞算法的安全性，當然了，在工程實踐中也可以直接回復一個錯誤，讓 Proposer 更早知道提案被拒絕然後生成提案重新開始流程。這裏我們應該重點思考的場景是一個 Acceptor 接受一個提案請求的時候，根據前面 Proposer 要求 Acceptor 的承諾，我們可以給 Acceptor 設置一個這樣的約束：

C4. 如果一個 Proposer 發出了帶 n 的 prepare 請求，只要 Acceptor 還沒有回覆過任何其他編號大於 n 的 prepare 請求，則該 Acceptor 可以接受這個提案。

因爲 Acceptor 需要對 Proposer 做出不接受編號小於 n 的提案的承諾，因此它需要做持久化記錄，那麼它就必須是有狀態的，也因此每個 Acceptor 都需要利用可靠性存儲（日誌）來保存兩個對象：

  1. Acceptor 接受過的編號最大的提案；

  2. Acceptor 回覆過的最大的 prepare 請求提案編號。

以上這就是 Acceptor 側的約束。接下來我們就可以得到 Paxos 的整個算法流程了。

Paxos 算法可以歸納爲兩大基本過程：

  1. 選擇過程；

  2. 學習過程。

選擇過程

選擇過程分爲兩個階段：

學習過程

選擇過程結束之後，我們得到了一個提案值，接下來就是要讓集羣中的所有 Learner 『學習』到這個值了，以求達到集羣的共識。

Learner 學習提案值的方式可以分成三種：

  1. 任意一個 Acceptor 接受了一個提案後就立刻將該提案發送給所有 Learner。優點：Learner 能實時學習到被 Paxos 流程選定的 Value；缺點：網絡通信次數太多，如果有 N 個 Acceptors 和 M 個 Learner，則需要的網絡通信是 N*M 次。

  2. 設置一個主 Learner，Acceptor 接受了一個提案後只將該提案發送給主 Learner，主 Learner 再轉發給剩下的 Learners。優點：網絡通信次數只需 N+M-1 次；缺點：主 Learner 有單點故障的風險。

  3. Acceptor 接受了一個提案後將該提案發送給一個 Learner 集合，由這個集合去通知剩下的 Learners。優點：用集合替代單點，可靠性更高；缺點：增加系統複雜度，需要維護一個 Learner 小集羣。

至此，我們就推導出了整個 Paxos 算法的流程：

算法證明

這一節我們來證明 Paxos 算法的正確性。

上一節我們已經提煉出來了 Paxos 的基本命題 P1，並通過歸約 P1 得到了約束性更強的另外兩個命題 P2 和 P3，根據歸約的原理，我們知道 P3 可以最終推導出 P1，也就是說如果要證明 Paxos 的基本命題 P1，只需要證明 P3 即可。爲什麼之前我們要不斷強化 Paxos 的命題呢？因爲從數學的層面來講，一個具有更強約束（更多假設）的命題一般會更容易證明。

現在我們把 P1, P2 和 P3 用更嚴格的數學語言來描述：

P1. 在一次 Paxos 流程中，如果一個包含 (n, v) 的提案被選定（Chosen），那麼存在未來被選定的提案 (k, v1)，必然滿足 k > n，v1 = v。

P2. 在一次 Paxos 流程中，如果一個包含 (n, v) 的提案被選定（Chosen），那麼存在未來被超過半數的 Acceptors 接受的提案 (k, v1)，必然滿足 k > n，v1 = v。

P3. 在一次 Paxos 流程中，如果一個包含 (n, v) 的提案被選定（Chosen），那麼存在未來由 Proposer 提議的提案 (k, v1)，必然滿足 k > n，v1 = v。

現在我們利用數學歸納法來證明 P3：

假設 k = m 時 P3 成立，由於 (n, v) 已經是被選定的提案，因此 Proposer 發起的從 n 到 k 的提案中的 Value 都會是 v，其中 m >= n，那麼根據歸約的原理可證 k = m 時 P1 也成立。

現在令 k = m+1，Proposer 發送帶編號 k 的 prepare 請求消息到 Acceptors 集合。

由於此前已經有了選定的提案，那麼根據 Paxos 的約束 C2 可知參與這一個提案投票的 Acceptors 集合必定和上一個集合有重合。

根據 Acceptors 集合重疊和 Paxos 的 P1b 階段可知，回覆的消息中必定附帶有已被大多數 Acceptors 接受的提案 (i, v0)。

然後根據 P2a 階段，Proposer 提案 (k, v1)，其中 v1 = v0。

還是根據 P1b，可知 i 是所有回覆消息裏編號最大的，可得 i >= m，又根據 P1a 可知 i <k，因此可以得出提案 (i, v0) 中有 v0 = v。

可知當 k = m+1 時，提案 (k, v1) 中的 v1 = v。

根據數學歸納法的原理，我們還需要找到一個特例來使得命題成立，然後由特例推廣到普遍，我們這裏選擇 k = 1 作爲特例，證明 k = 1 時 P3 成立：根據 Paxos 的約束 C1 易知在 n = 0，k = 1 的場景下，P3 成立。

因此可根據數學歸納法基於 k = 1 進行推廣至 k = m（m 代表任意自然數），最後 P3 命題得證。

再由歸約的原理可知，P3 可推導出 P2，最後 P2 推導出 P1。至此， Paxos 算法原理正確性的證明完成。

上述的證明只是一種比較簡單且粗淺的證明方法，但是對於工程師理解 Paxos 原理來說已經足夠了，如果希望進一步學習 Paxos 原理的嚴格數學證明，可以參閱 Leslie Lamport 的原始論文《The PartTime Parliament》，裏面給出了 Paxos 算法的嚴格數學證明。

Multi-Paxos

自 Lamport 於 1990 年在論文《The PartTime Parliament》中提出 Paxos 算法之後，這個算法一直被評價爲難以理解和實現，這篇論文中運用了大量的數學對 Paxos 的原理進行證明，而又由於 Lamport 在論文裏用講故事的形式解釋 Paxos，進一步增大了人們徹底理解 Paxos 的難度，事實上 Lamport 的這篇論文也因此在發表過程中一波三折，這裏不展開，有興趣的讀者可以自行去了解這段這段背景故事。

因爲業界在理解 Paxos 算法上持續的怨聲載道，Lamport 在 2001 年發表了論文《Paxos Made Simple》，對原論文進行精簡，以更通俗易懂的語言和形式闡述 Paxos 算法，並在其中提出了更加具備工程實踐性的 Multi-Paxos 的思想。

關於 Paxos 難以理解的問題上，我個人的一點愚見是：Paxos 算法的思想其實並不難理解，真正難的地方是：

  1. Paxos 背後那一套完整的數學原理和證明

  2. 在複雜分佈式環境將 Paxos 進行工程落地

我個人建議的 Paxos 學習資料是：《Paxos Made Simple》，《Paxos Made Live - An Engineering Perspective》以及 Paxos lecture (Raft user study)。第一篇論文可以說是 Lamport  1990 年那篇最初的論文的精簡版，可讀性提高了很多，論文裏也沒有使用任何數學公式，只需一點英文基礎就可以通讀，第二篇論文講的則是 Google 內部基於 Multi-Paxos 實現的分佈式鎖機制和小文件存儲系統，這是業界較早的實現了 Multi-Paxos 的大規模線上系統，十分具有參考性，最後的 Youtube 視頻則是 Raft 的作者 Diego Ongaro 爲了對比 Raft 和 Multi-Paxos 的學習的難易程度而做的，非常適合作爲學習 Paxos 和 Raft 的入門資料。

從上一節可知 Basic Paxos 算法有幾個天然缺陷：

關於第三點，前文提到分佈式共識算法必須滿足兩個最核心的約束：安全性（safety）和活性（liveness），從上一節我們可以看出 Basic Paxos 主要着重於 safety，而對 liveness 並沒有進行強約束，讓我們設想一種場景：兩個 Proposers (記爲 P1 和 P2) 輪替着發起提案，導致兩個 Paxos 流程重疊了：

  1. 首先，P1 發送編號 N1 的 prepare 請求到 Acceptors 集合，收到了過半的回覆，完成階段一。

  2. 緊接着 P2 也進入階段一，發送編號 N2 的 prepare 請求到過半的 Acceptors 集合，也收到了過半的回覆，Acceptors 集合承諾不再接受編號小於 N2 的提案。

  3. 然後 P1 進入階段二，發送編號 N1 的 accept 請求被 Acceptors 忽略，於是 P1 重新進入階段一發送編號 N3 的 prepare 請求到 Acceptors 集合，Acceptors 又承諾不再接受編號小於 N3 的提案。

  4. 緊接着 P2 進入階段二，發送編號 N2 的 accept 請求，又被 Acceptors 忽略。

  5. 不斷重複上面的過程......

在極端情況下，這個過程會永遠持續，導致所謂的『活鎖』，永遠無法選定一個提案，也就是 liveness 約束無法滿足。

爲了解決這些問題，Lamport 在《Paxos Made Simple》論文中提出了一種基於 Basic Paxos 的 Multi-Paxos 算法思想，並基於該算法引出了一個分佈式銀行系統狀態機的實現方案，感興趣的讀者不妨看一下。

Multi-Paxos 算法在 Basic Paxos 的基礎上做了兩點改進：

  1. 多 Paxos 實例：針對每一個需要達成共識的單值都運行一次 Basic Paxos 算法的實例，並使用 Instance ID 做標識，最後彙總完成多值共識。

  2. 選舉單一的 Leader Proposer：選舉出一個 Leader Proposer，所有提案只能由 Leader Proposer 來發起並決策，Leader Proposer 作爲 Paxos 算法流程中唯一的提案發起者，『活鎖』將不復存在。此外，由於單一 Proposer 不存在提案競爭的問題，Paxos 算法流程中的階段一中的 prepare 步驟也可以省略掉，從而將兩階段流程變成一階段，大大減少網絡通信次數。

關於多值共識的優化，如果每一個 Basic Paxos 算法實例都設置一個 Leader Proposer 來工作，還是會產生大量的網絡通信開銷，因此，多個 Paxos 實例可以共享同一個 Leader Proposer，這要求該 Leader Proposer 必須是穩定的，也即 Leader 不應該在 Paxos 流程中崩潰或改變。

由於 Lamport 在論文中提出的 Multi-Paxos 只是一種思想而非一個具體算法，因此關於 Multi-Paxos 的很多細節他並沒有給出具體的實現方案，有些即便給出了方案也描述得不是很清楚，比如他在論文中最後一節提出的基於銀行系統的狀態機中的多 Paxos 實例處理，雖然給了具體的論述，但是在很多關鍵地方還是沒有指明，這也導致了後續業界裏的 Multi-Paxos 實現各不相同。

我們這裏用 Google Chubby 的 Multi-Paxos 實現來分析這個算法。

首先，Chubby 通過引入 Master 節點，實現了 Lamport 在論文中提到的 single distinguished proposer，也就是 Leader Proposer，Leader Proposer 作爲 Paxos 算法流程中唯一的提案發起者，規避了多 Proposers 同時發起提案的場景，也就不存在提案衝突的情況了，從而解決了『活鎖』的問題，保證了算法的活性（liveness）。

Lamport 在論文中指出，選擇 Leader Proposer 的過程必須是可靠的，那麼具體如何選擇一個 Leader Proposer 呢？在 Chubby 中，集羣利用 Basic Paxos 算法的共識功能來完成對 Leader Proposer 的選舉，這個實現是具有天然合理性的，因爲 Basic Paxos 本身就是一個非常可靠而且經過嚴格數學證明的共識算法，用來作爲選舉算法再合適不過了，在 Multi-Paxos 流程期間，Master 會通過不斷續租的方式來延長租期（Lease）。比如在實際場景中，一般在長達幾天的時期內都是同一個服務器節點作爲 Master。萬一 Master 故障了，那麼剩下的 Slaves 節點會重新發起 Paxos 流程票選出新的 Master，也就是說主節點是一直存在的，而且是唯一的。

此外，Lamport 在論文中提到的過一種優化網絡通信的方法：“當 Leader Proposer 處於穩定狀態時，可以跳過階段一，直接進入階段二”，在 Chubby 中也實現了這個優化機制，Leader  Proposer 在爲多個 Paxos 算法實例服務的時候直接跳過階段一進入階段二，只發送 accept 請求消息給 Acceptors 集合，將算法從兩階段優化成了一階段，大大節省網絡帶寬和提升系統性能。

最後，Multi-Paxos 是一個 "腦裂" 容錯的算法思想，就是說當 Multi-Paxos 流程中因爲網絡問題而出現多 Leaders 的情況下，該算法的安全性（safety ）約束依然能得到保證，因爲在這種情況下，Multi-Paxos 實際上是退化成了 Basic Paxos，而 Basic Paxos 天然就支持多 Proposers。

在分佈式事務中，Paxos 算法能夠提供比兩階段提交協議更加可靠的一致性提交：通過將提交 / 放棄事務的決定從原來兩階段協議中單一的協調者轉移到一個由 Proposer + Acceptors 組成的集羣中。Lamport 曾經發表過一篇《Consensus on Transaction Commit》的論文，通過將兩階段提交協議和基於 Paxos 實現的分佈式提交協議做對比，對基於 Paxos 實現的提交協議有非常精彩的論述，感興趣的讀者不妨一讀。

Raft

Raft 算法實際上是 Multi-Paxos 的一個變種，通過新增兩個約束：

  1. 追加日誌約束：Raft 中追加節點的日誌必須是串行連續的，而 Multi-Paxos 中則可以併發追加日誌（實際上 Multi-Paxos 的併發也只是針對日誌追加，最後應用到內部 State Machine 的時候還是必須保證順序）。

  2. 選主限制：Raft 中只有那些擁有最新、最全日誌的節點才能當選 Leader 節點，而 Multi-Paxos 由於允許併發寫日誌，因此無法確定一個擁有最新、最全日誌的節點，因此可以選擇任意一個節點作爲 Leader，但是選主之後必須要把 Leader 節點的日誌補全。

基於這兩個限制，Raft 算法的實現比 Multi-Paxos 更加簡單易懂，不過由於 Multi-Paxos 的併發度更高，因此從理論上來說 Multi-Paxos 的性能會更好一些，但是到現在爲止業界也沒有一份權威的測試報告來支撐這一觀點。

對比一下 Multi-Paxos 和 Raft 下集羣中可能存在的日誌順序：

可以看出，Raft 中永遠滿足這樣一個約束：follower log 一定會是 leader log 的子集並且順序一定是連續的，而 Multi-Paxos 則不一定滿足這個約束，日誌記錄通常是亂序的。

由於 Raft 的核心思想源自 Multi-Paxos，在實現過程中做了很多改進優化，然而萬變不離其宗，我相信理解了 Multi-Paxos 之後再去學習 Raft 會事半功倍（Raft 在誕生之初也是打着 "容易理解" 的旗號來對標 Paxos 的），由於前面已經深度剖析過 Paxos 算法的流程和原理了，礙於本文的篇幅所限，這裏就不再對 Raft 算法的細節進行深入探討了，如果有意深入學習 Raft，可以從 The Raft Consensus Algorithm 處找到相關的論文、源碼等資料進行全面的學習。

最後有一些概念要澄清一下，Basic Paxos 是一個經過了嚴格數學證明的分佈式共識算法，但是由於前文提到的 Basic Paxos 算法應用在實際工程落地中的種種問題，現實中幾乎沒有直接基於 Basic Paxos 算法實現的分佈式系統，絕大多數都是基於 Multi-Paxos，然而 Multi-Basic 僅僅是一種對 Basic Paxos 的延伸思想而非一個具體算法，問題在於目前業界並沒有一個統一的 Multi-Paxos 實現標準，因此 Multi-Paxos 的工程實現是建立在一個未經嚴格證明的前提之上的，工程實現最終的正確性只能靠實現方自己去驗證，而 Raft 則是一個具有統一標準實現的、正確性已經過嚴格證明的具體算法，因此在分佈式系統的工程實踐中大多數人往往還是會選擇 Raft 作爲底層的共識算法。

算法類型

需要特別指出的一點是，根據解決的場景是否允許拜占庭（Byzantine）錯誤，共識算法可以分爲 Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance（BFT）兩類。

對於非拜占庭錯誤的情況，已經存在不少經典的算法，包括 Paxos（1990 年）、Raft（2014 年）及其變種等。這類容錯算法往往性能比較好，處理較快，容忍不超過一半的故障節點。

對於要能容忍拜占庭錯誤的情況，包括 PBFT（Practical Byzantine Fault Tolerance，1999 年）爲代表的確定性系列算法、PoW（1997 年）爲代表的概率算法等。確定性算法一旦達成共識就不可逆轉，即共識是最終結果；而概率類算法的共識結果則是臨時的，隨着時間推移或某種強化，共識結果被推翻的概率越來越小，最終成爲事實上結果。拜占庭類容錯算法往往性能較差，容忍不超過 1/3 的故障節點。

本文主要討論的分佈式共識算法是 CFT 類算法，畢竟對於大多數分佈式系統來說，集羣節點和網絡消息一般都是可控的，系統只會出現節點故障而不會出現像拜占庭錯誤那樣僞造的、欺騙性的網絡消息，在這種場景下，CFT 類算法更具有現實意義；BFT/PBFT 類算法更多是用在系統被惡意入侵，故意僞造網絡消息的場景裏。

併發控制

在分佈式事務中，集羣中的每個服務器節點要管理很多資源對象，每個節點必須保證在併發事務訪問這些資源對象時，它們能夠始終保持一致性。因此，每個服務器節點需要對自己的管理的資源對象應用一定的併發控制機制。分佈式事務中需要所有服務器節點共同保證事務以串行等價的的方式執行。

也就是說，如果事務 T 對某一個服務器節點上的資源對象 S 的併發訪問在事務 U 之前，那麼我們需要保證在所有服務器節點上對 S 和其他資源對象的衝突訪問，T 始終在 U 之前。

鎖併發控制

在分佈式事務中，某個對象的鎖總是本地持有的（在同一個服務器節點上）。是否加鎖是由本地鎖管理器（Local Lock Manager，LLM）決定的。LLM 決定是滿足客戶端持鎖的請求，還是阻塞客戶端發起的分佈式事務。但是，事務在所有服務器節點上被提交或者放棄之前，LLM 不能釋放任何鎖。在使用加鎖機制的併發控制中，原子提交協議在進行的過程中資源對象始終被鎖住，並且是排他鎖，其他事務無法染指這些資源對象。但如果事務在兩階段提交協議的階段一就被放棄，則互斥鎖可以提前釋放。

由於不同服務器節點上的 LLM 獨立設置資源對象鎖，因此，對於不同的事務，它們加鎖的順序也可能出現不一致。考慮一個場景：事務 T 和 U 在服務器 X 和 Y 之間的交錯執行：

  1. 事務 T 鎖住了服務器節點 X 上的資源對象 A，做寫入操作；

  2. 事務 U 鎖住了服務器節點 Y 上的資源對象 B，做寫入操作；

  3. 事務 T 試圖讀取服務器節點 Y 上的資源對象 B，此時 B 被事務 U 鎖住，因此 T 等待鎖釋放；

  4. 事務 U 試圖讀取服務器節點 X 上的資源對象 A，此時 A 被事務 T 鎖住，因此 U 等待鎖釋放。

在服務器節點 X 上，事務 T 在事務 U 之前；而在服務器節點 Y 上，事務 U 在事務 T 之前。這種不一致的事務次序導致了事務之間的循環依賴，從而引起分佈式死鎖。分佈式死鎖需要通過特定的方法 / 算法來檢測並解除，一旦檢測到死鎖，則必須放棄其中的某個事務來解除死鎖，然後通知事務協調者，它將會放棄該事務所涉及的所有參與者上的事務。

時間戳併發控制

對於單一服務器節點的事務來說，協調者在每個事務啓動時會爲其分配一個全局唯一的時間戳。通過按照訪問資源對象的事務時間戳順序提交資源對象的版本來強制保證以事務執行的串行等價性。在分佈式事務中，協調者必須保證每個事務都會附帶全局唯一的時間戳。全局唯一的時間戳由事務訪問的第一個協調者發給客戶端。如果任意一個服務器節點上的資源對象執行了事務中的一個操作，那麼事務時間戳會被髮送給該服務器節點上的協調者。

分佈式事務中的所有服務器節點共同保證事務以串行等價的方式執行。例如，如果在某服務器節點上，由事務 U 訪問的資源對象版本在事務 T 訪問之後提交；而在另一個服務器節點上，事務 T 和事務 U 又訪問了同一個資源對象，那麼它們也必須按照相同的次序提交資源對象。爲了保證所有服務器節點上的事務執行的相同順序，協調者必須就時間戳排序達成一致。時間戳是一個二元組 <本地時間戳，服務器 ID> 對。在時間戳的比較排序過程中，首先比較本地時間戳，然後再比較服務器 ID。

一個可靠的時間戳併發控制應該保證即使各個服務器節點之間的本地時間不同步，也能保證事務之間的相同順序。但是考慮到效率，各個協調者之間的時間戳還是最好還是要求大致同步。這樣的話，事務之間的順序通常與它們實際開始的時間順序相一致。可以利用一些本地物理時鐘同步方法來保證時間戳的大致同步。

如果決定利用時間戳機制進行分佈式事務的併發控制，那麼還需要通過某些方法來解決事務衝突問題。如果爲了解決衝突需要放棄某個事務時，相應的協調者會收到通知，並且它將在所有的參與者上放棄該事務。這樣，如果事務能夠堅持到客戶端發起提交請求命令的那個時候，那麼這個事務就總能被提交。因此在兩階段提交協議中，正常情況下參與者都會同意提交，唯一一種不同意提交的情況是參與者在事務執行過程中曾經崩潰過。

樂觀併發控制

加鎖機制這一類悲觀併發控制有許多明顯的缺陷：

由於鎖這一類的悲觀併發控制有上述的種種弊端，因此研究者們提出了另一種樂觀併發控制的機制，以求規避鎖機制的天然缺陷，研究者們發現這樣的一個現象：在大多數應用中兩個客戶端事務訪問同一個資源對象的可能性其實很低，事務總是能夠成功執行，就好像事務之間不存在衝突一樣。

所以事務的樂觀併發控制的基本思路就是：各個併發事務只有在執行完成之後並且發出 closeTransaction 請求時，再去檢測是否有衝突，如果確實存在衝突，那麼就放棄一些事務，然後讓客戶端重新啓動這些事務進行重試。

在樂觀併發控制中，每個事務在提交之前都必須進行驗證。事務在驗證開始時首先要附加一個事務號，事務的串行化就是根據這些事務號的順序實現的。分佈式事務的驗證由一組獨立的服務器節點共同完成，每個服務器節點驗證訪問自己資源對象的事務。這些驗證在兩階段提交協議的第一個階段進行。

關於分佈式事務的併發控制就暫時介紹到這裏，如果想要繼續深入學習更多併發控制的細節，可以深入閱讀《分佈式系統：概念與設計》、《數據庫系統實現》和《數據庫系統概念》等書籍或者其他資料。

總結

本文通過講解 BASE 原則、兩階段原子提交協議、三階段原子提交協議、Paxos/Multi-Paxos 分佈式共識算法的原理與證明、Raft 分佈式共識算法和分佈式事務的併發控制等內容，爲讀者全面而又深入地講解分析了分佈式事務 / 系統的底層核心原理，特別是通過對原子提交協議中的 2PC/3PC 的闡述和分析，以及對分佈式共識算法 Paxos 的原理剖析和正確性的證明，最後還有對分佈式事務中幾種併發控制的介紹，相信能夠讓讀者對分佈式事務 / 系統底層的一致性和併發控制原理有一個深刻的認知，對以後學習和理解分佈式系統大有裨益。

本文不僅僅是簡單地介紹分佈式事務和分佈式系統的底層原理，更是在介紹原理的同時，通過層層遞進的方式引導讀者去真正地理解分佈式系統的底層原理和設計思路，而非讓讀者死記硬背一些概念，所以希望通過這篇拋磚引玉的文章，能夠對本文讀者在以後學習、操作甚至是設計分佈式系統以及分佈式事務時的思路有所開拓。

參考 & 延伸

References

[1] DTP Model: http://pubs.opengroup.org/onlinepubs/009680699/toc.pdf
[2] 《The PartTime Parliament》: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[3] 《Paxos Made Simple》: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[4] 歸約: https://zh.wikipedia.org/wiki/%E6%AD%B8%E7%B4%84
[5] 《The PartTime Parliament》: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[6] 《The PartTime Parliament》: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[7] 《Paxos Made Simple》: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[8] 《Paxos Made Simple》: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[9] 《Paxos Made Live - An Engineering Perspective》: https://read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf
[10] Paxos lecture (Raft user study): https://www.youtube.com/watch?v=JEpsBg0AO6o
[11] 《Paxos Made Simple》: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[12] 《Consensus on Transaction Commit》: https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf
[13] The Raft Consensus Algorithm: https://raft.github.io
[14] ACID: https://en.wikipedia.org/wiki/ACID
[15] Eventual consistency: https://en.wikipedia.org/wiki/Eventual_consistency
[16] Atomic commit: https://en.wikipedia.org/wiki/Atomic_commit
[17] A Two-Phase Commit Protocol and its Performance : https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=558282
[18] The PartTime Parliament: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[19] Paxos Made Simple: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[20] Fast Paxos: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005-112.pdf
[21] The Performance of Paxos and Fast Paxos: https://arxiv.org/pdf/1308.1358.pdf
[22] Paxos Made Live - An Engineering Perspective: https://read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf
[23] Paxos (computer science): https://en.wikipedia.org/wiki/Paxos(computer_science)_
[24] The Chubby lock service for loosely-coupled distributed systems: _https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/chubby-osdi06.pdf_
[25] Consensus on Transaction Commit: _https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf_
[26] Life beyond Distributed Transactions: an Apostate’s Opinion: _https://www.ics.uci.edu/~cs223/papers/cidr07p15.pdf_
[27] In Search of an Understandable Consensus Algorithm: _https://raft.github.io/raft.pdf_
[28] Paxos lecture (Raft user study): _https://www.youtube.com/watch?v=JEpsBg0AO6o_
[29] Distributed Systems: Concepts and Design: _https://ce.guilan.ac.ir/images/other/soft/distribdystems.pdf_
[30] How to Build a Highly Available System Using Consensus: _https://www.microsoft.com/en-us/research/uploads/prod/1996/10/Acrobat-58-Copy.pdf_
[31] 數學歸納法: _https://zh.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95_
[32] 共識算法: _https://yeasy.gitbook.io/blockchain_guide/04_distributed_system/algorithms_
[33] Distributed Transaction Processing: The XA Specification: _https://pubs.opengroup.org/onlinepubs/009680699/toc.pdf_

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/cCvdNtuvrn0y9g-92f64DA

猜你喜歡