rsync文件实时同步_从文件同步rsync算法谈起

之前在某个产品中使用了Gossip算法进行数据库数据的同步，但是在新的产品中有个需求，就是当文件变化时，(由于文件比较大，比较多)支持增量推送到文件服务器上。于是想到了Unix下的rsync算法，本文也是拜读了很多大佬的作品，从自己理解的角度整理出来。关于rsync算法的原文请阅读

https://rsync.samba.org/tech_report/tech_report.html

1、同步技术

一般除了rsync增量同步外，还有一种scp的同步方式，用于将文件上传和下载，类似于ftp协议。scp username@servicename:/path/filename /var/localdir举例：比如使用这个命令scp root@192.168.0.1:/path/ClassPath.xml /var/localdir。意思就是将192.168.0.1服务器上面的Classpath.xml文件下载到本地的var/localdir文件夹中。scp /var/filename username@servicename:/path举例：比如使用scp /a.xml root@192.168.0.1:/path ,意思就是将本地的a.xml文件上传到192.168.0.1 服务器的path路径下，用户名root。

      当然了，还可以在scp命令的后面加上-r 参数，用于下载和上传整个文件夹。类似与rmdir 命令递归删除文件夹了。在使用scp的前提是对端服务器开启文件的写入权限。

    关于ftp这种应用层的上传下载协议，我也在项目中用过，这里不再叙述，推荐一个开源组件libcurl，可以支持多种协议，使用也比较简单。

2、rsync算法原理

      一般情况下，如果我们要同步的文件只想传不同的部分，我们就需要对两边的文件做差异对比，但是这两个问题在两台不同的机器上无法做对比。如果我们做对比，就要把一个文件传到另一台机器上做对比，但这样一来，我们就传了整个文件，这与我们只想传输不同部的初衷相背。

    rsync的算法是让这两边的文件不见面，但还能知道它们间有什么不同。

    rsync的算法如下：(假设我们同步源文件名为fileSrc，同步目的文件叫fileDst)

1)分块Checksum算法。首先，我们会把fileDst的文件平均切分成若干个小块，比如每块512个字节(一般在2的整数次方，比如512，1024，最后一块会小于这个数)，然后对每块计算两个checksum，

• 一个叫rolling checksum，是弱checksum，32位的checksum，其使用的是Mark Adler发明的adler-32算法，

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

这里使用两个checksum算法，是因为我们需要一个快算法来鉴别文件块的不同，但是弱的adler32算法碰撞概率太高了，所以我们还要引入强的checksum算法以保证两文件块是相同的。也就是说，弱的checksum是用来区别不同，而强的是用来确认相同。

2)传输算法。同步目标端会把fileDst的一个checksum列表传给同步源，这个列表里包括了三个东西，rolling checksum(4字节，32bits),

md5 checksume(16字节，128bits)，文件块编号。

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中的某个整数值。

   算法的流程如下所示：

   首先从目的文件获取了文件块的checksum，然后开始计算源端的文件。

1)取fileSrc的第一个文件块(我们假设的是512个长度)，也就是从fileSrc的第1个字节到第512个字节，取出来后做rolling checksum计算。计算好的值到hash表中查。

2)如果查到了，说明发现在fileDst中有潜在相同的文件块，于是就再比较md5的checksum，因为rolling checksume太弱了，可能发生碰撞。于是还要算md5的128bits的checksum，这样一来，我们就有 2^-(32+128) = 2^-160的概率发生碰撞，这太小了可以忽略。如果rolling checksum和md5 checksum都相同，这说明在fileDst中有相同的块，我们需要记下这一块在fileDst下的文件编号。

3)如果fileSrc的rolling checksum 没有在hash table中找到，那就不用算md5 checksum了。表示这一块中有不同的信息。总之，只要rolling checksum 或 md5 checksum 其中有一个在fileDst的checksum hash表中找不到匹配项，那么就会触发算法对fileSrc的rolling动作。于是，算法会住后移动1个字节，取fileSrc中字节2-513的文件块要做checksum，然后执行step1。

4)这样，我们就可以找出fileSrc相邻两次匹配中的那些文本字符，这些就是我们要往同步目标端传的文件内容了。

     经过算法的计算和对比，将不同的文件和文件块组成一个新的列表发送到fileDst端，fileDst端收到新的文件列表，则进行组装成新的文件。最终两个文件同步成功。

3 总结

      rolling checksum算法给我们提供了一种增量同步的思路。通过循环校验查找，找到相同的块。最终将不同的数据同步过去即可，极大的减少了网络传输的带宽。

总结

以上是生活随笔为你收集整理的rsync文件实时同步_从文件同步rsync算法谈起的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。