1. 简介
本文提出了一个复制协议CURP（一致无序复制协议）：
- 对于可交换的操作，只需要1 RTT时间（和无复制系统一样）；对于不可交换的操作，仍需要2 RTTs时间（和传统复制系统一样）
- 保证可靠性、可用性和一致性
- 不需要依赖其它硬件
该协议在Redis和RAMCloud实现，前者只损失一点性能，后者延迟减少一半且吞吐提高3倍。
2. 将持久化从顺序一致中分离
复制协议需要保证：
- 顺序一致：若副本两个操作$a$, $b$顺序为$(a, b)$，则没有任何客户端在看到$b$的时候，看不到$a$
- 持久化：一旦提交，进程崩溃后数据依旧不丢失
一般而言，传统复制协议延迟相对高一些，或有一些缺点：
- 主从复制：客户端$\rightarrow$主节点（1 RTT），主节点$\rightarrow$全部从节点（1 RTT）
- 类Paxos协议：客户端$\rightarrow$主节点（1 RTT），主节点$\rightarrow$超过半数从节点（1 RTT）
- Faxos Paxos和Generalized Paxos：1.5 RTTs
- NOPaxos和Speculative Paxos：接近1 RTT，但需要额外硬件支持，路由路径变长使得延迟会高一些
CURP的关键思路在于：对于可交换的操作，持久化顺序可以和操作顺序不一致，从而将延迟将为1 RTT
- 客户端往一个临时缓冲Witness写入请求，它不含顺序信息，客户端可并行向其写入
- 写入Witness同时，向主节点写入，然后立刻返回，只需要1 RTT
- 当主节点挂掉，Witness可用于重放和恢复
3. CURP协议
3.1. 架构和模型
CURP模型：
- 基于fail-stop模型，不处理拜占庭错误
- 有$1+f$个副本，可容$f$个错误
- 对网络没有限制
CURP架构：
3.2. 协议正常操作
a) 客户端
- 客户端并行向$f$个Witness写入操作（
record请求），并向主节点写入操作（execute请求） - Witness判断操作是否可交换，若不可交换则返回
reject - 客户端需要收到$f$个Witness响应
- 正常情况：只需要等待主节点写入成功的响应即可返回，主节点后台异步复制（1 RTT）
- 若收到
reject或少于$f$个响应：- 先向主节点发送
sync请求，等待主节点同步完请求（同步包含最新请求，2 RTTs ~ 3 RTTs） - 若收不到
sync响应，则说明主节点可能挂了，那么客户端重启进程并重发请求给新的主节点和witness
- 先向主节点发送
b) Witness
其支持3个操作：
- 记录客户端的操作
- 直到主节点告知可以删除前，维护客户端的操作
- 恢复时，提供之前的客户端操作
Witness记录客户端操作时，需要检验新操作是否与缓存的操作可交换，若不可交换则返回reject响应。
为了安全，通常Witness的数据存于NVM中。
c) 主节点
主节点串行执行客户端的请求，将请求添加到日志中。
其日志包含2个下标，将日志分为”已同步”和”未同步”的2部分：
对于1 RTT操作，客户端不需要等待主节点同步完，只需主节点写入完成后即可返回，主节点后台异步复制给其它从节点，因此会有”未同步”的部分。
主节点当然也是可以直到操作是否“冲突”（即“未同步部分”是否出现不可交换的部分），因此主节点探测到冲突时，执行请求后进行同步复制，返回的响应会带上synced标记。这样即使Witness返回了reject响应，客户端不需要发送sync请求，从而让延迟变为2 RTTs。
3.3. 恢复
CURP使用两阶段恢复：
- 选主，并从一个从节点恢复数据
- 再从Witness重放数据
- 选任意一个可用的Witness，若没有可用Witness，新的主节点需要等待其可用
- 然后让该Witness上拒绝任何请求，使其不可变
- 接着从该Witness上回放请求，由于请求可交换，因此顺序不重要
- 最后主节点数据同步复制到从节点，并重置Witness
不过从Witness重放数据时，可能造成重复执行的问题，违背线性一致性（Witness请求已经在主节点挂掉前被同步了，但还没被清除），其解决方法是使用RIFL：
- 它给所有的RPC赋上一个唯一ID
- 服务端存储该ID和请求的结果（与原子方式和更新的对象持久保存），来检测重复的请求
3.4. 垃圾回收
当主节点将请求同步给从节点后，Witness的数据即可删除。
CURP中，主节点会向Witness发送gc的请求，以删除Witness上的数据。该请求是一个“批量”请求，即一个gc请求可删除Witness的多条数据（因此会有3.3.中的恢复重复执行问题，而这由RIFL解决）。
3.5. 重新配置
本节讨论3个重配置场景：从节点恢复、Witness恢复、用于负载平衡的数据迁移。
a) 从节点恢复
CURP并没有改变处理从节点恢复的方式，系统直接恢复从节点即可
b) Witness恢复
当Witness挂掉：
-
配置管理器会给主节点移除挂掉的Witness，并赋上新的Witness，并通知主节点
- 主节点执行一次同步操作，保证$f$副本容错，然后响应给配置管理器
- 客户端就可以使用新的Witness（从配置管理器获取）
为了防止客户端使用旧Witness进行操作，CURP给Witness表维护一个递增版本号WitnessListVersion：
- 当Witness变更，主节点上该版本号都会递增
- 客户端请求会包含该版本号，主节点可检测版本号冲突并返回错误
- 当主节点返回Witness版本号错误，客户端会从配置管理器获取新版本的Witness列表
c) 用于负载平衡的数据迁移
为了负载均衡，主节点将数据分区，并分配给不同的主节点上。
迁移分为2步：
- 准备阶段：拷贝数据，此时可对外服务
- 迁移阶段：
- 停止对外服务，执行一次同步，并清空Witness保证最近请求都被拷贝
- 迁移数据，并改变配置
客户端可能会根据旧配置进行请求，此时旧的主节点会拒绝请求，从而客户端会拉去新配置。
3.6. 主节点读
对于主节点的读，主节点需要检查当前“未同步”的操作有没有和当前读操作冲突，若冲突，读之前会执行一次同步操作。
3.7. 从节点一致读
这里主要问题是stale read。
为了解决该问题，还是使用了Witness：
- 挑选一个从节点，访问Witness，判断是否有冲突
- 若没有冲突，说明数据是最新的，直接返回从节点的值即可
- 若冲突，说明数据是旧的，则重定向到主节点读取
4. NoSQL上的实现
4.1. Witness生命周期
Witness节点有2个模式：正常模式、恢复模式
- 正常模式：启动时进入该模式，可接收客户端的请求，并接收GC的请求
- 恢复模式：当主节点尝试获取恢复数据时，进入恢复模式，此时拒绝客户端的请求
下面记录了Witness的API：
4.2. Witness的数据结构
其数据结构类似于散列表。
对于单个对象更新：
- 其对请求的主键进行散列，然后插入到对应的slot中；
- 若没有可用slot，则返回
reject
对于多个对象更新：
- 检查所有对象是否出现冲突
- 对于每个对象，都有可用的slot进行存储
4.3. 主节点上进行可交换检测
CURP存在两段数据：”已同步”和“未同步”。因此可以根据”未同步”的部分进行检测。
但是这需要适配具体的存储方案：
- 以日志存储：根据日志同步的位置进行比较即可
- 以非日志形式存储：使用时间戳/版本号
- 主节点维护2个时间戳：最新更新时间戳，最新同步时间戳
- 请求根据比较这2个时间戳判断：两个时间戳必须相等才算不冲突
4.4. 提高主节点的吞吐
- 批量进行主从复制，减少RPC调用次数
- 批量过大，则提高了冲突的可能性，从而提高了
sync请求的可能性，导致吞吐下降 - 批量过小，则调用RPC数量过多，吞吐也会下降
- 批量过大，则提高了冲突的可能性，从而提高了
- 对于可交换操作，采用异步复制，不需等待主节点复制完成，降低延迟并提高吞吐
4.5. 垃圾回收
- CURP使用主键散列值和RIFL分配的请求ID定位需要回收的垃圾，收到GC请求后，删除对应的数据
- 由于延迟等情况，Witness可能存在未清除的垃圾数据，并造成冲突，这里有检测机制
- 若某个数据在多次GC后，还是冲突，则Witness就会标记它”可能未正确回收“
- 主节点发送GC请求后，这些”可能未正确回收“的数据会返回给主节点
- 主节点将会处理”可能未正确回收“的数据，重试GC
4.6. 恢复步骤
恢复时，首先从从节点恢复数据，然后重放Witness。通过RIFL可避免重放时的请求重复执行。
因此恢复操作是很快的。
4.7. 僵尸节点
僵尸节点是其它节点认定崩溃的节点，该节点的功能被接管了，但是该节点本身并没有崩溃（这种情况可能在网络分区下出现）。因此，客户端可能还是能和僵尸节点交互。
CURP协议假定下层系统能排除僵尸节点。
此外，Witness也提供了额外的保护：
- 若僵尸节点响应客户端，没等待复制完成（1 RTT操作），则客户端需要在完成请求前和所有Witness交互
- 若客户端在Witness重放前交互，则返回成功，因为请求将会被重放到新的主节点，数据不会丢失
- 若客户端在Witness重放后交互，则返回失败，因为请求不会再添加到新的主节点，因此客户端可以认定僵尸节点挂掉，从而请求新的主节点
5. 总结
本文的创新点在于将顺序和持久化分离，复制的时候可乱序执行可交换的请求，而可交换的请求即可采用异步复制，从而在不影响一致性下，提高了吞吐，降低了延迟。
而Witness缓存是架构中最大的创新：
- 它让主、从以及客户端都感知到哪些数据未完全同步，并利用它来判断请求是否可交换（以决定请求是否采用同步复制）
- 由于完全同步后，Witness数据即可删除，因此GC也很容易实现，Witness也不需要存很多值
- 对于恢复时的重复执行，RIFL的序列号也很简单的实现了去重的问题
