本文转载自微信公众号《架构改进之路》，作者张张。转载本文请联系建筑改良之路公众号。大家好，我是张张，公众号《架构提升之路》的作者。最近和组员聊了聊共识算法Raft，于是翻了翻之前发表的文章，重新学习了一下。1.Raft算法概述当我们只有一个服务节点时，不存在节点共识问题。当有多个不同的服务节点时，就会引入分布式一致性的问题。Raft是一个实现分布式共识的协议。所谓共识，就是多个节点就某件事达成共识，即使是在某些节点故障、网络延迟、网络分段的情况下。主要应用场景：RedisSentinel的选举LeaderEtcd主要是为了共享配置和服务发现实现一致性。Raft算法加密货币（比特币、区块链）的共识算法主要解决哪些问题？分布式存储系统的维护通常通过使用多副本来提高系统的可用性，这是分布式存储系统的核心问题之一：维护多副本的数据一致性。2.Raft算法实现过程为了提高理解力，Raft将共识算法分为leader选择、日志复制、安全等几个部分，并使用更强的一致性来减少必须考虑的状态。本文以一个小故事为例，方便大家快速理解。2.1Leader选举部门需要组建新的服务团队，现在有A，B，C三个同学，为了方便后期统一调配资源和管理需要，现在需要选举三个学生中的组长。A觉得自己有能力做好leader，就对B、C说，“来投我一票吧，我要当leader”。这时A成为候选人，提前投票给自己。1)IfBandChaveneverthoughtaboutbeingaleaderbefore,thensay"Okay,voteforyou"→Agets3votesandiselectedleader2)IfBthoughtaboutbeingaleaderbefore,BvotedforhimselfCvotesforA→Agets2votes(morethanhalfofthe3people),andiselectedLeader3)IfbothBandChavevotedforthemselves→A,B,andCeachgetone,theelectionfailsandre-initiates4)IfBhasthoughtofbeingaleaderbefore,andChasalreadyvotedforB→Bhasobtained2votes(morethanhalfofthe3people),theelectedLeadercanbefoundfromtheaboveelectionprocess,aAnodemust随时处于以下三种状态之一：Leader（领导者）Follower（追随者）Candidate（候选人）这三种状态的转换过程如下图所示：选举过程的第一步：Follower成为Candidate如果Follower如果听不到Leader的意见，就可以成为Candidate。步骤2：候选人争取为自己投票，并向其他节点发送投票请求。节点收到请求后响应。第三步：等待其他节点回复如果候选人如果一个人获得了超过一半节点的选票（包括他自己的一票），他将成为Leader。如果candidate被通知Leader已经生成，他会自己切换成Follower。Ifhedoesnotreceivemorethanhalfofthevotesforaperiodoftime,hewillremainacandidateRe-initiatetheelectionStep4:Thecandidatewinstheelection.新的Leader会立即向所有节点发送消息，以防止其他节点触发新的选举。2.2日志同步上面2.1的Leader选举完成后，GroupLeader就已经选好了。这里我们假设A已经被选为Leader。可以在对接端（称为客户端）承担同学们提出的一些操作任务。规定每次对接需求，都要经过组长。员工提出操作请求，Leader收到后记录下来，同步给群内其他同学。Leader会确认操作，并将执行结果同步给员工（Follower节点），直到其他同学确认请求。LogReplication（日志复制）经过Leader选举过程产生新的Leader节点，所有对系统的变更都必须通过Leader节点来实现。Step1:Leaderappendlogentry(追加日志条目)系统中的每一个变化都作为一个条目添加到节点的日志中Step2:Leader并行发送AppendEntriesRPC并等待响应Leader会等到超过一半节点在写入条目，Leader节点提交，然后Leader通知Follower条目已经提交。Step3：Leader得到大部分响应，将入口状态机应用到状态机：可以理解为一个definiteapplication。所谓确定，就是只要输入相同，任何状态机都会计算出相同的输出。第四步：Leader回复Client，同时通知Follower申请日志。当前集群已就系统状态达成共识。基于日志的复制状态机示意图：关于应用过程的几个问题Q1如果Client请求访问Follower节点怎么办？答：Follower节点会将请求转发给Leader节点。Q2当Leader和Follower的日志不一致时，怎么办？答：1）Leader处理日志不一致的方式是强制Follower复制自己的日志，Follower上不一致的日志会被Leader的日志覆盖。2）Leader为了让Followers的日志和自己的一致，Leader需要找到Follower和自己的日志一致的地方，然后覆盖该位置之后Followers的条目。3）Leader会从后往前试。每次AppendEntries失败，都会尝试之前的logentry，直到成功找到各个Follower的log一致位置，然后将那个位置之后的Followers的entry一一覆盖。2.3安全保障为了保证团队的稳定运行，默认有几个要求：2.3.1选举安全，即任何一个任期最多只能选举出一个leader。如果系统中同时有多个leader，则称为brainsplit，会导致datacoverage丢失。一个团队在一定时间内只能存在一个Leader（选举失败这种特殊情况除外），否则多个Leader同时处理需求并下达命令，容易造成团队内部不一致。在Raft中，有两点保证了这个属性：1）一个节点在某个任期内最多只能投一票；2）只有获得多数票的节点才能成为领导者。2.3.2日志匹配完整性如果同一个团队中的两个学生目前负责同一个事务，那么他们之前的工作记录也应该是一致的。即：相同的初始状态+相同的操作=相同的结束状态Leader将client的请求一个一个封装成日志条目，将这些日志条目复制到其他follower节点，每个人按顺序应用这些请求，那么最终状态一定是持续的。Raft日志同步的结论：1）如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的命令。2)如果不同日志中的两个条目具有相同的索引和任期，则所有先前的条目都是相同的。2.3.3领导者数据完整性团队中的后续领导者必须知道团队之前的工作内容，因为领导者任期内的所有工作记录都会被移交。如果在某个任期提交了一条日志条目，那么这条日志一定会出现在所有更高任期领导者的日志中。Raft日志覆盖规则：1)一条日志只有复制到多数节点才被提交2)一个节点只有获得多数票才能成为leader，节点A投票给节点B的前提条件之一是B的日志不能早于A的日志。3.总结所有算法的实现原理。其实都是对真实社会工作模式的影射。结合生活中的实际案例来理解复杂的共识算法，可以让我们事半功倍。本文旨在为大家简单介绍一下Raft协议。如果你有兴趣深入了解，我推荐你两个很好的链接：1）Raft可视化测试和各种语言版本的Raft实现：https://raft。github.io/2）Raft算法-动画演示（很好的入门教程）：http://thesecretlivesofdata.com/raft/
