分布式基石｜最难 paxos 和最易 raft？，java 排序算法面试题

3?加个状态机就起飞了

什么是状态机？

状态机全称为有限状态机。它接收条件的触发，由一种状态转变为新的状态。初始状态相同，输入的一系列事件相同，那么它最终的状态一定相同。

这可太常见了，比如 rocksdb，leveldb 等等 lsm 存储，它们数据先写 append log ，通过重放日志到达的系统状态一定是一致的。

这种状态机的应用模式可不仅限于存储服务。

到这，我相信童鞋们已经很豁然开朗了，只要我们通过 paxos 来产生分布式一致的有序的操作日志，加上状态机的配合，实现一个分布式存储服务必然不是问题。

通过不停的确定一个个值，形成一个有序的操作系列，配合状态机的应用，这，就是 paxos 的工程化方向。

4?活锁的问题怎么解决？

对于 paxos 来说，Proposer 和 Acceptor 角色是可以重叠的，每个节点既可以是 Proposer，也可以是 Acceptor ，或者两者都是。

这带来了非常大的灵活，每一个 Proposer 都可以递交协议（写入数据），但由于最终只能确定一个值，那么这会导致非常多的无效功，这期间是使用类似乐观锁来解决那些冲突的提议。

比如说，A 刚递交一个提案，B 就递交一个新提案导致 A 的提案被否定了，然后 A 又迅速递交一个提案，形成了一种类似活锁的状态，这时间就浪费了呀。

怎么解决？

问题根因在于可以提案的点太多，大家都是平等的。那么统一声音才能解决这个问题。于是 Leader 就应运而生。通过某种方法指定一个节点为 Leader ，只有一个节点能递交提案，这样就解决了混乱问题，效率提随之提升（这就是 Multi-Paxos ）。

5?paxos 工程化小结

小结一下，如果要将一个 paxos 工程化落地，衍生了哪些东西：

1. paxos 本质是确定一个值，把参与确定这个值的角色打包称为一组实例（ paxos instance ）；2.不同实例之间决议互不干扰。多组 paxos 实例确定多个值，形成一组操作序列，也是就日志?；

2. 日志 +?状态机?可以成为任何有意义的工程系统；

3. 为了解决递交提案混乱可能引发的效率问题（比如活锁），可以通过指定 Leader 角色来解决；

慢着，这个工程化方向咋这么眼熟呢？

这不就是 raft ！

raft 协议

终于到了 raft 协议，raft 的论文开篇就是这么一段话：

Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos;

raft 证明和 paxos 等价，raft 是一种日志复制的一致性算法。

看懂了吗？raft 的着眼点就是 日志+状态机 的方向。

划重点：raft 天生就是 paxos 协议工程化的一种样子。

如下图：

图里交代了关键模块：

1. 客户端（ Client ）：就是用户嘛，写入数据的就是它喽；

2. 一致性模块（ Consensus Module ）：负责写入 log，并且把 log 复制到其他节点；

3. 状态机（ State Machine ）：输入 log ，推进变更系统状态；

raft 确实比 paxos 简单啊，因为它已经把实现程序交互的样子都画出来了。

在 raft 论文里面直接把几个因素交代清楚了：

1. raft 就是管理日志复制的算法；

2. 日志 + 状态机 就能落地一个一致性的系统应用；

3. 集群角色有分类，Leader 作为唯一的写入点，所有日志复制是 Leader 到 Follower 单项传输；

说实话，上面的这些知识点都是我们对 paxos 工程化的长时间推导才想明白的。

没想到 raft 论文上来就给整好了，所以我才说，raft 协议出生就是为了解决工程化的问题的。

raft 把一致性归纳成三个核心问题：

1. Leader 的选举；

2. 日志的复制；

3. 正确性的保证（约束条件）；

其实真正要做的就两个，第三个问题贯穿前两个事情：

1. 选出一个 Leader ；

2. 把 Leader 的日志复制分发到 Follower 节点；

我们下面来看下这两个事情是怎么做的。

而用户则只好奇两个事情：

1. 数据怎么读写？

2. 节点扩缩容怎么搞？

1?Leader 选举

角色转变：

简单看下 raft 协议中关于 Leader 选举的部分。下面是角色转化图，非常清晰：

图里至少能得到这么几点知识点：

1. 系统开始每个节点都是从 Follower 角色开始；

2. 定时器超时之后，角色转变为 Candidate ，开始竞选 Leader；

3. Candidate 如果获得多数人的支持，那么选举成功，角色转变为 Leader 。如果选举失败，那么退为 Follower ；

Leader 选举成功之后则可以对外提供服务。

在论文中，为了让选举更高效（避免类似活锁的场景），各个节点的定时器间隔是随机值。

服务时间线：

从时间线来看，可以分为两部分时间（如下图）：

1. 无 Leader 状态（选举中）；

2. 正常状态（ Leader ）；

每个 Leader 都有自己的任期，注意：无 Leader 的状态是停服状态。

Leader 选举的规则？

被多数节点接受并且持久化的的日志叫做 committed log 。

说实话，Leader 选举的规则其实就一条：具备完备的 committed 的 log 数据即可。

那怎么才能选出具有完备数据的节点呢？

这就是 raft 协议里安全性的内容。投票发起者（ Candidate ）要告诉对方两个东西：

1. 任期编号；

2. 当前日志的最新位置；

其他节点（ Follower ）收到这两个信息会决定要投它一票，还是拒绝它？

划重点：做这个决定依赖于它的日志是不是比我新（全）。

那怎么判断谁更新（全）呢？

1. 先比 term ，谁更大谁就新;

