Raft 算法选主详解与复现, 完成 MIT 6.824(6.5840) Lab2A

背景: Raft算法是继Paxos之后又一伟大的共识算法。 所谓共识算法就是为了解决 分布式系统中各节点数据不一致而生的算法，围绕选主, 日志复制，安全性等一系列关键问题而展开。 大名鼎鼎的 ETCD 的底层实现就基于 RAFT。这篇文章致力于 Raft 选主部分 的最详细解释与算法复现。看完本文章你将有能力独立完成 MIT 6.8214(6.5804) Lab2A。 希望你提前看过 raft 论文 和 拥有 golang 并发编程的经验 。 此贴可能会非常的繁琐，但看完之后一定能解决你很多关于 raft 选主方面的疑惑。

什么是 选主(Leader Election)？

在 raft 算法中， 分布式系统的节点被分成三类, leader， follower, candidate. 其中 leader 具有一系列重要功能: 包括但不限于:

其他两个角色中,follower 作为 leader 的追随者, 处处听从 leader 指挥(前提是leader确实是有资格，合法的leader, 后面我会详解什么情况下leader不合法)。当 follower 找不到 leader， 或者认为现在的 leader 已不再够资格时 就会转化成 candidate， 然后竞选成为 下一代(raft 中成为下一个 term， 或者理解为任期) leader。candidate 竞选成为 leader的这一过程就成为 选主 (Leader Election）.

raft 算法中的leader是有任期的， 任期也成为 term。 一个 term 内有且只有一个 leader。 term在实现中是一个单调递增的变量。每到一个新任期, term 都会+1。后面我们会说到并不是每一个 term 都能选出 leader的。但是, 好的一致性算法应当保证尽可能每一个 term 都能选出leader。 试想如果经常选不出leader， 分布式系统中的节点将处于一个群龙无首的状态， 工作效率将会大打折扣。

正是因为 leader 在分布式系统中的重要性，选主的也成为了各类一致性算法的核心。

leader， follower, candidate 之间的转化关系

上面说完了 leader， follower, candidate 三个角色的分工， 下面详解三者之间如何转换。下图是 raft 算法中的转换图:

按照转化图, 我们可以简单翻译一下 各个 角色之间如何转换:

选主过程 详解

看完上面的转化图，详信你应该对 raft 的选主有个粗略的掌握了。之所以是粗略，那是因为实际中的选主远比上面的转化图要复杂得多。有许多边界情况，许多容错处理的情况, 以及选主的一致性保障，上面的图是没有办法覆盖的。下面我将尽可能由浅入深地讲解raft算法中的角色转换细节， 以及为什么这样转换

一致性保障

所谓一致性，就是尽量确保同一时刻有且仅有一个合法的 leader， 不能多个节点跳出来都声称自己是leader 。为此， raft 算法主要从以下多个维度来实现：

成为 leader的条件尽可能的 苛刻

raft采取投票的方式进行选主， 只有当一个 节点获得超过半数以上的节点投票给自己时， 自己才会宣布成为 leader。 如此一来，一旦选出了 leader， 即使有其他节点"起兵造反" 也会因为最多只能拿到小半数的投票 而老老实实让贤。

leader 通过心跳机制维护自己的 leader 身份

leader 一旦成为 leader 以后， 会规律地，定时地向其他节点发送心跳, 其他节点在收到leader心跳后, 会做出回应， 这里的回应可以是服从 leader， 也可以是反对leader

leader不会主动让位

为了尽可能维持系统的稳定性，不至于经常群龙无首， leader的身份应该尽可能地不受干扰。一个 leader 有且只有两种情况下才会被迫退出 leader 回到 follower， 分别是:

leader 只会变成 follower, 而不会成为 candidate

上面说过稳定的系统中，各个节点的 term 应该保持相同。除非 leader 不再合法，有节点跳出来成为 candidate， 既然有新的 candida 跳出来， leader就不能成为下一个 candidate了， 否则就会出现多个 candidate 打架的场面， 你不服我，我也不服你，大家耗着时间选不出来。

鲁棒性保障

所谓 鲁棒性，就是确保即使一小部分(不过半)的节点挂了(包括leader挂了的情况)以后，剩余的节点依旧可以选出合法的 leader来(某些term内可能存在选不出来，但长期来看必然选得出来)。 raft 算法主要通过以下多种方式实现:

超时选举

上面说过 leader的维持需要大多数节点的投票，如果leader心跳过程中没有收到超过半数的节点的同意，那么leader失去合法性。 如果其他节点很长一段时间没有收到leader的心跳的，那么它就会变成 candidate请求大家投票，成为新一个 term的 leader。为了记录有多久没有收到合法leader的心跳，此处应该有一个 timer, 如果 timer 触发了， 则说明很久都没有leader了，此时应该立刻成为 candidate 选主。

事实上这个 timer 不仅仅是记录有多久没有收到 leader 心跳的意义。它应该更通用，应该用来看看过了多久时间是不是应该进行选主了。 如此一来。这个 timer 还可以在以下三个场景都应该被置零

一个 term 内， 节点只能投票个一个 candidate

上面说过 term的意义是表示节点自己的地位。为了避免一个节点在一个 term 内反复投票，造成所有 candidate都获得同样的选票，raft 规定了一个 term 内只能投一张选票。

随机化的 超时选举

试想一下在某个时刻，leader挂掉了，每一个节点都过了300mS没有收到心跳，于是一起term+1，一起变成candidate，一起发起投票，那么将会出现非常混乱的局面，很有大家都没有收到超过半数的投票，从而选不出leader。为了避免大量节点在短时间内同时触发超时选举，所以超时选举的时间应该随机化。

心跳的间隔应该 len(rf.peers)/2 && rf.role == Candidate {
rf.role = Leader
rf.voteFor = -1
rf.mu.Unlock()
go rf.HearBeat()
return
}
rf.mu.Unlock()
} else if reply.Term > rf.term { // if find other peer's term greater than me, become follower immediately
rf.role = Follower
rf.term = reply.Term
rf.voteFor = -1
rf.mu.Unlock()
return
} else {
rf.mu.Unlock()
}

}(i)

}

}

