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

摘要

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

说明书

技术领域

本发明属于冗余数据管理技术领域，涉及一种基于有限二叉树布隆过滤器的去冗文件系 统及其构建方法，用于解决动态规模数据存储问题。

背景技术

在数字时代，数据的容量和复杂度呈爆炸性增长。据国际数据公司统计，世界上接近75% 的数据是副本——也就是说，只有25%的数据是唯一的，而且超过90%的冗余数据存在于备 份文件中。随着云存储和云计算应用的不断普及，在不久的将来数据中心可能会不断涌现。 应用数据去冗技术存储这些大数据，可以减小数据的冗余率，提高数据存储和传输效率。

最常见的去冗方式是将完整文件切分成较小的文件块，找出其中的冗余数据。通过比较 文件块的“指纹”——由文件块内容计算得出的MD5值，可以判断两个文件块是否相同。但 是，块级去冗面临着如何快速查找庞大的索引，最小化额外存储空间和额外内存占用的问题。

基于文件块的在线去冗文件系统的关键问题可归结如下：

◆快速判断文件块是否存在并快速定位块。

◆合理的内存、存储器、处理器的使用。

◆理想的读写速度。

◆可扩展性强，可存储动态规模数据。

现有一些去冗设计应用哈希表查找大索引。但是为了达到快速查找的时间要求，哈希表 的负载因子要远低于50%，以致和其他方式相比，哈希表占用的空间要多得多。这样就不能 将整个哈希表装入到主存中，而外存的延迟很大。一种解决方案便是将哈希表存储到单独的 额外固态硬盘（SSD）中。这种方案确实取得了不错的效果，但是SSD十分昂贵。

另一种方案是将布隆过滤器装载到内存中。布隆过滤器可以在常数时间内，以极大的正 确率判定文件块是否存在。如果不存在，立即返回。而且布隆过滤器占用空间较少。若每个 文件块的大小为8KB，则需要1GB的内存空间来存储8TB实际数据的信息，这种情况下的 出错概率非常低，为2%。但是普通的定长布隆过滤器只能判定文件块不存在，不具备块定位 的功能，而且随着存入数据量的增加，判定存在的出错概率也会不断上升。

发明内容

本发明根据传统去冗文件系统设计存在的问题，提出了一种基于有限二叉树布隆过滤器 的去冗文件系统及其构建方法。

本发明首先提供了一种有限二叉树布隆过滤器，具有L层节点，L为正整数，第1层具 有两个节点，设每层的节点数上限为Q，节点数首次达到上限的一层时，有限二叉树的高度 A＝[log₂ Q]，A由对以2为底Q的对数取整得到，[.]表示取整。则第i层的每个节点在第i+1 层都具有两个子节点，i为1到A-1；第j层的每个节点在第j＋1层都具有1个子节点，j为 A到L。每个节点是一个二阶段布隆过滤器，每个二阶段布隆过滤器包括两部分，第一部分 是标准布隆过滤器，第二部分存储了各数据块的指纹和存储地址。

第一部分的标准布隆过滤器，包括一个包含有K个哈希函数h1₁～h1_K的集合和一个位数 组；位数组中包含w个元素，依次对应1～w的整数，对每个待查找的数据块指纹，分别通 过哈希函数h1₁～h1_K计算哈希值，得到K个整数值；当位数组中对应K个整数值的元素都 设置为1时，表示该指纹在标准布隆过滤器中命中，否则表示该指纹在该节点中不存在。

第二部分包括哈希函数h2、起始位置数组、结束位置数组和大数组；指纹对应的K个整 数通过哈希函数h2计算，得到一个整数index；整数index所表示的一类数据块指纹，在大 数组中存储的起始位置和结束位置，分别存储在起始位置数组和结束位置数组的第index元 素中；将经过哈希函数h1₁～h1_K的集合和哈希函数h2计算得到相同整数index的数据块指纹 分为同一类数据块指纹；大数组中的每一项记录一个数据块的指纹、存储地址、引用次数和 存储同类数据块指纹的下一项地址。

当某数据块的指纹在标准布隆过滤器中命中时，将该指纹对应的K个整数值输入第二部 分，通过哈希函数h₂计算得到整数index，在大数组中从起始位置数组第index元素记录的位 置开始查找，在查询完大数组的当前项后，按照当前项所存储的下一项地址，找到对应的项 继续查找，如果找到完全相同的指纹，表示该数据块为重复数据块，当前节点被命中，在大 数组存储该指纹的项中更新引用次数；若直到结束位置数组第index元素记录的位置查询结 束，都没有找到完全相同的指纹，则表示该指纹在该节点中不存在。

