跳转至

lab2A: Leader Election

​image​

需要实现的部分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func:
    defined:
        Make() {}
        Raft.GetState() {}
        Raft.RequestVote() {}
        Raft.ticker() {}

    undefined:
        Raft.startElection() {}
        Raft.collectVotes() {}
        Raft.getGrantedVotes() {}
        Raft.sendHeartBeats() {}
        Raft.AppendEntries() {}
        Raft.isHeartBeatTimeOut() bool {}
        getRandElectionTimeOut() time.Duration {}

struct:
    Raft{}
    RequestVoteArgs{}
    RequestVoteReply{}
    AppendEntriesArgs{}
    AppendEntriesReply{}

流程

​image​

Follower

  • 响应来自Candidate和Leader的RPC请求
  • 如果等待时间超过选举超时的情况下，没有收到Leader的心跳发送，或者投票给某个候选人，进入投票Candidate状态

Candidate

从Follower进入到Candidate状态：

  • 增加当前的Term
  • 给自己投票
  • 重新设置选举时间
  • 发送RPC，向其他的服务器请求投票

如果获得大量选票，成为Leader

如果收到新Leader的AppendEntries RPC，转换为Follower

如果选举超时，发起新的一轮选举

Leader

成为Leader后，每隔一段heartBeatTimeOut​时间向其Follower发送一个心跳（AppendEntriesArgs{}​包），告知仍然存活

由多数Candidate选举产生

注意事项

  1. 关于选举间隔时间：建议 150 ~ 300 之间

    • 设置太高会浪费空闲时间
    • 设置太低又容易发生活锁，也存在一种情况就是leader选举出来了，但是又收到term更高的vote rp请求。

  2. 当选leader，应该尽快发送心跳rpc，防止follower过期

  3. leader 发送心跳的频率 ， 建议在100ms以上一次，官方建议1s不超过10次
  4. 一把大锁保护好状态，RPC期间释放锁，RPC结束后注意状态二次判定
  5. request/response都要先判断term > currentTerm，转换follower
  6. 一个currentTerm只能voteFor其他节点1次
  7. 注意candidates请求vote的时间随机性
  8. 注意requestVote得到大多数投票后立即结束等待剩余RPC
  9. 注意成为leader后尽快appendEntries心跳，否则其他节点又会成为candidates
  10. 注意几个刷新选举超时时间的逻辑点
  11. 初始化的currentTerm为0

实现

定义常量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
const (
    Follower  = 1
    Candidate = 2
    Leader    = 3

    ElectionSleepTime = 30 * time.Millisecond  // 选举睡眠时间 ms
    HeartBeatSendTime = 110 * time.Millisecond // 心跳包发送时间 ms

    ElectionTimeOutMin = 150 // 选举超时最小时间 ms
    ElectionTimeOutMax = 300 // 选举超时最大时间 ms
)

Struct

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
type Raft struct {
    mu        sync.Mutex          // Lock to protect shared access to this peer's state
    peers     []*labrpc.ClientEnd // RPC end points of all peers
    persister *Persister          // Object to hold this peer's persisted state
    me        int                 // this peer's index into peers[]
    dead      int32               // set by Kill()

    // 2A START
    currentTerm      int       // 当前任期
    votedFor         int       // 投票给谁
    peersVoteGranted []bool    // 已获得的选票
    role             int       // 角色 follower, candidate, leader
    heartBeatTimeOut time.Time // 上一次收到心跳包的时间+随即选举超时时间（在收到心跳包后再随机一个）
    // 2A End
}

type RequestVoteArgs struct {
    // 2A Start
    CandidateTerm  int // 候选人Term
    CandidateIndex int // 候选人Index
    // 2A End
}

type RequestVoteReply struct {
    // 2A Start
    FollowerTerm int  // 当前任期号，以便候选人更新自己的任期号
    VotGranted   bool // 候选人是否被投票
    // 2A END
}

// AppendEntriesArgs 心跳/追加包
type AppendEntriesArgs struct {
    LeaderTerm  int // leader's term
    LeaderIndex int // leader's index
}

type AppendEntriesReply struct {
    FollowerTerm int  // follower的term，用来更新leader自己的term
    Success      bool // 是否成功
}

推荐阅读

[1] [MIT6.824 lab2] Raft-Leader election 代码实现 & 踩坑记录​

[2] 运行 3000 次都不出错的 MIT 6.824 Raft 实验​

‍

回到页面顶部