文档章节

rsync 核心算法

s
 sunhongxi
发布于 2014/10/27 10:56
字数 1378
阅读 19
收藏 0

sync的算法如下:(假设我们同步源文件名为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://coolshell.cn/articles/7425.html

上一篇: Impala与Hive的比较
下一篇: hive 流量过程表
s
粉丝 2
博文 7
码字总数 3845
作品 0
朝阳
程序员
私信 提问
rsync 的核心算法

本文转载自酷壳coolshel 作者 陈皓 rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部...

aoniao
2012/05/17
685
3
rsync 的核心算法

rsync是 unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与 其他大部分类似程序或协定中所未见的重要特...

虫虫
2012/05/18
7.8K
19
Rolling Hash about the Rsync

今天看文献看到一个有趣的算法—Rolling Hash,这个算法可以更新在不同的machine上的两个“similar”的文件,也叫做rsync algorithm,rsync顾名思义:remote sync,远程镜像同步备份,现在在...

chambai
2014/01/16
0
0
Linux学习----文件的使者-Rsync(马哥教育原创)

文件的使者-Rsync(原创) Rsync是Unix下的一款应用软件,它能同步更新两处计算机的文件与目录,并适当利用差分编码以减少数据传输。rsync中一项与其他大部分类似程序或协议中所未见的重要特性...

Py爱好
2018/08/02
0
0
关于 rsync 中: 和 :: 及 rysnc 和 ssh 认证协议的区别

今天上午同事问我 rsync -av /SRC root@172.17.256.211:36000::/DEST 为何报 port 22 refused 的错误? 因为我们机器都是修改了 ssh 端口的,默认22端口是登录不上ssh的, 同事的本意是想修改...

大数据之路
2012/08/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

android6.0源码分析之Camera API2.0简介

前面几篇主要分析的是android Camera API1.0的架构以及初始化流程,而google在android5.0(Lollipop)开始对Camera的架构进行了调整,为了适应HAL3,新添加实现了CameraDeviceClient,而Camer...

天王盖地虎626
10分钟前
0
0
Flutter for Web 开发环境搭建与验证

最新的Flutter 1.5.4已经支持Web开发,这个教程将介绍如何在Linux、windows和Mac下 安装Flutter web开发环境:安装Flutter SDK和Flutter Web构建工具,并利用Flutter Web 演示代码来验证开发...

汇智网教程
14分钟前
0
0
微信小程序

张小龙的定义 1、不需要下载安装即可使用 实际上也有下载和安装的流程,只不过安装包很小<2M,使得这两个过程很短,不易感知到 2、用户"用完即走"不用关心是否安装太多应用 适用于偶尔使用一...

星闪海洋
39分钟前
2
0
JsonUtil工具类

使用的是fastJson package util; import java.io.IOException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.HashMap; import java.util.Map; import com.f......

嘿嘿嘿IT
40分钟前
2
0
Mementor模式

//个人感觉就想当于把某个类的某部分或全部复制一份保存在另一个类中,然后在有必要的时候用保存的复制的那部分来恢复之前的某种状态 https://blog.csdn.net/syc434432458/article/details/5...

南桥北木
45分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部