在学习完zookeeper后，又遇到了一种有趣的复制算法—CRAQ，这篇论文有两个较为有意思的东西，一是通过复制实现了容错，二是通过链复制（Chain-Replication）实现了与Raft不同的复制方式。在实际的生产系统中链复制也有比较多的应用，例如在HDFS中就使用链复制来完成块数据的复制。此外CRAQ还能利用所有节点处理读请求提升系统的吞吐性能并且还能保证线性一致，确认让人着迷。
链复制（Chain Replication）
本文主要讨论的是CRAQ的处理逻辑，但是在讨论CRAQ之前要先看下CRAQ的前身CR(Chain Replication)，CRAQ是对CR的改进拓展。CR与Raft都能保证线性一致，但是采用了与Raft不一样的拓扑结构。Raft是由Leader节点将log并行的复制到其他Follower节点，而CR是将所有的副本按照一定顺序组成一条链，第一个副本叫做HEADER,最后一个叫做TAIL。
复制原理
当执行写请求时客户端将写请求发往HEAD节点，在HEAD节点存储完成后继续向下传播，直到将写请求传递到TAIL节点为止，当TAIL节点处理完后就可以认为本次写请求已经提交（Commited），并由TAIL节点完成通知。
当执行读请求时客户端将读请求发往TAIL节点,TAIL节点将数据返回客户端。因为TAIL节点是最后看到写请求数据的，所以读请求发往TAIL节点读取到的数据一定是最新的，也由此保证了线性一致。
从性能上看，在CR中由于写请求都是往HEAD节点写，读请求都是从TAIL节点读，相对于RAFT的读写都在LEADER上完成，实际上CR从某种程度上来说分担了读写的压力。但是对于写请求有一个最大的问题就是写延迟，因为CR需要将写请求从HEAD节点依次在链中传递到TAIL节点才算是提交，所以CR的写延迟就是各个副本的写延迟之和。在CR中只要其中一个节点出现问题，最严重的情况会导致整个服务不可用。
故障恢复
在CR中，写请求总是从HEAD节点依次传播到TAIL节点。传输有以下情况，一是传递到TAIL节点完成提交，这是正常情况；二是传输过程中某个副本出现故障导致该副本的前驱节点都接收到了写请求，副本的后驱节点都没有收到请求，导致写请求最后无法顺利传递到TAIL节点完成提交。
CR的故障恢复还是比较简单的，下面分情况说明CR如何执行故障恢复。
第一种情况是CR的HEAD节点故障，那么只要让下一个节点称为HEAD节点即可。但是对于还在处理中的写请求还要分情况处理。
- 在HEAD节点故障前，HEAD节点已成功将写请求传播到后续节点，直到TAIL节点完成提交。这种情况下写请求无需做任何干预。
- 在HEAD节点故障时并未将写请求继续向下传递，那么在整个复制过程中这个写请求其实可以认为被丢弃，因为除了HEAD节点别的副本都不知道这个写请求的存在，因此也没有必要进行处理。
第二种情况是TAIL节点故障，当TAIL节点故障时，需要将TAIL的前驱节点作为新的TAIL节点。对于处理中的写请求是无需处理的，因为当写请求传递到TAIL节点之前必然存在于TAIL的前驱节点，也就认为写请求已经提交了。
第三种情况是中间节点故障，只要将故障的中间节点移除即可，可麻烦的是对于写请求要如何处理。
- 中间节点故障之前已经将写请求向下传播，那么这种情况下则无需处理，如果顺利写请求将会到达TAIL节点完成提交。
- 中间节点故障时还未到达中间节点，那么这种情况将中间节点后可以继续向下传递。
- 如果是写请求刚好到中间节点但是故障，这种情况需要移除中间节点后，由被移除中间节点的前驱节点重新向后发送。
以上便是CR的一个简单故障恢复流程。在一个长度为N的链上，理想情况下最多允许N-1次故障。我们接下来考虑一种场景，假设长度为3的链，中间节点与HEAD和TAIL节点产生了网络分区，此时将会出现一个很可怕的场景，HEAD、中间节点和TAIL节点都将以为自己是最后谨慎的节点还能继续提供正常服务。CR出现了脑裂！
是的，CR无法抵抗网络分区，无法抵抗脑裂。
CRAQ
我们从CR回到本文的主角CRQA，CRAQ是对CR的改进拓展，一是解决CR存在脑裂的问题，二是能将所有节点都用于处理读请求，提升系统的吞吐量。接下来我们将继续上一节内容的讨论，CRAQ为何能处理抵抗脑裂
配置管理器（Configuration Manager）
CR是一个很有用的方案，在很多场景下都有使用，但是会是以一种特殊的形式使用。通常CR都会配合外部权威（External Authority）来决定各个副本的状态，以及确定链的组成（哪些节点组成，什么样的编排顺序）。这个外部的权威通常称为配置管理器（Configuration Manager）。通常配置管理器会基于raft或者paxos，在CRAQ中使用zookeeper来做这个配置管理器。zookeeper本身是类似于raft的方案，我们已经在上文中提到了zookeeper的处理逻辑。
配置管理器的主要目的是检测各副本的活性，如果配置管理器认为副本挂了将会重新生成一套新的配置。在新的配置中，重新描述了链的新的定义，包含了链中节点的顺序。被配置管理器认为挂了的节点可能还活着，但是已经不需要关系了，因为还能和配置管理器通讯的节点都将按照新的配置运行。
在客户端与链的交互过程中，客户端需要知道链的HEAD节点和TAIL节点，而这些信息都存储在配置管理器中，因此客户端只需要访问配置管理器既可得到相关信息。
提升吞吐量的处理
在本文开头提到了CRAQ能够在保证线性一致的情况下提升读请求的吞吐量，其实CRAQ采用了一个多版本的方案。假定CRAQ之上运行的是一个key-value数据库，CRAQ的处理逻辑如下：
- CRAQ中的每一个节点都可以存储一个对象的多个版本，每个版本都包含一个单调递增的版本号和一个附加属性 clean 或者是 dirty。初始版本都是clean的
- 当节点接受到一个写的请求的时候，CRAQ会将新版本数据加到旧版本的列表当中然后继续向下传播。如果当前处理节点不是TAIL节点，那么将会把这个对象数据标记为dirty；如果是TAIL节点则在写完后将数据标记为clean，然后沿着链通知其他节点将对于对象数据标记为clean，然后要求其他节点删除旧的版本数据。
- 当接受到读请求的时候，如果节点上对于的对象数据是clean的，则直接返回对象值；如果对象数据是dirty ，并且当前的节点不是TAIL节点时，则询问当前应该返回哪个版本，根据TAIL节点决定返回结果。
上图描述了在新的写请求到来时，写请求的处理与读请求的处理。当要将k对于的值修改为v2版本，则在没有收到TAIL节点的通知时一直存储v1，v2两个版本的数据。如果此时读请求打到当前节点，那么这种情况称为脏读（dirty read）,因为没有收到TAIL节点通知，所以数据没有提交，因此需要返回的是V1版本。如果写请求还未到达TAIL节点是，读请求打到TAIL节点上，此时TAIL节点也只是存储了V1版本的数据，可以直接返回，此时还是线性一致的。
成员变更
虽然在谈到CR时简单提交了CR的故障恢复，但是CRAQ的设计上与CR还是有差别的。
对于正常的写传播，CRAQ节点遵循前面的协议。在恢复过程中，有时需要第二种传播方式，即反向传播。例如链表节点可能会在完成向后传播到头部节点之前失败。由于这些可能的故障状况，当新节点加入系统时，新节点会从其前任节点接收传播消息，并从其后继节点接收反向传播消息，以确保其正确性。新节点拒绝客户端对特定对象的读取请求，直到其与后继对象达成协议为止。
总结
- 链复制算法通过限定拓扑结构降低了达成一致性难度，也有着更好的故障恢复能力，这是比较吸引人的点，但是无法抵抗脑裂、网络分区，必须要引入外部权威来解决，例如像vmware ft里面的test server。
- CRAQ提供了一个提升吞吐率的通用方法，那就是加版本号，这或许是后续对某些场景的优化突破点。
参考资料
- https://www.zhihu.com/column/c_1273718607160393728 MIT6.824翻译
- R. van Renesse and F. B. Schneider. Chain replication for supporting high throughput and availability. In Proc. Operating Systems Design and Implementation (OSDI), Dec. 2004.
- Jeff Terrace and Michael J. Freedman. Object Storage on CRAQ: High-throughput chain replication for read-mostly workloads
附件
{% asset_link craq.pdf %}