Paxos与Raft算法

Paxos 问题是指分布式的系统中存在故障（ fault） ，但不存在恶意（ corrupt） 节点场景（ 即可能消息丢失或重复，但无错误消息） 下的共识达成（ Consensus） 问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。

Paxos

1990 年由 Leslie Lamport 提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（ 存在极小的概率无法实现一致） 的机制。Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中，Leslie Lamport 因此获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

Paxos 是第一个被证明的共识算法，其原理基于 两阶段提交并进行扩展。

作为现在共识算法设计的鼻祖，以最初论文的难懂（ 算法本身并不复杂） 出名。算法中将节点分为三种类型：

proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；

acceptor：负责对提案进行投票。往往是服务端担任该角色；

learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

并且，算法需要满足 safety 和 liveness 两方面的约束要求（ 实际上这两个基础属性是大部分分布式算法都该考虑的） ：

safety：保证决议结果是对的，无歧义的，不会出现错误情况。

决议（ value） 只有在被 proposers 提出的 proposal 才能被最终批准；

在一次执行实例中，只批准（ chosen） 一个最终决议，意味着多数接受（ accept）的结果能成为决议；

liveness：保证决议过程能在有限时间内完成。

决议总会产生，并且 learners 能获得被批准（ chosen） 的决议。

基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（ 概率很小） 。

Paxos 能保证在超过1/2的正常节点存在时，系统能达成共识。

单个提案者+多接收者

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

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

多个提案者+单个接收者

限定某个节点作为接收者。这种情况下，共识也很容易达成，接收者收到多个提案，选第一 个提案作为决议，拒绝掉后续的提案即可。

缺陷也是容易发生单点故障，包括接收者故障或首个提案者节点故障。以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。当提案者和接收者都推广到多个的情形，会出现一些挑战。

多个提案者+多个接收者

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

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

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

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

此外，提案者即便收到了多数接收者的投票，也不敢说就一定通过。因为在此过程中系统可能还有其它的提案。

两阶段的提交

提案者发出提案之后，收到一些反馈。一种结果是自己的提案被大多数接受了，另一种结果是没被接受。没被接受的话好说，过会再试试。

即便收到来自大多数的接受反馈，也不能认为就最终确认了。因为这些接收者自己并不知道自己刚反馈的提案就恰好是全局的绝大多数。

很自然的，引入了新的一个阶段，即提案者在前一阶段拿到所有的反馈后，判断这个提案是可能被大多数接受的提案，需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备（ prepare） 和提交（ commit） 。准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。

准备阶段：

提案者发送自己计划提交的提案的编号到多个接受者，试探是否可以锁定多数接受者的支持。

接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到的提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（ 如果还未接受过任何提案，则为空） 给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。

提交阶段：

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

接受者收到接受消息后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。

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

Raft

Raft算法是Paxos 算法的一种简化实现。

包括三种角色：leader、candidate 和 follower，其基本过程为：

Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最 多者被选为 leader；

同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记 录；

注：此处 log 并非是指日志消息，而是各种事件的发生记录。