1问题
想象一下你有两个文件，A和B,你想将B文件更新成A,最明显的方法是将A全部拷贝．
现在想象这两个文件分别在通过低网速连接的两台机器上．例如通过IP拨号连接．如果A非常大，将A全部拷贝，将会非常慢．在发送之前将文件压缩会快点．但也不会起太大的作用..
现在假设A和B非常相似,或许这两个文件都是由相同的文件衍生出来的,想要快速更新起来,可以利用文件的相似性.方法是仅仅发送A和B之间不同的数据,通过A和B的不同产生一个差异列表,然后通过这个差异列表重建文件.
2 rsync算法
猜想我们有两台普通的计算机Alpha和Beta ,计算机Alpha能够访问A文件,计算机Beta能够访问B文件,当文件A和B相似,两台计算机Alpha和Beta并且通过低网速连接着
Rsync包含一下步骤
第一步: Beta将文件B分割成连续的不重叠的固定大小的块S,最后的块可能小于S字节
第二步:通过Beta的每一块字节,计算出两个校验值:一个32位的弱校验(下面将会描述)和一个128位MD4校验
第三步:Beta将这些校验值发送给Alpha
第四步:Alpha通过搜索文件A的所有大小为S的数据块(偏移量可以任选，不一定非要是S的倍数)，来寻找与文件B的某一块有着相同的弱校验码和强校验码的数据块。这项工作可以借助下文所述的滚动校验很快完成。
第五步Alpha发送给Beta重新构建A文件的指令.每一个指令,要么是一个没有与文件B的任何一个数据块匹配上的数据块,要么是Beta拥有这个数据块而不需要发送的证明
最后的结果是Beta得到了A文件
3滚动校验
回滚校验具有给定x1到xn的校验值还有x1和x n+1的值,就可以很快的计算出x2到xn+1校验值的特性.
弱校验算法采用的是Mark Adler的adler-32校验,我们将校验定义为
s(k,l) = a(k,l) + 216 b(k,l)
s(k,l)是xk到xl的回滚校验,为了简单和快速我们将M定义为216
校验重要的特性是通过使用递推关系可以非常高效地计算出连续值
因此用一个回滚方式个校验能够计算所有可能的偏移的长度为S的块,.
尽管这个对比两个文件块第一级校验很简单.我们发现在实际应用当中,.当文件块不相等也会出现校验值相等的情况,所以为了对应这一情况,当弱校验比较之后还需要更加强壮校验的比较.
4校验搜索
当Alpha接受到B文件的校验列表,就开始对文件A的所有偏移数据块和B的数据块进行比较,.基本的策略就是计算出每一块长度为S的32位滚动校验值,搜索B文件的校验列表,我们采用三级搜索方案.
第一级使用16位的滚动校验(从32位校验中衍生)和, 216 入口哈希表,哈希值列表按照16位的滚动校验排序.,在哈希表中的每个入口指向列表元素的第一个哈希值,如果哈希值列表中没有元素将包含一个空值.
如果哈希表的哈希值不是空值,第二级检查开始
第二级校验包括扫描由哈希表入口指向的已经排过序的校验列表,以当前值和整个32位滚动校验对比.当到达整个16位hash不同的入口扫描停止.如果搜索到相同的校验值,第三级校验开始.
第三级校验包括计算当前文件偏移的强哈希,当前列表项与强哈希的比较.如果这两个强哈希匹配成功.我们就找到了B中与A相同的文件块
当匹配成功的时候,Alpha发送给Beta这个数据块在A中的开始和结束的位置,还有在这个数据块在B中的索引(位置).
匹配成功的时候,下一次的校验从匹配成功数据块的末尾开始,匹配不成功的时候，下一次的校验从该数据块开始的位置的下一个字节开始.例如文件是"12345678",假定分块大小是3.如果从1到3匹配成功,下次的校验是从4到6计算的.如果从1到3匹配不成功,下一次的校验是从2到4计算的.
本文大部分是翻译rsync的学术报告.有错误尽管指出来.
参考：
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/flyfish1986/archive/2008/07/02/2606132.aspx
阅读(571) | 评论(2) | 转发(0) |
