MIT 6.824 lab2 kv server

Linearizable

Linearizable(线性一致性)指的是，在一个分布式系统中，server对client而言，看起来像是个单副本，单线程执行的系统，满足原子性和时间顺序。线性一致性是最强的一致性模型。

在lab2中，任务是实现一个采用Linearizable的kv server，同时拥有网络容错机制。

KV server简介

客户端通过clerk对象与服务端交互，调用两种rpc方法：Put(key,value,version)，Get(key)

• Put(key, value, version)：

仅当传入的 version 与服务端当前该 key 的版本号完全匹配时，才会更新 value，并将版本号加 1。 若 key 不存在且 version == 0，则创建新 key，初始版本为 1。 若 key 不存在但 version > 0，返回 rpc.ErrNoKey。 若版本号不匹配，返回 rpc.ErrVersion。

• Get(key)：

返回 key 对应的 (value, version)。若 key 不存在，返回 rpc.ErrNoKey。 每个 key 在服务端维护一个 (value, version) 元组，其中 version 表示该 key 被成功写入的次数。这一机制不仅支持条件写入（类似 CAS），还能在不可靠网络下配合客户端重试，实现 at-most-once 语义，避免重复写入。

最终，server对client呈现出如同单机单线程执行的行为。

Step 1 key/value server with reliable network

该阶段的目标是实现一个基于可信网络的kv存储，较为简单。

• client

给rpc调用填一下参数即可，此阶段因为假设网络可信，所以不存在特殊情况，这种情况会在下面详细说明。

• server

首先决定KV的数据结构，除了KV缓存外，还需要value/version的map来存储版本信息，来实现线性一致性。为了处理并发，给一个锁。这里刚开始简单地使用了自旋锁，后续改成了读写锁，这样读操作不会产生锁的开销。

1
2
3
4
5
type KVServer struct {
	mu       sync.RWMutex
	kvalue   map[string]string
	kversion map[string]rpc.Tversion
}

Get(key)的实现较为简单，仅需要判kvalue中有无key即可，有则返回，否则返回ErrNoKey

Put(key,value)的实现麻烦一点。

1. key不存在：
2. version==0，新建kv
3. version!=0,返回ErrNoKey
4. key存在：
5. version匹配，设置kvalue[key]=rpckey
6. 不匹配，返回ErrVersion

Step 2 implementing a lock uisng key/value clerk

这部分最困扰的部分在于：刚开始没搞明白，这个锁到底是谁持有的？错误的以为是每个client在自己本地有一把锁，这样每个client都有一个自己的锁，锁就不起作用了。

正确的逻辑是：kv server持有一个<key,value>，这个key作为一个唯一标识符成为一把锁，每个client通过Gey(lock),Put(lock,value,version)来尝试持有和释放锁。

考虑锁的数据结构，需要有一个唯一的name，作为key。此外还需要什么？–clientID

这样才能区分是哪个client持有锁，从而避免一个client错误的释放不属于他的锁的情况。clientID作为value存储在server端。

此外，在生产环境中，可能存在这样的情况：某个Client A持有锁，但是它宕机了，锁无法再释放，其他client无法再获得锁。解决方法是，给锁上一个lease,超时后，server自动回收锁。

Acquire()：我的设计中，将key不存在和value为空串作为锁可用的标识。因此acquire的流程是：

1. Get(lockname)
2. 若收到ErrNoKey，则说明锁还未创建，直接Put(lockname,clientID,0)
3. 若成功，则持有锁
4. 若失败，说明锁已经被其他client抢先持有，轮询等待。
5. 若成功收到回复，检查value是否为空串：
6. 是，则同样Put，按照上述相同的逻辑返回或者重试
7. 不是，则重试

Release()

调用Get(lockname)，因为锁只能在lock后才能release，所以此步err必为OK。检查value是否等于clientID，若是，则Put(lockname,"",version)即可。否则，说明当前client不持有锁，不能执行Release操作，直接返回。

Step 3 key/value server with dropped messages

假设网络出现问题，server成功执行操作但是client没有收到rpc的回复，对于Get操作，重试即可。对于Put操作，因为有version的控制，重发的version因为不匹配而被拒绝，返回ErrVersion所以也不影响。

但是对于Put，还有另一种情况：

ClientA发送put，在该put到达前，ClinetB发送的put先到达server并执行成功，因此ClientA的put操作会返回ErrVersion，然而这个rpc因为网络问题没有发送到ClientA。此时ClientA再发送put，因为version不匹配，server再次返回ErrVersion，这次ClientA成功收到了此回复。在这种情况和上述的情况中，client都收到了ErrVersion，但是一个put执行成功了，一个put没有执行成功。所以，对于client，如果它的非第一次Put收到的ErrVersion，则client需要返回ErrMaybe，将此问题交给应用开发者解决。

Step 4 implementing a lock using key/value clerk and unreliable network

给lock的Put返回的err加上关于ErrMaybe的判断，重试即可。另外，如果Get获得的value==clientID，这是因为网络原因，收到了重发的rpc的回复，直接结束即可。

整体而言，lab2较为简单，重点在于理解线性一致性模型，以及分布式锁的概念。

• Previous
  MIT 6.824 lab1 MapReduce