MIT 6824 Lab 2A总结

1 minute read

1. 介绍

这篇是6824的lab 2A部分，目的是实现Raft paper中的第一部分leader election。虽然课程网站上的标记只是moderate，但是做起来感觉比lab 1 mapreduce要复杂不少，大概是lab 1中的mapreduce其实并没有多少多机通信的部分，比较容易debug，而这部分涉及到挺多比较复杂的通信，相对复杂一些

2. 结构定义

首先我们来看各个数据结构的定义，分成两个部分，第一部分是Raft本身的定义，第二部分是RPC的定义

2.1. Raft

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()

	// Your data here (2A, 2B, 2C).
	// Look at the paper's Figure 2 for a description of what
	// state a Raft server must maintain.

	// latest term server has been
	currentTerm int

	// candidateId that received vote in current term
	votedFor int

	// logs
	log []LogEntry

	// last heart beat time
	lastHeartBeatTime time.Time

	// state of current Raft
	state int

	// timer used for election
	electionTimer *time.Timer

	// timer used for heart beat
	heartbeatTimer *time.Timer
}

除了给出的fields之外，新添加的fields有

currentTerm: 当前term
state: 当前的状态，只能是LEADER, FOLLOWER, CANDIDATE中的一个
log: 存储的logs
votedFor: 在election中的投票对象，-1表示没有任何对象
electionTimer: 使用Timer记录是否遇到了election timeout
heartbeatTimer：使用Timer记录是否需要发送heartbeat给follower，这个只有LEADER适用

2.2. RPC

2.2.1. RequestVoteRPC

type RequestVoteArgs struct {
	// Your data here (2A, 2B).

	// candidate's term
	Term int

	// candidate requesting vote
	CandidateId int

	// index of candidate's last log entry
	LastLogIndex int

	// term of candidate's last log entry
	LastLogTerm int
}

//
// example RequestVote RPC reply structure.
// field names must start with capital letters!
//
type RequestVoteReply struct {
	// Your data here (2A).

	// currentTerm, for candidate to update itself
	Term int

	// true means candidate received vote
	VoteGranted bool
}

基本和raft paper中的定义一致

2.2.2. AppendEntries

//
// AppendEntries RPC arguments structure
//
type AppendEntriesArgs struct {
	// learder's term
	Term int

	// leader id
	LeaderId int

	// log entries to store
	Entries []LogEntry
}

//
// AppendEntries RPC reply structure
//
type AppendEntriesReply struct {
	// current term, for leader to update itself
	Term int

	// true if follower contained entry matching prevLogIndex and prevLogTerm
	Success bool
}

在leader election过程中，AppendEntries被当作heartbeat来发送，只不过没有log entries，在request中定义了当前的term，leaderId，而在reply中则提供了follower自己的term，这个term有可能比leader发来的还要高

3. 实现

3.1. Background Task

在Raft开始之后，我们马上会启动一个goroutine，这个goroutine主要等待两件事情，第一个是election timeout，如果发现election timeout则说明可能需要发起新一轮的leader election，在自己不是leader的情况下发起RequestVote，否则会无端引起term增加，给系统带来不必要的开销；第二个是heartbeat timeout，在遇到heartbeat timeout之后如果自己是leader，向follower发送heartbeat并充值heartbeat timer

我们来看election timeout之后要做的事情。首先判断自己是不是leader，如果不是则增加term更改自身状态为CANDIDATE，向其他各个Raft node发送RequestVote请求，注意发送RequestVote请求时要并行发送，这里可以用goroutine方便实现。接下来，每次在goroutine里收到回复的时候都要检查是否发起RequestVote时的term与reply中的term一致以及自己是否仍然处于CANDIDATE状态，因为很有可能某些reply的时间过长，等接收到的时候已经过了很久，这时候不应该让它再影响当前状态，所以要加上这个检查

这时我们就可以继续查看reply中的状态，如果reply中的term高于自己的term，那么说明其他Raft node竞选成功，将自己设置为FOLLOWER状态，更新currentTerm为最新term并且讲votedFor清空。另一方面如果发现voteGranted则增加计数器，若已取得majority共识，则更改自己为LEADER，马上向其他Raft node发送heartbeat宣示主权，并且重置hearbeatTimer

上面描述的是收到election timeout之后要做的事情，收到heartbeat timeout之后要做的事情比较简单，如果自己是LEADER则向各个Raft node发送heartbeat并重置heartbeatTimer，否则什么都不需要做

3.2. RequestVote

3.1.描述了大致流程，在这部分和接下来的部分描述RequestVote和AppendEntries handler的实现。RequestVote基本按照Raft paper描述的步骤实现，如果request的term比自己小或者自己已经vote了其他Raft node，则设置voteGranted为false并返回；如果request的term更大则将自己设置为FOLLOWER，更新currentTerm和votedFor；最后检查log是否up-to-date，若是则表明自己可以vote candidate，重置electionTimer

3.3. AppendEntries

AppendEntries在leader election中被当作heartbeat来使用，所以实现相对简单。若自己的term大于request，则在reply中跟新自己的term告知对方有更高的term，否则将自己设置为FOLLOWER并重置electionTimer

4. 细节

这个实验有很多细节需要注意，一不小心就会出错，除了上面黑体字提到的之外，还有一个我debug了好久的错误。在2A的第一个test case中，我总会遇到warning: term changed even though there were no failures，意思是在网络正常的情况下却进行了多次leader election，打印了很多log之后发现是因为在SendHeartbeat函数中，会先加锁，获取当前term与leader之后再释放锁，之后构建空AppendEntries并且向各个Raft node发送。而在实际运行中，这里的加锁经常会导致发送heartbeat较慢，因此其他的Raft node会首先election timeout接着发送RequestVote，导致term增长，解决方法就是讲term和leaderId放到SendHeartbeat参数中，这样只需要在调用SendHeartbeat时加锁，而不需要在实际发送heartbeat时加锁

Shen Zhu