当某个数据块的指纹在所述的有限二叉树布隆过滤器的各个节点中都没有查找到，则该 数据块为新数据块，在未载满的节点中加入该新数据块，具体是，将该新数据块的指纹经过 节点中K个哈希函数h1₁～h1_K计算得到K个整数，在节点中的位数组对应该K个整数的元 素设置为1，在节点的大数组中新增一项，记录该新数据块的指纹、存储地址、引用次数和 存储同类数据块指纹的下一项地址，同时在起始位置数组和结束位置数组中更新该新数据块 指纹所属一类指纹在大数组中的起始位置和结束位置。

本发明还提供了一种基于上述的有限二叉树布隆过滤器的去冗文件系统，包括：文件系 统接口、MD5生成器、有限二叉树布隆过滤器、索引文件和块存储器。文件系统接口接收外 部应用程序发来的写入文件命令时，将待写入文件传给指纹生成器。指纹生成器将待写入文 件进行定长划分，并为划分得到的每个数据块生成指纹。索引文件为每个文件建立一个索引， 将该文件的各数据块的指纹和存储地址按块顺序写入索引中。文件系统接口在接收到外部应 用程序发来的读取文件命令时，根据文件路径在索引文件中找到要读取文件的索引，根据索 引中各数据块的地址，依次从块存储器中读取各数据块的内容并输出给外部应用程序。指纹 生成器将各数据块及对应的指纹传送给有限二叉树布隆过滤器。有限二叉树布隆过滤器根据 数据块的指纹，对数据块进行查重，当某个数据块为新数据块时，为该数据块申请存储地址， 将申请的地址及数据块传给块存储器，并将数据块的指纹及存储地址传给索引文件，当某个 数据块为重复数据块时，直接将该数据块的指纹及存储地址传给索引文件。块存储器将数据 块的内容存入所申请的存储地址中。

本发明的一种基于有限二叉树布隆过滤器的去冗文件系统的构建方法，包括如下步骤：

步骤1：对待写入的文件进行定长分块，并计算每个数据块的指纹。

步骤2：将有限二叉树布隆过滤器中，未满载的节点保留在内存中，每层任选一个节点 保留在内存中，部分满载的节点只保留第一部分在内存中。所述的有限二叉树布隆过滤器， 第一层中左节点标记为0，右节点标记为1，同一父节点的左节点标记为0，右节点标记为1； 第1层节点的索引值就是该节点的标记值，第2层到第A层的任一节点的索引值为父节点的 索引值附带上该节点的标记值组成，第A+1层到第L层的任一节点的索引值就是父节点的索 引值，索引值为由0和1组成的二进制串。

步骤3：将每个数据块的指纹输入有限二叉树布隆过滤器中进行查找，首先从内存中保 留的节点中寻找索引值匹配的节点，并从所找到的各节点中查询数据块的指纹，如果查找到， 执行步骤4，如果未查找到，执行步骤5；所述的索引值匹配是指：设索引值q位，如果数据 块指纹的二进制串的前q位与索引值的q位相同，则说明数据块的指纹和节点的索引值匹配。

步骤4：该数据块为重复数据块，将与该数据块命中的节点处于同层的节点都取入内存 中，并保证有限二叉树布隆过滤器的每一层的任一节点和未满载的节点都保留在内存中，然 后取下一个数据块的指纹继续执行步骤3。

步骤5：该数据块为新数据块，为该数据块申请存储地址，块存储器将数据块的内容存入 所申请的存储地址，并在有限二叉树布隆过滤器存储该数据块的信息；保证有限二叉树布隆 过滤器未满载的节点都保留在内存中，然后取下一个数据块的指纹，继续执行步骤3。在未 满载的节点中，寻找与该数据块的指纹匹配的索引值的节点，如果找到，存储新数据块的信 息，如果没有找到，有限二叉树布隆过滤器最底一层与该数据块指纹匹配的索引值的节点生 成新的子节点，将该新数据块的信息存储到索引值匹配的新节点中。

步骤6：当文件的所有数据块的指纹都经过有限二叉树布隆过滤器查找后，在索引文件中 该文件对应的索引中，依据数据块在文件中的顺序，写入索引文件各数据块的指纹和存储地 址。

步骤7：当外部应用程序发来读取文件命令时，根据文件路径在索引文件中找到要读取 文件的索引，根据索引中各数据块的存储地址，依次从块存储器中读取各数据块的内容并输 出给外部应用程序。

步骤8：当外部应用程序发来删除文件命令时，根据文件路径在索引文件中找到要删除 文件的索引，根据索引找到各数据块的指纹和存储地址。对每个数据块的指纹在有限二叉树 布隆过滤器中查找，在所找到的节点中查看该数据块的引用次数是否为1，若是，在根据该 数据块的存储地址在块存储器中删除该数据块的内容，若引用次数大于1，则将引用次数-1。 当要删除文件的各数据块都经过有限二叉树布隆过滤器的查找和处理后，在索引文件中删除 该文件的索引。

