18

我必须存储两个文件 A 和 B，它们都非常大（比如 100GB）。但是 B 可能在很大程度上与 A 相似，因此我可以存储 A 和 diff(A, B)。这个问题有两个有趣的方面：

  1. 这些文件太大，我知道的任何差异库都无法分析，因为它们在内存中
  2. 我实际上并不需要差异 - 差异通常具有插入、编辑和删除，因为它是供人类阅读的。我可以得到更少的信息：我只需要“新的字节范围”和“从任意偏移量的旧文件复制字节”。

我目前不知道如何在这些条件下计算从 A 到 B 的增量。有谁知道这个算法？

同样，问题很简单：编写一个算法，考虑到两者非常相似的事实，可以用尽可能少的字节存储文件 A 和 B。

附加信息：虽然大部件可能相同，但它们可能具有不同的偏移量并且出现故障。最后一个事实是为什么传统的差异可能不会节省太多。

4

5 回答 5

16

您可以使用rdiff，它非常适用于大文件。在这里，我创建了两个大文件的A差异B：

  1. 创建一个文件的签名，例如

    rdiff signature A sig.txt

  2. 使用生成的签名文件sig.txt和其他大文件，创建增量：

    rdiff delta sig.txt B delta

  3. 现在包含当您同时拥有和时delta重新创建文件所需的所有信息。要重新创建 B，请运行BAdelta

    rdiff patch A delta B

在 Ubuntu 中，只需运行sudo apt-get install rdiff即可安装它。它非常快，我的 PC 上每秒大约 40 MB。我刚刚在一个 8GB 的​​文件上试了一下，rsync 使用的内存大约是 1MB。

于 2010-01-09T15:37:09.170 回答
14

看看 RSYNCs 算法，因为它的设计几乎就是为了做到这一点，因此它可以有效地复制增量。我记得，该算法有很好的文档记录。

于 2010-01-08T19:49:44.737 回答
8

这正是所谓的“重复数据删除”问题。最常用的方法是：

  • 读取块中的文件：
    • 拆分所谓的“块”的数据。最常用的方法称为“使用 Rabins 指纹方法的内容定义分块”（代码）。使用这种分块方法可以对大多数数据集进行更好的重复数据删除，然后使用静态大小的块（例如，此处显示）。
    • 使用密码指纹识别方法对块进行指纹识别，例如 SHA-256。
    • 如果指纹已知，则将指纹存储在索引中并查找每个块。如果指纹已知，则无需再次存储该块。只有当指纹未知时，才需要存储数据。

这种重复数据删除算法不像xdelta那样精确，但它对于大型数据集更快且更具可扩展性。分块和指纹识别以每核大约 50 MB/s (Java) 的速度执行。索引大小取决于冗余、块大小和数据大小。对于 200 GB，它应该适合内存中的块大小，例如 16KB。

Bentleys 和 Mciloys压缩方法非常相似（例如由 Google 的 BigTable 使用），但是我不知道有任何现成的命令行工具使用压缩技术。

“ fs-c”开源项目包含大部分必要的代码。但是，fs-c 本身仅尝试测量内存中的冗余和分析文件或使用Hadoop集群。

于 2010-01-08T20:11:14.130 回答
6

一个问题是文件中的记录大小是多少，即偏移量是否可以逐字节更改，或者文件是否由例如 1024B 块组成。假设数据是面向字节的，您可以执行以下操作：

  1. 为文件 A 创建一个后缀数组。这个数组是文件 A 的所有索引值的排列。如果 A 有 2^37 个字节，那么索引数组最容易用 64 位整数表示，所以每个字节（偏移到file) 对应索引数组中的 8 个字节，因此索引数组的长度为 2^40 字节。例如，800 GB。您也可以仅对第 1024 个位置进行索引，例如，以减小索引数组的大小。然后，这会根据可复制片段的平均运行时间来降低打包质量。

  2. 现在贪婪地打包文件 B，您从偏移量 o=0 的开头开始，然后使用索引数组在 A 中找到与从 'o' 开始的数据匹配的最长匹配项。您在打包文件中输出该对。这在您的情况下不需要任何编码 16 字节，因此如果运行小于 16 字节，您实际上会丢失空间。这可以通过使用然后位级编码并使用位标记来标记您是编码隔离字节（标记 + 8 位 = 9 位）还是偏移/长度对（标记 + 40 位 + 40 位 = 81位），说。在 o 处打包最长的片段后，将 o 增加到片段之后的下一个字节并重复直到文件末尾。

后缀数组的构造和使用很容易，您应该很容易找到引用。在高速应用程序中，人们使用后缀树或后缀尝试代替，它们操作起来更复杂，但提供更快的查找。在您的情况下，您将阵列放在辅助存储上，如果打包阶段的运行速度不是问题，则后缀阵列就足够了。

于 2010-01-08T20:02:00.017 回答
1

根据您的性能要求，您可以对指纹块进行采样，并在它们匹配时对其进行增长。这样您就不必对整个大文件运行校验和。

如果您需要任意字节对齐并且您真正关心性能，请查看simhash 算法，并使用它来查找相似但未对齐的块。

于 2010-01-08T20:28:31.710 回答