我个人正在寻求了解 rsync 算法的工作原理。经过一番阅读和思考,我想出了一个我认为算法失败的情况。我试图弄清楚这是如何在实际实现中解决的。
考虑这个例子,其中 A 是接收者,B 是发送者。
A = abcde1234512345fghij
B = abcde12345fghij
如您所见,唯一的更改是12345
已删除。
现在,为了让这个例子更有趣,让我们选择一个 5 字节(字符)的块大小。使用弱校验和对发送方的值进行散列得到以下值列表。
abcde|12345|fghij
abcde -> 495
12345 -> 255
fghij -> 520
values = [495, 255, 520]
接下来我们检查 A 中是否有任何哈希值不同。如果有匹配的块,我们可以跳到该块的末尾进行下一次检查。如果存在不匹配的块,那么我们发现了差异。我将逐步完成这个过程。
- 散列第一个块。这个哈希值是否存在于值列表中?
abcde -> 495
(是的,所以跳过) - 散列第二个块。这个哈希值是否存在于值列表中?
12345 -> 255
(是的,所以跳过) - 散列第三个块。这个哈希值是否存在于值列表中?
12345 -> 255
(是的,所以跳过) - 散列第四个块。这个哈希值是否存在于值列表中?
fghij -> 520
(是的,所以跳过) - 没有更多数据了,我们完成了。
由于在值列表中找到了每个哈希,我们得出结论 A 和 B 是相同的。在我看来,这不是真的。
在我看来,只要有多个块共享相同的哈希值,就会发生这种情况。我知道我已经跳过了计算和检查强哈希的步骤,但这不会有什么不同,因为第二个和第三个块完全相同
我错过了什么?