ITPub博客

首页 > 应用开发 > IT综合 > 分布式一致性算法Raft实现原理

分布式一致性算法Raft实现原理

原创 IT综合 作者:l86156117 时间:2015-08-20 17:15:22 0 删除 编辑

raft作为分布式一致性算法,现在以它实现的开源项目多为分布式存储系统,其选举机制保证系统可靠性,日志复制机制保证数据一致,而由数据一致衍生出的安全问题也设置了其算法的诸多规则。本文依据相对比较成熟的raft开源项目logcabin以及Stanford相关论文做出raft的实现原理和算法描述。
Raft
工作原理

raft算法实现一致性通过先选举机制出分布式系统中的leader节点,然后由leader节点完全负责管理日志复制。leader节点从客户端接受请求产生日志,并复制到其他服务器,然后通知那些服务器这是安全的将这些日志内容提交到状态机(这里可以按将日志内容持久化到数据库这样理解)

raft算法将一致性问题分解为三个相关的子问题:

1. leader选举

2. 日志复制

3. 安全

一个raft集群中的节点包含三种状态leader,followercandiate。正常情况下一个cluster中会包含一个leader和多个followerfollowers是被动的,这点表现在followers不主动发送请求,只会对leadercandiate的请求作出反应。leader处理所有的客户端请求,如果客户端连接follower,那么follower也会将连接重定向到leader。第三种状态,candidate主要是在发生选举事件时才会存在。

raft将时间分割成随意长度的terms。这些terms被标示成连续的数字。每个term开始于election,这时多个candidate尽力成为leader,如果赢得选举,那么在剩下的term时间里将扮演leader的角色。在某些情况下选举会导致分裂投票(就是candidate之间的票数一样)。这种情况下该term以没有leader结束。新的term瞬间开始。raft保证一次term中至少产生一个leader

termsraft中代表着一个逻辑钟,它们允许服务器检测到过时leader信息。每个server存储current term这个单调增长的变量。current termsservers通讯时交换。如果一个servercurrent term比其他的小,那么它将会更新current term至一个更大的值。如果candidate或者leader发现自己的term过期,那么就会立刻恢复为follower状态,如果server接收到过时term number,它会拒绝请求。

raft使用RPC进行通讯,最基本的一致性算法需要两种两种类型RPCrequestvote RPCcandiate在选举时开始,appendentries RPCleader在复制日志并提供心跳时开始

 

Leader election

raft使用心跳机制触发leader选举。当servers启动时,它们一开始都是followersserver保持follower状态只要它接收有效的来自leadercandidateRPCleader周期性得发送心跳(这里心跳其实是指不带日志更新内容得appendentries RPC)到所有的followers来保证自己的的leader状态。如果有一个follower未接收到上面的心跳超过election timeout这个时间。那么它会假定不存在有效的leader并且开始选举新leader。当开始选举时,follower增加它的current term并且转换成candidate状态。首先candidate会投票给自己再通过并行发送requestvote RPC给每个clustercandidate持续状态到下面三件事的发生:1.它赢得选择2.其他server赢得选举3.超时并未有谁在选举中胜出。

candidate赢得选举当它接收到大部分servers的投票在相同的term中。而每个server只能投一个candidate(基于先来先服务原则)。一旦有candidate赢得选举,它成为leader后就会发送心跳到其他servers来建立自己权威并且禁止投票。

在等待投票的时候,candidate接收appendentries RPC从其他已经宣布为leader的节点。如果leaderterm大于candidatecurrent term,那么认定leader合法并且自己将状态变为follow。反之小于的话那么candidate会拒绝RPC并且继续保持candidate状态。

还有一种情况就是没有一个candidate赢得选举。当这个发生后新的选举开始。没有人获得选举一个可能是因为票数旗鼓相当,另外就是选举超时,至于选举时间是随即生成的来防止分裂投票再次发生,一般情况下这个时间是150300ms

 

Log replication

一旦leader被选举出后,它开始处理客户端请求。每个客户端请求命令包含被状态机执行的命令(比如说SQL)。leader追加命令到自己的日志中,然后使用appendEntries RPC来并行进行复制到各个server。当每条日志被安全复制到server后,leader再将每条日志持久化到自己状态机中,并且返回结果给客户端。如果followers crash或者处理太慢或者网络包丢失,那么leader会再次尝试appendentries RPC直到所有followers最终存储所有的日志内容。每条存储在状态机中的命令包含term number,这个是用来检测日志的一致性。而每条日志中同样包含它们自己在日志中位置的数字。

