分布式之ChainReplication
0. 前言
MIT6.824 LEC10
为了容错，我们需要对数据进行备份。而当数据有多个备份副本之后，我们又需要保证各副本的一致性，即需要将状态（数据）同步到各个副本。
常见的一致性算法，比如raft，都采用主从拓扑结构。这种结构下，主节点接收读写请求，并负责将状态同步到所有备份节点。主节点负载较高，系统整体性能将受限于主节点。当然，也可以与Zookeeper一样，舍弃强一致性（线性一致性），将读请求分摊给备份节点。
而链式复制(CR, Chain Replication)采用链式拓扑结构，不选择主节点，每个节点只需将状态同步到下一个节点。CRAQ是基于CR的改进，它允许从任意副本中读数据，同时还保证线性一致性。
1. 链式复制CR
所有节点呈链式排布，头节点(HEAD)负责处理写请求，尾节点(TAIL)负责处理读请求：
写请求：头节点收到写请求后，会将其传递到下一个节点，下个节点再传递给下下个节点。当尾节点完成写请求后，则代表该请求是已提交的，它会向客户端返回响应。
读请求：尾节点处理所有读请求，客户端只会读到已提交的最新数据，保证了线性一致性。
故障恢复：
头节点故障，下一个节点会顶替头节点。如果一个写请求在头节点故障之前发送到了下一个节点，那下一个节点会继续完成并传递该请求；如果一个写请求在头节点故障之前未发送到下一个节点，那这个写请求肯定是未提交的。
尾节点故障，上一个节点会顶替尾节点。所有在尾节点中提交的状态，必定在上一个节点中也提交了。尾节点故障前，可能未将已提交的请求，响应给客户端。此时，客户端将重新发送写请求，头节点会判断该请求是否重复，若重复则不会被再次执行。
中间节点故障，会被移除，前后节点相接。前一个节点需要重新发送最近的写请求给下一个节点。
存在的问题：
脑裂问题：当头节点与其它节点之间的网络发送故障，头节点的下一个节点会顶替头节点，此时网络中将出现两个头节点。链式结构无法解决脑裂问题，需要第三方（比如Zookeeper）的帮助，来判断哪个节点存活哪个故障、哪个是头节点哪个是尾节点。
单个节点变慢，会影响整体性能。
2. CRAQ
在CR中，所有读请求都由尾节点处理，读请求较多时，尾节点的负载较高。
CRAQ(Chain Replication with ApportionedQueries) 是CR的一种改进：它允许客户端从任意节点读取数据，同时还保证了线性一致性。主要改进如下：
CRAQ中的每个节点会存储一个数据对象的多个版本，每个版本包括一个单调递增的版本号和一个附加的属性（其值为
clean或dirty），所有数据对象初始都被标记为clean。当节点收到一个数据对象的新版本时（对这个数据对象的更新写），该节点会将此最新版本附加到该数据对象的版本列表中：
如果节点不是尾节点，则将版本标记为
dirty，并向后续节点传递写操作；如果节点是尾节点，则将版本标记为
clean。此时写操作是已提交的，尾节点会通过链回传ACK，来通知其它节点操作已提交。
当节点收到ACK后，它将对应数据对象的版本标记为clean，然后删除该对象的所有旧版本。
当节点收到读请求时：
- 如果数据对象的最新版本是clean，则直接将值返回；
- 如果数据对象的最新版本是dirty，节点则与尾节点通信，询问该数据对象已提交的最新版本号，然后返回这个版本下的数据对象。
3. 个人总结
CR与Raft对比：
CR处理单个写请求的总时间比不上Raft，因为Raft只需要超半数节点提交。
Raft中主节点需要单独负责将状态同步到集群中其它节点，而CR中每个节点只需将状态同步到下一个节点，相当于将主节点的负载分摊到了所有节点。
CR不能算共识算法，它无法解决脑裂问题，无法对谁是头节点达成一致。
CR实现起来更加简单。
Raft中，为了保证线性一致性，客户端必须向leader读取数据，那能否将CRAQ的改进思路应用到Raft中呢？大概是不能的。因为CRAQ中，每个节点都知道数据是否在发生变更以及是否提交。但Raft中，由于网络延迟，部分follower可能并不知道数据发生变更，因此对于每个读请求，follower都需要向leader确认数据是否变更，这相当于读请求都转交给leader。