rsync算法原理及使用

4次阅读

共计 7045 个字符,预计需要花费 18 分钟才能阅读完成。

如果服务器之间需要保持某些文件的一致,我们可以使用 scp 来复制,如果需要长期保持一致,可以配合 crontab 脚本来使用。但是此时我们有更优的方式,就是 rsync+crontab 来实现定时增量传输保持文件一致。
rsync 功能很强大,网上的资料也都很全,这里做一些简单的汇总。

rsync 原理
这一小节内容大幅度转载了 RSYNC 的核心算法 的内容,因为原文章写的太好,就不再狗尾续貂了,感兴趣的可以直接查看原文。他的翻译原文是:The rsync algorithm。
rsync 是 linux 下同步文件的一个高效算法,用于同步更新两处计算机的文件和目录,并适当利用查找文件中的不同块以减少数据传输。rsync 的主要特点就是增量传输,只对变更的部分进行传送。
增量同步算法
假如我们现在需要同步两个文件保持一致,并且只想传送不同的部分,那么我们就需要对两边的文件做 diff,但是这两个问题在两台不同的机器上,无法做 diff。如果我们做 diff,就要把一个文件传到另一台机器上做 diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就是 rsync 的算法。

rsync 同步算法
我们将同步源文件名称为 fileSrc,同步目的文件叫 fileDst。
1. 分块 Checksum 算法
首先,我们会把 fileDst 的文件平均切分成若干个小块,比如每块 512 个字节(最后一块会小于这个数),然后对每块计算两个 checksum:

一个叫 rolling checksum,是弱 checksum,32 位的 checksum

另一个是强 checksum,128 位的,以前用 md4,现在用 md5 hash 算法。

为什么要这样?因为若干年前的硬件上跑 md4 的算法太慢了,所以,我们需要一个快算法来鉴别文件块的不同,但是弱的 adler32 算法碰撞概率太高了,所以我们还要引入强的 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 中的某个整数值。
4. 比对算法

取 fileSrc 的第一个文件块(我们假设的是 512 个长度),也就是从 fileSrc 的第 1 个字节到第 512 个字节,取出来后做 rolling checksum 计算。计算好的值到 hash 表中查。
如果查到了,说明发现在 fileDst 中有潜在相同的文件块,于是就再比较 md5 的 checksum,因为 rolling checksume 太弱了,可能发生碰撞。于是还要算 md5 的 128bits 的 checksum,这样一来,我们就有 2^-(32+128) = 2^-160 的概率发生碰撞,这太小了可以忽略。如果 rolling checksum 和 md5 checksum 都相同,这说明在 fileDst 中有相同的块,我们需要记下这一块在 fileDst 下的文件编号。
如果 fileSrc 的 rolling checksum 没有在 hash table 中找到,那就不用算 md5 checksum 了。表示这一块中有不同的信息。总之,只要 rolling checksum 或 md5 checksum 其中有一个在 fileDst 的 checksum hash 表中找不到匹配项,那么就会触发算法对 fileSrc 的 rolling 动作。于是,算法会住后 step 1 个字节,取 fileSrc 中字节 2 -513 的文件块要做 checksum,go to (1.) – 现在你明白什么叫 rolling checksum 了吧。
这样,我们就可以找出 fileSrc 相邻两次匹配中的那些文本字符,这些就是我们要往同步目标端传的文件内容了。

