CN105159915B - 可动态适应的lsm树合并方法及系统 - Google Patents

Abstract

本发明适用于文件处理技术领域，提供了一种可动态适应的LSM树合并方法，所述方法包括：将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件；根据当前数据的分布动态调整树的形状；当有新写入的文件时，遍历树寻找最适节点放入；对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact。本发明还相应的提供一种实现上述方法的可动态适应的LSM树合并系统。借此，本发明可以实现动态适应数据的分布，提高数据合并效率。

Description

可动态适应的LSM树合并方法及系统

技术领域

本发明涉及文件处理技术领域，尤其涉及一种可动态适应的LSM树合并方法及系统。

背景技术

Log-structured merge树，也被称为LSM树，是目前NoSQL数据库常用的数据组织方式。它把对索引的变更进行延迟和批量处理，并通过类似归并排序的方式高效地将更新迁移到磁盘。LSM树的节点在具体实现中往往就是一个文件，文件内部有序，文件之间无序，查询时需要查询所有文件，合并每个文件的结果，从而造成性能低下，所以一般会把若干个文件合并成一个大文件，通过合并文件，减少文件数量，真正删除数据，以减少每次查询涉及到的文件数，提高数据的查询效率，即Compact。Compact过程会读多个文件合并后重新写成文件，这会占用大量磁盘I/O等相关资源，而不当的Compact或不及时的Compact又会造成查询时涉及过多文件而使它的性能下降。目前主流的合并方法：Tiered Compact、LevelDBCompact和Stripe Compact。

1.Tiered Compact策略如下:

(1)首先将候选文件按照入库时间(Sequence ID，即顺序号)从旧到新排序，候选集为正在合并的文件之后的文件；

(2)如果请求是一个Major Compact，如果目前的文件列表是所有的文件，则进行Major Compact，否则不能进行Major Compact；

(3)如果列表文件数量小于配置的合并最小文件数量阈值，则放弃做MinorCompact；

(4)使用一个ratio参数，选取按照从老到新的顺序进行，遍历每个文件时，如果它的大小小于所有比它新的文件的和与ratio的乘积，则它是一个候选；

(5)选取处理的文件个数大于配置的合并最小文件数量阈值，则进行MinorCompact，否则放弃执行。

该方法和系统简单易实现，完成合并操作以后能够提升读性能，但是合并过程本身的代价是比较大的，在更新密集型的操作中，这样就会带来以下问题：

(1)数据分布不一致，一行数据可能在一个文件中，也可能跨越多个文件，最坏情况下可能每个文件中都有，这样针对不同key查询时涉及到的文件数量不同，查询性能不稳定；

(2)浪费大量I/O，一个文件可能执行多次合并，滚雪球似的反复被重写。没有考虑数据的分布，如不变化的key区间其实是不需要再被合并的了，但是在这个算法中仍然会执行这不必要的合并；

(3)只有Major Compact时才会清除掉删除数据，而Major Compact由于需要合并重写所有文件，消耗资源比较严重，执行时间很长，所以不会频繁执行，一般一天执行一次。那么由于无法保证删除的数据要多久才能被清除，在删除密集型操作中，有大量空间可能被浪费；

(4)合并过程中旧的文件只有在新的文件写入完成后才能删除，需要额外占用磁盘空间。Major Compact要将所有的文件合并重写，使得临时磁盘空间到达原来的两倍。

2.LevelDB Compact策略如下：

(1)当Level-L的文件总大小超过阈值时，后台线程进行合并；

(2)从Level-L中选出一个文件，从Level-(L+1)中选出与它的键值范围交叠的文件。Level-0比较特殊，因为Level-0的文件键值是互相交叠的，所以需要特别处理从Level-0到Level-1的合并：如果文件之间有键值交叠，可能需要从Level-0中选出多于一个文件；

(3)合并线程读取这些文件内容，归并排序生成一系列Level-(L+1)文件，当生成文件的大小超过2MB的时候就转而生成一个新文件来写入，还有与当前键值范围交叠的Level-(L+2)文件超过了10个时，那么也需要转而生成一个新文件来写入，这样可以保证后续Level-(L+1)文件的合并不会挑选出太多Level-(L+2)的文件；

