CN105095287B - Lsm数据合并排序方法和装置 - Google Patents

Abstract

本发明实施例提供一种LSM数据合并排序方法和装置，通过利用相邻两级之间SSTable的相似度，对相邻两级中键值相似度最高的一对SSTable进行合并排序操作，因为，键值相似度最高的一对SSTable内存在相同的键值最多，也就是存在键值的旧版本最多，因此，根据键值相似度确定进行合并排序操作的SSTable，能够最早最多的删除旧版本的键值，避免旧版本的键值在存储设备中存储较长时间，占用存储空间，从而，提高存储空间的利用率。

Description

LSM数据合并排序方法和装置

技术领域

本发明实施例涉及计算机技术，尤其涉及一种日志结构合并(Log StructuredMerge，以下简称：LSM)数据合并排序方法和装置。

背景技术

LSM是一种有序非本地更新的数据结构，常用于大数据合并排序的数据结构，其主要应用于频繁更新的数据索引，数据频繁更新意味着存储设备中有大量键值(key/value)存在两个或更多版本。

通常，LSM有7级(level)，现有技术中，当某级的数据大小超过预设阈值时，将该级中的某个键范围(key Range)内的排序字符串表(Sorted String Table，以下简称：SSTable)与下一级中的相同的键范围内的SSTable 进行合并排序(compact)操作，从而，实现对键值的压缩和排序。SSTable 是指在一个键范围内存储的键值的排序表。

然而，采用现有技术的方法，针对存储设备中同一个键值不能及时删除旧版本，导致存储空间的利用率不高。

发明内容

本发明实施例提供一种LSM数据合并排序方法和装置，以提高存储空间的利用率。

本发明实施例第一方面提供一种LSM数据合并排序方法，包括：

获取相邻两级之间键值相似度最高的一对排序字符串表；

对所述一对排序字符串表进行合并排序操作。

结合第一方面，在第一种可能的实现方式中，所述获取相邻两级之间键值相似度最高的一对排序字符串表，包括：

以预设时间间隔获取相邻两级之间键值相似度最高的一对排序字符串表。

结合第一方面，在第二种可能的实现方式中，所述获取相邻两级之间键值相似度最高的一对排序字符串表，包括：

判断所述相邻两级中的上一级存储的数据大小是否超过预设阈值；

当所述相邻两级中的上一级存储的数据大小超过预设阈值时，则获取相邻两级之间键值相似度最高的一对排序字符串表。

结合第一方面或第一种可能的实现方式或第二种可能的实现方式，在第三种可能的实现方式中，所述对所述一对排序字符串表进行合并排序操作，包括：

从所述一对排序字符串表的相同的键值中确定旧版本的键值；

将所述旧版本的键值删除；

对删除所述旧版本之后的所述一对排序字符串表中的各键值进行排序。

本发明实施例第二方面提供一种LSM数据合并排序装置，包括：

获取模块，用于获取相邻两级之间键值相似度最高的一对排序字符串表；

处理模块，用于对所述一对排序字符串表进行合并排序操作。

结合第二方面，在第一种可能的实现方式中，所述获取模块具体用于以预设时间间隔获取相邻两级之间键值相似度最高的一对排序字符串表。

结合第二方面，在第二种可能的实现方式中，所述获取模块具体用于判断所述相邻两级中的上一级存储的数据大小是否超过预设阈值；当所述相邻两级中的上一级存储的数据大小超过预设阈值时，则获取相邻两级之间键值相似度最高的一对排序字符串表。

结合第二方面或第一种可能的实现方式或第二种可能的实现方式，在第三种可能的实现方式中，所述处理模块具体用于从所述一对排序字符串表的相同的键值中确定旧版本的键值；将所述旧版本的键值删除；对删除所述旧版本之后的所述一对排序字符串表中的各键值进行排序。

