为什么学习 CRAQ

• Chain Replication (CR)，一种与 Raft 非常不一样的方法。
• CRAQ 能够从 replica 读取数据并且保持强一致性

什么是 CR

• write：
  1. client 发送写请求给 head server
  2. 请求按顺序沿着链下发
  3. 每个 server 用新数据覆盖旧数据
  4. 当 tail server 处理完成后回复给 client
• read：
  1. client 发送读请求给 tail server
  2. tail server 回复给 client（不涉及其他 server）
• 为了让 tail 回复，这条链的每个节点必须处理写请求，即整个路径上的节点都已经处理了写请求。
• 如果 head server fail，下一个节点可以代替 head 继续工作（tail server 同理，不过是上一个节点）。如果 head 中途 crash，但是数据还没有到 tail server，所以就不会回复给 client。
• 如果中间的 server fail，需要移除该节点，上一个节点重新发送请求给新的下一个节点。
• 不能处理 network partition 或者 spilt brain 的情况，需要配合第三方组件 configuration manager (cm) 来判断哪些服务器或者还是挂掉了，当有问题的时候，cm 会重新发出配置决定谁是 head，谁是 tail，怎么安排链等。cm 一般会使用 Raft 或者 Zookeeper。
• 可能不止一条链，也许是 replication group，以此来请求分流，这个都由 cm 去决定。
• 每个节点不需要更新其他服务器是否处于在线情况，当下一个节点挂掉后，上一个节点会一直尝试和下一个节点通信，除非收到了新的配置。

为什么 CR 比 Raft 更有吸引力

• client 请求的接收和回复在 CR 中是在两个不同的 server 中处理，Raft 需要 leader 都处理。
• 在 CR 中 head server 只需要发送一次请求，Raft 需要 leader 将请求发送给所有的 follower。
• 读取数据在 CR 中是由 tail server 完成，而在 Raft 中则是 leader，会增加 leader 的负载。
• 失败的情况比 Raft 更简单

可以让 client 读取 CR 中任一 replica？

• 当大量读取操作导致 tail server 负载很高的情况，此时中间的 server 可能还有很多闲置的性能。因此，如果中间节点也参与进处理读请求的话性能可能会更好。
• paper 中提出一种解决方案：
  plaintext

  Chain1: S1 S2 S3 Chain2: S2 S3 S1 Chain3: S3 S1 S2

  这不一定有效，如果请求没有均匀分配的话
• 这也会导致强一致性失效，可能会读到未提交的值，或者是从一个 replica 读到旧值，从另外一个 replica 读到新值。

如何让 CRAQ 支持强一致性读取任一 replica

• 每个 replica 存储每一个 object 的 version list：clean version 和最近写入的 dirty version
• write：
  • client 向 head server 发送写请求
  • 写请求在链传递的时候中间每个 replica 创建新的 dirty version
  • tail server 则创建 clean version，沿着链返回 ack，将 dirty version 转变为 clean version
• read from replica：
  • 如果最新版本是 clean version，则返回给 client
  • 如果最新是 dirty version，不能返回 recent clean version，因为 client 可能从别的 replica 获得了部分新的数据；也不能直接返回 dirty version，因为这个可能是未 committed 的
  • 只需要向 tail server 查询最新的版本即可（version query）

为什么 CRAQ 支持强一致性读取 replica，而 Raft/Zookpeer 不能

• CRAQ 的结构是一条链，所以对于所有的节点：
  • 在写入 commit 之前，所有节点都知道了这个写入
  • 能够知道何时查询 tail server 以得到最新的数据
• Raft/Zookpeer 的 leader 机制是以 majority 进行的，所以 follower 不能何时错过了一个 committed write

这是否意味 CR 比 Raft &c 更强大

• 所有的 CRAQ replica 都处理了请求后才能提交数据，Raft 只需要 majority
• 如果一个节点变得很慢的话，会影响这个链的性能，Raft 则没有这些影响。
• 不能像 Raft 或者 Zookeeper 那样立即可以 fault-tolerant