一种基于目录级可伸缩的Bloom Filter位图表的并行文件搜索方法

摘要

本发明针对当前大规模文件系统搜索存在准确率低下、额外开销大等问题，采用轻量级的存储技术，公开了一种基于目录级可伸缩的Bloom Filter位图表的并行文件搜索方法。通过基于目录级可伸缩的Bloom Filter位图表的搜索算法，快速缩小了目录结构的搜索范围，位图表只占用少量的系统资源，可以快速得缩小目录结构的搜索范围，提高了系统搜索性能。基于目录级可伸缩的Bloom Filter位图表的搜索算法，树形目录结构转化扁平化结构，为并行化搜索提供了基础，通过基于Map-Reduce框架达到并行化搜索，大大加快了搜索速率。根据应用需求，该方法克服了搜索准确率低、额外负载开销大技术难题，同时兼顾了高准确率和低开销的优点。因此，本发明具有高准确率和低额外负载开销，广阔的应用前景和可产生显著的经济效益等特色。

主权项

一种基于目录级可伸缩的Bloom Filter位图表的并行文件搜索方法，其特征在于：（1）在单台元数据服务器中，基于目录级可伸缩的Bloom Filter位图表的文件搜索方法缩小搜索范围首先，基于Bloom Filter位图表快速搜索技术，建立基于目录级可伸缩的Bloom Filter位图表的文件搜索方法，通过对树形目录结构中的目录节点的每一维属性建立可伸缩的Bloom Filter位图表，利用位图表中的0和1比特位来管理下层目录是否存在所要搜索的文件，达到通过占用少量的存储空间，提供快速而准确的文件搜索方法，将文件树形目录结构转变成扁平化结构，文件的属性值不再隐藏在底层；然后，将每一维文件属性的基于目录级可伸缩的Bloom Filter位图表通过基于链表的技术组织起来，形成一个链表形式的目录级可伸缩的Bloom Filter位图表；最后，针对多维属性中的每一维属性都组织成上述描述的链表形式，将整个树形的目录空间转变成扁平化结构，通过基于目录级可伸缩的Bloom Filter位图表可以快速准确的在目录结构中缩小搜索范围。（2）在多元数据服务器中，进行并行化快速搜索在多元数据服务器环境中，由于树形目录空间转化为扁平化结构，首先，基于采用类似于Map‑Reduce框架，建立多元数据服务器并行化搜索算法，达到多元数据服务器文件系统快速搜索，极大的提高了搜索速率；然后，针对Top‑K搜索，将用户的搜索请求广播到所有的元数据服务器上，多个元数据服务器同时进行搜索，用户搜素请求的数据量较小时，通过两次Map和Reduce的操作迭代过程可以到搜索结果，第一次Map和Reduce阶段返回目录结构中各分支满足搜索条件的位图表的部分给客户端，第二次Map和Reduce阶段通过输入第一次结果，返回满足搜索条件的具体的属性给客户端，当用户搜索请求的数据量大时，通过三次Map和Reduce的迭代操作过 程可以得到搜索过程，在第二次Map和Reduce阶段由于数据量大，为了减少系统开销先返回属性值到客户端，在客户端处理后，作为第三次Map和Reduce的输入，第三次Map和Reduce后，返回属性到客户端；最后，针对Range搜索，通过一次Map和Reduce的操作过程可以得到用户的请求结果，在Map阶段获得了目录结构各分支的满足搜索条件属性值的范围，在Reduce阶段在客户端得到满足搜索条件的属性范围。