湖南州省郴州,北京如何优化网站,群晖nas wordpress,wordpress安卓手机版强一致性、高可用的存储组件是构建现代分布式系统的必要条件#xff0c;广泛应用于注册中心、配置中心等平台设施中#xff0c;分布式锁、协调器等等各类场景需求也有相关需求#xff0c;在该领域有众多知名的开源组件#xff0c;如etcd、zookeeper、Tikv等等。共识算法是实…强一致性、高可用的存储组件是构建现代分布式系统的必要条件广泛应用于注册中心、配置中心等平台设施中分布式锁、协调器等等各类场景需求也有相关需求在该领域有众多知名的开源组件如etcd、zookeeper、Tikv等等。共识算法是实现这类组件的关键算法。简单的说共识算法是协调多个节点达成共识的算法这是构建高可用系统的基石。大部分典型的共识算法都是基于状态复制机来实现的每个节点都有一个状态机以及一个日志状态机用于保持一个共识的结果这样客户端只要连接到任意节点上就可以获取到状态机的内容。而日志是用于保证输入的顺序只要保证所有日志的提交顺序是一致的则可以保证各个节点的状态机是一直的。共识算法有很多种就我知道的有paxos、raft、zab、VR(Viewstamped Replication)等等。paxos以复杂和难以理解著称通常来说raft是更容易理解的算法也更容易在工程实践中采用而且在性能上并没有损失所以下面我们讨论一下raft的的基本原理和一些要点。 下面的文章主要基于raft的paper整理而成相关资料可以从https://raft.github.io/获取。raft算法原理与实现raft最主要的贡献在于2点一个是将复杂的分布式算法分解成几个独立的解释和解决的子问题并且。将状态进行简化最小程度的考虑必要的问题这些工作使得raft共识算法成为一种有效的新的方法。广泛的应用于教学和工程实践中 raft算法的基本流程是首先选举出leader由leader完成日志复刻的功能。如果follower仅仅接受来自leader的日志复制请求而没有反向的日志流。raft的leader是一个强大的leader。当follower的日志和leader的日志不同时会强制覆盖自己的日志给follower。当leader宕机时会选出新的leader来继续任务。raft讲上述的基本流程拆分成3个部分选主过程(leader election)、日志复制(log replication)、安全性(safety)加上成员变更(membership changing)。不过在具体讨论这4个部分的内容的过程中我们还是简单的讨论下raft的一些关键模型和概念角色和周期节点的角色raft的典型节点可以分为3种follower、candidate、leader。follower所有节点在初始化之后都是follower。follower的职责仅仅是接受来自leader的复制日志的请求或是在leader宕机时(未在超时时间内接受到心跳信息)成candidate尝试成为leader亦或是接受到candidate的投票请求时响应改请求candidate当leader宕机时超过超时时间的follower会转变成candidatecandidater会向集群内的所有机器发送请求投票给自己的请求。leaderleader负责日志复制的过程。并且将自己的日志通过心跳发送给其他机器同步日志所有来自客户端的写请求都会由leader处理在过半数的机器提交之后就可以返回成功标志给客户端。任期周期raft工作流程由一个个任期组成通常来说任期由2部分组成一部分是选举阶段在该阶段集群会尝试进行选主选主如果成功则进入了常规操作阶段。在选举阶段是没办法响应客户端请求的只有进入常规操作阶段才能正常的提供服务。 当然也会存在没有选出主节点的情况这时会开启一个新的任期。此外还有一点需要说明一个集群内的节点可能在同一时刻处于不同的任期中的因此任期本身是有编号的如果节点接受到更高任期节点发送过来的请求则会更新自己的任期并转变成follower。 在raft中实施上只需要2中rpc一种是由候选人发出的请求投票信息用于在选主阶段将请求其他服务器投票给自己另一种是附加条目请求由领导人发起用来复制日志并提供一种心跳机制。Leader electionraft使用一种从leader到follower的心跳机制来探活机器如果在一个心跳周期内follower如果没有收到来自leader的心跳则follower会认为集群内没有leader节点自动转成candidate并发起投票请求。 在选举过程中follwer会将任期加1并且转换成candidate持续发送请求直到下面3个情况发生 (1)赢得半数以上的票数赢得选举。每个服务器会对一个任期投出一张选票会投票给最先到来的请求。 (2)其他服务器成为领导者候选人也会接收到其他机器的投票请求rpc如果接收到投票请求所属的任期小于当前任期候选人则会承认该请求发送者的领导者地位并转换成follower如果rpc所属的任期比自己小就拒绝掉该请求。 (3)一段时间后没有这种情况下是可能有同时存在多个候选人因此没有一个候选人获取了大多数人的支持这种情况下则需要结束当前任期开始一个新的任期。为了避免重复这种现象rafr使用随机选举超时时间的方法来确保很少发生选票瓜分的情况。 其实这里还涉及到一个选举超时时间的设定。基本上来说raft的算法要求系统满足下面的时间要求 广播时间(broadcastTime) 选举超时时间(electionTimeout) 平均故障间隔时间(MTBF) 广播时间是节点发送rpc的品能根据rt时间故障时间通常至少有几个月。因此选项时间大概在几十或者几百毫秒比较合适。Log replication领导者接收到的来自客户端的请求后会给在本地日志附加一套新的记录并且并发的发送该记录给其他机器中。当这条日志条目被安全的复制领导人会应用这条日志条目到他的状态机中并且把结果返回给客户端。如果有follower没有返回请求则leader会不断重试。每一条日志条目存储一个条状态机指令和从领导人收到这条指令时的任期号。日志中的任期号用来检测是否出现不一致的情况。每条日志也有一个整数索引值表明他的位置。 当一个日志对应的rpc接收到大多数机器的响应则说明该日志已经被提交了raft会保证已提交的日志会被可用的状态机执行。一旦当前的日志被提交该条日志之前的所有日志都会被提交。包括有其他领导人创建的、以及此前任期创建的日志。领导人会保持当前被提交的日志的最大索引号该索引会跟随追加条目的rpc因此该索引号会被其他服务器提交。 raft的日志具有日志匹配的特性如果在不同的日志中的两个条目拥有相同的索引和任期号那么他们存储了相同的指令。领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目同时日志条目在日志中的位置也从来不会改变。如果在不同的日志中的两个条目拥有相同的索引和任期号那么他们之前的所有日志条目也全部相同。因为在发送附加日志 RPC 的时候领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目那么他就会拒绝接收新的日志条目。然而在leader宕机的情况下附加日志的rpc会不一致。如上图所示follower的日志可能比leader多或者少这种情况下leader会强制复制自己的日志从而简化操作。 为了使得follower和自己的日志一致领导人必须找到最后2者一致的地方。然后删除从这个点那之后的所有日志。为了找到这个不一致的其实日志leader在发送追加日志的rpc的时候回针对每个follwer维护一个nextIndex。每当leader进入常规阶段时会将nextIndex初始化为leader的最后一条日志会将这个nextIndex给发送给其他follwer。如果follwer和当前机器不一致则会返回失败而这时leader会把该follwer对应的nextIndex-1跟随下一次追加日志的rpc发送直到找到不一致的日志起始点。Safety前面的章节里描述了 Raft 算法是如何选举和复制日志的。然而到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。这里需要讨论一些特殊的限制选举限制在基于leader 的一致性算法中领导人必须存储已经提交的所有日志。为了保证这一点raft的策略是在投票阶段杜绝这种情况。RPC 中包含了候选人的日志信息然后投票人会拒绝掉那些日志没有自己新的投票请求。 Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同那么任期号大的日志更加新。如果两份日志最后的条目任期号相同那么日志比较长的那个就更加新。提交之前任期内的日志条目下图描述了一种之前未讨论过的情况如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中S1 是leader部分的复制了索引位置 2 的日志条目。在 (b) 中S1 崩溃了然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)S5 又崩溃了S1 重新启动选举成功开始复制日志。在这时来自任期 2 的那条日志已经被复制到了集群中的大多数机器上但是还没有被提交。如果 S1 在 (d) 中又崩溃了S5 可以重新被选举成功(通过来自 S2S3 和 S4 的选票)然后覆盖了他们在索引 2 处的日志。反之如果在崩溃之前S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上就如 (e) 中那样那么在后面任期里面这些新的日志条目就会被提交(因为S5 就不可能选举成功)。 这样在同一时刻就同时保证了之前的所有老的日志条目就会被提交。 为了消除这种场景Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有当前任期里的日志条目通过计算副本数目可以被提交一旦当前任期的日志条目以这种方式被提交那么由于日志匹配特性之前的日志条目也都会被间接的提交。 Cluster membership change多节点的成员变更前3个小节的内容基本描述了整个raft的主要内容但是在工程实践中还有一个问题需要讨论如果完成节点的配置替换或者希望新增或者删除节点改如何处理呢在如上图的情况中在新旧2个配置的集群中可能会同时存在2个组分别产生2个leader的情况违反了safety。 raft的原文中提出了一种2阶段提交的方式基本思路是不允许旧配置和新配置同时进行决策而是在2者之间加入一段Joint Consensus的过渡时期。具体的做法来说向leader发送一个集群配置变更的请求Cold,newleader将改日志复制给其他节点尝试commit如果失败了就重试如果commit成功说明大部分节点都有该日志了这时即使leader宕机了重新启动的节点也是拥有该节点的。这时leader发送一个Cnew状态变更指令带到这个指令commit之后就可以只使用新配置来选主了。Single Cluster MemberShip Change这里描述的方式虽然可行但是实践中大部分不会采用这么麻烦的方式一种策略也是Diego在其博士论文中提出的Single Cluster MemberShip Change其基本思路就是上问中出现两个leader的根本原因是2个集群的节点不存在重叠也就是说无法存在一个仲裁者来觉得采用哪个配置。如果所示实际上如果每次只变更一个节点要获得大多数集群的投票新旧集群就必定有相交Single Cluster MemberShip Change定了一种configuration LogEntry添加到日志configuration LogEntry代表了集群配置的更新。Diego还论证了configuration LogEntry只要追加到日志就行了因为如果configuration LogEntry没有被提交其影响也仅仅是系统配置回滚到原始配置而已。 当然这种方式也有问题在于如果前一次的configuration LogEntry还没有完全提交新一次的configuration LogEntry就被写入了也可能导致老配置被回滚而配置错误不过一般情况下配置变更是人为可控的完全可以等到新配置生效后再进行下一个节点的配置。 不过即使是这样实践中还是有更简单的方式比如etcd就是等到configuration LogEntry完全应用之后再进行下一次配置变更。raft 语义与概念最后我们总结一下raft的实现要点状态状态所有服务器上持久化currentTerm服务器最新任期号(初始化为 0持续递增)votedFor在当前获得选票的candidateIdlog[]日志条目集每一个条目包含一个用户状态机执行的指令和收到时的任期号状态所有服务器上非持久化commitIndex已知的最大的已经被提交的日志条目的索引值lastApplied最后被应用到状态机的日志条目索引值(初始化为 0持续递增)状态所有服务器上非持久化nextIndex[]对于每一个服务器需要发送给他的下一个日志条目的索引值(初始化为leader最后索引值加一)matchIndex[]对于每一个服务器已经复制给他的日志的最高索引值rpc协议追加日志请求参数解释termleader的任期号leaderIdleader的 Id以便于跟随者重定向请求prevLogIndex新的日志条目紧随之前的索引值prevLogTermprevLogIndex 条目的任期号entries[]准备存储的日志条目(表示心跳时为空一次性发送多个是为了提高效率)leaderCommit领导人已经提交的日志的索引值返回参数解释term当前的任期号用于领导人去更新自己success跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真接收者实现如果 term currentTerm 就返回 false如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配则返回 false如果已经存在的日志条目和新的产生冲突(索引值相同但是任期号不同)删除这一条和之后所有的附加日志中尚未存在的任何新条目如果 leaderCommit commitIndex令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个请求投票请求参数解释termleader的任期号candidateId请求选票的候选人的 IdlastLogIndex候选人的最后日志条目的索引值lastLogTerm候选人最后日志条目的任期号返回参数解释term当前的任期号用于领导人去更新自己voteGranted候选人赢得了此张选票时为真接收者实现如果term currentTerm返回 false如果 votedFor 为空或者为 candidateId并且候选人的日志至少和自己一样新那么就投票给他规则所有服务器如果commitIndex lastApplied那么就 lastApplied 加一并把log[lastApplied]应用到状态机中如果接收到的 RPC 请求或响应中任期号T currentTerm那么就令 currentTerm 等于 T并切换状态为跟随者 follower响应来自候选人和领导者的请求如果在超过选举超时时间的情况之前都没有收到领导人的心跳或者是候选人请求投票的就自己变成候选人 candidate在转变成候选人后就立即开始选举过程自增当前的任期号(currentTerm)给自己投票重置选举超时计时器发送请求投票的 RPC 给其他所有服务器如果接收到大多数服务器的选票那么就变成领导人如果接收到来自新的领导人的附加日志 RPC转变成跟随者如果选举过程超时再次发起一轮选举 leader一旦成为领导人发送空的附加日志 RPC(心跳)给其他所有的服务器在一定的空余时间之后不停的重复发送以阻止跟随者超时如果接收到来自客户端的请求附加条目到本地日志中在条目被应用到状态机后响应客户端如果对于一个跟随者最后日志条目的索引值大于等于 nextIndex那么发送从 nextIndex 开始的所有日志条目如果成功更新相应跟随者的 nextIndex 和 matchIndex如果因为日志不一致而失败减少 nextIndex 重试如果存在一个满足N commitIndex的 N并且大多数的matchIndex[i] ≥ N成立并且log[N].term currentTerm成立那么令 commitIndex 等于这个 N
