1.简介<br />
了解分布式的同学都知道，在分布式理论中有个CAP定理，CAP代表分布式系统的三个要素：一致性（C）、可用性（A）、分区容错性（P），本文要介绍的Raft算法，它就是实现日志复制一致性的算法；之前用ETCD做服务注册、发现时，有接触过一点Raft，但是，了解的不够深入，正好前段时间休了个长假，就研读论文、结合网上资料，按照自己的理解、重新整理如下，如有不当或者疑问之处，还请各位大佬留言、多多指点。<br />
1.1由来<br />
Paxos是1990年由Lamport提出，但一直以来，该算法被抱怨是难以理解、晦涩，针对Paxos算法晦涩难懂、工程实现复杂的问题，斯坦福大学的两位教授Diego Ongaro和John Ousterhout决定设计一种更容易理解的一致性算法，后来在发表的"In search of an Understandable Consensus Algorithm"论文中提出了Raft算法（论文地址是： https://raft.github.io/raft.pdf ），相比之下，Raft更容易理解、易于工程实现。<br />
1.2结构<br />
论文共有十二章节，每章节的内容是：<br />
1）一、三、四章节主要是论文简介、分析Paxos存在问题以及Raft设计理念，以understandability为目标<br />
2）二章节介绍了复制状态机模型，复制状态机对外整体的一致性基于日志复制的一致实现<br />
3）五章节是实现核心，围绕算法核心——"leader选举"、"log复制"、"safety安全性"三部分介绍<br />
4）六、七、八章节分别介绍了集群配置变更、日志压缩以及与客户端交互<br />
5）剩余的章节就是算法效果评估、相关工作以及结论、感谢<br />
本文并非是对论文的逐章翻译，是按照自己的理解重新编排，主要是针对第五章核心部分，首先是结构、术语介绍，然后是leader选举、log复制等核心流程介绍，再结合安全性对核心流程完善。<br />
2.实现<br />
Raft算法主要是围绕两点实现——leader选举和log复制，下面重点介绍。<br />
2.1概念<br />
2.1.1术语<br />
2.1.1.1服务角色<br />
集群中，服务角色有三种：<br />
1）leader 对外负责与客户端交互，对内负责日志复制、心跳通知<br />
2）candidate 发起选举，竞选leader，确保集群可用性<br />
3）follower 接收leader日志，检测leader心跳，选举投票<br />
2.1.1.2RPC<br />
服务间通信都是通过RPC实现的，RPC也有三种类型：<br />
1）RequestVote Rpc 请求投票RPC，由candidate节点发出 <br />
2）AppendEntry Rpc 日志复制、心跳检测RPC，由leader节点发出<br />
3）Snapshot Rpc 基于快照的日志同步，由leader节点发出<br />
其中，RequestVote Rpc和AppendEntry Rpc是常用RPC，Snapshot Rpc感兴趣的可以了解；Raft算法中，RPC都是幂等、无伤害的，如果RPC响应异常，会继续请求；如果RPC已经执行过，则会忽略。<br />
2.1.1.3其他<br />
Raft算法实现中，还用到其他概念：<br />
1）term 任期，算法的重要组成部分，在leader选举和log复制中都有用到<br />
2）committed 日志条目的状态，这表示已提交状态<br />
3）nextIndex 同步索引，leader要发给follower的下个日志条目的索引<br />
4）election timeout 选举超时时间，是发起新一轮选举的超时时间<br />
对于committed补充几点，后面也会提到：<br />
1）如果一个日志条目被leader复制到绝大多数服务上，则认为该日志条目是 committed 状态<br />
2）如果一个日志条目是committed状态，则该日志条目之前的日志条目都是committed状态，无论之前的日志条目是由哪个leader在哪个term创建的<br />
3）leader会维持一个已提交日志条目的最大索引（highest committed index），该索引用于告知follower日志条目的提交进展，follower会将提交日志应用到本地状态机<br />
2.1.2复制状态机<br />
复制状态机一般用于实现分布式系统中的容错问题，如果集群里的服务都能保持相同状态，即使某些机器故障，集群依旧可以正常、可靠的对外提供服务；论文中复制状态机的模型结构是：<br />
<br />
复制状态机的典型实现方式就是使用日志复制，每个服务都保存一份日志，而这些日志都按照相同的顺序保存着相同的命令，这样每个状态机都可以按照相同的日志顺序执行命令，并最终处于相同的状态，而如何保持复制日志的一致性就是一致性算法的核心工作，如上图所示：<br />
1）每个服务上都有一个一致性模块<br />
2）主服务上的一致性模块用于接收客户端的命令、并添加到自己的服务日志上<br />
3）主服务上的一致性模块会在和其他服务上的一致性模块联系、进行日志复制<br />
4）一旦日志成功复制，每个服务的状态机都能按照相同的日志顺序执行命令，并产生相同的输出，从而，整个服务对外体现整体的独立、高可用<br />
2.2leader选举<br />
Raft算法是个强Leader的算法，leader不仅参与选举，还涉及日志复制；而Raft算法中leader选举的基本流程是：<br />
如果follower在选举超时后，一直收不到leader的心跳检测（如：集群初始启动阶段、leader节点宕机），则会进入candidate状态，然后，发起新的选举，并向其他服务请求投票，如果获得大多数服务的投票，该服务成为新的leader节点，负责与客户端交互以及向follower服务发送心跳，如果竞选失败，则依据情况，进入follower状态或者继续发起下一轮选举。<br />
2.2.1状态转换<br />
论文中有列leader选举的基本流程图，但考虑涉及到的细节较多，故重新画了一个服务状态转换的流程图：<br />
<br />
如上图所示，各服务节点在状态转换中的作用：<br />
leader服务：<br />
1）负责与客户端交互，将客户端发送的命令封装成entry，追加到日志中<br />
2）心跳维护，定时发送空AppendEntry RPC到其他服务，让其维护follower状态<br />
3）将日志复制到其他服务，本部分到日志复制中再细说<br />
candidate服务：<br />
1）发起选举，向集群中其他服务发起投票<br />
2）根据选举结果不同，进入不同的处理流程，这块可以详看选举流程<br />
follower服务<br />
1）RPC响应——响应leader、candidate发起的心跳、投票、日志复制等RPC<br />
2）选举超时——leader心跳接收失败，待选举超时后，进入candidate状态，发起新的选举<br />
2.2.2选举过程<br />
选举超时后，follower节点会进入candidate状态、发起选举：<br />
<br />
选举细节如上图所示，有两个地方细说下：<br />
1）每次新的选举都会引发term自增，如上图中，follower服务首先将term自增加1，然后进入candidate状态<br />
2）candidate向集群其他服务发起投票RPC，即RequestVote RPC，投票结果分三种情况：<br />
1）投票成功，成为leader，发送心跳告知集群<br />
2）其他服务成为leader，收到新leader的心跳后，转入follower状态<br />
3）没有服务胜出，都没有得到大多数投票，则等待选举超时，进入下一轮选举，即进入"脑裂"情况<br />
关于投票，有一点需要注意下，每个服务在每个任期内只能投票一次，并且有权拒绝投票；补充一点：通过随机选举超时时间，减少碰撞机会实现，避免选举"脑裂"情况。<br />
2.2.3任期逻辑<br />
在Raft算法中，任期起到逻辑时钟的效果，主要是用于控制leader选举和log复制，它的特点是：<br />
1）整型，取值从0开始，单调递增<br />
2）term取值与election强相关，每开始一次新的选举，term都会加1<br />
任期涉及到的逻辑判断比较简单，主要是进行大小比较，总结来说，处理场景分为：<br />
1）如果收到的RPC中任期大，则更新服务任期，并进行状态转换，进入、维持follower状态，如：leader状态遇到高任期的请求，则更新自己的term、进入follower状态，等待新的选举<br />
2）如果收到的RPC中任期小，则不理会，如：日志复制中，会检测任期，如果leader的任期小，则follower不理会本次复制，选举也是一样<br />
2.3log复制<br />
Raft算法中，log复制的基本流程是：<br />
leader收到client发送的请求后，会将commands追加到日志中、并以条目的形式存在中，即log entry，然后，通过AppendEntry RPC复制日志，如果成功复制给大多数服务，则通知状态机执行entry并将结果返回给客户端，然后，状态机将日志条目标记为committed，同时，将committed日志条目同步给其他服务。<br />
2.3.1日志构成<br />
日志由条目构成，条目在日志中都进行了编号，每个条目都主要包含三部分信息：1）所属任期term；2）用于状态机执行的命令；3）日志提交标记，如：<br />
<br />
2.3.2复制流程<br />
log复制流程图如下：<br />
<br />
log复制的大致步骤是：<br />
1）客户端将携带command的请求发给集群（command交由状态机执行）<br />
2）leader服务负责响应客户端请求（补充一点，如果客户端连接的不是leader服务，该服务
会把leader地址同步给client，让client重连）<br />
3）leader将受到的请求追加到日志条目中，然后通过RPC复制给其他服务，如果实现大多数复制，则将该日志标记为committed<br />
4）通知状态机执行日志条目中的command，并将执行结果返回给客户端<br />
5）leader会记录committed状态下的最大日志索引，然后通过RPC将该索引发给follower，follower会在本地状态机执行对应的日志条目<br />
由此确保follower和leader日志执行的一致性：按照日志顺序，对于committed日志，按照相同的顺序执行条目中的command；而日志复制中的一致性检测：<br />
1）new entry的一致性检测<br />
1）leader在发送AppendEntry RPC复制日志前，会将new entry前面条目的索引、任期包含到RPC中<br />
2）follower收到RPC后，会检测本地是否有相同索引、任期的条目，如果没有，则拒绝该新条目<br />
2）old entry的一致性检测（当日志出现不一致时，leader会强制follower复制自己的日志）<br />
1）leader首先要找出与follower有共同日志的地方，处理的方式是：<br />
1）leader会为每个follower维持一直next index（初始为leader自己的条目索引），next index是leader要发给follower的下个日志条目的索引<br />
2）当RPC检测发现leader和follower日志索引不匹配时，follower会拒绝RPC，此时leader会将nextindx减1、然后继续发送RPC直到找出共同部分<br />
2）找出共同条目后，RPC会通知follower删除冲突条目、并将leader的条目复制到自己日志中<br />
需要注意的一点是：在Raft算法中，日志复制是单向的，只能从leader服务复制到follower服务，这简化了日志复制流程，后面安全性会再次提到。<br />
2.4安全性<br />
在实际环境中，leader、follower服务都会存在宕机的情况，这会对leader选举和log复制都产生影响，针对可能的异常情况，Raft也提供了安全措施确保一致性。<br />
2.4.1选举约束<br />
leader选举要求一个服务要想成为leader服务，它必须包含之前term中的所有committed日志条目；这块是在投票中处理的，其实现原理是：<br />
candidate发起选举后，会先调用RequestVote RPC向其他服务发起投票，该RPC中会携带记录candidate的日志信息，主要是日志中最后一个条目的索引和任期；其他服务收到该RPC后，会和自己的日志条目比较下，如果candidate的日志过时，则拒绝为其投票（任期越大或者索引越大，说明日志越新）；由此保证日志复制单向，只从leader服务复制到follower服务没有问题、简化日志复制流程。<br />
2.4.2提交历史任期的条目<br />
leader服务只能提交当前任期的日志，不能提交之前任期的日志，根据Log Match Property属性，如果当前任期的日志被提交，则历史任期的日志都会被提交，对此，论文中有个样例，如下图所示，关键是最后一句：<br />
<br />
2.4.3计时条件<br />
简答地说，计时条件就是满足算法流程，不出现紊乱，因为算法涉及心跳广播和选举超时，故其计时条件是：<br />
broadcastTime << electionTimeout << MTBF<br />
broadcastTime是RPC广播时长，一般不超过20ms；electionTimeout是选举超时时间，随机范围是150~300ms；MTBF是服务宕机时长。<br />
3.参考资料<br />
本文参考资料如下，感谢各位大佬：<br />
1）https://raft.github.io/raft.pdf<br />
2）https://blog.csdn.net/baijiwei/article/details/78759364<br />
3）https://blog.csdn.net/baijiwei/article/details/78760308<br />
4）https://blog.csdn.net/baijiwei/article/details/78819381<br />
有疑问加站长微信联系（非本文作者）