(4)当新文件生成并服务后，老的文件就会被舍弃；

(5)对于一个Level，文件合并的顺序是轮流的，记录上次此Level合并的最大键值(end key)，下次此Level合并的时候则选择此键值开始的第一个文件(如果没有则转回此Level的第一个文件)；

(6)合并清除同一个键的旧数据，也会清除删除标记影响的数据，当更高Level中没有此键值范围的文件就可以清除删除标记。

算法的好处是在合并的过程中，仅需由两个Level的部分文件参与，而不是要对所有文件执行合并操作，这样会加快合并执行的效率。大部分的读操作有LRU特性，都会落入较低的Level上。因此，数据越“热”，Level就越低，有利于多种存储介质的合理使用。

算法的主要问题是它无法动态调整Level层数，如果Level过多，在递归合并的过程中，容易造成某个区间的合并风暴，并且每次下推都需要重写文件。此外，不同Level之间的键值没有对应关系，上层Level的键值区间对应下层Level的区间事先无法预测，当上层Level的某一个文件需要与下层Level合并的时候，对下层Level的影响范围并不存在确定性，由当前的键值范围影响。

3.Stripe Compact策略如下：

(1)对于Region下的键值区间进行二次切分，分成更多小区间，每个区间即为Stripe；

(2)Region下的数据文件分为Level-0和Level-1两层。其中Level-0包括整个键值区间，从内存中刷写下来的文件和批量导入产生的文件默认放在Level-0；

(3)当Level-0文件积累到阈值时，通过合并把Level-0的文件切分到Level-1，每个键值与其相交的Stripe都会形成一个文件放入相应Stripe；

(4)Stripe内部可以进行合并以防止Stripe文件数过多；

(5)Stripe的切分有两种方式：基于个数的方式(Count-based)和基于大小的方式(Size-based)；

(6)读取时，一个键值所涉及的数据范围有内存、Level-0所有文件、以及Level-1中对应的Stripe的文件；

(7)容错机制。在Level-1的Stripe间的键值范围应该是连续的，如果出现异常情况导致Stripe之间存在空洞，那么可将所有Level-1的文件重新放回Level-0；

Stripe合并保留了分层的优势的同时，降低了层级数量和文件个数，有利于Region的分裂和合并。它的问题在于Level-1中Stripe的分布和数量很难动态调整，如果Stripe过小，从Level-0刷写下来的文件就会过小；如果Stripe过大，Stripe区间很大，每个Stripe中会遇到与Region内部Tiered Compact同样的问题。

现有技术无法动态适应数据的分布，数据的组织方式无法随着数据的分布不同而高效地动态调整，合并效率低下，经常做一些无用的合并，占用系统资源。

综上可知，现有技术在实际使用上显然存在不便与缺陷，所以有必要加以改进。

发明内容

针对上述的缺陷，本发明的目的在于提供一种可动态适应的LSM树合并方法及系统，其可以动态适应数据的分布，提高数据合并效率。

为了实现上述目的，本发明提供一种可动态适应的LSM树合并方法，所述方法包括：

将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件；

根据当前数据的分布动态调整树的形状；

当有新写入的文件时，遍历树寻找最适节点放入；

对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact。

根据本发明的可动态适应的LSM树合并方法，所述树形结构的根节点对应完整的键值区间；

所述树形结构的子节点是父节点的划分，所有子节点的键值区间组合起来形成所述父节点的键值区间，且各个子节点对应的键值区间之间相互连续、互斥无重合。

根据本发明的可动态适应的LSM树合并方法，所述根据当前数据的分布动态调整树的形状步骤包括：

根据当前数据的分布动态调整树的节点数量和/或树的高度和/或树的度。

根据本发明的可动态适应的LSM树合并方法，所述方法还包括：

当文件中缺失了所在的节点信息时，遍历树寻找最适节点放入所述文件。

根据本发明的可动态适应的LSM树合并方法，所述当有新写入的文件时，遍历树寻找最适节点放入步骤之前还包括：

配置每个节点的最大值SizeMax和最小值SizeMin；

设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin。

