MIT 6.5840 分布式系统 Lab 3: Raft

Leader Election 领导者选举

Raft使用心跳检测机制触发领导者选举，当服务器启动时，他是追随者，只要持续收到来自领导者或候选者的有效的RPC(RequestVote, AppendEntries)调用，服务器就一直保持为追随者。领导者定期向追随者发送心跳包(不带日志的AppendEentries)以保持权威。追随者在选举超时的一段时间内没有收到任何通信，他会假设现在没有领导者，把自己变为候选者，并开始选举新的领导者，获得大多数（超过半数）投票的候选者会变成新的领导者。

思路：

• 服务器有3种状态：追随者、候选者、领导者
• 服务器启动时是追随者，在收到有效的RPC调用时重置领导者超时计时器，收到RequestVote时也要重置计时器，避免和现有的候选者竞争
• 领导者超时计时器超时后，服务器把自己变为候选者，任期+1，开始选举新的领导者；在选举时也要设定一个选举超时计时器，避免长时间等待ReqeustVote的回信，选举超时后，再随机等待一段时间，开始下一轮新的选举
• 服务器成为领导者后，立刻开始定时发送心跳包给其他服务器，在定时发送心跳包时不要等待上一个心跳包完成之后再发送下一个心跳包，避免因网络波动导致心跳包发送时间过长，进而导致领导者超时计时器超时

代码：https://github.com/tlxxzj/6.5840-Distributed-Systems/tree/lab3A-raft-leader-election/src/raft

Log Replication 日志复制

领导者被选举出来后，开始处理来自客户端的请求，每个请求都包含一个将被状态机执行的命令。领导者将命令追加到日志中，并通过AppendEntries RPC调用把日志复制到追随者，当日志被安全复制之后，领导者执行命令，返回执行结果给客户端。

思路：

• Leader为每个Follower开启一个Worker线程，负责发送心跳包和同步日志
• Leader根据nextIndex发送AppendEntries, 成功：更新nextIndex, matchIndex, commitIndex, 失败：回退nextIndex，重试
• AppendEntries成功：对matchIndex顺序排序，对于X = (N – 1) / 2，Y = matchIndex[X]，有超过半数的matchIndex[i] >= matchIndex[X]，如果Y > commitIndex 并且 log[Y].Term = CurrentTerm，更新Y为新的commitIndex，触发Apply线程执行命令
• Leader为每个Follower开启一个Worker线程，负责Apply执行命令，Apply线程执行时，把未执行的日志，即log[appliedIndex+1: commitIndex+1]复制一份，再顺序执行命令，复制日志后可释放锁，避免Apply线程长期占用锁