04年,链式复制被提出,思路是每个节点只负责向后续节点进行备份,从而将压力分摊到整个链上。然而,由于其ROWAA(read one, write all available)的思路,读请求始终通过TAIL节点。
如果把备份数定义为m,请求数定义为n,对于链式复制,读写压力都是是
,但是如果能够分摊读请求到不同备份,那么读的压力就成了
。
2009年,普林斯顿的CRAQ(Chain Replication with Apportioned Queries: 读均摊的链式复制) 这篇论文对于上述问题进行了改进,同时还提供了weak consistency的支持,在低一致性需求的workload下提高性能。
Reference: Object Storage on CRAQ
上图是传统的链式复制,除此之外还有master用于服务发现和心跳检测,在CRAQ中作者使用zookeeper进行实现。
更新时,通过HEAD节点进行更新,然后链上的节点向后续节点进行同步,直到TAIL回复。
读取时则通过TAIL节点读取并由TAIL回复。
可以看出,这是ROWAA的思想,写整个链,读TAIL节点。
对对象而言,CRAQ为其赋予了一个单调增的版本号,以及标记版本是否dirty的bit,一个对象是很多版本数据的列表,每个版本的数据初始化时均为clean。
如果节点接收到写请求,则把这个新版本数据append到列表末尾。
如果节点接收到读请求,则看最新版本的数据是否clean。
即使在响应Client前,TAIL又进行了COMMIT,但也不会破坏读的串行(相当于读之后又有个写请求)。
由于上述设计,在读为主(读clean)或者频繁写(读dirty)的情况下,CRAQ比CR更优,因为读均摊(读clean)且末尾节点只负责版本查询(读dirty),所以承担的压力更小,允许吞吐量更大。
CRAQ提供几种的一致性模型
强一致性
默认配置(上述规则),对系统而言,读写操作是线性的。读操作只会读到最终写的值。
最终一致性
允许读没有commit的数据,在写操作被整个链提交前,不同的节点可能有着不同的值,存在一定时间的不一致性,也就是最终一致性。
但是如果client始终访问同一个节点,那么读依然是单调的。
有界的最终一致性
允许读没有commit的数据,但是时间或者版本号必须在一定界限内。正常情况下,数据会比提交的版本新;如果是partition的情况下,则由于没有接收到最新的写,会比提交的版本旧。
We are currently in the process of implementing these extensions.
懂了,在画饼。
mini事务
不感兴趣
组播multicast降低写延迟
multicast貌似是硬件IP层的技术,能发一个包给多个对象。这样避免了broadcast时对链上每个节点都发一个包。
data通过multicast来传播,而metadata则通过链来传播。
如果metadata到了,而data没到,则向前置节点请求data之后再向后续节点继续传播metadata。
这个向前迭代的通知也通过multicast来传播,而不通过data。如果没有传播到也没事,因为查询时会对TAIL做版本查询,到时候也能通知。
集成zookeeper
服务发现利用/nodes/dc_name/node_id
链为/chains/chain_id,保存链的metadata
链节点功能
用one-hop的分布式哈希表组织链,和前置后续节点TAIL保持了稳定的连接池。作者论文里用的是in-memory存储,后续改成用kv的数据库。
集群成员变更
作者提了下如果新增的节点不是Tail的话,需要从后向前反向传播。
这个感觉可以通过运维强制约束避免,暂时不考虑了,实现有点复杂。
如果把备份数定义为m,请求数定义为n,对于链式复制,读写压力都是是
,但是如果能够分摊读请求到不同备份,那么读的压力就成了
。CRAQ就做了这方面的优化,主要是一方面允许clean的节点直接读取,一方面利用版本号使得TAIL只用负责dirty节点的版本查询而不是数据查询。
另外CRAQ还支持了最终一致性,允许读没COMMIT的数据,不过感觉没什么改动,毕竟CR理论上也能读中间节点,只不过为了强一致性所有读都走TAIL,但是读中间的也没啥问题。