Paxos 与 Raft

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

Paxos

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

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

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

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

• proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
• acceptor：负责对提案进行投票。往往是服务端担任该角色；
• learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

并满足safetey 和 liveness 两方面的约束要求：

• safety：保证决议结果是对的，无歧义的。
  • 决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；
  • 在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议；
• liveness：保证能在有限时间内正常运行。
  • 决议总会产生，并且 learners 能获得被批准（chosen）的决议。

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

Paxos 能保证在超过一半的正常节点存在时，系统能达成一致。

读者可以试着自己设计一套能达成一致性的方案，会发现在满足各种约束情况下，算法自然就会那样设计。

单个提案者+多接收者

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

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

多个提案者+单个接收者

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

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

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

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

多个提案者+多个接收者

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

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

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

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

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

两阶段的提交

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

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

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

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

下面，我们简化认为更大的提案号意味着更新的提案。

准备阶段，比较简单，多个提案者可以发送提案：<id, value>，接收者收到提案就返回收到消息，并且只保留最新的提案。如果收到一个请求的提案号比目前保留的小，则返回保留的提案给提案者，告诉它已经有其它人发出更新的提案了。

提交阶段，如果一个提案者在准备阶段收到大多数的回复（表示大部分人听到它的请求，可能做好了最终确认的准备了），则再次发出确认消息。如果再次收到大多数的回复，并且大家都返回空，则带上原来的提案号和内容；如果返回中有更新的提案，则替换提案值为更新提案的值。如果没收到足够多的回复，则需要再次发出请求。

接收者如果发现这个提案号跟自己目前保留的一致，则确认该提案。

Raft

Raft 是对 Paxos 的重新设计和实现。

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

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

• Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader；
• 同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录；

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