面向大数据的高效布鲁姆过滤器研究与应用

摘要

大数据正在成为继云计算、物联网、移动互联网之后新的信息革命高潮。无论是从数据传递及共享、数据存储，还是从数据检索及分析，信息技术正面临前所未有的挑战。信息表示和查询算法是进行数据传递及共享、数据存储、数据检索及分析时用到的关键技术之一。当数据膨胀时，借助简洁的数据结构表示信息，并研究与之对应的高效查询算法已成为提升和完成大规模数据管理的关键技术！作为信息表示和查询算法之一的布鲁姆过滤器(BF)是一种空间效率很高的随机数据结构，具有计算复杂度低、并行程度高等优势，已经广泛应用于数据库、分布式系统、网络等场景中。
　　本论文针对大数据时代的应用场景，从命名数据网络(NDN)路由器中名字快速查找、闪存中数据温度识别、闪存键值存储的索引结构、Hadoop-Join算法、多维属性数据集查询等五个方面展开BF研究，设计新的适应于不同环境与应用的高效BF，本文创新性研究成果主要体现在以下五个方面:
　　(1)设计了一种面向NDN中名字查找的哈希布鲁姆过滤器
　　名字查找算法是提高NDN中数据包转发速率的关键技术之一。NDN使用类似URL层次化的命名机制，一个名字由没有个数限制的词元组成，每个词元是一个可变长的字符串。这种命名特点使得名字查找比IP地址查找更加复杂、更加困难。为了实现快速名字查找，本文设计了一种面向NDN中名字查找的哈希布鲁姆过滤器(HBF)。HBF由位于片内存储器中的g个计数器布鲁姆过滤器(CBF)、g个计数器和位于片外存储器中的g个哈希表组成，每个哈希表与1个CBF和1个计数器关联。为了避免因部分CBF存入名字过多导致的HBF高误判率，HBF通过二次哈希选择算法将NDN路由器中FIB/CS/PIT表项完整信息均匀分散保存于g个CBF和g个哈希表中，同时也利于数据包转发的并行处理。理论分析和实验结果表明HBF利用片内存储器中CBF的定位与过滤作用，大幅度减少片外存储器的访问开销，提高数据包转发速率，同时有效避免泛洪攻击。
　　(2)设计了一种面向闪存的数据温度感知布鲁姆过滤器
　　考虑到闪存的读写不对称、异地更新等特点，冷热数据识别算法就成为提高闪存性能和降低存储成本的关键因素。为了提高冷热数据识别精度，本文设计了一种面向闪存的数据温度感知布鲁姆过滤器(DTPBF)。DTPBF将闪存中一段时间内的数据访问记录划分为n个周期，通过1个CBF与n个BF组合依据Round-robin方式记录每个周期内的数据访问频度。每个周期内访问频度用不同温度来表示，并将每个周期的温度通过双射函数映射成一个温度，该温度就代表该数据在这段时间内的访问特性。根据DTPBF提供的数据温度，闪存就能将具有相同访问特性或规律的数据保存于闪存中相同物理块上，从而降低闪存写入放大率、提高闪存写性能、提高闪存寿命和可靠性;DTPBF也能识别偶尔变热的数据，提高闪存中缓冲区命中率，有效降低混合存储模式（硬盘+闪存）中数据迁移成本，提高系统效率。理论分析和实际实验结果表明DTPBF具有较小的内存消耗和计算复杂度低等特点。
　　(3)设计了一种面向闪存键值存储的矩阵索引布鲁姆过滤器
　　索引结构是提高闪存键值存储插入和查询性能的关键技术之一。闪存键值存储中直接使用传统B+树建立索引容易导致其父节点直至树根节点的级联更新，致使系统性能严重下降。为了解决此类问题，本文设计了一种面向闪存键值存储的矩阵索引布鲁姆过滤器(MIBF)。MIBF由m×s的比特位矩阵表示的多个布鲁姆过滤器组(MBFG)和一个附加布鲁姆过滤器(ABF)组成，其核心思想是借鉴编码器原理，将键值对的闪存页地址被拆分为多组比特，每组比特采用MBFG中的一组布鲁姆过滤器(BF)来表示，同时将键值对的key与闪存页地址组合值存入ABF中。根据key查询value时，MBFG中的每组BF产生多个比特值，组合生成键值对的闪存页地址，并通过ABF滤掉部分伪闪存页地址，达到较精确地址定位，降低闪存访问次数，提高系统性能。
　　(4)设计了一种面向Hadoop-Join算法高精度计数器布鲁姆过滤器
　　Key-value存储没有传统数据库中的数据关系模型，未向用户提供类似SQL连接操作语句，应用层需要编程实现多个数据集的Join操作。Hadoop-Join算法是提高大规模分布式key-value多数据集综合统计分析效率的关键技术。为了克服Hadoop计算环境中没有索引支持而带来Join操作性能下降的问题，本文设计了一种高精度计数器布鲁姆过滤器(ACBF)过滤掉不参与Join操作的数据记录，减少通信成本，提高Hadoop-Join算法性能。ACBF主要思想是充分利用CBF的空闲空间来降低假阳性误判概率。ACBF将CBF中计数器向量划分为由偏移索引组织的多层结构，第一层次用于执行集合成员查询操作，而其它层用于表示插入和删除的计数器。本文通过优化ACBF第一层大小来最大程度地降低ACBF假阳性误判概率，同时保持其标准CBF功能不受影响。仿真结果表明在相同内存开销情况下，ACBF假阳性要明显低于CBF;基于ACBF的Hadoop-Join算法有效过滤掉Shuffle过程中冗余数据记录，大幅度减少网络I/O和Reduce端的无效操作，进一步提高了Hadoop-Join算法性能。
　　(5)设计一种面向多维属性数据的高精度多维计数布鲁姆过滤器
　　大数据时代，数据结构复杂，元素属性多维化。在快速变化的海量数据中通过高精度的多维属性数据的信息表示和查询算法迅速地完成数据的价值“提纯”，成为有效进行大数据处理过程中极具挑战性的问题。在分析现有针对多维属性数据表示的布鲁姆过滤器特点的基础上，本文设计了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法。AMD-CBF中元素表示和查找分两步进行，第一步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第二步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息，然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF)，完成元素整体属性的表示和查询确认。理论分析和仿真实验结果表明，AMD-CBF能够支持多维集合元素的高效表示和查询及删除，相比同类研究查询假阳性降低明显，查询精度大幅度提高。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 论文研究背景-大数据时代

