基于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增量传输算法有比较详细的介绍[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增量下载的思路,制定云盘文件增量同步方案,如下图所示:

主要的方案设计要点是:

  • 计算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)

原文发表时间:2017-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python绿色通道

Python爬虫实战题荟萃

公众号Python爬虫系列文章基础写完了,所以就有了一些实战题目,有兴趣的可以来去围观一下.,为什么要进行Python项目实战 项目实战第二季

892
来自专栏Petrichor的专栏

Tensorflow源码 目录树

很多博客中提到的 models/(位于根目录下,该目录下存放这多个使用python实现的模型实例),我并没有看到。估计是最新版的Tensorflow源码取消了这...

751

如何构建智能反垃圾邮件的WordPress插件

在本文中,我们将为您展示如何构建一个利用机器学习来阻止垃圾邮件、成人邮件,甚至是负面评论的WordPress插件。该插件兼容WordPress 3...

2549
来自专栏怀英的自我修炼

考研数学-11-公式整理

匆匆忙忙到现在,才把公式整理完。接下来就是要消化这些公式,公式比较多,有100+个,希望借助Anki,这次能完全背熟6成。这也是个不小的挑战,继续二中吧。

681
来自专栏铭毅天下

干货 | Elasticsearch 趋势科技实战分享笔记

单一索引的问题: 1)不能更新Mapping。 比如:主分片数不可以修改(除非reindex)。 2)无法灵活、快速地扩展。 3)更适合固定、小型数据集。

981
来自专栏数据和云

深入并行:从生产者到消费者模型深度理解Oracle的并行

陈焕生 Oracle Real-World Performance Group 成员,senior performance engineer,专注于 OLTP...

2946
来自专栏听雨堂

轻松水印-批量提取exif信息加水印的工具

        今天整理了一下自己的照片,选了一部分准备到网上冲印出来,整理好的照片,都没有日期,我很希望能够有日期,以后看到照片立刻就能想起来。但是,如果手工...

2225
来自专栏WOLFRAM

Mma粉丝疑问【为啥不用个列表写短点呢?】

1714
来自专栏人工智能

如何构建智能反垃圾邮件WordPress插件

在本文中,我们将看到我们如何构建一个使用机器学习来阻止垃圾邮件,成人邮件,甚至是负面评论的WordPress插件。该插件与WordPress 3.6v或更高版本...

23210
来自专栏Golang语言社区

数据说话:Go语言的Switch和Map性能实测

在开发pgx(一个针对Go语言的PostgreSQL driver)的时候,有好几次我都需要在20多个代码分支间跳转。通常我会选用switch语句。还有个更加可...

3565

扫码关注云+社区