【作者】 李玮；

【导师】 张大方；

【作者基本信息】 湖南大学 ， 计算机科学与技术， 2015， 博士

【摘要】 大数据正在成为继云计算、物联网、移动互联网之后新的信息革命高潮。无论是从数据传递及共享、数据存储,还是从数据检索及分析,信息技术正面临前所未有的挑战。信息表示和查询算法是进行数据传递及共享、数据存储、数据检索及分析时用到的关键技术之一。当数据膨胀时,借助简洁的数据结构表示信息,并研究与之对应的高效查询算法已成为提升和完成大规模数据管理的关键技术!作为信息表示和查询算法之一的布鲁姆过滤器(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能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高。更多还原

【Abstract】 As a new information revolution climax,big data emerges following cloud computing,Internet of things,mobile Internet.Big data has brought great challenges in data transfer and sharing,data storage,data retrieval and analysis.Information representation and query algorithms are key technologies in big data environment.When the data expands,developing efficient query algorithm with simple data structure has become one of the key technologies to enhance the effieicny of data management.As a succinct data structure supporting efficient information representing and query,Bloom filter(BF)has attracted lots of research interests and has been widely used in storage management and distributed systems.However,ever-increasing data in big data envieoments brings great challenges to apply Bloom Filter for supporting high speed and effiecent data respresent and manamgent in network filed and storage filed.Focusing on designing bloom filter in big data environment,this thesis makes following contributions.(1)Design of a hash Bloom filter for name lookup in named data networking.Quick name lookup is one of the key technologies to improve data packet forwarding rate in Named Data Networking(NDN).NDN uses a similar URL hierarchical naming scheme.Unlike fixed length IP addresses,NDN names have variable and unbounded length,which makes the name lookup more complex and difficult than IP addresses.To provide quick name lookup technique,this thesis designs a hash Bloom filter(HBF).HBF consists of g on-chip Counter Bloom filters(CBFs),g on-chip counters and g off-chip hash tables.Each hash table is associated with a CBF and a counter.To reduce the false positive rate introducing by unbalanced name insertion in to CBFs,we propose two-hash-choice algorithm which disperses the FIB/CS/PIT entries into g hash tables and CBFs.Moreover,HBF has a good feature of parallel processing of data packet forwarding because HBF adopts multiple hash tables and CBFs.Theoretical and simulated results demonstrate that HBF can achieve very efficient name lookup by well utilizing the on-chip memory through localization and filtering function of CBF.Therefore,the proposed HBF improves data packet forwarding rate and effectively avoiding flooding attacks.(2)Design of a data temperature perceptive Bloom filter for flash-based storage.Because of the inherent asymmetry of read and write speeds,out-of-place update,hot and cold data identification algorithm has become a key factor in improving the performance and reducing the flash storage costs.To identify the hot and cold data,this thesis designs a Data Temperature Perceptive Bloom Filter(DTPBF).DTPBF divides the period of data access record into n cycles.Based on round-robin fashion,DTPBF records data access frequency of each cycle through combination of a CBF and n BFs.The access frequency of each cycle is represented by a different temperature.The characteristic of the data access is calculated by utilizing n cycle temperatures.To guarantee single characteristic of the data,we utilize a bijective function to map n cycle temperatures into a single temperature value.Based on the single temperature value,the data with the same visiting regular pattern can be placed in same block in flash.Therefore,the proposed DTPBF can reduce the flash write magnification,improve flash write performance,enhance flash life and reliability.DTPBF also can identify the occasional hot data,which raises the flash buffer hit ratio,reduces the cost of data migration in hybrid storage mode and improves system efficiency.Theoretical and simulated results demonstrate that DTPBF can achieve low memory consumption and computational complexity.(3)Design of matrix-indexed Bloom filter(MIBF)for flash-based key-value storeIndexing structure is one of key technologies to improve the performance of system insertion and query.Directly using traditional B+ tree indexing in key-value storage based on flash easily leads to cascading updates from its parent node to the root node,which results in a serious decline in system performance.To solve this problem,this thesis designs a Matrix-Indexed Bloom filter(MIBF)for flash-based key-value store.MIBF is composed of multiple Bloom filter group(MBFG)represented by mxs bits matrix and additional Bloom filter(ABF).The core idea of MIBF is that flash page address of key-value pair is split into multiple bit groups,and MBFG is also divided into multiple groups correspondingly,each group bits are represented by the one group Bloom filter(BF)in MBFG,while the combined value of key and flash page address is inserted into ABF.When an element is queried according to the key,each BF group in MBFG generates a plurality of bit values and combines to generate the flash page address for the key-value pairs.In order to reduce pseudo flash page address generated by the MBFG due to false positive probability,pseudo flash page addresses are filtered out through the ABF,thereby achieving more accurate address location,reducing the number of flash access,and improving the system performance.Compared to previous work,the address location accuracy of MIBF query is improved and the access number of RAM and flash decreased significantly,which greatly improves the performance of solid state sisk(SSD)insertion and query.(4)Design of an accurate counter Bloom filter for Hadoop-Join algorithmWithout traditional data relational model,Key-value storage does not provide a similar SQL join language to user.Hadoop-Join algorithm is one of the key technologies to improve the efficiency of the comprehensive statistics analysis across large-scale distributed key-value data sets.However,hadoop is not very efficient to perform the join operation since it always processes all records in the datasets even in the cases that only small fraction of datasets are relevant for the join operation.An Accurate Counting Bloom Filter(ACBF)is proposed to filter out redundant intermediate records in join operation,which reduces communication costs and improves the performance of Hadoop-join algorithm.In order to take advantage of CBF free space to reduce the probability of false positive,we divide the counter vector of ACBF into the multilayer structure which organized by the offset index.The first level of ACBF is used to perform query operations for a set of membership,and the other layeres are used to represent insertion and deletion of the counter.In order to minimize false positive probability,the paper maximizes the size of the first layer to optimize the ACBF,while maintaining the normal function of CBF.Simulation results show that in the same situation of memory overhead,the false positives of ACBF is significantly lower than the CBF.ACBF is implemented the join operations in key-value database based on MapReduce model.The redundant data produced in the process of the shuffle is filtered out the through ACBF,which reduces network I/O,and further improves the performance of reduce-side join algorithm.(5)Design of accurate multi-dimension counting Bloom Filter aimed for multi-dimensional attribute dataPrecision multi-dimensional data representation and query algorithms become a challenging problem in dynamic big data enviroement.To conque this challenge,this thesis proposes an Accurate Multi-Dimension Counting Bloom Filter(AMD-CBF)query algorithm based on bijective function.When representing or querying an element,AMD-CBF needs two steps.The first step is to hash and map each attribute of the element to their corresponding Accurate Counting Bloom Flter(A-CBF).The second step is to transform all attributes of the element into a value by bijective function to represent the overall information of the element,then the value is hashed and mapped into a Combined Counting Bloom Fliter(C-CBF)for completing the representation and query confirmation of the elements overall.Both theoretical analysis and experiment demostrate that the AMD-CBF can support concise representation,approximate membership query and deletion of multi-Dimension data set and significantly lower false positive rate and improve query accuracy compared to similar researches.更多还原