Dropbox差异同步算法rsync及其改进算法原理
近来研究Dropbox,想看看它的同步怎么做的,没找到官方资料,不过据推测应该用的就是rsync,于是,看看鼎鼎大名的rsync是怎么实现的吧。
rsync算法要解决的问题很简单:A和B两个文件在两台服务器中,要将A同步到与B一致,要求尽量减少同步带来的网络传输开销。
rsync基本算法
先说基本的rsync算法,并不复杂,简单的说是三步:
1、按固定大小将A分为多块,每块都计算出一个32位的滚动哈希值和一个128位的MD4(有些也用MD5),发给B一端。
2、B一端从位置0开始按的同样块大小的滚动哈希值,查找看是否命中A给的某个滚动哈希值,若匹配,则表明B文件中的这块内容与对应的A中的那块内容很可能是一致的,但由于32位的哈希值强度不够,因此再计算MD4,若还是匹配,则确认是一致内容,这时B发给A端匹配的段号。对于那些不能匹配的内容,则发给A端原始内容。
3、A端得到B端给的匹配信息,构造一个与B一致的复本,若是匹配的块,则拷贝原A文件中对应的块,若是不匹配内容则追加之。
滚动哈希值的设计基于Adler32算法,使得2~K+1字节的哈希可以根据1~K字节哈希和1、K+1字节的内容快速计算得到,这可以提高从位置0开始依次计算滚动哈希值的效率。
据试验一般来说块大小取500~1000字节效果比较好。
rsync初级优化
在上述基本算法之上可以进行一些初级的优化,比如:
1、传输数据再做压缩
2、先用更短小的哈希值作同步,然后比较同步后二者MD5,如果不一样,再换用更长的哈希值,如此在大多数情况下可以减小哈希值的传输开销。因为如果用500字节的块大小的话,一个32位的滚动哈希值和一个128位的MD4会占用原始数据1/25的开销,并不太小
基于rsync的改进算法
基于rsync的改进算法主要有多轮rsync和本地rsync两个。
多轮rsync的原理简单的说就是先用较大的块大小按rsync的方法处理一轮,但只传输那些命中的块,那些没命中的数据称为“空洞”,按较小的块大小再按rsync的方法又处理一轮,如此双可能产生规模更小的“空洞”,如此按来一轮,直到块大小到配置的最小块大小为止。最后一轮跟原始rsync是一样的,当然只处理上一轮遗留下来的“空洞”。多轮rsync在理论上可以将最差情况下的复杂度(以传输的数据量称是)从原rsync的O(sqrt(n))提高到O(ln n)。试验中有时多轮rsync可以比原rsync有10倍的提升,但大部分情况下是类似的。
本地rsync则是直接更新A到与B一致,原始rsync算法是需要构造一个与B一致的副本。为实现这一点,需要先拿到所有匹配信息后进行拓扑排序,再依次应用,是有些复杂的。
建议继续学习:
- rsync同步的艺术 (阅读:8301)
- Linux探索:一次删除一百万个文件的最快方法 (阅读:5831)
- rsync 的核心算法 (阅读:4492)
- rsync自动输入密码实现数据备份 (阅读:4082)
- 使用 rsync 或 unison 备份或同步支持 ssh 的 web 主机 (阅读:3283)
- puppet使用rsync来同步文件教程 (阅读:3251)
- rsync主动同步代码 (阅读:3128)
- SHELL TIPS: rsync 和 crontab 变量 (阅读:2940)
- Linux下使用rsync进行数据备份的命令详解 (阅读:1838)
- Dropbox的邀请返利设计 (阅读:1814)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:风轻扬 来源: 风轻扬
- 标签: Dropbox rsync 差异同步
- 发布时间:2010-11-13 09:05:03
- [54] IOS安全–浅谈关于IOS加固的几种方法
- [52] android 开发入门
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [49] Go Reflect 性能
- [49] Oracle MTS模式下 进程地址与会话信
- [47] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [37] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