【论文阅读】《Chain Replication for Supporting High Throughput and Availability》

--

论文链接：http://www.cs.cornell.edu/fbs/publications/chainreplicosdi.pdf

--

摘要：针对分布式对象存储系统，满足副本的强一致性，同时支持高吞吐高可用的设计方案。简称链式复制。

文章提出了链式复制的方案，并给出了查询、更新操作的流程，节点故障恢复方案。并和primary backups的方案进行了对比。认为链式复制的方案在吞吐上更优。从文章的实验结论看，应该是在更新操作比例小时，吞吐更优。

从个人理解来看，链式复制在吞吐上并没有优势。更多的是在高可用性上的优势比较明显。

--

系统背景：

1. 分布式对象存储系统

2. 支持对象查询和更新操作

不想数据库这么重量级，又比文件系统支持更多的应用语义。

QoS：

1. 高可用

2. 高吞吐

3. 强一致

api前提：

1. query、update是按某种顺序执行的

2. 更新操作生效后，会被后续的查询感知到

3. 查询操作幂等，更新操作不保证幂等。客户端的更新操作没有收到落地反馈需要重发，客户端不区分发起失败与服务处理失败。由于更新不幂等，客户端需要等待发起的更新操作的反馈，需要控制请求流量。

--

每个几点维护一个历史处理对象id集合Hist{ObjectIds}, 和待处理对象id集合Pending{ObjectIds}。更新请求都发到Head节点，查询请求都发到Tail节点。请求到来append到Pending集合，Tail节点处理完成从Pending集合删除，并加入到Hist集合。

有一个master来管理，master负责：1. 检测故障机器，2. 通知每个机器它的前驱和后继节点， 3. 通知客户端链的Head和Tail节点。

master通过Paxos来协调多个master副本。避免单点故障。

Head节点故障，删除原Head节点，将Head节点的后继作为新的head节点。

Tail节点故障，删除原Tail节点，将Tail节点的前驱作为新的Tail节点。

中间节点S故障，删除S节点，master通知S的后继其前驱改为S的前驱，然后通知S的前驱其后继改为S的后继。

Extending a Chain：故障节点被master从chain中摘除后，为了可靠性，需要扩展chain的节点。选择一个节点T+加入chain的尾部。通知T不再是Tail节点且其后继为T+。T+作为新的Tail节点。后续查询请求发送到T+。

Tail落地后将ack反向返回到head,各层节点更新Hist和Pending 集合。

primary/Backups模型：顺序化请求；客户端请求处理广播到backups，并等待全部非故障的backups的反馈。如果primary挂了，选择一个backup作为新的master。primary返回给client。