6.5840 Lab4
Task
本次实验中，需要在 Lab2 中实现的single server multiple clients 的 KV storage，和 Lab3 实现的 Raft 协议的基础上，构建一个mutiple servers multiple clients 的 KV storage，并且要能支持节点崩溃重启、快照等功能。数据库分区的功能将在 Lab5 进行实现。
本次实验需要修改 /src/kvraft 下的 client.go, server.go, common.go。
Implementation
PartA
-
服务器节点收到请求后，不是直接执行对应的操作，而是先把这个请求送往 Raft 层，即
kv.rf.Start(op)。待 Raft 层对这个 op 取得一致后（已发往大多数节点），当前服务器才能真正执行这个请求的操作。为此，需要开启一个协程applyTicker，不断轮询通道kv.applyCh，检查是否还有尚未应用的、已取得共识的命令。 -
一个重要的优化思路：client 应该维护上一次成功发送请求的 leader 的索引，下一次请求时优先发往这个节点，以减少不必要的轮询。
-
使用
sync.Map避免手动的锁操作。在 PartB 中不能直接将 sync.Map 直接序列化，因为它内部持有了锁。应该先将其中的内容拷贝到一个普通的 map 中，再序列化这个 map。
-
如何处理冗余的请求？（下面将 Get 请求称为读请求，将 Put/Append 请求称为写请求）
-
策略 1：每个请求必须附加上一个 UUID 进行标识。节点缓存的 key 是 UUID，value 是这个请求的返回值。如果收到了一个相同 UUID 的请求，将直接返回缓存中的返回值。那么如何清理缓存？目前采用的策略是，客户端确认收到请求的响应后，发送一个特殊的 Get 请求示意服务器删除对应的缓存。不过这种策略不是最佳的，会增加网络负载。
这种策略可能导致 Snapshot 过大而不能通过 Part B 的一个测试用例。故最终采取了下面一种策略。
-
策略 2：每个请求再附上一个
<客户端 ID，请求序号 Seq>的二元组。节点缓存的 key 是这个二元组，value 是这个请求的返回值。对于每个发送过请求的客户端，服务器各为其维护一个lastSeq属性，代表最近一次处理的来自该客户端的请求的序号。当收到来自同一个客户端的、Seq <= lastSeq 的 Get 请求时，返回缓存中的返回值；当收到来自同一个客户端的、Seq <= lastSeq 的 Put/Append 请求时，将不对数据库进行任何处理，只是返回一个 OK 即可。那么如何清理缓存？当服务器节点收到来自同一个客户端的、Seq > lastSeq 的请求时，服务器可以确信，对于前面所有请求，这个客户端均已成功收到了响应，此时可以删除所有 seq <= lastSeq 的缓存，并更新 lastSeq = Seq。这种单调增计数器的思想广泛见于多种分布式系统的设计中。为了支持上述算法，必须在MakeClerk中初始化客户端的 ID，可以复用 UUID 函数得到一个全局唯一的 ID。
-
PartB
-
根据实验要求，
maxraftstate应该与persister.RaftStateSize()比较。其中 raftstate 包含：1
2
3
4
5
6
7
8
9
10
11
12
13
14func (rf *Raft) persist() {
// Your code here (PartC).
w := new(bytes.Buffer)
e := labgob.NewEncoder(w)
// the following are raftstate
e.Encode(rf.CurrentTerm)
e.Encode(rf.VotedFor)
e.Encode(rf.Entries)
e.Encode(rf.LastIncludedIndex)
e.Encode(rf.LastIncludedTerm)
raftstate := w.Bytes()
// PartD, save SnapShots
rf.persister.Save(raftstate, rf.Snapshots)
}其中的
rf.Entries是一个数组，它的大小随着运行时间而膨胀，这就解释了为何要定期检测 raftstate 的大小去调用rf.Snapshot()。 -
k/v server 层为 Raft 层提供的 snapshot 应包含哪些信息？
rf.Snapshot的函数签名如下：1
func (rf *Raft) Snapshot(index int, snapshot []byte)其中，
index必须是在 kv server 中已经 apply 的最大的那条 CommandIndex。snapshot是 kv server 中的持久化状态。 -
本节需要实现三个功能
- 如果一个 applyMsg 的类型是 Snapshot，那么 kvserver 应该读取持久化状态并恢复
- 在 apply 一个 Command 之后，kvserver 应该检查是否应该 Snapshot
- kvserver 重启时，应该读取 Snapshot 并修改自身的状态
Result
PartA
1 | |
PartB
1 | |