顺序：Lab1 MapReduce / Lab2 KV Server / Lab3 Raft / Lab4 KV over Raft / Lab5 Sharded KV
Lab2 的核心：Client 请求 → Server 去重检查 → 执行/返回缓存 → Client 确认清理。
一句话总结
Lab2 在单个服务器上实现一个 KV 存储，核心挑战是在不可靠网络下保证每个请求最多执行一次（at-most-once）。
从 Lab1 到 Lab2：解决什么新问题？
Lab1 的 MapReduce 是无状态计算——Worker 处理完就结束，结果写文件，没有”正在服务”的概念。Lab2 开始进入有状态服务的世界：Server 持续运行，维护 KV 数据，Client 随时来读写。新的挑战：网络可能丢消息，同一个请求可能被执行多次。
为什么要做这个
网络是不可靠的。Client 发了一个 Append("balance", "+100") 请求：
- Server 执行了，回复丢了 → Client 重试 → 余额多加了 100！
- 这就是”exactly-once”问题。
Lab2 教你如何用请求去重解决这个问题，这个模式会贯穿后面所有 Lab。
核心问题：重复请求
1
2
3
4
5
6
| Client Server
│── Put("x", "1") ────→ │ ✓ 执行，x="1"
│ │
│←── OK ─────────────── │ ← 这个回复丢了！
│ │
│── Put("x", "1") ────→ │ ← Client 重试，Server 怎么知道这是重复的？
|
如果 Server 不做任何处理，第二次请求会被当作新请求执行。对于 Put 还好（幂等），但对于 Append 就会重复追加。
解决方案：去重表 + Finish 确认
每个请求带一个全局唯一的 ID。Server 维护一张表记录已处理的请求：
1
2
3
4
5
| type KVServer struct {
mu sync.Mutex
data map[string]string
request map[int64]string
}
|
处理流程（以 Append 为例）：
1
2
3
4
5
6
7
8
9
10
11
12
| func (kv *KVServer) Append(args *PutAppendArgs, reply *PutAppendReply) {
kv.mu.Lock()
defer kv.mu.Unlock()
if _, ok := kv.request[args.Id]; ok {
reply.Value = kv.request[args.Id]
return
}
oldValue := kv.data[args.Key]
kv.data[args.Key] = oldValue + args.Value
kv.request[args.Id] = oldValue
reply.Value = oldValue
}
|
但是——内存会爆炸
去重表会无限增长！每个成功的请求都缓存着。解决方案是 Client 确认机制（Finish RPC）：
1
2
3
4
5
6
7
8
9
10
11
12
|
func (ck *Clerk) PutAppend(key string, value string, op string) string {
args := PutAppendArgs{Key: key, Value: value, Id: atomic.AddInt64(&id, 1)}
reply := PutAppendReply{}
for !ck.server.Call("KVServer."+op, &args, &reply) {}
Finishreply := PutAppendReply{}
for !ck.server.Call("KVServer.Finish", &args, &Finishreply) {}
return reply.Value
}
|
1
2
3
4
5
6
|
func (kv *KVServer) Finish(args *PutAppendArgs, reply *PutAppendReply) {
kv.mu.Lock()
defer kv.mu.Unlock()
delete(kv.request, args.Id)
}
|
三种操作的处理
| 操作 |
幂等？ |
需要去重？ |
说明 |
| Get |
是 |
否 |
读操作天然幂等，重复执行无影响 |
| Put |
是 |
否（但实际做了） |
覆盖写，结果相同 |
| Append |
否 |
是 |
追加写，重复执行会多加一次 |
严格来说只有 Append 需要去重，但实现中对 Put/Append 统一去重简化了逻辑。
Client 的设计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| var id int64
func (ck *Clerk) PutAppend(key string, value string, op string) string {
args := PutAppendArgs{
Key: key,
Value: value,
Id: atomic.AddInt64(&id, 1),
}
reply := PutAppendReply{}
for !ck.server.Call("KVServer."+op, &args, &reply) {
}
Finishreply := PutAppendReply{}
for !ck.server.Call("KVServer.Finish", &args, &Finishreply) {}
return reply.Value
}
|
关键点：
- 全局 atomic 自增保证 ID 唯一
- 同一个请求的所有重试使用相同的 ID，Server 识别重复
- 成功后 Finish 清除缓存，防止内存无限增长
时序图：完整的请求生命周期
1
2
3
4
5
6
7
8
9
| Client Server
│ │
│── PutAppend(id=42) ────────→ │ 查 request[42]：不存在
│ │ 执行 Append，缓存 request[42]=result
│←── OK(result) ──────────── │
│ │
│── Finish(id=42) ──────────→ │ delete(request[42])
│←── OK ─────────────────── │
│ │
|
如果第一步的回复丢了：
1
2
3
4
5
6
7
8
9
| Client Server
│ │
│── PutAppend(id=42) ────────→ │ 执行，缓存 request[42]=result
│←── OK(result) ──── ✗ 丢了 │
│ │
│── PutAppend(id=42) ────────→ │ 查 request[42]：已存在！
│←── result（缓存值）──────── │ 不重复执行
│ │
│── Finish(id=42) ──────────→ │ 清除缓存
|
这个 Lab 建立的思维模式
- 不可靠网络是常态：任何 RPC 都可能丢失、延迟、重复
- 去重是幂等的基础：非幂等操作必须有去重机制
- Client 和 Server 要协作：只靠一方无法解决问题
去重机制的演进：Lab2 vs Lab4/5
Lab2 的去重方式（全局 ID + Finish 清理）和后面 Lab 的方式不同，理解这个演进很重要：
|
Lab2 |
Lab4/5 |
| ID 方式 |
全局 atomic 自增 |
ClientId + 每 Client 单调递增 RequestId |
| 内存管理 |
Finish RPC 显式清理 |
只保留每个 Client 的最大 RequestId，自动覆盖 |
| 为什么变了 |
单机可以靠 Finish |
分布式下 Finish 也可能丢失，且需要过 Raft |
Lab4/5 的方案更优雅：每个 Client 的 RequestId 单调递增，Server 只需记住 max(RequestId)，小于它的请求都是重复的。不需要额外的 Finish 清理步骤，天然 bounded。
1
2
|
LastRequestMap[clientId] = max(LastRequestMap[clientId], requestId)
|