leader决定什么时候是安全地提供每条日志到状态机,这样地日志可以被成为commitedraft保证每条commited纪录持久化并且最终被执行到大部分状态机。一旦leader将产生地日志纪录复制到大部分servers那么日志纪录将被提交。而提交的时候将会提交所有之前的纪录,包括前任leader产生的纪录。

leader追踪已经它已经直到的最大已经提交的索引,这个索引包含在以后要发送的appendentries RPC,也会被其他所有servers处理。一旦follower发现日志纪录被提交,那么它将会将纪录提交到自己的状态机。

这样设置raft日志机制的话能保证很高的一致性在不同servers的日志中。raft包含下面两个特性,而这两个特性一起形成来日志一致特性(log matching property

1.如果两条不同日志中的纪录包含相同的索引和term,那么这两条纪录将存储相同的命令

2.如果两条不同日志中的纪录包含相同的索引和term,那么这两个日志之前的纪录是一模一样的

对于第一个特性,是因为leader大部分产生的日志纪录都包含log indexterm并且日志纪录永远不会改变它们自己在日志中的位置。对于第二个特性,由简单的appendentries来保证。当发送 appendentries RPC,leader先发送新纪录之前的indexterm。如果followers在自己的纪录中没有发现相同的indexterm那么它也就拒绝接收新纪录(appendentries check下面日志非一致状态有涉及)。从一开始,日志的初始化空状态需要满足上面说到log matching property,而这种一致性检查同样在日志扩张的过程中保持满足log matching property。作为结果,不论什么时候appendentries这个过程成功,leader都知道follow日志和自己的日志一致。

正常情况下leaderfollow的日志是保持一致的,然而当leader crash后可能由于并没有完全复制到servers就会导致日志的不一致。下面这张图就代表了和leader日志差异的a~f例子

 


对于raftleader处理非一致问题是通过将有冲突的纪录进行覆盖。为了follower与自己的日志一致,那么leaderfollower就要找到产生差异的那个pointfollower删除那个点之后的纪录,而leader要提交那个点之后的纪录给follower。对于上面的实现方法,主要利用leader包含的nextindex,这个变量是下一个发送给follower的日志纪录索引。当一个leader当权,它会初始化nextindex这个值为它日志中最大索引后的一个值。首先leaderappendentries check因为日志非一致失败之后,那么在下一次appendentriesRPC前,leader减小nextindex,如果继续失败,那么继续减小直到leaderfollower相同的point。找到point之后将会上面所说进行处理。这种机制使得leader不需要在掌权时自己恢复一致性,也不需要对自己的日志纪录做任何修改。

 

Safety

前面一直在说raft的选举和复制,然而这些机制其实也不能充分保证每个状态机以同样的顺序执行同样的命令。比如一个不可靠的followerleader提交一些日志纪录后又被选为leader那么之前leader提交的日志纪录肯定会被覆盖抹除,这就会造成不一致。

对于这种一致性的不可靠,raft算法在选举的时候添加了一些规定来保证leader在提交任何term的纪录时候都包含之前提交的所有term纪录。

选举的规定

在任何基于leader这种一致性算法,leader是必须包含所有已经提交的日志纪录的。而raft使用了比较简单方法来保证所有提交的terms纪录在选举那一会儿就都已经在新的leader中,而不需要转移这些纪录到leader,这也意味着日志纪录永远是从leader流向follower,也不需要让leader自己改动日志纪录。

raft使用投票这个过程来防止不包含所有已经提交纪录的candidate赢得选举。具体实现是candidate包含candidate的日志信息发送Requestvote RPC后,参与投票的server便会比较candidate的日志是不是比自己的新,如果不是的话将拒绝投票。而raft比较日志谁更加新,是通过比较indexterm中的最后一条记录。

Committing entries from previous term,如果之前的leader没有commit一些纪录,那么这是一个新的leader所需要做的。为了避免一些问题,raft不提交之前term的日志纪录通过对复制了几个server进行计数,只有当前的term纪录才会通过计数提交,并在提交后将之前所有的term纪录间接地提交,因为它们不符合log matching property上面提到地特性。

raft引用这种额外复杂地规则因为日志纪录包含它们原始term编号当leader复制之前的term中的纪录时。

 

 

followercandidatecrashes

到目前为止一直讨论的时leadercrashes。相对来说followercandidatecrashes更加简单。如果followercandidate crashes,那么以后的requestvote appendentries RPC发送就会失败。raft会不断得去尝试发送个体失败节点,如果crashed server重启那么RPC也会成功。如果接收到在日志中已经有得纪录那么它也会忽略这个请求。

 

关于时间和可靠性

需要说得时,raft的安全不能依赖时间,系统不可能因为事件发生快了或者慢了而去产生错误结果。然而可靠性又必须

依靠时间。比如server crashes导致的信息交换延迟可能就会让candidate hang在那了。或者没有稳定的leaderraft就不能正常工作了。

leader electionraft的重要一部分。raft发起选举和维护稳定的leader只要满足下面的时间要求

广播时间<<选举超时时间<<MTBF

 

关于集群成员变换

到现在为止都是假设集群的配置是合适的,即所有的servers都参与到一致性算法中了。事实上,偶尔需要改变配置,比如说替换失败的节点或者改变复制的等级。尽管这可以通过让集群下线,更新配置,再重新上线来实现。但这样会影响系统的可靠性或者产生人工的错误。为了避免这些问题应该自动改变配置并且把新servers融入raft算法中。

 

日志比较

随着日志增长,它会占用更多空间并且需要更多时间作出响应,那么如果不删除过期的日志那么会造成一些问题。

快照是最简单的方法处理这个问题。在快照中,整个当前系统状态作为快照被写入到稳定的存储中,然后删除到快照的那个点。

 

logcabinraft算法实现

关于状态

相对稳定的状态变量 for all server(在回复RPC之前更新)

currentTerm

当前的term,初始化为0,单调增

voteFor

当前term所投给的candidate Id

log[]

状态机需要纪录的命令以及从leader接收的纪录

 

不稳定的状态变量 for all server,索引为1

commitIndex

最新提交纪录的索引,初始化为0,单调递增

lastApplied

提交给状态机的最新索引,初始化为0,单调递增

 

不稳定的状态变量 for leaders

nextIndex[]

发给每个server下一条纪录的索引,初始化为上一个leader的最后日志索引+1

matchIndex[]

每个server已知复制到server的索引,初始化为0,单调递增

 

关于AppendEntries RPC(执行leader复制,同样)

变量

term  leaderterm

leaderId 方便follower重定向客户端

prevLogIndex

先于新索引的日志纪录索引

prevLogTerm

prevLogIndexterm

entries[]

存储的日志纪录

leaderCommit

leader'scommitIndex

返回结果

term currentTerm,leader更新

success 返回true如果follower包含与prevLogIndexpreLogTerm匹配的纪录

 

接收者实现:

1. 返回false如果term<currentTerm

2. 返回false如果不包含与prevLogIndexprevLogTerm匹配的纪录

3. 如果已经存在的纪录和新纪录冲突(相同索引不同term),删除存在的纪录并且从此处开始纪录

4.追加任何不存在的新纪录

5.如果leaderCommit>commitIndex,那么将commitIndex设置为最小的leaderCommit

 

关于RequestVote RPC

变量

term candidateterm

candidateId 求票的candidateid

lastLogIndex candidate最新log纪录索引

lastLogTerm candidate最新log纪录索引的term

 

返回:

term 当前term,用于candidate自我更新

voteGranted 返回true意味着接受到了投票

接受者实现:

1.返回false如果term<currentTerm

2.voteFornull或者candidateId,candidate日志要比接收者的日志新就给票

 

一些servers的规则

所有servers:

1.如果commitIndex>lastApplied,增加lastApplied,并且将log[lastApplied]提交给状态机,也就是持久化

2.如果RPC包含的term T>currentTerm那么更新currentTerm,转变为follower

 

followers

1.candidatesleadersRPC作出响应

2.如果因为没有接收到leadercandidate AppendEntrieselection timeout,转变为candidate

 

candidates

1.转化为candidate后开始选举,潜规则是currentTerm增加,给自己投票以及重置选举时间

2.如果接收到大多数servers的投票,那么成为leader

3.如果接收到新leaderappendentries RPC,那么转换为leader

4.如果选举超时那么开始新的选举

 

leaders

1.选举后,发送初始化空的appendentries RPC即心跳给每个server,重复发送心跳来防止超时选举

2.如果从客户端接收命令后,先追加纪录到本地日志,将纪录提交给状态机后回复客户端

3.如果last log index>nextIndex对于follower,那么将从nextIndex的纪录发送给follower

如果成功,更新followernextIndexmatchIndex

如果失败那么减小nextIndex再重试。

 

 

 

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/28944233/viewspace-1777786/,如需转载,请注明出处,否则将追究法律责任。

上一篇: InnoDB参数内幕
下一篇: 碎记
请登录后发表评论 登录
全部评论

注册时间:2014-10-22

  • 博文量
    16
  • 访问量
    56264