重复数据删除的数据

有许多重复数据删除方法。必须了解文件的内部结构可能是最不吸引人的选择——至少对我来说是这样。我们做了一些类似于你要求的事情，并围绕它开发了一个产品。

几个观察结果;首先，你可能已经听够了，考虑到这个问题的年龄，MD5并不是你最好的朋友。在这些类型的应用程序中使用碰撞的概率太高。我们选择了SHA-1，因为有很多其他产品做类似的工作。

你发现了简单的"分块"数据的问题…在文件早期插入的情况下，所有后续块可能必须重写。

首先，您可能会认识到，在某个大小阈值以下，这几乎无关紧要。对于更改后的小文件，您可能只需要吸收IO。

但是，对于较大的文件，如果只有一小部分更改，则不必重写所有数据就好了……对于许多大的可写文件，在一个大的静态数据集中发生的小的变化就是这样。具有内部数据库结构的文件，例如。

这个技巧(如果可以认为是技巧的话)是识别静态数据的范围。这相当于在您识别的数据上计算哈希值。

例如，想象一下在遍历文件时逐个字节地计算滚动散列。如果您的哈希函数是合理分布的，那么每个新字节将产生一个与前一个字节的贡献相当随机的哈希值。

识别散列仅仅意味着该散列值在您任意选择的值的某个子集中…您决定表示哨兵散列。例如，您可能会识别出所有的哈希值，这些哈希值平均除以一个常量值。

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

现在，这些偏移量之间的相对距离将由你对哈希识别器的选择程度来控制。举个例子，如果你选择识别hash % 32 == 0，你会在相对距离较小的地方有很多偏移。如果是hash % 65536 == 0就会有更少，更宽间距的偏移。每个偏移量之间的距离是可变的……有些会很小，有些会很大。注意:大块是非常可压缩的

这些偏移量将成为断点…您将从偏移量到偏移量存储块。在存储块之前，您将计算该块的哈希值(SHA-1哈希值，而不是运行哈希值)。如果您已经在存储中存储了该块，则不需要再次存储它。在存储中，文件变成了块列表。块最初可能来自一个文件，但也会被识别为出现在其他文件中。重复数据删除!

应用于运行散列的选择性不仅控制块大小，而且还控制在大文件中捕获"小变化"的程度。

在这里，区分运行散列和滚动散列是很重要的。当你滚动一个长文件时，你所计算的是last n bytes上的散列，其中n是滑动框架的宽度，这一点非常重要。我们在而不是计算偏移量到偏移量的哈希值。我们正试图找到我们能识别的n个字节的哨兵。

n的大小也很重要。你会计算从0到n-1的哈希值，然后是1到n，然后是2到n+1，等等。如果您仔细想想，n表示将存在的最小块大小(除了紧跟在哨兵后面的文件结束符)。

所以，在这一点上，你必须要想，"嘿，这是很多哈希!"，你是对的;但它并没有你想象的那么糟糕。选择正确的滚动哈希算法是非常重要的。有一个算法非常适合这个。我们使用的是Rabin- karp滚动散列，它使用Rabin指纹来发现哨兵偏移量，它的美妙之处在于，添加和删除一个字节的贡献是微不足道的，廉价的算法。

滚动散列(相对于运行散列)重要的原因是变更检测。假设在更改之前发生了可识别的前哨偏移…然后另一个可识别的哨兵在变化后出现。只有这两个偏移量之间的块将被存储。更改前的部分和更改后的部分将预先存储。

您可以查看rsync及其算法。

否则，您可能不得不做类似于dataddomain所做的事情。校验和可变块大小，以便可以独立于给定文件中的偏移量来识别数据段。请在网上搜索他们的专利等。