c# - 重复数据删除

Question

我想将所有的ms office，pdf，html，xml文件增量备份到共享网络。我将读取5mb的文件，也将对数据进行MD5处理以考虑重复因素。我的问题是说特定文件在上载后被修改，现在我要增量备份更改的数据，如果我考虑相同的块大小，则所有块似乎都不同，我需要再次全部上传。那么，有没有更好的重复数据删除方法，或者知道所有指定文件的结构（原始读取）然后进行重复数据删除会更好？

Answer 1

有多种重复数据删除方法。至少对于我而言，必须了解文件的内部结构可能是最没有吸引力的选择。我们做了与您要求的类似的事情，并围绕它构建了一个产品。

一些观察；首先，考虑到这个问题的年龄，您可能已经听够了，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表示将存在的最小块大小（标记后的文件）。

因此，在这一点上，您必须要想，“ Holey，这是很多哈希！”，您是对的；但这并没有你想的那么糟。选择正确的滚动哈希算法非常重要。有一种非常适合此的算法。我们使用的一种称为Rabin-Karp滚动哈希，并使用Rabin fingerprint来发现前哨偏移，其优点在于，添加字节的贡献和删除字节的贡献是微不足道的，廉价的算法。

滚动哈希很重要（而不是运行哈希）的原因是更改检测。假设一个已识别的前哨偏移发生在更改之前...然后在更改后发生另一个已识别的前哨偏移。仅存储这两个偏移量之间的块。更改前的部分和更改后的部分将事先存储。