`

rsync 的核心算法

 
阅读更多

转自 http://www.linuxeden.com/html/sysadmin/20120518/124367.html

 rsync 是 unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与 其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递 归拷贝。rsync利用由 Andrew Tridgell 发明的算法。这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是 Unix的文化啊。

本 来不想写这篇文章的,因为原先发现有很多中文blog都说了这个算法,但是看了一下,发现这些中文blog要么翻译国外文章翻译地非常烂,要么就是介绍这 个算法介绍得很乱让人看不懂,还有错误,误人不浅,所以让我觉得有必要写篇rsync算法介绍的文章。(当然,我成文比较仓促,可能会有一些错误,请指 正)

问题

首 先, 我们先来想一下rsync要解决的问题,如果我们要同步的文件只想传不同的部分,我们就需要对两边的文件做diff,但是这两个问题在两台不同的机器上, 无法做diff。如果我们做diff,就要把一个文件传到另一台机器上做diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。

于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就出现了rsync的算法。

算法

rsync的算法如下:(假设我们同步源文件名为fileSrc,同步目的文件叫fileDst

 

1)分块Checksum算法 。首先,我们会把fileDst的文件平均切分成若干个小块,比如每块512个字节(最后一块会小于这个数),然后对每块计算两个checksum,

  • 一个叫rolling checksum ,是弱checksum,32位的checksum,其使用的是Mark Adler发明的adler-32 算法,
  • 另一个是强checksum,128位的,以前用md4,现在用md5 hash算法。

为什么要这样?因为若干年前的硬件上跑md4的算法太慢了,所以,我们需要一个快算法来鉴别文件块的不同,但是弱的adler32算法碰撞概率太高了,所以我们还要引入强的checksum算法以保证两文件块是相同的。也就是说,弱的checksum是用来区别不同,而强的是用来确认相同 。(checksum的具体公式可以参看这篇文章

2)传输算法。 同步目标端会把fileDst的一个checksum列表传给同步源,这个列表里包括了三个东西,rolling checksum(32bits)md5 checksume(128bits)文件块编号

我估计你猜到了同步源机器拿到了这个列表后,会对fileSrc做同样的checksum,然后和fileDst的checksum做对比,这样就知道哪些文件块改变了。

但是,聪明的你一定会有以下两个疑问:

  • 如果我fileSrc这边在文件中间加了一个字符,这样后面的文件块都会位移一个字符,这样就完全和fileDst这边的不一样了,但理论上来说,我应该只需要传一个字符就好了。这个怎么解决?
  • 如果这个checksum列表特别长,而我的两边的相同的文件块可能并不是一样的顺序,那就需要查找,线性的查找起来应该特别慢吧。这个怎么解决?

很好,让我们来看一下同步源端的算法。

3)checksum查找算法 。 同步源端拿到fileDst的checksum数组后,会把这个数据存到一个hash table中,用rolling checksum做hash,以便获得O(1)时间复杂度的查找性能。这个hash table是16bits的,所以,hash table的尺寸是2的16次方,对rolling checksum的hash会被散列到0 到 2^16 – 1中的某个整数值。(对于hash table,如果你不清楚,建议回去看大学时的数据结构教科书)

顺便说一下,我在网上看到很多文章说,“要对rolling checksum做排序”(比如这篇这篇 ),这两篇文章都引用并翻译了原作者的这篇文章 ,但是他们都理解错了,不是排序,就只是把fileDst的checksum数据,按rolling checksum做存到2^16的hash table中,当然会发生碰撞,把碰撞的做成一个链表就好了。这就是原文 中所说的第二步——搜索有碰撞的情况。

4)比对算法 。这是最关键的算法,细节如下:

4.1)取fileSrc的第一个文件块(我们假设的是512个长度),也就是从fileSrc的第1个字节到第512个字节,取出来后做rolling checksum计算。计算好的值到hash表中查。

4.2) 如果查到了,说明发现在fileDst中有潜在相同的文件块,于是就再比较md5的checksum,因为rolling checksume太弱了,可能发生碰撞。于是还要算md5的128bits的checksum,这样一来,我们就有 2^-(32+128) = 2^-160的概率发生碰撞,这太小了可以忽略。如果rolling checksum和md5 checksum都相同,这说明在fileDst中有相同的块,我们需要记下这一块在fileDst下的文件编号

4.3) 如果fileSrc的rolling checksum 没有在hash table中找到,那就不用算md5 checksum了。表示这一块中有不同的信息。总之,只要rolling checksum 或 md5 checksum 其中有一个在fileDst的checksum hash表中找不到匹配项,那么就会触发算法对fileSrc的rolling动作。于是,算法会住后step 1个字节,取fileSrc中字节2-513的文件块要做checksum,go to (4.1)  - 现在你明白什么叫rolling checksum了吧。

4.4)这样,我们就可以找出fileSrc相邻两次匹配中的那些文本字符,这些就是我们要往同步目标端传的文件内容了。

图示

怎么,你没看懂? 好吧,我送佛送上西,画个示意图给你看看(对图中的东西我就不再解释了)。

这 样,最终,在同步源这端,我们的rsync算法可能会得到下面这个样子的一个数据数组,图中,红色块表示在目标端已匹配上,不用传输(注:我专门在其中显 示了两块chunk #5,相信你会懂的),而白色的地方就是需要传输的内容(注意:这些白色的块是不定长的),这样,同步源这端把这个数组(白色的就是实际内容,红色的就放 一个标号)压缩传到目的端,在目的端的rsync会根据这个表重新生成文件,这样,同步完成。

最后想说一下,对于某些压缩文件使用rsync传输可能会传得更多,因为被压缩后的文件可能会非常的不同。对此,对于gzip和bzip2这样的命令,记得开启 “rsyncalbe” 模式。

参考文档 http://rsync.samba.org/tech_report/tech_report.html

分享到:
评论

相关推荐

    (175797816)华南理工大学信号与系统Signal and Systems期末考试试卷及答案

    内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。

    深圳建设施工项目安全生产奖惩管理制度.docx

    深圳建设施工项目安全生产奖惩管理制度

    离散数学课后题答案+sdut往年试卷+复习提纲资料

    离散数学课后题答案+sdut往年试卷+复习提纲资料

    自考04741计算机网络原理真题及答案及课件

    04741计算机网络原理 2018(尚德).pdf 13年试题(2套).pdf 2015年10月自考计算机网络原理04741试题及答案解析.docx 2021年4月自考04741计算机网络原理真题及答案.docx 2021年4月自考04741计算机网络原理试卷.bak.docx 计算机网络原理 课后题答案 全 李全龙版 自考04741.zip.zip 计算机网络原理课件 计算机网络原理课件.rar

    C++实现rpc,全程手写

    C++实现rpc,全程手写

    前端拿到的列表数据里id都一样的处理办法.txt

    前端拿到的列表数据里id都一样的处理办法.txt

    最新仿720云全景制作源码-krpano仿720云全景网站源码 新增微信支付+打赏+场景红包

    最新仿720云全景制作源码|krpano仿720云全景网站源码(新增微信支付+打赏+场景红包等)是一款基于php+mysql开发制作的全景在线制作网站源码,包含全景图片,全景视频等。数据存储全部存于OSS云端或本地,源码完全开源可自行二次开发。 环境要求:PHP5.5.X+MYSQL5.6.X+伪静态 熟悉linux系统推荐使用LAMP,web服务器最好使用apache,不要使用nginx(发布大全景图需要时间可能需要20多分钟, nginx超时机制不好控制)。 Windows系统推荐使用phpstudy。Liunx推荐宝塔控制面板apache 前端为HTML5开发,自适应手机版! 1、支持VR虚拟现实、全景视频、环物全景、说一说、点赞评论、重力感应、智能视频嵌入、场景切换热点、加载进度条、 地图导航、光晕flash特效、物体全景嵌入、场景自播、场景解说、雷达导航等业内前沿功能。 2、支持windows、Linux、Mac、安卓、IOS等几乎所有的系统观看。支持CDN图片转存,极大的减轻的服务器流量费用。 3、支持用户权限分配。方便会员制收费。

    YOLO算法-可乐罐子数据集-336张图像带标签-可乐.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    环境监测系统源代码全套技术资料.zip

    环境监测系统源代码全套技术资料.zip

    【编码解码】基于matlab罗利衰落信道编解码器设计【含Matlab源码 9930期】.zip

    Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

    四轮转向系统横摆角速度控制simulink仿真模型,利用滑模控制算法,基于八自由度车辆模型,控制有比较好的效果,附参考说明

    四轮转向系统横摆角速度控制simulink仿真模型,利用滑模控制算法,基于八自由度车辆模型,控制有比较好的效果,附参考说明。

    YOLO算法-工作场所安全隐患数据集-859张图像带标签-倒下的工人-配备个人防护装备的工人-无个人防护装备的工人-火.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    自学考试02331数据结构试题及答案2021-2022

    02142数据结构导论历年真题及答案(2012-2018共13套).rar 02331数据结构历年真题共267页2009.10-2019.4.rar 24数据结构201704_8.pdf 25数据结构201710_10.pdf 26数据结构201804_11.pdf 27数据结构201810_9.pdf 全国2021年04月高等教育自学考试02331数据结构试题及答案.docx 全国2022年04月高等教育自学考试02331数据结构试题及答案.docx 数据结构-课件.rar 第l六讲.ppt 第一讲.ppt 第七讲.ppt 第三讲.ppt 第九讲.ppt 第二讲.ppt 第五讲.ppt 第八讲.ppt 第四讲.ppt

    验收确认单表格.docx

    验收确认单表格.docx

    内存搜索工具(易).rar

    内存搜索工具(易).rar

    饮食管理系统项目源代码全套技术资料.zip

    饮食管理系统项目源代码全套技术资料.zip

    计算机视觉项目:Swin-Transformer 【tiny、small、base】模型实现的图像识别项目:番茄病害图像分类

    【项目简介】 代码主干网络采用Swin-Transformer 家族系列,包括【tiny、small、base】三种模型。pretrained和freeze_layers参数为是否采用官方预训练模型和是否仅训练分类头。为了做对比消融试验,优化器采用了Adam和SGD、AdamW三种。损失函数采用多类别的交叉熵、学习率优化策略采用cos余弦退火算法 【评估网络】 评估的指标采用loss和准确率(accuracy),分别会在训练集和验证集上进行评估、输出、绘制曲线图像。同时会在训练集、验证集进行一系列评估,包含混淆矩阵、recall、precision、F1 score等等曲线图像,以及recall、precision、F1 score、特异度的输出信息等等。 【具体各类别的指标在json文件中查看】 【如果想要更换数据集训练,参考readme文件】 【本项目为8种番茄病害图片(约4k张数据),包含数据集和标签,可以一键运行】

    (177121232)windows电脑下载OpenHarmony鸿蒙命令行工具hdc-std

    windows电脑下载OpenHarmony鸿蒙命令行工具hdc_std。内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。

    小程序毕业设计项目-音乐播放器

    本项目可以作为小程序毕设项目,主要功能为音乐播放器,主要功能是:可以播放歌曲(采用mp3网络连接实现)、专辑封面播放时可以旋转,能够实现开始和暂停播放,可以点击下一首歌曲,主页面实现动态轮播图

    考研学习分享-JAVA-基于Vue+SpringBoot的考研学习分享平台设计与实现(毕业论文)

    考研学习分享功能的描述可以涵盖以下几个主要模块,旨在为考研学生提供一个互动、资源共享、经验交流的平台: 1. 用户注册与个人信息管理 学生可以通过邮箱或手机号注册账户,填写个人信息,如姓名、专业、目标院校等。 用户可设置学习目标和进度,方便记录自己的学习历程。 2. 学习资料共享 用户可以上传、下载考研相关学习资料,如教材、真题、笔记、复习计划等。 提供文件分类功能,按学科、院校、难度等进行整理,方便用户查找。 支持多种文件格式,如PDF、Word、Excel、图片等。 3. 复习经验分享 学生可以发布自己的复习经验文章,分享复习方法、备考心得、时间管理技巧等。 提供文章评论和互动功能,其他学生可以点赞、评论、提问,促进经验交流。 设置专栏或专题,帮助学生快速找到自己感兴趣的复习内容。 4. 考研小组与社交功能 学生可以创建或加入学习小组,组内成员可共享资料、讨论问题、互相鼓励。 提供私信、群聊功能,方便学员在小组内进行实时讨论和交流。 支持设置小组学习目标和定期检查进度,增加学习动力。 5. 在线课程与讲座 提供考研各科目(如英语、数学、政治等)的在线课程资源,用户可以报名参加。

Global site tag (gtag.js) - Google Analytics