Raft算法

2022-11-29 09:13:16 浏览数 (2)

Raft 算法也是一种少数服从多数的算法,在任何时候一个服务器可以扮演以下角色之一:

Leader:负责 Client 交互 和 log 复制,同一时刻系统中最多存在一个

Follower:被动响应请求 RPC,从不主动发起请求 RPC

Candidate : 由Follower 向Leader转换的中间状态

Term 在Raft中使用了一个可以理解为周期(第几届、任期)的概念,用Term作为一个周期,每个Term都是一个连续递增的编号,每一轮选举都是一个Term周期,在一个Term中只能产生一个Leader;先简单描述下Term的变化流程:Raft开始时所有Follower的Term为1,其中一个Follower逻辑时钟到期后转换为Candidate,Term加1,这时Term为2(任期),然后开始选举,这时候有几种情况会使Term发生改变: 

如果当前Term为2的任期内没有选举出Leader或出现异常,则Term递增,开始新一任期选举

当这轮Term为2的周期选举出Leader后,过后Leader宕掉了,然后其他Follower转为Candidate,Term递增,开始新一任期选举

当Leader或Candidate发现自己的Term比别的Follower小时,Leader或Candidate将转为Follower,Term递增

当Follower的Term比别的Term小时,Follower也将更新Term保持与其他Follower一致;

可以说每次Term的递增都将发生新一轮的选举,Raft保证一个Term只有一个Leader,在Raft正常运转中所有的节点的Term都是一致的,如果节点不发生故障一个Term(任期)会一直保持下去,当某节点收到的请求中Term比当前Term小时则拒绝该请求;

 选举 Raft的选举由定时器来触发,每个节点的选举定时器时间都是不一样的,开始时状态都为Follower,某个节点定时器触发选举后Term递增,状态由Follower转为Candidate,向其他节点发起RequestVote RPC请求,这时候有三种可能的情况发生:

该RequestVote请求接收到n/2 1(过半数)个节点的投票,从Candidate转为Leader,向其他节点发送heartBeat以保持Leader的正常运转

在此期间如果收到其他节点发送过来的AppendEntries RPC请求,如该节点的Term大则当前节点转为Follower,否则保持Candidate拒绝该请求

Election timeout发生则Term递增,重新发起选举

在一个Term期间每个节点只能投票一次,所以当有多个Candidate存在时就会出现每个Candidate发起的选举都存在接收到的投票数都不过半的问题,这时每个Candidate都将Term递增、重启定时器并重新发起选举,由于每个节点中定时器的时间都是随机的,所以就不会多次存在有多个Candidate同时发起投票的问题。 

0 人点赞