本发明实施例提供的LSM数据合并排序方法和装置，通过利用相邻两级之间SSTable的相似度，对相邻两级中键值相似度最高的一对SSTable进行合并排序操作，因为，键值相似度最高的一对SSTable内存在相同的键值最多，也就是存在键值的旧版本最多，因此，根据键值相似度确定进行合并排序操作的SSTable，能够最早最多的删除旧版本的键值，避免旧版本的键值在存储设备中存储较长时间，占用存储空间，从而，提高存储空间的利用率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明的LSM存储结构示意图；

图2为本发明LSM数据合并排序方法实施例一的流程示意图；

图3为本发明LSM数据合并排序方法实施例二的流程示意图；

图4为本发明LSM数据合并排序装置实施例一的结构示意图；

图5为本发明LSM数据合并排序装置实施例二的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

LSM通常有7级，如图1所示，图1为本发明的LSM存储结构示意图，自上而下将每级分别标记为Li，其中，0≤i≤6，从第0级到第6级每级的存储空间大小呈递增趋势，也就是，第0级的存储空间最小，第6级的存储空间最大；通常，第0级设置在内存中，也是数据最开始写入的一级，其他各级设置在磁盘中；根据键值将每级划分为多个键范围，例如：每级划分为 3个范围，分别为K1-K100，K101-K200，K201-K300，当有键值存入时，存到相应的键值范围内，例如：K15存在K1-K100的键范围内，并且，同一键范围内的键值按序排列；为了便于进行合并排序操作，通常，每级的键范围划分方式相同，例如：L0划分为K1-K100、K101-K200、K201-K300；L1～L6 也划分为K1-K100、K101-K200、K201-K300。

当某级存储的数据大小超过预设阈值时，为了便于描述，将存储的数据大小超过预设阈值的一级称为“待操作级”，将待操作级中的某个键范围内的SSTable与待操作级的下一级的同一键范围内的SSTable进行合并排序 (compact)操作；例如：待操作级为L2，待操作级的下一级则为L3，合并排序操作具体为：按照轮询规则确定L2级中待合并的键范围的SSTable，例如为K1-K100的SSTable，则从L3中获取K1-K100的SSTable，在L2的存储空间中，将L2中的K1-K100的SSTable与L3中的K1-K100的SSTable中进行合并排序操作，具体是，从相同的键值中确定一个最新版本，删除所有旧版本，实现对键值的压缩，然后，对各键值进行排序，将压缩排序之后的键值写入到L3的K1-K100的SSTable中。其中，在相同的键值中确定一个最新版本可以根据键值的编号进行确定，上述键值的编号是按照键值存储到存储设备(L0)的先后顺序编排的，通常，存入越晚，编号越大，因此，通常确定相同的键值中编号最大的为最新版本。

然而，采用上述方法，不能尽早的删除相同的键值中旧版本，旧版本的键值可能会经过多次合并排序操作与新版本的键值层级相距越来越大，因此，新版本的键值要经过多次合并排序操作之后，才能与旧版本的键值进行合并排序，将旧版本的键值删除，因此，相同的键值中旧版本的键值会在存储设备中存在较长时间，会造成存储空间利用率不高。

为了解决上述问题，本发明对合并排序操作的调度策略进行了改进，对相邻级之间相同的键范围之间SSTable的相似度进行比较，优先调度键值相似度最高的SSTable进行合并排序操作。键值相似度越高，说明相同的键值越多，从而，实现在最早的时间删除最多的相同的键值中旧版本，从而提高存储空间的利用率。

下面以具体地实施例对本发明的技术方案进行详细说明。下面这几个具体的实施例可以相互结合，对于相同或相似的概念或过程可能在某些实施例不再赘述。

图2为本发明LSM数据合并排序方法实施例一的流程示意图，如图1所示，本实施例的方法包括：

S201：获取相邻两级之间键值相似度最高的一对排序字符串表。

例如：L1中的K1-K100的SSTable与L2中的K1-K100的SSTable有80％的键值相同，L1中的K101-K200的SSTable与L2中的K101-K200的SSTable 中有20％的键值相同，L1中的K201-K300的SSTable与L2中的K201-K300 的SSTable中有10％的键值相同，则认为L1和L2两级中键值相似度最高的一对SSTable为L1中K1-K100的SSTable和L2中K1-K100的SSTable。

