Raft协议之Leader选举

Raft节点状态

Raft协议的工作模式是一个Leader和多个Follower节点的模式。在Raft协议中,每个节点都维护了一个状态机,该状态机有3种状态,Leader,Follower,Candidate,在任意时间,集群中的任意节点都处于这三个状态之一。

Leader

Leader节点的主要工作有两个,一个是处理所有client的请求,另一个是定期向Follower节点发送心跳信息。

当收到客户端写入请求时,Leader节点会在本地追加一个日志,然后将其封装成消息发送到集群中的其他Follow节点。Follower节点收到对应消息对其进行响应。Leader如果收到超过半数节点的响应信息,则认为该条日志已被committed,可以对client返回响应

定期向Follower发送心跳信息是为了防止集群其他Follower节点的选举计时器超时而导致触发新一轮选举

Follower

Follower节点不会处理任何请求,他们只是简单的响应来自Leader或者Candidate的请求。Follower会将client节点的请求重定向给集群的Leader节点

Candidate

Candidate节点由Follower节点转换而来,当Follower节点长时间没有收到来自Leader节点发送的心跳信息,则该节点的选举计时器就会过期,同时将自身状态变为Candidate,发起新一轮选举

Leader选举

在Raft协议中有两个时间控制Leader选举发生

  1. 选举超时时间(election timeout)
  2. 心跳超时时间(heartbeat timeout)

选举超时时间:Follower在election timeout时间内没有收到Leader的心跳信息,则切换为Candidate开始新一轮的选举。election timeout一般设置为150ms~300ms的随机数,也即每个节点的选举超时时间一般都不同

心跳超时时间:Leader向Follower节点发送心跳消息的间隔时间

初始选举

  1. 集群初始化时,所有节点为Follower
  2. 在经过一段时间后(election timeout)收不到Leader的心跳信息,则认为Leader出现故障,切换为Candidate发起选举
  3. Raft协议中每次发起选举,任期(Term)都会进行递增,每个节点都会记录当前任期(currentTerm)
  4. 当一个Candidate收到超过半数节点的选票,则成为Leader

假设集群有A,B,C三个节点,若A节点的选举超时时间最先超时,则

  1. A切换为Candidate,同时重置选举计时器(election timer)
  2. A先把票投给自己,并向集群其他节点B,C发送选举请求(Request vote),此时A的term=1
  3. B,C收到选举请求时,因为两个节点的term=0,且都是Follower状态,所以它们会把选票投给A节点
  4. B,C节点投票之后,会重置选举计时器,这是防止一个任期中出现多个Candidate,导致选举失败
  5. A节点得到超过半数的选票,在term=1的任期中,A成为集群的Leader
  6. A节点成为Leader后,会定期向B,C节点发送心跳信息,防止B,C节点的选举计时器超时而触发新一轮选举,所以心跳超时时间要远小于选举超时时间

出现多个Candidate节点

当出现多个Candidate同时发起选举,而每个Candidate都获取不到半数的选票,这种情况Raft情况会如何处理呢?

假设集群有4个节点,其中节点A和节点B的选举计时器同时到期,切换为Candidate并向集群其他节点发起选举请求

  1. 假设A的选举请求先到C,而B的请求先到D,则节点A和节点B得票数都为2,没有超过半数
  2. 在这种情况下,这次选举以失败结束,随着时间流逝,当任意节点的选举计时器到期后,会再一次发起选举。
  3. 由于election timeout是一个时间区间内取的随机数,所以上述情况多次出现的概率不大

宕机选举

假设集群中有4个节点,其中A为Leader,B,C,D为Follower,在系统运行一段时间后(当前term为5),A因为故障而宕机。

  1. 由于Leader不在往Follower发送心跳消息,Follower的election timer将会过期,假设为D节点最先超时,切换为Candidate发起新一轮选举
  2. 当B和C收到节点D的选举请求后,会将其选票投给D,由于节点A已经宕机,无法投票,但D节点仍获得超过半数的投票,成为新任期(term=6)的Leader,并开始向其他节点发送心跳信息
  3. 当A节点恢复后,会收到来自D节点的心跳信息,改信息中携带的任期号(term=6)大于节点A当前记录的任期号(term=5),A节点切换为Follower

在Raft协议中,当某个节点收到的消息中所携带的任期号大于当前节点记录的任期号,那么节点会自动切换为Follower,并且更新自身记录的任期号

Leader选举时间要求

通过上述几个例子,可以看到Leader选举对于时间的要求比较严格,一般要求整个集群的时间满足如下不等式

广播时间 << 选举超时时间 << 平均故障间隔时间

广播时间指从一个节点发送心跳信息到其他节点收到信息并发出响应的平均时间

平均故障时间是指一个节点,两次故障之间的平均时间。

为了保证集群可用,广播时间必须比选举超时时间小一个数量级,这样Leader才能发送心跳信息来重置其他Follower的选举计时器,从而防止他们切换为Candidate,触发新一轮选举。选举超时时间是一个随机数 ,这样可以减少出现多个Candidate而瓜分选票的情况。

一般情况广播时间可以做到0.5ms~50ms,选举超时时间一般设置为200ms~1s之间。

总结

  1. Raft协议中节点有三种状态Leader,Follower,Candidate
  2. 控制选举触发的时间有两个,一是选举超时时间(election timeout),一个心跳超时时间(heartbeat timeout)
  3. 选举计时器(election timer)每次重置都会从某个时间区间随机取一个随机数,作为新的选举超时时间,这样是为了避免出现多个Candidate而导致选举无效的情况出现

Reprint please specify: wbl Raft协议之Leader选举

Previous
Raft协议之日志复制 Raft协议之日志复制
上篇Raft协议之Leader选举介绍了Leader选举的过程。Leader会处理来自客户端的请求,并将客户端更新操作以消息(Append Entries消息)的形式发送到集群中所有Follower节点。本文将介绍Raft协议日志复制的流程
2019-03-31
Next
Spring Boot多数据源 Spring Boot多数据源
maven 配置<parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-sta
2019-03-23