6.5840 Lab4

Misc

Go

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 避免手动的锁操作。
• 如何处理冗余的请求？（下面将 Get 请求称为读请求，将 Put/Append 请求称为写请求）
  • 策略 1：每个请求必须附加上一个 UUID 进行标识。节点缓存的 key 是 UUID，value 是这个请求的返回值。如果收到了一个相同 UUID 的请求，将直接返回缓存中的返回值。那么如何清理缓存？目前采用的策略是，客户端确认收到请求的响应后，发送一个特殊的 Get 请求示意服务器删除对应的缓存。不过这种策略不是最佳的，会显著增加网络负载。
  • 策略 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

Result

PartA

D\C\6\s\kvraft [master] [?⇡]
17:08 HernandoPC ExApricity » go test -run 4A
Test: one client (4A) ...
labgob warning: Decoding into a non-default variable/field Err may not work
  ... Passed --  15.2  5 11330  476
Test: ops complete fast enough (4A) ...
  ... Passed --  33.0  3 12379    0
Test: many clients (4A) ...
  ... Passed --  15.9  5 17956  483
Test: unreliable net, many clients (4A) ...
  ... Passed --  16.3  5  5106  424
Test: concurrent append to same key, unreliable (4A) ...
  ... Passed --   2.8  3   416   52
Test: progress in majority (4A) ...
  ... Passed --   0.5  5   111    2
Test: no progress in minority (4A) ...
  ... Passed --   1.1  5   290    3
Test: completion after heal (4A) ...
  ... Passed --   1.0  5   154    3
Test: partitions, one client (4A) ...
  ... Passed --  22.7  5 24807  408
Test: partitions, many clients (4A) ...
  ... Passed --  23.0  5 58421  453
Test: restarts, one client (4A) ...
  ... Passed --  19.3  5 27362  470
Test: restarts, many clients (4A) ...
  ... Passed --  20.6  5 26981  378
Test: unreliable net, restarts, many clients (4A) ...
  ... Passed --  22.7  5  3676  206
Test: restarts, partitions, many clients (4A) ...
  ... Passed --  28.2  5 20945  272
Test: unreliable net, restarts, partitions, many clients (4A) ...
  ... Passed --  30.2  5  3875  143
Test: unreliable net, restarts, partitions, random keys, many clients (4A) ...
  ... Passed --  39.2  7  9502  165
PASS
ok      6.5840/kvraft   292.739s

PartB

Reflection