Rsync中使用了一种滚动检验(Rolling Checksum)算法,用于快速计算数据块的检验值。它是一种弱校验算法,采用的是Mark Adler的adler-32校验,它的定义如下:
a(k, l) = (∑Xi) mod M
b(k, l) = (∑(l - i +1)Xi) mod M
s(k, l) = a(k, l) + 216b(k, l)
上面公式中,s(k, l)表示数据块Xk, ..., Xl的滚动校验值,为了简化以及计算速度考虑,M取值为216。这种校验计算公式具有一个非常关键的特性,那就是后续校验值可以通过递推关系高效地计算获得。
a(k+1, l+1) = (a(k, l) - Xk + Xl+1)) mod M
b(k+1, l+1) = (b(k, l) - (l - k +1)Xk + a(k+1, l+1)) mod M
s(k+1, l+1) = a(k+1, l+1) + 216b(k+1, l+1)
因此,给定X1, ..., Xn的校验值,X1以及Xn+1,我们就可以快速地计算出X2, ..., Xn+1校验值。这样,利用这种性质我们就可以高效地计算数据块连续校验值,大幅减少checksum计算量。dedup util中,我在CDC和Sliding-block文件分块处理中使用了该校验值算法,性能得到大幅提升。
附Adler32_checksum算法实现:
分享到:
相关推荐
基于内容分块的Rsync核心算法改进,刘彦,张茹,Rsync是一个在unix/linux下用于同步文件的高效算法,它能同步更新两处计算机的文件与目录,并且能通过查找出文件中的不同块来减少数据
rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的...
pyrsync 是一个 Python 模块,它实现了 [rsync 算法] 1,用纯 Python 编写。它不是rsync 的包装器,而是一组通过 Python 应用完整 rsync 功能的函数。 最初的 rsync 规范要求使用 MD5 哈希,该模块的开发人员认为该...
rsync 是一个 Unix 系统下的文件同步和传输工具。..."rsync 算法",提供一个非常快速的档案传输,使本地和远端二部主机之间的 文件达到同步,它主要是传送二个文件的异动部份,而非每次都整份传送,因此 速度相当地快。
linux发行版中大多都自带rsync,不过版本比较低,一般都是2.6.X 在2.X的版本中,rsync备份时都是先列表再备份(添加或者删除),在处理大量文件时,会耗费比较多的内存。 备份的时候,rsync扫描到的每个文件(目录也...
rsync rpm安装包
windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类windows rsync工具类
ubuntu rsync中文乱码 window ubuntu rsync同步中文乱码.docx
-c, --checksum 打开校验开关,强制对文件传输进行校验 -a, --archive 归档模式,表示以递归方式传输文件,并保持所有文件属性,等于-rlptgoD -r, --recursive 对子目录以递归模式处理 -R, --relative 使用相对路径...
aix下rsync安装包,可用于AIX平台下与linux平台下的数据同步
rsync 服务器架设方法 v0.1b (正在修订中) 作者: 北南南北 来自:Linuxsir.Org 摘要: rsync 是一个快速增量文件传输工具,它可以用于在同一主机备份内部的备分,我们还可以把它作为不同主机网络备份工具之用。...
rsync_架设手册
基于java实现的,以rsync算法原理为基础的二进制文件差异比较处理
该算法使用MD5加密哈希函数和滚动校验和哈希函数(Taylor的C3-C4)。 每次文件传输最多需要在原始文件上进行两次传递。 此文件传输算法与本文中描述的RSYNC应用程序不兼容。 最大文件大小为4GiB。 这仅是代码库形式...
AIX文件同步复制工具RSYNC,rsync-3.1.2 for aix6.1。。。
RSYNC软件介绍: rsync是类unix系统下的数据镜像备份工具,从软件的命名上就可以看出来了——remote sync。它的特性如下: 可以镜像保存整个目录树和文件系统。 可以很容易做到保持原来文件的权限、时间、软硬链接...
Rsync version 3.2.3
rsync常见错误及解决方法rsync常见错误及解决方法rsync常见错误及解决方法
rsync是用于
rsync-3.0.8源代码 Rsync version 3.0.8 released March 26th, 2011 Rsync version 3.0.8 has been released. This is a bug-fix release.