本发明结合树形布隆过滤器和二阶段布隆过滤器的特点设计出有限二叉树布隆过滤器， 并基于所述有限二叉树布隆过滤器提供了一种去冗文件系统和去冗文件系统构建方法。本发 明具有如下优点和积极效果：

（1）由于每个节点都是一个二阶段布隆过滤器，并利用有限二叉树布隆过滤器存储文件 数据块的特征值（指纹）及对应存储地址，二次查询，减少了误判；

（2）由于有限二叉树布隆过滤器的每一层都至少有一个节点载入内存，一旦在该层命中 冗余块，随即载入该层的所有节点，根据局部性原理，接下来的文件块很有可能在该层命中， 因此实现了很高的去冗率存取；

（3）本发明还具备低内存占用、低CPU使用、低额外空间占用、可扩展性优良的特点。

附图说明

图1是二阶段布隆过滤器的构造图；

图2是本发明的基于有限二叉树布隆过滤器的去冗文件系统的结构示意图；

图3是当层节点上限为8时的有限二叉树布隆过滤器结构示意图；

图4是数据块IO和计算的分离设计示意图；

图5是本发明的去冗文件系统的构建方法中写入文件的流程示意图。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。通过足够详细的描述这些实施 示例，使得本领域技术人员能够理解和实践本发明。在不脱离本发明的主旨和范围的情况下， 可以对实施做出逻辑的、实现的和其他的改变。因此，以下详细说明不应该被理解为限制意 义，本发明的范围仅仅由权利要求来限定。

数据块的指纹可以采用冲突率低的算法来设定，如MD5，SHA等算法，本发明具体实施 的说明中，数据块的指纹采用MD5算法（Message-Digest Algorithm5，信息-摘要算法5）得 到，得到的MD5值作为数据块的指纹。

本发明提供的有限二叉树布隆过滤器，具有L层节点，L为正整数，第1层具有两个节 点，设每层的节点数上限为Q，A＝[log₂ Q]，A是以2为底Q的对数的整数部分，[.]表示取 整。第i层的每个节点在第i+1层都具有两个子节点，i为1到A-1；第j层的每个节点在第j ＋1层都具有1个子节点，j为A到L。每个节点是一个二阶段布隆过滤器。每个二阶段布隆 过滤器包括两部分，第一部分是标准布隆过滤器，第二部分存储了各数据块的指纹和存储地 址。每个节点存储数据块的信息都是有限的，节点的存储容量可由用户设定为固定值或者不 一样的值。当某一节点不能再存储新的数据块信息时，表示该节点满载，否则，该节点未满 载。数据块的信息包括数据块的指纹、存储地址和引用次数等等。

如图1所示，是二阶段布隆过滤器的一个构造图。图中，数据块的指纹用X₁～X_n序列表 示。第一部分的标准布隆过滤器，包括一个包含有K个哈希函数h1₁～h1_K的集合和一个位数 组；位数组中包含w个元素，依次对应1～w的整数，对每个待查找的数据块指纹，分别通 过哈希函数h1₁～h1_K计算哈希值，得到K个整数值；当位数组中对应K个整数值的元素都 设置为1时，表示该指纹在标准布隆过滤器中命中，否则表示该指纹在该节点中不存在。第 二部分包括哈希函数h2、起始位置数组、结束位置数组和大数组。将指纹对应的K个整数值 通过哈希函数h2计算，得到一个整数index。整数index所表示的一类数据块指纹，在大数 组中存储的起始位置和结束位置，分别存储在起始位置数组和结束位置数组的第index元素 中。将经过哈希函数h1₁～h1_K的集合和哈希函数h2计算得到相同整数index的数据块指纹分 为同一类数据块指纹。大数组中的每一项记录一个数据块的指纹、存储地址、引用次数和存 储同类数据块指纹的下一项地址。

图1中，每个数据块的MD5值利用K个哈希函数h1₁～h1_K可以得到K个整数值。查看 位数组对应这K个整数的元素是否置为1，如果全为1，则说明极大概率该块已经存入系统。 否则，该块在该节点中不存在。若全为1，则去第二部分查看是否有完全一样的MD5值。

当某数据块的指纹在标准布隆过滤器中命中时，将该指纹对应的K个整数值输入第二部 分，通过哈希函数h₂计算得到整数index，在大数组中从起始位置数组第index元素记录的位 置开始查找，在查询完大数组的当前项后，按照当前项所存储的下一项地址，找到对应的项 继续查找，如果找到完全相同的指纹，表示该数据块为重复数据块，当前节点被命中，在大 数组存储该指纹的项中更新引用次数；若直到结束位置数组第index元素记录的位置查询结 束，都没有找到完全相同的指纹，则表示该指纹在该节点中不存在。

