- 浏览: 43613 次
- 来自: 杭州
文章分类
最新评论
转自 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
发表评论
-
fedora系统删除多余内核
2013-01-22 21:32 1720查看本地系统安装的内核版本: $rpm -q ... -
Ubuntu change GNOME to XFCE problem
2012-12-14 16:10 824I'm now experiencing this probl ... -
Signal信号
2012-10-07 12:55 01) SIGHUP 本信号在用户终端连接(正常或非正常)结 ... -
Nginx
2012-09-20 23:38 0nginx (pronounced "engine ... -
Linux 灾难恢复
2012-09-19 21:57 0简介: Linux 发行版本 ... -
close_on_exec标志位
2012-09-06 21:33 2489close_on_exec是一个进程所有文件描述 ... -
Linux进程地址空间的探究解析
2012-08-08 23:35 0我们知道,在32位机器上 linux操作系统中的进程的地址空 ... -
git使用
2012-08-08 23:23 0我认为每个学过Git的人都应该做过类似这种笔记,因为Git命令 ... -
select, poll和epoll的区别
2012-07-31 21:34 0随着2.6内核对epoll的完全支持,网络上很多的文章和 ... -
linux多线程编程
2012-07-28 23:09 0本篇总结POSIX线程。可以用多个线程在单进程环境中执行多个任 ... -
select 和 epoll区别
2012-07-27 23:16 0最近有朋友在面试的时候被问了select 和epoll效率差的 ... -
echo显示变色
2012-07-24 17:07 0先来熟悉一下echo,如下: 名称 ... -
How to create and apply a patch with Git
2012-07-24 13:55 0Git is quite common now ... -
Facebook Folly源代码分析
2012-07-23 21:33 0Folly 是 Facebook 的一个开源C++11组件库, ... -
浅谈GCC预编译头技术
2012-07-23 09:51 893——谨以此文,悼念我 ... -
MySQL索引背后的数据结构及算法原理
2012-07-21 22:37 0转自 http://blog.jobbole.com/2400 ... -
patch文件的制作与使用
2012-07-01 18:43 2098创建补丁文件: 比如一个工程目录为project-o ... -
动态链接库版本管理
2012-06-28 20:24 0一、Linux的动态共享库版本控制实现 li ... -
ulimit命令使用
2012-06-22 03:56 805ulimit: usage: ulimit [-SHacdef ... -
负载均衡工具haproxy安装配置使用
2012-06-18 20:10 905一,什么是haproxy HAProxy提供高可用性、负 ...
相关推荐
基于内容分块的Rsync核心算法改进,刘彦,张茹,Rsync是一个在unix/linux下用于同步文件的高效算法,它能同步更新两处计算机的文件与目录,并且能通过查找出文件中的不同块来减少数据
rsync是unix/linux下同步文件的一个...这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。首先,我们先来想一下rs
rsync核心算法,同步机制,快速更新,快速定位与查找
pyrsync 是一个 Python 模块,它实现了 [rsync 算法] 1,用纯 Python 编写。它不是rsync 的包装器,而是一组通过 Python 应用完整 rsync 功能的函数。 最初的 rsync 规范要求使用 MD5 哈希,该模块的开发人员认为该...
基于java实现的,以rsync算法原理为基础的二进制文件差异比较处理
linux发行版中大多都自带rsync,不过版本比较低,一般都是2.6.X 在2.X的版本中,rsync备份时都是先列表再备份(添加或者删除),在处理大量文件时,会耗费比较多的内存。 备份的时候,rsync扫描到的每个文件(目录也...
ubuntu rsync中文乱码 window ubuntu rsync同步中文乱码.docx
rsync rpm安装包
windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类
rsync 是一个 Unix 系统下的文件同步和传输工具。..."rsync 算法",提供一个非常快速的档案传输,使本地和远端二部主机之间的 文件达到同步,它主要是传送二个文件的异动部份,而非每次都整份传送,因此 速度相当地快。
aix下rsync安装包,可用于AIX平台下与linux平台下的数据同步
-B, --block-size=SIZE 检验算法使用的块尺寸,默认是700字节 -e, --rsh=COMMAND 指定替代rsh的shell程序 --rsync-path=PATH 指定远程服务器上的rsync命令所在路径信息 -C, --cvs-exclude 使用和CVS一样的方法自动...
rsync 服务器架设方法 v0.1b (正在修订中) 作者: 北南南北 来自:Linuxsir.Org 摘要: rsync 是一个快速增量文件传输工具,它可以用于在同一主机备份内部的备分,我们还可以把它作为不同主机网络备份工具之用。...
AIX文件同步复制工具RSYNC,rsync-3.1.2 for aix6.1。。。
rsync_架设手册
librsync,主要包括rsync的算法,使用平台:linux
rsync常见错误及解决方法rsync常见错误及解决方法rsync常见错误及解决方法
RSYNC软件介绍: rsync是类unix系统下的数据镜像备份工具,从软件的命名上就可以看出来了——remote sync。它的特性如下: 可以镜像保存整个目录树和文件系统。 可以很容易做到保持原来文件的权限、时间、软硬链接...
rsync-3.1.2-4.el7.x86_64.rpm linux系统下rsync安装包
Rsync version 3.2.3