分布式系统——Raft的分析与实现
这是一篇来自研究生一年级的课程—— 《分布式系统》 的作业记录博客。
其主要是实现分布式系统中一致性的算法 Raft 。
论文链接如下：Raft算法英文原文地址
而中文翻译地址如下：中文翻译版本
首先我们大致通过一个动画过程来了解一下Raft。链接如下：Raft动画演示
1 分布式系统的一致性问题
我们假设有一个客户端 X 和一个服务器 Y ，然后 X 发送一个值给 Y，那么唯一的一个服务器就有了这个值。
但我们试想一下现实世界中，服务器的数量不可能只有一个，所以假设有 n 个服务器 Y[n] ，如何将客户端 X 发的值
让多个服务器都能一致起来，这就是需要探究的一个问题。
而在论文中提到，一致性算法是从复制状态机的背景下提出的。复制状态机图示如下：
复制状态机是基于复制日志来实现的，从上图可知，每一个服务器都存储一个包含一系列指令的日志。
客户端向一致性模块发送指令，一致性模块接收到指令然后增加到自己的日志中，它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求。
一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理它们，然后输出结果被返回给客户端。
2 Raft 一致性算法
针对上面提到的分布式系统中一致性问题，Raft 便是一种可以实现一致性的协议（或者算法）。具体的讲，它就是用来管理上图复制状态机中复制日志的算法。
Raft通过选举一个leader，并赋予给它完全的管理复制日志权限来实现一致性。
leader从client接收日志条目，然后将日志条目复制到其他服务器中，并当可以保证安全性时告知其他的服务器需要应用日志条目到它们的状态机中。
这样我们就将 Raft 算法分成三部分：
- 领导选举
- 日志复制
- 安全性
具体内容下面分别来讲述。
2.1 Raft 基础知识
我们首先要了解一下Raft的一些基础知识。
首先 Raft 中的服务器一共有 3 个状态：
- Follower
- Candidate
- Leader
三个状态相互转化关系图如下：
也就是说，每个服务器起始的状态都是 Follower，然后开始选举之后，其中一个服务器称为 Candidate， 然后接受投票，若获得大部分的投票则称为 Leader，当然从 Candidate 和 Leader 状态都可以转化成 Follower状态。
而每一个时期，系统只能存在一个 Leader，如果大于1个，则错误，而其他的节点都是 Follower。Follower 都是被动的：他们不会发送任何请求，只是简单的响应来自 Leader 或者 Candidate 的请求。
2.2 Leader Election
领导选举是一种非常关键的步骤，也是实现Raft的第一个步骤。
它的过程如下：
首先系统中存在多个服务器，每个服务器都维护着自己的一个 election timeout，它是随机设定的（一般是150~300ms）。
如下图所示，一共有 3 个服务器，每个服务器有一个 “进度条” 代表其 election timeout 。
一旦其中一个节点的进度条走完，便成为 Candidate。