rsync算法原理及使用 - Go语言中文社区

rsync算法原理及使用


如果服务器之间需要保持某些文件的一致,我们可以使用scp来复制,如果需要长期保持一致,可以配合crontab脚本来使用。但是此时我们有更优的方式,就是rsync+crontab来实现定时增量传输保持文件一致。

rsync功能很强大,网上的资料也都很全,这里做一些简单的汇总。

rsync原理

这一小节内容大幅度转载了 RSYNC 的核心算法 的内容,因为原文章写的太好,就不再狗尾续貂了,感兴趣的可以直接查看原文。他的翻译原文是:The rsync algorithm

rsynclinux下同步文件的一个高效算法,用于同步更新两处计算机的文件和目录,并适当利用查找文件中的不同块以减少数据传输。rsync的主要特点就是增量传输,只对变更的部分进行传送。

增量同步算法

假如我们现在需要同步两个文件保持一致,并且只想传送不同的部分,那么我们就需要对两边的文件做diff,但是这两个问题在两台不同的机器上,无法做diff。如果我们做diff,就要把一个文件传到另一台机器上做diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就是rsync的算法。

rsync同步算法

我们将同步源文件名称为fileSrc,同步目的文件叫fileDst

1. 分块Checksum算法

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

  1. 一个叫rolling checksum,是弱checksum32位的checksum
  2. 另一个是强checksum128位的,以前用md4,现在用md5 hash算法。

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

2. 传输算法

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

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

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

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

3. checksum查找算法

同步源端拿到fileDstchecksum数组后,会把这个数据存到一个hash table(特殊的数据结构体,可以快速检索)中,用rolling checksumhash,以便获得O(1)时间复杂度的查找性能。这个hash table16bits的,所以,hash table的尺寸是2的16次方,对rolling checksumhash会被散列到0 到 2^16 – 1中的某个整数值。

4. 比对算法

图片描述

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

5. 传输

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

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

rsync的使用

同样的,这一小节内容也是大幅度转载了 第2章 rsync(一):基本命令和用法 的内容,因为原文章很全面,感兴趣的可以直接查看原文。

rsync是实现增量备份的工具。配合任务计划,rsync能实现定时或间隔同步,配合inotifysersync,可以实现触发式的实时同步。它的目的是实现本地主机和远程主机上的文件同步(包括本地推到远程,远程拉到本地两种同步方式),也可以实现本地不同路径下文件的同步,但不能实现远程路径1到远程路径2之间的同步(scp可以实现)。

rsync同步过程中由两部分组成:决定哪些文件需要同步的检查模式以及文件同步时的同步模式。

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

如果仅有一个SRCDEST参数,则将以类似于"ls -l"的方式列出源文件列表(只有一个路径参数,总会认为是源文件),而不是复制文件。

源路径如果是一个目录的话,带上尾随斜线和不带尾随斜线是不一样的,不带尾随斜线表示的是整个目录包括目录本身,带上尾随斜线表示的是目录中的文件,不包括目录本身。

# 在/tmp目录下创建etc目录
[root@xuexi ~]# rsync -a /etc /tmp
# 不会在/tmp目录下创建etc目录,源路径/etc/中的所有文件都直接放在/tmp目录下
[root@xuexi ~]# rsync -a /etc/ /tmp

参考资料

  1. 酷壳-RSYNC 的核心算法:https://coolshell.cn/articles...
  2. The rsync algorithm:https://rsync.samba.org/tech_...
  3. 博客园-rsync(一):基本命令和用法:http://www.cnblogs.com/f-ck-n...
  4. 博客园-man rsync翻译(rsync命令中文手册): http://www.cnblogs.com/f-ck-n...
版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/weixin_34270865/article/details/88567385
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2020-06-27 23:46:56
  • 阅读 ( 1091 )
  • 分类:算法

0 条评论

请先 登录 后评论

官方社群

GO教程

猜你喜欢