深入浅出一文搞懂分布式一致性算法新贵Raft协议

　　前言
　　在分布式的世界里，要说最核心最复杂的功能，一致性地实现无出其右，之前的paxos算法堪称经典，被认为是同类算法中效果最好的，基本上成为分布式一致性的代名词，但是paxos算法也是出了名的难理解，而且相当不好实现。本人也花了很多时间、看了很多材料也没有真正理解。所以基于paxos的思想进行的一致性算法的简化和实现就成为了现实的需求，在此背景下，本文的主角Raft就出现了。
　　Raft算法的头号目标就是容易理解（UnderStandable），这从论文中就可以看出来。当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不输于Paxos的。建议大家拜读下作者的论文 Raft论文，下面将详细说明raft的思想以及实现的过程 正文
　　raft为了实现容易理解的目标，在paxos的基础上进行的状态简化以及问题拆分，将之前复杂的逻辑拆成若干个子问题，基本上可以总结成下面几个方面： leader election：选取主节点 log replication：日志备份，数据同步 safety：为了实现上述两点而产生的一些约束条件和保障条件 leader electionrole
　　首先先说明下Raft算法中节点的角色，分为以下三种： leader：由所有节点选举，在candidate中产生，负责整个集群的状态以及元数据管理，当发现更大的term时，转化为follower candidate：由follower在集群选举时转化而成，选举时得到多数选票，则转化为leader，若发现主节点或者更大的term则转化为follower follower：集群初始化时所有节点的角色都是follower，若未发现leader心跳，则发起leader选举，并将角色转化为candidate；leader以及candidate在某些条件下也会转化成follower
　　给出状态机，协助大家理解：
　　role
　　上面在讲解role的时候好几次说到了一个名词term，这是raft算法中的一个核心概念，很多的机制都需要依赖term。term通俗来讲就是任期，即一个leader正常工作的时间段，如果因为某些原因当前的leader不再是leader时，则该term结束，重新进行选举，开始新的任期，是不是和现实生活中的选举很像？
　　另外term在raft算法中也起到了逻辑时钟的作用，在raft的实现中起到了重要的作用，此处用一句话先来概括：即term大的优先级高，leader必须是拥有更大的term。用白话理解：就是当前总统和前总统的关系，总统只能有一个就是当期总统，前总统在当前总统面前就变成选民了。在Raft中，term是个整数型的值，term变化即将term的值加1 leader election process
　　下面就来说说leader选举的详细过程，从上面的状态机可以看出，集群初始化时，大家都是follower，当未发现leader心跳并超时后，则follower变成candidate，并发起leader election。每个candidate的动作如下： 给自己投一票 向其他节点发起RequestVote RPC来进行拉票 等待其他节点的响应
　　在此过程中会出现三种情况： 该candidate收到了多数（majority）的选票当选了leader，并发送leader心跳告知其他节点，其他节点全部变成follower，集群选主成功 该candidate收到了其他节点发来的leader心跳，说明主节点已经选举成功，该candidate变成follower，集群选主成功 一段时间内（election timeout），该candidate未收到超过半数的选票，也未收到leader心跳，则说明该轮选主失败，重复进行leader election，直到选主成功
　　上述情况的产生需要满足下面几个约束： 在每个任期中每个人只能投出一票：注意是每个任期，任期变了（准确的说法是任期增加了）就可以重新投票 投票的规则：candidate肯定投给自己，follower是先到先得 当选leader的条件是得到多数（N/2+1）选票：此处的多数选票是为了避免脑裂而出现多leader的情况而进行的约束，保证了整个集群中leader的唯一性 leader的消息是最新的（其实就是term最大，index也是最大的，后面的log replication模块进行详细分析）
　　上面的前两种情况比较容易理解，我们重点来说说第三中情况，用一个比较形象的例子来说明选举过程：
　　有五个小伙伴要选取一个组长，选举过程如下：
　　注：F,C,L分别对应的是follower，candidate和leader角色，在本例中就是组员，候选人和组长；名字是用来区分节点的标识；而括号中的数字则代表着term的值
　　初始状态大家都是组员，等待组长联系自己 等待一段时间后（leader heartbeat timeout），昌坦，继东和呈祥发现没有组长或者组长掉线了，这三个人就变成了候选人，然后发起了组长选举的流程 选举开始后，三个候选人都将自己的任期加1变成了2，然后投了自己一票，而组员晓通选了昌坦，组员溪泽选了呈祥，三个候选人的票数比是2：1：2，未能达到法定的半数以上的多数票，未能选出组长 漫长的等待后（election timeout），昌坦发现自己没有获得多数选票，也没有收到其他候选人当选组长的消息（leader heartbeat），意识到了此次选举失败，然后将自己的任期加1变成3，再次发起选举，组员晓通和溪泽发现该任期中未投票 ，先到先得，直接投给了昌坦，而候选人继东和呈祥发现昌坦的任期比自己大，则放弃候选人的角色变成了组员并投票给昌坦（此处从候选人变成组员也可能是收到了昌坦当选组长的消息后转变的，因为组长的当选并不需要全票，只要达到多数选票即可） 昌坦全票当选组长，并向其他组员通报了自己成为组长的消息，后续所有的组内管理以及消息同步都通过组长昌坦向其他组员传达
　　整个leader election流程就是这样，是不是很好理解，基本上符合现实生活中的理解。但是上述的流程可能有一个问题，分为以下两种情况： 如果在第三阶段三个候选人同时发现选举未成功，同时发起二次选举，而恰好昌坦和晓通的关系很好，呈祥和溪泽的关系很好（关系好可以理解为网络近，优先到达，优先获得投票），则可能出现多次2：1：2，无法达到多数（majority）的情况 如果当前的组员不是5个人，而是4个人或者6个人，而候选人是2个，则会出现2：2或者3：3的情况，无法达到多数（majority）的情况
　　上述的两种情况会影响到leader election的成功率和效率，在设计中应该被规避，面对这两种情况，Raft给出了自己的解决方案： 节点数尽量是奇数个，尽量保证majority的产生 每个candidate的election timeout时间在某一个时间段内随机，如150ms-300ms,这样能最大程度上避免同时再次发起选举的概率，某个candidate可以率先发现election timeout然后增加term并重新发起选举，大概率能获得多数选票而当选，另外每一次选举每个candidate都会刷新election timeout，来保证majority的产生 leader election
　　当系统有了leader后，系统就进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
　　下图就是请求写入处理的相关流程：
　　客户端向leader提交写入请求 leader接收到客户端请求后封装RPC并行将修改发送到follower follower在接收到leader发送的RPC后，回复leader已经收到该请求 在leader接收到多数（majority，含leader）follower的回复后，回复客户端接收成功，将变更状态设置为commited，然后将变更写入到状态机，此时写入实际上已经生效，无法回滚 leader与follower通信，协助follower完成变更的提交，当变更提交完毕后，follower会将变更写入到状态机，此时变更才真正的影响到节点，此时的状态可以理解为applied。此过程中，可能会出现各种问题，比如说网络连接超时，命令执行不成功等问题，leader会持续和follower进行通信，保证follower最终完成所有的操作，与leader达成最终一致性。这种最终一致性是对内的，对外部的client的透明的，外部的client只会看到leader上状态的强一致性。这种强一致性和最终一致性的配合使用，不仅降低了一致性实现的各种成本，还保证了系统的健壮性，能保证在各种异常情况下的恢复与状态同步。
　　上述流程中，有点类似于两阶段提交（2PC），这种提交方式的好处就是能简化分布式事务的复杂性，在不直接使用分布式锁的前提下，能最大程度保证分布式事务的实现。但是这里和标准的2PC还是有差别的，差别就是这里leader只需要多数（majority）的follower答复即可，那么在这种情况下，raft是怎么保证一致性以及数据的完整性，尤其在集群主节点发生故障的时候呢？此处先留下这个问题，后续在safety模块进行解答
　　最后看下log长什么样子吧：
　　log由三部分组成： 序号：代表着命令的执行顺序，leader将命令按顺序发给follower，follower按顺序执行命令，保证数据的一致性 term值：将命令按term进行划分，每个命令都属于一个term 操作命令：真正执行和影响节点状态的命令
　　log为了配合raft实现leader选举以及状态同步，需要具备某些特性 ，满足相关的约束： 回到上文的问题，leader选举的时候要保证leader上的log是最新的，那最新的概念是什么？这里解答下：log最新的概念就是term是最大的且index也是最大的，如图中的leader，term是4，index是7，都是最大的 从初始状态为空开始，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。 log是append only的file，对于已经committed的命令，log只会新增，不会修改和删除，这也带来了另外一个特性，就是如果两个不同节点在同一位置的日志相同，那么在此位置之前的所有的值都相同 只有leader的发送的log entry被多数（majority）的节点（包含leader）接收并响应，才会被标识为committed safety
　　上面大部分说的都是正常情况下raft是怎么工作和运行的，但是一个分布式不仅需要在正常情况下能稳定高效的运行，也需要在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。raft也是如此，上面两个章节已经说明了为了达到safety目标raft所采取的一些策略和约束，下面就来以几个典型场景来说明下raft是怎样容错的。 follower crash
　　follower crash处理起来相对简单，只要重新上线加入集群后 ，发现了已经存在的leader，直接加入集群并且接收来自leader的消息，然后在leader的指导下完成数据和状态的同步，在此过程中，leader与follower通信使用的是AppendEntries RPC，借用官方的结构图：
　　另外，每个节点上的日志都是通过状态机（State Machine）进行管理的，节点上applied的command会提交到状态机进行保存，用于后续节点（leader-follower）之间进行数据和状态同步，下面是状态机中状态相关的结构图：
　　从上图可以看出对于每个follower，leader保持2个属性，一个就是nextIndex即leader要发给该follower的下一个entry的index，另一个就是matchIndex即follower发给leader的确认index。
　　实现过程如下：
　　leader当选成功后，会进行部分属性的初始化： nextIndex=leader的log的最大index+1 matchIndex=0
　　然后开始准备AppendEntries RPC请求的参数： prevLogIndex=nextIndex-1 prevLogTerm=从log中得到prevLogIndex对应的term
　　初始化entries数组： 初始化以及成功当选的第一次心跳的时候是空 后续的值是从本地log中取prevLogIndex+1到最后的所有log entry
　　最后是leaderCommit赋值： leaderCommit=leader上的commit indexentry
　　至此，所有参数准备完毕，发送RPC请求到所有的follower,follower再接收到这样的请求之后，处理如下： 重置HeartbeatTimeout 检查传过来的请求term和当前follower的term，如果当前term大于master的term，则返回false 检查prevLogIndex和prevLogTerm和当前follower的对应index的log是否一致。检查的方法就是follower在prevLogIndex这里是不是有entry，如果有的话，term的值和prevLogTerm是否一致。这里可能就是不一致的，因为初始prevLogIndex和prevLogTerm是leader上log的lastLog，因为网络等原因，可能还未同步到这个index，如果不一致的话返回false，同时将该follower上log的lastIndex传送给leader leader接收到上述false之后，会记录该follower的上述lastIndex nextIndex=follower传回来的index+1 matchIndex=follower传回来的index 然后leader会从新按照上述规则，发送新的prevLogIndex、prevLogTerm、和entries数组 nextIndex=follower传回来的index+1 matchIndex=follower传回来的index prevLogIndex=follower传回来的index prevLogTerm=从log中得到上述prevLogIndex对应的term entry[]=从本地log中取prevLogIndex+1到最后的所有log entry leaderCommit=leader上的commit index follower检查prevLogIndex和prevLogTerm和对应index的log是否一致（目前一致了） 然后follower就开始将entries中的数据全部覆盖到本地对应的index上，如果没有则算是添加如果有则算是更新，也就是说和leader的保持一致 最后follower将最后复制的index发给leader,同时返回ok，leader会像上述一样来更新follower的macthIndex leader crash
　　leader crash相对来说比较复杂，需要针对几个固定场景进行具体分析，详细参考这篇文章： Leader节点的一致性保障 leader与follower同步数据
　　在集群出现异常重新选取leader后都需要面临数据同步的问题，下面这张图列举了集中场景：
　　上面列举了6钟follower可能存在的状态，前两种follower的数据比leader少，中间两种follower数据比leader多，最后两种leader和follower数据有多有少。这里需要注意一下：
　　图中的虚线框代表着uncommitted的log entry；
　　另外，此时leader的term是8（如果这7个节点是一个集群的话），后续分析中这一点很重要。
　　具体分析下上述几种场景中follower状态产生的原因： 第一种情况比较常见，follower和leader在同一term，就少一个index，这是client刚将数据写入到leader，leader正常将该数据同步到follower即可 第二种情况是follower在term 4就crash或者网络中断了，在term 6重新恢复，此时leader只要通过AppendEntries RPC正常同步即可。 第三种情况产生的原因是该follower在term 6的时候是leader，在写入第三个值的时候，还没来得及同步给follower，自己就crash或者网络中断了，所以最后一个log entry处于uncommitted的状态 第四种情况产生的原因是该follower在term 7的时候是leader，刚当选leader并通知其他follower后就网络中断了，自己处于一个局域网中，在client端写入两个值后，无法同步给follower，所以最后两个log entry处于uncommitted的状态 第五种情况产生的原因是该follower在term 4的时候是leader，刚当选leader并通知其他follower后，写入了两个值同步给follower并commit后就网络中断了，自己处于一个局域网中，在client端继续写入两个值后，无法同步给follower，所以最后两个log entry处于uncommitted的状态 第六种情况产生的原因是该follower在term 2的时候是leader，刚当选leader并通知其他follower后就网络中断了，自己处于一个局域网中，在client端写入三个值后，无法同步给follower，所以term 2的三个log entry处于uncommitted的状态；此时网络突然恢复，进入了term 3，在该term中，该follower参加leader选举又被选为leader，刚当选leader并通知其他follower后就网络中断了，自己处于一个局域网中，在client端写入三个值后，无法同步给follower，所以term 3的三个log entry处于uncommitted的状态
　　上面的几种情况虽然不太具备现实意义，但是还是对于我们理解整个raft的各种机制有很大的帮助，建议大家好好梳理下，肯定会有收获的。
　　针对上面的所有情况，处理方式就就是，leader选举时所有的uncommitted的log entry都会回滚（所以图中所有的uncommitted的log entry其实在term 8 leader选举后就不存在了，此处画出来仅仅是为了方便大家理解整个数据和状态的演变过程），然后当出现了leader与follower不一致的情况，leader强制follower复制自己的log，复制的过程参加follower crash这一章节 raft算法如何保证leader的数据永远是最新的且不会丢数据
　　这个问题其实是由上面的几个majority以及几个约束共同来完成的： majoritycommit majority：一条消息只有变成committed状态才被认为已经提交成功，而committed状态的前提是该消息已经同步到了majority的节点 vote majority：某个candidate当选leader的条件就是该candidate获得到了majori节点的选票 约束leader当选的条件是log是最新的
　　综上，commit majority代表着最新数据的持有；而vote majority代表着最后的leader会从这里面产生（candidate肯定会投自己的票，所以也在vote majority之中），而这两个majority肯定会有1到(N/2+1)个节点是重复的，也就是这些节点既有最新的数据，也有机会成为leader，再看那个约束条件，这个约束条件将vote majority中不具有最新数据的那些节点排除，那么最后的leader节点一定会在两个majority重复的节点中产生，而这些节点持有最新的数据，保证了leader的数据永远是最新的且不会丢数据。
　　raft与其他协议（Viewstamped Replication、mongodb）不同，raft始终保证leader包含最新的已提交的日志，因此leader不会从follower catchup日志，这也大大简化了系统的复杂度。 总结
　　raft将一致性问题分解成两个相对独立的问题，leader election，log replication。流程是先选举出leader，然后leader负责复制、提交log（log中包含command），为了在任何异常情况下系统不出错，即满足safety属性，对leader election，log replication两个子问题有诸多约束，在满足功能和性能的基础上，尽量简化模型以及状态，提高了整个算法的易理解性和易实现性，堪称经典且实用的算法。
　　想想 Paxos 算法是 Leslie Lamport 在 1990 年就公开发表在了自己的网站上，想想我们是什么时候才听说的？什么时候才有一个可用的实现？而 Raft 算法是 2013 年发表的，现在可以看到有许多不同语言开源的实现库了。而且很多raft-like算法在raft的基础上进行了定制化扩展，用以满足各种系统需求（如elasticsearch 7中的集群协调子系统中定制化raft的实现），这就是易理解性和易实现性的重要性。