【IT168 評論】Paxos(分布式一致性算法)作為分布式系統的基石，一直都是計算機系統工程領域的熱門話題。Paxos號稱是最難理解的算法，其實現真的這麼困難麼?「X-Paxos」是阿里巴巴資料庫團隊面向高性能、全球部署以及阿里業務特徵等需求，實現的一個高性能分布式強一致的Paxos獨立基礎庫。X-Paxos具體又有哪些優勢，能給現有的系統帶來什麼用的收益呢?
背景
分布式一致性算法(Consensus Algorithm)是一個分布式計算領域的基礎性問題，其最基本的功能是為了在多個進程之間對某個(某些)值達成一致(強一致);進而解決分布式系統的可用性問題(高可用)。Paxos是最重要的分布式一致性算法，很多人都把它作為「分布式一致性協議」的代名詞(Mike Burrows, inventor of the Chubby service at Google, says that 「there is only one consensus protocol, and that’s Paxos」)。
關於Paxos的歷史和原理，已經有很多經典的論文可以參考，也有廠內外的文章有詳細的描述，本文就不再重複了。感興趣的同學可以閱讀下這些論文[1,2,3,4]。
業內
雖然Paxos的理論提出已經17年了，從第一個Paxos的工業實現到現在也已經11年了，但是直到近幾年，無論是頂級會議，還是業內，Paxos相關的文章和項目還是層出不窮。
轉向業內，雖然使用了Paxos及各種變種的產品已經層出不窮;但是真正工業級的，獨立的，Paxos基礎庫還是相當的少見：Google並沒有開源其任何Paxos基礎庫(連包含Paxos的項目都沒有開源過); Facebook也沒有公布過包含Paxos的產品; Apache有Zookeeper，但是其協議並不能支持一個高吞吐的狀態機複製，且並沒有提供獨立的第三方庫，可供快速接入。在Github上能找到的Paxos的獨立庫，star最高的是騰訊於去年開源的phxpaxos(後文會作為競品進行詳細對比)。
因此到目前為止業內還鮮有成熟可靠的，可供快速使用的獨立第三方Paxos庫，開源的Paxos生態也尚未成熟。
X-Paxos正文
願景
我們的初衷並不是要做一個Paxos的公共庫，X-Paxos誕生於阿里巴巴的分布式資料庫AliSQL X-Cluster，但X-Paxos並不屬於AliSQL X-Cluster。Paxos是分布式系統的基石，X-Paxos可用於解決各種各樣的分布式系統中的一致性問題。因此在整個分布式資料庫的設計之初，我們就獨立設計了分布式一致性協議模塊，並把它獨立為X-Paxos。X-Paxos為AliSQL X-Cluster解決了分布式一致性問題，同樣可以快速賦予其他系統分布式一致性能力。分布式一致性需求，並不是AliSQL X-Cluster所特有的，很多系統都存在這高可用和強一致的需求，我們把Paxos的能力獨立成一個基礎庫，希望能夠把這個能力帶給更多的其他系統。例如：團隊內的同學把X-Paxos融入到單機KV資料庫RocksDB中，快速實現了一個分布式KV引擎。集團已有業務團隊團隊把X-Paxos融入到業務存儲系統中，構建全新的分布式強一致存儲服務。
同時也正是AliSQL X-Cluster，成就了X-Paxos。Google的論文《Paxos made live》中有一段話說的很好，大意是說：Paxos從理論到現實世界的實現之間有巨大的鴻溝，在真正實現一個Paxos的時候，往往需要對Paxos的經典理論做一些擴展，(尤其是在實現一個高性能的Paxos的時候，擴展點就更多了，可以參考後文的功能增強和性能優化)，這往往會導致真正的Paxos實現其實都是基於一個未被完全證明的協議。這也就是傳說中，理論證明一個Paxos的實現，比實現這個Paxos還要難的原因了。因此一個成熟的Paxos實現很難獨立產生，往往需要和一個系統結合在一起，通過一個或者多個系統來驗證其可靠性和完備性。這也是為什麼大部分成熟的Paxos案例都是和分布式資料庫相結合的，例如最早的Paxos實現(Chubby)，當前的主要Paxos實現(Google的MegaStore、Spanner，AWS的DynamoDB、S3等)。而X-Paxos正是依託於AliSQL X-Cluster驗證了其可靠性和完備性。
我們的願景是希望能夠提供一個經過實踐檢驗的，高度成熟可靠的獨立Paxos基礎庫。使得一個後端服務能夠通過簡單的接入，就能擁有Paxos算法賦予的強一致、高可用、自動容災等能力。真正將晦澀難懂的Paxos，變得平易近人，帶入千萬家。
架構
X-Paxos的整體架構如上圖所示，主要可分為網絡層、服務層、算法模塊、日誌模塊4個部分。
網絡層
網絡層基於阿里內部非常成熟的網絡庫libeasy實現。libeasy的異步框架和線程池非常契合我們的整體異步化設計，同時我們對libeasy的重連等邏輯進行了修改，以適應分布式協議的需求。
服務層
服務層是驅動整個Paxos運行的基礎，為Paxos提供了事件驅動，定時回調等核心的運行功能，每一個Paxos實現都有一個與之緊密相關的驅動層，驅動層的架構與性能和穩定性密切相關。
X-Paxos的服務層是一個基於C++11特性實現的多線程異步框架。常見的狀態機/回調模型存在開發效率較低，可讀性差等問題，一直被開發者所詬病;而協程又因其單線程的瓶頸，而使其應用場景受到限制。C++11以後的新版本提供了完美轉發(argument forwarding)、可變模板參數(variadic templates)等特性，為我們能夠實現一種全新的異步調用模型提供了可能。
例如：這是X-Paxos內實際的一行創建單次定時任務的代碼
new ThreadTimer(srv_->getThreadTimerService(), srv_, electionTimeout_, ThreadTimer::Oneshot,
&Paxos::checkLeaderTransfer, this, targetId, currentTerm_.load(), log_->getLastLogIndex());
以上一行程序，包含了定時器的創建，任意回調函數的設置，回調函數參數的轉發，並保證在回調觸發後(Oneshot)內存的自動回收。同時服務層支持嵌套回調，即在回調函數中再一次生成一個定時/即時任務，實現一個有限次定時循環邏輯。
算法模塊
X-Paxos當前的算法基於unique proposer的multi-paxos[3]實現，大量理論和實踐已經證明了基於unique proposer的multi-paxos，性能好於multi-paxos/basic paxos，當前成熟的基於Paxos的系統，大部分都採用了這種方式。
算法模塊的基礎功能部分本文不再重複，感興趣的同學可以參考相關論文[1,2,4]。在基礎算法的基礎上，結合阿里業務的場景以及高性能和生態的需求，X-Paxos做了很多的創新性的功能和性能的優化，使其相對於基礎的multi-paxos，功能變的更加豐富，在多種部署場景下性能都有明顯的提升。下一章中，將對這些優化進行詳細的介紹。
日誌模塊
日誌模塊本是算法模塊的一部分，但是出於對極致性能要求的考慮，我們把日誌模塊獨立出來，並實現了一個默認的高性能的日誌模塊;有極致性能以及成本需求的用戶，可以結合已有的日誌系統，對接日誌模塊接口，以獲取更高的性能和更低的成本。這也是X-Paxos作為高性能獨立庫特有的優勢，下一章會進行詳細的介紹。
功能增強
結合廣泛的業務場景，構建開放的生態。
1. 在線添加/刪除節點，在線轉讓leader
X-Paxos在標準multi-paxos的基礎上，支持在線添加/刪除多種角色的節點，支持在線快速將leadership節點轉移到其他節點(有主選舉)。
2. 策略化多數派和權重化選主
集團及螞蟻目前的多地有中心的架構，很多應用因其部署的特點，往往要求其在未發生城市級容災的情況下，僅在中心寫入資料庫，或調用其他分布式服務;同時又要求在發生城市級容災的時候(同一個城市的多個機房全部不可用)，可以完全不丟失任何數據的情況下，將寫入點切換到非中心。
而經典的multi-paxos並不能滿足這些需求。經典理論中，多數派強同步以後即可完成提交，而多數派是非特定的，並不能保證某個/某些節點一定能得到完整的數據，並激活服務。在實際實現中，往往地理位置較近的節點會擁有強一致的數據，而地理位置較遠的節點，一直處於非強一致節點，在容災的時候永遠無法激活為主節點，形同虛設。
同時當中心單節點出現故障需要容災的時候，往往需要將主節點就近切換到同中心的另外一個節點;由於應用在多地的部署往往是非對稱的原因，才出現單個region全掛的時候，寫需要將主節點切到特定的region內。這些需求都需要Paxos在選主的時候，可以由用戶指定規則，而經典理論中同樣沒有類似的功能，添加權重也需要保證Paxos的正確性。
X-Paxos在協議中實現了策略化多數派和權重化選主。基於策略化多數派，用戶可以通過動態配置，指定某個/某些節點必須保有強一致的數據，在出現容災需求的時候，可以立即激活為主節點。基於權重化選主，用戶可以指定各個節點的選主權重，只有在高權重的節點全部不可用的時候，才會激活低權重的節點。
3. 節點角色定製化(Proposer/Accepter/Learner的獨立配置)
在經典的multi-paxos實現中，一般每個節點都包含了Proposer/Accepter/Learner三種功能，每一個節點都是全功能節點。但是某些情況下我們並不需要所有節點都擁有全部的功能，例如：
1）經典的三個副本部署中，我們可以裁剪其中一個節點的狀態機，只保留日誌(無數據的純日誌節點，但是在同步中作為多數派計算)，此時我們需要裁剪掉協議中的Proposer功能(被選舉權)，保留Accepter和Learner功能。
2）我們希望可以有若干個節點可以作為下遊，訂閱/消費協議產生的日誌流，而不作為集群的成員(不作為多數派計算，因為這些節點不保存日誌流)，此時我們裁剪掉協議的Proposer/Accepter功能，只保留Learner功能
當然還有其他的組合方式，通過對節點角色的定製化組合，我們可以開發出很多的定製功能節點，即節約了成本，又豐富了功能。
4. Witness SDK
基於上節節點角色定製化中的單獨Learner角色的功能，引發了無窮的想像力。Learner角色，可以抽象成一個數據流訂閱者(Witness Node)，整個集群中可以加入無數個訂閱者，當有新的日誌被提交的時候，這些訂閱者會收到其關心的日誌流，基於訂閱者功能，我們可以讓一個集群很容易的實現下遊訂閱消費，日誌即時備份，配置變更推送等等的功能。
因此我們把Learner角色單獨封裝成了一個SDK。基於這個SDK，用戶可以快速的為自己的集群添加，訂閱註冊，流式訂閱定功能;結合特定的用途打造一個完成的生態。
例如日誌流SDK在AliSQL X-Cluster中打造的生態：
採用了X-Paxos也可以利用Witness SDK快速實現分布式系統和下遊的其他系統的對接，形成一個完整的生態。
我們拿MySQL的日誌(binlog)備份來舉例：
1）普通方案
每隔固定時間Tb，將MySQL生成的binlog文件備份到永久備份系統(OSS、S3等)
RPO (Recovery Point Objective)為 Tb
2）SDK方案
X-Paxos支持由SDK訂閱增量日誌，備份系統只需要簡單的實現從SDK流到OSS流的對接，即可實現流式備份
RPO (Recovery Point Objective)為 0
除備份以外，Witness SDK在下遊流式訂閱(DRC)、自封閉高可用系統(X-Driver)、異步只讀備庫等方面都有實戰案例，更多的應用案例在不斷的添加中。
性能優化
我們一直堅信網絡延遲不應該影響吞吐。
1. Batching & Pipelining
Paxos除了設計之初的強一致和高可用以外，其高性能也是至關重要的，尤其是應用於AliSQL X-Cluster這種高性能分布式資料庫的時候，對協議的吞吐，延遲都提出了很高的要求。同時作為可全球部署的分布式一致性協議，在高延遲下的性能挑戰變得尤為重要。
X-Paxos針對高延遲網絡做了大量的協議優化嘗試和測試，並結合學術界現有的理論成果[5,6,7]通過合理的Batching和Pipelining，設計並實現了一整套自適應的針對高延遲高吞吐和低延遲高吞吐網絡的通信模式，極大的提升了X-Paxos的性能(對比見下節)。類似的優化在同類競品中還非常的罕見。
Batching是指，將多個日誌合併成單個消息進行發送;Batching可以有效的降低消息粒度帶來的額外損耗，提升吞吐。但是過大Batching容易造成單請求的延遲過大，導致並發請求數過高，繼而影響了吞吐和請求延遲。
Pipelining是指在上一個消息返回結果以前，並發的發送下一個消息到對應節點的機制，通過提高並發發送消息數量(Pipelining數量)，可以有效的降低並發單請求延遲，同時在transmission delay小於propagation delay的時候(高延遲高吞吐網絡)，有效提升性能。
經推導可知 Batching(消息大小:M)和Pipeling(消息並發:P)在如下關係下，達到最高吞吐
M/R * P = D
其中R為網絡帶寬，D為網絡傳播延遲(propagation delay，約為RTT/2)
X-Paxos結合以上理論，通過內置探測，針對不同節點的部署延遲，自適應的調整針對每個節點的Batching和Pipeling參數，達到整體的最大吞吐。
Pipeling的引入，需要解決日誌的亂序問題，特別是在異地場景下，window加大，加大了亂序的概率。X-Paxos實現了一個高效的亂序處理模塊，可以對底層日誌實現屏蔽亂序問題，實現高效的亂序日誌存儲。
2. 多線程，全異步的Paxos庫
由於Paxos的內部狀態複雜，實現高效的單實例多線程的Paxos變成一個非常大的挑戰。無論我們上面提到的github中star最多的phxpaxos，還是Oracle MySQL Group Replication中使用的xcom，都是單線程的實現。phxpaxos採用了單分區單線程，多實例聚合的方式提升總吞吐，但是對單分區的性能非常的有限;而xcom是一個基於協程的單線程實現。單線程的Paxos實現，在處理序列化/反序列化，分發、發包等邏輯的時候都為串行執行，性能瓶頸明顯。
X-Paxos完全基於多線程實現，可以在單個分區Paxos中完全的使用多線程的能力，所有的任務都有通用的woker來運行，消除了CPU的瓶頸。依賴於服務層的多線程異步框架和異步網絡層，X-Paxos除了必要的協議串行點外，大部分操作都可以並發執行，並且部分協議串行點採用了無鎖設計，可以有效利用多線程能力，實現了Paxos的單分區多線程能力，單分區性能遠超競品，甚至超過了競品的多分區分區性能。
3. Locality Aware Content Distribution
基於unique proposer的分布式系統的存在的一個瓶頸點就是主節點是唯一的內容輸出源，當集群存在大量節點的時候，主節點的大量網絡收發工作會導致主節點的負載過大，引發CPU和帶寬的瓶頸;在全國/全球部署的時候，所有節點和主節點之間的直接通信會造成跨region之間的長傳/國際鏈路的帶寬佔用過大。
X-Paxos是旨在解決全球分布式強一致問題的Paxos獨立庫，在設計之初就考慮到了這個問題。X-Paxos在穩態運行時會感知各個節點之間的網絡延遲(物理距離)，並形成級聯拓撲，有效降低主節點的負載，降低長傳鏈路的帶寬使用;而在有節點異常的時候，又會自動重組拓撲，保證各個存活節點間的同行的正常進行。同時X-Paxos支持有業務來設定重組拓撲的規則，業務可以根據自己APP的部署架構和延遲特性來針對性的設置拓撲重組規則。
4. 可插拔日誌
X-Paxos和現有的大部分paxos庫很大的不同點就是X-Paxos支持可插拔的日誌模塊。日誌模塊是Paxos中一個重要的模塊，它的持久化關係到數據的一致性，它的讀寫性能很大程度上會影響協議整體的讀寫性能。當前大部分獨立Paxos庫都是內置日誌模塊，並且不支持插拔的。這會帶來2個弊端：
1）默認的日誌模塊提供通用的功能，很難結合具體的系統做針對性的優化
2）現有的系統往往已經存在了WAL(Write Ahead Log),而Paxos協議中需要再存一份。這使得 a)單次commit本地需要sync 2次(影響性能);b)雙份日誌浪費了大量的存儲
例如：phxpaxos內置的日誌模塊採用LevelDB，作為日誌系統其操作大量冗餘，無針對優化，性能堪憂;同時採用phxpaxos的phxsql單節點需要即保存binlog，又保存Paxos log(在獨立的phxbinlogsvr中)，嚴重影響了性能，浪費了存儲空間。而採用X-Paxos的AliSQL X-Cluster直接改造了現有的binlog模塊，對接到X-Paxos的日誌模塊，單節點僅一份日誌，即降低了存儲，又提高了性能。
分布式正確性驗證
對於一個分布式強一致協議來說，正確性是生命線。上文已經提及，一個分布式強一致協議，很難完整的理論證明其正確性，再加上工程實現的問題，困難就更多了。我們從理論和工程2方面用了大量的理論和技術手段來保證X-Paxos的正確性和完備性。
1. Jepsen
Jepsen是開源社區比較公認的分布式資料庫的測試框架。Jepsen驗證過包括VoltDB、CockroachDB、Galera、MongoDB、etcd在內的幾乎所有的主流分布式資料庫/系統，檢驗出了不少的問題。
X-Paxos完成了和Jepsen的對接，並驗證了各個分布式資料庫已有的case。
2. TLA+
TLA+是Paxos創始人、圖靈獎獲得者Leslie Lamport老爺子發明的一種形式化規約語言。TLA+專用於設計、建模和驗證分布式並發系統。Amazon DynamoDB/S3/EBS和Microsoft Cosmos DB都通過TLA+的模型驗證發現了不少問題
X-Paxos目前已經通過了TLA+的模型驗證。
3. 隨機異常系統
我們搭建了一套自動隨機異常驗證系統，可以自動化驗證各種異常場景下的協議正確性和穩定性。驗證X-Paxos在模擬網絡丟包、閃斷、隔離，磁碟故障等情況下的功能正確和數據一致。
4. 異常回歸系統
X-Paxos擁有一套異常case回歸系統，對於曾經出現過或者預期的並發異常case，都會加到異常case庫中，進行日常回歸驗證。同時異常case庫也在不斷的豐富中。
競品分析和對比
1、XCOM (MySQL Group Replication)
MySQL Group Replication是MySQL官方借鑑Galera的思想，在MySQL上構建分布式強一致集群的一個插件。MySQL Group Replication早期採用的分布式協議是CoroSync，這是由Red Hat開發的基於Totem(The Totem Single-Ring Ordering and Membership Protocol)[8]協議開發的分布式一致性協議庫;由於Totem算法本身存在的一些局限性能原因，從MySQL 5.7.9以後，官方採用了自己研發的基於類Paxos(Mencius)[10]的一致性協議庫XCOM。
XCOM是MySQL Group Replication的核心組件，稱為Group Communication Core[9]。我們分析了XCOM的源碼，XCOM內部是一個由純C語言編譯的核心模塊以及有C++實現的proxy實現的系統。純C模塊由單線程驅動，依賴協程實現任務調度。因此Client(MySQL Group Replication Plugin)必須用tcp連接向XCOM發送請求。因此XCOM存在如下的不足之處:
1）單線程驅動，無多線程能力
架構決定，很難突破
2）通信流需要額外的一次TCP協議棧
在內存拷貝都要精細計算的應用中，線程間多一次網絡通信很難接受
3）XCOM雖然實現了Batching和Pipelining，但是其值均為固定值，很難適應真實的場景
官方的文檔中也提到了這一點[9]
這也使得MySQL Group Replication在跨Region場景中性能很不理想(見AliSQL X-Cluster對比測試)
2、phxpaxos (phxsql)
phxpaxos是騰訊推出的基於Paxos協議的獨立庫，其和MySQL結合後推出了phxsql項目，也是基於MySQL實現的分布式強一致MySQL集群。phxpaxos可獨立用於其他項目，是目前github上star最多(1000+)的Paxos獨立庫。關於phxsql的細節本文不再敘述，可以參考(AliSQL X-Cluster的競品分析部分)，我們這裡主要分析phxpaxos。phxpaxos也是基於multi-Paxos實現的獨立庫，其架構上採用單Paxos單線程設計，但是支持多Paxos分區以擴展多線程能力，這種擴展需要多數據進行提前分區。因此phxpaxos的不足之處如下：
1）單Paxos對象只支持單線程;可支持多Paxos對象，共享網絡層
2）不支持pipelining，在跨Region環境(高延遲)下，幾乎不可用
3）多份日誌冗餘，基於LevelDB的日子系統性能瓶頸
性能對比
我們還是拿騰訊的phxpaxos作為競品和我們進行對比(XCOM無獨立組件，可間接參考MySQL Group Replication和AliSQL X-Cluster的對比測試結果)
我們分別在a) Region內3節點部署 b) 3個Region各一個節點部署 調節下,以不同的請求大小進行壓測。
從上面2個對比圖中可以看到：
1. X-Paxos的同Region性能是phxpaxos的100倍以上
2. 跨Region場景下phxpaxos幾乎不可用，而X-Paxos在444Byte(sysbench insert場景單請求大小)，性能只有3.5%的下降，幾乎不影響吞吐。
現狀與未來
1、現狀
目前X-Paxos一期已經發布上線。
基於X-Paxos的集團資料庫團隊產品AliSQL X-Cluster已在集團內廣泛使用。
X-Paxos和業務系統結合打造的分布式服務也相繼落地上線。
2、未來
Paxos是分布式系統的基石，即使是近幾年，學術界關於Paxos的文章，新的演進方向一致在不斷的湧現，我們的X-Paxos也會不停的發展，以更好的適應集團內外的需求，未來主要的發展方向如下：
1）高效率，多分區支持
基於新的異步框架，實現一個深度底層共享的多分區Paxos
2）多節點強一致讀
經典的multi-paxos只有在leader上才能提供強一致讀，spanner和業界都有一些在多節點上提供強一致讀的方案，但還是有比較明顯的缺陷。
最後，無論是對Paxos協議感興趣的同學，還是想更多的了解或使用X-Paxos的同學，都可以聯繫我(@小強-zju)，歡迎一起交流，互相學習!
參考文件
[1] The part-time parliament
[2] The Chubby lock service for loosely-coupled distributed systems
[3] Paxos Made Simple
[4] Paxos Made Live - An Engineering Perspective
[5] Everything You Ever Wanted to Know About Message Latency
[6] Adaptive Batching for Replicated Servers
[7] Tuning Paxos for high-throughput with batching and pipelining
[8] The Totem single-ring ordering and membership protocol
[9] Group Replication: A Journey to the Group Communication Core
[10] Mencius: Building Efficient Replicated State Machines for WANs