在诸如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
最后的序号是多少
你后面的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)