System|分布式|CRAQ读均摊链式复制

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设计

对对象而言，CRAQ为其赋予了一个单调增的版本号，以及标记版本是否dirty的bit，一个对象是很多版本数据的列表，每个版本的数据初始化时均为clean。

如果节点接收到写请求，则把这个新版本数据append到列表末尾。

• 如果节点为中间节点，标记为dirty，并向后续节点发出写请求。
• 如果节点为末尾节点，标记为clean(COMMIT），并向前迭代通知前置节点标记为clean。
• 当节点收到请求更新为clean后，则删除之前版本的数据(因此clean一定是最前的数据)

如果节点接收到读请求，则看最新版本的数据是否clean。

• 如果clean，返回这个值。即只有一个版本的数据。
• 如果dirty，则询问尾节点最后COMMIT的版本，然后返回该版本的数据。即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时对链上每个节点都发一个包。

• 如果节点为中间节点，标记为dirty，并向后续节点发出写请求

data通过multicast来传播，而metadata则通过链来传播。

如果metadata到了，而data没到，则向前置节点请求data之后再向后续节点继续传播metadata。

• 如果节点为末尾节点，标记为clean(COMMIT），并向前迭代通知前置节点标记为clean。

这个向前迭代的通知也通过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，但是读中间的也没啥问题。