科创中国

本发明公开了一种动态布隆过滤器，以根据实际应用场景设计布隆过滤器，减小内存空间的消耗和计算元素哈希映射的代价。所述动态布隆过滤器包含sm个同构子布隆过滤器BF，以se为锚点，sm个同构子BF被分为组子链表，组子链表中每组子链表被指派一个索引线程以对组子链表进行并行操作，se为每个子链表的期望长度；根据键‑值存储系统的性能需求，动态布隆过滤器的相关参数被初始化为定值。一方面，键‑值存储系统可以支持不同集合的并行多线程索引查询，提升了索引整体吞吐率；另一方面，支持并行查询优化和BF之间的位向量操作，有利于资源管理；第三方面，能够估算性能和索引空间的最佳平衡点。

一种动态布隆过滤器，其特征在于，所述动态布隆过滤器包含sm个同构子布隆过滤器BF，以se为锚点，所述sm个同构子布隆过滤器BF被分为组子链表，所述组子链表中每组子链表被指派一个索引线程以对所述组子链表进行并行操作，所述se为每个子链表的期望长度；根据键-值存储系统的性能需求，所述动态布隆过滤器的相关参数被初始化为定值，所述相关参数包括元素查询的最坏时间代价Qw、动态布隆过滤器的假阳性错误概率的上限期望值Fmax、每个所述同构子布隆过滤器BF的假阳性错误概率的期望值fppe、每个所述同构子布隆过滤器BF最多索引元素个数n、每个所述同构子布隆过滤器BF的内存消耗空间大小m、所述sm个同构子布隆过滤器BF总的内存消耗空间大小M和所述每个子链表的期望长度se。

对于当今大规模、高性能的数据密集型应用，基于键-值(Key-Value，Κ-ν)的存储 系统是影响应用性能的至关重要的构件。因此，无论在商业领域还是学术范畴，例如，重复 数据删除系统、电子商务平台、数据库字典和网络对象缓存技术等，高性能的K-V存储系统 设计都得到了广泛的关注。为了实现低延迟和高吞吐率的性能需求，并充分利用有限的I/O资源，K-V存储系 统需要高效、紧凑的内存索引方案来快速确定请求的数据是不是特定集合的成员。一方面， 基于内存K-V存储系统，例如，memcached、RAMCloud、Redis等，将索引全部存入内存从而避 免磁盘查找导致的性能瓶颈，目前高性能的K-V存储需要每秒能支持数万甚至是数十万的 查询请求，然而，内存容量随着存储规模地递增而成倍地增长将导致购买价格和功耗呈指 数型增长，因此，索引的空间开销成为影响K-V存储系统可伸缩性和整体成本效益的最重要 的要素之一；另一方面，基于磁盘的索引查询效率太低，一般而言，磁盘的查询代价在毫秒 级别，因此，每秒吞吐率在千次以下，特别是，当某个请求索引未匹配时将导致磁盘的一次 空查找，从而极大地影响了整个K-V系统的吞吐率。

中国科学院深圳先进技术研究院提升了粤港地区及我国先进制造业和现代服务业的自主创新能力，推动我国自主知识产权新工业的建立，成为国际一流的工业研究院。 深圳先进院目前已初步构建了以科研为主的集科研、教育、产业、资本为一体的微型协同创新生态系统，由九个研究平台，国科大深圳先进技术学院，多个特色产业育成基地、多支产业发展基金、多个具有独立法人资质的新型专业科研机构等组成。开展先进技术研究，促进科技发展。信息、电子、通讯技术研究新材料、新能源技术研究高性能计算、自动化、精密机械研究生物医学与医疗仪器研究相关学历教育、博士后培养与学术交流。

一方面，由组子链表中每组子链表被指派一 个索引线程以对所述组子链表进行并行操作，因此，键-值存储系统可以支持不同 集合的并行多线程索引查询，提升了索引整体吞吐率;另一方面，由于动态布隆过滤器包含 的是同构子BF，因此，每个元素通过哈希函数的映射位置一致，支持并行查询优化和BF之间 的位向量操作，有利于资源管理;第三方面，动态布隆过滤器的相关参数初始化是根据键-值存储系统的性能需求而定，因此，能够估算性能和索引空间的最佳平衡点。

技术合作

以上对本发明实施例所提供的动态布隆过滤器和基于动态布隆过滤器的元素操 作方法进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述， 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一 般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所 述，本说明书内容不应理解为对本发明的限制。