实验要求

直接看这个链接：https://pdos.csail.mit.edu/6.824/labs/lab-kvsrv.html

实现

本次实验较为简单，提一点即可：

为了正确处理 RPC 请求 丢失 或其它异常，服务端需要实现 Exactly Once，即对于写请求，应该 有且仅执行一次

实现方式比较简单，参考 Kafka 的实现方式

客户端生成一个随机 ID 作为 client_id，以及一个 epoch

服务端维护 client_id 与 epoch 的状态

如果某一次写请求，客户端提供的 epoch 小于等于服务端保存的该客户端的 epoch，那么服务端直接忽略请求

注意：

  1. 实验要求即使是过期的消息，也要返回执行结果，因此，服务端还需要维护 client_id 与 lastReply 的映射关系
  2. 实验要求服务端应该及时释放内存

Your scheme for duplicate detection should free server memory quickly, for example by having each RPC imply that the client has seen the reply for its previous RPC. It’s OK to assume that a client will make only one call into a Clerk at a time.

在做这个 lab 的时候，释放内存 这块卡了一会，最终的实现方式如下：

  • 仅当 client 发起一个 Append 请求，我们才校验 epoch（对于 Get 请求，直接返回最新的执行结果；对于 Put 请求，直接写即可）
  • 仅当 client 发起一个 Append 请求，我们才缓存 client_id 与 lastReply 的映射关系
  • 当 client 发起一个 Get/Put 请求，需要删除 client_id 与 lastReply 的映射关系

放一段核心代码感受一下：

func (kv *KVServer) do(req *Request) *Reply {
	reply := &Reply{
		status: FetchSuccess,
	}
	var err error

	// handle epoch status

	if req.reqType == AppendRequest && !kv.checkAndUpdateEpoch(req) {
		DPrintf("client_id: %v, cur epoch: %v, last: %v", req.clientID, req.epoch, kv.clientEpoch[req.clientID])
		if kv.lastReply[req.clientID] != nil {
			reply = kv.lastReply[req.clientID]
		}
		reply.status = FetchExpired
		return reply
	}
	// kv.lastReply[req.clientID] = nil

	switch req.reqType {
	case GetRequest:
		err = kv.get(req, reply)
	case PutRequest:
		err = kv.put(req, reply)
	case AppendRequest:
		err = kv.append(req, reply)
	default:
		log.Printf("Invalid Request Type: %v", req.reqType)
		reply.status = FetchFail
	}
	if err != nil {
		log.Printf("do failed, err: %v", err.Error())
		reply.status = FetchFail
	}

	if req.reqType == AppendRequest {
		kv.lastReply[req.clientID] = reply
	} else {
		// remove epoch status
		delete(kv.clientEpoch, req.clientID)
		delete(kv.lastReply, req.clientID)
	}
	return reply
}

正确性验证

注意：截止 2024.4.19，从 git://g.csail.mit.edu/6.5840-golabs-2024 6.5840 clone 的仓库，srv/kvsrv/test_test.go 的第 598 行为：

if m1 >= 3*MEM*N {

这个应该是一个 bug，要检验内存是否超出使用限制，应该将 m1 - m0，即终止内存占用与起始内存占用的差，与 limit，即 3*MEM*N 做比较

正确代码应该是：

if m1 >= m0+3*MEM*N {

修改之后，就能通过所有测试用例了：

image

参考资料