当某个数据块的指纹在所述的有限二叉树布隆过滤器的各个节点中都没有查找到，则该 数据块为新数据块，在未载满的节点中加入该新数据块，具体是，将该新数据块的指纹经过 节点中K个哈希函数h1₁～h1_K计算得到K个整数，在节点中的位数组对应该K个整数的元 素设置为1，在节点的大数组中新增一项，记录该新数据块的指纹、存储地址、引用次数和 存储同类数据块指纹的下一项地址，同时在起始位置数组和结束位置数组中更新该新数据块 指纹所属一类指纹在大数组中的起始位置和结束位置。

每个二阶段布隆过滤器中还包含存储块数St、存储容量Ca和块删除计数Co三个属性。 容量是由位数组长度w及第一部分误判概率p决定的。由于在块删除时，即在大数组中删除 某一项时，并没有对位数组进行修改，只是更新块删除计数Co。原本位数组有些位需要置0， 以保证布隆过滤器的误判率小于定制的常数。本发明采取的机制是，当删除块数量达到存储 容量的一定比重W时，利用大数组里的MD5数据重新计算，更新位数组中的元素值。数学 证明，在删除块数在一定比重下，对布隆过滤器的误判率影响小。比重W可根据实际使用情 况调整，一般根据误判概率p增加一个数量级来制定。

如图2所示，本发明基于所述的有限二叉树布隆过滤器的去冗文件系统，包括：文件系 统接口1、指纹生成器2、有限二叉树布隆过滤器3、块存储器4和索引文件5。本发明实施 例中的文件系统接口1可以采用FUSE（File system in Userspace，用户态文件系统）接口。 文件系统接口1接收外部应用程序发出的写入或读取文件的命令，将待写入文件传给指纹生 成器2，将读取的文件内容输出给外部应用程序。指纹生成器2将待写入文件定长划分成若 干数据块，并对每个数据块生成指纹，块的指纹可以采用冲突率低的算法来设定，本发明实 施例中，指纹是用MD5算法计算的MD5值。指纹生成器2将MD5值及对应的数据块传给 有限二叉树布隆过滤器3。有限二叉树布隆过滤器3对每个数据块，查询该数据块的MD5值 是否存在，如果不存在，为该数据块申请存储地址，并将申请的存储地址及数据块传给块存 储器4，最后，将该数据块的MD5值及存储地址传给索引文件5；如果存在，该数据块为重 复数据块，直接将该数据块的指纹及存储地址传送给索引文件5。块存储器4将数据块的内 容存入所申请的存储地址。索引文件5为每个文件建立一个索引，将该文件的所有数据块的 MD5值及存储地址按块顺序写入文件的索引中。文件系统接口1在接收到外部应用程序发来 的读取文件的命令时，根据文件路径在索引文件4中找到要读取的文件的索引，然后根据索 引中各数据块的地址，依次从块存储器4中读取各数据块的内容，输出给外部应用程序。

本发明实施例中，有限二叉树布隆过滤器中，第一层的两个节点，左节点标记为0，右 节点标记为1，同一父节点的左节点标记为0，右节点标记为1。设有限二叉树布隆过滤器每 层的节点数上限为2^A，则对第1层到第A层的任一节点来说，该节点的索引值为父节点的索 引值附带上该节点的标记值组成，第1层节点的索引值就是该节点的标记值，索引值是由0 和1组成的二进制串。对第A+1层开始的任一节点来说，该节点的索引值就是父节点的索引 值。

新数据块的信息存储在有限二叉树布隆过滤器中的节点，需要满足条件：设存储新数据 块信息的节点的索引值具有q位，新数据块的指纹的二进制串的前q位与该节点的索引值匹 配。数据块的信息包括数据块的指纹、数据块的存储地址、数据块的引用次数等。在未满载 的节点的索引值中，寻找与该数据块指纹的二进制串前若干位相匹配的索引值，如果找到， 将该数据块的信息存储到所找到的索引值对应的节点中。如果没有找到，则最底一层中，与 该数据块指纹的二进制串前若干位匹配的索引值对应的节点生成新的子节点，将该新数据块 信息存储到满足条件的新子节点中。

开始时，有限二叉树布隆过滤器生成第一层的两个节点，左边节点索引值以0，右边节 点的索引值为1。根据数据块的MD5值的二进制串，将数据块的信息不断写入节点中，将以 0为首位的MD5的二进制串对应的数据块信息存储在索引值为0的节点中，将以1为首位的 MD5的二进制串对应的数据块信息存储在索引值为1的节点中。当数据块数超过两个节点的 存储量时，第1层的两个节点分别生成两个子节点，具有同一父节点的两个子节点以0为左， 以1为右，例如节点0的两个子节点的索引值分别为00和01。以此类推，存储新的数据块 信息。

在有限二叉树布隆过滤器中查询数据块指纹时，首先根据数据块指纹的二进制串的前若 干位选取内存中已装载的索引值匹配的节点，在所选节点中依次查询该数据块的指纹。如， MD5的二进制串为011…，以0为左，以1为右，则分别选取有限二叉树布隆过滤器第1层 的左节点，第1层的左节点的右节点(即第2层的第2个节点)，依次类推。

