eraft 精解课程
我们团队致力于解读国外优秀的分布式存储相关开源课程，下面是课程体系图 我们始终坚信优秀的本科教学不应该是照本宣科以及应付考试，一门优秀的课程，应该具备让学生学会思考、动手实践、找到问题、反复试错、并解决问题的能力，同时应该尽量用最直白，最简单的语言传达关键的知识点。作为计算机工业界的工作者，我相信做课程和做技术一样，并不是越复杂越好，应该尽量的让设计出来的东西简单化。 关注我们的最新动态，欢迎关注 https://www.zhihu.com/people/liu-jie-84-52 接下来我们进入正题，如何实现一个分布式系统。MIT 分布式系统（三）Raft 论文解读 #
raft 概览
这一小节我们不深入 Raft 算法细节，而是带着大家概览一下 Raft 算法在一个实际的应用系统中的应用。
我们看到上图的系统，这是一个使用 Raft 算法实现的一个分布式 KV 系统。我们这个系统的设计目标是保证集群中所有节点状态一致，也就是每个节点中 KV 表（这里使用通俗的“表”的概念描述，实际这些数据会存储到一个存储引擎里面）里面的数据状态最终是一致的。
先不考虑故障的场景，我们来看看系统在正常的情况下是怎么运行的。
我们来分析一下 Put 操作经过这个系统的流程，首先客户端会将 Put 请求发送给当前 Raft 集群中的 Leader 节点对应的 K/V 应用层。这个操作会被 Leader 包装成一个操作给 Raft 层，Raft 对这个 Put 请求生成一条日志存储到自己的日志序列中，同时会把这的操作日志，复制给集群中的 Follower 节点，当集群中的半数以上节点都复制这个日志并返回响应之后，Leader 会提交这条日志，并应用这条日志，写入数据到 KV 表，并通知应用层。这个操作成功执行，这时候 K/V 层会响应客户端，同时 Leader 会把 Commit 信息在下一次复制请求带给 Follwer，Follower 也会应用这条日志，写入数据到 KV 表中，最终集群中所有节点的状态一致，整个系统的运行的时序下图所示。
这就是应用 Raft 实现一个能保证一致性状态系统的例子，乍一看，像是很简单。但是当你深入到算法细节里面的时候，这个系统就简单了。例如日志复制的时候会有很多约束条件来保证提交日志的一致性，以及故障的时候如何正确的选出下一个 leader？多次故障之后，日志状态一致性如何能够安全的保证？当然，这些细节也是我们后续分析的重点，我们会结合具体代码，尽量简单，让你系统的理解 raft 在处理这些问题时候的解决办法。
分布式系统中的脑裂
在我们介绍 Raft 算法之前我们先来看一下分布式系统的脑裂的问题，脑裂字面上是大脑裂开的意思，大脑是人体的控制中心，如果裂开了，那么整个系统就会出现紊乱。
对应到我们分布式系统里面，一般就是集群中的节点由于网络故障或者其他故障被划分成不同的分区，这时候系统中不同分区由于无法通信会出现状态不一致的情况，如果系统没有考虑处理这种情况。那么当网络再恢复的时候，系统也就没法再保证正确性了。
我们看到上图, 这就是分布式系统出现网络分区的情形。系统里面有 A-E 五个节点，由于故障， A,B 节点和 C,D,E 节点被划分到了各自的网络分区里面。绿色的圆形代表两个客户端，如果它们向不同的分区节点写入数据，那么系统能保证分区恢复后状态一致吗？Raft 算法解决了这个问题，在后续下一节讨论怎么解决的。
多数派协议
Raft 论文中提到的半数票决 (Majority Vote) ，也叫做多数派协议。是解决脑裂问题的关键，首先我们来解释一下半数票决是怎么做的，假设分布式系统中有 2*f + 1 个服务器，系统在做决策的时候需要系统中半数节点以上投票同意，也就是必须要 f + 1 个服务器都要活着，系统才能正常工作。那么这个系统最多可以接受 f 个服务器出现故障。
Raft 正是应用了半数票决来解决脑裂问题，假设我们有奇数个节点 (3,5...2n+1) 个节点组成的分布式系统，其中一旦出现网络分区，那么必然会有一个分区存在半数节点以上的，那么过半票决这个策略就能正常运行，这样系统就不会因此不可用，多数派票决正是解决脑裂问题的关键。
Raft 的日志结构
前面我们概览了整个 Raft 算法的流程，请求经过系统最开始就要写 Raft 算法层的日志了，那这个日志的结构是什么样的呢？接下来我们就来看看 Raft 日志的结构：
上图表示一个 raft 节点日志的结构，日志主要用来记录用户的操作，我们会对这些操作进行编号。图中每一条（1~8）日志都有独立的编号 log index。然后日志中还有任期号，如图中 1-3号日志为任期 1 的日志。这个任期号是用来表示这个日志的选举状态的，我们后面解释它的作用。 然后每个日志都有一个操作，这个操作是对状态机的操作，如 1 号日志我们的操作是把 x 设置成 3。
Raft 的状态转换
Raft 协议的工作模式是一个 Leader 和多个 Follower 节点的模式。在 Raft 协议中，每个节点都维护了一个状态机。该状态机有 3 中状态：Leader、Follower 和 Candidate。系统起来后的任意一个时间点，集群中的任何节点都处于这三个状态中的一个。
每个节点一启动就会进入 Follower 状态，然后当选举超时时间到达后，它会转换成 Candidate 状态，这时候就开始选举了，当它获得半数节点以上的选票之后，Candidate 状态的节点会转变成 Leader。或者当 Candidate 状态的节点发现了一个新的 leader 或者收到新任期的消息，它会变成 Follower, Leader 发现更高任期的消息也会变成 Follower, 系统正常运行中会一直在这三种状态之间转换。
Leader 选举
在说明 Leader 选举流程之前，我们先来解释下 Raft 协议中与选举相关的两个超时时间：选举超时（election timeout）时间和心跳超时 (heartbeat timeout) 时间。当 Follower 节点在选举超时时间之内没有收到来自 Leader 的心跳消息之后，就会切换成 Candidate 开始新一轮的选举。选举超时时间一般设置为 150ms ~ 300ms 的随机数，这里随机的目的是为了避免节点同时发起选票到时有相同票数的节点，从而选举失败重新选举的情况，增加这个时间的随机性有利于更快的选出 Leader。心跳超时时间则是指 Leader 向 Follower 节点发送的心跳消息间隔时间。
我们来梳理一下选举的流程
1.集群初始化，所有节点都会变成 Follower 状态。
2.经过一段时间后（选举超时时间到达）Follower 还没收到来自 Leader 的心跳消息，那么它会开始切换为 Candidate 开始发起选举。
3.变成 Candidate 之后节点的任期号也会增加，同时给自己投一票，然后并行的向集群中的其他节点发送请求投票 (RequestVoteRPC) 消息。
4.Candidate 状态的节点赢得了半数以上选票成为 Leader 节点，之后散播心跳给集群中其他节点，成功选举成 Leader
以上是大致的流程，但是有两个细节点需要注意：
在等待投票的过程中，Candidate 可能会收到来自另外一个节点成为了 Leader 之后发送的心跳消息，如果这个消息中 Leader 的任期号 （term）大于 Candidate 当前记录的任期号，Candidate 会认为这个 Leader 是合法的，它会装换为 Follower 节点。如果这个心跳消息的任期号小于 Candidate 当前的任期号，Candidate 将会拒绝这个消息，继续保持当前状态
另一种可能的结果是 Candidate 即没有赢得选举也没有输：也就是集群中多个 Follower 节点同时成为了 Candidate, 这种情况叫做选票分裂，没有任何 Candidate 节点获得大多数选票，当这种情况发生的时候，每个 Candidate 会重新设置一个随机的选举超时时间，然后继续选举，由于选举时间是随机的，下一轮选举很大概率会有一个节点获得多数选票会成为新的 Leader。
日志复制
我们假设集群中有 A，B，C 三个节点，其中节点 A 为 Leader，此时客户端发送了一个操作到集群：1.当收到客户端请求，节点 A 将会更新操作记录到本地的 Log 中。
2.节点 A 会向集群中其他节点发送 AppendEntries 消息，消息中记录了 Leader 节点最近收到的客户端提交请求的日志信息（还没有同步给 Follower 的部分）。
3.B，C 收到来自 A 的 AppendEntries 消息时，会将操作记录到本地的 Log 中，并返回通知 Leader 成功追加日志的消息。
4.当 A 收到半数节点以上成功追加日志响应消息时，会认为集群中有半数节点完成了日志同步操作，它会将日志提交的 committed 号更新。
5.Leader 向客户端返回响应，并且在下一次发送 AppendEntires 消息的时候把 commit 号通知给 Follower
6.Follower 收到消息之后，也会更新自己本地的 commit 号。
注意：上述流程是假设正常的情形下的流程，如果 Follower 宕机了或者运行很慢或者 Leader 发过来的消息某次丢失了, Leader 上记录了到某个 Follower 同步的日志进度，如果追加请求没成功，会不停的重新发送消息，直到所有 Follower 都存储了所有的日志条目。
日志合并和快照发送
Raft 论文在第 7 章介绍了日志压缩合并相关要点，按我们前面介绍的 Raft 复制相关内容，只要客户端有新的操作过来，就会写我们的日志文件，并且 Leader 同步给 Follower 之后，集群中所有节点的日志量都会随着操作的变多一直增长。eraft 中使用 leveldb 存储了 Raft 日志条目，如果日志量不断增长，那么我们引擎去访问日志的耗时就会不断增长，如果有节点挂了重新加入集群，我们需要给它追加大量的日志，这个操作会非常消耗 IO 资源，影响系统性能。
那么如何解决这个问题呢，首先我们再分析下日志结构：
我们看到这里的操作，都是对 x，y 的操作，每次日志提交完，我们都会应用日志到状态机中。这里我们会发现其实我们并没有必要存储每一个日志条目，我们只关心一致的状态，也就是已经提交的日志让状态机最终到达一种什么样的状态。那么在图中，我们就可以把 1,2,3,4 号日志的操作之后状态机记录下来，也就是 x <- 0, y = 9, 并且记录这个状态之后第一条日制的信息，然后 1～4 号日志可以被安全的删除了。
以上的整个操作在 Raft 里面被叫做快照 (snapshot)，Raft 会定期的打快照吧历史的状态记录下来。当集群中有某个节点挂了，并且日志完全无法找回之后，集群中 Leader 节点首先会发送快照给这个挂掉之后新加入的节点，并且用一个 InstallSnapshot 的 RPC 发送快照数据给它，对端安装快照数据之后，会继续同步增量的日志，这样新的节点能快速的恢复状态。
捐赠
整理这本书耗费了我们大量的时间和精力。如果你觉得有帮助，一瓶矿泉水的价格支持我们继续输出优质的分布式存储知识体系，2.99¥，感谢大家的支持。
遵循MIT协议开源。
感谢 「赫蹏」 提供如此优秀的中文排版系统