Paxos和Raft的前世今生
在保證數據安全的基礎上，保持服務的持續可用，是核心業務對底層數據存儲系統的基本要求。業界常見的1主N備的方案面臨的問題是“最大可用（Maximum Availability）”和“最大保護（Maximum Protection）”模式間的艱難抉擇：
“最大可用”模式，表示主機盡力將數據同步到備機之后才返回成功，如果備機宕機或網絡中斷那么主機則單獨提供服務，這意味著主備都宕機情況下可能的數據丟失（MySQL的半同步模式）；
“最大保護”模式，表示主機一定要將數據同步到備機后才能返回成功，則意味著在任意備機宕機或網絡中斷情況下主機不得不停服務等待備機或網絡恢復（MySQL的全同步模式）。
可見傳統主備方式下，如果要求數據不丟，那么基本放棄了服務的持續可用能力。
Paxos算法是Leslie Lamport在1990年提出的一種基于消息傳遞的一致性算法。由于算法難以理解，起初并沒有引起大家的重視，Lamport在1998年將論文重新發表到TOCS上，即便如此Paxos算法還是沒有得到重視，2001年Lamport用可讀性比較強的敘述性語言給出算法描述。
06年Google發布了三篇論文，其中在Chubby鎖服務使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。
基于Paxos協議的數據同步與傳統主備方式最大的區別在于：Paxos只需超過半數的副本在線且相互通信正常，就可以保證服務的持續可用，且數據不丟失。
Basic-Paxos解決的問題：在一個分布式系統中，如何就一個提案達成一致。
需要借助兩階段提交實現：
Prepare階段：
Proposer選擇一個提案編號n并將prepare請求發送給 Acceptor。
Acceptor收到prepare消息后，如果提案的編號大于它已經回復的所有prepare消息，則Acceptor將自己上次接受的提案回復給Proposer，并承諾不再回復小于n的提案。
Accept階段：
當一個Proposer收到了多數Acceptor對prepare的回復后，就進入批準階段。它要向回復prepare請求的Acceptor發送accept請求，包括編號n和根據prepare階段決定的value（如果根據prepare沒有已經接受的value，那么它可以自由決定value）。
在不違背自己向其他Proposer的承諾的前提下，Acceptor收到accept請求后即接受這個請求。
參考資料
《The Part-Time Parliament》，Leslie Lamport，May 1998，論文原文
《Paxos Made Simple》，Leslie Lamport，Nov 2001
《一步一步理解Paxos算法》，相對通俗易懂
《使用Basic-Paxos協議的日志同步與恢復》，偏實現
Mulit-Paxos解決的問題：在一個分布式系統中，如何就一批提案達成一致。
當存在一批提案時，用Basic-Paxos一個一個決議當然也可以，但是每個提案都經歷兩階段提交，顯然效率不高。Basic-Paxos協議的執行流程針對每個提案（每條redo log）都至少存在三次網絡交互：1. 產生log ID；2. prepare階段；3. accept階段。
所以，Mulit-Paxos基于Basic-Paxos做了優化，在Paxos集群中利用Paxos協議選舉出唯一的leader，在leader有效期內所有的議案都只能由leader發起。
這里強化了協議的假設：即leader有效期內不會有其他server提出的議案。因此，對于后續的提案，我們可以簡化掉產生log ID階段和Prepare階段，而是由唯一的leader產生log ID，然后直接執行Accept，得到多數派確認即表示提案達成一致（每條redo log可對應一個提案）。
相關產品
X-DB、OceanBase、Spanner都是使用Multi-Paxos來保障數據一致性。
MySQL Group Replication的xcom中也使用了Multi-Paxos。
參考資料
《使用Multi-Paxos協議的日志同步與恢復》
?
X-PaxosX-Paxos是X-DB中的Multi-Paxos實現，通過異步流水線化、Batching和Pipeline等手段提升性能。
參考資料
《阿里如何實現高性能分布式強一致的獨立 Paxos?基礎庫》
PaxosStore是我司WXG基于Paxos實現的分布式一致性中間件，在微信的用戶賬號管理、用戶關系管理、即使消息、社交網絡、在線支付等場景中廣泛應用。
參考資料
《PaxosStore:High-availability Storage Made Practical in WeChat》，PaxosStore在VLDB發的論文
PaxosStore（C++）
https://github.com/tencent/paxosstore
PaxosStore是騰訊公司WXG基于Paxos實現的分布式一致性中間件。
PhxPaxos（C++）
https://github.com/Tencent/phxPaxos
PhxPaxos是騰訊公司微信后臺團隊自主研發的一套基于Paxos協議的多機狀態拷貝類庫。它以庫函數的方式嵌入到開發者的代碼當中， 使得一些單機狀態服務可以擴展到多機器，從而獲得強一致性的多副本以及自動容災的特性。這個類庫在微信服務里面經過一系列的工程驗證，并且其開發團隊對它進行過大量的惡劣環境下的測試，使其在一致性的保證上更為健壯。
LibPaxos（C）
http://libPaxos.sourceforge.net/
LibPaxos的主要價值是可以用來做研究，可以讓程序員對Paxos的細節了解更加清楚。
如果要基于LibPaxos實現一個可以用于生產環境的Paxos庫，還需要做幾個工作：
各個單元的狀態信息固化，防止宕機發生信息丟失；
增加leader模型；
改為多線程實現并合并learner、proposer、acceptor為一個進程；
對庫做充分細致的測試。?
Raft是斯坦福大學的Diego Ongaro、John Ousterhout兩個人以易理解為目標設計的一致性算法，在2013年發布了論文：《In Search of an Understandable Consensus Algorithm》。從2013年發布到現在，已經有了十幾種語言的Raft算法實現框架，較為出名的有etcd，Google的Kubernetes也是用了etcd作為他的服務發現框架。
與Paxos相比，Raft強調的是易理解、易實現，Raft和Paxos一樣只要保證超過半數的節點正常就能夠提供服務。
眾所周知，當問題較為復雜時，可以把問題分解為幾個小問題來處理，Raft也使用了分而治之的思想，把算法分為三個子問題：
選舉（Leader election）
日志復制（Log replication）
安全性（Safety）
?分解后，整個raft算法變得易理解、易論證、易實現。
相關產品
etcd使用Raft來保障數據一致性。
參考資料
《In Search of an Understandable Consensus Algorithm》，Diego Ongaro，John Ousterhout，2013
《一致性算法Raft詳解》
許多NewSQL數據庫的數據規模上限都定位在100TB以上，為了負載均衡，都會對數據進行分片（sharding），所以就需要使用多個Raft集群（即Multi-Raft），每個Raft集群對應一個分片。
在多個Raft集群間可增加協同來減少資源開銷、提升性能（如：共享通信鏈接、合并消息等）。
相關產品
TiDB、CockroachDB、PolarDB都是使用Mulit-Raft來保障數據一致性。
Parallel-Raft是PolarDB中的Multi-Raft實現，通過支持亂序日志復制（亂序確認、亂序提交、亂序應用）等手段來提升性能。
參考資料
《面向云數據庫，超低延遲文件系統PolarFS誕生了》
《PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database》，PolarDB在VLDB上發的論文
etcd/raft（Go）
??etcd里面使用raft做數據同步
https://github.com/etcd-io/etcd
應用廣泛，成熟度高。因為是Go語言開發，集成到C/C++應用中比較困難。
TiKV/raft（Rust）
TiKV里面使用raft做數據同步
https://github.com/tikv/tikv
Rust語言目前還比較小眾。
kudu/raft（C++）
kudu里面也使用了raft
https://github.com/apache/kudu
LogCabin（C++）
https://github.com/logcabin/logcabin
由Raft論文作者Diego Ongaro主導的開源項目，沒有得到廣泛應用，很久沒更新了。
其他實現
目前有十幾種語言實現的幾十個Raft算法實現框架，參見：
https://raft.github.io?
Raft是基于對Multi-Paxos的兩個限制形成的：
發送的請求的是連續的, 也就是說Raft的append 操作必須是連續的， 而Paxos可以并發 (這里并發只是append log的并發, 應用到狀態機還是有序的)。
Raft選主有限制,必須包含最新、最全日志的節點才能被選為leader. 而Multi-Paxos沒有這個限制，日志不完備的節點也能成為leader。
Raft可以看成是簡化版的Multi-Paxos。
Multi-Paxos允許并發的寫log,當leader節點故障后，剩余節點有可能都有日志空洞。所以選出新leader后, 需要將新leader里沒有的log補全,在依次應用到狀態機里。
參考資料
知乎里朱一聰做的比較相對客觀、全面：
https://www.zhihu.com/question/36648084/answer/82332860
總結
以上是生活随笔為你收集整理的Paxos和Raft的前世今生的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 大牛书单 | 数据库专题好书分享
- 下一篇： Fashion-MNIST 一周年 |