基于有限二叉树布隆过滤器的去冗文件系统及其构建方法

摘要

本发明提供了一种有限二叉树布隆过滤器，以及基于该有限二叉树布隆过滤器的去冗文件系统及其构建方法。本发明有限二叉树布隆过滤器每层的节点数设置有上限，每个节点是一个二阶段布隆过滤器，每个二阶段布隆过滤器包括标准布隆过滤器和存储了各数据块的指纹和地址的第二部分。对数据块的指纹首先在标准布隆过滤器中查找，若未查找到，则该节点未命中，否则，继续查找第二部分，在第二部分找到完全匹配的指纹时，该节点命中，否则，该节点未命中。去冗文件及构建方法基于有限二叉树布隆过滤器实现文件的写入、读取和删除。本发明通过二次查询，减少了误判，具备低内存占用、低CPU使用、低额外空间占用、高去冗率存取和可扩展性优良的特点。

主权项

一种有限二叉树布隆过滤器，其特征在于，该布隆过滤器具有L层节点，L为正整数，第1层具有两个节点，设每层的节点数上限为Q，A通过对以2为底Q的对数取整得到，则第i层的每个节点在第i+1层都具有两个子节点，i为1到A‑1；第j层的每个节点在第j＋1层都具有1个子节点，j为A到L；每个节点是一个二阶段布隆过滤器，每个二阶段布隆过滤器包括两部分，第一部分是标准布隆过滤器，第二部分存储了各数据块的指纹和存储地址；第一部分的标准布隆过滤器，包括一个包含有K个哈希函数h11～h1K的集合和一个位数组；位数组中包含w个元素，依次对应1～w的整数，对每个待查找的数据块指纹，分别通过哈希函数h11～h1K计算哈希值，得到K个整数值；当位数组中对应K个整数值的元素都设置为1时，表示该指纹在标准布隆过滤器中命中，否则表示该指纹在该节点中不存在；第二部分包括哈希函数h2、起始位置数组、结束位置数组和大数组；将指纹对应的K个整数值通过哈希函数h2计算，得到一个整数index；整数index所表示的一类数据块指纹，在大数组中存储的起始位置和结束位置，分别存储在起始位置数组和结束位置数组的第index元素中；将经过哈希函数h11～h1K的集合和哈希函数h2计算得到相同整数index的数据块指纹分为同一类数据块指纹；大数组中的每一项记录一个数据块的指纹、存储地址、引用次数和存储同类数据块指纹的下一项地址；当某数据块的指纹在标准布隆过滤器中命中时，将该指纹对应的K个整数值输入第二部分，通过哈希函数h2计算得到整数index，在大数组中从起始位置数组第index元素记录的位置开始查找，在查询完大数组的当前项后，按照当前项所存储的下一项地址，找到对应的项继续查找，如果找到完全相同的指纹，表示该数据块为重复数据块，当前节点被命中，在大数组存储该指纹的项中更新引用次数；若直到结束位置数组第index元素记录的位置查询结束，都没有找到完全相同的指纹，则表示该指纹在该节点中不存在；当某个数据块的指纹在所述的有限二叉树布隆过滤器的各个节点中都没有查找到，则该数据块为新数据块，在未载满的节点中加入该新数据块的信息，具体是，将该新数据块的指纹经过节点中K个哈希函数h11～h1K计算得到K个整数，在节点中的位数组对应该K个整数的元素设置为1，在节点的大数组中新增一项，记录该新数据块的指纹、存储地址、引用次数和存储同类数据块指纹的下一项地址，同时在起始位置数组和结束位置数组中更新该新数据块指纹所属一类指纹在大数组中的起始位置和结束位置。