本发明中需要把部分节点载入内存。当占用内存达到设定上限时，将部分满载的节点写 回主存，将剩下的部分满载节点的第二个部分(即存储MD5值和地址的部分)写回内存。未满 载的节点需要完整保留在内存里，等待新数据块的写入。一般地，根据MD5算法，未满载节 点都在同一层。最近命中冗余的节点层也需要载入内存，因为根据空间局部性原理，当一层 的某个节点命中冗余后，接下来在同一节点命中冗余的概率更大。那么，一般需要把两层完 整的节点信息载入内存。除此之外，其余层也应保留一个节点进行去冗检测。如果在某一节 点被命中后，与该节点同层的节点将会被调入内存。因为有限二叉树布隆过滤器一层一层往 下扩展节点，所以属于同个文件的数据块的MD5值最有可能存储在有限二叉树布隆过滤器的 同一层上。当一个数据块命中某个节点，之后的同一文件的数据块很有可能命中该节点同一 层中的节点。而且，只需要将二阶段布隆过滤器的第一部分载入到内存中，因为第二部分主 要用来定位数据块。因为内存的使用要在合理范围以内，所以需要设定一层的节点数上限Q， 并称之为有限二叉树布隆过滤器。

图3是每层节点数上限为8时有限二叉树布隆过滤器的结构示意图。阶段一、二和三分 别表示本发明的去冗文件系统工作的不同模式。阶段一，去冗文件系统的节点较少，所有节 点都放置在内存里，每次增加叶子节点的数量都是最底层节点数的两倍。阶段二，文件系统 节点多，非命中层(近期没有命中冗余块的非最底层)只留下一个代表节点在内存里，每次增 加叶子节点的数量都是最底层节点数的两倍。阶段三，节点数量非常多，非命中层只留下一 个代表节点，每次增加叶子节点的数量都是固定的常数。文件系统初次运行时处于阶段一， 即文件系统中的有限二叉布隆过滤器中只有两个刚刚建立的空节点，也就是0*BF和1*BF， 0*代表任意以0为首位的二进制串，BF代表有限二叉树布隆过滤器节点。0*BF只存储MD5 值首位为0的数据块的MD5值和存储地址。和0*BF类似，1*BF只存储MD5值首位为1的 块的MD5值和地址。根据MD5算法的特点，新数据块的MD5值在两个节点中均匀分布。 当其中一个节点装满时，会在该节点之下建立两个子节点。很明显，为了存储新块的MD5 值和地址值，需要将有限二叉树布隆过滤器最底层(未满载)的节点装入内存。但也要将图3 中的已满载的0*BF，00*BF和000*BF节点载入内存，因为需要利用它们来执行成员查询， 即查询数据块是否在这些节点中。如果一个数据块在第二层的00*BF中命中，则将第二层的 01*BF，10*BF和11*BF节点都载入内存来执行成员查询。根据空间局部性，之后的数据块 命中00*BF，01*BF，10*BF和11*BF的可能性要比命中其它节点高得多。

为了提高写通量，设计了流水线模式来分别处理数据块的计算和数据块的存储，整体的 写时间只等于这两部分所花时间的较大值。由于数据块MD5值的计算及有限二叉树布隆过滤 器的操作所需要的时间和块存储时间接近，该文件系统的写通量和普通文件系统的写通量接 近。如果在多磁盘硬件条件下引入多线程，每两个线程为一组，分别处理文件块的计算和IO 操作，那么写通量将成倍增长。

如图4所示，是数据块IO操作和计算的分离设计示意图。Key1,C1分别是第一个数据块 的MD5值和块内容，以此类推。对每一个新读入的数据块，如果计算时间小于IO操作时间， 那么去冗文件系统的IO速率将和正常文件系统相同。图中所示为最简单的一个单核CPU和 一块独立硬盘的情况。如果能在一个数据块的IO操作时间内完成一个块的相关计算，便可以 达到和正常文件系统相仿的IO速率。如果有更多的核和独立磁盘，可以建立更多的线程提高 IO速度。同时，也要尽可能的保证空间局部性。在设计中，每个数据块的计算时间包括计算 MD5值，将MD5值转换为二进制字符串，有限二叉树布隆过滤器及元数据文件操作。花费 时间最长的是用MD5算法计算MD5值。对有限二叉树布隆过滤器的操作很少涉及到磁盘读 写，所以一般会执行几个固定的步骤，在瞬间完成。有时，有限二叉树布隆过滤器需要向硬 盘写节点或从硬盘读取节点载入到内存之中，但是这些文件都很小。

