我希望能够将所有的微软办公软件、PDF、HTML、XML文件进行增量备份到共享网络上。同时，我会以5MB为单位读取文件，并计算MD5值以考虑去重因素。我的问题是，如果某个文件在上传后被修改，现在我想增量备份更改的数据，如果我使用相同的分块大小，则所有的分块都将不同，我需要重新上传它们。因此，是否有更好的去重方法，或者更好的了解所有指定文件的结构（原始读取），然后进行去重处理？
数据去重
3
- Haseena Parkar
1
2这是一个真的很糟糕的标题。请阅读http://meta.stackexchange.com/questions/10647/how-do-i-write-a-good-title。 - Soner Gönül
2个回答
2
有许多去重的方法。对我来说，必须知道文件的内部结构可能是最不吸引人的选择。我们做了类似于您要求的事情，并围绕它建立了一个产品。
有几个观察结果；首先，也许您已经听够了这个问题的年龄，MD5 不是您最好的朋友。在这些类型的应用中使用碰撞的概率太高了。我们选择了 SHA-1，许多其他类似工作的产品也是如此。
您认识到了数据简单“分块”的问题……在文件早期插入的情况下，所有后续块可能都必须被重写。
首先，您可能会意识到，在某个大小阈值以下，这几乎无关紧要。更改较小文件的 IO 是您可能只需吸收的内容。
但是，对于较大的文件，如果仅更改了一小部分，则无需重写所有数据将会很好……对于许多具有内部数据库结构的大型可写文件，这正是发生的情况。例如，具有内部数据库结构的文件。
技巧（如果可以称之为技巧）是识别静态数据范围。这相当于在您识别的数据上计算哈希。
例如，想象一下在文件中逐字节计算滚动哈希。如果您的哈希函数是合理分布的，每个新字节都将导致一个哈希值，该值与上一个字节的贡献相比具有相当随机的距离。
“识别”哈希值只意味着哈希值在您任意选择的某些值的子集中...即您已经决定表示“标记”哈希值。例如，您可能会识别所有可以被常量值整除的哈希值。
当您识别一个哈希值时，您会捕获文件中该字节的偏移量，并将滚动哈希重置为其初始状态。在文件结尾处，您将积累一系列偏移量。
现在，这些偏移量之间的相对距离将受到您对哈希识别器的选择性控制。例如，如果您选择识别“hash % 32 == 0”，那么您将有许多相互之间具有较小相对距离的偏移量。如果您选择“hash % 65536 == 0”，那么您将有更少、更广泛间隔的偏移量。每个偏移量之间的距离将是可变的...有些将非常小，而有些将非常大。注意：大块非常可压缩。
这些偏移量将成为断点...您将从偏移量到偏移量存储块。在存储块之前，您将计算该块的哈希值（SHA-1哈希值，而不是运行哈希值）。如果您已经将该块存储在存储器中，则无需再次存储。在您的存储器中，文件变成了块列表。块最初可能来自一个文件，但也可能被识别为出现在其他文件中。去重！
您对运行哈希的选择性不仅控制块大小，还能很好地捕捉大文件中的“小变化”。
在此时，有必要区分“滚动”哈希和“滑动”哈希。当您通过文件进行滚动时，非常重要的一点是要计算一个哈希值，该哈希值覆盖“最后n个字节”，其中n是滑动帧的宽度。我们并没有从偏移量到偏移量计算哈希值。我们试图找到我们认识的n字节标志。
n的大小也很重要。你需要为0到n-1计算哈希值，然后是1到n，然后是2到n+1等等。如果你考虑一下，n代表了将存在的最小块大小（除了在哨兵右侧紧跟着文件结尾）。
所以，在这一点上，你必须想，"天啊，这得哈希多少次啊！"，你是对的；但它并没有你想象的那么糟糕。选择正确的滚动哈希算法非常重要。有一种算法非常适合这个问题。我们使用的是称为Rabin-Karp滚动哈希的算法，并使用Rabin指纹来发现哨兵偏移量，它的优美之处在于添加一个字节的贡献和移除一个字节的贡献都是微不足道的廉价算术运算。
滚动哈希的重要性（而不是运行哈希）在于变更检测。假设在变更之前发生了一个已识别的哨兵偏移量......然后在变更之后又发生了另一个已识别的哨兵。只有这两个偏移量之间的块将被存储。变更之前的部分和变更之后的部分都已经被存储过了。
有几个观察结果；首先，也许您已经听够了这个问题的年龄，MD5 不是您最好的朋友。在这些类型的应用中使用碰撞的概率太高了。我们选择了 SHA-1，许多其他类似工作的产品也是如此。
您认识到了数据简单“分块”的问题……在文件早期插入的情况下，所有后续块可能都必须被重写。
首先，您可能会意识到，在某个大小阈值以下，这几乎无关紧要。更改较小文件的 IO 是您可能只需吸收的内容。
但是，对于较大的文件，如果仅更改了一小部分，则无需重写所有数据将会很好……对于许多具有内部数据库结构的大型可写文件，这正是发生的情况。例如，具有内部数据库结构的文件。
技巧（如果可以称之为技巧）是识别静态数据范围。这相当于在您识别的数据上计算哈希。
例如，想象一下在文件中逐字节计算滚动哈希。如果您的哈希函数是合理分布的，每个新字节都将导致一个哈希值，该值与上一个字节的贡献相比具有相当随机的距离。
“识别”哈希值只意味着哈希值在您任意选择的某些值的子集中...即您已经决定表示“标记”哈希值。例如，您可能会识别所有可以被常量值整除的哈希值。
当您识别一个哈希值时，您会捕获文件中该字节的偏移量，并将滚动哈希重置为其初始状态。在文件结尾处，您将积累一系列偏移量。
现在，这些偏移量之间的相对距离将受到您对哈希识别器的选择性控制。例如，如果您选择识别“hash % 32 == 0”，那么您将有许多相互之间具有较小相对距离的偏移量。如果您选择“hash % 65536 == 0”，那么您将有更少、更广泛间隔的偏移量。每个偏移量之间的距离将是可变的...有些将非常小，而有些将非常大。注意：大块非常可压缩。
这些偏移量将成为断点...您将从偏移量到偏移量存储块。在存储块之前，您将计算该块的哈希值（SHA-1哈希值，而不是运行哈希值）。如果您已经将该块存储在存储器中，则无需再次存储。在您的存储器中，文件变成了块列表。块最初可能来自一个文件，但也可能被识别为出现在其他文件中。去重！
您对运行哈希的选择性不仅控制块大小，还能很好地捕捉大文件中的“小变化”。
在此时，有必要区分“滚动”哈希和“滑动”哈希。当您通过文件进行滚动时，非常重要的一点是要计算一个哈希值，该哈希值覆盖“最后n个字节”，其中n是滑动帧的宽度。我们并没有从偏移量到偏移量计算哈希值。我们试图找到我们认识的n字节标志。
n的大小也很重要。你需要为0到n-1计算哈希值，然后是1到n，然后是2到n+1等等。如果你考虑一下，n代表了将存在的最小块大小（除了在哨兵右侧紧跟着文件结尾）。
所以，在这一点上，你必须想，"天啊，这得哈希多少次啊！"，你是对的；但它并没有你想象的那么糟糕。选择正确的滚动哈希算法非常重要。有一种算法非常适合这个问题。我们使用的是称为Rabin-Karp滚动哈希的算法，并使用Rabin指纹来发现哨兵偏移量，它的优美之处在于添加一个字节的贡献和移除一个字节的贡献都是微不足道的廉价算术运算。
滚动哈希的重要性（而不是运行哈希）在于变更检测。假设在变更之前发生了一个已识别的哨兵偏移量......然后在变更之后又发生了另一个已识别的哨兵。只有这两个偏移量之间的块将被存储。变更之前的部分和变更之后的部分都已经被存储过了。
- Clay
0
你可以查看rsync及其算法。
否则，您可能需要像datadomain一样执行某些操作。对可变块大小进行校验和，以便可以独立于给定文件中的偏移量识别数据段。请在网络上搜索以了解他们的专利等信息。在此处提供完整的写作是不可能的。
否则，您可能需要像datadomain一样执行某些操作。对可变块大小进行校验和，以便可以独立于给定文件中的偏移量识别数据段。请在网络上搜索以了解他们的专利等信息。在此处提供完整的写作是不可能的。
- Vikram
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接