MIT 6.5840 (Spring, 2024) – Lab 2: Key/Value Server
👨💻 Charles
🔗 实验手册：6.5840 Lab 2: Key/Value Server
✍️ 本系列前文
该 lab 需要实现一个简单的 K/V 存储系统，由于还没涉及分布式，且底层存储可以直接用 map ，写起来难度不大。貌似也是 6.5840 中唯一一个难度标注为 easy 的 lab 了，直接上代码吧。
完整代码见 github
common.go
// Put or Append
type PutAppendArgs struct {
Key string
Value string
// You'll have to add definitions here.
// Field names must start with capital letters,
// otherwise RPC will break.
ClerkID int64
RequestID int64
}
type PutAppendReply struct {
Value string
}
type GetArgs struct {
Key string
// You'll have to add definitions here.
}
type GetReply struct {
Value string
}
非常简单，唯一要注意的就是为了“客户端请求去重”， PutAppendArgs 需要携带一下客户端 ID 和这次请求的 ID（唯一）：
在不可靠网络中，客户端可能会多次重发相同的 RPC 请求。如果服务器简单处理，多次处理同一个请求会导致重复操作 —— 例如一个写操作被执行多次，导致数据不一致或者越界。为了避免这些问题，服务器需做请求去重并返回幂等的结果。因此这里采用一种常见策略：
- 客户端维护一个单调递增的请求 ID（
RequestID），在每次请求 RPC 中带上。 - 服务器保存每个客户端最近处理过的
lastRequestID和对应的lastReply。 - 当它收到一个请求时，如果发现
RequestID=lastRequestID（即重复请求），它就直接返回已保存的lastReply，而不重复执行。
由于
RequestID是单调递增，且只有客户端确认收到该请求的回复后，才会让RequestID加一，所以不会出现client's RequestID < server's lastReuqestID[client]的情况。
详细实现见下面的 server.go 。
server.go
type KVServer struct {
mu sync.Mutex
// Your definitions here.
db map[string]string
lastRequest map[int64]int64 // clerkID -> its last requestID
lastReply map[int64]string // clerkID -> its last reply value
}
func (kv *KVServer) Get(args *GetArgs, reply *GetReply) {
// Your code here.
kv.mu.Lock()
defer kv.mu.Unlock()
reply.Value = kv.db[args.Key]
}
func (kv *KVServer) Put(args *PutAppendArgs, reply *PutAppendReply) {
// Your code here.
kv.mu.Lock()
defer kv.mu.Unlock()
if kv.lastRequest[args.ClerkID] == args.RequestID {
return
}
kv.db[args.Key] = args.Value
reply.Value = args.Value
}
func (kv *KVServer) Append(args *PutAppendArgs, reply *PutAppendReply) {
// Your code here.
kv.mu.Lock()
defer kv.mu.Unlock()
if kv.lastRequest[args.ClerkID] == args.RequestID {
reply.Value = kv.lastReply[args.ClerkID]
return
}
oldValue := kv.db[args.Key]
kv.db[args.Key] = oldValue + args.Value
reply.Value = oldValue
kv.lastRequest[args.ClerkID] = args.RequestID
kv.lastReply[args.ClerkID] = oldValue
}
func StartKVServer() *KVServer {
kv := new(KVServer)
// You may need initialization code here.
kv.db = make(map[string]string)
kv.lastRequest = make(map[int64]int64)
kv.lastReply = make(map[int64]string)
return kv
}
client.go
type Clerk struct {
server *labrpc.ClientEnd
// You will have to modify this struct.
id int64
requestID int64
}
func nrand() int64 {
max := big.NewInt(int64(1) << 62)
bigx, _ := rand.Int(rand.Reader, max)
x := bigx.Int64()
return x
}
func MakeClerk(server *labrpc.ClientEnd) *Clerk {
ck := new(Clerk)
ck.server = server
// You'll have to add code here.
ck.id = nrand()
return ck
}
func (ck *Clerk) Get(key string) string {
// You will have to modify this function.
args := GetArgs{Key: key}
reply := GetReply{}
try := 0
success := false
for !success {
try++
success = ck.server.Call("KVServer.Get", &args, &reply)
DPrintf("CK[%d] Get[%s], %v; try time: %d", ck.id, key, success, try)
}
DPrintf("CK[%d] Get[%s] = '%s'", ck.id, key, reply.Value)
return reply.Value
}
func (ck *Clerk) PutAppend(key string, value string, op string) string {
// You will have to modify this function.
args := PutAppendArgs{
Key: key,
Value: value,
ClerkID: ck.id,
RequestID: atomic.AddInt64(&ck.requestID, 1),
}
reply := PutAppendReply{}
success := false
try := 0
for !success {
try++
success = ck.server.Call("KVServer."+op, &args, &reply)
DPrintf("CK[%d] %s[%s]='%s', %v\ntry time: %d\nrequestID: %d",
ck.id, op, key, value, success, try, args.RequestID)
}
return reply.Value
}
func (ck *Clerk) Put(key string, value string) {
ck.PutAppend(key, value, "Put")
}
// Append value to key's value and return that value
func (ck *Clerk) Append(key string, value string) string {
return ck.PutAppend(key, value, "Append")
}
实验结果
用测试脚本跑 2000 轮（打开数据竞态检测），全部通过：