RequestVote 作为响应投票请求的函数, 逻辑也非常简单。只有在 请求节点的 term 大于自己的 term 或者 term 相等且没有投过票时才会投票(重置超时选主 timer，切换角色，标记投票给谁)，否则拒绝投票。

func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
   // Your code here (2A, 2B).

   rf.mu.Lock()
   if args.Term > rf.term || (args.Term == rf.term && rf.voteFor == -1) {
      rf.role = Follower
      rf.term = args.Term
      rf.voteFor = args.CandidateId
      rf.electionTimer = time.NewTimer(rf.randomTimeout())
      reply.VoteGranted = true
      reply.Term = rf.term
      rf.mu.Unlock()
      return
   } else {
      reply.VoteGranted = false
      reply.Term = rf.term
      rf.mu.Unlock()
      return
   }

}

发送心跳

HeartBeat 函数作为发送心跳的主逻辑，一进来就对 节点角色进行判断，若不为 leader 则立即退出。随后重置 心跳 timer, 向所有节点发送心跳。一旦有节点的 term 更大，则立即让贤变成 follower。特别的是，用了一个 heartBeatNoResp 来记录多少节点没有响应，如果超半数节点没有响应，则应该立即退出 leader。这里必须用 waitGroup 进行等候，否则则可能go routine 因为网络被阻塞了而来不及结束，而 HearBeat 却早早结束了，导致非法的leader没有让出位置。

func (rf *Raft) HearBeat() {

   for !rf.killed() {
      // once the peer is dead or it's not leader, the peer will stop sending heartbeat to others
      rf.mu.Lock()
      if rf.role != Leader {
         rf.mu.Unlock()
         return
      }
      rf.heartbeatTimer.Reset(rf.heartBeatInterval)
      args := AppendEntriesArgs{Term: rf.me}

      rf.mu.Unlock()

      wg := sync.WaitGroup{}
      hearBeatNoResp := 0

      // sending heartbeat to other peers
      for i := 0; i  rf.term {
               rf.term = reply.Term
               rf.role = Follower
               rf.voteFor = -1
            }
            rf.mu.Unlock()
         }(i)

      }

      wg.Wait()
      rf.mu.Lock()
      if hearBeatNoResp > len(rf.peers)/2 && rf.role == Leader {
         rf.role = Follower
         rf.voteFor = -1
         rf.mu.Unlock()
         return
      }
      rf.mu.Unlock()
   }
}

AppendEntries 作为响应leader心跳的函数会对 leader合法性进行校验,若term更小则不会更新自己的选主超时 timer，也就是不接受此次心跳。同时也会把自己的term返回回去，若leader发现别的节点term更大则会退出leader。

func (rf *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {

   rf.mu.Lock()
   reply.Term = rf.term
   // only update my election timer when it's a valid leader
   if args.Term >= rf.term {
      rf.electionTimer = time.NewTimer(rf.randomTimeout())
   }
   rf.mu.Unlock()
}
 

测试函数解读

lab2A 有三个测试用例, 全部位于 6.824/src/raft/test_test.go 中， 分别是:

在6.824/src/raft/目录下运行以下命令就能测试选主了

 go test -run 2A

踩过的坑

目前为止，已经完全可以实现lab2a要求，回想我实现起来踩过不少的坑，一些踩坑经验和 debug 经验分享给大家:

巨人的肩膀