聊聊分布式算法 Raft
二哥的编程知识星球 （点击了解详情）正式上线了，来和 180 多名 小伙伴一起打怪升级吧！这是一个 Java 学习指南 + 编程实战的私密圈子，你可以向二哥提问、帮你制定学习计划、跟着二哥一起做实战项目，冲冲冲。
大名鼎鼎的 Paxos 算法可能不少人都听说过，几乎垄断了一致性算法领域，在 Raft 协议诞生之前，Paxos 几乎成了一致性协议的代名词。但是对于大多数人来说，Paxos 算法太难以理解了，而且难以实现。因此斯坦福大学的两位教授 Diego Ongaro 和 John Ousterhout 决定设计一种更容易理解的一致性算法，最终提出了 Raft 算法！
Raft 是一种更为简单方便易于理解的分布式算法，主要解决了分布式中的一致性问题。相比传统的 Paxos 算法，Raft 将大量的计算问题分解成为了一些简单的相对独立的子问题，并有着和 Multi-Paxos 同样的性能，下面我们通过动图，以后还原 Raft 内部原理。
Raft 基础
名词解释
Raft协议一共包含如下3类角色：
Leader（领袖）：领袖由群众投票选举得出，每次选举，只能选出一名领袖； Candidate（候选人）：当没有领袖时，某些群众可以成为候选人，然后去竞争领袖的位置； Follower（群众）：这个很好理解，就不解释了。
然后在进行选举过程中，还有几个重要的概念：
Leader Election（领导人选举）：简称选举，就是从候选人中选出领袖； Term（任期）：它其实是个单独递增的连续数字，每一次任期就会重新发起一次领导人选举； Election Timeout（选举超时）：就是一个超时时间，当群众超时未收到领袖的心跳时，会重新进行选举。
角色转换
这幅图是领袖、候选人和群众的角色切换图，我先简单总结一下：
群众 -> 候选人：当开始选举，或者“选举超时”时 候选人 -> 候选人：当“选举超时”，或者开始新的“任期” 候选人 -> 领袖：获取大多数投票时 候选人 -> 群众：其它节点成为领袖，或者开始新的“任期” 领袖 -> 群众：发现自己的任期ID比其它节点分任期ID小时，会自动放弃领袖位置 备注：后面会针对每一种情况，详细进行讲解。
选举
情况 1：领导人选举
为了便于后续的讲解，我画了一副简图，“选举定时器”其实就是每个节点的“超时时间”。
成为候选人：每个节点都有自己的“超时时间”，因为是随机的，区间值为150~300ms，所以出现相同随机时间的概率比较小，因为节点B最先超时，这时它就成为候选人。
选举领导人：候选人B开始发起投票，群众A和C返回投票，当候选人B获取大部分选票后，选举成功，候选人B成为领袖。
心跳探测：为了时刻宣誓自己的领导人地位，领袖B需要时刻向群众发起心跳，当群众A和C收到领袖B的心跳后，群众A和C的“超时时间”会重置为0，然后重新计数，依次反复。
这里需要说明一下，领袖广播心跳的周期必须要短于“选举定时器”的超时时间，否则群众会频繁成为候选者，也就会出现频繁发生选举，切换Leader的情况。
情况 2：领袖挂掉情况
当领袖B挂掉，群众A和C会的“选举定时器”会一直运行，当群众A先超时时，会成为候选人，然后后续流程和“领导人选举”流程一样，即通知投票 -> 接收投票 -> 成为领袖 -> 心跳探测。
情况 3：出现多个候选者情况
当出现多个候选者A和D时，两个候选者会同时发起投票，如果票数不同，最先得到大部分投票的节点会成为领袖；如果获取的票数相同，会重新发起新一轮的投票。
当C成为新的候选者，此时的任期Term为5，发起新一轮的投票，其它节点发起投票后，会更新自己的任期值，最后选择新的领袖为C节点。
日志复制
复制状态机
复制状态机的基本思想是一个分布式的状态机，系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在操作日志中。如下图所示，服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中，它与其他服务器上的一致性模块进行通信，以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。
数据同步流程
数据同步流程，借鉴了“复制状态机”的思想，都是先“提交”，再“应用”。当Client发起数据更新请求，请求会先到领袖节点C，节点C会更新日志数据，然后通知群众节点也更新日志，当群众节点更新日志成功后，会返回成功通知给领袖C，至此完成了“提交”操作；当领袖C收到通知后，会更新本地数据，并通知群众也更新本地数据，同时会返回成功通知给Client，至此完成了“应用”操作，如果后续Client又有新的数据更新操作，会重复上述流程。
日志复制原理
每一个日志条目一般包括三个属性：整数索引Log Index、任期号Term和指令Commond。每个条目所包含的“整数索引”即该条目在日志文件中的槽位，“任期号”对应到图中就是每个方块中的数字，用于检测在不同服务器上日志的不一致问题，指令即用于被状态机执行的外部命令，图中就是带箭头的数字。
领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的呢？一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的。例如，图中的9号条目在其中4节点（一共7个节点）上具有复制，所以9号条目是可被提交的；但条目10只在其中3个节点上有复制，因此10号条目不是可被提交的。
一般情况下，Leader和Follower的日志都是保存一致的，如果Leader节点在故障之前没有向其它节点完全复制日志文件之前的所有条目，会导致日志不一致问题。在Raft算法中，Leader会强制Follower和自己的日志保存一致，因此Follower上与Leader的冲突日志会被领导者的日志强制覆写。为了实现上述逻辑，就需要知道Follower上与Leader日志不一致的位置，那么Leader是如何精准找到每个Follower日志不一致的那个槽位呢？
Leader为每一个Follower维护了一个nextlndex，它表示领导人将要发送给该追随者的下一条日志条目的索引，当一个Leader赢得选举时，它会假设每个Follower上的日志都与自己的保持－致，于是先将 nextlndex初始化为它最新的日志条目索引数+1，在上图中，由于Leader最新的日志条目index是10 ，所以nextlndex的初始值是11。当Leader向Follower发送AppendEntries RPC时，它携带了（item_id，nextIndex - 1）二元组信息，item_id即为nextIndex - 1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后，会进行一致性检查，即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就像Leader返回AppendEntries RPC失败，然后领导人会将nextIndex递减，然后进行重试，直到成功为止。之后的逻辑就比较简单，Follower将nextIndex之前的日志全部保留，之后的全部删除，然后将Leader的nextIndex之后的日志全部同步过来。
上面只是讲述了方法，下面举个例子，加深一下理解，还是以上面的图为例。Leader的nextlndex为11，向b发送AppendEntries RPC(6,10)，发现b没有，继续发送(6,9)(6,8) (5,7) (5,6) (4,5)，最后发送(4,4)才找到，所以对于b，nextlndex=4之后的日志全部删除，然后将Leader的nextlndex=4的日志全部追加过来。
脑裂情况
当网络问题导致脑裂，出现双Leader情况时，每个网络可以理解为一个独立的网络，因为原先的Leader独自在一个区，所以向他提交的数据不可能被复制到大多数节点上，所以数据永远都不会提交，这个可以在第4幅图中提现出来（SET 3没有提交）。
当网络恢复之后，旧的Leader发现集群中的新Leader的Term比自己大，则自动降级为Follower，并从新Leader处同步数据达成集群数据一致，同步数据的方式可以详见“日志原理”。
没有什么使我停留——除了目的，纵然岸旁有玫瑰、有绿荫、有宁静的港湾，我是不系之舟。
推荐阅读：
