前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >System|分布式|Chain Replication

System|分布式|Chain Replication

作者头像
朝闻君
发布2021-11-22 10:59:50
2980
发布2021-11-22 10:59:50
举报
文章被收录于专栏:用户9199536的专栏

在诸如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)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 架构
  • 协议细节
  • 容错
  • 总结
相关产品与服务
云服务器
云服务器(Cloud Virtual Machine,CVM)提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源,适应变化的业务需求,并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本,简化 IT 运维工作。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档