相邻两级之间相似度越高的一对SSTable，说明一对SSTable中相同的键值越多，则存在的旧版本越多。

S202：对上述一对排序字符串表进行合并排序操作。

具体地。从上述一对排序字符串表的相同的键值中确定旧版本的键值；将上述旧版本的键值删除；对删除上述旧版本之后的一对排序字符串表中的各键值进行排序。

接着S201中的例子进行描述，由于L1和L2两级之间键值相似度最高的一对SSTable为L1中K1-K100的SSTable和L2中K1-K100的SSTable则对L1中的K1-K100中的SSTable和L2中的K1-K100的SSTable进行合并排序操作；假设，L1中的K1-K100的SSTable为：K1、K10、K21、K30、K40、 K45、K46、K47、K78、K90；L2中的K1-K100的SSTable为：K1、K10、K21、K45、K46、K47、K78、K90、K92、K93；则对一对SSTable进行合并排序操作具体为：将L2中的K1-K100的SSTable读取到L1中，与L1中的 K1-K200中的SSTable进行合并，由于L2中的K1-K100中的SSTable的K1、 K10、K21、K45、K46、K47、K78、K90与L1中的相比较，为旧版本，因此，删除L2中的K1-K100的SSTable的K1、K10、K21、K45、K46、K47、 K78、K90，将L2中的K1-K100的SSTable剩余的键值K92、K93与L1中的 K1-K100的SSTable的K1、K10、K21、K30、K40、K45、K46、K47、K78、 K90进行排序，排序后的SSTable为K1、K10、K21、K30、K40、K45、K46、K47、K78、K90、K92、K93；然后，将排序后的SSTable从L1中写入到L2 中K1-K100的键范围内，从而，完成一次合并排序操作。

本发明实施例，通过利用相邻两级之间SSTable的相似度，对相邻两级中键值相似度最高的一对SSTable进行合并排序操作，因为，键值相似度最高的一对SSTable内存在相同的键值最多，也就是存在键值的旧版本最多，因此，根据键值相似度确定进行合并排序操作的SSTable，能够最早最多的删除旧版本的键值，避免旧版本的键值在存储设备中存储较长时间，占用存储空间，从而，提高存储空间的利用率。

在上述实施例中，具体在什么时间获取相邻两级之间键值相似度最高的一对SSTable包括但不限于以下几种实现方式：

第一种实现方式：可以以预设时间间隔获取相邻两级之间键值相似度最高的一对SSTable；例如：每隔10秒钟对相邻两级中键值相似度最高的一对 SSTable进行合并排序操作。预设时间间隔的具体长短，可依据实际应用情况进行设置。

第二种实现方式：可以是判断相邻两级的上一级存储的数据大小是否超过预设阈值，当相邻两级中的上一级存储的数据大小超过预设阈值时，获取相邻两级之间键值相似度最高的一对SSTable，本发明所描述的相邻两级中的上一级是指两级中存储空间小的那一级，例如：L1和L2中的上一级是指L1， L2和L3中的上一级是指L2，L3和L4中的上一级是指L3，对此，不再一一列举；现有技术中，是当超过阈值时，根据轮询规则确定进行合并排序操作的SSTable，例如：上一次合并排序的是K1-K100键范围的SSTable，则这次合并排序的是K101-K200键范围的SSTable。与现有技术相比，显然，本发明的实现方式根据键值相似度确定的进行合并排序的SSTable在很大概率上比根据轮询规则确定的SSTable，能够删除更多的旧版本的键值，能够提高存储空间的利用率。

