集群重复数据删除策略的研究

陈 晓 张龙军 王 谦 武警工程大学信息工程系 陕西西安 71008

基金项目：国家自然科学基金（NO.61003250）

【文章摘要】

 　　提出了集群内的全局重复数据删除方案，运用 Bloom Filter 技术为集群中存储的所有数据块建立快速索引的摘要信息，组成一个可以检测重复数据的指纹摘要阵列（FSA），分布在存储节点前端的控制服务器，控制服务器节点将客户端发送到的数据块指纹合并成若干粒度大小均匀的超块，进行重复数据的检测，然后将超块有状态地路由到各个存储节点进行数据删重。利用 FSA 检测全局范围内所有存储节点之间的重复数据，获取较高的重复数据删除率，极大的提高了内存空间的利用率。

【关键词】

重复数据删除；指纹摘要阵列；超块

0 引言

随着大数据时代的发展，数据量正在爆炸式增长，数据更新变化也在时刻进行。数据量从TB 上升到PB 甚至EB，随着数据集关联性的日益繁杂，面向云环境的集群中心会产生大量冗余数据。调查发现云端数据中心有60% 以上数据是冗余的，这就为数据同步提出了巨大挑战。为支持云环境下分布式存储的特点， 单一的数据同步技术已难以满足节省存储空间和系统扩展的需求，集群内所有节点之间进行数据去重的数据同步技术应运而生。集群重复数据删除是在存储系统全局范围内进行分布并行的数据删重技术。它通过有效的数据路由指导策略将客户端上传的数据分发到集群内的存储节点进行数据删重。

1 Bloom Filter

我们假设 Bloom Filter 使用一个长度为 n 的位数组 N，首先将位数组N 的所有位初始化为0。设定一个包含 m 个元素的集合 S={x1, x2,…xm}， Bloom Filter 使用 k 个相互独立的哈希函数h1, h2,…,hk，它们分别将集合 S 中的每一个元素映射到位数组{1, 2, …,n} 的范围中，当有任意一个x 元素进入集合S 中，第 i 个独立哈希函数映射的位置N [hi(x)]（i =1, …, k）就会被置为 1。对于不同的元素，其独立的哈希函数可能会映射到同一位置，即某一位被重复地置为 1。例中采用 3 个相互独立的哈希函数，即 k = 3，当元素x1 和 x2 先后被插入到位数组N 时，有两个哈希函数映射到位数组中的第 8 位，此时只有第一次映射起作用，即位数组第8 位映射的是先进入集合的元素x1。

判断一个未知的元素 y 是否属于集合 S， 需要对元素y 应用 k 次哈希函数得到k 个哈希值，检查所有的哈希值对应的位 N [hi(y)]（i =1, …, k）是否都被置为了 1。如果都为 1，则 y 可能是集合中的元素，此时将这种情况视为 Positive，否则 元素y 就不属于集合S，这种情况为 Negative。y1 不是集合 S 中的元素， 而 y2 可能属于集合 S。

DDFS 重复数据删除系统设计使用一个 Bloom Filter 来表示整个集群中全部的数据块指纹，并被抽象成指纹摘要向量，它具有常量级的时间复杂度，是建立在磁盘索引访问之前的快速索引机制，能够较快的查询并判断重复数据块，可以较高的提升系统吞吐率。

2 基于 Bloom Filter 的全局数据删重策略

2.1 全局去重策略的设计与实现

利用Bloom Filter 机制，可以将集群内所有存储节点上存储的数据块指纹表示成Bloom Filter 指纹摘要（Fingerprint Summary），形成全局的快速索引序列。例如集群中有p 个存储服务器节点，假设所有节点的 Bloom Filter 长度全部为 n，并且所有节点采用k 个相同且相互独立的哈希函数。为实现全局的重复数据删除，将集群内每一个节点的Bloom Filter 指纹摘要聚合到一块，组成Bloom Filter 代表的阵列（Bloom Filter Array， BFA）， 保存到数据存储节点前端的控制服务器节点中心并分发到每个存储节点， BFA 又可称作指纹摘要阵列， 即Fingerprint Summary Arra，简称FSA，如下图 1 所示：

当集群服务器中心接受客户端发送的数据块指纹时，此指纹信息首先会传输到存储服务器节点前端的控制服务器中，并将数据块指纹按照均匀的粒度组成超块Q，根据Bloom Filter 阵列依次进行重复数据检测。检测完成后删除重复的数据，将可能不重复的数据有状态的路由到存储节点进行细粒度的检测，最后确定数据块是否是新块或是已存在的数据块。数据中心接收到客户端发送来的数据块指纹时，检测该块是新块还是已存储的数据块，其

