基于rsync的文件增量同步方案

背景

犀牛云盘是美团点评内部一个基于美团云的文件协作平台,核心是文件的结构化云存储以及上传和下载的体验优化。文件同步是云盘功能的重要部分(包括文件内容的同步和文件增删的同步,应该有上传、下载、创建、删除等动作,但在本文的叙述中,主要关注文件内容的传输,即上传、下载),如何快速高效地进行文件同步,就成了云盘亟需解决的技术难题。本文阐述的方案就是在这种场景下提出来的,我们希望通过rsync增量传输算法,来提高文件同步速度。但原始rsync算法在高并发的服务上会存在性能问题,所以本方案也借鉴zsync的思路,做了优化。

rsync增量传输算法

rsync增量传输算法首度发表于1996年6月19日,原始作者为Andrew Tridgell与Paul Mackerras [1]。实现增量传输的主要过程,就是差异检测和差异数据组织及传输,前者是rsync增量传输算法的核心。

rsync增量传输算法是一种滑动块差异检测算法。以检测文件A和B的差异为例,首先对A按固定长度L划分为若干块,并对每一块生成弱摘要(Adler-32:速度快)和强摘要(MD5:鉴别度高),然后对B从第一个字节开始,以长度为L的滑动窗口,遍历整个文件,计算每个窗口块的弱、强摘要,并与A中的摘要值进行比较,弱、强摘要都相同者,即视为相同数据块,否即为差异块。如下图所示:

基于rsync的文件增量同步方案

rsync增量传输算法主要有两个特点:

  • 固定块摘要和滑动块检测的结合,提高命中率;
  • 弱摘要和强摘要的结合,加快比对速度。

酷壳网有篇文章对rsync增量传输算法有比较详细的介绍[2]。

rsync性能优秀且简单容易理解,作者用了两年研究出来,而使用者只用两小时就可以理解了。

rsync工具的工作机制

rsync增量传输算法使用最多的场景就是类UNIX系统上的rsync同步工具。该工具非常流行,被应用于大量的文件传输场景。比如现在美团点评发布系统就用rsync同步发布机器上编译后文件到生产机器上的。

rsync工具的工作机制,如下阐述。

目标:主机A、B,A要同步文件F-new给B,B上已有文件F-old,跟F-new相似度高。

步骤:

  • B对文件F-old分块计算强弱摘要,链接起来生成sign文件,此过程简称sign,把sign文件发送给A;
  • A根据sign文件和本地文件F-new比较,滑动块进行差异检测,把相同块的序号和不同块的内容拼装为delta文件,此过程也简称delta,发送给B;
  • B拿到delta文件,并与本地源文件F-old结合,生成F-new文件,此过程简称patch。

如果目标是B要同步文件给A,那就是步骤中把A、B换一下位置。

小结:同步的双方A、B基本是对等的,一方计算sign和合并文件,一方计算delta。 双方都有较大计算量,这在一个服务器多客户端场景下,服务端压力会过大。

zsync工具的工作机制

zsync是Ubuntu上使用比较多的工具,主要用于分发Ubuntu的安装镜像ISO文件。zsync是rsync的一种变体,对rsync增量传输算法有所改造,并且基于HTTP协议,适合广域网应用[3]。

zsync适用的场景是:大文件、变动少、一个分发点(服务端)、大量下载(客户端)。

使用步骤为:

  • 发布方制作好新版系统安装ISO镜像(大文件),同时生成对应的sign文件,两者都提供HTTP下载地址;
  • 客户端如果没有旧版本镜像,那么全量下载ISO文件;
  • 客户端如果有旧版本镜像,那么下载sign文件,自己计算delta文件,同时自己合并出新版本镜像。合并过程是,发现相同块就从本地旧版本读取,不同的块,则使用HTTP Range的方式从服务端下载。

zsync算法,使发布方(服务端)只要一次签名文件的计算即可支撑大量客户端增量下载,缓解服务端压力。需要增加的签名文件存储空间,也是成本很低的。

云盘的文件增量同步方案

基于上面介绍的rsync工具的传输步骤,并借鉴zsync增量下载的思路,制定云盘文件增量同步方案,如下图所示:

基于rsync的文件增量同步方案

基于rsync的文件增量同步方案
主要的方案设计要点是:

  • 计算sign和计算delta都在PC客户端进行,服务器端只做必不可少的合并处理,同时客户端根据结算结果,如果发现命中率低,也可以选择全量传输;
  • 增量下载时,借鉴zsync,也把计算量放在PC客户端进行,这个实现也需要参考zsync对rsync原算法进行一定改造;
  • 浏览器处理能力有限,无法实现增量同步;
  • 服务端需要存(一定量的)sign文件、delta文件;
  • 服务端还要合并出新文件并存储,主要是基于这些考虑:
    ① 防止delta管理的复杂;
    ② 有完整文件,下载简单,浏览器下载可以直接通过mss(美团云对象存储服务,犀牛云盘的文件数据的存储工具) tempurl下载;
    ③ 增量同步出问题还可以降级服务,保证基本功能正常。

