Paxos 算法与 Raft 算法

Paxos 问题是指分布式的系统中存在故障（crash fault），但不存在恶意（corrupt）节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。这也是分布式共识领域最为常见的问题。因为最早是 Leslie Lamport 用 Paxos 岛的故事模型来进行描述，而得以命名。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 算法

1988 年，Brian M. Oki 和Barbara H. Liskov 在论文《Viewstamped Replication: A New Primary Copy Method toSupport Highly-Available Distributed Systems》中首次提出了解决 Paxos 问题的算法。

1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 算法本质上与前者相同，被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者，因为相关杰出贡献获得了 2013 年度图灵奖。

论文中为了描述问题编造了一个虚构故事：在古代爱琴海的 Paxos 岛，议会如何通过表决来达成共识。议员们通过信使传递消息来对议案进行表决。但议员可能离开，信使可能走丢，甚至重复传递消息。

Paxos 是首个得到证明并被广泛应用的共识算法，其原理类似 两阶段提交 算法，进行了泛化和扩展，通过消息传递来逐步消除系统中的不确定状态。

作为后来很多共识算法（如 Raft、ZAB 等）的基础，Paxos 算法基本思想并不复杂，但最初论文中描述比较难懂，甚至连发表也几经波折。2001 年，Leslie Lamport 还专门发表论文《Paxos Made Simple》进行重新解释。

基本原理

算法中存在三种逻辑角色的节点，在实现中同一节点可以担任多个角色。

  • 提案者（Proposer）：提出一个提案，等待大家批准（Chosen）为结案（Value）。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色。
  • 接受者（Acceptor）：负责对提案进行投票，接受（Accept）提案。往往由服务端担任该角色。
  • 学习者（Learner）：获取批准结果，并帮忙传播，不参与投票过程。可为客户端或服务端。

算法需要满足安全性（Safety） 和存活性（Liveness）两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的。

  • Safety：保证决议（Value）结果是对的，无歧义的，不会出现错误情况。
    • 只有是被提案者提出的提案才可能被最终批准；
    • 在一次执行中，只批准（chosen）一个最终决议。被多数接受（accept）的结果成为决议；
  • Liveness：保证决议过程能在有限时间内完成。
    • 决议总会产生，并且学习者能获得被批准的决议。

基本思路类似两阶段提交：多个提案者先要争取到提案的权利（得到大多数接受者的支持）；成功的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。

Paxos 并不保证系统总处在一致的状态。但由于每次达成共识至少有超过一半的节点参与，这样最终整个系统都会获知共识结果。一个潜在的问题是提案者在提案过程中出现故障，这可以通过超时机制来缓解。极为凑巧的情况下，每次新一轮提案的提案者都恰好故障，又或者两个提案者恰好依次提出更新的提案，则导致活锁，系统会永远无法达成共识（实际发生概率很小）。

Paxos 能保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案，会发现在满足各种约束情况下，算法过程总会十分类似 Paxos 的过程。这也是为何 Google Chubby 的作者 Mike Burrows 说：“这个世界上只有一种一致性算法，那就是 Paxos（There is only one consensus protocol, and that’s Paxos）”。

下面，由简单情况逐步推广到一般情况来探讨算法过程。

单个提案者+多接受者

如果系统中限定只允许某个特定节点是提案者，那么共识结果很容易能达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接受者的投票，即可认为通过，因为系统中不存在其他的提案。

但此时一旦提案者故障，则整个系统无法工作。

多个提案者+单个接受者

限定某个特定节点作为接受者。这种情况下，共识也很容易达成，接受者收到多个提案，选第一个提案作为决议，发送给其它提案者即可。

缺陷也是容易发生单点故障，包括接受者故障或首个提案者节点故障。

以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提案者和接受者都推广到多个的情形，会出现一些挑战。

多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障，那么就得允许出现多个提案者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间、序列、或者大家猜拳（出一个参数来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对他们进行区分呢？这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。

如何为提案分配序号呢？一种可能方案是每个节点的提案数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提案，意味着很可能单个提案人无法集齐足够多的投票；另一方面，提案者即便收到了多数接受者的投票，也不敢说就一定通过。因为在此过程中投票者无法获知其它投票人的结果，也无法确认提案人是否收到了自己的投票。因此，需要实现两个阶段的提交过程。

两阶段的提交

提案者发出提案申请之后，会收到来自接受者的反馈。一种结果是提案被大多数接受者接受了，一种结果是没被接受。没被接受的话，可以过会再重试。即便收到来自大多数接受者的答复，也不能认为就最终确认了。因为这些接受者自己并不知道自己刚答复的提案可以构成大多数的一致意见。

很自然的，需要引入新的一个阶段，即提案者在第一阶段拿到所有的反馈后，需要再次判断这个提案是否得到大多数的支持，如果支持则需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备（Prepare）和提交（Commit）。准备阶段通过锁来解决对哪个提案内容进行确认的问题，提交阶段解决大多数确认最终值的问题。

准备阶段：

  • 提案者发送自己计划提交的提案的编号到多个接受者，试探是否可以锁定多数接受者的支持。
  • 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。

提交阶段：

  • 提案者如果收到大多数的回复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功。则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求。
  • 接受者收到接受消息后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。

一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认。

Raft 算法

Paxos 算法虽然给出了共识设计，但并没有讨论太多实现细节，也并不重视工程上的优化，因此后来在学术界和工程界出现了一些改进工作，包括 Fast Paxos、Multi-Paxos，Zookeeper Atomic Broadcast（ZAB）和 Raft 等。这些算法重点在于改进执行效率和可实现性。

其中，Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出，基于 Multi-Paxos 算法进行重新简化设计和实现，提高了工程实践性。Raft 算法的主要设计思想与 ZAB 类型，通过先选出领导节点来简化流程和提高效率。实现上分解了领导者选举、日志复制和安全方面的考虑，并通过约束减少了不确定性的状态空间。

算法包括三种角色：领导者（Leader）、候选者（Candidate） 和跟随者（Follower），每个任期内选举一个全局的领导者。领导者角色十分关键，决定日志（log）的提交。每个日志都会路由到领导者，并且只能由领导者向跟随者单向复制。

典型的过程包括两个主要阶段：

  • 领导者选举：开始所有节点都是跟随者，在随机超时发生后未收到来自领导者或候选者消息，则转变角色为候选者（中间状态），提出选举请求。最近选举阶段（Term）中得票超过一半者被选为领导者；如果未选出，随机超时后进入新的阶段重试。领导者负责从客户端接收请求，并分发到其他节点；
  • 同步日志：领导者会决定系统中最新的日志记录，并强制所有的跟随者来刷新到这个记录，数据的同步是单向的，确保所有节点看到的视图一致。

此外，领导者会定期向所有跟随者发送心跳消息，跟随者如果发现心跳消息超时未收到，则可以认为领导者已经下线，尝试发起新的选举过程。