数据去重--文献综述

文献综述

Created Wednesday 22 February 2012

I，背景介绍
随着计算机技术的广泛应用，备份数据的增长速度非常快，当备份设备由传统的磁带机越来越普遍的被磁盘代替后，去重技术就应运而生【3，在大多文章的introduction都可以找到描述，3给出了一些具体的数据】。去重与压缩类似，是一种数据缩减技术，不同的是，压缩的范围一般是文件，粒度是bit，而去重的范围则为整个磁盘，或者服务器上的所有磁盘。因此去重在备份数据的缩减上，有比压缩显著得多的效果，因为两份备份数据之间往往仅仅很小的差别，通过去重，可仅保存有差别的数据，而压缩堆单个备份数据的作用是有限的。根据【1】文中的数据，对某备份服务器一个月的数据进行处理，结果达到的38.54:1的删减比率。
如此高效的数据删减比例，带来的好处不言而喻：首先可以节省大量的备份设备成本，其次可以节省一部分电费开支，再次可以减少大量数据对网络带宽和磁盘带宽的压力。

去重方案按照不同的角度可以分为以下几种：
1，in-line vs out-line
in-line对数据流实时的去重处理，处理完成之后再写入磁盘。【1，2，3，4】均属于in-line方式；
out-line是将数据先暂存至另一块磁盘上，等到空闲的时候在对这些暂存数据进行处理。

out-line可以达到更到的写入速度，但需要额外的磁盘来暂存数据，in-line方式则对数据的去重速度提出了更高的要求，【1】提出了三大措施，使in-line去重的throughtput从5,6M/S的水平提升至100M/S的水平，这样in-line方式才具有真正的实用价值。
目前，in-line方式是研究热点及未来的方向

2，full file vs chunk based
根据数据处理的粒度来划分，full file在文件系统层次，以整个文件为处理单元，通过对比文件属性来寻找相同或相似的文件。这种方式的好处是对内存要求较少，处理速度较高，但其压缩比率比较低。
chunk based则是将数据流划分为chunks，以chunk为处理单元，通过chunk的index来查找相同或相似的数据块。index通常采用hash算法生成。该方式的好处是可以达到较高的压缩比率，但chunks的footprint会占用大量的空间，导致无法完全保存在MEM中，导致在index查找过程需要磁盘访问，这也是为什么传统的chunk based方式的throughtout很低的原因。不过，随着[1]文及之后提出的解决方案，chunk based已达到实用的高度。

3，Identity based vs Similarity based
这是按照在chunk based的去重方案中，对chunk的比较方式的不同而区分的。
在传统chunk based方案中，包括[1]，都是采用对chunk进行一致性比对的方式，即chunks之间要么相同，要么不同，而Similarity based方案则采用相似对比的方式，即在chunks之间计算相似度，相似的chunks再通过hash对比或者字节对比技术进行处理。相似对比技术主要是为了进一步解决chunk based方式中，chunk index过大的问题，【1】文将每16T数据的index cache限定在1G左右，虽然较以前的方案有大幅缩小，但对于PB级的数据，其index cache依然会远超接受范围，相似对比技术首先将数据流划分为segment，segment又划分chunk，segment较大，如16M，chunk较小，如4k，segment的index由所包含的chunk的hash值抽样组成，则具有相同index的segment可认为是相似的。
[4,5]文采用了Similarity Based技术

4，backup vs primary
应该说，数据去重主要是应用在backup和archive领域，但现在随着去重服务器的throughtout值的提高，及硬件加速的部分应用，在主存中使用去重的呼声愈高。

[6]文对压缩，定长/变长去重，文件去重，去重和压缩的顺序关系进行了实验，并给出了详尽的实验数据，值得一看。从文中我们可以看出，压缩与去重联合使用可达到更好的效果，其二者各有所长。压缩对随机文件包有很好的效果，而去重对重复率很高的数据包之间有很好的效果，如daily backup数据，virtual machine系统数据。
正因为去重在virtual machine中的效果显著，所以去重目前也是云计算的热点之一。

[7]文则通过数据分析，对不同数据的重复率进行了通过，统计结果表明，对于同一用户的用户目录备份数据，重复率达到94.7%，同一组内的用户的数据重复率为5.2%，不同组的用户的数据重复率很少。由此提出了根据文件的用户组属性来判定的多层去重结构。

根据[6,7]文，我们可以看到，去重的应用领域是比较特定的，不能以为任何数据都可以使用去重技术，否则只会得不偿失。

II，关键技术
1，variable chunk
变长分块技术，[6]文对定长分块和变长分块做了对比，对压缩比有一定的提升，但实现稍复杂。[7,8,9]文是关于变长分块的参考文件，没来得及看。大概是从数据流中解析文件属性，以文件的边界为附加条件划分chunk。
[1]文2.1也对fix chunk和variable chunk进行了对比选择，选择结果是variable chunk。

