分布式算法

发表于 2022-06-22 分类于 distributed 阅读次数：

简介

分散式算法（英语：Distributed algorithm），一种算法类型。为分散式计算而设计，它运行在一群相互连结的处理器所构成的计算机硬件平台上。分散式算法以并行方式执行，是平行算法下的子类别。因为同时运行在不同处理器上，对算法其他部分运行情况的资讯所知有限，使得这类型的算法较为困难。

常见的分布式算法

分布式算法 - 一致性 Hash 算法
- 一致性 Hash 算法是个经典算法，Hash 环的引入是为解决 单调性(Monotonicity) 的问题；虚拟节点的引入是为了解决 平衡性(Balance) 问题
分布式算法 - Paxos 算法
- Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得 2013 年图灵奖。自 Paxos 问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性, 很多分布式一致性算法都由 Paxos 演变而来
分布式算法 - Raft 算法
- Paxos 是出了名的难懂，而 Raft 正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案
分布式算法 - ZAB 算法
- ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）, 它应该是所有一致性协议中生产环境中应用最多的了。为什么呢？因为他是为 Zookeeper 设计的分布式一致性协议！
分布式算法 - Snowflake 算法
- Snowflake，雪花算法是由 Twitter 开源的分布式 ID 生成算法，以划分命名空间的方式将 64-bit 位分割成多个部分，每个部分代表不同的含义。这种就是将 64 位划分为不同的段，每段代表不同的涵义，基本就是时间戳、机器 ID 和序列数。为什么如此重要？因为它提供了一种 ID 生成及生成的思路，当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer 的缓冲设计提高性能。

一致性 Hash 算法

一致性 Hash 算法简介

在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的 hash(object)%N 算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。

一致性哈希算法在 1997 年由麻省理工学院提出的一种分布式哈希(DHT)实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和 CARP 十分类似。一致性哈希修正了 CARP 使用的简单哈希算法带来的问题，使得分布式哈希(DHT)可以在 P2P 环境中真正得到应用。

一致性 hash 算法提出了在动态变化的 Cache 环境中，判定哈希算法好坏的四个定义:

平衡性(Balance): 平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
单调性(Monotonicity): 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
分散性(Spread): 在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

一致性 Hash 算法原理

Hash 环

使用常见的 hash 算法可以把一个 key 值哈希到一个具有 2^32 个桶的空间中。也可以理解成，将 key 值哈希到 [0, 2^32) 的一个数字空间中。我们假设这个是个首尾连接的环形空间。如下图:

distributed-algorithm-hash-1

假设我们现在有 key1,key2,key3,key4 4 个 key 值，我们通过一定的 hash 算法，将其对应到上面的环形 hash 空间中。

k1=hash(key1);
k2=hash(key2);
k3=hash(key3);
k4=hash(key4);

distributed-algorithm-hash-2

同样的，假设我们有 3 台 cache 服务器，把缓存服务器通过 hash 算法，加入到上述的环中。一般情况下是根据机器的 IP 地址或者唯一的计算机别名进行哈希。

1
2
3

c1=hash(cache1);
c2=hash(cache2);
c3=hash(cache3);

distributed-algorithm-hash-3

接下来就是数据如何存储到 cache 服务器上了，key 值哈希之后的结果顺时针找上述环形 hash 空间中，距离自己最近的机器节点，然后将数据存储到上面，如上图所示，k1 存储到 c3 服务器上， k4,k3 存储到 c1 服务器上， k2 存储在 c2 服务器上。用图表示如下:

distributed-algorithm-hash-4

删除节点

假设 cache3 服务器宕机，这时候需要从集群中将其摘除。那么，之前存储再 c3 上的 k1，将会顺时针寻找距离它最近的一个节点，也就是 c1 节点，这样，k1 就会存储到 c1 上了，看一看下下面的图，比较清晰。

distributed-algorithm-hash-5

摘除 c3 节点之后，只影响到了原先存储再 c3 上的 k1，而 k3、k4、k2 都没有受到影响，也就意味着解决了最开始的解决方案(hash(key)%N)中可能带来的雪崩问题。

增加节点

新增 C4 节点之后，原先存储到 C1 的 k4，迁移到了 C4，分担了 C1 上的存储压力和流量压力。

