(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210958407.X (22)申请日 2022.08.09 (71)申请人 福建天晴数码有限公司 地址 350000 福建省福州市君竹路83号科 技发展中心大楼第四层Q476室 （自贸 试验区内） (72)发明人 刘德建　叶伟　李佳　 (74)专利代理 机构 福州旭辰知识产权代理事务 所(普通合伙) 35233 专利代理师 程勇 (51)Int.Cl. G06F 16/2455(2019.01) G06F 16/22(2019.01) G06F 16/215(2019.01) (54)发明名称 一种解决布隆过滤器误判缓存数据的方法 及系统 (57)摘要 本发明提供了一种解决 布隆过滤器误判缓存 数据的方法及系统， 该方法为： 1、 设置位图bitmap 初始长度,通过布隆过滤器算法bloomfilter计 算数据标识得到3次hash结果， 在bitmap对应的 下标位都设为1。 2、 收到数据查询请求后， 根据布 隆过滤器算法把数据标识的3次hash结果在 bitmap中查询是否都为1， 如果存在0则返回数据 不存在。 3、 用数据标识作为缓存key从缓存中查 询数据， 如果得到数据则直接返回数据， 如果得 到数据空标识"nil"， 则返回数据不存在， 如果缓 存中得不到任何数据则进行下一步。 4、 从数据库 中查询数据， 如果数据不存在， 则存储数据空标 识"nil"到缓存中， 如果数据存在则存储数据到 缓存中， 并且设置bitmap对应 下标为1。 本发明能 够解决布隆过滤器在数据缓存使用场景中存在 误判的情况。 权利要求书3页 说明书7页 附图2页 CN 115269657 A 2022.11.01 CN 115269657 A 1.一种解决布隆过 滤器误判缓存数据的方法， 其特 征在于： 所述方法包括如下步骤： 步骤S1、 设置位图bitmap初始长度， 通过布隆过滤器算法bloomfilter对数据库每条数 据的数据标识计算得到每条数据对应的3次hash结果， 所述3次hash结果即为3个数字下标， 根据3个数字下 标将位图bitmap对应的存 储bit位置都置为1； 步骤S2、 收到数据查询请求后， 通过布隆过滤器算法bloomfilter对要查询数据的数据 标识计算得到3个下标位数值， 根据3个下标位数值在位图bitmap中查询对应的bit位置是 否都为1， 如果存在0则返回数据不存在； 如果否为1， 则进入步骤S3； 步骤S3、 用要查询的数据的数据 标识作为缓存key从缓存中查询数据， 如果得到数据则 直接返回数据， 如果得到数据空标识"nil"， 则返回数据不存在， 如果缓存中得不到任何数 据则进入步骤S4； 步骤S4、 从数据库中查询数据， 如果数据不存在， 则 存储数据空标识"nil"到缓存中， 如 果数据存在则存储数据到缓存中， 并且根据所述3个下标位数值设置位图bitmap对应的存 储bit位置都置为1， 从而解决布隆过 滤器误判。 2.根据权利要求1所述的一种解决布隆过滤器误判缓存数据的方法， 其特征在于： 所述 方法还包括维护位图bitmap的扩容和重建操作， 所述扩容和重建操作为： 定时检测位图 bitmap的使用量是否超过75％， 超过则把位图bitmap进行翻倍扩容， 并且根据当前数据库 数据重建位图bitmap， 在新位图bitmap重建的过程中， 设置数据库为只读状态， 不允许删除 数据， 新位图bitmap重建完成后替换旧位图bitmap， 并且移除数据库的只读状态。 3.根据权利要求1所述的一种解决布隆过滤器误判缓存数据的方法， 其特征在于： 所述 步骤S1进一步具体为： 设置数据库中数据总量为N条数据， 则设置位图bitmap初始长度为 5N， 遍历数据库中所有数据， 把每条数据的数据标识通过布隆过滤器bloomfilter 算法进行 3次不同的hash调用， 得到长度为5N内的3个数字下标， 在位图bitmap对应的3个数字下标的 存储bit位置都设为1， 也就是3个存储bit位置都为1则代表该数据存在； 利用该方式把N条 数据的数据标识的对应位图bitmap下 标的存储bit位置都设为1。 4.根据权利要求1所述的一种解决布隆过滤器误判缓存数据的方法， 其特征在于： 所述 步骤S4进一步具体为： 通过布隆过滤器和缓存的判断是否存在后， 如果 都不存在， 则表 示此 数据从未进 行过数据库查询， 则从数据库查询数据标识的数据， 如果数据库不存在此数据， 存储数据空标识"nil"到缓存中， 以此告诉缓存数据不存在， 后续无需再进行查询； 如果在 未来数据 表示为数据标识的数据被新增至数据库中， 则删除缓存中的空标识" nil"， 重新执 行向数据库进 行该数据的查询； 如果数据库查询到该数据， 则把数据存入缓存之中， 以供下 次查询能直接从缓存得到数据； 并且根据所述3个下标位数值设置位图bitmap对应的存储 bit位置都置为1。 5.根据权利要求2所述的一种解决布隆过滤器误判缓存数据的方法， 其特征在于： 所述 步骤位图bitmap的扩容进一步具体为： 定时检测位图bitmap中值为1的个数是否超过 bitmap总长度的75％， 如果超 过则表示随着数据量的增长， bitmap的碰撞 概率会增加， 需要 对bitmap 进行扩容重建， 新建一个位图bitmap， 容量为原先长度翻倍， 由于长度的变化导致 hash结果会不同， 所以需要对bitmap数据进行重 建， 即重新遍历数据库中所有数据， 把每条 数据的数据标识通过布隆过滤器bloomfilter算法进行3 次不同的hash调用， 得到3个数字 下标， 在位图bitmap对应的3个数字下 标的存储bit位置都设为1。权　利　要　求　书 1/3 页 2 CN 115269657 A 26.一种解决布隆过滤器误判缓存数据的系统， 其特征在于： 所述系统包括： 位图设置模 块、 布隆过 滤器判断数据模块、 缓存查询数据模块、 以及反馈信息模块； 所述位图设置模块， 设置位图bitmap初始长度， 通过布隆过滤器算法bloomfilter对数 据库每条数据的数据标识计算得到每条数据对应的3次hash结果， 所述3次hash结果即为3 个数字下 标， 根据3个数字下 标将位图bitmap对应的存 储bit位置都置为1； 所述布隆过滤器判断数据模块， 收到数据查询请求后， 通过布隆过滤器算法 bloomfilter对要查询数据的数据标识计算得到3个下标位数值， 根据3个下标位数值在位 图bitmap中查询对应的bit位置是否都为1， 如果存在0则返回数据不存在； 如果否为1， 则进 入步骤S3； 所述缓存查询数据模块， 用要查询的数据的数据标识作为缓存key从缓存中查询数据， 如果得到数据则直接返回数据， 如果得到数据空标识"nil"， 则返回数据不存在， 如果缓存 中得不到任何数据则进入步骤S4； 所述反馈信息模块， 从数据库中查询数据， 如果数据不存在， 则存储数据空标识"nil" 到缓存中， 如果数据存在则存储数据到缓存中， 并且根据所述3个下标位数值设置位图 bitmap对应的存 储bit位置都置为1， 从而解决布隆过 滤器误判。 7.根据权利要求6所述的一种解决布隆过滤器误判缓存数据的系统， 其特征在于： 所述 系统还包括维护位图bitmap的扩容和重建操作， 所述扩容和重建操作为： 定时检测位图 bitmap的使用量是否超过75％， 超过则把位图bitmap进行翻倍扩容， 并且根据当前数据库 数据重建位图bitmap， 在新位图bitmap重建的过程中， 设置数据库为只读状态， 不允许删除 数据， 新位图bitmap重建完成后替换旧位图bitmap， 并且移除数据库的只读状态。 8.根据权利要求6所述的一种解决布隆过滤器误判缓存数据的系统， 其特征在于： 所述 位图设置模块的实现方式进一步具体为： 设置数据库中数据总量为N条数据， 则设置位图 bitmap初始长度为5N， 遍历数据库中所有数据， 把每条数据的数据标识通过布隆过滤器 bloomfilter算法进行3次不同的hash调用， 得到长度为5N内的3个数字下标， 在位图bitmap 对应的3个数字下标的存储bit 位置都设为1， 也就是3个存储bit 位置都为1则代表该数据存 在； 利用该 方式把N条数据的数据标识的对应位图bitmap下 标的存储bit位置都设为1。 9.根据权利要求6所述的一种解决布隆过滤器误判缓存数据的系统， 其特征在于： 所述 反馈信息模块的实现方式进一步具体为： 通过布隆过滤器和缓存的判断是否存在后， 如果 都不存在， 则表示此数据从未进 行过数据库查询， 则从数据库查询数据标识的数据， 如果数 据库不存在此数据， 存储数据空标识"nil"到缓存中， 以此告诉缓存数据不存在， 后续无需 再进行查询； 如果在未来数据表示为数据标识的数据被新增至数据库中， 则删除缓存中的 空标识"nil"， 重新执行向数据库进行该数据的查询； 如果数据库查询到该数据， 则把数据 存入缓存之中， 以供下次查询能直接从缓存得到数据； 并且根据所述3个下标位数值设置位 图bitmap对应的存 储bit位置都置为1。 10.根据权利要求7所述的一种解决布隆过滤器误判缓存数据的系统， 其特征在于： 所 述步骤位图bitmap的扩容进一步具体为： 定时检测