根据本发明的可动态适应的LSM树合并方法，所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当一个非叶节点的文件总大小大于SizeMax时，将所述文件分发到子节点；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量小于ChildrenNumberMax时，该叶节点分裂为两个大小相同的与原节点同深度的兄弟节点，所述叶节点对应的键值区间也相应的分开。

根据本发明的可动态适应的LSM树合并方法，所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量不小于ChildrenNumberMax时，将该叶节点分裂出两个相同大小的子节点，该叶节点的键值区间也相应的分为两部分，并分配给子节点，把所述文件写到所述两个子节点中；

当一个叶节点的大小小于SizeMin时，将该叶节点与兄弟节点合并。

根据本发明的可动态适应的LSM树合并方法，所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当上一层的节点数目小于ChildrenNumberMin，并且存在一个节点的子节点数目与这一层节点数量的和不大于ChildrenNumberMax时，则将该子节点上提处理。

本发明还提供一种可动态适应的LSM树合并系统，包括：

树组建模块，用于将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件；

树调整模块，用于根据当前数据的分布动态调整树的形状；

节点配置模块，用于当有新写入的文件时，遍历树寻找最适节点放入；

文件处理模块，用于对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact。

根据本发明的可动态适应的LSM树合并系统，所述系统还包括：

阈值配置模块，用于配置每个节点的最大值SizeMax和最小值SizeMin；以及设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin。

本发明通过将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件，并根据当前数据的分布动态调整树的形状，借此优化组织形式来提高合并效率和查询速度。当有新写入的文件时，遍历树寻找最适节点放入，一次找到当前最适合的节点，减少文件从根往叶子节点流动时合并的次数。当对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行MajorCompact，借此减小Major Compact范围，提高合并效率。

附图说明

图1是本发明的可动态适应的LSM树合并方法流程图；

图2是本发明一实施例的随机数据情况下查询涉及文件数示意图；

图3是本发明一实施例的随机数据情况下的平均合并数示意图；

图4是本发明一实施例的时序数据情况下查询涉及文件数示意图；

图5是本发明一实施例的时序数据情况下平均合并数示意图；

图6是本发明一实施例的数据组织方式结构示意图；

图7是本发明一实施例的数据组织方式与分布结构示意图；

图8是本发明的可动态适应的LSM树合并系统结构示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

发明人在进行基于LSM的数据存储系统研究时，发现现有技术中的缺陷是由不当的合并策略导致的。经过对现有合并方法和传统数据库数据组织方法研究发现，解决该项缺陷可以通过树形结构的数据组织的方法来实现。LevelDB Compact将文件按照层级组织，但是层级之间并没有直接联系，当在层级之间发生合并时并不知道涉及到的下层区间。Stripe Compact定义了两个层级，但是这样的限制又会使得区间的大小很难调整。本发明通过提出的树形结构旨在解决上述问题，实现动态适应，提高查询速度和合并效率

参见图1，本发明提供了一种可动态适应的LSM树合并方法，其包括下述步骤：

步骤S101，将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件。

具体的，本发明中树形结构的根节点对应完整的键值区间，树形结构的子节点是父节点的划分，即：所有子节点的键值区间组合起来形成父节点的键值区间，且各个子节点对应的键值区间之间相互连续、互斥无重合。

步骤S102，根据当前数据的分布动态调整树的形状。

随着树的节点中数据的变化，树形结构可以根据当前数据的分布动态调整树的形状，具体包括调节树的节点数量和/或树的高度和/树的度。借此，通过步骤S101和S102的优化组织形式，可以大大提高合并效率和查询速度。

步骤S103，当有新写入的文件时，遍历树寻找最适节点放入。

本发明所述的最适节点，具体的说是节点深度越深越适合放入文件。一次找到当前最适合的节点，可以减少文件从根往叶子节点流动时合并的次数。

步骤S104，对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact。通过该步骤S104，可以减小Major Compact范围，提高合并效率。

优选的是，当文件中缺失了所在的节点信息时，与新加入的文件相同采用相同处理方式，遍历树寻找最适节点放入文件，借此保证在极端条件下数据不会丢失，提高处理系统可靠性和数据安全性。

