重复数据删除

Question

我想将我的所有ms office，pdf，html，xml文件逐步备份到共享网络。我将以5mb大块的形式读取文件，同时我还将对这些数据进行MD5处理，以考虑欺骗因素。我的问题是，上传后特定的文件被修改，现在我想增量备份更改的数据，如果我考虑相同的块大小，那么所有的块将显示不同，我需要再次上传它们。那么是否有更好的方法来解决重复数据的问题？或者，最好是知道所有指定文件的结构（原始读取），然后处理重复数据？

感谢和问候， Haseena

Answer 1

您可以检查了rsync的和它的算法。

否则，您可能不得不做类似datadomain的操作。校验变量块的大小，使得数据段可以独立于给定文件中的偏移而被识别。请在网上搜索以查看他们的专利等。在这里完成写作是不可能的。

Answer 2

有许多重复删除的方法。必须知道文件的内部结构可能是最没有吸引力的选择 - 至少对我而言。我们做了类似于你要求的东西，并围绕它建立了一个产品。

一些观察;首先，考虑到问题的年代，你可能已经听够了，MD5不是你最好的朋友。在这些类型的应用中碰撞的可能性太高。我们选择了SHA-1，就像很多其他做类似工作的产品一样。

您认识到数据的简单“分块”问题......在文件早期插入的情况下，所有后续块可能必须重写。

首先，您可能会意识到，低于一定的大小阈值，这很重要。更改较小文件的IO是您可能会吸收的东西。

但是，对于较大的文件，如果只有一小部分更改，就不必重写所有数据......并且有很多大的可写文件，大的静态数据集中的小改动正是发生。例如，具有内部数据库结构的文件。

诀窍，如果它可以被视为一个窍门，是识别静态数据的范围。这相当于计算你认识的数据的哈希值。

例如，想象一下计算一个滚动散列，在文件中逐字节地读取它。如果你的哈希函数是合理分配的，那么每个新的字节将产生一个散列值，它与前一个字节的贡献非常相似。

认识哈希只是意味着哈希值是你任意选择......你已经决定代表定点散列值的某个子集。例如，您可能会识别出所有通过恒定值均匀分配的哈希值。

当您识别散列时，将捕获文件中该字节的偏移量，并将滚动散列重置为初始状态。在文件末尾，您将累积一个偏移量列表。

现在，这些偏移量之间的相对距离将受到散列识别器选择性的控制。例如，如果您选择识别hash % 32 == 0，那么您将在彼此相对较小的相对距离处有很多偏移量。如果你有hash % 65536 == 0，你将会有更少，更宽的偏移量。每个偏移量之间的距离将是可变的...有些会很小，有些会很大。 注意：大块很可压缩。

这些偏移量将成为中断点...您将存储从偏移量到偏移量的块。在存储块之前，您将计算该块的散列（SHA-1散列，而不是正在运行的散列）。如果您已经在存储中获得了该块，则不需要再次存储它。在您的存储中，文件成为块的列表。块最初可能来自一个文件，但也会被识别为发生在其他文件中。重复数据删除！

您应用于正在运行的散列的选择性不仅控制块的大小，而且还控制如何在大文件中捕获“小改动”。

在这一点上，重要的是要区分运行散列和滚动散列。真正重要的是，当你在文件中滚动时，你计算的是一个关于last n bytes的散列，其中n是滑动框架的宽度。我们是而不是计算从偏移量到偏移量的散列值。我们正在努力寻找我们认识到的n -byte哨兵。

n的大小也很重要。你将会计算一个从0到n-1，然后是1到n，然后是2到n + 1等的散列。如果你仔细想想，n表示将存在的最小块大小（除了end-这个文件是在一个哨兵之后发生的）。

所以，在这一点上，你必须思考，“Holey，这是很多哈希！”，你是对的;但并不像你想象的那么糟糕。选择正确的滚动哈希算法是非常重要的。有一个非常适合这个的算法。我们使用的称为Rabin-Karp滚动散列，并使用Rabin fingerprint来发现标记偏移，它的美妙之处在于添加字节的贡献和删除字节的贡献是微不足道的，廉价的算法。

滚动散列很重要的原因（与正在运行的散列相反）是变化检测。假设在更改之前发生识别的哨兵偏移...，然后在更改后发生另一个可识别的哨兵。只有这两个偏移之间的块才会被存储。更改前的部分和更改后的部分先前已存储。