CRAQ

这篇论文主要介绍 chain replication，改进了读性能。CRAQ 是 Chain Replication with Apportion Queries 的缩写，将读操作分摊到所有的节点上，所有的节点都可以进行读操作。chain 越长，读性能就越好，但是写性能就越差。

操作流程

Chain Replication

所有的写操作必须从头开始，逐步往下传递，传到尾。尾部返回确认信息，逐步往上传，直到头部，才回复确认给客户端。

所有的读操作，必须在尾部完成。

这个结构是具有强一致性的。可以通过构造多条链的方式来将负载均衡。

Chain Replication with Apportioned Queries

所有的写操作必须从头开始，逐步往下传递，并将节点标记为 dirty，传到尾。尾部返回确认信息，逐步往上传，将节点标记为 clean，直到头部，才回复确认给客户端。

任意的节点都可以进行读操作。如果当前节点是 dirty，那么这个节点去询问尾节点，尾节点返回一个版本号，当前节点返回对应版本号的信息。

{{uploading-image-33854.png(uploading...)}}

一些思考

慢节点

有一个节点非常慢，那么这个节点将拖慢整体的速度，因为 chain replication 复制的时候是一个一个节点往下传递的，所以当其中一个节点很慢，那么这个节点后面的节点都要受到这个节点的速度的制约。

多条链

这个方法来自笔记里面。我们可以将 objects 分到多条链上面，让所有的 server 参与到这些链当中，从而可以将负载均衡起来。

Split objects over many chains, each server participates in multiple chains.

C1: S1 S2 S3
C2: S2 S3 S1
C3: S3 S1 S2

Split brain

如果节点间不能通信，节点必须等待，不能做 configuration 的改变，因为有 Split brain 问题。

Tail 优化

读操作不在 Tail 上进行了，Tail 只进行版本查询。

Q&A

Q: Item 4 in Section 2.3 says that, if a client read request arrives and the latest version is dirty, the node should ask the tail for the latest committed version. Suppose, instead, that the node replied with its most recent clean version (ignoring any dirty version and not sending a version query to the tail). This change would cause reads to reflect the most recent committed write that the node is aware of. Explain how this could lead to violations of linearizability -- or violations of the paper's goal of strong consistency.

A: 我觉得可以设想这样一个场景，有一个写操作正在往下传递，假设原来节点中只有数据 A，写操作在 A 后面追加 B。现在 client 读取了一个已经写入了 B 的节点，于是根据题设，返回 B。client 再次读取，可是这回节点奔溃了，然后读另外的节点，这个节点还没有写入 B，于是读取到了原来的数据 A。因此，违反了强一致性。

Q: 公开课里面讲的一个有意思的问题，现在有一条链，第一个节点和第二个节点是在线的，但是这两个节点不能通信。此时第一个节点想尝试成为 TAIL，而第二个节点想尝试成为 HEAD，如何处理这个问题(split brain)呢？

A: 课上讲到的一个方法是使用 configuration manager，chain 上的节点不能做配置的修改，它们不能尝试成为 HEAD or TAIL。只有 manager 改变了配置之后，才可以让他们成为 HEAD or TAIL。此外，这个 manager 不仅仅需要知道节点是否在线，还需要知道节点之间是否可以通信。

Q: crap vs. raft

A: 速度是 craq 快，因为接受命令的 head 需要的操作比 raft 的 leader 少。craq head 只需发给下一个节点，然而 raft leader 需要发给所有节点。如果节点出现故障，那么 craq 整体会受到影响，因为所有节点都要进行写入操作才能接着操作。然后 raft 不会受到某个节点故障的影响，因为 raft 只需要 majority 即可。