在上述实施例中，无论是第一种实现方式还是第二种实现方式，都有可能出现，在两级之间键值相似度最高SSTable包括至少两对，当相似度最高的SSTable包括至少两对时，可以根据每对中处在上一级的SSTable所在键范围的允许磁盘寻道次数(allowedseeks)值的大小，从至少两对SSTable中确定出一对待合并排序的SSTable；其中，允许磁盘寻道次数是指在读的过程中，键范围的命中率，例如：L2中K1-K100的键范围，初始允许磁盘寻道次数值为10，在读的过程中，如读K10，在L2中的K1-K100中没有命中，则允许磁盘寻道次数值减1为9，再一次读的过程中，如读K15，在L2中的K1-K100 中依然没有命中，则允许磁盘寻道次数值继续减1为8，如此操作，不再举例；相似度最高SSTable包括至少两对时，则根据允许磁盘寻道次数确定，确定允许磁盘寻道次数值最小的键范围的SSTable为待合并排序的一对 SSTable；如果允许磁盘寻道次数值初始值为0，每次读的过程中，未命中则加1，则确定允许磁盘寻道次数值最大的键范围的SSTable为待合并排序的 SSTable。如果至少两对SSTable的键值相似度相同，并且每对中处在上一级的SSTable所在的键范围的允许磁盘寻道次数值也相同，则从中随机确定待合并排序的一对SSTable，或者，按照轮询的规则从中确定待合并排序的一对 SSTable，对此本发明不做限制。

本发明获取相邻两级之间键值相似度最高的一对排序字符串表，对所述一对排序字符串表进行合并排序操作的技术方案，可单独使用，也可以与现有的进行合并排序操作的调度条件任意结合使用，对此本发明不做限制，下面给出一个跟现有技术的调度条件结合的实施例，如图3所示：图3为本发明LSM数据合并排序方法实施例二的流程示意图，如图3所示，本实施例的方法包括：

S301：判断是否有不可更改的内存排序字符串表(immutable memtable)，若有，执行S302，若没有，执行S303。

键值存储系统启动后，开始合并排序线程，首先判断设置在内存中的L0 级是否有写满，当其中一个内存排序字符串表写满之后，则将其置为不可更改，并与L1中的键值进行合并排序操作，写入到L1中，由于内存写的速度比磁盘写的速度快，因此，要优先将内存中的键值写入到L1层中，以减缓写暂停。

S302：对上述不可更改的内存排序字符串表与L1级进行合并排序操作。

S303：判断是否存在存储的数据大小是否超过预设阈值的级；若存在，执行S304，若不存在，执行S305。

S304：对存储的数据大小超过预设阈值的级的某个键范围的SSTable与下一级的同一键范围内的SSTable进行合并排序操作。

具体地，可以按照轮询的规则确定将哪个键范围内的SSTable与下一级的同一键范围内的SSTable进行合并排序操作；也可以根据键值相似度确定两级之间相似度最高的一对SSTable进行合并排序操作。优选后者，本发明对此不做限制。

S305：判断是否存在允许磁盘寻道次数值最小的键范围，若存在，执行 S306，若不存在，执行S307。

S306：将允许磁盘寻道次数值最小的键范围的SSTable与下一级的同一键范围内的SSTable进行合并排序操作。

S307：获取相邻两级之间键值相似度最高的一对SSTable。

S308：对上述一对SSTable进行合并排序操作。

S307和S308的具体描述可以参见图2所示实施例的具体描述，在此不再赘述。

本实施例中，通过结合相邻两级之间键值相似度，确定进行合并排序操作的SSTable，能够最早最多的删除旧版本的键值，避免旧版本的键值在存储设备中存储较长时间，占用存储空间，从而，提高存储空间的利用率。

需要说明的是，在上述各实施例中，由于采用本发明的技术方案能够最早最多的删除旧版本的键值，避免旧版本的键值在存储空间中存储较长时间，也避免了与下级进行合并排序操作，从而减少了输入输出(input/output，以下简称：I/O)访问次数。

图4为本发明LSM数据合并排序装置实施例一的结构示意图，如图4所示，本实施例的装置包括获取模块401和处理模块402，其中，获取模块401 用于获取相邻两级之间键值相似度最高的一对排序字符串表；处理模块402 用于对所述一对排序字符串表进行合并排序操作。

在上述实施例中，获取模块401具体用于以预设时间间隔获取相邻两级之间键值相似度最高的一对排序字符串表。

