Go语言学习——深入学习一致性算法Raft

tianqy · · 1973 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

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

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1973 次点击  ∙  2 赞  
加入收藏 微博
5 回复  |  直到 2021-10-07 13:18:48
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传