图1 指纹摘要阵列040

软件开发

Software Development

电子制作

流程如图2 所示：

2.2 存储节点的去重策略

DDFS 系统为保持冗余的局部性， 采取了基于流的块排列（SISL）技术，在容器（Container）中根据先后的逻辑关系存储一个文件的数据块及相应指纹。冗余局部性是指一个数据块是重复块的时候，其附近的数据块极可能也是重复快。

控制中心服务器将超快指纹分发到存储节点之前，必须进行存储节点的选择。选取存储节点时，常用的方法是利用数据块指纹取模的算法，这样就会存在比较大的弊端，由于数据块在存储之前被置乱，所以一个存储节点存储的数据块可能来自于不同的文件，删重后的数据仍然会存储到此节点，数据的局部性便会受到一定的影响，进而影响后续数据删重的效果及效率。另一种方法是利用指纹前缀来选择存储节点，将属于同一类指纹前缀的数据块存放到一个节点，但是指纹前缀不能判断表数据块是否来自同一文件，因而数据的局部性也不能得到改善。

设计在选取存储节点时，首先，计算出节点内已存在的数据块指纹数{r1,r2,r3,…,rm}，所有的 m 个值可以反映出超块Q 与存储节点中数据的相似度。然后，计算各节点的相对存储使用率，以一个存储节点的存储使用率比整个服务器集群内所有节点的平均存储率来计算各个节点的相对存储使用率{w1,w2,w3,…,wm}，利用节点相对存储使用率可以为存储节点的相似度加权{ r1 /w1, r2/w2, r3/w3,…rm,/wm, }。最后，在存储节点中选取满足Idi 满足ri/wi=max{ r1 / w1, r2/w2, r3/w3,…rm,/wm, } 的重复数据删除节点作为超块Q 的路由目标节点。

2.3 指纹摘要阵列FSA 的同步

在前文叙述中，本章节结合Summary Cache 的协议保持各节点之间以及控制服务器节点的FSA 的数据同步，维护FSA 的一致性。在每个存储服务器节点都会保存一个全局的指纹摘要阵列FSA 的副本，这样当有新数据块存储到相应的存储节点时，该节点就会查询（读操作）此前存储的FSA 副本，并动态地更新（写操作）本地保存的FSA 副本阵列，即新数据块运用k 个哈希函数计算得出的值在指纹摘要阵列相应的行中置为1。此时数据中心前端的控制服务器节点中地FSA 保存的数据依然是之前存储的。这样，控制服务器节点与所有存储节点间的FSA 副本数据同步问题就变得尤为重要，它直接关系着集群内数据块的缩减率及去重的效果。

控制服务器节点的FSA 与各存储节点间的 FSA 副本的可以进行实时数据同步，也可以采取周期性数据同步的方式维护数据的一致性。实时性的数据同步需要在每次数据存储时，所有存储节点中的FSA 阵列都需要即时更新，可以运用基于副本的信息一致性策略[96] 进行个节点FSA 阵列的实时同步，但由于用户众多且更新频率较快的事实，会引起节点间数据实时同步的一致性维护策略较大的开销。本文采取了周期性数据同步的策略进行数据的一致性维护。周期性的方法则是指设置一定的时间间隔进行FSA 副本的同步操作。但周期性同步数据的过程中，可能有多个节点存储了新的数据块，即FSA 中有多条记录进行了修改

3 结束语

文章主要研究了集群内部的全局重复数据删除。删除集群内重复的数据，以节省存储空间。通过 FSA 可以在所有存储节点间进行全局范围的重复数据检测，以消除各节点间的冗余数据，获取较高的重复数据删除率，最大程度地节省集群系统的存储空间。

【参考文献】

[1] Mitzenmacher M. Compressed Bloom filters[J]. Networking IEEE/ACM Transactions on, 2002, 10(5):604-612.

[2] 魏建生. 高性能重复数据检测与删除技术研究[D]. 华中科技大学, 2012.

[3] 王龙翔, 张兴军, 朱国锋等. 重复数据删除中的无向图遍历分组预测方法[J]. 西安交通大学学报, 2013, 47(10): 51-56.

【作者简介】

陈晓（1991-），男，在读硕士研究生，主要研究领域为云计算.

张龙军，教授，主要研究方向为网络安全、云计算.

图 2 重复数据检测流程041