高效的两轮远程文件快速同步算法  

High Effective Two-round Remote File Fast Synchronization Algorithm

作　　者：徐旦[1] 生拥宏[2] 鞠大鹏[2] 吴建平[1] 汪东升[2,3] 

机构地区：[1]北京邮电大学计算机科学与技术学院,北京100876 [2]清华大学计算机科学与技术系,北京100084 [3]清华大学信息科学与技术国家实验室,北京100084

出　　处：《计算机科学与探索》2011年第1期38-49,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60833004;60673145;国家高技术研究发展计划(863)No.2009AA1Z104~~

摘　　要：远程文件快速同步在文件备份与恢复、Web与ftp网站镜像、分发网络、Web访问中具有广泛的应用。提出了一种高效的基于变长分块和定长滑动块相结合的两轮快速文件同步算法——tpsync。同步算法分两轮进行,第一轮利用基于可变分块技术在粗粒度上定位待同步文件的局部变化数据段,第二轮对局部变化数据段采用定长滑动切块技术在细粒度上查找出差异数据,最终通过两轮数据交互实现文件的同步。将tpsync与传统的单轮同步算法rsync进行了对比实验,通过对文本、二进制和数据库三种文件类型相似版本之间的同步实验,结果表明tpsync在平均同步时间和网络传输数据量两个方面均优于rsync。Fast remote file synchronization has a widespread application in many scenarios such as the file backup and recovery, Web and ftp site mirroring, content distribution network, Web access and so on. This paper presents a high effective two-round fast synchronization algorithm tpsync which combines content-based variable-sized chunk and fixed-sized sliding block methods, tpsync is implemented with two rounds. For the first round, tpsync adopts content-based variable-sized chunk to locate the local change between similar files in coarse-grained scale. In the second round, tpsync looks up the differential data in the local changed data segment with fixed-sized sliding block method in fine-grained scale, and finally achieves the file synchronization by two-round data interaction. This paper executes a comparison experiment between tpsync and the traditional single-round synchronization method rsync. Extensive experiments on text, binary and database files demonstrate that tpsync can achieve a higher performance on average synchronization time and the amount of network traffic data than rsync.

关 键 词：重复数据检测 文件同步 RSYNC算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]