基于Bloom Filter的重复数据删除技术研究与应用

摘要

在大数据时代，每天都会产生大量的数据，而在这些产生的数据中有很大部分是重复数据，如何对海量重复数据进行快速检索越来越受到人们的关注。
　　Bloom Filter作为一种轻量级的数据结构在数据的检索中受到了广泛的应用，但是Bloom Filter也存在着不足之处，由于其是一种概率型数据结构，故在数据的检索中存在误判的发生，同时Bloom Filter只针对于静态数据集的表示与查找，而不能进行动态扩展存储。近年来，针对Bloom Filter以上所提到的不足之处存在多种改进，其中拆分Bloom Filter和动态Bloom Filter实现了元素的动态增长存储，从而解决了Bloom Filter静态存储的问题，并且能够有效地减少误判率，但是拆分Bloom Filter和动态Bloom Filter却增加了元素的查询时间开销。
　　本文根据当前Bloom Filter的动态存储以及查询等问题，提出了多路平衡型矩阵Bloom Filter(Multi-groups Balance Matrix Bloom Filter,M-BMBF),M-BMBF根据数据集合大小建立一个r×m矩阵型Bloom Filter，设计多个定位哈希函数将该矩阵Bloom Filter分为多组（多路）以实现平衡插入和高效查询操作。为减缓Bloom Filter中比特的消耗速度，应用一种“最长位匹配”填充方式，新元素的插入将从多路备选Bloom Filter中选择新置为1比特个数最少的Bloom Filter中进行。
　　HDFS是一种开源的分布式文件系统，为了保证文件的可靠性，通常在HDFS中会存储文件的多个副本，默认是3个，当用户每一次向HDFS中上传同一个文件时，在HDFS中都会保留该文件的多个副本，故在HDFS中存在着大量的重复数据，而HDFS对用户所上传的重复数据并没有做出有效的处理，都将其视为新数据写入系统中，同时还在系统中保留多个副本，导致存储空间的极大浪费，本文最后在对HDFS进行深入的分析和研究的基础上，设计和实现了一个基于M-BMBF的HDFS重复数据删除系统，并对系统进行了测试，实验结果表明，相较典型拆分Bloom Filter，M-BMBF能在维持算法消耗时间为常量的基础上，有效节省存储空间，降低误判率，同时通过M-BMBF算法能够通过快速判断重复数据从而节省数据上传到HDFS的时间以及节省HDFS的存储空间。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 国外研究现状

1．2．2 国内研究现状

1．3 论文主要工作

1．4 论文结构

第2章 Bloom Filter及其应用研究

2．1 引言

2．2 Bloom Filter的发展与应用

2．3 Bloom Filter相关算法

2．3．1 Bloom Filter算法

2．3．2 拆分Bloom Filter

2．3．3 动态Bloom Filter

2．4 小结

第3章 一种多路平衡型矩阵Bloom Filter

3．1 引言

3．2 多路平衡型矩阵Bloom Filter

3．2．1 算法设计思想

3．2．2 算法实现

3．2．3 性能分析

3．3 小结

第4章 基于Bloom Filter的分布式重删存储系统的设计与实现

4．1 引言

4．2 HDFS技术背景

4．2．1 HDFS架构

4．2．2 HDFS读操作

4．2．3 HDFS写操作

4．3 系统的需求分析

4．3．1 系统设计目标

4．3．2 系统架构

4．3．3 系统功能需求分析

4．4 系统设计与实现

4．4．1 客户端模块

4．4．2 重复数据删除端模块

4．4．3 存储端模块

4．5 系统重删工作流程

4．6 小结

第5章 实验与结果分析

5．1 引言

5．2 实验环境

5．3 实验结果与分析

5．3．1 M-BMBF性能测试

5．3．2 M-BMBF重删系统性能测试

5．4 小结

结论

参考文献

附录A 攻读硕士学位期间所发表的学术论文

附录B 攻读硕士学位期间所参与的科研项目

致谢