面向大数据的高效存储容量缩减技术研究

摘要

随着信息化的发展，全球数据量呈指数式增长，数据中心存储规模快速迈向了PB级甚至是EB级，其中包含了大量的冗余数据。这些冗余数据占用了大量的存储资源，导致存储系统性能降低，数据存储和管理成本增加等问题。在此背景下，存储容量缩减技术在不改变数据基本属性前提下，通过采用重复数据删除技术和数据压缩技术，有效地缩减数据量的规模，提高存储资源利用率，降低管理成本。存储容量缩减技术已经成为业界研究的热点，显示出重要的学术价值和应用价值。
　　然而，大数据的规模巨大、类型繁多、冗余量庞大以及对数据处理的速度要求较高等特点，导致存储容量缩减技术在面对大数据应用时仍然存在许多需要解决的技术问题。例如如何降低数据分块时间开销，减少冗余数据块发现时间以及提高数据压缩速度和压缩率等方面。针对上述问题，从存储容量缩减技术的数据分块策略、冗余数据块的发现机制以及数据块的高速压缩机制等方面进行深入的研究。具体来说，主要从以下三个方面提出了创新性理论或方法：
　　1.基于位串内容感知的数据分块策略（Bit-string Content-aware Chunking Strategy，BCCS）：围绕影响数据分块性能的各种因素进行分析和讨论，实现了一种新的基于位串的数字签名技术，并在此基础上提出了BCCS。BCCS从数据块每个正文字节中抽取某一特定比特来构成窗口特征数据，并使用位操作替代传统的比较操作。该策略充分利用每一次失败的匹配尝试所带来的特征信息，尽量排除尽可能多的不能匹配位置，从中获取最大跳跃长度，从而加快二进制串的匹配过程，降低确定块边界的CPU资源消耗。实验结果表明，对于可变数据测试集，相对Rabin算法，BCCS的数据块划分速度最多可以提高197％；对于固定数据测试集，相对于FSP算法，BCCS速度仅仅降低10.8%，而其数据压缩率却较FSP的0.977提高到了1.206，可以提高20%。
　　2.基于二级布隆过滤的冗余数据块发现机制（Redundant ChunkQuery Mechanism based on Two-staged Bloom Filter，RCQM-TBF）：针对数据指纹（FingerPrint,FP）数量巨大，不能完全存储在内存中，导致性能下降的问题，提出了RCQM-TBF。RCQM-TBF中第二级布隆过滤器作为第一级布隆过滤器结果的一个整体表现，其每一个比特位代表进入相同准二级假阳性误判状态的所有FP。对于FP假阳性访问，TBF通过降低二级布隆过滤机制中第一级和第二级过滤的假阳性误判率，快速判断新到达数据块的非存在性；对于FP正常性访问，TBF通过建立FP高速缓存链表和对应的FP预取机制来减少直接的硬盘访问，对新到达的数据块存在性进行快速判断；同时TBF创建了一个具有强全局散列特性的哈希函数族，减小碰撞发生的可能性。实验结果表明，对于非冗余测试数据集，RCQM-TBF的FP查询延迟性能和数据块的存储性能较采用标准布隆过滤算法的ZHU-BLOOM FILTER最多提升了28%；对于冗余测试数据集，RCQM-TBF的存储速度较ZHU-BLOOM FILTER最多可以提高100%到135%；当扩充服务器内存时，理论上RCQM-TBF可管理的存储数据容量最大可以达到64PB。
　　3.基于多矩阵并行匹配的高速数据压缩机制（Parallel MatchingLZSS based on Multiple Matrix，PMLZSS-MM）：为了加快压缩速度，并提高存储容量利用率，提出了PMLZSS-MM。该机制实现了一种GPU平台下的多矩阵并行匹配工作模式，将需要压缩的数据动态划分多个字典串和预读串，分别将其作为矩阵的纵轴和横轴，分解到GPU中的不同线程块中，形成多个矩阵进行并行匹配；而对于需串行执行的压缩编码生成部分，仍然在CPU上执行。通过合理的调度策略，协调两者共同完成任务。实验结果表明，PMLZSS-MM容量缩减率有所下降。相对于经典CPU平台上的串行LZSS算法，容量缩减率最多下降了1.5%。但PMLZSS-MM显著提高了大数据的压缩速度，当字典窗口设置为4KB，预读数据窗口设置为64B时，相对于CPU平台上的串行LZSS算法，其压缩吞吐率最大提高了18倍；相对于GPU平台上的并行CULZSS算法，其压缩吞吐率最大提高了20.8%。
　　综上所述，通过采用BCCS，有效地减小数据分块过程中的CPU资源消耗，提高发现块边界的速度；采用RCQM-TBF，提高数据指纹查询速度，获取高效的查询速度；引入PMLZSS-MM，进一步补充和优化前两项技术的不足，获取更高的存储容量缩减率。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 国内外研究概况

1.3 研究内容

1.4 论文组织结构

2 基于位串内容感知的数据分块策略

2.1 研究背景

2.2 问题的提出

2.3 基于位串内容感知的数据分块策略及实现

2.4 性能分析

2.5 性能评测

2.6 本章小结

3 基于二级布隆过滤的冗余数据块发现机制

3.1 研究背景

3.2 问题的提出

3.3 基于二级布隆过滤的冗余数据块发现机制及实现

3.4 二级布隆过滤性能分析

3.5 性能评测

3.6 本章小结

4 基于多矩阵并行匹配的高速数据压缩机制

4.1 研究背景

4.2 GPU硬件体系结构与工作模式

4.3 基于多矩阵并行匹配的无损压缩算法及实现

4.4 算法时间复杂度分析

4.5 性能评测

4.6 本章小结

5 总结与展望

致谢

参考文献

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

附录2 攻读博士学位期间申请发明专利与软件著作版权

附录3 攻读博士学位期间参加与主持的主要科研项目

附录4 缩略词简表

附录5 个人简历