(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210833801.0 (22)申请日 2022.07.15 (71)申请人 阿里巴巴 （中国） 有限公司 地址 311121 浙江省杭州市余杭区五常街 道文一西路969号3幢5层5 54室 (72)发明人 王志强　裴晓辉　毛耀宽　谢东凯　 颜红波　方铭　 (74)专利代理 机构 北京辰权知识产权代理有限 公司 11619 专利代理师 鞠永帅 (51)Int.Cl. G06F 3/06(2006.01) G06F 16/23(2019.01) G06F 16/27(2019.01) (54)发明名称 一种垃圾数据回收方法、 装置、 电子设备及 可读存储介质 (57)摘要 本申请提供了一种垃圾数据回收方法、 装 置、 电子设备及可读存储介质， 所述方法包括： 基 于LSM树结构 对数据记录的布局元数据进行单独 存储， 所述布局元数据包含所述数据记录的数据 量以及所述数据记录所属的数据文件的标识； 响 应于垃圾数据回 收请求， 遍历所述LSM树结构， 计 算每个数据文件的垃圾比； 根据所述数据文件的 垃圾比对所述数据文件执行垃圾数据回收操作。 这样， 无需关注存储系统中二维的目录树结构以 及数据文件 大小的可变性等问题， 直接遍历存储 的LSM树结构， 计算对应数据文件的垃圾比， 计算 简单、 高效、 精确。 权利要求书2页 说明书11页 附图2页 CN 115237345 A 2022.10.25 CN 115237345 A 1.一种垃圾数据回收方法， 包括： 基于LSM树结构对数据记录的布局元数据进行单独存储， 所述布局元数据(L ayoutMata   Data)包含所述数据记录的数据量以及所述数据记录所属的数据文件的标识； 响应于垃圾数据回收请求， 遍历所述 LSM树结构， 计算每 个数据文件的垃圾比； 根据所述数据文件的垃圾比对所述数据文件执 行垃圾数据回收操作。 2.根据权利要求1所述的方法， 其中， 所述LSM树结构的所述布局元数据按照预设的布 局元数据文件(LayoutFile)的存储逻辑进行存储， 每个布局元数据文件包含至少一个所述 布局元数据， 且所述布局元数据文件的扩展头中包含该布局元数据文件的所有布局元数据 所关联的所述数据文件的标识以及该 所述数据文件内的有效数据量。 3.根据权利要求2所述的方法， 其中， 通过如下步骤遍历所述LSM树结构： 遍历所述LSM 树结构的所有布局元数据文件的扩展头， 基于所述数据文件的标识统计每个所述数据文件 在各个所述布局元数据文件的扩展头中记录的该所述数据文件内的有效数据量， 并确定所 述数据文件的有效数据总量。 4.根据权利要求3所述的方法， 其中， 所述计算每个数据文件的垃圾比中， 根据所述数 据文件的数据总量和有效数据总量， 计算该 所述数据文件的垃圾比。 5.根据权利要求1所述的方法， 其中， 所述LSM树结构采用N层数据结构， N为大于1的整 数； 所述基于LSM树结构对数据记录的布局元 数据进行 单独存储， 包括： 接收至少一个数据记录的所述布局元 数据， 存储在内存中进行积累； 所述内存中的数据量达到第 一预设阈值的情况下， 将所述内存中的所述布局元数据转 存到所述 LSM树结构的第1层； 根据预设的合并策略对所述 LSM树结构进行 逐层合并， 得到第N层。 6.根据权利要求5所述的方法， 其中， 所述根据预设的合并策略对所述LSM树结构进行 逐层合并， 得到第N层， 包括： 所述LSM树结构的第N ‑1层满足预设条件的情况下， 将第N ‑1层的所述布局元数据和第N 层当前的所述布局元数据进 行合并， 并清空第N ‑1层的所述布局元数据和第N层当前的所述 布局元数据， 清空后的所述第N层用于存 储合并后的所述布局元 数据。 7.根据权利要求5所述的方法， 其中， 所述根据预设的合并策略对所述LSM树结构进行 逐层合并， 得到第N层， 包括： 所述LSM树结构的第I ‑1层满足预设条件 的情况下， 将第I ‑1层的所述布局元数据合并 到所述LSM树结构的第I层， 并清空第I ‑1层的所述布局元 数据， I包 含2至N‑1的整数。 8.根据权利 要求1所述的方法， 其中， 采用N层数据结构的所述LSM树结构中， 第1层所述 布局元数据所关联的所有 数据文件的最大数据量与第N层所述布局元数据所关联的所有 数 据文件的最大 数据量的比例， 小于预设的比例阈值。 9.一种垃圾数据回收装置， 包括： 元数据存储模块， 其用于基于LSM树结构对数据记录的布局元数据进行单独存储， 所述 布局元数据包含所述数据记录的数据量以及所述数据记录所属的数据文件的标识； 垃圾比计算模块， 其用于响应于垃圾数据回收请求， 遍历所述LSM树结构， 计算每个数 据文件的垃圾比； 数据回收模块， 其用于根据 所述数据文件的垃圾比对所述数据文件执行垃圾数据回收权　利　要　求　书 1/2 页 2 CN 115237345 A 2操作。 10.一种电子设备， 包括： 存 储器和处 理器； 所述存储器， 其用于存 储程序； 所述处理器， 耦合至所述存 储器， 用于执 行所述程序， 以用于： 基于LSM树结构对数据记录的布局元数据进行单独存储， 所述布局元数据包含所述数 据记录的数据量以及所述数据记录所属的数据文件的标识； 响应于垃圾数据回收请求， 遍历所述 LSM树结构， 计算每 个数据文件的垃圾比； 根据所述数据文件的垃圾比对所述数据文件执 行垃圾数据回收操作。 11.一种计算机可读存储介质， 其上存储有计算机程序， 所述程序被处理器执行实现权 利要求1‑8任一项所述的方法。权　利　要　求　书 2/2 页 3 CN 115237345 A 3