重复数据删除

Question

我想逐步备份我所有的ms office，pdf，html，xml文件到一个共享的网络。我将读取大小为5mb的文件，我还将对这些数据执行MD5操作，以考虑重复数据消除因素。我的问题是，假设一个特定的文件在上传后被修改，现在我想增量地备份更改后的数据，如果我考虑相同的区块大小，那么所有的区块看起来都是不同的，我需要重新上传它们。那么，有没有更好的重复数据消除方法，或者是先了解所有指定文件的结构(原始读取)，然后再进行重复数据消除？

Answer 1

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

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

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

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

但是，对于较大的文件，如果只有一小部分changes...and与许多大型可写文件一起重写，那么就不必重写所有数据就好了，在一个大型的静态数据集中进行小的更改就好了。例如，具有内部数据库式结构的文件。

如果它可以被认为是一个技巧，那么它的诀窍就是识别静态数据的范围。这相当于对您识别的数据进行哈希计算。

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

识别散列仅仅意味着散列值在您选择的某个值的子集中，您已经决定arbitrarily...that表示定点散列。例如，您可能会识别所有由常量值平均划分的散列。

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

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

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

应用于运行哈希的选择性不仅控制块的大小，还控制在大文件中捕获“小更改”的能力。

在这一点上，区分运行散列和滚动散列是很重要的。很重要的一点是，当您在文件中滚动很长一段时间时，计算的是last n bytes上的散列，其中n是滑动框架的宽度。我们正在计算一个从偏移量到偏移量的散列，而不是。我们正在尝试找到我们能识别的n字节的前哨。

N的大小也很重要。您将计算0到n-1的散列，然后是1到n，然后是2到n+1，依此类推。如果您考虑一下，n表示将存在的最小块大小(除了紧跟在前哨之后的文件末尾)。

因此，在这一点上，您必须想，"Holey，这是大量的散列！“，您是对的；但它并不像您可能认为的那么糟糕。选择正确的滚动哈希算法是非常重要的。有一个非常适合这方面的算法。我们使用的方法被称为拉宾-卡普滚动哈希，它使用Rabin fingerprint来发现标记偏移量，它的优点是添加字节的贡献和删除字节的贡献是微不足道的、廉价的算法。

滚动哈希之所以重要(与运行哈希相反)是因为更改检测。假设识别的标记偏移发生在change...and之前，然后在改变之后出现另一个识别的标记。只有这两个偏移量之间的块才会被存储。更改之前的部件和更改后的部件将已预先存储。

Answer 2

您可以查看rsync及其算法。

否则，你可能不得不做一些像datadomain所做的事情。校验和可变块大小，以便可以独立于给定文件中的偏移量来识别数据段。请在网上搜索他们的专利等，在这里不可能给出一个完整的。