Tinykv Project3 MultiRaft

2021-09-16

在 Project2 中，我们已经基于Raft构建了一个高可用的键值服务器，但是我们假设的是每个store中都只有一个Region，也就是服务器中总共只有一个raft group，这样的话每个写操作都需要访问同一个Leader，等待命令被提交并串行执行，这样虽然保证了各个节点的数据一致性，但却严重影响了执行效率，无法提供高性能的服务。

在 Project3 中，我们要实现一个带有平衡调度器的多 Region 键值服务器，每个 Region 代表键在某一个范围内的数据。新的结构如下图所示，具体的操作请求会被判断位于哪一个Region，从而访问对应Raft group中的Leader。这样使得对不同Region的操作可以并发执行，提高了执行效率。

该Project包含了三个部分，分别是：

在 Raft 算法中实现成员变更和领导人变更
实现raftstore中的配置更改和region分裂
引进调度器

Part A

在这一部分需要实现成员变更和领导人变更的基础raft算法。成员变更，也就是配置更改，可以为raft集群增加或者移除节点；领导人变更用于将Leader转移给其他节点，在调度中很有用。

领导人变更

要实现领导人变更，引入了 MsgTransferLeader 和 MsgTimeoutNow 两类消息类型，在进行领导人转化时，需要在当前领导人上调用 raft.Raft.Step 处理 MsgTransferLeader 消息，而消息中的 from 就是需要转移的目标节点。为了保证能够成功转移领导人并保证数据的一致性不被破坏，当前领导人需要检查目标节点是否有最新的日志，是否符合成为领导人的条件。如果不符合条件，当前领导人会停止接收新的 proposal 请求，并向目标节点发送 MsgAppend，使其日志达到同步的最新状态。符合要求后，当前领导人会向目标节点发送 MsgTimeoutNow 消息，目标节点在收到该消息后会使用更高的 Term 立刻开启一个新的选举，这样将有很大机会成为新的领导人节点。

对 MsgTransferLeader 消息的处理函数如下，需要判断目标节点状态，日志信息等。

func (r *Raft) handleTransferLeader(m pb.Message) {
	// already leader
	if m.From == r.id {
		return
	}
	// under transfering
	if r.leadTransferee != None && r.leadTransferee == m.From {
		return
	}
	// The transferee dosen't exist
	if _, ok := r.Prs[m.From]; !ok {
		return
	}
	r.leadTransferee = m.From
	r.transferElapsed = 0
	// check transferee's log
	if r.Prs[m.From].Match == r.RaftLog.LastIndex() {
		r.sendTimeoutNow(m.From)
	} else {
		r.sendAppend(m.From)
	}
}

而对于 MsgTimeoutNow 消息，直接调用 requestElection 发起选举即可。当领导人变更正在进行，即 leadTransferee 不为空时，不处理 MsgPropose 消息。

成员配置变更

在该系统中没有像 Raft 论文中那样实现一次性添加或移除任意多个节点，而是每次增加或删除一个节点，这样实现起来更加简单。成员变更开始于调用Leader的 raft.RawNode.ProposeConfChange，它会 propose 一个类型为 EntryConfChange 的实体，将 pb.ConfChange 写入实体的 data，当该实体被提交后，通过 RawNode.ApplyConfChange 将该配置应用，然后可以通过 raft.Raft.addNode 和 raft.Raft.removeNode 执行对应的增加或删除节点的操作。

增加或删除节点的代码如下所示：

// addNode add a new node to raft group
func (r *Raft) addNode(id uint64) {
	// Your Code Here (3A).
	if _, ok := r.Prs[id]; ok {
		r.Prs[id] = &Progress{Next:  1}
	}
	r.PendingConfIndex = None
}

// removeNode remove a node from raft group
func (r *Raft) removeNode(id uint64) {
	// Your Code Here (3A).
	if _, ok := r.Prs[id]; ok {
		delete(r.Prs, id)
		if r.State == StateLeader {
			r.detectCommit()
		}
	}
	r.PendingConfIndex = None
}