高性能重复数据检测与删除技术研究

摘要

信息技术的不断突破和发展推动全球进入大数据时代。近年来,数据去重作为提高硬盘存储系统空间效率和降低数据维护成本的关键技术成为存储学术界和工业界的研究热点。数据去重是在数据集或数据流中发现和消除重复内容以提高数据的存储和/或传输效率的过程。一般来说,发现和消除重复数据的粒度可以是文件、字节串、定长分块或变长分块。研究如何高效地界定、检测和删除重复数据对构建高性能去重存储系统十分重要。
　　可变长度分块技术能够有效侦测到相似文件之间的重复内容,文件级去重技术则能够在更大粒度上发现和消除重复内容,从而降低块级去重的计算和查找复杂度。针对当前同时在文件级和变长块级消除冗余的数据去重方法,提出基于多核并行的流水化的两级指纹计算方法PDF。通过分解指纹计算的主要任务,PDF使用多个数据缓存消除计算任务间的数据依赖和缓存竞争,并采用流水调度方式将各计算任务部署到不同的处理器核,从而实现在单次内容扫描中同时生成数据的文件级和块级指纹。实验结果表明,PDF可达到比传统多线程方法更高的指纹计算性能。
　　基于滑动窗口模型的重复元素检测是统计和分析流式数据的重要技术手段,缓存滑动窗口内动态更新的元素序列需要消耗大量内存且具有较高的重复元素查询复杂度。现有支持重复元素检测的快速索引方法存在内存效率低和不可扩展等问题,因此提出可在滑动窗口模型下对流式数据进行重复元素快速检测的分离计数型布隆过滤器阵列(Detached Counting Bloom filter Array,DCBA)。DCBA由一组同构的分离计数型布隆过滤器(Detached Counting Bloom Filter,DCBF)构成,其中的布隆过滤器用于描述滑动窗口内元素的成员资格,而计数器组(计时器组)用于记录元素的时间戳。DCBA以循环先入先出队列的方式工作,位于队尾的DCBF处于填充状态以容纳新元素,位于队首的DCBF处于衰减状态以淘汰旧元素,中间满载的DCBF相对稳定且其计时器组可被转储到硬盘以节约内存资源。DCBA的大部分DCBF组件都具有稳定性,因此其可被高效同步到多个节点用于共享信息或增强可靠性,也可进一步将其扩展部署到多个节点以在分析大数据流时描述超大容量滑动窗口。数学分析和实验数据表明,DCBA的内存空间效率和可扩展性明显优于已有解决方案。
　　存储系统中的数据集通常具有较强的可扩展性,采用固定容量的快速索引方法描述可扩展数据集合有两个明显缺点。首先,若集合元素的实际数量超过索引的设计容量,则需要较大的时间和空间开销重建整个索引;其次,若集合基数需要很长的时间才能增长到索引的设计容量,则索引机制需要长期占据不必要的内存资源,降低了内存空间利用率。因此,提出动态布隆过滤器阵列(Dynamic Bloom filter Array,DBA)用于描述存储系统中的可扩展数据集并支持重复元素快速检测。DBA以布隆过滤器为基本组件,具有较高的内存空间效率,其可根据数据集合规模的增长按需创建新的布隆过滤器以扩展索引容量。DBA采用优化的内存数据结构以增强索引单元的访问并行度和提高查询效率。通过局部调整布隆过滤器成员的设计容量或误判率阈值,DBA可有效控制整体查询准确度。如果将集合划分为不相交的子集并分别采用不同的布隆过滤器作为索引,则DBA可根据查询结果直接定位疑似重复元素所对应的子集。针对去重存储系统批量回收空间的特点,DBA采用懒惰更新策略支持元素删除。
　　构建可扩展的高性能去重存储系统面临两大挑战。首先,大数据集的全量索引可能溢出可用内存空间,从而导致查找重复数据对象时的硬盘访问瓶颈。其次,去重存储系统扩展到多个节点时必须有效消除节点间的重复内容,以免形成孤岛效应。已有去重方法在部分或同时解决上述问题时无法完全消除存储系统中的重复数据,因此提出面向备份存储系统的可扩展的高性能精确去重方法 MAD2以同时在文件级和块级检测和消除重复数据。MAD2采用四种技术提高去重性能和实现可扩展性。首先,MAD2创建哈希桶矩阵(HBM)作为存储数据指纹的全量索引,HBM的各行可用于保存指纹序列的局部性。其次,MAD2采用动态布隆过滤器阵列(DBA)作为常驻内存的快速索引,用以加速重复指纹的检测过程。再次,MAD2设计双缓存机制捕捉和挖掘指纹序列的局部性,并提高HBM的访问效率。最后,MAD2采用基于分布式哈希表(DHT)的数据路由策略将备份数据划分为不相交的子集并分配到多个存储节点,在实现可扩展性的同时保持负载平衡。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 数据去重的研究背景

1.2 重复数据的界定方法

1.3 去重效率的评估方法

1.4 数据去重的研究现状

1.5 本文的主要研究内容

2 数据指纹的快速计算方法

2.1 可变长度分块技术

2.2 两级去重方法的基本框架

2.3 两级指纹的流水计算方法

2.4 实验评估与结果分析

2.5 本章小结

3 流式数据重复元素的快速检测方法

3.1 静态数据集的快速索引方法

3.2 非可扩展动态数据集的快速索引方法

3.3 分离计数型布隆过滤器阵列

3.4 理论分析与实验评估

3.5 本章小结

4 可扩展数据集重复元素的速判方法

4.1 可扩展数据集的快速索引方法

4.2 动态布隆过滤器阵列

4.3 实验评估与理论分析

4.4 本章小结

5 高性能可扩展的数据去重方法

5.1 去重存储系统的研究现状

5.2 MAD2数据去重方法

5.3 实验评估与结果分析

5.4 本章小结

6 全文总结

致谢

参考文献

附录1 攻读博士学位期间发表的学术论文

附录2 攻读博士学位期间参加的科研项目及申请的专利