gpt4 book ai didi

algorithm - rsync算法如何正确识别重复 block ?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:37:17 27 4
gpt4 key购买 nike

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

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

A = abcde1234512345fghij
B = abcde12345fghij

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

现在,为了让这个例子更有趣,让我们选择 5 个字节(字符)的 block 大小。使用弱校验和对发件人端的值进行散列处理,得到以下值列表。

abcde|12345|fghij

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

values = [495, 255, 520]

接下来我们检查 A 中是否有任何哈希值不同。如果有匹配的 block ,我们可以跳到该 block 的末尾进行下一次检查。如果有一个不匹配的 block ,那么我们就发现了差异。我将逐步完成此过程。

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

由于在值列表中找到了每个散列,我们得出结论 A 和 B 相同。以我的拙见,这不是真的。

在我看来,只要有多个区 block 共享相同的哈希值,就会发生这种情况。我知道我已经跳过了计算和检查强哈希的步骤,但这不会有什么不同,因为第二个和第三个 block 完全相同

我错过了什么?

最佳答案

rsync 算法发送两个校验和:一个用于每个 block ,一个“滚动”校验和用于整个文件。在您的示例中,一旦到达“加倍” block ,A 就会看到滚动校验和的差异。

关于algorithm - rsync算法如何正确识别重复 block ?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2557927/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com