5. 传输
最终在同步源这端,我们的 rsync 算法可能会得到这个样子的一个数据数组,图中,红色块表示在目标端已匹配上,不用传输(注:我专门在其中显示了两块 chunk #5,代表数据中有复制的地方,不用传输),而白色的地方就是需要传输的内容(注意:这些白色的块是不定长的),这样,同步源这端把这个数组(白色的就是实际内容,红色的就放一个标号)压缩传到目的端,在目的端的 rsync 会根据这个表重新生成文件,这样,同步完成。
最后想说一下,对于某些压缩文件使用 rsync 传输可能会传得更多,因为被压缩后的文件可能会非常的不同。对此,对于 gzip 和 bzip2 这样的命令,记得开启“rsyncalbe”模式。

rsync 的使用
同样的,这一小节内容也是大幅度转载了 第 2 章 rsync(一):基本命令和用法 的内容,因为原文章很全面,感兴趣的可以直接查看原文。
rsync 是实现增量备份的工具。配合任务计划,rsync 能实现定时或间隔同步,配合 inotify 或 sersync,可以实现触发式的实时同步。它的目的是实现本地主机和远程主机上的文件同步(包括本地推到远程,远程拉到本地两种同步方式),也可以实现本地不同路径下文件的同步,但不能实现远程路径 1 到远程路径 2 之间的同步(scp 可以实现)。
rsync 同步过程中由两部分组成:决定哪些文件需要同步的检查模式以及文件同步时的同步模式。

检查模式是指按照指定规则来检查哪些文件需要被同步,例如哪些文件是明确被排除不传输的。默认情况下,rsync 使用 ”quick check” 算法快速检查源文件和目标文件的大小、mtime(修改时间)是否一致,如果不一致则需要传输。当然,也可以通过在 rsync 命令行中指定某些选项来改变 quick check 的检查模式,比如 ”–size-only” 选项表示 ”quick check” 将仅检查文件大小不同的文件作为待传输文件。rsync 支持非常多的选项,其中检查模式的自定义性是非常有弹性的。
同步模式是指在文件确定要被同步后,在同步过程发生之前要做哪些额外工作。例如上文所说的是否要先删除源主机上没有但目标主机上有的文件,是否要先备份已存在的目标文件,是否要追踪链接文件等额外操作。rsync 也提供非常多的选项使得同步模式变得更具弹性。

相对来说,为 rsync 手动指定同步模式的选项更常见一些,只有在有特殊需求时才指定检查模式,因为大多数检查模式选项都可能会影响 rsync 的性能。

rsync 四种工作方式
rsync 的基础语法为:rsync [OPTION…] SRC… [DEST]
支持的参数高达一百多个,最常用的选项组合是 ”avz”,即压缩和显示部分信息,并以归档模式传输。详细的可以参考 博客园 -man rsync 翻译(rsync 命令中文手册),下面是部分参数说明:
-v:显示 rsync 过程中详细信息。可以使用 ”-vvvv” 获取更详细信息。
-P:显示文件传输的进度信息。(实际上 ”-P”=”–partial –progress”,其中的 ”–progress” 才是显示进度信息的)。
-n –dry-run:仅测试传输,而不实际传输。常和 ”-vvvv” 配合使用来查看 rsync 是如何工作的。
-a –archive:归档模式,表示递归传输并保持文件属性。等同于 ”-rtopgDl”。
-r –recursive:递归到目录中去。
-t –times:保持 mtime 属性。强烈建议任何时候都加上 ”-t”,否则目标文件 mtime 会设置为系统时间,导致下次更新
:检查出 mtime 不同从而导致增量传输无效。
-o –owner:保持 owner 属性(属主)。
-g –group:保持 group 属性(属组)。
-p –perms:保持 perms 属性(权限,不包括特殊权限)。
-D:是 ”–device –specials” 选项的组合,即也拷贝设备文件和特殊文件。
-l –links:如果文件是软链接文件,则拷贝软链接本身而非软链接所指向的对象。
-z:传输时进行压缩提高效率。
-R –relative:使用相对路径。意味着将命令行中指定的全路径而非路径最尾部的文件名发送给服务端,包括它们的属性。用法见下文示例。
–size-only:默认算法是检查文件大小和 mtime 不同的文件,使用此选项将只检查文件大小。
-u –update:仅在源 mtime 比目标已存在文件的 mtime 新时才拷贝。注意,该选项是接收端判断的,不会影响删除行为。
-d –dirs:以不递归的方式拷贝目录本身。默认递归时,如果源为 ”dir1/file1″,则不会拷贝 dir1 目录,使用该选项将拷贝 dir1 但不拷贝 file1。
–max-size:限制 rsync 传输的最大文件大小。可以使用单位后缀,还可以是一个小数值(例如:”–max-size=1.5m”)
–min-size:限制 rsync 传输的最小文件大小。这可以用于禁止传输小文件或那些垃圾文件。
–exclude:指定排除规则来排除不需要传输的文件。
–delete:以 SRC 为主,对 DEST 进行同步。多则删之,少则补之。注意 ”–delete” 是在接收端执行的,所以它是在
:exclude/include 规则生效之后才执行的。
-b –backup:对目标上已存在的文件做一个备份,备份的文件名后默认使用 ”~” 做后缀。
–backup-dir:指定备份文件的保存路径。不指定时默认和待备份文件保存在同一目录下。
-e:指定所要使用的远程 shell 程序,默认为 ssh。
–port:连接 daemon 时使用的端口号,默认为 873 端口。
–password-file:daemon 模式时的密码文件,可以从中读取密码实现非交互式。注意,这不是远程 shell 认证的密码,而是 rsync 模块认证的密码。
-W –whole-file:rsync 将不再使用增量传输,而是全量传输。在网络带宽高于磁盘带宽时,该选项比增量传输更高效。
–existing:要求只更新目标端已存在的文件,目标端还不存在的文件不传输。注意,使用相对路径时如果上层目录不存在也不会传输。
–ignore-existing:要求只更新目标端不存在的文件。和 ”–existing” 结合使用有特殊功能,见下文示例。
–remove-source-files:要求删除源端已经成功传输的文件。
1. 本地文件系统上实现同步
rsync [OPTION…] SRC… [DEST]
2. 本地主机使用远程 shell 和远程主机通信
Pull: rsync [OPTION…] [USER@]HOST:SRC… [DEST]
Push: rsync [OPTION…] SRC… [USER@]HOST:DEST
3. 本地主机通过网络套接字连接远程主机上的 rsync daemon

Pull: rsync [OPTION…] [USER@]HOST::SRC… [DEST]
rsync [OPTION…] rsync://[USER@]HOST[:PORT]/SRC… [DEST]
Push: rsync [OPTION…] SRC… [USER@]HOST::DEST
rsync [OPTION…] SRC… rsync://[USER@]HOST[:PORT]/DEST
前两者的本质是通过管道通信,即使是远程 shell。而方式 (3) 则是让远程主机上运行 rsync 服务,使其监听在一个端口上,等待客户端的连接。
路径的格式可以是本地路径,也可以是使用 user@host:path 或 user@host::path 的远程路径,如果主机和 path 路径之间使用单个冒号隔开,表示使用的是远程 shell 通信方式,而使用双冒号隔开的则表示的是连接 rsync daemon。另外,连接 rsync daemon 时,还提供了 URL 格式的路径表述方式 rsync://user@host/path。
4. 远程 shell 临时启动一个 rsync daemon

rsync [options] –rsh=ssh auth_user@host::module
rsync [options] –rsh=”ssh -l ssh_user” auth_user@host::module
rsync [options] -e “ssh -l ssh_user” auth_user@host::module
rsync [options] -e “ssh -l ssh_user” rsync://auth_user@host/module
这不同于方式(3),它不要求远程主机上事先启动 rsync 服务,而是临时派生出 rsync daemon,它是单用途的一次性 daemon,仅用于临时读取 daemon 的配置文件,当此次 rsync 同步完成,远程 shell 启动的 rsync daemon 进程也会自动消逝。此通信方式的命令行语法格式同 ”Access via rsync daemon”,但要求 options 部分必须明确指定 ”–rsh” 选项或其短选项 ”-e”。
一些用法示例
# 将 /etc/fstab 拷贝到 /tmp 目录下
rsync /etc/fstab /tmp
# 将 /etc/cron.d 目录拷贝到 /tmp 下
rsync -r /etc/cron.d /tmp
# 将 /etc/cron.d 目录拷贝到 /tmp 下,但要求在 /tmp 下也生成 etc 子目
rsync -R -r /etc/cron.d /tmp
# 拷贝源路径较长,但只保留一部分目录结构,使用一个点代表相对路径的起始位置
rsync -R -r /var/./log/anaconda /tmp
# 对远程目录下已存在文件做备份,备份后缀为 ”~”,使用 ”–suffix” 指定后缀
rsync -R -r –backup /var/./log/anaconda /tmp
# 指定备份文件保存路径,默认将不会加备份后缀,使用 ”–suffix” 显式指定后缀
rsync -R -r –backup –backup-dir=/tmp/log_back /var/./log/anaconda /tmp
# . 指定 ssh 连接参数,如端口、连接的用户、ssh 选项等
rsync -e “ssh -p 22 -o StrictHostKeyChecking=no” /etc/fstab 172.16.10.5:/tmp
# 使用 ”–existing” 选项使得只更新目标端已存在的文件
rsync -r -v –existing /tmp/a/ /tmp/b
# “–ignore-existing” 更新目标端不存在的文件
rsync -r -v –ignore-existing /tmp/a/ /tmp/b
# “–remove-source-files” 删除源端文件
rsync -r -v –remove-source-files /tmp/a/anaconda /tmp/a/audit /tmp
# 使用 ”–exclude” 选项指定排除规则,排除那些不需要传输的文件。
rsync -r -v –exclude=”anaconda/*.log” /var/log/anaconda /var/log/audit /tmp
如果仅有一个 SRC 或 DEST 参数,则将以类似于 ”ls -l” 的方式列出源文件列表(只有一个路径参数,总会认为是源文件),而不是复制文件。
源路径如果是一个目录的话,带上尾随斜线和不带尾随斜线是不一样的,不带尾随斜线表示的是整个目录包括目录本身,带上尾随斜线表示的是目录中的文件,不包括目录本身。
# 在 /tmp 目录下创建 etc 目录
[root@xuexi ~]# rsync -a /etc /tmp
# 不会在 /tmp 目录下创建 etc 目录,源路径 /etc/ 中的所有文件都直接放在 /tmp 目录下
[root@xuexi ~]# rsync -a /etc/ /tmp
参考资料

酷壳 -RSYNC 的核心算法:https://coolshell.cn/articles…

The rsync algorithm:https://rsync.samba.org/tech_…

博客园 -rsync(一):基本命令和用法:http://www.cnblogs.com/f-ck-n…

博客园 -man rsync 翻译(rsync 命令中文手册):http://www.cnblogs.com/f-ck-n…

正文完
 0