网易视频云：分布式存储复制技术-链式复制

网易视频云是网易倾力打造的一款基于云计算的分布式多媒体处理集群和专业音视频技术，为客户提供稳定流畅、低时延、高并发的视频直播、录制、存储、转码及点播等音视频的 PASS 服务。在线教育、远程医疗、娱乐秀场、在线金融等各行业及企业用户只需经过简单的开发即可打造在线音视频平台。现在，网易视频云与大家分享一下分布式存储复制技术-链式复制。

分布式系统中，强一致性通常被认为和高可用、高吞吐不相容，为了实现系统的高可用、高吞吐必须要牺牲强一致性。比如在亚马逊的 Dynamo 提供最终一致性，但是这样其实给开发者带来很多问题[0] • 写入的数据在后续的读操作中不能被读取到 • 写入的数据有可能在后续的读操作中获取到，但是读到后下一次又读不到 Dynamo 不保证一定能够读到写入的数据，将复杂的冲突合并工作留到了客户端；由于 Dynamo 的冲突合并过于复杂，在后来的系统 Amazon S3 使用’ Last-write wins ’来解决冲突，但是仍然不能完全解决上面提到的问题。 Google 的 GFS 在写成功时是一致的，写失败时是不一致的，因此 GFS 的 Record Append 提供的是至少成功写一次的语义，由客户端读的时候自己来解决一致性问题。这样会带来一致性问题[1],比如: 数据在某个 chunk 副本中重复出现了多次，但是在其他副本中可能没有。在记录级别上，读到的记录顺序依赖于刚好读取到哪个 chunk 副本。而开发者更加希望系统能够提供强一致的保证，由分布式系统提供强一致性的保证，这样可以提高开发效率。在 Chain Replication for Supporting High Throughput and Availability 这篇论文中作者提出强一致性、高吞吐(high throughput)、高可用（ high availability ）是相容的，并且解释了具体的实现方法。

链式复制

如果所示，所有的写操作由头结点处理，读操作 /写操作的确认由尾结点处理头结点包含所有的写操作，从头结点到尾结点所包含的写操作越来越少（所有的操作需要从上一个节点传递下来），对写操作的确认在尾节点，读操作也在尾节点进行。节点上的操作向下一个节点同步是 FIFO 的，因此后续节点上的数据记录肯定是前面节点的前缀。比如： HEAD 节点: (a=1) (b=2) (c=3) (d=4) TAIL 节点: (a=1) (b=2) TAIL 节点上的数据记录是 HEAD 节点、 MIDDLE 节点的前缀， MIDDLE 节点上的记录是 HEAD 节点记录的前缀。

头结点拥有四个写操作，其中 a=1,b=2 已经达到尾节点，由尾节点向客户端返回成功。 c=3,d=4 这两条记录尾节点还未返回成功。这时如果客户端的读发生在尾节点，因此只能读到(a=1,b=2)这两条记录；(c=3,d=4)这两条记录现在读不到。在正常流程中强一致性的保证是显而易见的，现在我们来分析异常宕机时的情况：

头节点宕机头节点宕机，记录 d=4 丢失，但是由于对 d=4 这条记录的确认没有返回给客户端，因此并不影响数据的一致性
尾节点宕机 TAIL 节点宕机后， TAIL 节点的父节点接替它成为尾节点，由于它上面的记录总是比尾节点上的记录多，而且尾节点上的记录是它父节点记录的前缀。因此客户端看见的数据变多了，并没有丢失数据，因此也是强一致的。
中间节点宕机中间节点宕机后，并不影响读的一致性，由上图可知 TAIL 节点上的数据是 HEAD 节点数据的前缀，只要父节点将数据同步下来即可。

协议应用

在 CRAQ[2]论文中介绍了使用链式复制的 CRAQ 系统, 该系统扩展了链式复制协议，使得读操作可以在每个节点上发生，提高系统的吞吐，同时仍然提供强一致性的保障。 Hibari 是一个使用链式复制的开源 key-value 数据库，文档非常完善，支持客户端支持 java, C/C++, Python, Ruby, erlang ，而且已在数百万用户的电信系统中稳定运行。相比 Riak[3], Hibari 提供了强一致的保证，对开发者更加友好。微软云计算平台 Windows Azure[4]、 FDS[5]都使用链式复制协议提供强一致性保证。百度的新存储[6], 从它的架构图中以及提供的一致性保证中，可以推测也是使用链式复制协议。