高性能的CDC算法

在Pcompress中,我实现了基于滚动散列的按内容分块的一个变体方案,这个方案同时具有较高的重复数据删除准确性和性能。本文试图解释分块过程,包括Pcompress中完成的分块计算,然后讨论针对非常快速的滑动窗口分块的优化。

背景

重复数据删除需要将数据流分割成一系列数据块,然后在这些数据块中查找重复的块。如果找到,则只存储其中一个块,其他相同的块对它进行引用。数据流分块看似一个非常普通的过程,但是它对查找重复数据的效率非常关键。最简单的方案是固定分块(static chunking or fixed-block),这种方法非常快速,几乎不需要处理,但它在数据转移时会带来一些限制问题。

我们用下面的图来解释这个问题。两个64字符的数据流大致相同,仅有两个字符不一样。起初的固定分块拥有较好的重复检测率。分成的7个块中有5个是完全相同的块。
如果在开头插入一个字符,会移动整个数据流,但是块的边界却没有移动。这样虽然两个数据流依然是大体上相同的,但是却不能检测到重复的数据块。

static_chunking.png

这个图解释了“插入”情况,同样的事情会发生在“删除”时。通常情况下,已有的重复检测结果会在“插入”或“删除”后丢失。

为了解决这个问题,大多数据去重方案使用按内容定义的分块(Content Defined Chunking, CDC)。它依照数据中的标记来决定分块的切割点,如果数据的标记发生了移动,那么切割点也会随之发生移动。我们用下面这张图来说明:

dynamic_chunking1.png

由于分块是和内容相关的,块的长度不再固定不变(但总体上接近我们期望的长度)。因为块的边界会随数据内容一起变化,变化后依然有不错的重复数据检测率。且只有部分被修改过的块是唯一的。

滚动哈希计算(The Rolling Hash computation)

现在的问题是应该根据数据流中的哪些数据模式来确定分割的边界?常用的技术是计算数据流中每个字符位置的连续几个字节的哈希值。如果哈希值匹配某个预定义模式,我们可以在该位置声明一个块边界。为了有效地进行这种计算,出现了一种称为滚动散列 滚动散列的技术。它使用滑动窗口扫描数据字节并在每个点计算散列值。
在位置I处的散列值可以非常方便地从I-1位置的散列值计算出来,

$$ H(X_{(i,n)}) \Leftarrow (H(X_{(i-1,n)})+X_{i}-X_{i-n}) mod M$$

n是窗口大小,$ X_{(i,n)} $代表在位置 $i$ 处的窗口字节。用数学术语说,这是一个递归关系。滚动哈希在Rabin-Karp子字符串搜索和Rsync中得到了应用。如今它也广泛应用在重复数据检测的分块算法中。

重复数据检测中一个常用的滚动哈希算法是 Rabin Fingerprinting ,它由图灵奖得主 Michael O. Rabin 在他的论文 “Fingerprinting By Random Polynomisals”(《通过随机多项式进行指纹识别》)中提出。如果你对数学感兴趣可能会希望阅读这篇论文。也有一些其他的滚动哈希算法,比如Rsync中使用的算法、HP提出的TTTD算法、FBC算法等。

rolling_hash.png

虽然我不是一个很擅长数学的人,但我仍然需要一个很好的滚动哈希算法,以便在Pcompress中完成内容定义的分块。
看过LBFS和其他一些开源软件(如n-gram散列)之类的各种实现之后,我想出了一种运行良好的方法,并生成了接近所需值的平均块大小。

我使用了一个16字节的滑动窗口,在每个字节位置产生一个64位的指纹,每个字节位置需要加,减,乘和有条件的异或。如果指纹的尾部 Y 位是零,它将声明一个块边界。Y的值将取决于所需的平均块大小。例如,如果我们需要4KB的平均大小,就使用低12位。这种方法的核心来源于 Rabin Fingerprinting 。具体可以参考:http://www.infoarena.ro/blog/rolling-hash

$$ rollhash = (rollhash * PRIME + inbyte - outbyte * POW) \% MODULUS $$

inbyte是滑动窗口头部的输入字节,outtype是滑动窗口尾部的输出字节。且 $ POW = (PRIME ^ {windowsize}) \% MODULUS $, $ PRIME $的值与Bulat Ziganishin在其SREP工具中使用的值相,实验表明它有不错的效果。除此之外,我使用LBFS中的不可约多项式(参见GF(2))预先计算表。outbyte用于索引表,并且该值与散列值异或以产生最终的指纹。我对这种分块方法做了一些分析,其结果很好。分析的过程记录在之前的两篇文章:

