rsync算法如何正确识别重复块？

Question

我正在寻求了解rsync算法的工作原理.经过一番阅读和思考,我想出了一个我认为算法失败的情况.我试图找出在实际实现中如何解决这个问题.

考虑这个例子,其中A是接收者,B是发送者.

A = abcde1234512345fghij
B = abcde12345fghij

如您所见,唯一的变化是12345已被删除.

现在,为了让这个例子变得有趣,让我们选择一个5字节的块大小(字符).使用弱校验和散列发送方的值会给出以下值列表.

abcde|12345|fghij

abcde -> 495
12345 -> 255
fghij -> 520

values = [495, 255, 520]

接下来我们检查A中是否有任何哈希值不同.如果有匹配的块,我们可以跳到该块的末尾进行下一次检查.如果有一个不匹配的块,那么我们发现了一个区别.我会逐步完成这个过程.

1. 哈希第一个块.这个哈希值是否存在于值列表中？abcde -> 495(是的,所以跳过)
2. 哈希第二块.这个哈希值是否存在于值列表中？ 12345 -> 255(是的,所以跳过)
3. 哈希第三块.这个哈希值是否存在于值列表中？ 12345 -> 255(是的,所以跳过)
4. 哈希第四块.这个哈希值是否存在于值列表中？ fghij -> 520(是的,所以跳过)
5. 没有更多的数据,我们已经完成了.

由于在值列表中找到了每个哈希值,因此我们得出结论:A和B是相同的.在我看来,这不是真的.

在我看来,只要有多个块共享相同的哈希值,就会发生这种情况.我知道我已经跳过了计算和检查强散列的步骤,但这不会产生任何影响,因为第二个和第三个块完全相同

我错过了什么？

Answer 1

rsync算法发送两个校验和:每个块一个,以及整个文件的"滚动"校验和.在您的示例中,A将在滚动校验和到达"doubled-up"块时看到差异.