MIT6.824:Lab4

终于到了这个 Lab4，不容易啊。。。

# 4A

a set of replica groups

每一个 replica group 负责一系列 shards。每个 group 就是一个 raft 组

shard master

shard master 负责 shard key 由哪个 group 负责。

shard controller 也必须是 F.T，所以需要使用 Raft。

shardctrler 必须管理一系列 configuration，每一个 configuration 都表述了一组 replica groups 已经将 shard 到 replica 的 assignment。每当 assignment 需要改变的时候，这个 shard controller 就创建一个新的 configuration 进行新的 assignment。KV clients 和 servers 都和 shardctrler 进行沟通，当他们想要新的 configuration（或者旧的 configuration？这里为什么需要旧的）

首先我们需要实现 4 个 RPC，这些列出用于控制 shardctrler，加入新的 replica group 或者清除 replica groups。

Join：用于 replica 的组的加入，参数是 groupID 到 servername 的映射。如果 shardctrler 救助站了这个新的组，那么需要做一个新的 configuration。shardctrler 需要将 shard 切分得尽量均匀 assign 给 replica group。并且需要 move 尽量少的 shard 来到达目标。并且 GID 可以被重用，也就是 GID 允许加入、退出、重新加入。

Leave：leave 就是一些 GIDs。shardCtrler 需要重新创建新的 configuration。这个新的 configuration 需要同样 shards 被 divide 尽量均匀

Move：Move 就是把一个 shard 分配到一个 GID，这个 Move RPC 用于测试。Move 操作之后的 Join 和 Leave 实际上是在对 Move 进行 Undo，因为这两个操作都会重新分配 shard。

Query：query 查询的是一个 configuration number，如果这个 configuration number 不存在，那就返回最大的一直 configuration number 的 configuration。

最开始的 configuration number 为 0，并且不包含任何的 group，所有的 shard 都 assign 给 GID 0.

Hints：

1. 可以 copy 之前的 kvraft server。
2. 需要过滤重复的 rpc。
3. 状态机的 shard rebalancing 需要确定

直接套用 Lab3 带代码：

Test: Basic leave/join ...
  ... Passed
Test: Historical queries ...
  ... Passed
Test: Move ...
  ... Passed
Test: Concurrent leave/join ...
  ... Passed
Test: Minimal transfers after joins ...
  ... Passed
Test: Minimal transfers after leaves ...
  ... Passed
Test: Multi-group join/leave ...
  ... Passed
Test: Concurrent multi leave/join ...
  ... Passed
Test: Minimal transfers after multijoins ...
  ... Passed
Test: Minimal transfers after multileaves ...
  ... Passed
Test: Check Same config on servers ...
  ... Passed
PASS
ok  	6.824/shardctrler	2.389s

简单 pass 一个。

# 4B

需要修改：

shardkv/client.go , shardkv/common.go , and shardkv/server.go 这三个文件。

replica groups have to hand off shards to each other

可能需要重新设计 4A 的代码，尽量少移动 shard。问题来了，怎么在不同的 raft 组之间移动数据？

必须实现线性一致性，这个可以仿照之前 lab3 来做。

This must be true even when Get s and Put s arrive at about the same time as configuration changes.

这说明 configuration change 完毕的时候，必须是相同的副本，可以简单设计 reconfiguration 时候不处理任何 get 和 put 请求？这个之后再考虑。

Think about how the shardkv client and server should deal with ErrWrongGroup . Should the client change the sequence number if it receives ErrWrongGroup ? Should the server update the client state if it returns ErrWrongGroup when executing a Get / Put request?

我的设计，当查询到配置变更信息后，立刻加锁进行迁移数据，这样就可以拒绝接受请求和 apply log。完成迁移数据之后再释放锁。对于此后再次 apply 上的 log index，如果此时 server 不负责这个 shard，那么直接丢弃就可以了，也不更新查重表。对于此后如果旧的请求再次到来，如果是 put/append，直接查查重表，即使不负责这个 shard 如果之前做过这个请求，也可以返回 OK。但是之后的之后的请求就会发送 ErrWrongGroup 。

对于新的迁移过去的 shard，查重表初始为 0，对应着任务没有完成，因为这个新的 server 并不会去服务旧的 rpc，所以此时也是可以正常工作的。

（所以 client 的逻辑就是，只有接受到 ErrWrongGroup 的请求才会查询新的配置，防止重复 apply）

After a server has moved to a new configuration, it is acceptable for it to continue to store shards that it no longer owns

即使迁移了一个新的配置，也可以保留原来的数据。

# 3.20 更新

Lab4 + 2Challenge 完美通过，并发测试没有搞，我的电脑配置不支持这个 lab 的批量测试。。。而且我也不想搞了，太心累了

Test: static shards ...
  ... Passed
Test: join then leave ...
  ... Passed
Test: snapshots, join, and leave ...
  ... Passed
Test: servers miss configuration changes...
  ... Passed
Test: concurrent puts and configuration changes...
  ... Passed
Test: more concurrent puts and configuration changes...
  ... Passed
Test: concurrent configuration change and restart...
  ... Passed
Test: unreliable 1...
  ... Passed
Test: unreliable 2...
  ... Passed
Test: unreliable 3...
  ... Passed
Test: shard deletion (challenge 1) ...
  ... Passed
Test: unaffected shard access (challenge 2) ...
  ... Passed
Test: partial migration shard access (challenge 2) ...
  ... Passed
PASS
ok  	6.824/shardkv