方案还存在的问题

  1. 碎片块,这是rsync增量传输算法特点造成的,由于是滑动窗口检测,在两个相同块之间,有可能存在一个长度不定的差异块。如果相同块不连续,就会形成一系列碎片块。减少滑动块长度(也即是sign计算的固定块长度),可以提高命中率、减少碎片块,但计算量也随着加大,sign文件也变大,可能得不偿失。所以只能根据试验情况,取一个折衷的块长度。目前我们采取默认2KB的块长度,对每块生成4B弱摘要,16B强摘要,那么sign文件与源文件的长度比=20/2K=1/100(这里忽略sign文件头固定8B的小量影响)。

  2. 对JPEG、视频等类型的文件,局部改变可能性小,且文件一般比较大,差异检测计算量大但命中率低,不进行增量同步尝试。

  3. 基于以上设计方案,服务器端要做合并patch操作,但合并操作的时间和资源消耗还是挺大的,需要做:

  • 接收并缓存delta文件;
  • 从底层存储(mss)下载旧文件;
  • 合并文件;
  • 向底层存储上传新文件。

该问题可从以下两方面做优化尝试:

  • 改进点1:合并文件流式处理,但网络的流对流处理容易不稳定。而旧文件还得全部下载,因为有随机读;
  • 改进点2:把合并过程作为异步处理,接收delta文件后,就返回给客户端“成功”,服务端慢慢合并,但如果失败了,很难有手段再重新从客户端取到正确文件,需要借助消息推送辅助。

算法的后续优化项

第一,rsync工具及类库中为了做到极致的最小传输量,sign文件头没有保存源文件长度,delta文件块长度用不同数量的Byte来表示。建议修改。前者保存文件长度,方便做类似zsync的改造(zsync算法起作用需要整个文件长度)和下载时的长度校验;后者用固定数量Byte表示长度(每个长度值都要使用多个Byte),虽然多消耗一些传输量,但编码简单,处理效率高。

第二,对某些文件格式已知的文件,可以根据格式特点,做变长分块。比如MS Office的Open XML格式,其实是Zip组织方式,可以按Zip协议的分界标识来分块,提高命中率,但这需要对rsync增量传输算法进行修改。

第三,结合CDC(content-defined chunking)做变长分块检测,这方面属于研究的方向,但目前还没有比较通用可靠的解决方案。下面根据找到的资料做一下描述:

CDC算法是一种变长分块算法,它应用数据指纹(如Rabin指纹[5])将文件分割成长度大小不等的分块策略。与定长分块算法不同,它是基于文件内容进行数据块切分的,因此数据块大小是可变化的。算法执行过程中,CDC使用一个固定大小(如48字节)的滑动窗口对文件数据计算数据指纹。如果指纹满足某个条件,如当它的值模特定的整数等于预先设定的数时,则把窗口位置作为块的边界。

CDC算法可能会出现病态现象,即指纹条件不能满足、块边界不能确定,导致数据块过大。实现中可以对数据块的大小进行限定,通过设定上下限来解决这种问题。CDC算法对文件内容变化不敏感,插入或删除数据只会影响到较少的数据块,其余数据块不受影响。CDC算法也有缺陷,数据块大小的确定比较困难,粒度太细则开销太大,粒度过粗则检测效果不佳。如何两者之间权衡折衷,这是一个难点。

相比CDC,rsync是滑动块算法。滑动块算法对插入和删除问题处理非常高效,并且能够检测到比CDC更多的冗余数据,它的不足是容易产生数据碎片。如果能结合两者的优点,那就能更高效做差异检测,比如上面提到的Open XML格式按Zip标记分界的思路,其实是CDC思路的一个特例。

参考文档

  1. Tridgell A, Mackerras, P. The rsync algorithm. The Australian National University, 1996.
  2. rsync核心算法.
  3. zsync — Optimised rsync over HTTP.
  4. Rabin指纹.
  5. 刘爱贵. 数据同步算法研究. CSDN博客.




发现文章有错误、对内容有疑问,都可以关注美团点评技术团队微信公众号(meituantech),在后台给我们留言。我们每周会挑选出一位热心小伙伴,送上一份精美的小礼品。快来扫码关注我们吧!

基于rsync的文件增量同步方案

上一篇:使用IDEA创建Maven工程,集成SpringMVC和MyBatis框架,完成简单的签到程序


下一篇:API 面试四连杀:接口如何设计?安全如何保证?签名如何实现?防重如何实现?