【读点论文】Chain Replication for Supporting High Throughput and Availability

在分布式系统中，强一致性往往和高可用、高吞吐是矛盾的。比如传统的关系型数据库，其保证了强一致性，但往往牺牲了可用性和吞吐量。而像 NoSQL 数据库，虽然其吞吐量、和扩展性很高，但往往只支持最终一致性，无法保证强一致性。由此 Chain Replication for Supporting High Throughput and Availability 提出了链式复制协议，旨在保证高吞吐、高可用的同时，支持数据的强一致性。

链式复制协议

所谓链式复制，顾名思义就是将各个数据节点串联成一条链，如同一个链表，第一个节点是 header 头，最后一个节点是 tail 尾节点，如图所示：

chain-replication-01

该协议对服务器环境有两个要求：

当服务器故障时会停机
如果某台服务器停机，环境能够将该服务器从链中移除

这样对于多台服务器组成的一条链，当客户端发来请求时：

写请求：全部发送到 header 节点。
读请求：全部发送到 tail 节点。
响应：全部由 tail 节点响应。

基于上述流程，一个写请求到来时，先在 header 进行运算并写入，然后不断向后传播，一直到尾结点写入成功后，整个写请求才算成功。
读请求全部发送到 tail 节点，只有在尾节点写成功的数据才会被读取到，因此保证了强一致性。

容错处理

链式复制需要有一个管理面（Control Plane）来管理其节点信息，论文中称其为 master 服务，其主要功能如下：

检查链中各节点是否正常
当链中的节点信息发生变化时，及时更新各个节点的前后节点信息
通知客户端链的 header 和 tail 节点信息

通常可以使用 Zookeeper 或者 etcd 这种具有强一致性存储的组件来实现。其节点扩缩容的处理如下：

Header 节点故障

当 header 节点故障时，master 服务会选择原 header 的后一个节点作为新的 header 节点。此时如果有数据写入被 header 接收但尚未被 header 的后续节点收到，对于客户端来说相当于请求丢失，可以通过重试机制来解决。

Tail 节点故障

当 tail 节点故障时，master 服务会选择原 tail 的前一个节点作为新的 tail 节点。因为所有已经写入 tail 节点的数据肯定已经写入到其前一个节点中，因此不会造成任何数据丢失。

其他节点故障

当链中间的某个节点 S 故障时，master 服务需要通知 S 节点的前一个节点 S- 和后一个节点 S+，将 S 从链中移除，并更新 S- 和 S+ 的前后节点信息。这样可能会导致数据丢失，比如某些写请求已经被传到了 S 节点，但尚未被传到 S+ 节点，因此需要一个同步机制如下：

S 节点故障停机，master 检测到故障后获取 S- 和 S+ 的信息
master 向 S+ 节点发送消息 1 请求 S+ 节点的请求序列号
S+ 收到消息 1 后，向 master 返回消息 2 告知其请求序列号
master 发送消息 3 给 S- 节点，告知其节点变更信息以及 S+ 的请求序列号
S- 收到消息后，根据S+的请求序列号同步其所缺失的请求，保证数据一致

扩容节点

为了实现的简易性，链式复制设定扩容时只能将新节点作为 tail 节点加入到链中，因为是一个新 tail 节点，其所需要做的唯一工作就是将前一个节点的数据同步到新节点中与此同时，原来的 tail 节点还可以继续工作，直到新节点与原来的 tail 节点数据同步完成，然后 master 服务可以切换 tail 节点：

T 节点被告知其不再是 Tail 节点，然后 T 可以将收到的读请求丢掉或者转发给新的 Tail 节点
所有发送到 T 的写请求全部向后继续发给 Tail 节点
T+节点被告知成为新的 Tail 节点
master 服务通知所有客户端新的 Tail 节点信息

与主从复制的比较

链式复制算是主从复制（Primary/Backup）协议的一种变体，主要区别在于链式复制是类似链表的形式，写请求时串行，而主从复制是类似星形拓扑，写请求时并行。

论文比较了两者在读写和容错的优劣，在读写方面：

对于 primary 负责读写的场景，primary 必须等待先前的写入成功后才能执行读取，性能要低于链式复制直接从 tail 节点读取的处理。
对于写处理，链式复制是串行处理，延迟是每个节点写入的延迟总和；而主从复制是并行处理，延长取决于某个最慢节点的延迟情况，通常情况下要优于链式复制。

在容错方面，链式复制有三种异常情况：

header 节点故障：对读数据没有影响，对于写请求需要等待 2 个消息延迟：master 广播新节点并通知客户端。
其他节点故障：对读数据没有影响，但对于写请求，需要执行上图提到的同步操作后才能正常执行后续写入，因此数据写入不会丢失，但会延迟大约 4 个消息通信的时间。
tail 节点故障：对读写数据都会造成影响，需要 master 广播新节点并通知客户端新的 tail 节点，至少需要 2 个消息延迟。

对于 Primary/Backup 协议则有两种情况：

primary 故障：对读写数据都有影响。需要经历一个新的选主并同步数据的过程，大约会有 5 个消息延迟。
- 1. master 通知所有从节点 primary 节点故障，停止处理请求。
- 1. 从节点返回其当前的数据状态
- 1. master 确定新的 primary 并通知 backup 节点
- 1. 新的 primary 向所有 backup 节点同步数据
- 1. master 通知所有客户端新的 primary 节点
backup 节点故障：没有写请求在处理，则读数据不会受到影响；如果有数据写入在处理，master 需要通知 primary 某个 backup 节点已经故障，因此可能会有 1 个消息延迟。

总体来看，链式复制在容错方面表现更好，其最坏情况下的延迟（尾结点故障）优于 Primary/Backup 的主节点故障，而最好情况下的延迟（中间节点故障）则与 Primary/Backup 的 backup 节点故障相当。