rsync 算法
场景:假设有两台计算机 CA和 CB , CA 上有文件 FA , CB 上有文件 FB , FA 和 FB 是“相似的”。 CA 和 CB 通过低速通信链接连接,现在要把 FA 同步到 FB 上去,如何才能高效同步。
rsync 算法包含下面的步骤:
1、 CB把 FB 分割成固定大小 S 字节的块,最后一块可能少于 S 字节;
2、 对于每个块,CB 计算两个校验和:一个弱的“滚动” 32 位校验和和一个强的 128 位 MD4 校验和。
3、 CB把这些校验和发给 CA 。
4、 CA搜索 FA 来查找 S 大小的块,这些块与 CB 的块有相同的弱和强校验和。这可以通过一次遍历来完成,通过利用滚动校验和的特殊属性。
5、 CA给 CB 发送一序列指令来构建一个 FA 的拷贝。每个指令要么指向 FB 的一个块,要么是文字数据。文字数据只用于发送 FA 的那些不匹配 FB 块的区域。
最终结果是 CB有了 FA 的拷贝,但只发送了那些在 FB 里找不到的数据。
这个算法只要求一个来回,减少了网络延迟。
这个算法的最重要的细节是滚动校验和 和 associated multi-alternate search mechanism which allows the all-offsets checksum search to proceed very quickly.
这里说到的多选择搜索机制,在实现时用HashMap + List。
算法图示
此图来自 酷壳: “rsync 的核心算法”, 见参考资料
红色的是匹配的块,白色的是实际传输的内容。
滚动校验和
rsync算法使用的弱滚动校验和 须具有非常廉价地根据 X 1 .. X n 和字节值 X 1 和 X n +1 快速计算 X 2 .. X n +1 的校验和的性质。
rsync算法使用弱校验和算法是由 Mark Adler 发明的adler-32 校验和。校验和定义如下:
实现
在实现时,MD5 算法在 Java 里是现成的,滚动校验和也是不难实现。网上其他的博客提到在计算块的滚动校验和时, a 的初始值是 1 ,在我实现时发现那是错的, rsync 的报告文档没说要这样,报告给出的算法公式也没要求,误导我费了不少时间。
在实现过程中,我觉得比较难的在于 根据 checksum 流计算 diffitem 流,也是我要在这里想说的。
下面这两个图所表示的是基于避免把整个文件读入内存实现的,如果不考虑内存占用,把整个文件读入内存,只需要看第 2 张流程图。在把文件部分读入内存时,第 2 张图是第 1 张图红色字体部分的逻辑。
在实现有两个缓存:
buffer:缓存,容量是块的N倍,直接使用数组。
outBuffer:新增数据块的缓存,是ByteArrayOutputStream的实例。
还有一些int类型的充当指针的变量。
流程图说明:
确保滚动查找数据足够: 判断缓存里是否还有有效的数据,并返回boolean 值表示流是否结束。如果有,返回 false ,如果没有,调用 为块匹配填充缓存,并返回调用结果。
为块匹配填充缓存: 整理并填充缓存,返回boolean 值表示流是否结束。首先把 roll 过的不属于当前块的数据写入新增数据缓存,然后把当前块拷贝到缓存的首部,然后从文件流读取数据填充剩余的缓存空间,并返回表示流是否结束的 boolean 值。
具体源代码见github : https://github.com/wen866595/jrsync
参考资料
http://rsync.samba.org/tech_report/tech_report.html
rsync 的核心算法 | 酷壳 - CoolShell.cn
欢迎关注我的微信公众号: coderbee笔记。
相关推荐
基于内容分块的Rsync核心算法改进,刘彦,张茹,Rsync是一个在unix/linux下用于同步文件的高效算法,它能同步更新两处计算机的文件与目录,并且能通过查找出文件中的不同块来减少数据
yajsync, rsync协议的Java实现 yajsyncyajsync是 rsync的一个端口,用Java编写。当前yajsync支持rsync协议版本 30.0的最小子集。当前实现的rsync选项:增量递归( R,--recursive )保留所有者( -o,
rsync是unix/linux下同步文件的一个...这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。首先,我们先来想一下rs
基于java实现的,以rsync算法原理为基础的二进制文件差异比较处理
rsync 配置与使用实现 rsync 配置与使用实现 rsync 配置与使用实现
rsync安装部署-实现两台计算机节点的实时产生的数据文件同步。包含:安装部署手册和软件安装包!
pyrsync 是一个 Python 模块,它实现了 [rsync 算法] 1,用纯 Python 编写。它不是rsync 的包装器,而是一组通过 Python 应用完整 rsync 功能的函数。 最初的 rsync 规范要求使用 MD5 哈希,该模块的开发人员认为该...
linux下Rsync+sersync实现文件数据实时同步
rsync+inotify实现实时同步 随着应用系统规模的不断扩大,对数据的安全性和可靠性也提出的更好的要求,rsync在高端业务系统中也逐渐暴露出了很多不足,首先,rsync同 步数据时,需要扫描所有文件后进行比对,进行差...
摘要: rsync 是一个快速增量文件传输工具,它可以用于在同一主机备份...本文主要讲述的是如何自架rsync服务器,以实现文件传输、备份和镜像。相对tar和wget来说,rsync 也有其自身的优点,比如速度快、安全、高效。
rsync+inotify实现服务器之间目录文件实时同步
Rsync+sersync实现数据实时同步备份,这个很有用,大家实践实践吧,这个勒索病毒横行的年代,懂得保护自己数据
Linux_rsync_配置具体实现说明
Rsync实现文件备份同步,定时备份,同步数据,如果源地址文件删除,目标地址也会删除,我们公司就用rsync同步图片资源,很实用。
用rsync实现网站镜像和备份
在对rsync服务器配置结束以后,下一步就需要在客户端发出rsync命令来实现将服务器端的文件备份到客户端来。rsync是一个功能非常强大的工具,其命令也有很多功能特色选项。 一、rsync的六种工作模式: 1.1、拷贝本地...
rsync+inotify实现服务器之间文件实时同步,内包含部署所需jar包和配置文件
Ubuntu Server Rsync服务端与Windows cwRsync客户端实现数据同步
rsync+inotify实现数据的实时备份
用Rsync实现Linux文件系统备份.pdf