(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210790603.0 (22)申请日 2022.07.05 (71)申请人 南京大学 地址 210093 江苏省南京市 鼓楼区汉口路 22号 (72)发明人 吴侗雨　李猛　柴华溢　戴海鹏　 顾荣　陈贵海　 (74)专利代理 机构 苏州威世朋知识产权代理事 务所(普通 合伙) 32235 专利代理师 沈晓敏 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2453(2019.01) G06F 16/2455(2019.01) (54)发明名称 一种用于加速云平台数据库LSM树查询的高 效过滤方法 (57)摘要 本发明公开了一种用于加速云平台数据库 LSM树查询的高效过滤方法， 包括如下步骤： 将已 写入的数据按自身特点划分至互相独立的数据 集子块内， 为每一个数据集子块单独构建缓存行 大小的分块布隆过滤器； 结合在本数据块内缺 失， 但是历史查询频繁的数据， 自适应调整已写 入的数据的哈希函数集并存入分块哈希表达器； 将分块布隆过滤器以及分块哈希映射表共同构 成分块哈希自适应过滤器， 并部署到系统中。 在 进行数据是否写入的判断时， 采用单指令多数据 流技术同时检测一个块内多个比特位。 本发明将 过滤器按缓存 行大小进行分块， 并行检测分块内 的比特数据， 极大提升了查询效率， 并结合哈希 自适应技术， 有效避免了分块带来的准确性降低 问题。 权利要求书1页 说明书5页 附图3页 CN 115292308 A 2022.11.04 CN 115292308 A 1.一种用于加速云平台数据库LSM树 查询的高效过 滤方法， 包括以下步骤： (1)分块哈希自适应过滤器初始化阶段： 首先， 将所有 的数据按照是否已写入LSM树划 分为已写入的数据和未写入的数据， 其中， 未写入的数据是指在本数据块内缺 失， 但是历史 查询频繁的数据， 所述未写入的数据通过收集日志获得， 其次， 将已写入的数据按自身特点 划分至互相独立的数据集子块内， 最后， 为每一个数据集子块单独构建 分块布隆过 滤器； (2)分块哈希自适应过滤器自适应阶段： 首先， 将未写入的数据划分至分块布隆过滤 器， 将未写入的数据划分为被误判的未写入的数据和未被误判的未写入的数据； 其次， 根据 已写入的数据和未被误判的未写入的数据， 分别建立两个分块哈希映射表； 再次， 调整已写 入的数据的哈希函数集， 以减少被误判的未写入的数据的数量； 最后， 将 每个已写入的数据 根据调整后的哈希函数集重新插入分块布隆过滤器中， 并同时存储调整后的哈希函数集到 分块哈希 表达器中； (3)分块哈希自适应过滤器部署应用阶段： 分块布隆过滤器以及两个分块哈希映射表 共同构成分块哈希自适应过滤器， 并部署到系统中。 在 进行查询时， 采用单指 令多数据流技 术提高分块布隆过 滤器内比特位的比较速度。 2.根据权利要求1所述的一种用于加速云平台数据库LSM树查询的高效过滤方法， 其特 征在于， 所述步骤(1)中， 将已写入的数据按照自身特征划分不同分块， 并分别插入对应的 缓存行大小的分块布隆过滤器中， 随后 将所述缓存行大小的布隆过滤器合并形成分块布隆 过滤器。 3.根据权利要求1所述的一种用于加速云平台数据库LSM树查询的高效过滤方法， 其特 征在于， 所述步骤(1)中， 分块布隆过滤器的初始 化构建过程包含如下步骤： 首先， 申请长度 为m位的比特数组， 并将所述比特数组划分为等长的n份， 每份称为一个块； 其次， 对于每个 插入的已写入的数据， 使用哈希函数f将所述已写入的数据映射到比特数组的一个块中； 最 后， 对于已经映射到块中的已写入的数据， 通过使用k个哈希函数得到块中的k个位， 将所述 k个位设置为1。 4.根据权利要求1所述的一种用于加速云平台数据库LSM树查询的高效过滤方法， 其特 征在于， 所述步骤(2)中， 分块哈希表达器包含多个块结构， 所述块结构包含多个元 组， 所述 块结构的位置与分块布隆过滤器中的块一一对应， 所述元组的位置与缓存 行大小的布隆过 滤器中比特的位置一一对应； 分块哈希表达器的每个分块中存储了对应分块布隆过滤器中 已写入的数据的哈希函数集。 5.根据权利要求1所述的一种用于加速云平台数据库LSM树查询的高效过滤方法， 其特 征在于， 所述步骤(3)中， 在 对分块布隆过滤器进 行操作时， 使用单指 令多数据流， 在一条指 令的执行周期内同时进 行多次数据运算， 从而提升程序的执行效率； 预先定义好一组模式， 模式指一个块内的随机k个比特的位置； 当准备插入或查询分块布隆过滤器时， 仅使用一个 哈希函数选择一个模式， 随后利用单指令多数据流向块内插 入或检测所述模式。权　利　要　求　书 1/1 页 2 CN 115292308 A 2一种用于加速 云平台数据库LSM树查询的高 效过滤方法 技术领域 [0001]本发明涉及云平台数据库领域， 具体涉及一种用于加速云平台数据库LSM树查询 的高效过 滤方法。 背景技术 [0002]日志结构合并(Log  Structured  Merge,LSM)树是一种被广泛应用于数据库存储 引擎的数据结构 。 其基本思想是将数据分层 存储， 最高层使用内存存储数据， 其余层 级均使 用磁盘。 写操作只面向内存进 行数据写入， 当层级中存储的数据容量达到阈值时， 将该层级 数据按照排序顺序合并写入下一层级。 查询操作从最高层级内存开始， 向下查询每一个层 级直到找到该数据。 使用LSM树， 可以带来极高的写入速度， 但读取速度较慢， 极端情况下， 若待查询的数据未被写入， 则读取操作需要对所有数据进行扫描。 [0003]由于LSM树的查询失败带来的I/O代价非常高， 因此严重影响了数据库的查询性 能。 一种常见的优化方式为使用布隆过滤器记录那些被写入的数据， 当进 行查询操作前， 先 通过布隆过滤器判断待查询的数据是否被写入， 再决定是否进 行查询。 然而， 布隆过滤器存 在误报情况， 即未被写入的数据被判断为已写入， 这 导致性能下降。 发明内容 [0004]发明目的： 为了解决LSM树查询性能不高的问题， 本 发明提出一种用于加速云平台 数据库LSM树查询的高效过滤方法， 核心是充分利用缓存， 首先提出一种新型的布隆过滤 器： 分块哈希自适应过滤器， 核心是将布隆过滤器分块； 其次提出基于 分块哈希自适应过滤 器的数据写入判断系统的构建。 技术方案： 本发明提供一种用于加速 云平台数据库LS M树查 询的高效过 滤方法， 包括以下步骤： [0005](1)分块哈希自适应过滤器初始化阶段。 具体步骤包括： 首先， 将所有的数据按照 是否已写入LSM树划分， 即已写入的数据和未写入的数据， 其次， 将已写入的数据按自身特 点划分至互相独立的数据集子块内， 最后， 为每一个数据集子块单独构建 分块布隆过 滤器。 [0006](2)分块哈希自适应过滤器自适应阶段。 具体步骤包括： 首先， 将未写入的数据划 分至分块布隆过滤器， 根据是否被误判， 将未写入的数据划分为两个集合， 即被误判的未写 入的数据和未被误判的未写入的数据。 其次， 根据已写入的数据和未被误判的未写入的数 据， 分别建立两个分块哈希映射表。 再次， 调整已写入的数据的哈希函数集， 以期减少被误 判的未写入的数据的数量。 最后， 将每个已写入的数据根据其调整后的哈希函数集重新插 入分块布隆过 滤器中， 并同时存 储哈希函数集到分块哈希 表达器中。 [0007](3)分块哈希自适应过滤器部署应用阶段。 分块布隆过滤器以及两个分块哈希映 射表共同构成分块哈希自适应过滤器， 并部署 到系统中。 在进 行查询时， 采用单指令多数据 流技术提高分块布隆过 滤器内比特位的比较速度。 [0008]为优化上述 技术方案， 采取的具体措施还 包括： [0009]进一步地， 步骤(1)中， 阶段1中， 未写入的数据是指在本数据块内缺失， 但是历史说　明　书 1/5 页 3 CN 115292308 A 3