背景
分布式一緻性算法（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的理論從1990年提出到現在已經有近30年了，但是真正工業級、獨立的Paxos基礎庫還是相當的少見。Google并沒有開源其任何Paxos基礎庫（連包含Paxos的項目都沒有開源過）；Facebook也沒有公布過包含paxos的産品; Apache有Zookeeper，但是其協定并不能支援一個高吞吐的狀态機複制，且并沒有提供獨立的第三方庫，可供快速接入；在Github上能找到的Paxos的獨立庫，star數最高是騰訊雲開源的phxpaxos庫，18年之後也基本沒有更新。
近幾年NewSQL和雲原生資料庫的不斷興起，極大地推動了關系資料庫和一緻性協定的結合，PolarDB-X也是在這樣的背景下應運而生。
X-Paxos 誕生和發展
2014年，阿裡随着業務的高速增長，同城主備部署的方式已經無法滿足阿裡對可擴充的部署、國際化、以及容災方面的需求，“異地多活”成為了公司應用的新标準。基于這樣的業務背景驅動，PolarDB-X早期，在阿裡集團MySQL設計了分布式一緻性協定子產品，并把它獨立命名為X-Paxos，基于單機MySQL實作了一緻性能力，配合TDDL分庫分表的模式部分解決了業務訴求。随着技術的不斷發展和演進，以及面向雲的時代的全面普及，我們PolarDB-X 2.0中融合了分布式SQL引擎和基于X-Paxos的資料庫存儲技術，提供全新的雲原生分布式資料庫。
在PolarDB-X 2.0中，我們也進一步擴充了分布式和Paxos的協同，比如多副本的一緻性讀、副本的動态遷移和管理能力等。反過來，PolarDB-X有了X-Paxos的加持，可以做到金融級資料庫的高可用和容災能力，做到RPO=0的生産級别可用性。Paxos協定對于面向雲的架構是非常必要的，雲的本質是虛拟化和資源池化，節點的變化和彈性是一個正常操作，我們需要解決面向使用者透明運維的能力，任何情況下資料都不能丢、不能錯。
除此以外，X-Paxos除了為資料庫解決了分布式一緻性問題，同樣可以快速賦予其他系統分布式一緻性能力。我們把Paxos的能力獨立成一個基礎庫，希望能夠把這個能力帶給更多的其他系統。ps. 我們也做過快速的嘗試，把X-Paxos融入到單機KV資料庫RocksDB中，就可以很快速實作了一個分布式KV引擎。
Google的論文《Paxos made live》中有一段話說的很好，大意是說：Paxos從理論到現實世界的實作之間有巨大的鴻溝，在真正實作一個Paxos的時候，往往需要對Paxos的經典理論做一些擴充，（尤其是在實作一個高性能的Paxos的時候，擴充點就更多了，可以參考後文的功能增強和性能優化），這往往會導緻真正的Paxos實作其實都是基于一個未被完全證明的協定。這也就是傳說中，理論證明一個Paxos的實作，比實作這個Paxos還要難的原因了。是以一個成熟的Paxos實作很難獨立産生，往往需要和一個系統結合在一起，通過一個或者多個系統來驗證其的可靠性和完備性。這也是為什麼大部分成熟的Paxos案例都是和分布式資料庫相結合的，例如最早的Paxos實作（Chubby），目前的主要Paxos案例（Google的MegaStore、Spanner，AWS的DynamoDB、S3等）。而X-Paxos正是依托于PolarDB-X驗證了其可靠性和完備性。
X-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目前的算法基于強leadership的multi-paxos[3]實作，大量理論和實踐已經證明了強leadership的multi-paxos，性能好于multi-paxos/basic paxos，目前成熟的基于paxos的系統，都采用了這種方式。
算法子產品的基礎功能部分本文不再重複，感興趣的同學可以參考相關論文[1,2,4]。在基礎算法的基礎上，結合阿裡業務的場景以及高性能和生态的需求，X-Paxos做了很多的創新性的功能和性能的優化，使其相對于基礎的multi-paxos，功能變的更加豐富，性能也有明顯的提升。後面将對這些優化進行詳細的介紹。
日志子產品
日志子產品本是算法子產品的一部分，但是出于對極緻性能要求的考慮，我們把日志子產品獨立出來，并實作了一個預設的高性能的日志子產品；有極緻性能以及成本需求的使用者，可以結合已有的日志系統，對接日志子產品接口，以擷取更高的性能和更低的成本。這也是X-Paxos作為高性能獨立庫特有的優勢，後面也會對這塊進行詳細介紹。
X-Paxos 特色功能
線上添加/删除節點，線上轉讓leader
X-Paxos在标準multi-paxos的基礎上，支援線上添加/删除多種角色的節點，支援線上快速将leadership節點轉移到其他節點（有主選舉）。這樣的線上運維能力，将會極大地友善分布式節點的有計劃性的運維工作，将RTO降低到最低。
政策化多數派和權重化選主
阿裡目前多地架構會有中心機房的訴求，比如：應用因其部署的特點，往往要求在未發生城市級容災的情況下，僅在中心寫入資料庫，資料庫的leader節點在正常情況下隻在中心地域；同時又要求在發生城市級容災的時候（同一個城市的多個機房全部不可用），可以完全不丢失任何資料的情況下，将leader點切換到非中心。
而經典的multi-paxos并不能滿足這些需求。經典理論中，多數派強同步以後即可完成送出，而多數派是非特定的，并不能保證某個/某些節點一定能得到完整的資料，并激活服務。在實際實作中，往往地理位置較近的節點會擁有強一緻的資料，而地理位置較遠的節點，一直處于非強一緻節點，在容災的時候永遠無法激活為主節點，形同虛設。
同時當中心單節點出現故障需要容災的時候，往往需要将主節點就近切換到同中心的另外一個節點，而經典理論中同樣沒有類似的功能。
X-Paxos在協定中實作了政策化多數派和權重化選主。
- 基于政策化多數派，使用者可以通過動态配置，指定某個/某些節點必須保有強一緻的資料，在出現容災需求的時候，可以立即激活為主節點。
- 基于權重化選主，使用者可以指定各個節點的選主權重，隻有在高權重的節點全部不可用的時候，才會激活低權重的節點。
節點角色定制化（Proposer/Accepter/Learner的獨立配置）
在經典的multi-paxos實作中，一般每個節點都包含了Proposer/Accepter/Learner三種功能，每一個節點都是全功能節點。但是某些情況下我們并不需要所有節點都擁有全部的功能，例如：
- 經典的三個副本部署中，我們可以裁剪其中一個節點的狀态機，隻保留日志（無資料的純日志節點，但是在同步中作為多數派計算），此時我們需要裁剪掉協定中的Proposer功能（被選舉權），保留Accepter和Learner功能。
- 我們希望可以有若幹個節點可以作為下遊，訂閱/消費協定産生的日志流，而不作為叢集的成員（不作為多數派計算，因為這些節點不儲存日志流），此時我們裁剪掉協定的Proposer/Accepter功能，隻保留Learner功能。
當然還有其他的組合方式，通過對節點角色的定制化組合，我們可以開發出很多的定制功能節點，即節約了成本，又豐富了功能。比如下面的三副本部署，其中一個Follower節點配置為僅做logger模式(參與多數派投票，但不存儲資料)，這樣可以将三副本的3份資料成本優化為隻有2份：
Witness SDK
基于上節節點角色定制化中的單獨Learner角色的功能，引發了無窮的想象力。Learner角色，可以抽象成一個資料流訂閱者（Witness Node），整個叢集中可以加入無數個訂閱者，當有新的日志被送出的時候，這些訂閱者會收到其關心的日志流，基于訂閱者功能，我們可以讓一個叢集很容易的實作下遊訂閱消費，日志即時備份，配置變更推送等等的功能。
是以我們把Learner角色單獨封裝成了一個SDK。基于這個SDK，使用者可以快速的為自己的叢集添加，訂閱注冊，流式訂閱定功能；結合特定的用途打造一個完成的生态。采用了X-Paxos也可以利用Witness SDK快速實作分布式系統和下遊的其他系統的對接，形成一個完整的生态。
Leader 主動回切
在現實應用場景中，Follower 和 Leader 的狀态機難免會存在回放延遲，比如一個大的 DDL 會導緻 Follower 的回放延遲被無限放大，而如果在回放延遲存在的情況下 Leader 挂掉新主選出時，新主無法對外提供服務，而此時老 Leader 可能已經重新開機恢複，是以在這種情況下 X-Paxos 會主動探測狀态機的健康狀況，如果在一段時間内回放延遲無法追平，則會嘗試 Leader 主動回切，讓沒有回放延遲的老 Leader 對外提供服務。
多連接配接
傳統方式leader和learner之間采用單連接配接同步資料，在跨IDC場景中，網絡延時往往比較大，會導緻leader和learner之間的資料差異較大。leader和learner之間通過多連接配接并發的發送資料，可以有效提升吞吐，減少資料差異，在弱一緻的模式下，可以更好地對外提供讀能力。同時在單IDC出現完全不可用的情況下，提供更好的災備能力。
X-Paxos 性能優化
Batching & Pipelining
X-Paxos除了設計之初的強一緻和高可用以外，其高性能也是至關重要的，尤其是應用于PolarDB-X分布式資料庫，對協定的吞吐和延遲都提出了很高的要求。同時作為可全球部署的分布式一緻性協定，在高延遲下的性能挑戰變得尤為重要。
X-Paxos針對高延遲網絡做了大量的協定優化嘗試和測試，并結合學術界現有的理論成果[5,6,7]通過合理的Batching和Pipelining，設計并實作了一整套自适應的針對高延遲高吞吐和低延遲高吞吐網絡的通信模式，極大地提升了X-Paxos的性能。
- Batching是指，将多個日志合并成單個消息進行發送；Batching可以有效的降低消息粒度帶來的額外損耗，提升吞吐。但是過大Batching容易造成單請求的延遲過大，導緻并發請求數過高，繼而影響了吞吐和請求延遲。
- Pipelining是指在上一個消息傳回結果以前，并發的發送下一個消息到對應節點的機制，通過提高并發發送消息數量（Pipelining數量），可以有效的降低并發單請求延遲，同時在transmission delay小于propagation delay的時候（高延遲高吞吐網絡），有效提升性能。
R為網絡帶寬，D為網絡傳播延遲（propagation delay，約為RTT/2），經推導可知 Batching（消息大小:M）和Pipeling（消息并發:P）在如下關系下，達到最高吞吐。
M/R * P = D X-Paxos結合以上理論，通過内置探測，針對不同節點的部署延遲，自适應的調整針對每個節點的Batching和Pipeling參數，達到整體的最大吞吐。因Pipeling的引入，需要解決日志的亂序問題，特别是在異地場景下，window加大，加大了亂序的機率。X-Paxos實作了一個高效的亂序處理子產品，可以對底層日志實作屏蔽亂序問題，實作高效的亂序日志存儲。
多線程的全異步Paxos庫
由于Paxos的内部狀态複雜，實作高效的單執行個體多線程的Paxos變成一個非常大的挑戰。比如開源産品phxpaxos、Oracle MySQL Group Replication中使用的xcom，都是單線程的實作。phxpaxos采用了單配置設定單線程，多執行個體聚合的方式提升總吞吐，但是對單分區的性能非常的有限；xcom是一個基于協程的單線程實作。單線程的Paxos實作，在處理序列化/反序列化，分發、發包等邏輯的時候都為串行執行，性能瓶頸明顯。
X-Paxos完全基于多線程實作，可以在單個分區Paxos中完全的使用多線程的能力，所有的任務都有通用的worker來運作，消除了CPU的瓶頸。依賴于服務層的多線程異步架構和異步網絡層，X-Paxos除了必要的協定串行點外，大部分操作都可以并發執行，并且部分協定串行點采用了無鎖設計，可以有效利用多線程能力，實作了Paxos的單分片多線程能力，單分區性能遠超競品，甚至超過了競品的多執行個體性能。
可插拔日志
X-Paxos和現有的大部分Paxos庫很大的不同點就是X-Paxos支援可插拔的日志子產品。日志子產品是Paxos中一個重要的子產品，它的持久化關系到資料的一緻性，它的讀寫性能很大程度上會影響協定整體的讀寫性能。目前大部分獨立Paxos庫都是内置日志子產品，并且不支援插拔的。這會帶來2個弊端：
- 預設的日志子產品提供通用的功能，很難結合具體的系統做針對性的優化
- 現有的系統往往已經存在了WAL（Write Ahead Log），而Paxos協定中需要再存一份。這使得 a) 單次commit本地需要sync 2次（影響性能）；b) 雙份日志浪費了大量的存儲
例如：phxpaxos内置的日志子產品采用LevelDB，作為日志系統其操作大量備援，無針對優化；同時采用phxpaxos的phxsql單節點需要即儲存binlog，又儲存paxos log（在獨立的phxbinlogsvr中），會有性能性能、以及浪費存儲空間。而采用X-Paxos的MySQL存儲引擎可直接改造現有的binlog子產品，對接到X-Paxos的日志子產品，單節點僅一份日志，既降低了存儲，又提高了性能。
X-Paxos 正确性驗證
《Paxos made live》中有過一個說法，證明一個Paxos實作是正确的，比實作這個Paxos本身會更難。是以我們在設計和實作X-Paxos的時候，投入了大量的精力在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庫也在不斷的豐富中。
未來
Paxos是分布式系統的基石，即使是近幾年，學術界關于Paxos的文章，新的演進方向一直在不斷的湧現，我們的PolarDB-X分布式資料庫也會在X-Paxos的基礎上不停的發展，比如多分區Paxos、基于Paxos多副本的HTAP架構、以及Geo-Partition的特性等。
參考文檔
[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