2，blooming filter
blooming filter是一项很成熟的算法，可参考http://blog.csdn.net/jiaomeng/article/details/1495500
Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

[1]文将blooming filter应用到去重中。其称之为summary vector，具体做法是：选择合适的m，来构造长度为m的blooming filter，选择k个hash函数h1,h2..hk，对每个chunk的index(fingerprint)，计算k个hash值，并将得到都值都映射至blooing filter table中，当有新的chunk进入时，则计算k个hash值，并在blooming filter table中查找hash值对应的bit位是否被置1，如果都被置1，则该chunk有可能已经在磁盘里，如果有一个bit没有置1，则该chunk肯定不在该磁盘里。
[2]文在[1]文的基础上提出了多重blooming table，实际实现中针对8TB的磁盘(4k chunk)，构造了1664, 1664x1664两重blooming table，占用内存空间11G，实现了1500 IOs/s写速度和700 IOPS读速度。要注意的是这是应用在primary storage中的，与备份服务器有很大的差别。

总的来说，采用blooming filter之前，chunk的index体积很大，即使采用较大的chunk，1TB原始数据对应的chunk index也要几个G，所以chunk index无法完全保存在内存里，那么就会导致chunk index search的时候频繁IO操作，处理能力肯定低下。而blooming filter相比完整的blooming filter体积小很多，在[1]文中，16TB的原始数据，只需要1G的空间，那么blooming filter可以完全保存到内存中。
但是，blooming filter不是代替chunk index，在[1]中，chunk index会保存到磁盘中，blooming filter保存在内存中。只有那些全新的chunk(并非全部)可以通过blooming判定不存在相同的chunk，从而避免了chunk search过程中的磁盘IO。但对非全新chunk(磁盘中存在相同的chunk)，还是需要去进行chunk index search的操作，磁盘IO无法避免。按照[1]文给出的比率，blooming filter可以在chunk index search过程中减少16%左右的磁盘IO。
MBL(multi blooming filter)则使用更大的内存空间，精确的定位chunk index的位置，从而避免读取不相关的chunk index。

3，Locality Preserved Caching
这个也是[1]文中提出的，在上面说过，blooming filter可以避免全新chunk的chunk index查找过程。但对于可能重复的chunk，还是需要查找index。因此，[1]文又提出了后两项技术，Stream-Informed Segment Layout(SISL)和Locality Preserved Caching(LPC)，我将其合并为后者，因为前者是后者的准备工作。
简单的说，这项技术是利用了数据的空间局部性原理，SISL将无特征的数据整理为有特征的连续数据块，这些数据块在磁盘的物理空间上是尽量连续保存的，其对应的index也是连续保存的，并且被划分为区域，当一次chunk index查找命中，则该区域内的所有chunk index都会被load到MEM中，那么接下来的chunk index可能也在这些load到MEM中的index里面。
该思想的背景：
备份过程有Application控制，其行为是比较固定的，即备份固定目录的数据，所以数据流可以被解析为连续，有意义的。当命中某一备份数据流的第一个chunk，可以预见，接下来的chunk也会和上一次的备份数据流中的下一个chunk相同。但，对于primary storage，该方法显然不会有太好的效果，因为primary的数据流是较为随机的。

4， 相似性查找
该方法在背景介绍中有提及，可参考[4,5]两文。

就我们的情况来说，我们可实现1,2两项技术，3只适用于备份领域，不过其效果极其显著。

III，小结
看完这些文献，我的感觉是去重在备份领域的可达到很好的效果，这样产品也很多，不过现在越来越重视处理速度。在主存领域，我想随着云计算的发展，虚拟机数据的缩减也是去重效果较好的地方，但处理速度现在还是问题。
算法方面，[1]文可以说是最重要的文章，他最早将处理速度提升至100M/s，而且提出使用blooming filter也被很多文章引用，即使是采用相似性查找方案的文章，也将[1]文作为对比文。
文献中倒是没什么文章提到硬件加速，我想，一方面，目前的去重瓶颈仍然在chunk index查找中的IO操作，hash算法并没有拖慢处理速度，另一方面，备份服务器的CPU占用率并不是那么重要。但是，如果将去重用到主存领域，硬件加速就显现出优势来了。

遗漏的一点，chunk index保存在SSD中我记得上下面某篇文章中提到过，且有参考文献。不过该文没有采用，认为会带来额外的硬件成本。
还有一些文章，并没有记录在上面，如在chunk index查找中使用B+树来提升查找速度，我觉得没什么新意，第一是常规手段，第二并不能解决查找中的IO操作。
另外，文件系统中采用去重的也没有文章提及。

IV，参考文献
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,