distributed-algorithm-hash-6

不平衡的问题

上面的简单的一致性 hash 的方案在某些情况下但依旧存在问题: 一个节点宕机之后，数据需要落到距离他最近的节点上，会导致下个节点的压力突然增大，可能导致雪崩，整个服务挂掉。

如下图所示:

distributed-algorithm-hash-7

当节点 C3 摘除之后，之前再 C3 上的 k1 就要迁移到 C1 上，这时候带来了两部分的压力:

之前请求到 C3 上的流量转嫁到了 C1 上,会导致 C1 的流量增加，如果之前 C3 上存在热点数据，则可能导致 C1 扛不住压力挂掉。
之前存储到 C3 上的 key 值转义到了 C1，会导致 C1 的内容占用量增加，可能存在瓶颈。

当上面两个压力发生的时候，可能导致 C1 节点也宕机了。那么压力便会传递到 C2 上，又出现了类似滚雪球的情况，服务压力出现了雪崩，导致整个服务不可用。这一点违背了最开始提到的四个原则中的 平衡性，节点宕机之后，流量及内存的分配方式打破了原有的平衡。

虚拟节点

“虚拟节点” (virtual node) 是实际节点 (机器) 在 hash 空间的复制品 (replica) ，一实际个节点 (机器) 对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。

依旧用图片来解释，假设存在以下的真实节点和虚拟节点的对应关系。

Visual100—> Real1
Visual101—> Real1
Visual200—> Real2
Visual201—> Real2
Visual300—> Real3
Visual301—> Real3

同样的，hash 之后的结果如下:

hash(Visual100)—> V100  —> Real1
hash(Visual101)—> V101  —> Real1
hash(Visual200)—> V200  —> Real2
hash(Visual201)—> V201  —> Real2
hash(Visual300)—> V300  —> Real3
hash(Visual301)—> V301  —> Real3

key 值的 hash 结果如上，这里暂时不写了。

distributed-algorithm-hash-8

和之前介绍的不添加虚拟节点的类似，主要聊下如果宕机之后的情况。

假设 Real1 机器宕机，则会发生一下情况。

原先存储在虚拟节点 V100 上的 k1 数据将迁移到 V301 上，也就意味着迁移到了 Real3 机器上。
原先存储再虚拟节点 V101 上的 k4 数据将迁移到 V200 上，也就意味着迁移到了 Real2 机器上。

结果如下图:

distributed-algorithm-hash-9

这个就解决之前的问题了，某个节点宕机之后，存储及流量压力并没有全部转移到某台机器上，而是分散到了多台节点上。解决了节点宕机可能存在的雪崩问题。

当物理节点多的时候，虚拟节点多，这个的雪崩可能就越小。

Paxos 算法

Paxos 算法简介

Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，使其获得 2013 年图灵奖。

Paxos 由 Lamport 于 1998 年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛 Paxos 作为比喻，描述了 Paxos 小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在 2001 年，Lamport 觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。

自 Paxos 问世以来就持续垄断了分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性。Google 的很多大型分布式系统都采用了 Paxos 算法来解决分布式一致性问题，如 Chubby、Megastore 以及 Spanner 等。开源的 ZooKeeper，以及 MySQL 5.7 推出的用来取代传统的主从复制的 MySQL Group Replication 等纷纷采用 Paxos 算法解决分布式一致性问题。

Paxos 算法推导

通常说 Paxos 算法是复杂算法难以理解是指其推导过程复杂。理论证明一个 Paxos 的实现，比实现这个 Paxos 还要难。一个成熟的 Paxos 实现很难独立产生，往往需要和一个系统结合在一起，通过一个或者多个系统来验证其可靠性和完备性。

理解 Paxos 算法的推导过程: https://blog.csdn.net/yeqiuzs/article/details/76862026

Basic Paxos 算法

Paxos 算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值(决议)达成一致。

Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2F+1 的容错能力，即 2F+1 个节点的系统最多允许 F 个节点同时出现故障。

一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos 算法使所有提案中的某一个提案，在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。

角色

Paxos 将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