在基于LSM的数据存储系统中，本发明的方法主要影响的是系统资源，如磁盘I/O和查询时涉及的文件数量。在下述实施例中，本发明测试中选择了随机数据和时序数据两种场景，数据总量为2亿个键值对，每个键值对1KB大小。

图2示出的是随机数据情况下查询涉及文件数，图3示出的是随机数据情况下的平均合并数。根据图2和图3所示，本发明提出的方法在随机数据中与Tiered Compact结果相当，但在时序数据中本发明比Tiered Compact文件数少80％，IO减少50％。由此可见，本发明可以大大节省系统资源。

图4示出的是时序数据情况下查询涉及文件数，图5示出的是时序数据情况下平均合并数。如图4和图5所示本专利提出的方法在时序数据中比Stripe Compact文件数减少50％，IO减少50％。(图2～图5所示的实施例中的文件数是指查询时涉及到的文件数量)

图6是本发明一实施例的数据组织方式结构示意图。该实施例中，在组织好树形结构后，步骤S103之前还包括：配置每个节点的最大值SizeMax和最小值SizeMin；设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin。并且步骤S103在遍历树寻找最适节点放入新文件具体包括如下处理规则：

当一个非叶节点的文件总大小大于SizeMax时，将所述文件分发到子节点；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量小于ChildrenNumberMax时，该叶节点分裂为两个大小相同的与原节点同深度的兄弟节点，所述叶节点对应的键值区间也相应的分开；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量不小于ChildrenNumberMax时，将该叶节点分裂出两个相同大小的子节点，该叶节点的键值区间也相应的分为两部分，并分配给子节点，把所述文件写到所述两个子节点中；

当一个叶节点的大小小于SizeMin时，将该叶节点与兄弟节点合并；

当上一层的节点数目小于ChildrenNumberMin，并且存在一个节点的子节点数目与这一层节点数量的和不大于ChildrenNumberMax时，则将该子节点上提处理，借此可以压缩路径。

进一步的，本发明在查询一个键值Rowkey的数据时，如图7所示，先从根节点开始，从根节点到叶节点的路径上依次选出与RowKey相关的节点；再把这些节点的文件返回给上层接口，再根据这些文件的键值区间对文件进行过滤。如图7所示每个区间都对应了键值范围，当查询Rowkey＝7540的数据时，那么候选就是N0、N2、N4节点内的文件，选出文件后再根据文件的键值区间过滤。

另外本发明在进行查询时，可首先给出查询请求键值范围[A,B)，然后从根节开始向下搜索包含[A,B)的节点，并返回所有满足的节点文件，完成查询过程。

参见图8，本发明提供了一种实现上述方法的可动态适应的LSM树合并系统，该系统100包括：

树组建模块10，用于将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件。

本发明中树形结构的根节点对应完整的键值区间，树形结构的子节点是父节点的划分，即：所有子节点的键值区间组合起来形成父节点的键值区间，且各个子节点对应的键值区间之间相互连续、互斥无重合。

树调整模块20，用于根据当前数据的分布动态调整树的形状。

随着树的节点中数据的变化，树形结构可以根据当前数据的分布动态调整树的形状，具体包括调节树的节点数量和/或树的高度和/树的度。借此，本发明优化组织形式，大大提高合并效率和查询速度

阈值配置模块30，用于配置每个节点的最大值SizeMax和最小值SizeMin；以及设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin。

节点配置模块40，用于当有新写入的文件时，遍历树寻找最适节点放入。本发明所述的最适节点，具体的说是节点深度越深越适合放入文件。一次找到当前最适合的节点，可以减少文件从根往叶子节点流动时合并的次数。

在遍历树寻找最适节点放入新文件具体包括如下处理规则：

当一个非叶节点的文件总大小大于SizeMax时，将所述文件分发到子节点；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量小于ChildrenNumberMax时，该叶节点分裂为两个大小相同的与原节点同深度的兄弟节点，所述叶节点对应的键值区间也相应的分开；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量不小于ChildrenNumberMax时，将该叶节点分裂出两个相同大小的子节点，该叶节点的键值区间也相应的分为两部分，并分配给子节点，把所述文件写到所述两个子节点中；

当一个叶节点的大小小于SizeMin时，将该叶节点与兄弟节点合并；

