System|分布式|Chain Replication

在诸如Primary/Backup、Raft、Paxos这类备份模型中，主节点需要进行广播操作，命令备份节点同步。这就导致了scalability的问题，因为广播的吞吐量随着备份数的增长而线性增长，主节点承载着更大的压力。

Reference:SJTU,SE,CSDI slide: Availability

04年，链式复制被提出，思路是每个节点只负责向后续节点进行备份，从而将压力分摊到整个链上。因为其与上述的广播类备份协议相比，在需要scalability的workload下吞吐量具备优势，因此也被用于许多工业产品例如Ceph。

之前只看过相关视频，有空读论文补习一波基础知识，后续再读CRAQ。

Reference： OSDI 2004 Chain Replication for Supporting High Throughput and Availability

架构

链式复制建立在Fail-stop的基础上:

• 如果失败，宁可停止服务，也不能进行错误的状态转移(强一致性)
• 环境有能力监测到故障

作者假设了一个永不失败的Master，我们把它想成paxos/raft/zab集群就行，进行:

• 心跳检测
• 通知链上服务器它的前后节点
• 通知客户端链的首尾

更新时，通过HEAD节点进行更新，然后链上的节点向后续节点进行同步，直到TAIL回复。如果更新时需要进行计算，则只需要HEAD计算，后续节点都是单纯写，避免重复计算。

读取时则通过TAIL节点读取并由TAIL回复。

协议细节

[公式]

表示TAIL通过的update请求序列，上标表示节点的序号。如果

[公式]

，显然

[公式]

，因为只有链前面的节点通过，才会同步后面的。

[公式]

表示链收到但是没有被TAIL处理的请求。

作者定义了三个不会影响一致性的操作。

对于链式复制而言，能改变这两个集合的仅仅有两种情况。

Client对链的首或者尾发出请求，则在入队Pending，对应T1。

TAIL处理请求，出队Pending，如果是update则入队Hist，然后做出相应的响应，对应T3。

链中间的同步并不会改变

[公式]

和

[公式]

，因为链已经收到且TAIL并没有处理。但是会改变中间的

[公式]

。

容错

头节点故障

可以简单地看成是头节点没有同步的那些Pending请求丢失了，也就是T2。

因此依然满足一致性。

尾结点故障

由于原本的倒数第二个节点变成了尾结点，因此那些由倒数第二个节点处理过的Pending请求会变成已被尾结点处理，也就是重复了T3。

因此依然满足一致性。

中间节点故障

显然，如果

[公式]

，显然

[公式]

，因为只有链前面的节点通过，才会同步后面的。这里的处理，是视频里没有提到过的，也就是为什么要知道前置节点。

在这个基础上，作者额外让链上每个服务器

[公式]

存储一个列表，

[公式]

，即那些请求后续节点同步(未必已经同步)，但是没有被尾结点处理过的请求。

向后续节点发出同步请求后，将请求加入

[公式]

当尾节点处理之后，发出ACK让前置节点从

[公式]

删除请求，然后前置节点接着递归。

根据定义，如果

[公式]

，显然

[公式]

，取并集

因此，如果中间的节点

[公式]

故障，前置节点

[公式]

只需要向后续节点

[公式]

同步那些存在于

[公式]

且不存在于

[公式]

的请求即可。流程如下。

1. master告知节点

[公式]

你前面的

[公式]

挂了，赶紧恢复

1. 节点

[公式]

告诉master

[公式]

最后的序号是多少

1. master告知节点

[公式]

你后面的S挂了，赶紧恢复，以及

[公式]

的序号

1. 节点

[公式]

向

[公式]

同步

新增节点

新增的节点

[公式]

增加在链尾，在同步完成前先不提供查询服务，将

[公式]

全量复制到

[公式]

，由于复制的时间可能很长，原本的尾部

[公式]

因此还并发地承担之前的责任以确保可用性，但是将这段时间的更新同时增加到

[公式]

，直到全量复制完成，满足

[公式]

。

之后，

[公式]

将之后的查询请求丢弃或者转发给新的链尾

[公式]

,并把已有的

[公式]

的请求发送给

[公式]

。然后master通知client新的链尾，并让它直接访问

[公式]

。

总结

广播式星型备份，存在scalability的问题

链式复制延续了ROWAA(read one, write all available)的思路，而很多其他系统为了保证scalability和availability牺牲了一定的强一致性。

主要亮点我觉得是均摊开销解决scalability+平滑扩容解决availability, 用了Sent来处理错误情况和扩容的情况，slide和视频都不提这个Sent，果然还是得看原文才能更理解。

缺点

如果把备份数定义为m，请求数定义为n，那么对于星型复制，读压力是O(n), 写压力是O(mn)

对于链式复制，读写压力都是是O(n），读操作没有均摊开销，其他副本不可读。

所以后来CRAQ似乎解决的是这个问题。

另外就是写操作的latency是O(m)