滑动块算法结合了定长切分和CDC切分的优点,块大小固定。它对定长数据块先计算弱校验值,如果匹配则再计算md5强校验值,两者都匹配则认为是一个数据块边界。该数据块前面的数据碎片也是一个数据块,它是不定长的。如果滑动窗口移过一个块大小的距离仍无法匹配,则也认定为一个数据块边界。滑动块算法对插入和删除问题处理非常高效,并且能够检测到比CDC更多的冗余数据,它的不足是容易产生数据碎片。
6、差异编码
差异编码的基础是文件B数据分块信息和文件A,它首先对文件A进行对等数据分块(滑动块算法除外,它对文件B的切分是定长算法,而对文件A是滑动块算法),然后匹配文件B数据分块信息。如果数据块匹配,则用数据块索引表示,达到重复数据删除效果。否则,则将对应的文件A数据块写入差异编码文件中。数据块匹配算法方面,定长切分和CDC切分是基本相同,文件A采用和文件B对等的切分算法进行数据块切分。滑动块算法与其他两种算法不同,它与rsync类似,它对文件B的切分是定长算法,而对文件A的切分是滑动块算法。因此,这种算法切分是不对等的。
然后根据文件B构造hashtable,通过hash查找进行匹配,并按照差异编码数据布局构造相应数据文件。
7、文件同步
Beta得到差异编码文件delta,再结合已有的文件B,即可以将文件B同步成文件A的副本。同步算法遍历delta文件,读取每一个数据块描述实体,根据embeded标志分别从delta和文件B中读取相应的数据块,重新构造出文件A。
8、PULL与PUSH模式
数据同步有PULL和PUSH两种应用模式,PULL是将远程数据同步到本地,而PUSH是将本地数据同步到远程。对应到同步算法,主要区别在于数据分块和差异编码位置不同。PULL和PUSH同步模式步骤分别如下所述。
PULL同步模式流程:
1、本地对文件A进行数据切分,生成数据块描述文件chunk;
2、上传chunk文件至远程服务器;
3、远程服务器对文件B进行差异编码,生成差异编码文件delta;
4、下载delta文件至本地;
5、本地同步文件A至文件B,相当于下载文件B到本地文件A。
PUSH同步模式流程:
1、远程服务器对文件B进行数据切分,生成数据块描述文件chunk;
2、下载chunk文件至本地;
3、本地对文件A进行差异编码,生成差异编码文件delta;
4、上传delta文件至远程服务器;
5、远程同步文件B到A,相当于上传文件A到远程文件B。
转载:http://blog.csdn.net/liuben/archive/2010/08/06/5793706.aspx
本文链接:http://www.blueidea.com/tech/program/2010/7878.asp
出处:CSDN
责任编辑:bluehearts
上一页 数据同步算法研究 [3] 下一页
◎进入论坛网络编程版块参加讨论
|