(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211285954.2 (22)申请日 2022.10.20 (71)申请人 河北工业大 学 地址 300130 天津市红桥区丁字沽光 荣道8 号河北工业大 学东院330# (72)发明人 刘靖宇　范小芹　史巧硕　李娟　 朱怀忠　武优西　 (74)专利代理 机构 天津翰林知识产权代理事务 所(普通合伙) 12210 专利代理师 付长杰 (51)Int.Cl. G06F 16/22(2019.01) (54)发明名称 基于频度的存 储和差异化管理方法 (57)摘要 本发明为基于频度的存储和差异化管理方 法， 该方法以键值对的频度值为基础， 将键值对 归类为高频度键值对、 中频度键值对以及低频度 键值对， 设计一种基于频度的新键值格式， 以便 对不同频度的数据存储选择不同的键值格式， 同 时提出了根据键值对类型实行差异化管理。 可以 大大减少日志结构合并树LSM ‑tree中的数据量， 进一步减轻写放大问题， 从而提高读写性能。 可 以对高频度键值对达到快速读写访问的效果， 将 中频度键值对的值和键地址以及整个低频度键 值对存放在值日志ValueLog中， 因为范围查询需 要随机读， 故从值日志Value  Log中预取值可以 提高范围查询性能。 权利要求书2页 说明书8页 附图3页 CN 115510069 A 2022.12.23 CN 115510069 A 1.一种基于频度的存 储和差异化管理方法， 其特 征在于， 该 方法包括以下步骤： 1)基于频度将键值对分类为高频度键值对、 中频度键值对以及低频度键值对： 2)根据键值对不同分类设计相对应的键值格式： 对于高频度键值对， 其键值格式只需添加键值对类型字段H， 不作其 余变动； 对于中频度键值对， 对其键值格式分开设计， 键格式中有键值对类型typ e字段M、 键key 字段以及值地址value  addr字段， 值格式中含有键值对类型type字段M、 分段号segment_ no、 偏移量offset、 实际值value四个字段； 值地址value  addr代表实际值value在值日志 Value Log中的地址， 分段号segment_no代表实际值value处于值日志Value  Log中的第几 段， 偏移量 offset代表实际值value在段内的偏移值； 对于低频度键值对， 低频度键值对键值格式为键值对类型typ e字段L、 分段号segment_ no、 偏移量 offset字段、 键key和值value； 3)对不同类别的键值对执 行差异化管理： 高频度键值对将其键值存放在日志结构合并树LSM ‑tree中； 对中频度键值对实行键值 分离操作， 将 键和值地址存放在日志结构合并树LSM ‑tree中， 将实际值valu e存放在值日志 Value Log中； 对于低频度键值对， 直接将 键值对放在值日志Value  Log中， 在读取低频度键 值对时， 利用固态硬 盘的并行I/O特性， 在范围查询期间从值日志 Value Log中预取值。 2.根据权利要求1所述的基于频度的存储和差异化管理方法， 其特征在于， 步骤1)中， 对于一个block数据块中的键值对序列， 计算每个键值对的频度， 获得相应置信度并排序， 将置信度排名前10％的键值对定义为高频度键值对； 将 置信度排名前11％～ 40％的键值对 定义为中频度键值对； 将剩余6 0％的键值对定义 为低频度键值对； 具体过程是： 11)传入数据bl ock块： 键值对序列(KV1,KV2…,KVn)， n为键值对序列中键值对的数量； 12)计算每 个键值对单位时间内的频度ki并根据频度ki对键值对进行排序： 其中： PRi和PWi分别为键值对KVi的读频次和写频次， T为时间 间隔； 13)计算频度间隙di： di＝ki+1‑ki 14)计算置信度Δi： 15)采用简单选择排序对键值对置信度进行从小到大排序， 排序后的置信度 序列为： Δ′1,Δ′2,…,Δ′n‑1 16)把键值对序列按照置信度6： 3： 1的比例将键值对分为 三支： 按照置信度大小将排序后的置信度序列划分三个分支， 包括高频度分支[0， Δ '0.1(n‑1)]、 中频度分支[ Δ'0.2(n‑1),Δ'0.4(n‑1)]以及低频度分支[ Δ'0.5(n‑1),Δ'(n‑1)]， 找到三 支中排序后的置信度分别对应的键值对， 并按照置信度大小有序存储键值对， 获得高频度 键值对序列KVH、 中频度键值对序列KVM以及低频度键值对序列KVL, 低频度： 权　利　要　求　书 1/2 页 2 CN 115510069 A 2中频度： 高频度： 其中， l取值为1～L， L为低频度分支中的序列数量， m取值为1～M， M为中频度分支中的 序列数量， h取值为1～H， H为高频度分支中的序列数量， KVl为低频度键值对序列KVL中的键 值对， KVm为中频度键值对序列KVM中的键值对， KVh为高频度键值对序列KVH中的键值对； [0， Δ'0.1(n‑1)]为排序后的置信度序列的前10％， 下标n ‑1表示置信度序列的长度， 下标 0.1、 0.2、 0.4、 0.5表示当前置信度在排序后的置信度 序列中的相对位置 。 3.根据权利要求1所述的基于频度的存储和差异化管理方法， 其特征在于， 所述步骤3) 的具体过程是： 31)将高频度键值对键值存放在日志结构合并树LSM ‑tree的排序字符串表SST文件中， 高频度键值对在排序字符串表S ST文件中以置信度有序排列； 32)将中频度键值对的键和值分开存 储： 存储值： 中频度键值对的实际值存储在值日志Value  Log中， 其 中包含键值对类型typ e 字段M； 值日志V alue Log文件选择段式存储方式， 故包含键值对存储在值日志 中的分段号 segment_n o以及偏移量 offset以及实际值value； 存储键： 将键和值地址存放在日志结构合并树LSM ‑tree的排序字符串表SST文件中， 在 排序字符串表SST文件中， 中频度键值对与高频度键值对相同都是以置信度有序排列， 将中 频度键值对和高频度键值对单独存放在不同的排序字符串表SST文件中， 并对排序字符串 表SST文件加以区分， 以SSTH表示高频度键值对存放的排序字符串表SST， 以SSTM表示中频度 键值对存放的排序字符串表S ST， 以便在查询键值对时快速分辨； 日志结构合并树LSM ‑tree的每一层中高频度键值对和中频度键值对均按照1:2的比例 放置相应的键 值对， 第一层C0中放置一个高频度键 值对和两个中频度键 值对， 第二层C2中放 置两个高频度键值对和四个中频度键值对， 下一层比上一层存放的键值对数量多三个， 当 上一层存 满后合并到下一层； 33)低频度键值对仅要求范围读性能， 在访问速度上不作要求， 将低频度键值对的键值 存放在值日志 Value Log中且与中频度键值对的值存 储区分开。权　利　要　求　书 2/2 页 3 CN 115510069 A 3