在删除一个文件时，系统先根据索引文件里提供的MD5值找到所要删除文件的各数据块 的指纹在有限二叉树布隆过滤器里的对应位置，并查看其存储的引用次数，如果引用次数为 1，则无其他文件引用该块，可以将块内容删除，并把在有限二叉树布隆过滤器里的对应节点 大数组中的项删除。如果一个节点里删除操作达到一定数量，那么利用大数组里的MD5数据 重新计算节点中的位数组，更新标准布隆过滤器，减少误判。通过试验计算，发现由于一个 文件的数据块指纹分布在一层的节点中，删除文件的操作对一个节点的影响较小，因此删除 操作所要求的比重W很少达到，很少触发节点的更新计算。

如果将一台计算机作为有限二叉树布隆过滤器的一个节点，在每台计算机上又布置一个 有限二叉树布隆过滤器，那么就组成了一个集群去冗存储系统。当然，多台计算机的节点组 成一个有限二叉树布隆过滤器，该有限二叉树布隆过滤器与每台计算机上的有限二叉树布隆 过滤器应对MD5查询的节点策略不同，但在每个二阶段布隆过滤器中的查询都是相同的。该 集群去冗系统还可以进行MD5值的并行查询，文件内容的并行存取。

本发明基于所述的有限二叉树布隆过滤器，还提供了一种去冗文件系统的构建方法，主 要包括如下八个步骤。写入文件的步骤如图5所示，包括步骤1至步骤6。

步骤1：当外部应用程序发来写入文件命令时，对待写入的文件进行定长分块，并计算 每个数据块的指纹。

步骤2：将有限二叉树布隆过滤器中，未满载的节点保留在内存中，每层任选一个节点 保留在内存中，部分满载的节点只保留第一部分在内存中。所述的有限二叉树布隆过滤器， 第一层中左节点标记为0，右节点标记为1，同一父节点的左节点标记为0，右节点标记为1； 第1层节点的索引值就是该节点的标记值，第2层到第A层的任一节点的索引值为父节点的 索引值附带上该节点的标记值组成，第A+1层到第L层的任一节点的索引值就是父节点的索 引值，索引值为由0和1组成的二进制串。

步骤3：将每个数据块的指纹输入有限二叉树布隆过滤器中进行查找，首先从内存中保 留的节点中寻找索引值匹配的节点，并从所找到的各节点中查询数据块的指纹，如果查找到， 执行步骤4，如果未查找到，执行步骤5；所述的索引值匹配是指：设索引值q位，如果数据 块指纹的二进制串的前q位与索引值的q位相同，则说明数据块的指纹和节点的索引值匹配。

步骤4：该数据块为重复数据块，将与该数据块命中的节点处于同层的节点都取入内存 中，并保证有限二叉树布隆过滤器的每一层的任一节点和未满载的节点都保留在内存中，然 后取下一个数据块的指纹继续执行步骤3。

步骤5：该数据块为新数据块，为该数据块申请存储地址，块存储器将数据块的内容存入 所申请的存储地址，并在有限二叉树布隆过滤器存储该数据块的信息；保证有限二叉树布隆 过滤器未满载的节点都保留在内存中，然后取下一个数据块的指纹，继续执行步骤3。在未 满载的节点中，寻找与该数据块的指纹匹配的索引值的节点，如果找到，存储新数据块的信 息，如果没有找到，有限二叉树布隆过滤器最底一层与该数据块指纹匹配的索引值的节点生 成新的子节点，将该新数据块的信息存储到索引值匹配的节点中。

步骤6：当文件的所有数据块的指纹都经过有限二叉树布隆过滤器查找后，在索引文件中 该文件对应的索引中，依据数据块在文件中的顺序，写入索引文件各数据块的指纹和存储地 址。

步骤7：当外部应用程序发来读取文件命令时，根据文件路径在索引文件中找到要读取 文件的索引，根据索引中各数据块的存储地址，依次从块存储器中读取各数据块的内容并输 出给外部应用程序。

步骤8：当外部应用程序发来删除文件命令时，根据文件路径在索引文件中找到要删除 文件的索引，根据索引找到各数据块的指纹和存储地址。对每个数据块的指纹在有限二叉树 布隆过滤器中查找，在所找到的节点中查看该数据块的引用次数是否为1，若是，在根据该 数据块的存储地址在块存储器中删除该数据块的内容，若引用次数大于1，则将引用次数-1。 当要删除文件的各数据块都经过有限二叉树布隆过滤器的查找和处理后，在索引文件中删除 该文件的索引。

在步骤8进行删除数据块操作时，当某个数据块的信息在一个节点中被删除时，设置该 节点内块删除计数Co的值加1，当当块删除计数Co达到存储容量的比重W时，利用大数组 里的指纹重新计算，更新位数组。

数据块的指纹以MD5值来表示，并且设上一个数据块命中有限二叉树布隆过滤器的第H 层的节点，此时需要将H层的节点都取入内存中。在有限二叉树布隆过滤器中查询当前数据 块的指纹时，可采用下面步骤1.1～步骤1.6实现。

