MIT6.824 kv-raft

使用lab2构建的raft库，提供一个fault-tolerance的key-value服务

完整代码：link

lab3A

Client轮询发送RPC请求，直到找到是leader的server。

Server接受Client的请求，构造Op日志，交给raft节点，raft节点集群之间达成共识后，每个raft节点通过applyCh告诉相应的server，server将日志的命令应用到状态机上，leader server将结果返回给client。

难点

当存在多个client同时请求的时候，有多个日志被提交，leader如何定位状态机的应用结果返回给哪个client？解决：用每个命令提交时的log index作为索引，映射到一个返回结果的通道，对于applyCh返回来的日志，根据日志index确定要通知的client。

如何实现线性化语义？解决：给每一个请求一个UniqueID（Increasing），server保存记录目前已经被应用到状态机最大的请求ID，防止请求被多次应用（写请求）。对于读请求，总让client看到最新的状态。client发送RPC请求的时候，附带clientID和commandId，共同构成这个uniqueID。

需要注意的点

发送RPC的for循环中需要使用一个新的reply结构体，传递给rpc，否则还是之前的reply结果。

server中，只有leader需要在RPC的等待channel上发送返回response。

运行结果

$ go test -run 3A                                          
Test: one client (3A) ...
  ... Passed --  15.7  5   396   74
Test: many clients (3A) ...
  ... Passed --  18.1  5   765  365
Test: unreliable net, many clients (3A) ...
  ... Passed --  24.0  5   959  179
Test: concurrent append to same key, unreliable (3A) ...
  ... Passed --   6.4  3   150   52
Test: progress in majority (3A) ...
  ... Passed --   1.5  5    53    2
Test: no progress in minority (3A) ...
  ... Passed --   1.6  5    77    3
Test: completion after heal (3A) ...
  ... Passed --   1.2  5    41    3
Test: partitions, one client (3A) ...
  ... Passed --  24.1  5   621   46
Test: partitions, many clients (3A) ...
  ... Passed --  25.5  5  1019  220
Test: restarts, one client (3A) ...
labgob warning: Decoding into a non-default variable/field int may not work
  ... Passed --  22.9  5  1096   70
Test: restarts, many clients (3A) ...
  ... Passed --  25.0  5  1733  375
Test: unreliable net, restarts, many clients (3A) ...
  ... Passed --  30.1  5  2015  151
Test: restarts, partitions, many clients (3A) ...
  ... Passed --  31.9  5  1534  159
Test: unreliable net, restarts, partitions, many clients (3A) ...
  ... Passed --  33.1  5  1775   97
Test: unreliable net, restarts, partitions, many clients, linearizability checks (3A) ...
  ... Passed --  32.7  7  4532  293
PASS
ok      _/Users/sjy/develop/Go/6.824/src/kvraft 296.354s

Lab3B Key/value service with log compaction

为了防止raft的log无限制增长浪费空间，kvserver需要在适当的时候告诉raft进行日志压缩，并主动保存状态机的相关状态，保存到persister的snapshot中。raft的leader节点也要检测follower的log是否过于过时，如果follower对于回应AppendEntry RPC的回复出现请求的日志条目已经被snapshot了，leader需要发送installSnapshot RPC，更新follower的Snapshot。

为了实现动态的日志，给Raft结构增加一个startIndex，代表了日志条目逻辑下标的开始下标，之前一直默认是1。当进行日志压缩后，startIndex增加，需要给Raft定义新的日志操作接口，来完成逻辑下标到真实下标的转换。startIndex也要作为需要persist的持久状态（否则就不能通过TestSnapshotUnreliableRecoverConcurrentPartitionLinearizable3B）。

当kvserver和raft重启的时候，需要读取相关的state或者snapshot，来获得崩溃之前的状态（如状态机等）。

对于不是leader的kvserver，相应的raft节点可能收到leader的InstallSnapshot RPC，此时raft节点需要通过applyCh来告诉kvserver来更新状态机。

运行结果

$ go test -run 3B
Test: InstallSnapshot RPC (3B) ...
  ... Passed --  18.8  3   409   63
Test: snapshot size is reasonable (3B) ...
--- FAIL: TestSnapshotSize3B (161.48s)
    config.go:65: test took longer than 120 seconds
Test: restarts, snapshots, one client (3B) ...
labgob warning: Decoding into a non-default variable/field int may not work
  ... Passed --  22.8  5  1111   74
Test: restarts, snapshots, many clients (3B) ...
  ... Passed --  35.2  5  4156 1480
Test: unreliable net, snapshots, many clients (3B) ...
  ... Passed --  23.6  5   933  189
Test: unreliable net, restarts, snapshots, many clients (3B) ...
  ... Passed --  27.0  5  1860  197
Test: unreliable net, restarts, partitions, snapshots, many clients (3B) ...
  ... Passed --  35.4  5  1807   89
Test: unreliable net, restarts, partitions, snapshots, many clients, linearizability checks (3B) ...
  ... Passed --  34.2  7  4541  258
FAIL
exit status 1

发现TestSnapshotSize3B总是超时，要求在120s内完成，但是我的实现总是160s。一开始以为是我的raft层没有实现好，于是又去参考了vtta的raft进行实现，返现速度仍然是160s。尬住了