大名鼎鼎的 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_idnextIndex - 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)才找到所以对于bnextlndex4之后的日志全部删除然后将Leader的nextlndex4的日志全部追加过来。脑裂情况当网络问题导致脑裂出现双Leader情况时每个网络可以理解为一个独立的网络因为原先的Leader独自在一个区所以向他提交的数据不可能被复制到大多数节点上所以数据永远都不会提交这个可以在第4幅图中提现出来SET 3没有提交。当网络恢复之后旧的Leader发现集群中的新Leader的Term比自己大则自动降级为Follower并从新Leader处同步数据达成集群数据一致同步数据的方式可以详见“日志原理”。