步骤1.1：设置计数器iter初值为H；如果当前数据块为所要查询的第一个数据块，此时 设置H为1。

步骤1.2：判断iter值是否大于有限二叉树布隆过滤器的高度L，若是，返回块地址Addr 的值-1，表示该数据块在当前有限二叉树布隆过滤器中不存在，然后退出；否则，执行步骤 1.3。

步骤1.3：在内存中有限二叉树布隆过滤器第iter层的节点中查找数据块的指纹，如果查 找到，返回块地址Addr，否则设置Addr的值为-1，返回Addr。

步骤1.4：判断Addr的值是否为-1，若是，执行步骤1.5，若否，执行步骤1.6。

步骤1.5：判断iter是否等于H，若是，则设置iter的值为1，若否，设置iter的值为H+1， 然后，转步骤1.2执行；

步骤1.6：判断H和iter的值是否相等，若不相等，则将有限二叉树布隆过滤器的第H 层的代表节点保留在内存，第H层的其余节点写回外存，然后将H的值设置为iter，将第H 层的节点取入内存中，返回块地址Addr。

在某一节点的二阶段布隆过滤器中查询MD5值，可依据下面步骤2.1～步骤2.7实现。

步骤2.1：首先将数据块的MD5值分别通过K个哈希函数h1₁～h1_K计算，得到K个整数 值。如图1所示，本发明实施例中，X₁X₂．．．．．．X_n为某一数据块的MD5值的二进制串，将每 个二进制位X_i（i＝1,2,…,n）分别经K个哈希函数运算，得到K个整数。

步骤2.2：查看节点的位数组中对应步骤2.1得到的K个整数值的元素是否都为1，若是， 则继续执行步骤2.3，若否，说明该数据块的指纹在该节点中未命中，返回块地址Addr的值 为-1，表示该数据块的指纹在该节点中不存在。

步骤2.3：将K个整数通过哈希函数h2进行计算，得到整数index。本发明实施例中本步 骤的实现方法是：设变量secondIndex的初始值为0，然后将K个整数依次和secondIndex按 位进行异或操作，每次操作的结果存入secondIndex，最后对secondIndex的值取模，得到整 数index。

步骤2.4：从起始位置数组中读取第index元素的值pos，若pos为-1，则表示该节点中没 有存储该类数据块指纹，返回块地址Addr的值为-1。起始位置数组中，在初始各元素的值都 设置为-1，表示该节点中还未存入数据块的信息。若pos不为-1，则根据pos，在大数组中找 到该类数据块指纹的起始地址。

步骤2.5：在大数组list中，查询list[pos]项中的MD5值，是否与数据块的MD5值相同， 若不相同，执行步骤2.6，若相同，将list[pos]项中的引用次数加1，将list[pos]项中的存储地 址赋给Addr，并返回。

步骤2.6：将list[pos]项中的下一项地址赋值给pos，然后判断pos是否为-1，若是，执行 步骤2.7；若否，转步骤2.5执行。

步骤2.7：整数index所代表的一类数据块指纹在该节点中查询完毕，返回块地址Addr 为-1，该数据块在该节点中未命中，停止查询。

当某个数据块为新数据块时，在有限二叉树布隆过滤器中需要写入该数据块的信息，具 体可依据步骤3.1～步骤3.4找到所要写入的节点。

步骤3.1：设置变量iter的值为L，L为当前有限二叉树布隆过滤器的高度。

步骤3.2：判断iter的值是否小于1，若是，转至步骤3.4执行，若否，执行步骤3.3。

步骤3.3：判断第iter层的与数据块的指纹匹配的索引值的节点是否满载，若否，在该节 点中存入新数据块的信息，结束本过程。若是，iter值减1，然后转步骤3.2执行。

步骤3.4：若有限二叉树布隆过滤器最底层的节点数不小于每层的节点数上限Q的一半， 则进入如图3所示的阶段三，在阶段三，最底层的每个节点都生成一个子节点，然后转步骤 3.1执行；否则进入如图3所示的阶段一或二，最底层的每个节点都生成两个子节点，然后转 步骤3.1执行。

在找到所要写入的节点后，具体可通过下面步骤4.1～步骤4.5在所找到的节点中写入新 数据块的信息。

步骤4.1：首先通过K个哈希函数h1₁～h1_K分别计算新数据块的指纹，得到K个整数， 具体计算过程与步骤2.1所给出的相同。然后将位数组中对应K个整数的元素的值置位1。

步骤4.2：将K个整数通过哈希函数h2进行计算，得到整数index。具体计算方法和步 骤2.3中的相同。