在上述实施例中，所述获取模块401具体用于判断所述相邻两级中的上一级存储的数据大小是否超过预设阈值；当所述相邻两级中的上一级存储的数据大小超过预设阈值时，则获取相邻两级之间键值相似度最高的一对排序字符串表。

在上述实施例中，所述处理模块402具体用于从所述一对排序字符串表的相同的键值中确定旧版本的键值；将所述旧版本的键值删除；对删除所述旧版本之后的所述一对排序字符串表中的各键值进行排序。

上述实施例的装置对应的可用于执行前述方法实施例的技术方案，其实现原理和技术效果类似，在此不再赘述。

图5为本发明LSM数据合并排序装置实施例二的结构示意图，如图5 所示，本实施例的装置至少包括：处理器501、存储器502、通信接口503 和总线504。其中，所述处理器501、所述存储器502和所述通信接口503通过所述总线504通信。

所述存储器502用于存放程序。具体的，程序中可以包括程序代码，所述程序代码包括计算机执行指令。所述存储器502可以为高速RAM存储器，也可以为非易失性存储器(non-volatile memory)，例如至少一个磁盘存储器。

所述处理器501用于执行所述存储器502存储的执行指令，可能为单核或多核CPU，或者为ASIC，或者为被配置成实施本发明实施例的一个或多个集成电路。

所述通信接口503用于与转发设备进行通信。当LSM数据合并排序装置运行时，处理器501运行程序，以执行以下指令：

获取相邻两级之间键值相似度最高的一对排序字符串表；

对所述一对排序字符串表进行合并排序操作。

本发明实施例的装置可以用于执行前述方法实施例的技术方案，其实现原理和技术效果类似，此处不再赘述。

本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims (8)

1.一种LSM数据合并排序方法，其特征在于，包括：

获取相邻两级之间键值相似度最高的一对排序字符串表；所述键值相似度用于指示所述相邻两级中相同键范围内的一对排序字符串表之间的相同键值所占的比例；

对所述一对排序字符串表进行合并排序操作。

2.根据权利要求1所述的方法，其特征在于，所述获取相邻两级之间键值相似度最高的一对排序字符串表，包括：

以预设时间间隔获取相邻两级之间键值相似度最高的一对排序字符串表。

3.根据权利要求1所述的方法，其特征在于，所述获取相邻两级之间键值相似度最高的一对排序字符串表，包括：

判断所述相邻两级中的上一级存储的数据大小是否超过预设阈值；

当所述相邻两级中的上一级存储的数据大小超过预设阈值时，则获取相邻两级之间键值相似度最高的一对排序字符串表。

4.根据权利要求1～3任一项所述的方法，其特征在于，所述对所述一对排序字符串表进行合并排序操作，包括：

从所述一对排序字符串表的相同的键值中确定旧版本的键值；

将所述旧版本的键值删除；

对删除所述旧版本之后的所述一对排序字符串表中的各键值进行排序。

5.一种LSM数据合并排序装置，其特征在于，包括：

获取模块，用于获取相邻两级之间键值相似度最高的一对排序字符串表；所述键值相似度用于指示所述相邻两级中相同键范围内的一对排序字符串表之间的相同键值所占的比例；

处理模块，用于对所述一对排序字符串表进行合并排序操作。

6.根据权利要求5所述的装置，其特征在于，所述获取模块具体用于以预设时间间隔获取相邻两级之间键值相似度最高的一对排序字符串表。

7.根据权利要求5所述的装置，其特征在于，所述获取模块具体用于判断所述相邻两级中的上一级存储的数据大小是否超过预设阈值；当所述相邻两级中的上一级存储的数据大小超过预设阈值时，则获取相邻两级之间键值相似度最高的一对排序字符串表。

8.根据权利要求5～7任一项所述的装置，其特征在于，所述处理模块具体用于从所述一对排序字符串表的相同的键值中确定旧版本的键值；将所述旧版本的键值删除；对删除所述旧版本之后的所述一对排序字符串表中的各键值进行排序。