Paxos和Raft的前世今生

前言

在保证数据安全的基础上，保持服务的持续可用，是核心业务对底层数据存储系统的基本要求。业界常见的1主N备的方案面临的问题是“最大可用（Maximum Availability）”和“最大保护（Maximum Protection）”模式间的艰难抉择：

“最大可用”模式，表示主机尽力将数据同步到备机之后才返回成功，如果备机宕机或网络中断那么主机则单独提供服务，这意味着主备都宕机情况下可能的数据丢失（MySQL的半同步模式）；

“最大保护”模式，表示主机一定要将数据同步到备机后才能返回成功，则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复（MySQL的全同步模式）。

可见传统主备方式下，如果要求数据不丢，那么基本放弃了服务的持续可用能力。

算法演进

Paxos

Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。由于算法难以理解，起初并没有引起大家的重视，Lamport在1998年将论文重新发表到TOCS上，即便如此Paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述。

06年Google发布了三篇论文，其中在Chubby锁服务使用Paxos作为Chubby Cell中的一致性算法，Paxos的人气从此一路狂飙。

基于Paxos协议的数据同步与传统主备方式最大的区别在于：Paxos只需超过半数的副本在线且相互通信正常，就可以保证服务的持续可用，且数据不丢失。

Basic-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

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-Paxos

X-Paxos是X-DB中的Multi-Paxos实现，通过异步流水线化、Batching和Pipeline等手段提升性能。

参考资料

《阿里如何实现高性能分布式强一致的独立 Paxos 基础库》

PaxosStore

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

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详解》

Mulit-Raft

许多NewSQL数据库的数据规模上限都定位在100TB以上，为了负载均衡，都会对数据进行分片（sharding），所以就需要使用多个Raft集群（即Multi-Raft），每个Raft集群对应一个分片。

在多个Raft集群间可增加协同来减少资源开销、提升性能（如：共享通信链接、合并消息等）。

相关产品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft来保障数据一致性。

Parallel-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是基于对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