步骤4.3：在起始位置数组中读取第index元素的值pos，若pos为-1，表示该节点没有存 储该类数据块指纹，则将大数组中下一个空单元的位置G赋值给pos和结束位置数组中第 index元素，然后执行步骤4.4；否则，当pos不等于-1，表示该节点中存储有该类数据块指 纹，但未存储该新数据块的信息，直接读取结束位置数组中第index元素的值pla，然后执行 步骤4.5。

步骤4.4：在大数组list[pos]项中写入新数据块的指纹、数据块的存储地址、引用次数1 和下一项地址，下一项地址设置为-1。

步骤4.5：将大数组中下一个空单元的位置G赋值给大数组list[pla]项中的下一项地址， 然后在list[G]项中在大数组list[pos]项中写入新数据块的指纹、数据块的存储地址、引用次数 1和下一项地址-1。

设上一个数据块命中有限二叉树布隆过滤器的第H层的节点，此时将H层的节点都取入 内存中，将待删除的数据块的MD5值输入有限二叉树布隆过滤器，然后进行如下步骤：

步骤5.1：设置计数器iter的初值为1；

步骤5.2：若iter的值大于有限二叉树布隆过滤器的高度，返回；

步骤5.3：若MD5值的二进制串的前iter位代表的节点不在内存中，载入该节点至内存。 试着删除该节点中待删除数据块的MD5值所对应的值；

步骤5.4：若返回SUCCESS，当iter和H不相等时，将H层节点(代表节点除外)写回外 存，iter层的节点载入内存，iter的值赋给H，返回。否则，进行步骤5.5；

步骤5.5：iter值加1，跳至步骤5.2。

在一个二阶段布隆过滤器进行数据块信息删除的操作，包括如下步骤：

步骤6.1：当在标准布隆过滤器中查找数据块对应的K个整数对应的位结果有0时，返 回FAILURE，若对应的位结果都为1，则执行步骤6.2；

步骤6.2：变量secondIndex的值置为0；

步骤6.3：将K个整数依次和secondIndex按位进行异或操作，结果存入secondIndex；

步骤6.4：对secondIndex的值取模，存入index；

步骤6.5：从起始位置数组中读取第index元素的值pos；

步骤6.6：当pos等于-1时，返回FAILURE；

步骤6.7：若pos不为-1，判断大数组list中的项list[pos]中的哈希值和输入的MD5值是 否相等，如果相等，则将list[pos]项中的引用次数减1；如果不相等，跳至步骤6.10；

步骤6.8：当list[pos]中的引用次数为0时，将list[pos]中的地址赋给Addr，在块存储器 ChunkStore中删除Addr存储的数据。该二阶段布隆过滤器中的块删除计数TRC加1；

步骤6.9：若TRC的值达到存储容量的比重W时，利用大数组里的指纹重新计算更新位 数组，然后TRC清零；释放项list[pos]，返回SUCCESS；

步骤6.10：将list[pos]项中的下一项地址赋值给pos，然后跳至步骤6.6执行。

写入一个文件时，输入文件数据、文件路径和块大小L，将文件定长L分块，设块依次 为c1,c2…cj，然后执行如下步骤：

步骤7.1：设参数i初值为1；

步骤7.2：若i小于等于j时，进行步骤7.3；否则返回；

步骤7.3：生成各数据块的MD5值，设依次为Key1,Key2…Keyj，在有限二叉树布隆过 滤器LBTBF中查找Keyi对应地址，将返回值赋给变量Addr；

步骤7.4：若变量Addr的值为-1，将Addr置为一个未使用的地址，将(Keyi,Addr)值对写 入LBTBF，将块ci的内容写入对应地址Addr，并将(Keyi,Addri)写入文件对应的索引文件；

步骤7.5：若变量Addr的值不为-1，将(Keyi,Addri)写入文件对应的索引文件，i值加1， 跳至步骤7.2。

在读取一个文件时，通过文件系统接口1接收到文件路径，然后执行如下步骤，输出文 件数据：

步骤8.1：根据文件路径找到对应的索引文件，将对应的索引文件载入内存；

步骤8.2：依次读取索引文件中各数据块的地址，设其分别为Addr1,Addr2,…Addrj；j为 数据块总数；

步骤8.3：设参数i初值为1；

步骤8.4：若i小于等于j时，进行步骤8.5；否则返回；

步骤8.5：读取Addri地址存储的数据块内容，然后，i=i+1，跳至步骤8.4继续执行。

在删除一个文件时，通过文件系统接口1接收到文件路径，然后执行如下步骤：

步骤9.1：根据文件路径找到对应的索引文件，将对应的索引文件装入内存；

步骤9.2：依次读取索引文件中各数据块的MD5值：Key1,Key2,…Keyj；j为数据块总数；

步骤9.3：设计数参数i初值为1；

步骤9.4：若i小于等于j时，进行步骤9.5，否则返回；

步骤9.5：在有限二叉树布隆过滤器里删除Keyi，然后，i=i+1，跳至步骤9.4继续执行。