Proposer: 提出提案 (Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
Acceptor: 参与决策，回应 Proposers 的提案。收到 Proposal 后可以接受提案，若 Proposal 获得多数 Acceptors 的接受，则称该 Proposal 被批准。
Learner: 不参与决策，从 Proposers/Acceptors 学习最新达成一致的提案(Value)。

在多副本状态机中，每个副本同时具有 Proposer、Acceptor、Learner 三种角色。

distributed-algorithm-paxos-1

可以理解为人大代表(Proposer)在人大向其它代表(Acceptors)提案，通过后让老百姓(Learner)落实。

3 个阶段

distributed-algorithm-paxos-2

第一阶段: Prepare 阶段

Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。

Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。
Promise: Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”。
- 承诺 1: 不再接受 Proposal ID 小于等于(注意: 这里是<= )当前请求的 Prepare 请求;
- 承诺 2: 不再接受 Proposal ID 小于(注意: 这里是< )当前请求的 Propose 请求;
- 应答: 不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。

第二阶段: Accept 阶段

Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的 Propose 请求进行 Accept 处理。

Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。
Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。

第三阶段: Learn 阶段

Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。

伪代码

distributed-algorithm-paxos-3

获取一个 Proposal ID n，为了保证 Proposal ID 唯一，可采用时间戳+Server ID 生成；
Proposer 向所有 Acceptors 广播 Prepare(n)请求；
Acceptor 比较 n 和 minProposal，如果 n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
Proposer 接收到过半数回复后，如果发现有 acceptedValue 返回，将所有回复中 acceptedProposal 最大的 acceptedValue 作为本次提案的 value，否则可以任意决定本次提案的 value；
到这里可以进入第二阶段，广播 Accept (n,value) 到所有节点；
Acceptor 比较 n 和 minProposal，如果 n>=minProposal，则 acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回 minProposal。
提议者接收到过半数请求后，如果发现有返回值 result >n，表示有更新的提议，跳转到 1；否则 value 达成一致。

实现举例

下面举几个例子，实例 1 如下图:

distributed-algorithm-paxos-4

图中 P 代表 Prepare 阶段，A 代表 Accept 阶段。3.1 代表 Proposal ID 为 3.1，其中 3 为时间戳，1 为 Server ID。X 和 Y 代表提议 Value。

实例 1 中 P 3.1 达成多数派，其 Value(X)被 Accept，然后 P 4.5 学习到 Value(X)，并 Accept。

distributed-algorithm-paxos-5

实例 2 中 P 3.1 没有被多数派 Accept(只有 S3 Accept)，但是被 P 4.5 学习到，P 4.5 将自己的 Value 由 Y 替换为 X，Accept(X)。

distributed-algorithm-paxos-6

实例 3 中 P 3.1 没有被多数派 Accept(只有 S1 Accept)，同时也没有被 P 4.5 学习到。由于 P 4.5 Propose 的所有应答，均未返回 Value，则 P 4.5 可以 Accept 自己的 Value (Y)。后续 P 3.1 的 Accept (X) 会失败，已经 Accept 的 S1，会被覆盖。

Paxos 算法可能形成活锁而永远不会结束，如下图实例所示:

distributed-algorithm-paxos-7

回顾两个承诺之一，Acceptor 不再应答 Proposal ID 小于等于当前请求的 Prepare 请求。意味着需要应答 Proposal ID 大于当前请求的 Prepare 请求。

两个 Proposers 交替 Prepare 成功，而 Accept 失败，形成活锁(Livelock)。

Paxos 算法拓展

Multi-Paxos 算法

原始的 Paxos 算法(Basic Paxos)只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos 搞不定了。因此 Basic Paxos 几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos 正是为解决此问题而提出。Multi-Paxos 基于 Basic Paxos 做了两点改进:

针对每一个要确定的值，运行一次 Paxos 算法实例(Instance)，形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。
在所有 Proposers 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptors 进行表决。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

distributed-algorithm-paxos-8

Multi-Paxos 首先需要选举 Leader，Leader 的确定也是一次决议的形成，所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal，在 Leader 宕机之后服务临时不可用，需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下，Prepare 阶段可以跳过。

Multi-Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例，从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段，后续只需要执行 Accept 阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个 Instance ID 标识，Instance ID 由 Leader 本地递增生成即可。

Multi-Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性，这样的场景即退化为 Basic Paxos。

Chubby 和 Boxwood 均使用 Multi-Paxos。ZooKeeper 使用的 Zab 也是 Multi-Paxos 的变形。

Raft 算法

Raft 是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。

动图模拟网址：

动画理解 Raft 神器
 Raft Visualization

Raft 算法简介

不同于 Paxos 算法直接从分布式一致性问题出发推导出来，Raft 算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。 Raft 实现了和 Paxos 相同的功能，它将一致性分解为多个子问题: Leader 选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等。同时，Raft 算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。

Raft 算法原理

角色

Raft 将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选人(Candidate):

Leader: 接受客户端请求，并向 Follower 同步请求日志，当日志同步到大多数节点上后告诉 Follower 提交日志。
Follower: 接受并持久化 Leader 同步的日志，在 Leader 告之日志可以提交之后，提交日志。
Candidate: Leader 选举过程中的临时角色。

Raft 要求系统在任意时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Followers。

角色状态转换

distributed-algorithm-raft-1

Follower 只响应其他服务器的请求。如果 Follower 超时没有收到 Leader 的消息，它会成为一个 Candidate 并且开始一次 Leader 选举。收到大多数服务器投票的 Candidate 会成为新的 Leader。 Leader 在宕机之前会一直保持 Leader 的状态。

distributed-algorithm-raft-2

Raft 算法将时间分为一个个的任期(term)，每一个 term 的开始都是 Leader 选举。在成功选举 Leader 之后，Leader 会在整个 term 内管理整个集群。如果 Leader 选举失败，该 term 就会因为没有 Leader 而结束。

Raft 实现了和 Paxos 相同的功能，它将一致性分解为多个子问题: Leader 选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等

Raft 算法子问题

Leader 选举

Raft 使用心跳(heartbeat)触发 Leader 选举。当服务器启动时，初始化为 Follower。Leader 向所有 Followers 周期性发送 heartbeat。如果 Follower 在选举超时时间内没有收到 Leader 的 heartbeat，就会等待一段随机的时间后发起一次 Leader 选举。

Follower 将其当前 term 加一然后转换为 Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC (RPC 细节参见八、Raft 算法总结)。结果有以下三种情况:

赢得了多数的选票，成功选举为 Leader；
收到了 Leader 的消息，表示有其它服务器已经抢先当选了 Leader；
没有服务器赢得多数的选票，Leader 选举失败，等待选举时间超时后发起下一次选举。

distributed-algorithm-raft-3

选举出 Leader 后，Leader 通过定期向所有 Followers 发送心跳信息维持其统治。若 Follower 一段时间未收到 Leader 的心跳则认为 Leader 可能已经挂了，再次发起 Leader 选举过程。

Raft 保证选举出的 Leader 上一定具有最新的已提交的日志，这一点将在安全性中说明。

日志同步

Leader 选出后，就开始接收客户端的请求。Leader 把请求作为日志条目(Log entries)加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC (RPC 细节参见八、Raft 算法总结)复制日志条目。当这条日志被复制到大多数服务器上，Leader 将这条日志应用到它的状态机并向客户端返回执行结果。

distributed-algorithm-raft-4

某些 Followers 可能没有成功的复制日志，Leader 会无限的重试 AppendEntries RPC 直到所有的 Followers 最终存储了所有的日志条目。

日志由有序编号(log index)的日志条目组成。每个日志条目包含它被创建时的任期号(term)，和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交(commit)了。

distributed-algorithm-raft-5

Raft 日志同步保证如下两点:

如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于 Leader 在一个 term 内在给定的一个 log index 最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader 会把新日志条目紧接着之前的条目的 log index 和 term 都包含在里面。如果 Follower 没有在它的日志中找到 log index 和 term 都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader 和 Followers 的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader 崩溃可能会导致日志不一致: 旧的 Leader 可能没有完全复制完日志中的所有条目。

distributed-algorithm-raft-6

上图阐述了一些 Followers 可能和新的 Leader 日志不同的情况。一个 Follower 可能会丢失掉 Leader 上的一些条目，也有可能包含一些 Leader 没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader 通过强制 Followers 复制它的日志来处理日志的不一致，Followers 上的不一致的日志会被 Leader 的日志覆盖。

Leader 为了使 Followers 的日志同自己的一致，Leader 需要找到 Followers 同它的日志一致的地方，然后覆盖 Followers 在该位置之后的条目。

Leader 会从后往前试，每次 AppendEntries 失败后尝试前一个日志条目，直到成功找到每个 Follower 的日志一致位点，然后向后逐条覆盖 Followers 在该位置之后的条目。

安全性

Raft 增加了如下两条限制以保证安全性:

拥有最新的已提交的 log entry 的 Follower 才有资格成为 Leader。

这个保证是在 RequestVote RPC 中做的，Candidate 在发送 RequestVote RPC 时，要带上自己的最后一条日志的 term 和 log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条 log entry 的 term 更大，则 term 大的更新，如果 term 一样大，则 log index 更大的更新。

Leader 只能推进 commit index 来提交当前 term 的已经复制到大多数服务器上的日志，旧 term 日志的提交要等到提交当前 term 的日志来间接提交(log index 小于 commit index 的日志被间接提交)。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况:

distributed-algorithm-raft-7

在阶段 a，term 为 2，S1 是 Leader，且 S1 写入日志(term, index)为(2, 2)，并且日志被同步写入了 S2；

在阶段 b，S1 离线，触发一次新的选主，此时 S5 被选为新的 Leader，此时系统 term 为 3，且写入了日志(term, index)为(3， 2);

S5 尚未将日志推送到 Followers 就离线了，进而触发了一次新的选主，而之前离线的 S1 经过重新上线后被选中变成 Leader，此时系统 term 为 4，此时 S1 会将自己的日志同步到 Followers，按照上图就是将日志(2， 2)同步到了 S3，而此时由于该日志已经被同步到了多数节点(S1, S2, S3)，因此，此时日志(2，2)可以被提交了。；

在阶段 d，S1 又下线了，触发一次选主，而 S5 有可能被选为新的 Leader (这是因为 S5 可以满足作为主的一切条件: 1. term = 5 > 4，2. 最新的日志为(3，2)，比大多数节点(如 S2/S3/S4) 的日志都新)，然后 S5 会将自己的日志更新到 Followers，于是 S2、S3 中已经被提交的日志(2，2)被截断了。

增加上述限制后，即使日志(2，2)已经被大多数节点(S1、S2、S3)确认了，但是它不能被提交，因为它是来自之前 term(2)的日志，直到 S1 在当前 term(4)产生的日志(4， 4)被大多数 Followers 确认，S1 方可提交日志(4，4)这条日志，当然，根据 Raft 定义，(4，4)之前的所有日志也会被提交。此时即使 S1 再下线，重新选主时 S5 不可能成为 Leader，因为它没有包含大多数节点已经拥有的日志(4，4)。

日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft 采用对整个系统进行 snapshot 来解决，snapshot 之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行 snapshot，并且只能对已经提交的日志记录进行 snapshot。

Snapshot 中包含以下内容:

日志元数据。最后一条已提交的 log entry 的 log index 和 term。这两个值在 snapshot 之后的第一条 log entry 的 AppendEntries RPC 的完整性检查的时候会被用上。
系统当前状态。

当 Leader 要发给某个日志落后太多的 Follower 的 log entry 被丢弃，Leader 会将 snapshot 发给 Follower。或者当新加进一台机器时，也会发送 snapshot 给它。发送 snapshot 使用 InstalledSnapshot RPC。

做 snapshot 既不要做的太频繁，否则消耗磁盘带宽，也不要做的间隔太久，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次 snapshot。

做一次 snapshot 可能耗时过长，会影响正常日志同步。可以通过使用 copy-on-write 技术避免 snapshot 过程影响正常日志同步。

成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向 Leader 发送成员变更请求，Leader 复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置(Cold)切换到新成员配置(Cnew)。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置(Cold)切换到新成员配置(Cnew)的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在 Cold 和 Cnew 中同时存在两个不相交的多数派，进而可能选出两个 Leader，形成不同的决议，破坏安全性。

distributed-algorithm-raft-8

由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。

为了解决这一问题，Raft 提出了两阶段的成员变更方法。集群先从旧成员配置 Cold 切换到一个过渡成员配置，称为共同一致(joint consensus)，共同一致是旧成员配置 Cold 和新成员配置 Cnew 的组合 Cold U Cnew，一旦共同一致 Cold U Cnew 被提交，系统再切换到新成员配置 Cnew。

distributed-algorithm-raft-9

Raft 两阶段成员变更过程如下:

Leader 收到成员变更请求从 Cold 切成 Cnew；
Leader 在本地生成一个新的 log entry，其内容是 Cold U Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该 log entry 复制至 Cold U Cnew 中的所有副本。在此之后新的日志同步需要保证得到 Cold 和 Cnew 两个多数派的确认；
Follower 收到 Cold U Cnew 的 log entry 后更新本地日志，并且此时就以该配置作为自己的成员配置；
如果 Cold 和 Cnew 中的两个多数派确认了 Cold U Cnew 这条日志，Leader 就提交这条 log entry；
接下来 Leader 生成一条新的 log entry，其内容是新成员配置 Cnew，同样将该 log entry 写入本地日志，同时复制到 Follower 上；
Follower 收到新成员配置 Cnew 后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在 Cnew 这个成员配置中会自动退出；
Leader 收到 Cnew 的多数派确认后，表示成员变更成功，后续的日志只要得到 Cnew 多数派确认即可。Leader 给客户端回复成员变更执行成功。

异常分析:

如果 Leader 的 Cold U Cnew 尚未推送到 Follower，Leader 就挂了，此后选出的新 Leader 并不包含这条日志，此时新 Leader 依然使用 Cold 作为自己的成员配置。
如果 Leader 的 Cold U Cnew 推送到大部分的 Follower 后就挂了，此后选出的新 Leader 可能是 Cold 也可能是 Cnew 中的某个 Follower。
如果 Leader 在推送 Cnew 配置的过程中挂了，那么同样，新选出来的 Leader 可能是 Cold 也可能是 Cnew 中的某一个，此后客户端继续执行一次改变配置的命令即可。
如果大多数的 Follower 确认了 Cnew 这个消息后，那么接下来即使 Leader 挂了，新选出来的 Leader 肯定位于 Cnew 中。
两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对 Cold 与 Cnew 的关系没有做任何假设，为了避免 Cold 和 Cnew 各自形成不相交的多数派选出两个 Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设 Cold 与 Cnew 任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制 Cold 与 Cnew，使之任意的多数派交集不为空呢? 方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold 与 Cnew 不可能形成两个不相交的多数派。

一阶段成员变更:

成员变更限制每次只能增加或删除一个成员(如果要变更多个成员，连续变更多次)。
成员变更由 Leader 发起，Cnew 得到多数派确认后，返回客户端成员变更成功。
一次成员变更成功前不允许开始下一次成员变更，因此新任 Leader 在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
Leader 只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

ZAB 算法

ZAB 算法简介

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。

Zookeeper 是一个为分布式应用提供高效且可靠的分布式协调服务。在解决分布式一致性方面，Zookeeper 并没有使用 Paxos ，而是采用了 ZAB 协议。
ZAB 协议定义： ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。
基于该协议，Zookeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性。具体如下图所示：

上图显示了 Zookeeper 如何处理集群中的数据。所有客户端写入数据都是写入到主进程（称为 Leader）中，然后，由 Leader 复制到备份进程（称为 Follower）中。从而保证数据一致性。从设计上看，和 Raft 类似。
那么复制过程又是如何的呢？复制过程类似 2PC，ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交，大大减小了同步阻塞。也提高了可用性。

简单介绍完，开始重点介绍 消息广播 和 崩溃恢复。 整个 Zookeeper 就是在这两个模式之间切换。简而言之，当 Leader 服务可以正常使用，就进入消息广播模式，当 Leader 不可用时，则进入崩溃恢复模式。

消息广播

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似一个二阶段提交过程。对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数成功响应，则执行 commit 操作（先提交自己，再发送 commit 给所有 Follwer）。

基本上，整个广播流程分为 3 步骤：

1.将数据都复制到 Follwer 中

distributed-algorithm-zab-2

等待 Follwer 回应 Ack，最低超过半数即成功

distributed-algorithm-zab-3

当超过半数成功回应，则执行 commit ，同时提交自己

distributed-algorithm-zab-4

通过以上 3 个步骤，就能够保持集群之间数据的一致性。实际上，在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，避免同步，实现异步解耦。

还有一些细节：

Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务 ID（ZXID），ZAB 兮协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。
在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。
zookeeper 集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。
实际上，这是一种简化版本的 2PC，不能解决单点问题。等会我们会讲述 ZAB 如何解决单点问题（即 Leader 崩溃问题）。

崩溃恢复

刚刚我们说消息广播过程中，Leader 崩溃怎么办？还能保证数据一致吗？如果 Leader 先本地提交了，然后 commit 请求没有发送出去，怎么办？

实际上，当 Leader 崩溃，即进入我们开头所说的崩溃恢复模式（崩溃即：Leader 失去与过半 Follwer 的联系）。下面来详细讲述。

假设 1：Leader 在复制数据给所有 Follwer 之后崩溃，怎么办？
假设 2：Leader 在收到 Ack 并提交了自己，同时发送了部分 commit 出去之后崩溃怎么办？

针对这些问题，ZAB 定义了 2 个原则：

ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
ZAB 协议确保丢弃那些只在 Leader 提出/复制，但没有提交的事务。

所以，ZAB 设计了下面这样一个选举算法：能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。

针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。

而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

distributed-algorithm-zab-5

这样，我们刚刚假设的两个问题便能够解决。假设 1 最终会丢弃调用没有提交的数据，假设 2 最终会同步所有服务器的数据。这个时候，就引出了一个问题，如何同步？

数据同步

当崩溃恢复之后，需要在正式工作之前（接收客户端请求），Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了，即是否完成了数据同步。目的是为了保持数据一致。

当所有的 Follwer 服务器都成功同步之后，Leader 会将这些服务器加入到可用服务器列表中。

实际上，Leader 服务器处理或丢弃事务都是依赖着 ZXID 的，那么这个 ZXID 如何生成呢？

答：在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。

而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 epoch 值，然后再对这个值加一。

distributed-algorithm-zab-6

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。

基于这样的策略：当 Follower 链接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

ZXID 原理

zxid 就是上面提到的事务编号，是一个 8 字节的整型数字，但是 ZK 设计的时候把这一个数字拆成了两部分使用，一鱼两吃！

8 个字节的整数一共有 64 位长度，前 32 位用来记录 epoch，后 32 位就是用来计数。你可能要问了？ epoch？是啥？

zxid 初始化是 0，也就是这样

1	00000000000000000000000000000000 00000000000000000000000000000000

每一次写请求都会增加后 32 位，假设现在进行了 10 次写请求（无论该请求有没有真的修改到数据），zxid 就会变成这样

1	00000000000000000000000000000000 00000000000000000000000000001010

当进行一次选举的时候，前 32 位就会增加 1，并且清零后 32 位

1	00000000000000000000000000000001 00000000000000000000000000000000

除了选举以外，当后 32 位彻底用完（变成全 1，也就是 ZK 正常执行了 2^32 - 1 次写请求都没进行过一次选举，牛逼！）也会让前 32 位增加 1，相当于进位

# 进位前
00000000000000000000000000000000 11111111111111111111111111111111
# 进位后
00000000000000000000000000000001 00000000000000000000000000000000

到这里我就可以回答大家前面的问题了，epoch 就是 zxid 前 32 位的这个数字，epoch 本身的翻译是 “纪元，时代” 的意思，意味着更新换代，而 zxid 的后 32 位数字仅仅是写请求的计数罢了

总结

ZAB 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有一个 Leader，用来保证一致性（Paxos 并没有使用 Leader 机制保证一致性）。再有采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。

ZAB 让整个 Zookeeper 集群在两个模式之间转换，消息广播和崩溃恢复，消息广播可以说是一个简化版本的 2PC，通过崩溃恢复解决了 2PC 的单点问题，通过队列解决了 2PC 的同步阻塞问题。

而支持崩溃恢复后数据准确性的就是数据同步了，数据同步基于事务的 ZXID 的唯一性来保证。通过 + 1 操作可以辨别事务的先后顺序。

Snowflake 算法

Snowflake 算法简介

Snowflake，雪花算法是由 Twitter 开源的分布式 ID 生成算法，以划分命名空间的方式将 64-bit 位分割成多个部分，每个部分代表不同的含义。这种就是将 64 位划分为不同的段，每段代表不同的涵义，基本就是时间戳、机器 ID 和序列数。为什么如此重要？因为它提供了一种 ID 生成及生成的思路，当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer 的缓冲设计提高性能。

Snowflake 算法原理

Snowflake，雪花算法是由 Twitter 开源的分布式 ID 生成算法，以划分命名空间的方式将 64-bit 位分割成多个部分，每个部分代表不同的含义。而 Java 中 64 bit 的整数是 Long 类型，所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

第 1 位占用 1 bit，其值始终是 0，可看做是符号位不使用。
第 2 位开始的 41 位是时间戳，41-bit 位可表示 2^41 个数，每个数代表毫秒，那么雪花算法可用的时间年限是 (1L<<41)/(1000*60*24*365)=69 年的时间。
中间的 10-bit 位可表示机器数，即 2^10 = 1024 台机器，但是一般情况下我们不会部署这么台机器。如果我们对 IDC（互联网数据中心）有需求，还可以将 10 bit 分 5 bit 给 IDC，分 5 bit 给工作机器。这样就可以表示 32 个 IDC，每个 IDC 下可以有 32 台机器，具体的划分可以根据自身需求定义。
最后 12-bit 位是自增序列，可表示 2^12 = 4096 个数。

这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生 4096 个有序的不重复的 ID。但是我们 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序 ID 数是翻倍的。

distributed-algorithm-snowflake-1

Snowflake 的 Twitter 官方原版是用 Scala 写的，对 Scala 语言有研究的同学可以去阅读下，以下是 Java 版本的写法。

package example.distributed.snowflake;

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。
 * 41位的时间截，可以使用69年，年 T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，
 * 经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeDistributeId {

    // ==============================Fields===========================================

    /**
     * 开始时间截 (2020-01-01)
     */
    private final long twepoch = 1577808000000L;

    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据标识id所占的位数
     */
    private final long datacenterIdBits = 5L;

    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /**
     * 序列在id中占的位数
     */
    private final long sequenceBits = 12L;

    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;

    /**
     * 数据标识id向左移17位(12+5)
     */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /**
     * 时间截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作机器ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeDistributeId(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================

    /**
     * 获得下一个ID (该方法是线程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     *
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

测试的代码如下

public static void main(String[] args) {
    SnowflakeDistributeId idWorker = new SnowflakeDistributeId(0, 0);
    for (int i = 0; i < 1000; i++) {
        long id = idWorker.nextId();
//      System.out.println(Long.toBinaryString(id));
        System.out.println(id);
    }
}

雪花算法提供了一个很好的设计思想，雪花算法生成的 ID 是趋势递增，不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的，而且可以根据自身业务特性分配 bit 位，非常灵活。

但是雪花算法强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些 ID，而时间回退后，生成的 ID 就有可能重复。官方对于此并没有给出解决方案，而是简单的抛错处理，这样会造成在时间被追回之前的这段时间服务不可用。

很多其他类雪花算法也是在此思想上的设计然后改进规避它的缺陷，后面介绍的百度 UidGenerator 和 美团分布式ID生成系统 Leaf 中 snowflake 模式都是在 snowflake 的基础上演进出来的。

对比

Raft 与 Multi-Paxos 对比

Raft 与 Multi-Paxos 都是基于领导者的一致性算法，乍一看有很多地方相同，下面总结一下 Raft 与 Multi-Paxos 的异同。

Raft 与 Multi-Paxos 中相似的概念:

Raft	Multi-Paxos
Leader	Proposer
Term	Proposal ID
Log	Proposal Value
Log index	Instance ID
RequestVote	Prepare 阶段
AppendEntries	Proposer
Leader	Accept 阶段

Raft 与 Multi-Paxos 的不同:

	Raft	Multi-Paxos
领导者	唯一 Leader	允许多 Proposer
领导者选举权	具有最新提交的日志的副本	任意副本
日志连续性	保证连续	允许空洞
日志提交	推进 commit index	异步的 Commit 消息

简介