Lab2 Key/Value Server

前言

这应该是最简单的一个 Lab 了，只算写代码的时间，花了不到两天。学习lecture3 主备复制和 lecture4 一致性模型花了3天时间，但是实际与完成Lab2关系不大。

Lab2 要求构建一个单机键值存储服务器。需要在网络故障的情况下保证线性一致性与至多一次执行语义。并基于它实现一个分布式锁。

讲义开头讲了“版本号机制”：通过在服务端为每个 key 维护单调递增版本号来实现乐观并发控制。客户端执行 Put 操作，需要先通过 Get 获取版本号，再作为 Put 参数传递给服务端。

版本号机制的其他作用：“对于"使用 Put 实现锁" 和 "在网络不可靠且客户端重传时确保 Put 的至多一次语义" 这两个功能的实现来说，维护每个 key 的版本号非常有用。” task2 task3 会体现这两点。

task1：在没有网络故障的情况下，实现键值服务器。

按照代码注释写即可，很简单。

task2：在没有网络故障的情况下，实现分布式锁。

首先要知道分布式锁的实现位于客户端侧，服务端只提供最基本的功能。

最简单的实现：在服务端维护一个键值对，初始 value 为 "unlocked"。如果客户端想要获得锁，修改 value 为自己的标识；如果想要释放锁，将 value 修改为 "unlocked"。

一个需要解决的问题是：获取锁的逻辑会并发执行，Get 发现 value 为 "unlocked"，当 Put 时，value 可能已经被其他客户端修改。

解决方法：将 Get 和 Put 合为一个原子操作。这时候就能利用版本号机制关联 Get 与 Put，如果 Put 返回 ErrVersion，循环执行 Get Put，直到 Put 成功。

拓展：这种方式与 CAS（比较并交换）很类似：先获取旧值，计算出新值。更新共享变量时，先比较当前共享变量的值是否与旧值相等，如果相等，则更新，否则重试。其中"比较并交换"实际是一个原子操作。

task3：在网络故障的情况下，实现键值服务器。

代码很简单，但是对 ErrMaybe 的引入很有趣：

客户端与服务端通信时，网络可能会丢弃 RPC 请求消息，也可能会丢弃 RPC 回复消息。客户端无法知道哪条消息被丢弃。

棘手的情况：服务器对服务端的重试响应了 ErrVersion。

除非服务端维护每个客户端的状态，否则很难保证 exactly-once，只能保证 at-most-once。需要将 at-most-once 的结果返回给应用层，由开发者根据实际情况处理。

task4：在网络故障的情况下，实现分布式锁。

关键1：处理 task3 中 Put 返回 ErrMaybe 的情况，当 Put 返回 ErrMaybe 时，需要进一步判断 Put 是否执行成功。

判断依据：task2 中，锁的 value 会维护客户端的标识，根据它完成进一步判断。（这也算是对 task3 中“除非服务端维护每个客户端的状态”的实现。）

关键2：需要认识到 Acquire 之间一定是并发执行的，Release 之间一定是串行执行的，Acquire 与 Release 二者会并发执行。

lecture3 论文与视频主要讲解主备复制，与 Lab2 关系不是很大，似乎与 Lab3 Raft 有关。

个人认为 lecture3 有价值的知识点：

问题：容错虚拟机的优势？

解答： - "复制"不能解决的问题：软件 bug、硬件设计缺陷。 - 大部分场景都是应用程序级别的复制，如 GFS。 - VMware FT 的独特之处在于，它从机器级别实现复制。从虚拟机层面保障了软件的容错性。

问题：如何解决主备同步时可能的延迟？

解答：在确认 Backup 接收到后，Primary 再去向客户端返回数据。（类似 WAL）

问题：当主节点打算发送输出时，若不使用带有两阶段提交的事务，备份节点就无法确定主节点是在发送最后一个输出之前还是之后立即崩溃的。（论文2.2最后一段原话）

解答： 1. 网络基础设施如 TCP 会丢弃重复报文。 2. 视频中说：“事实上，对于任何有主从切换的复制系统，基本上不可能将系统设计成不产生重复输出。”链接

问题：“脑裂”

解答： - Test-and-Set 服务，用于解决脑裂问题的第三方服务。一般依赖于一小块共享存储实现仲裁功能。 - 现在一般使用基于 Paxos/Raft 的分布式协调服务（如 ZooKeeper/etcd）