# 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 to Support Highly-Available Distributed Systems》中首次提出了解决 Paxos 问题的算法。

Paxos 算法由 Leslie Lamport 于 1989 年完成，1990 年在论文《The Part-time Parliament》中提出，1998 年在 ACM Transactions on Computer Systems (TOCS) 上正式发表的 [Paxos](http://research.microsoft.com/users/lamport/pubs/lamport-paxos.pdf) 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 算法本质上与前者相同，被广泛应用在 Chubby、ZooKeeper 这样的分布式系统中。Leslie Lamport 作为分布式系统领域的早期研究者，因为相关杰出贡献获得了 2013 年度图灵奖。

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

Paxos 是首个得到证明并被广泛应用的共识算法，其原理类似于 [两阶段提交](https://en.wikipedia.org/wiki/Two-phase_commit_protocol) 算法，进行了泛化和扩展，通过消息传递来逐步消除系统中的不确定状态。

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

*注：Leslie Lamport 对密码学也有研究，1979 年提出的多 Hash 签名机制，具备抗量子计算攻击特性。*

### 基本原理

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

* 提案者（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）。准备阶段通过锁来解决对哪个提案内容进行确认的问题，提交阶段解决大多数确认最终值的问题。

**准备阶段**：

* 提案者向多个接受者发送计划提交的提案编号 n，试探是否可以锁定多数接受者的支持；
* 接受者 i 收到提案编号 n，检查回复过的提案的最大编号 M\_i。如果 n > M\_i，则向提案者返回准备接受（accept）提交的最大编号的提案 P\_i（如果还未接受过任何提案，则为空），并不再接受小于 n 的提案，同时更新 M\_i = n。这一步是让接受者筛选出它收到的最大编号的提案，接下来只接受其后续提交。

**提交阶段**：

* 某个提案者如果收到大多数接受者的回复（表示大部分人收到了 n），则准备发出带有 n 的提交消息。如果收到的回复中带有提案 P\_i（说明自己看到的信息过期），则替换选编号最大的 P\_i 的值为提案值；否则指定一个新提案值。如果没收到大多数回复，则再次发出请求；
* 接受者 i 收到序号为 n 的提交消息，如果发现 n >= P\_i 的序号，则接受提案，并更新 P\_i 序号为 n。

一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认。之后可以开始新一轮的提交确认。

需要注意，Paxos 并不一定能保证每一轮都能提交提案。

## Raft 算法

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

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

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

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

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

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