大文件高效区分算法

看看rsyncs算法,因为它的设计非常精确,所以可以有效地复制delta。我记得,这个算法有很好的文档记录。

你可以使用 rdiff 这对大文件非常适用。这里我创建了两个大文件的差异 A 和 B 以下内容:

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

   rdiff signature A sig.txt
   

2. 使用生成的签名文件 sig.txt 另一个大文件,创建delta:

   rdiff delta sig.txt B delta
   

3. 现在 delta 包含重新创建文件所需的所有信息 乙 当你两个都有的时候 一 和 三角洲 .要重新创建b,请运行

   rdiff patch A delta B
   

在Ubuntu,快跑 sudo apt-get install rdiff 安装它。它相当快,我在我的PC上每秒获得大约40MB的内存。我刚在8GB文件上尝试过,rsync使用的内存大约是1MB。

这就是所谓的问题 "data deduplication" . 最常用的方法是:

• 读取块中的文件:
  • 分割所谓“块”的数据。最常用的方法称为“使用rabins指纹方法定义内容的分块”。( Code )。使用这种分块方法可以在大多数数据集中实现更好的重复数据消除,然后使用静态大小的数据块(如图所示 here )
  • 使用加密指纹方法(例如sha-256)对块进行指纹识别。
  • 将指纹存储在索引中,并在已知指纹的情况下查找每个块。如果指纹是已知的,则不需要再次存储块。只有当指纹未知时,才必须存储数据。

这种重复数据消除算法不如例如 xdelta 但对于大型数据集来说,它更快、更具可扩展性。每个核心(Java)执行大约50 Mb/s的组块和指纹。索引大小取决于冗余、块大小和数据大小。对于200GB,它应该适合于块大小为16KB的内存。

Bentleys and Mciloys 压缩方法非常类似(例如由Google Bigtable使用),但是我不知道使用压缩技术的任何现成命令行工具。

这个 "fs-c" 开源项目包含了大部分必需的代码。但是,fs-c本身只尝试测量内存中的冗余和analzye文件,或者使用 Hadoop 集群。

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

1. 为文件A创建一个后缀数组。此数组是对文件A的所有索引值的排列。如果A有2^37个字节,则索引数组最容易由64位整数表示,因此每个字节(偏移到文件)对应于索引数组中的8个字节,因此索引数组的长度将为2^40个字节。例如,800 GB。也可以只对每1024个位置进行索引,例如,减小索引数组的大小。然后,根据可复制片段的平均运行时间,这会影响包装的质量。

2. 现在,为了贪婪地打包文件b,从偏移量o=0开始,然后使用索引数组在a中查找与从“o”开始的数据匹配的最长匹配项。在压缩文件中输出对。在这种情况下,不需要编码16个字节,因此如果运行为<16个字节,实际上会丢失空间。这可以通过使用位级编码和使用位标记来标记是对独立字节(marker+8位=9位)还是偏移/长度对(marker+40位+40位=81位)进行编码来很容易解决。将最长的片段打包到o之后,将o增加到片段后面的下一个字节,并重复操作,直到文件结尾。

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

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

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