2. 举个例子，Follower 节点保存的任期是 4，Candidate 发过来的是 3 ，这种就直接拒绝了；

3. 如果任期相同，那么就比较 index ，index 谁更大就新;

4. 举个例子，对面发过来的 index 是 7，我本地是的 8 ，那么就多说了，拒绝；

我们看一眼下图，我们知道 raft 的操作对象就是日志。在 raft 协议中，每个日志都有唯一的编号：index ，代表了它唯一的槽位。

题外话：这里可以类比上面 paxos 章节说的 instance 概念。其实每一个日志槽位和其他模块对象结合其他就是单独的 instance?，这一系列的日志对象就类似于 paxos 多实例 instance?确定的值。

每个 index 槽位代表的值一旦确定将永不更改，它们的确认不相互影响。

从完备的数据来看 committed 的位置在 index：7 这个位置。那么第一个节点、第三个节点、第五个节点都具备完备的数据，但是按照协议跑起来，只有第一个节点和第三个节点才有可能会成为 Leader 。因为它们两个节点有最新的数据（虽然是没有 commited 的），第五个节点找它们投票的时候，会被拒绝（它虽然有完备的数据，但是不够新）。

2?日志复制

日志复制有几个特点：

1. 日志传输为单向传输，Leader 到 Follower ；

2. Leader?永远不会改写或者删除自己的日志，永远只做 Append ；

3. 日志内容一切以 Leader 为主，哪怕是强制覆盖?；

和 paxos 类似，每个日志槽位的值一旦确定就无法更改，无论怎么投票，怎么运转，这个值不再变更。raft 就这样连续的确定值就能形成一个的日志序列，给到状态机使用。

这里类比 paxos 的 instance ，其实我们只需要保证每个槽位的投票和数据的独立就和 instance 的是一个效果。

以这个图为例，在不切主的情况下，数据从节点（1）向其他节点发送，补齐数据。

经过状态机应用，所有的节点最终系统状态一致：

• x = 4

• y = 7

思考一个问题：如果用户写失败了，系统提供了什么结果语义？

划重点：未定义。有可能写入了，有可能没写入。这种场景只能依赖于用户重试。标准的存储服务写失败语义。

还是以上图举例，就拿 index：8 这个位置的写入来说，用户从节点（1）写入数据 x=4。

场景一：这个时候只把日志成功复制到节点（3）就挂了。用户那边自然是失败的。节点（1）恢复后，还是又成为了 Leader ，由于 leader 永远不会删改日志，所以最终还是会把 index 的日志复制到其他节点，等复制完之后，满足 quroum 系统状态就变了就变成 x=4 了。

场景二：一条日志没写入，那么系统状态就还是 x=5 ；

所以，用户写入失败的场景，一定要依赖重试。不能对结果假定。这种假定在存储系统中通用。

关于 raft 日志复制，有个规则不得不提：Leader 永远不能 commit 非自己任期的日志。哪怕已经满足 quorum 。

为什么会有这个限定 ？

看一个 raft 论文中的简单的例子：

这是一个时间序列，从 a -> b -> c -> d -> e ：

1. a 时刻：Leader 为 S1（ 黑框的为 Leader ），它有着最新的日志 index:2 ，虽然最新的 index:2 并没有 committed（复制到多数），只复制到了 S2 ；

2. b 时刻：S1 挂了，S5 被选举为 Leader ，任期为 3 ，并且 Client 还递交了一个写入；

3. c 时刻：S5 挂了，S1 被重新选举为 Leader ，任期为 4，这个时候它复制日志，把 index:2 的日志复制给了 S1，S2，S3 ，这是满足了 quorum （但注意了，这个系统千万不能认为 commit 了，且往后看）。并且 Client 还递交了一个写入在 index:3 的位置；

4. d 时刻：S1 挂了，S5 被重新选举为 Leader（S2，S3，S4 都会投票），于是把 index:2 的日志强制覆盖到所有节点；

5. e 时刻：这个时刻是一种假设，假设说，S1 在 c 时刻的时候在挂掉之前把任期 4，index:3 的日志复制到多数节点，那结果又不一样了。这种场景系统可以认为 index:3 被 commit 了，index:2 则是被间接 commit 了；

看到了吗？

为什么在 c 时刻一直强调，不要认为

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

index:2 满足了 quorum 就认为是 committed 的日志，然后就去 apply 。因为你一旦这样做了，d 时刻的场景发生之后，index:2 的日志是被修改了。

这就导致 index:2 两次 commit 了不同的 log ！这就违背了一个槽位确定一个值，永不更改的承诺。

这绝对不行。

怎么办？

解决很简单，上面已经讲了，在 c 时刻这种场景，就算 index:2 被复制到多数，满足了 quorum 也不能认为是 committed （?没有 commit 自然就不能 apply?），Leader 只能 commit 自己任期的日志。前面的日志将被间接的递交。

再谈谈 e 时刻为什么把 index:3 的日志复制到多数之后，就可以认为 index:2 被 commit 了？

因为，这样做了之后，将不可能出现 d 时刻的场景。因为 S5 的任期只有 3 ！它将不可能成为 Leader 。

题外话：etcd 在每次选举出 Leader 的第一件事就是广播一条空白消息，原因就在这里。目的是为了间接 commit 掉前任的日志。

3?状态机

这部分其实是最简单的，状态机做的事情我们叫做 apply 。apply 的内容则是各个业务自行解释，举个例子，如下的日志，这是一个典型的 kv 系统的样子：

日志 apply 完之后，系统状态为：

x = 4

y = 7

划重点：日志里面的内容由业务自行解释，raft 只保证日志复制是完全一致的。