在诸如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让前置节点从
删除请求，然后前置节点接着递归。
根据定义，如果
，显然
，取并集
因此，如果中间的节点
故障，前置节点
只需要向后续节点
同步那些存在于
且不存在于
的请求即可。流程如下。
- master告知节点
你前面的
挂了，赶紧恢复
- 节点
告诉master
最后的序号是多少
- master告知节点
你后面的S挂了，赶紧恢复，以及
的序号
- 节点
向
同步
新增节点
新增的节点
增加在链尾，在同步完成前先不提供查询服务，将
全量复制到
，由于复制的时间可能很长，原本的尾部
因此还并发地承担之前的责任以确保可用性，但是将这段时间的更新同时增加到
，直到全量复制完成，满足
。
之后，
将之后的查询请求丢弃或者转发给新的链尾
,并把已有的
的请求发送给
。然后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)
