学点 Raft
Raft 这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"（“可靠、可复制、可冗余、可容错”）的首字母缩写。
Raft 是一种用于解决分布式一致性/可用性问题的简洁协议(并不是某个软件)。相比于 Paxos 协议，Raft 协议更加容易理和实现。
它解决了其它分布式协议所具有的一些问题，比如说——过于复杂，脑裂，单点故障，不一致等等。
Raft 本身的目标就是为了解决集群内有限状态机的同步问题，而 Raft 本身工作的状态也很容易被抽象成一个有限状态机——单个机器的状态可以是领袖、追随者，或是候选人之间的任意一种，且可能会发生转换。
每个状态自身都会进行无限循环，根据接收的消息来决定是执行操作还是转换状态。
不出意外的话，候选人状态应该是持续时间最短的状态，但代码实现却是相对最复杂的。
如何解决脑裂问题–过半票决
假设我们现在有 2n+1 台服务器，但是这 2n+1 台服务器有些连在了不同的交换机上，内网通过交换机之间的网线传输数据，对外服务则通过路由连接到互联网。
这个时候如果出现了什么问题，比如说交换机之间的网线断了或是被人踢掉了，那么就会出现脑裂问题。
Raft 协议并没有通过引入第三方的监控机制来解决问题，而是通过选举和简单的计数方式来决定分裂后的哪部分节点可以继续为用户提供服务。
简单来说，2n+1 台服务器在发生脑裂后，分裂出的两个集群中，必定有一个集群中机器的数量是大于等于 n+1 的，而另一个集群中机器的数量一定是小于等于 n 的。
根据可用性的原则，我们自然会选择机器数量大于等于 n+1 的集群来继续为用户提供服务，而小于等于 n 的集群则会停止服务，以避免出现数据不一致。
要实现这样的功能，只要保证 Leader 在无法收到过半的 follower 的确认时，不会提交 commit，只是阻塞并发送心跳包即可。
从故障中恢复——选举新的 leader
网络发生故障分区的时候，如果原先的 leader 主机恰好分在了具有较少主机的集群中，那么具有较多主机的集群就会短暂的停止服务，并开始选举出新的 leader。
而旧的 leader 发现自己所在的集群中主机的数量小于 n 时，也会停止接受请求。当然这个停止请求的部分不用我们去单独再实现，因为如果 leader 在提交 commit 时无法得到 n+1 个 follower 确认，leader 就会阻塞并不再响应请求。
选举 leader 的部分应该算是 raft 协议中最复杂的部分了。
在群 follower 无 leader 的情况下，我们对每个 follower 设置了一个随机的超时时间。在一段时间之后，总会有一些 follower 的超时时间到了。那么这些 follower 就会转变为 candidate 并开始选举拉票。
拉票时，candidate 会向所有的 follower 发送投票请求，并且附上自己的任期号、自己的最后一条 log 的索引。
投票的规则如下：
- follower 在收到投票请求后，如果请求中的任期号大于自己的任期号，并且该任期这个 follower 还没有投过票，则会将自己的任期号更新为请求中的任期号，并将自己的选票投给请求中的 candidate
- follower 在收到投票请求后，如果请求中的任期号等于自己的任期号，且 log 记录的长度大于等于请求中的 log 记录的长度，则会将自己的投票投给请求中的 candidate
- follower 在收到投票请求后，如果请求中的任期号小于自己的任期号，则会拒绝投票
- 每个 candidate 一定会把票投给自己
- 如果 candidate 收到了来自其它 candidate 的投票请求，且自己的任期号不大于对方的任期号，则会放弃竞选并投票给对方
- 如果 candidate 收到了超过半数的投票，则会成为新的 leader
另外，我们还需要一个超时期限来判定集群中的机器是否发生了故障，而这个期限我们通常可以通过两个时间节点来均衡：广播延迟和平均故障时间。
一般来说，在本地网络的情况下，广播时间只需要不到 10ms，而平均故障时间通常是以年/月为单位的。
我们需要保证 广播延迟 << 超时期限 << 平均故障间隔 ，同时考虑到我们希望系统从故障中恢复的时间尽可能短，因此我们把超时期限设置在 20ms-500ms 都算是可以接受的。
一致性的解决方案——log 复制与两步提交
raft 用来解决一致性问题的方式很简单，就是通过 leader 来统一管理所有的状态变更，将变更转换为 log，然后将 log 至少同步给过半的 follower 后，才认为这个变更已被成功可以进行提交。
确认可以进行提交之后，leader 会向所有的 follower 发送 commit 命令，follower 收到 commit 命令后，才会将 log 持久化。确认持久化成功后，leader 才会将 log 添加到自己的 log 栈中，并且向用户返回提交成功
当然这只是保证提交可以正常储存到集群中的机器上。如果之前断开的机器恢复了连接，或者是维护人员加入了全新的机器，那么这些机器上的数据就会和集群中的其它机器不一致。这个时候我们就需要复制日志来保证新机器的数据可以被同步。
简单来说，新机器在加入集群的时候会主动联系当前的 leader，然后两者会开始匹配自身的 log，直到发现了两者最晚的相同 log。
查找的方式用二分查找即可，因为 log 是按照时间顺序排列的，所以可以通过二分查找来以$O(log\ n)$的时间复杂度找到最晚的相同 log。考虑到我们是做简单实现，直接用枚举来做查找也没啥问题。
如何保证集群中 log 的唯一性呢？我们可以通过让 leader 在发送 log 给 follower 时给 log 加上自增 id 来保证 log 间可以被比较。如果一个 follower 转变成了 leader，那么它的 log 的 id 就会从其目前所持有的 log 的最大 id 开始自增。
整体的框架实现
一个简单的 raft 架构图
这个图片基本是我自己在实现 raft 算法时所设计的程序结构。
程序在开始时首先读取配置并初始化状态机中的一些必要变量，之后默认作为 Follower 加入集群并向配置文件中的每个对端发送握手信息。
发送握手后，程序就进入了监听端口的无限循环，等待来自其它机器的消息。
以下是论文中关于程序数据结构的描述。实际上 raft 算法所包含的数据结构并不复杂。只需要实现两种 RPC 接口就可以实现 raft 算法中的数据交换。
参考链接：