分布式之系统底层原理
作者：allanpan，騰訊 IEG 高級后臺工程師
導言
分布式事務是分布式系統必不可少的組成部分，基本上只要實現一個分布式系統就逃不開對分布式事務的支持。本文從分布式事務這個概念切入，嘗試對分布式事務以及分布式系統最核心的底層原理逐一進行剖析，內容包括但不限于 BASE 原則、兩階段原子提交協議、三階段原子提交協議、Paxos/Multi-Paxos 分布式共識算法的原理與證明、Raft 分布式共識算法和分布式事務的并發控制等內容。
事務
事務是訪問并可能更新各種數據項的一個程序執行單元(unit)。事務由一個或多個步驟組成，一般使用形如 begin transaction 和 end transaction 語句或者函數調用作為事務界限，事務內的所有步驟必須作為一個單一的、不可分割的單元去執行，因此事務的結果只有兩種：1. 全部步驟都執行完成，2. 任一步驟執行失敗則整個事務回滾。
事務最早由數據庫管理系統(database management system，DBMS)引入并實現，數據庫事務是數據庫管理系統執行過程中的一個邏輯單位，由一個有限的數據庫操作序列構成。數據庫事務嚴格遵循 ACID 原則，屬于剛性事務，一開始數據庫事務僅限于對單一數據庫資源對象的訪問控制，這一類事務稱之為本地事務 (Local Transaction)，后來隨著分布式系統的出現，數據的存儲也不可避免地走向了分布式，分布式事務（Distributed Transaction）便應運而生。
剛性事務
剛性事務（如單一數據庫事務）完全遵循 ACID 規范，即數據庫事務的四大基本特性：
Atomicity（原子性）：一個事務（transaction）中的所有操作，或者全部完成，或者全部不完成，不會結束在中間某個環節。事務在執行過程中發生錯誤，會被回滾（Rollback）到事務開始前的狀態，就像這個事務從來沒有執行過一樣。即，事務不可分割、不可約簡。
Consistency（一致性）：在事務開始之前和事務結束以后，數據庫的完整性沒有被破壞。這表示寫入的資料必須完全符合所有的預設約束、觸發器、級聯回滾等。
Isolation（隔離性）：數據庫允許多個并發事務同時對其數據進行讀寫和修改的能力，隔離性可以防止多個事務并發執行時由于交叉執行而導致數據的不一致。事務隔離分為不同級別，包括未提交讀（Read uncommitted）、提交讀（read committed）、可重復讀（repeatable read）和串行化（Serializable）。
Durability（持久性）：事務處理結束后，對數據的修改就是永久的，即便系統故障也不會丟失。
剛性事務也能夠以分布式 CAP 理論中的 CP 事務來作為定義。
柔性事務
在電商領域等互聯網場景下，傳統的事務在數據庫性能和處理能力上都遇到了瓶頸。因此，柔性事務被提了出來，柔性事務基于分布式 CAP 理論以及延伸出來的 BASE 理論，相較于數據庫事務這一類完全遵循 ACID 的剛性事務來說，柔性事務保證的是 “基本可用，最終一致”，CAP 原理相信大家都很熟悉了，這里我們講一下 BASE 原則：
基本可用（Basically Available）：系統能夠基本運行、一直提供服務。
軟狀態（Soft-state）：系統不要求一直保持強一致狀態。
最終一致性（Eventual consistency）：系統需要在某一時刻后達到一致性要求。
柔性事務（如分布式事務）為了滿足可用性、性能與降級服務的需要，降低一致性（Consistency）與隔離性（Isolation）的要求，遵循 BASE 理論，傳統的 ACID 事務對隔離性的要求非常高，在事務執行過程中，必須將所有的資源對象鎖定，因此對并發事務的執行極度不友好，柔性事務（比如分布式事務）的理念則是將鎖資源對象操作從本地資源對象層面上移至業務邏輯層面，再通過放寬對強一致性要求，以換取系統吞吐量的提升。
此外，雖然柔性事務遵循的是 BASE 理論，但是還需要遵循部分 ACID 規范：
原子性：嚴格遵循。
一致性：事務完成后的一致性嚴格遵循；事務中的一致性可適當放寬。
隔離性：并行事務間不可影響；事務中間結果可見性允許安全放寬。
持久性：嚴格遵循。
本地事務
本地事務（Local Transaction）指的是僅僅對單一節點/數據庫資源對象進行訪問/更新的事務，在這種事務模式下，BASE 理論派不上用場，事務完全遵循 ACID 規范，確保事務為剛性事務。
分布式事務
在分布式架構成為主流的當下，系統對資源對象的訪問不能還局限于單節點，多服務器、多節點的資源對象訪問成為剛需，因此，本地事務無法滿足分布式架構的系統的要求，分布式事務應運而生。
訪問/更新由多個服務器管理的資源對象的平面事務或者嵌套事務稱之為分布式事務（Distributed Transaction），分布式事務是相對于本地事務來說的。
平面事務：單一事務，訪問多個服務器節點的資源對象，一個平面事務完成一次請求之后才能發起下一個請求。
嵌套事務：多事務組成，頂層事務可以不斷創建子事務，子事務又可以進一步地以任意深度嵌套子事務。
對于分布式事務來說，有兩個最核心的問題：
如何管理分布式事務的提交/放棄決定？如果事務中的一個節點在執行自己的本地事務過程中遇到錯誤，希望放棄整個分布式事務，與此同時其他節點則在事務執行過程中一切順利，希望提交這個分布式事務，此時我們應該如何做決策？
如何保證并發事務在涉及多個節點上資源對象訪問的可串行性（規避分布式死鎖）？如果事務 T 對某一個服務器節點上的資源對象 S 的并發訪問在事務 U 之前，那么我們需要保證在所有服務器節點上對 S 和其他資源對象的沖突訪問，T 始終在 U 之前。
問題 1 的解決需要引入一類分布式原子提交協議的算法如兩階段提交協議等，來對分布式事務過程中的提交或放棄決策進行管理，并確保分布式提交的原子性。而問題 2 則由分布式事務的并發控制機制來處理。
原子提交協議
原子性是分布式事務的前置性約束，沒有原子性則分布式事務毫無意義。
原子性約束要求在分布式事務結束之時，它的所有操作要么全部執行，要么全部不執行。以分布式事務的原子性來分析，客戶端請求訪問/更新多個服務器節點上的資源對象，在客戶端提交或放棄該事務從而結束事務之后，多個服務器節點的最終狀態要么是該事務里的所有步驟都執行成功之后的狀態，要么恢復到事務開始前的狀態，不存在中間狀態。滿足這種約束的分布式事務協議則稱之為原子提交協議。
當一個分布式事務結束時，事務的原子特性要求所有參與該事務的服務器節點必須全部提交或者全部放棄該事務，為了實現這一點，必須引入一個協調者（Coordinator）的角色，從參與事務的所有服務器節點中挑選一個作為協調者，由它來保證在所有服務器節點上最終獲得同樣的結果。協調者的工作原理取決于分布式事務選用的協議。
一般來說，分布式事務中包含的兩個最基礎的角色就是：
Coordinator -- 協調者
Participants -- 參與者
單階段原子提交協議
單階段原子提交協議（one-phase atomic commit protocol, 1APC）是最簡單的一種原子提交協議，它通過設置一個協調者并讓它不斷地向所有參與者發送提交（commit）或放棄（abort）事務的請求，直到所有參與者確認已執行完相應的操作。
1APC 協議的優點是簡單易用，對一些事務不復雜的場景比較合適，但在復雜事務場景則顯得捉襟見肘，因為該協議不允許任何服務器節點單方面放棄事務，事務的放棄必須由協調者來發起，這個設計會導致很多問題：首先因為只有一次通信，協調者并不會收集所有參與者的本地事務執行的情況，所以協調者決定提交還是放棄事務只基于自己的判斷，在參與者執行事務期間可能會遇到錯誤從而導致最終事務未能真正提交，錯誤一般與事務的并發控制有關，比如事務執行期間對資源對象加鎖，遇到死鎖，需要放棄事務從而解開死鎖，而協調者并不知道，因此在發起下一個請求之前，客戶端完全不知道事務已被放棄。另一種情況就是利用樂觀并發控制機制訪問資源對象，某一個服務器節點的驗證失敗將導致事務被放棄，而協調者完全不知情。
兩階段提交協議
定義
兩階段提交協議（two-phase commit protocol, 2PC）的設計初衷是為了解決 1APC 不允許任意一個服務器節點自行放棄它自己的那部分本地事務的痛點，2PC 允許任何一個參與者自行決定要不要放棄它的本地事務，而由于原子提交協議的約束，任意一個本地事務被放棄將導致整個分布式事務也必須放棄掉。
兩階段提交協議基于以下幾個假設：
存在一個節點作為協調者（Coordinator），分布式事務通常由協調者發起（當然也可以由參與者發起），其余節點作為參與者（Participants），且節點之間可以自由地進行網絡通信，協調者負責啟動兩階段提交流程以及決定事務最終是被提交還是放棄。
每個節點會記錄該節點上的本地操作日志（op logs），日志必須持久化在可靠的存儲設備上（比如磁盤），以便在節點重啟之后需要恢復操作日志。另外，不記錄全局操作日志。
所有節點不能發生永久性損壞，也就是說節點就算是損壞了也必須能通過可靠性存儲恢復如初，不允許出現數據永久丟失的情況。
參與者對協調者的回復必須要去除掉那些受損和重復的消息。
整個集群不會出現拜占庭故障（Byzantine Fault）-- 服務器要么崩潰，要么服從其發送的消息。
原理
兩階段提交協議，顧名思義整個過程需要分為兩個階段：
準備階段（Prepare Phase）
提交階段（Commit Phase）
在進行兩階段提交的過程中，協調者會在以下四種狀態間流轉：
init
preparing
committed
aborted
而參與者則會在以下三種狀態間流轉：
working
prepared
committed
階段 I（投票表決階段）
任意一個參與者發起分布式事務 T 并執行本地事務成功，接著將一條 <ready T> 記錄追加到本地日志 buffer 中并 flush 到可靠性存儲設備如磁盤上，從 working 狀態進入 prepared 狀態，然后向協調者發送 prepare T 消息；
收到參與者發來的 prepare T 消息后，協調者將一條 <prepare T> 記錄追加到日志中，然后從 init 狀態進入 preparing 狀態，緊接著向分布式事務的其他參與者發出 canCommit? 消息，發起事務表決過程；
當參與者收到 canCommit? 請求后，除了發起事務的那一個之外，其他還在 working 狀態的參與者會先嘗試執行本地事務，如果本地事務執行成功，則會往本地日志 buffer 寫入一條 <ready T> 記錄并 flush 到可靠性存儲中，但不提交事務，進入 prepared 狀態，然后回復一條 ready T 消息對此事務投 YES 票；如果本地事務執行失敗，則參與者會往本地日志 buffer 寫入一條 <don't commit T> 記錄并 flush 到可靠性存儲中，然后回復一條 don't commit T 消息投 NO 票。
階段 II（收集投票結果完成事務）
協調者收集所有的投票（包括它自己的投票）；
(a) 如果所有的投票都是 ready T，則表示沒有故障發生，那么協調者決定提交該事務，首先它會在其本地日志中追加一條 <commit T> 記錄，從 preparing 狀態進入 committed 狀態，然后向所有的參與者發送 doCommit 請求消息，要求參與者提交它們的本地事務；
(b) 如果有任一個投票是 No，則協調者決定放棄掉該事務，首先它會往本地日志中追加一條記錄，從 preparing 狀態進入 aborted 狀態，然后發送 doAbort 請求消息給所有的參與者，通知它們回滾各自的本地事務。
投了 YES 票的參與者阻塞等待協調者給它發來 doCommit 或 doAbort 消息，如果接收到的是 doCommit 消息則提交本地事務并在此過程中記錄日志 <commit T>，然后進入 committed 狀態，最后回復一個 haveCommitted 的消息通知協調者本地事務已經成功提交；反之，如果收到的是 doAbort 消息則回滾本地事務并寫入日志 <abort T>，然后進入 aborted狀態。
上面的過程是一種更通用的流程，即由任意的參與者發起一個分布式事務，而在實踐中一般把分布式事務的發起交給協調者來做，減少事務發起者確認該事務已被提交所需等待的網絡消息延遲：
性能
網絡 I/O 開銷
假設兩階段提交過程一切運行正常，即協調者和參與者都不出現崩潰和重啟，網絡通信也都正常。那么假設有一個協調者和 N 個參與者，兩階段提交過程中將會發送如下的消息：
任意一個參與者從 working 狀態進入 prepared 狀態并發送 Prepared 消息給協調者，1 條消息。
協調者收到消息后，向其他參與者發送 canCommit? 請求消息，N - 1 條消息。
收到 canCommit? 消息的參與者各自回復協調者投票消息，N - 1 條消息。
協調者統計投票情況之后，發送 doCommit 消息給其他參與者，N 條消息。
所以，事務發起者在經過 4 條網絡消息延遲之后確認該分布式事務已被提交，而整個過程共計發送 3N - 1 條網絡消息（因為 haveCommitted 在 2PC 僅僅是用于最后通知協調者而已，屬于可有可無的一次網絡消息，2PC 在該消息缺省的情況下也能正常運行，因此 haveCommitted 一般不計入網絡延遲成本中）。
前面我們提到，在實踐中一般是由協調者來發起事務，如果考慮這種情況的話，事務發起者 -- 協調者在經過 3 條網絡消息延遲之后確認該分布式事務已經被提交，而整個過程實際發送的網絡消息則變成 3N 條。
總而言之，兩階段提交協議的網絡通信開銷和集群節點的數量成 3 倍正比。
本地存儲設備 I/O 開銷
基于前文中敘述的兩階段提交協議的基本假設之一：每個節點會通過日志來記錄在本地執行的操作，以便在節點發生故障并重啟節點之后能利用日志恢復到故障前的狀態，因此兩階段提交過程中除了網絡 I/O 的開銷之外，還有本地存儲設備 I/O 的開銷：
發起事務的參與者執行本地事務，1 次寫操作。
其余參與者執行各自的本地事務，N - 1 次寫操作。
協調者統計投票結果并決定提交事務，1 次寫操作。
所以事務發起者在經過 3 次本地存儲設備 I/O 延遲之后確認該事務已被提交，整個過程總計有 N + 1 次本地存儲設備 I/O，而如果由協調者來發起事務的話，則還是需要 N + 1 次本地存儲設備 I/O，但是只需要經過 2 次本地存儲設備 I/O 延遲即可確認事務已被提交。
恢復
在分布式事務中，所有的參與者節點都可能發生故障，所以我們需要保證在該故障節點恢復時發生的一切都和分布式事務 T 的全局決策保持一致。節點在恢復的時候會讀取 T 的最后一個本地日志記錄并作出相應的操作：
如果 T 的最后一條日志記錄是 <commit T>，那么說明協調者在節點發生故障時的全局決策是提交 T，根據本地事務所使用的日志方式，在該節點上可能需要執行 redo T。
如果 T 的最后一條日志記錄是 <abort T>，那么說明協調者在節點發生故障時的全局決策是中止 T，根據本地事務所使用的日志方式，在該節點上可能需要執行 undo T。
如果 T 的最后一條日志記錄是 <don't commit T>，則和第 2 中情況類似，執行 undo T。
如果 T 的最后一條日志記錄是 <ready T>，這種情況比較麻煩，因為恢復節點無法確認在它故障之后協調者發出的最終全局決策是什么，因此它必須要和集群中其余至少一個節點取得聯系，詢問 T 的最終結果是什么：恢復節點先嘗試詢問協調者，如果此時協調者正在工作，則告知恢復節點 T 的最終結果，如果是提交就執行 redo T，中止就執行 undo T；如果協調者因故不在工作，則恢復節點可以要求其他某一個參與者節點去查看本地日志以找出 T 的最終結果并告知恢復節點。在最壞的情況下，恢復節點無法和集群中其他所有節點取得聯系，這時恢復節點只能阻塞等待，直至得知 T 的最終結果是提交還是中止。
如果本地日志中沒有記錄任何關于 T 在兩階段提交過程中的操作，那么根據前面的兩階段提交流程可知恢復節點還沒來得及回復協調者的 canCommit? 請求消息就發生了故障，因此根據兩階段算法，恢復節點只能執行 undo T。
缺陷
同步阻塞：兩階段提交協議是一個阻塞的協議，在第二階段期間，參與者在事務未提交之前會一直鎖定其占有的本地資源對象，直到接收到來自協調者的 doCommit 或 doAbort 消息。
單點故障：兩階段提交協議中只有一個協調者，而由于在第二階段中參與者在收到協調者的進一步指示之前會一直鎖住本地資源對象，如果唯一的協調者此時出現故障而崩潰掉之后，那么所有參與者都將無限期地阻塞下去，也就是一直鎖住本地資源對象而導致其他進程無法使用。
數據不一致：如果在兩階段提交協議的第二階段中，協調者向所有參與者發送 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）。
三階段提交協議是對兩階段提交協議的擴展，它在特定假設下避免了同步阻塞的問題。該協議基于以下兩個假設：
集群不發生網絡分區；
故障節點數不超過 K 個（K 是預先設定的一個數值）。
基于這兩個假設，三階段提交協議通過引入超時機制和一個額外的階段來解決阻塞問題，三階段提交協議把兩階段提交協議的第一個階段拆分成了兩步：1) 評估，2) 資源對象加鎖，最后才真正提交：
CanCommit 階段：協調者發送 CanCommit 請求消息，詢問各個參與者節點，參與者節點各自評估本地事務是否可以執行并回復消息（可以執行則回復 YES，否則回復 NO），此階段不執行事務，只做判斷；
PreCommit 階段：協調者根據上一階段收集的反饋決定通知各個參與者節點執行（但不提交）或中止本地事務；有兩種可能：1) 所有回復都是 YES，則發送 PreCommit 請求消息，要求所有參與者執行事務并追加記錄到 undo 和 redo 日志，如果事務執行成功則參與者回復 ACK 響應消息，并等待下一階段的指令；2) 反饋消息中只要有一個 NO，或者等待超時之后協調者都沒有收到參與者的回復，那么協調者會中止事務，發送 Abort 請求消息給所有參與者，參與者收到該請求后中止本地事務，或者參與者超時等待仍未收到協調者的消息，同樣也中止當前本地事務。
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）：
Safety：保證決議（Value）結果是對的，無歧義的，不會出現錯誤情況。
只有是被提案者提出的提案才可能被最終批準；
在一次執行中，只批準（chosen）一個最終決議。被多數接受（accept）的結果成為決議；
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）達到最終的共識。
基礎概念
Value：提案值，是一個抽象的概念，在工程實踐中可以是任何操作，如『更新數據庫某一行的某一列』、『選擇 xxx 服務器節點作為集群中的主節點』。
Number：提案編號，全局唯一，單調遞增。
Proposal：集群需要達成共識的提案，提案 = 編號 + 值。
Proposal 中的 Value 就是在 Paxos 算法完成之后需要達成共識的值。
Paxos 算法中有三個核心角色：
Proposer：生成提案編號 n 和值 v，然后向 Acceptors 廣播該提案，接收 Acceptors 的回復，如果有超過半數的 Acceptors 同意該提案，則選定該提案，否則放棄此次提案并生成更新的提案重新發起流程，提案被選定之后則通知所有 Learners 學習該最終選定的提案值（也可以由 Acceptor 來通知，看具體實現）。Basic Paxos 中允許有多個 Proposers。
Acceptor：接收 Proposer 的提案并參與提案決策過程，把各自的決定回復給 Proposer 進行統計。Acceptor 可以接受來自多個 proposers 的多個提案。
Learner：不參與決策過程，只學習最終選定的提案值。
在具體的工程實踐中，一個節點往往會充當多種角色，比如一個節點可以既是 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 側的算法流程：
Proposer 生成一個新的提案編號 n 然后發送一個 prepare 請求給超過半數的 Acceptors 集合，要求集合中的每一個 Acceptor 做出如下響應：
(a) 向 Proposer 承諾在收到該消息之后就不再接受編號小于 n 的提案。
(b) 如果 Acceptor 在收到該消息之前已經接受過其他提案，則把當前接受的編號最大的提案回復給 Proposer。
如果 Proposer 收到了超過半數的 Acceptors 的回復，那么就可以生成 (n, v) 的提案，這里 v 是所有 Acceptors 回復中編號最大的那個提案里的值，如果所有 Acceptors 回復中都沒有附帶上提案的話，則可以由 Proposer 自己選擇一個 v。
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 都需要利用可靠性存儲（日志）來保存兩個對象：
Acceptor 接受過的編號最大的提案；
Acceptor 回復過的最大的 prepare 請求提案編號。
以上這就是 Acceptor 側的約束。接下來我們就可以得到 Paxos 的整個算法流程了。
Paxos 算法可以歸納為兩大基本過程：
選擇過程；
學習過程。
選擇過程
選擇過程分為兩個階段：
階段一（Phase 1）：
(a) Proposer 生成一個全局唯一且單調遞增的提案編號 n，然后發送編號為 n 的 prepare 請求（P1a msg）給超過半數的 Acceptors 集合。
(b) 當一個 Acceptor 收到一個編號為 n 的 prepare 請求，如果 n 比它此前接受過其他的提案編號（如果有）都要大的話，那么將這個提案編號 n 寫入本地日志，這里記為 max_n，然后作出『兩個承諾，一個回復』:
否則就忽略該 prepare 消息或者回復一個錯誤。
在不違背以前作出的承諾下，回復消息（P1b msg），附帶上自己已經接受過的提案中編號最大的那個提案的 v 和 n，沒有則返回空值。
不再接受編號小于等于 n 的 prepare 請求
不再接受編號小于等于 n 的 accept 請求
兩個承諾：
一個回復：
階段二（Phase 2）：
(a) 當 Proposer 收到超過半數的 Acceptors 回復它的編號為 n 的 prepare 請求的響應，此時有兩種可能：
(b) 當 Acceptor 收到一個編號為 n 的提案的 accept 請求消息，需要分兩種情況處理：
如果 n >= max_n（通常情況下這兩個值是相等的），則接受該提案并回復消息（P2b msg）。
如果 n < max_n，則忽略該 accept 消息或者回復一個錯誤（P2b error）。
Free：沒有任何一個 Acceptor 的回復消息中附帶已被接受的提案，意味著當前流程中還沒有提案值被最終接受，此時 Proposer 可以自由地選擇提案值 Value，最后發送一個包含 (n, v) 提案的 accept 請求消息（P2a msg）給 Acceptors 集合。
Forced：某些 Acceptors 的回復消息中附帶已被接受的提案，那么 Proposer 必須強制使用這些回復消息中編號最大的提案 Value 作為自己的提案值，最后發送一個包含 (n, v) 提案的 accept 請求消息（P2a msg）給 Acceptors 集合。
學習過程
選擇過程結束之后，我們得到了一個提案值，接下來就是要讓集群中的所有 Learner 『學習』到這個值了，以求達到集群的共識。
Learner 學習提案值的方式可以分成三種：
任意一個 Acceptor 接受了一個提案后就立刻將該提案發送給所有 Learner。優點：Learner 能實時學習到被 Paxos 流程選定的 Value；缺點：網絡通信次數太多，如果有 N 個 Acceptors 和 M 個 Learner，則需要的網絡通信是 N*M 次。
設置一個主 Learner，Acceptor 接受了一個提案后只將該提案發送給主 Learner，主 Learner 再轉發給剩下的 Learners。優點：網絡通信次數只需 N+M-1 次；缺點：主 Learner 有單點故障的風險。
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 算法的思想其實并不難理解，真正難的地方是：
Paxos 背后那一套完整的數學原理和證明
在復雜分布式環境將 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 算法有幾個天然缺陷：
只能就單個值（Value）達成共識，不支持多值共識。在實際的工程實踐中往往是需要對一系列的操作達成共識，比如分布式事務，由很多執行命令組成。
至少需要 2 輪往返 4 次 prepare 和 accept 網絡通信才能基于一項提案達成共識。對于一個分布式系統來說，網絡通信是最影響性能的因素之一，過多的網絡通信往往會導致系統的性能瓶頸。
不限制 Proposer 數量導致非常容易發生提案沖突。極端情況下，多 Proposer 會導致系統出現『活鎖』，破壞分布式共識算法的兩大約束之一的活性（liveness）。
關于第三點，前文提到分布式共識算法必須滿足兩個最核心的約束：安全性（safety）和活性（liveness），從上一節我們可以看出 Basic Paxos 主要著重于 safety，而對 liveness 并沒有進行強約束，讓我們設想一種場景：兩個 Proposers (記為 P1 和 P2) 輪替著發起提案，導致兩個 Paxos 流程重疊了：
首先，P1 發送編號 N1 的 prepare 請求到 Acceptors 集合，收到了過半的回復，完成階段一。
緊接著 P2 也進入階段一，發送編號 N2 的 prepare 請求到過半的 Acceptors 集合，也收到了過半的回復，Acceptors 集合承諾不再接受編號小于 N2 的提案。
然后 P1 進入階段二，發送編號 N1 的 accept 請求被 Acceptors 忽略，于是 P1 重新進入階段一發送編號 N3 的 prepare 請求到 Acceptors 集合，Acceptors 又承諾不再接受編號小于 N3 的提案。
緊接著 P2 進入階段二，發送編號 N2 的 accept 請求，又被 Acceptors 忽略。
不斷重復上面的過程......
在極端情況下，這個過程會永遠持續，導致所謂的『活鎖』，永遠無法選定一個提案，也就是 liveness 約束無法滿足。
為了解決這些問題，Lamport 在《Paxos Made Simple》論文中提出了一種基于 Basic Paxos 的 Multi-Paxos 算法思想，并基于該算法引出了一個分布式銀行系統狀態機的實現方案，感興趣的讀者不妨看一下。
Multi-Paxos 算法在 Basic Paxos 的基礎上做了兩點改進：
多 Paxos 實例：針對每一個需要達成共識的單值都運行一次 Basic Paxos 算法的實例，并使用 Instance ID 做標識，最后匯總完成多值共識。
選舉單一的 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 實現各不相同。kd
我們這里用 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 的一個變種，通過新增兩個約束：
追加日志約束：Raft 中追加節點的日志必須是串行連續的，而 Multi-Paxos 中則可以并發追加日志（實際上 Multi-Paxos 的并發也只是針對日志追加，最后應用到內部 State Machine 的時候還是必須保證順序）。
選主限制：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 之間的交錯執行：
事務 T 鎖住了服務器節點 X 上的資源對象 A，做寫入操作；
事務 U 鎖住了服務器節點 Y 上的資源對象 B，做寫入操作；
事務 T 試圖讀取服務器節點 Y 上的資源對象 B，此時 B 被事務 U 鎖住，因此 T 等待鎖釋放；
事務 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 的原理剖析和正確性的證明，最后還有對分布式事務中幾種并發控制的介紹，相信能夠讓讀者對分布式事務和分布式系統底層的一致性和并發控制原理有一個深刻的認知，對以后學習和理解分布式系統大有裨益。
本文不僅僅是簡單地介紹分布式事務和分布式系統的底層原理，更是在介紹原理的同時，通過層層遞進的方式引導讀者去真正地理解分布式系統的底層原理和設計思路，而非讓讀者死記硬背一些概念，所以希望通過這篇拋磚引玉的文章，能夠對本文讀者在以后學習、操作甚至是設計分布式系統以及分布式事務時的思路有所開拓。
參考&延伸
ACID
Eventual consistency
Atomic commit
A Two-Phase Commit Protocol and its Performance
The PartTime Parliament
Paxos Made Simple
Fast Paxos
The Performance of Paxos and Fast Paxos
Paxos Made Live - An Engineering Perspective
Paxos (computer science)
The Chubby lock service for loosely-coupled distributed systems
Consensus on Transaction Commit
Life beyond Distributed Transactions: an Apostate’s Opinion
In Search of an Understandable Consensus Algorithm
Paxos lecture (Raft user study)
Distributed Systems: Concepts and Design
How to Build a Highly Available System Using Consensus
數學歸納法
共識算法
Distributed Transaction Processing: The XA Specification
總結
以上是生活随笔為你收集整理的分布式之系统底层原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CentOS 下线，TencentOS
- 下一篇： “免疫杀手” Deep X-RAY