您现在的位置是：首页 > IT基础架构 > 计算存储 >

重复数据删除综述(2)：固定和可变长度数据块

2012-12-27 15:53:33作者：来源：

摘要为了更细粒度的检测重复数据，可以将文件分割成固定大小的数据块，这就是基于固定大小数据块的重复数据检测。实现时，首先将存储系统中所有的文件按固定大小划分成数据块，计算每个数据块的hash函数值，将所有的hash函数值单独存储起来构成hash值库。...

　　1.2 数据块级别相同

　　1.2.1 固定大小数据块

　　为了更细粒度的检测重复数据，可以将文件分割成固定大小的数据块，这就是基于固定大小数据块的重复数据检测。实现时，首先将存储系统中所有的文件按固定大小划分成数据块，计算每个数据块的hash函数值，将所有的hash函数值单独存储起来构成hash值库。当有新的数据需要存储时，同样按照这个固定的大小将其划分成数据块，用每块的hash函数值同hash值库中的逐一比较。如果发现新的数据块hash函数值已经存在于哈市值库中，说明这块数据已经在系统中存储过，无需再次存储，只要将指向这个hash函数值所代表的数据块的指针存入相应位置即可;如果新的数据块hash函数值不在hash值库中，则将其实际存储到系统中，并将新的hash函数值添加到库里。实现流程如下图所示。

　　图固定大小数据块检测

　　经典文献

　　u Venti: A new approach to archival storage

　　Quinlan S, Dorward S. In: Proc. of the 1st Usenix Conf. on File and Storage Technologies (FAST 2002). Berkeley: USENIX Association, 2002. 89–102.

　　几乎所有涉及dedupe的文章都提到了Venti系统。它是贝尔实验室设想的一款用于归档数据的网络存储系统原型。它和Plan 9操作系统绑定，所以不能用于诸如Windows，Linux之类系统的后端存储设备。Venti以固定大小数据块作为存储单位，并且计算每个数据块的SHA-1值作为块标识，通过比较块的hash值检测重复数据。

　　比较值得一提的是Venti的write-once策略。每个数据块占用唯一一个地址，多次写入相同的数据块地址相同，所以同一个数据块只存储一次。数据块不能删除，这也是永久或者备份存储的理想选择。另外，Venti还实现了快照功能。Venti 实现了一个针对大磁盘索引的cache，用以加速fingerprint 查找。由于fingerprint 当中没有位置信息，它的索引cache 不是很有效。尽管用8 个磁盘并行查找fingerprint，它的吞吐率只是局限于7MB/sec 以内。

　　1.2.2 可变大小数据块(基于文件内容的查找)

　　可变大小数据块的检测是基于文件内容的将文件分成大小不等的数据块，通常是利用Rabin指纹的方法计算出数据内容的指纹值。Rabin指纹是一种高效的指纹计算函数，利用hash函数的随机性，它对任意数据的计算结果表现出均匀分布。基于内容的数据块划分方法如下：

　　预先设定一对整数D，r(D>r)和一个滑动窗口的固定宽度l(实际中常用r=D-1)。对于一个序列S=S1,S2,……,Sn，当且仅当窗口的边缘停在某一个k位置，也就是子序列W=S(k-l+1),S(k-l+2),……,Sk的指纹函数计算结果为h(W) mod D = r，则k位置有一个D-match。k位置也就是某个数据块的边界位置。