rsync 的核心算法

标签: 杂项资源 adler checksum Linux MD5 | 发表时间:2012-05-17 00:25 | 作者:陈皓
出处:http://coolshell.cn

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” 模式。

(全文完, 转载时请注明作者和出处

您可能也喜欢:

Linux/Unix 新手和专家教程

Unix 40年:Unix年鉴

Unix 40年:昨天,今天和明天

用Unix的设计思想来应对多变的需求

Unix传奇(下篇)
无觅

相关文章

相关 [rsync 核心 算法] 推荐:

rsync 的核心算法

- - 酷壳 - CoolShell.cn
rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输. rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送. rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递归拷贝.

翻译《The rsync algorithm》

- AWard - CSDN博客推荐文章
     最近在学习Rsync工具,在对Rsync算法大加赞赏之余,决定将《The rsync algorithm 》翻译,有不正之处 还请指正. 安德鲁Tridgell 保罗马克拉斯  部计算机科学 澳大利亚国立大学 堪培拉,ACT 0200,澳大利亚.        本报告介绍了将一台计算机上的文件内容同步到另一台机器上的文件的算法(同步后保证文件内容需要一致).

linux配置ssh+rsync

- - CSDN博客推荐文章
sftp    文件共享 类似ftp  ssh  secure file transfer client. scp    文件共享 类似cp. #PermitRootLogin yes    改成no 禁止root直接登录. #Port 22    改变ssh的默认端口号   要打开注释. 登录  ssh  gwyy@192.168.111.130  然后输入密码就好了.

Rsync同步使用

- - 开源软件 - ITeye博客
rsync是类unix系统下的数据镜像备份工具——remote sync. /etc/rsyncd/rsyncd.conf 是你刚才编辑的rsyncd.conf的位置. 也可以在/etc/rc.d/rc.local里加入让系统自动启动等. rsync -参数 用户名@同步服务器的IP::rsyncd.conf中那个方括号里的内容 本地存放路径 如:.

inotify-rsync实时同步脚本

- lostsnow - 无网不剩
rsync是linux下一款非常强大的同步工具,采用差异同步的方法,只上传文件/文件夹的不同部分,同时可以对上传部分先进行压缩,所以rsync的传输效率是很高的. 但rsync也有缺点,最大的问题就是每次执行rsync命令都会遍历目标目录,当文件不多时,这没什么问题,一旦文件数到了一定规模,那么每次遍历都会消耗很多资源.

rsync服务安装和配置

- - CSDN博客推荐文章
作者: javaboy2012. 如果安装了,则需要做如下配置和修改. 修改 /etc/xinetd.d/rsync 下的内容. disable = yes 改为 disable = no. 新建:vi /etc/rsyncd.conf.  注意:客户端必须执行同步命令触发同步操作..  要实现定时同步,可以通过crontab -e加入定时任务来实现..

[转]用rsync对网站进行镜像备份

- - 小鸥的博客
对系统管理员来说,平时的工作重心应该集中在维护系统正常运转,能够正常提供服务上,这里往往牵涉到一个数据备份的问题,在我所了解. 的情况中,有80%的系统管理员不是太关心自己服务器的安全性,但往往对备分镜像的技术相当感兴趣,但由于商业产品的软硬件价格都相当高. 这里准备介绍的rsync就是这样的软件,它可以满足绝大多数要求不是特别高的备份需求.

rsync的文件同步,复制,镜像,增量备份

- - 开心平淡对待每一天。热爱生活
rsync是一个linux下的:快速,多功能,远程(本地)文件复制工具. 官方网站:http://rsync.samba.org/. 维基百科:http://zh.wikipedia.org/wiki/Rsync. rsync是Unix下的一款应用软件,它能同步更新两处计算机的档案与目录,并适当利用差分编码以减少数据传输.

lsyncd实时同步搭建指南——取代rsync+inotify

- - SegmentFault 最新的文章
使用这两个组合的好处在于,它们都是最基本的软件,可以通过不同选项做到很精确的控制,比如排除同步的目录,同步多个模块或同步到多个主机. 搭建过程参考 Linux下同步工具inotify+rsync使用详解 或 这里. 后来听同事说 sersync 这么个工具可以提高同步的性能,也解决了同步大文件时出现异常的问题,所以就尝试了一下.

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

- - 美团点评技术团队
犀牛云盘是美团点评内部一个基于美团云的文件协作平台,核心是文件的结构化云存储以及上传和下载的体验优化. 文件同步是云盘功能的重要部分(包括文件内容的同步和文件增删的同步,应该有上传、下载、创建、删除等动作,但在本文的叙述中,主要关注文件内容的传输,即上传、下载),如何快速高效地进行文件同步,就成了云盘亟需解决的技术难题.