当上一层的节点数目小于ChildrenNumberMin，并且存在一个节点的子节点数目与这一层节点数量的和不大于ChildrenNumberMax时，则将该子节点上提处理，借此可以压缩路径。

文件处理模块50，用于对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact，借此减小Major Compact范围，提高合并效率。

综上所述，本发明通过将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件，并根据当前数据的分布动态调整树的形状，借此优化组织形式来提高合并效率和查询速度。当有新写入的文件时，遍历树寻找最适节点放入，一次找到当前最适合的节点，减少文件从根往叶子节点流动时合并的次数。当对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact，借此减小Major Compact范围，提高合并效率。

当然，本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。

Claims (8)

1.一种可动态适应的LSM树合并方法，其特征在于，所述方法包括：

将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件；

根据当前数据的分布动态调整树的形状；

当有新写入的文件时，遍历树寻找最适节点放入；

对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact；

其中所述当有新写入的文件时，遍历树寻找最适节点放入步骤之前还包括：配置每个节点的最大值SizeMax和最小值SizeMin；设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin；

所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当一个非叶节点的文件总大小大于SizeMax时，将所述文件分发到子节点；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量小于ChildrenNumberMax时，该叶节点分裂为两个大小相同的与原节点同深度的兄弟节点，所述叶节点对应的键值区间也相应的分开。

2.根据权利要求1所述的可动态适应的LSM树合并方法，其特征在于，所述树形结构的根节点对应完整的键值区间；

所述树形结构的子节点是父节点的划分，所有子节点的键值区间组合起来形成所述父节点的键值区间，且各个子节点对应的键值区间之间相互连续、互斥无重合。

3.根据权利要求1所述的可动态适应的LSM树合并方法，其特征在于，所述根据当前数据的分布动态调整树的形状步骤包括：

根据当前数据的分布动态调整树的节点数量和/或树的高度和/或树的度。

4.根据权利要求1所述的可动态适应的LSM树合并方法，其特征在于，所述方法还包括：

当文件中缺失了所在的节点信息时，遍历树寻找最适节点放入所述文件。

5.根据权利要求1所述的可动态适应的LSM树合并方法，其特征在于，所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量不小于ChildrenNumberMax时，将该叶节点分裂出两个相同大小的子节点，该叶节点的键值区间也相应的分为两部分，并分配给子节点，把所述文件写到所述两个子节点中；

当一个叶节点的大小小于SizeMin时，将该叶节点与兄弟节点合并。

6.根据权利要求1所述的可动态适应的LSM树合并方法，其特征在于，所述当有新写入的文件时，遍历树寻找最适节点放入步骤包括：

当上一层的节点数目小于ChildrenNumberMin，并且存在一个节点的子节点数目与这一层节点数量的和不大于ChildrenNumberMax时，则将该子节点上提处理。

7.一种可动态适应的LSM树合并系统，其特征在于，包括：

树组建模块，用于将键值区间划分为若干节点，将所述节点组织为树形结构，每个所述节点对应一键值区间，每个所述键值区间包含对应该键值区间范围的文件；

树调整模块，用于根据当前数据的分布动态调整树的形状；

节点配置模块，用于当有新写入的文件时，遍历树寻找最适节点放入；

文件处理模块，用于对文件进行处理时，对节点内部进行Minor Compact处理，并且只通过叶节点执行Major Compact；

其中所述当有新写入的文件时，遍历树寻找最适节点放入之前还包括：配置每个节点的最大值SizeMax和最小值SizeMin；设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin；

所述当有新写入的文件时，遍历树寻找最适节点放入包括：

当一个非叶节点的文件总大小大于SizeMax时，将所述文件分发到子节点；

当一个叶节点的文件总大小大于SizeMax，且该叶节点的兄弟节点的数量小于ChildrenNumberMax时，该叶节点分裂为两个大小相同的与原节点同深度的兄弟节点，所述叶节点对应的键值区间也相应的分开。

8.根据权利要求7所述的可动态适应的LSM树合并系统，其特征在于，所述系统还包括：

阈值配置模块，用于配置每个节点的最大值SizeMax和最小值SizeMin；以及设置每个节点的子节点个数最大值ChildrenNumberMax和最小值ChildrenNumberMin。