利索能及
我要发布
收藏
专利号: 2023108330687
申请人: 华侨大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-11-04
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于键值分离的键值存储系统中范围查询优化方法,其特征在于,包括以下步骤:将键存储在LSM‑Tree中,获取在SSTable文件中点查询或范围查询的查询结果,根据所述查询结果动态调整阈值allowed_seeks,具体包括:响应于确定所述查询结果为命中,则将所述阈值allowed_seeks增加一;

响应于确定所述查询结果为未命中,则将所述阈值allowed_seeks减少一;所述阈值allowed_seeks为点查询和范围查询的查询结果中SSTable文件的最大容忍未命中次数,范围查询时的未命中表示对该SSTable文件查询时的无效迭代次数超过范围查询的一半范围,根据所述阈值allowed_seeks确定是否触发Seek Compaction,具体包括:响应于确定所述阈值allowed_seeks小于0,则触发Seek Compaction,并且在不存在Size Compaction时开始执行Seek Compaction;

将值存储在值存储空间,将所述值存储空间按键范围进行分组,并记录每个分组的访问频率,确定每个分组的访问热度,根据每个分组内的有效键值对数量、键值对数量和访问热度计算出每个分组的分数值,具体包括:采用下式计算分数值Score:

;

其中,Hotness表示分组的访问热度,与分组的访问频率正相关,KVNum表示分组内的键值对数量,ValidNum表示分组内的有效键值对数量,按所述分数值通过大顶堆进行排序;

选择大顶堆的堆顶元素所属的分组进行GC;

在GC之后,根据分组的访问热度对分组进行自适应动态调整,所述调整包括合并、分裂或维持不变。

2.根据权利要求1所述的基于键值分离的键值存储系统中范围查询优化方法,其特征在于,还包括:采用分组表格记录所述值存储空间内所有分组的信息,所述分组的信息包括分组的键范围的最小值和最大值、分组的标识ID、分组内的键值对数量和分组内的有效键值对数量,其中,分组内的有效键值对数量在分组GC后更新,并在每次分组GC后刷新所述分组表格中的信息,并追加到分组日志中;

采用GC堆记录所有分组对应的标识ID、分数值和访问热度,在所述GC堆内按所述分数值通过大顶堆进行排序。

3.根据权利要求1所述的基于键值分离的键值存储系统中范围查询优化方法,其特征在于,所述根据分组的访问热度对分组进行自适应动态调整,具体包括:响应于确定分组Groupi触发GC,读取分组Groupi的信息,从GC堆中读取下一个堆顶元素对应分组Groupj的访问热度;

响应于确定分组Groupi的访问热度大于或等于分组Groupj的访问热度的两倍,且分组Groupi的键范围的最大值与最小值之差大于或等于最小分组范围,则将所述分组Groupi分裂为两个分组;

响应于确定分组Groupi的访问热度大于或等于分组Groupj的访问热度的两倍,且分组Groupi的键范围的最大值与最小值之差小于最小分组范围,则将分组Groupi维持不变;

响应于确定分组Groupi的访问热度小于分组Groupj的访问热度的两倍,分组Groupi‑1的访问热度大于或等于分组Groupi的访问热度的一半且小于或等于分组Groupi的访问热度的两倍,分组Groupi+1的访问热度小于分组Groupi的访问热度的一半且大于分组Groupi的访问热度的两倍,则将分组Groupi和分组Groupi‑1合并;

响应于确定分组Groupi的访问热度小于分组Groupj的访问热度的两倍,分组Groupi‑1的访问热度大于或等于分组Groupi的访问热度的一半且小于或等于分组Groupi的访问热度的两倍,分组Groupi+1的访问热度大于或等于分组Groupi的访问热度的一半且小于或等于分组Groupi的访问热度的两倍,则将分组Groupi、分组Groupi‑1和分组Groupi+1合并;

响应于确定分组Groupi的访问热度小于分组Groupj的访问热度的两倍,分组Groupi‑1的访问热度小于分组Groupi的访问热度的一半且大于分组Groupi的访问热度的两倍,分组Groupi+1的访问热度大于或等于分组Groupi的访问热度的一半且小于或等于分组Groupi的访问热度的两倍,则将分组Groupi和分组Groupi+1合并;

响应于确定分组Groupi的访问热度小于分组Groupj的访问热度的两倍,分组Groupi‑1的访问热度小于分组Groupi的访问热度的一半且大于分组Groupi的访问热度的两倍,分组Groupi+1的访问热度小于分组Groupi的访问热度的一半且大于分组Groupi的访问热度的两倍,则将分组Groupi维持不变。

4.一种基于键值分离的键值存储系统中范围查询优化装置,其特征在于,包括:

阈值调整模块,被配置为将键存储在LSM‑Tree中,获取在SSTable文件中点查询或范围查询的查询结果,根据所述查询结果动态调整阈值allowed_seeks,具体包括:响应于确定所述查询结果为命中,则将所述阈值allowed_seeks增加一;

响应于确定所述查询结果为未命中,则将所述阈值allowed_seeks减少一;所述阈值allowed_seeks为点查询和范围查询的查询结果中SSTable文件的最大容忍未命中次数,范围查询时的未命中表示对该SSTable文件查询时的无效迭代次数超过范围查询的一半范围,根据所述阈值allowed_seeks确定是否触发Seek Compaction,具体包括:响应于确定所述阈值allowed_seeks小于0,则触发Seek Compaction,并且在不存在Size Compaction时开始执行Seek Compaction;

分组模块,被配置为将值存储在值存储空间,将所述值存储空间按键范围进行分组,并记录每个分组的访问频率,确定每个分组的访问热度,根据每个分组内的有效键值对数量、键值对数量和访问热度计算出每个分组的分数值,具体包括:采用下式计算分数值Score:

;

其中,Hotness表示分组的访问热度,与分组的访问频率正相关,KVNum表示分组内的键值对数量,ValidNum表示分组内的有效键值对数量,按所述分数值通过大顶堆进行排序;

GC模块,被配置为选择大顶堆的堆顶元素所属的分组进行GC;

分组调整模块,被配置为在GC之后,根据分组的访问热度对分组进行自适应动态调整,所述调整包括合并、分裂或维持不变。

5.一种电子设备,包括:

一个或多个处理器;

存储装置,用于存储一个或多个程序,

当所述一个或多个程序被所述一个或多个处理器执行,使得所述一个或多个处理器实现如权利要求1‑3中任一所述的方法。

6.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现如权利要求1‑3中任一所述的方法。