一种基于日志结构合并树的两阶段合并方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107526550A(43)申请公布日2017.12.29(21)申请号201710795391.4(22)申请日2017.09.06(71)申请人中国人民大学地址100872北京市海淀区中关村大街59号(72)发明人柴云鹏韦皓诚梁雨诗(74)专利代理机构北京纪凯知识产权代理有限公司11245代理人徐宁刘美丽(51)Int.Cl.G06F3/06(2006.01)权利要求书2页说明书5页附图2页(54)发明名称一种基于日志结构合并树的两阶段合并方法(57)摘要本发明涉及一种基于日志结构合并树的两阶段合并方法，包括以下步骤：1)根据不均衡得分在开源系统中选出空间分布最不合理的一层；2)根据轮询原则选出空间分布最不合理一层中的目标文件；3)将目标文件按覆盖相同键值范围的下层文件分割碎片，将每一碎片与对应键值范围的下层文件链接，并为每一下层文件增加SliceLink；4)检查每一下层文件SliceLink数量，若所有下层文件SliceLink数量均不超过预设阈值则进入步骤2)，直到存在下层文件SliceLink数量超过预设阈值则进入步骤5)；5)将SliceLink数量超过预设阈值的下层文件以及与该下层文件碎片链接的对应键值范围目标文件分别读入开源系统内存中进行合并生成新文件后写入下层文件所在层，本发明可广泛用于信息存储技术领域中。CN107526550ACN107526550A权利要求书1/2页1.一种基于日志结构合并树的两阶段合并方法，其特征在于，包括以下步骤：1)根据不均衡得分，在开源系统中选出空间分布最不合理的一层；2)根据轮询原则，选出空间分布最不合理的一层中的目标文件；3)链接阶段：将目标文件按照覆盖相同键值范围的下层文件分割碎片，将每一碎片与对应键值范围的下层文件进行链接，并为每一下层文件均增加用于记录链接信息的链接元数据，记为SliceLink；4)检查每一下层文件的SliceLink数量，若所有下层文件的SliceLink数量均不超过预设阈值，则进入步骤2)，直到存在下层文件的SliceLink数量超过预设阈值，则进入步骤5)；5)合并阶段：将SliceLink数量超过预设阈值的下层文件以及与该下层文件碎片链接的对应键值范围的目标文件分别读入开源系统的内存中进行合并，生成新文件后写入下层文件所在层中。2.如权利要求1所述的一种基于日志结构合并树的两阶段合并方法，其特征在于，所述步骤3)中将目标文件按照覆盖相同键值范围的下层文件分割碎片，将每一碎片与对应键值范围的下层文件进行链接，并为每一下层文件均增加用于记录链接信息的链接元数据，具体过程为：①将目标文件标记为冻结状态，通过开源系统表缓存中的目标文件元数据记录目标文件的键值范围；②在开源系统的表缓存中获取与目标文件覆盖相同键值范围的若干下层文件；③根据每一下层文件的键值范围将目标文件分割成若干碎片，并将每一碎片与对应键值范围的下层文件进行链接；④为目标文件引入用于记录目标文件被链接次数的引用计数；⑤在开源系统的内存中为每一下层文件均增加用于记录链接信息的SliceLink，其中，链接信息包括所链接碎片的来源和键值范围。3.如权利要求2所述的一种基于日志结构合并树的两阶段合并方法，其特征在于，所述步骤4)中的预设阈值根据日志结构合并树的扇出进行设置。4.如权利要求3所述的一种基于日志结构合并树的两阶段合并方法，其特征在于，所述步骤5)中将SliceLink数量超过预设阈值的下层文件以及与该下层文件碎片链接的对应键值范围的目标文件分别读入开源系统的内存中进行合并，生成新文件后写入下层文件所在层中，具体过程为：a)根据SliceLink数量超过预设阈值的下层文件中每一SliceLink记录的碎片来源，确定该下层文件中每一碎片链接的冻结状态目标文件；b)根据上述SliceLink记录的碎片键值范围和对应冻结状态目标文件的元数据，得到该下层文件中每一碎片的键值范围覆盖的目标文件数据块；c)将该下层文件和目标文件数据块分别读入开源系统的内存后进行一次归并排序生成新文件，并将新文件写入该下层文件所在层中；d)检测冻结状态目标文件的引用计数，当引用计数为0时，该冻结状态的目标文件即能够被回收并删除。5.如权利要求1所述的一种基于日志结构合并树的两阶段合并方法，其特征在于，在对下层文件进行读操作处理时采用小粒度读操作，即先读取下层文件的SliceLink，若所需读2CN107526550A权利要求书2/2页取的数据不在该SliceLink中，则再去该下层文件中进行搜索。3CN107526550A说明书1/5页一种基于日志结构合并树的两阶段合并方法技术领域[0001]本发明是关于一种基于日志结构合并树的两阶段