1．2 论文研究问题的提出及意义

1．2．1 数据传递及共享技术在大数据时代面临的挑战

1．2．2 数据存储技术在大数据时代面临的挑战

1．2．3 数据检索及分析技术在大数据时代面临的挑战

1．3 论文主要研究内容及贡献

1．4 论文结构与章节安排

第2章 布鲁姆过滤器概述及相关工作

2．1 布鲁姆过滤器工作原理

2．1．1 标准布鲁姆过滤器

2．1．2 标准计数器布鲁姆过滤器

2．2 布鲁姆过滤器国内外研究现状

2．3 布鲁姆过滤器典型扩展算法介绍

2．4 小结

第3章 面向NDN中名字查找的哈希布鲁姆过滤器

3．1 引言

3．2 背景及相关工作

3．2．1 NDN数据包转发机制介绍

3．2．2 相关研究成果介绍

3．3 哈希布鲁姆过滤器

3．3．1 HBF结构和原理

3．3．2 HBF算法分析

3．3．3 HBF算法实现

3．4 实验评估

3．4．1 实验方案及数据

3．4．2 HBF中插入CBF中名字个数均衡度

3．4．3 HBF误判率

3．4．4 HBF片内存储器访问次数

3．4．5 HBF片外存储器访问次数

3．4．6 HBF实际总体访问成本对比分析

3．4．7 HBF与d-left HTPIT访问次数及访问成本对比

3．5 小结

第4章 面向闪存的数据温度感知布鲁姆过滤器

4．1 引言

4．2 相关工作

4．3 数据温度感知布鲁姆过滤器

4．3．1 设计思想和动机

4．3．2 DTPBF结构和原理

4．3．3 DTPBF算法分析

4．4 实验评估

4．4．1 实验方案及实验数据

4．4．2 实验结果分析

4．5 小结

第5章 面向闪存键值存储的矩阵索引布鲁姆过滤器

5．1 引言

5．2 背景及相关工作

5．2．1 SkimyStash

5．2．2 BloomStore

5．3 矩阵索引布鲁姆过滤器

5．3．1 设计思想和动机

5．3．2 MIBF结构和原理

5．3．3 MIBF算法分析

5．3．4 MIBF算法实现

5．4 实验评估

5．4．1 模拟数据实验

5．4．2 实际数据实验

5．5 小结

第6章 面向Hadoop-Join算法的高精度布鲁姆过滤器

6．1 引言

6．2 背景及相关工作

6．3 高精度布鲁姆过滤器

6．3．1 ACBF构造原理

6．3．2 ACBF优化

6．3．3 模拟数据实验结果

6．4 ACBF在Hadoop中实现

6．4．1 MapReduce介绍

6．4．2 基于ACBF的Reduce-side Join算法

6．4．3 实验结果

6．5 小结

第7章 面向多维属性数据的高精度多维计数布鲁姆过滤器

7．1 引言

7．2 多维计数布鲁姆过滤器相关工作

7．3 高精度多维计数布鲁姆过滤器

7．3．1 AMD-CBF结构和原理

7．3．2 AMD-CBF理论假阳性计算

7．3．3 AMD-CBF实现算法

7．4 AMD-CBF实验评估

7．4．1 模拟数据实验

7．4．2 实际数据实验

7．5 小结

结论

参考文献

致谢

附录A 攻读学位期间发表的学术论文及著作

附录B 攻读学位期间主持或参与科研、专利