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表示将存在的最小块大小（除了 end-of-紧跟在哨兵之后的文件）。

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

滚动哈希很重要（与运行哈希相反）的原因是更改检测。假设一个已识别的标记偏移发生在更改之前……然后另一个已识别的标记发生在更改之后。只有这两个偏移量之间的块将被存储。更改前的部分和更改后的部分将被预先存储。

Answer 2

您可以检查 rsync 及其算法。

否则，您可能必须执行类似于 datadomain 的操作。校验和可变块大小，以便可以独立于给定文件中的偏移量来识别数据段。请在网上搜索以查看他们的专利等。这里不可能给出全文。