(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210312977.1 (22)申请日 2022.03.28 (71)申请人 浙江邦盛科技股份有限公司 地址 310012 浙江省杭州市西湖区西斗门 路3号天堂软件园D幢17层ABCD座 (72)发明人 陈伟　王刚　鲁萍　黄滔　杨运平　 叶金韬　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 刘静 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/23(2019.01) (54)发明名称 一种面向内存键值表的子集过滤器 (57)摘要 本发明公开了一种面向内存键值表的子集 过滤器， 主要分为五个部分： 子集过滤器的定义、 子集过滤器的数据项存储、 子集过滤器的数据项 更新、 子集过滤器的重建和子集过滤器的扫描。 本发明支持任意类型指标数据的过滤， 支持指定 任意数据特征的过滤， 从而提供灵活的扫描方 式， 并且扫描时不需要遍历全部的指标数据， 有 效加速扫描操作。 本发明可应用于大部分的内存 键值表， 具有一定的通用性。 权利要求书1页 说明书5页 附图2页 CN 114676136 A 2022.06.28 CN 114676136 A 1.一种面向内存键值表的子集过滤器， 其特征在于， 所述子集过滤器设置有用于抽取 键值对特征 的过滤器函数以及匹配值， 当抽取 的键值对特征与匹配值一致时， 子集过滤器 记录键值对的内存地址； 所述子集过滤器包括子集过滤器构建模块、 数据项存储模块、 数据 项更新模块和扫描模块； 所述子集过滤器构建模块用于根据内存键值表构建一个子集过滤器， 子集过滤器构建 模块标记内存键值表 为不可写状态， 并通过过滤器函数抽取内存键值表中所有键值对数据 的键值对特 征， 与匹配值 一致时， 将键值对内存地址保存到 子集过滤器中； 所述数据项存 储模块用于将子集过 滤器记录的键值对的内存地址存 储在链表中； 所述数据项更新模块用于在内存键值表对某个键值对执行完更新操作时， 通过过滤器 函数抽取更新后的键值对特征， 当更新后的键值对特征与匹配值一致时， 记录更新后的键 值对的内存地址； 并遍历数据项存储模块中的链表， 若链表中存在旧键值对内存地址， 则将 其修改为更新后键值对的内存地址， 否则创建新的链 表项， 保存更新后键值对的内存地址； 所述扫描模块用于加速对具有特定特征键值对的扫描， 根据扫描线程的数量， 将数据 项存储模块中的分段平均分配给每个扫描线程； 每扫描到一个对应特定特征键值对的内存 地址， 根据内存地址获取内存键值表的键值对数据。 2.根据权利要求1所述的一种面向内存键值表的子集过滤器， 其特征在于， 所述数据项 存储模块具有2s个分段， 每个分段拥有2b条链表， 链表上存储了满足特征的键值对内存地 址。 3.根据权利要求2所述的一种面向内存键值表的子集过滤器， 其特征在于， 遍历数据项 存储模块中的链表时， 计算键值对的键散列值， 根据散列值， 取最后s位确定 分段， 然后取之 前的b位确定链 表。 4.根据权利要求2所述的一种面向内存键值表的子集过滤器， 其特征在于， 所述扫描模 块的每个扫描线程逐分段 逐链表扫描子 键值对内存地址 。权　利　要　求　书 1/1 页 2 CN 114676136 A 2一种面向内存键值表的子集 过滤器 技术领域 [0001]本发明涉及风控、 反欺诈等需要进行高频实时信息处理和存储的金融领域， 涉及 一种面向内存键值表的子集过 滤器。 背景技术 [0002]在风控、 反欺诈等需要实时计算的金融领域， 不仅仅需要计算如 “某实体过去1天 的交易量 ”、“某实体过去1星期最大 交易额”等金融指标， 而且还需要进 行如“寻找话费充值 后30分钟内进 行3C交易， 再10 分钟内进 行贵重物品交易的实体 ”、“寻找相邻2笔 交易金额总 额超过100万元的交易 实体”等复杂事件的计算和处理， 这些计算需要对交易 实体的指标数 据进行扫描， 指标数据保存在内存键值表中， 因此加速内存键值表的扫描对于该类计算非 常重要。 [0003]由于扫描内存键值表的全部数据时间开销巨大， 目前面向内存键值表的扫描加速 方法主要为构建索引， 通过索引加速扫描操作， 索引主 要为下列2类： [0004](1)基于字 典树的前缀索引。 Redis采用了该索引方法， 对键进行索引， 从而实现了 前缀扫描。 [0005](2)基于B+树的索引。 Aerospike采用了该索引方法， 对特定类型的值(如字符、 整 数)进行索引， 以实现该类数据的范围扫描。 [0006]在金融风控、 反欺诈的复杂时间处理和计算场景下， 扫描的事件和指标数据越来 越复杂， 扫描的方式越来越灵活多样， 而 上述的索引方法难以满足这些扫描需求， 存在下列 2点缺陷： [0007](1)索引支持的数据类型有限： 数据格式受限于字符串、 整数等普通数据类型， 无 法满足复杂事 件和计算指标的索引需求。 [0008](2)基于索引 支持的扫描方式有限： 基于字典树的前缀索引只支持字符串的前缀 扫描， 而基于B+树的索引只支持特定有序数据的范围扫描， 满足特定条件的复杂事件和 计 算指标的扫描， 其效率十分低下。 [0009]综上所述， 上述已有索引加速扫描的方法无法完全满足风控、 反欺诈等金融实时 计算和复杂事 件处理的扫描需求。 发明内容 [0010]针对上述已有索引加速扫描的方法所产生的问题和缺陷， 本发明提出了一种面向 内存键值表的子集过滤器， 加速了风控、 反欺诈等金融实时计算和复杂事件场景下对于内 存键值表指标 数据的扫描操作。 [0011]本发明的目的是通过以下技术方案来实现的： 一种面向内存键值表的子集过滤 器， 所述子集过滤器设置有用于抽取键值对特征 的过滤器函数以及匹配值， 当抽取 的键值 对特征与匹配值一致时， 子集过滤器记录键值对的内存地址； 所述子集过滤器包括子集过 滤器构建模块、 数据项存 储模块、 数据项更新模块和扫描模块；说　明　书 1/5 页 3 CN 114676136 A 3