通常情况下可能会使用大于16字节的窗口,例如LBFS使用48字节,其他的一些方法甚至使用更大的窗口。
然而在实践中,从上述分析可以明显看出,这个实现产生了很好的结果,16字节的窗口大小允许进行优化,我们将在下面介绍。

优化

虽然现在处理器的乘法运算已经很快,但依然需要一定的性能开销。即使我正在使用一个16字节的小窗口,仍然需要对整个字节序列进行计算,以便找到分割点。相对于固定分块,其计算开销是非常可观的。从上面的哈希公式中,我们很容易找到下面的优化方法:

  • 因为要处理字节,我们可以预先为 $ outbete * POW $ 计算一个表
  • 如果它是2的幂,则可以用掩码代替 MODULUS 模操作

这些优化有一定效果,但扫描数据并不断更新内存中的滑动窗口的开销仍然存在。

最终我在Pcompress中实现了几个新的优化,结果非常显著:

  • 由于滑动窗口只有16个字节,因此可以将它完全保存在一个128位的SSE寄存器中。
  • 由于我们对块大小有上下限,我们在找到分割点后,可以直接跳过连续的几个字节(最小块长度)后再开始扫描。这样可以通过避免扫描大部分数据流来获得显著的性能提升。

用不同类型的数据进行实验表明,第二次优化结果只扫描了28%到40%的数据,其他数据都被直接跳过。块大小的上下限用来保证最后所有的块大小分布都接近我们期望的平均值大小。
因为滚动哈希算法的切割点会位于最小值和一个最大值之间,所以在最小值之前进行数据扫描是没有意义的。

opt_dynamic_chunking2.png

所有这些优化结合在一起,最后的效果达到了530MB/s,硬件环境为第二代Core i5(2.2GHz x 2),当然现在更新的处理器会有更好的性能表现。当然吞吐量和和数据本身的性质有关,如果数据的模式比较特殊从而导致生成很多较大的块,性能会下降。这会造成最坏的情况。

最坏情况的性能概述

最坏的情况就是所有的块都达到了最大的大小。也就是说,在达到最大块大小之前没有产生分割点,等同于以最大块大小为期望的固定分块,却以滚动散列的计算开销为代价。在这种情况下,大多数据都被扫描和计算,但是具体是多少呢?

假设我们块最小3KB,最大64KB,我们准备100MB的数据,我们会得到 $ 100MB/64KB = 1600 $ 个块。对于每个块,会有 $ 3KB - smallconstant $ 的数据被跳过扫描,在我的当前实现中 smallconstant 是256。所以实际跳过 $ 3072 - 256 = 2816 $ 字节,也即在每100MB中跳过 $ 2816 * 1600 = 4505600 $字节,占4.92% ,换句话说,另外95%的数据被扫描,这使性能下降了超过一半。

现在的问题是什么类型的数据会导致这种情况?如果你看了Pcompress中的滚动哈希算法的具体实现,你会发现最后的指纹是通过来自 表 的多项式的与或运算得到的。这些值是非零的,我们通过检测指纹的低12位是否为零来决定分割点。所以如果计算的散列值为零,与或运算会使这些位和低12位变成非零。
如果数据为零,则哈希值为零。也就是说,零字节的文件会产生最坏情况。

我创建了一个零字节文件用来测试,吞吐量为200MB/s,并且所有的块大小都是最大的64KB。在实际的情况中,零字节文件是可能出现的,但大量的零字节文件是很少出现的。其中一种零字节文件的情况是 VMDK/VDI文件。所以我测试了一个Fedora18的虚拟磁盘文件(VirtualBox),结果依然是大多块都是4KB,不过会有64KB的峰值出现。吞吐量为490MB/s,大约41%的数据被扫描。所以即使是一个虚拟硬盘文件也会像格式化标记一样在内部有非零的字节,只有零字节的几百MB的文件是很少见的。
最后从整体重复数据删除的角度来看,这些文件将被最大限度的重复数据删除,数据压缩率接近98%,最终压缩阶段也将非常快(仅为零字节)。所以即使分块受到影响,整体重复数据删除也会很快。

最后

如果你有兴趣查看Pcompress的具体实现,请参考:https://github.com/moinakg/pcompress/blob/master/rabin/rabin_dedup.c#L598

标签: CDC 数据去重

发表评论: