CN116048396B - 基于日志结构化合并树的数据存储装置和存储控制方法 - Google Patents

Abstract

本公开涉及基于日志结构化合并树的数据存储装置和存储控制方法。所述日志结构化合并树包括存储在至少一个存储介质上的多个SST文件。所述存储控制方法包括：采用所述第一过滤器获得所述查询键匹配的SST文件集；采用所述第二过滤器对SST文件集中的匹配标签进行全局排序，以生成全局标签集；根据全局标签集选择SST文件执行文件IO操作以读取键值对。该存储控制方法根据全局标签集选择SST文件执行文件IO操作，因而可以在数据读取操作中减少文件IO操作的次数，从而提高文件IO效率。

Description

基于日志结构化合并树的数据存储装置和存储控制方法

技术领域

本公开涉及数据存储技术领域，更具体地，涉及基于日志结构化合并树的数据存储装置和存储控制方法。

背景技术

固态硬盘(SSD，即，Solid State Drives的缩写)是采用用固态电子存储芯片制作的存储硬盘，主要由控制器、存储介质和缓存芯片组成。目前最主流的固态硬盘采用闪存存储器(Flash Memory)作为存储介质来存储数据，例如以NAND闪存为例的非易失性存储器。

随着SSD性能的快速提高，在过去几年中SSD也可始广泛地应用于存储服务器上。在采用SSD的存储服务器上，对4KB页面的读写延迟可以小于10微秒。然而，现有的存储引擎，例如RocksDB，采用同步方式执行文件I/O以读取键值对。存储服务器的CPU线程必须等待文件I/O的完成，在操作系统中触发一个上下文切换(context-switch)。与SSD的低延迟相比，操作系统的上下文切换需要更长的时间，因而导致存储性能劣化。

在存储服务器的SSD中，采用数据文件存储海量的数据。例如，有序字符串表(Sorted String Table)是用于存储键值对的数据文件。为了满足高密度存储的需求，在存储服务器上安装大量的SSD，每个SSD可以提供超过100万次的IOPS。

对于单次的数据查询请求，查找结果可能存在于多个SSD的多个SST文件中。如果查找结果存在于多个SST文件中，则现有的数据查询操作需要对多个SST文件进行文件IO操作以读取所有匹配的键值对形成结果集，然后对结果集进行精确匹配才能获得最终的查找结果。因此，该储控制方法需要耗费大量的时间进行多个SST文件的文件IO操作，已经成为影响存储服务器的读写速度的主要瓶颈。

发明内容

鉴于上述问题，本公开的目的在于提供基于日志结构化合并树的数据存储装置和存储控制方法，其中，根据全局标签集选择SST文件执行文件IO操作，因而可以在数据读取操作中减少文件IO操作的次数，从而提高文件IO效率。

根据本公开的第一方面，提供一种基于日志结构化合并树的存储控制方法，所述日志结构化合并树包括存储在至少一个存储介质上的多个SST文件，所述存储控制方法包括：在所述多个SST文件的数据区段中，采用标准化存储单元存储多个键值对；在所述多个SST文件的元数据区段中，建立第一过滤器和第二过滤器；采用所述第一过滤器获得所述查询键匹配的SST文件集；采用所述第二过滤器对SST文件集中的匹配标签进行全局排序，以生成全局标签集；根据全局标签集选择SST文件执行文件IO操作以读取键值对。

优选地，所述第一过滤器为布隆过滤器，所述第二过滤器为标签过滤器。

优选地，所述标签过滤器包括所述多个键值对的标签，所述标签为所述多个键值对的键哈希值。

优选地，所述多个键值对的标签分别占用固定大小的内存空间。

优选地，所述多个键值对的键包括前缀部分和后缀部分，所述多个键值对的标签包括基于所述前缀部分计算出的前缀标签和基于所述后缀部分计算出的后缀标签。

优选地，所述前缀标签和所述后缀标签分别是采用不同的哈希算法进行计算获得的哈希值。

优选地，所述后缀标签是采用保序哈希算法计算的哈希值。

优选地，采用所述第二过滤器对SST文件集中的匹配标签进行全局排序的步骤包括：对所述SST文件集中的SST文件分别进行标签过滤，以获取SST文件的匹配标签集；以及按照后缀标签，对所述SST文件集中的SST文件的所有匹配标签进行全局排序，其中，所述全局标签集中的匹配标签按照所述后缀标签从小到大排序。

优选地，所述匹配标签的前缀标签与所述查询键的前缀标签相等，并且，所述匹配标签的后缀标签大于等于所述查询键的后缀标签。

优选地，根据全局标签集选择SST文件执行文件IO操作的步骤包括：采用遍历所述全局标签集的方式获取最相关键值对的标签；对所述最相关键值对的标签关联的SST文件执行文件IO操作，以读取与所述标签相对应的键值对的数据内容；以及将所述查询键与读取的键值对进行比较以进行查询验证。

优选地，在所述查询验证失败的情形下继续遍历所述全局标签集，在所述查询验证成功的情形下停止遍历所述全局标签集，以及将读取的键值对作为查找结果。

优选地，在所述全局标签集中包括彼此相等的多个匹配标签的情形下，对所述彼此相等的多个匹配标签关联的SST文件执行文件IO操作，以读取所述多个键值对的数据内容，以及根据所述多个键值对的数据内容实现所述多个键值对的键排序。

优选地，在所述多个SST文件的元数据区段中，按照数据桶、数据页和数据片的分级方式索引所述多个SST文件的数据区段中存储的键值对。

优选地，所述多个SST文件的元数据区段分别包括桶元数据区、桶描述符，所述桶描述符用于描述多个数据桶的起始位置和大小。

优选地，所述桶元数据区包括页索引和标签区，在所述标签区中存储所述多个键值对的标签。

优选地，在打开数据库过程中，还包括：将所述数据库的多个SST文件的元数据区段预先加载到内存中。

优选地，在执行文件IO操作以读取键值对的步骤之前，还包括：在内存表和不可变内存表至少之一中查找所述查询键匹配的键值对。将在所述内存表和不可变内存表至少之一中查找的键值对添加至结果集中；将执行文件IO操作以读取的键值对添加至结果集中；以及在所述结果集中取最小值作为查找结果。

根据本公开的第二方面，提供一种数据存储装置，包括：多个SSD存储装置，在所述多个SSD存储装置上存储多个SST文件；处理器和内存，其中，所述处理器用于执行指令以执行以下步骤：在所述多个SST文件的数据区段中，采用标准化存储单元存储多个键值对；在所述多个SST文件的元数据区段中，建立第一过滤器和第二过滤器；采用所述第一过滤器获得所述查询键匹配的SST文件集；采用所述第二过滤器对SST文件集中的匹配标签进行全局排序，以生成全局标签集；根据全局标签集选择SST文件执行文件IO操作以读取键值对。

根据本公开实施例的数据存储系统中，在SST文件中建立双过滤器。第一过滤器例如是SST文件中的布隆过滤器，用于指示所述查询键与所述多个SST文件中的文件匹配关系。第二过滤器例如是SST文件中的标签过滤器，用于实现键值对的文件内定位和键值对的排序。

根据本公开实施例的存储控制方法，在数据读取操作时，根据标签过滤器中的后缀标签对具有相同前缀标签的多个键值对进行排序，可以预先对多个SST文件进行文件筛选，即预先判断对多个SST的哪个文件执行文件IO操作，可以读取最相关的键值对。因此，根据本实施例的存储控制方法可以减少文件IO操作的次数，从而提高文件IO效率。

附图说明

通过以下参照附图对本公开实施例的描述，本公开的上述以及其他目的、特征和优点将更为清楚。

图1示出基于日志结构化合并树的数据存储系统的示意性框图。

图2示出根据现有技术的数据存储系统中SST文件的数据结构示意图。

图3示出根据本公开实施例的数据存储系统中SST文件的数据结构示意图。

图4示出根据本公开实施例的存储控制方法的示意性流程图。

图5示出图4所示存储控制方法中对标签进行全局排序的详细流程图。

图6示出图4所示存储控制方法中对标签进行全局排序后获得的全局标签集的示意图。

图7示出图4所示存储控制方法中根据全局标签集执行文件IO操作的详细流程图。

图8示出根据本公开实施例的数据存储装置的示意性框图。

具体实施方式

以下将参照附图更详细地描述本公开。在各个附图中，相同的元件采用类似的附图标记来表示。为了清楚起见，附图中的各个部分没有按比例绘制。此外，可能未示出某些公知的部分。

以下基于实施例对本公开进行描述，但是本公开并不仅仅限于这些实施例。在下文对本公开的细节描述中，详尽描述了一些特定的细节部分。对本领域技术人员来说没有这些细节部分的描述也可以完全理解本公开。为了避免混淆本公开的实质，公知的方法、过程、流程、元件和电路并没有详细叙述。

图1示出基于日志结构化合并树的数据存储系统的示意性框图。

在大数据存储的数据存储系统中，键值数据库是重要的数据库类型。与传统的关系型数据库相比，键值(key-value)数据库采用键标识数据行，不限于固定的数据表结构，因而可以节省时间和空间开销，并且可以减少磁盘的读写次数和提高读写性能。

键值(key-value)数据库可以采用日志结构化合并树(Log Structured MergeTree，LSM-Tree)来实现。基于日志结构化合并树的数据存储系统包括已有的RocksDB结构或LevelDB结构等。以RocksDB为例，如图1所示，基于日志结构化合并树的数据存储系统包括内存层和持久层。

在内存层中，键值对可以存储在内存表(Memtable)和不可变内存表(ImmutableMemtable)中，二者共同形成在内存中组织与维护数据的结构。在持久层中，键值对按照多个层级存储在数据文件中。持久层例如由硬盘存储装置(例如，Solid-State Disk，即SSD)之类的硬件实现。例如，有序字符串表(Sorted String Table)是用于存储键值对的数据文件。

数据存储系统的内存层和持久层共同维护键值对的数据存储。在写入键值对时，先将键值对存储于内存层，随着内存中的存储空间达到预定值，则将内存数据转入持久层中，形成数据文件。

进一步地，在持久层中，如果L0级的SST文件的数量或大小达到预定阈值，则L0级的SST文件将会进行合并和排序，从而形成L1级的SST文件。进一步地，L1级的SST文件可以合并成L2级的SST文件，从而形成多个层级的SST文件。该SST文件的合并过程也称为压实(Compaction)。

因此，在内存层中存储最新数据，在持久层中，较低层级(例如，L0级)的SST文件中存储相对较新的数据。

参见图1，在接收到数据更新请求(例如put、update、delete操作)时，数据存储系统执行的数据写入过程包括步骤S01至S04。

在步骤S01中，在将数据写入内存缓冲前，将键值对写入前日志，也称为预写式日志(WriteAheadLog，WAL)。

在步骤S02中，将数据写入内存表Memtable。

在步骤S03中，如果内存表Memtable的数据大小达到预定阈值(例如，64MB)，则将内存表Memtable关闭并且转换成不可变内存表Immutable Memtable，同时，创建新的内存表以响应新的数据更新请求。

在步骤S04中，在步骤S03之后，立即发起一个后台任务，将不可变内存表Immutable Memtable中的键值对转存为一个SST文件，写入SSD存储装置中，从而将内存数据写入SST文件形成持久化存储。上述步骤S04的文件转存操作也称为Flush。在Flush之后，系统释放Immutable Memtable占用的资源。

在步骤S05中，将低层级的SST文件压实成高层级的SST文件。例如，在某层级的SST文件的总大小超过预定阈值(每个层级的SST文件阈值可以不同，高层级的SST文件阈值可以是低层级的SST文件阈值的数倍)时，则将该层级的SST文件合并转换为一个SST文件，并且存储为高一层级的SST文件。该文件合并过程也称为压实(Compaction)。

在接收到数据读取操作(例如get操作)时，数据存储系统执行的数据查询过程包括依次访问内存层的内存表Memtable、不可变内存表Immutable Memtable之后，如果未能在内存中匹配到查询键(query key)，则通过内存中维护的SSTable Info Cache定位SST文件，同时使用SST文件对应的过滤器来判断在SST文件中是否存在查询键，若SST文件中存在查询键，则对SST文件进行IO操作以读取文件内容，从而获取匹配的键值对作为查找结果(query result)。在数据读取操作中，可以先从较低层级(例如，L0级)的SST文件中获取查找结果。如果直到最高层级(例如，Ln级)的SST文件中均未匹配数据，则表示不论是内存层还是持久化层均不存在命中的键值对。

上述基于日志结构化合并树的数据存储系统，采用SST文件实现持久化存储。SST文件不仅包含数据本身，而且包含元数据，例如，元数据包括过滤器。SST文件的过滤器用于判断查询键是否匹配SST文件的键集合，例如是，布隆过滤器(Bloom Filter)、商过滤器(Quotient Filters)等。

上述基于日志结构化合并树的数据存储系统，在数据读取操作中可以实现以下的特性：如果在数据存储系统中存在多个匹配数据，则数据读取操作可以先读取到最新的匹配数据。

图2示出根据现有技术的数据存储系统中SST文件的数据结构示意图。

在根据现有技术的数据存储系统中，SST文件包括多个块(Block)。每个块的大小固定，例如配置为与SSD存储装置的页大小相同，例如，4KB。以RocksDB为例，如图2所示，SST文件包括多个数据块Data Block、多个元数据块Meta Block、元数据索引块Meta IndexBock。

SST文件的数据块Data Block用于存储所有的键值对。在每个数据块中，例如，以连续方式存储多个键值对。SST文件的元数据块Meta Blocks用于存储元数据，例如，元数据块Meta Blocks包括基于SST文件中所有的键值对构建的布隆过滤器BF、以及数据块DataBlock的索引键(index key)。SST文件的元数据索引块Meta Index Block用于存储元数据块的索引信息，例如，元数据块的个数、索引块的偏移量、布隆过滤器的偏移量等。

此外，SST文件还包括页脚Footer，其中描述SST文件的额外信息。

在数据读取操作时，一种方式是将SST文件的元数据预先加载到内存中。根据元数据中的布隆过滤器，判断查询键是否匹配SST文件的键集合，然后进行文件IO操作以读取SST文件的数据块。然而，该文件IO操作仅能提供数据块Data Block的粗略文件内定位，使得文件IO效率劣化。

在数据读取操作时，另一种方式是将SST文件的元数据和键值对预先加载到内存中，根据元数据中的布隆过滤器，判断查询键是否匹配SST文件的键集合，以及进行内存数据操作以读取SST文件的数据块。然而，该文件加载方式需要耗费大量的内存空间。由于数据处理系统的内存空间的限制，难以使用单个CPU或单个CPU核的数据处理系统中并行执行多个存储通道的读写操作。

图3示出根据本公开实施例的数据存储系统中SST文件的数据结构示意图。

在根据本公开实施例的数据存储系统中，SST文件包括多个区段(Segment)。如图3所示，SST文件包括数据区段Data Segment、元数据区段Meta Segment、布隆过滤器BF和页脚Footer。在打开数据时，SST文件的元数据区段Meta Segment和布隆过滤器BF可以预先加载到内存中，因而常驻内存。

SST文件的数据区段Data Segment包括多个数据桶Bucket。进一步地，每个数据桶Bucket包括连续的至少一个数据页Page，每个数据页Page包括连续的至少一个数据片Slab。

在本实施例中，数据桶Bucket的大小是不固定的，即，数据桶Bucket与数据页Page的数量成比例，数据页Page和数据片Slab是固定大小的标准化存储单元。优选地，SST文件的数据页Page的大小与SSD存储装置的物理页大小相同，例如，大小为4KB，SST文件的数据片Slab的大小设定为预定值，例如，大小为64B。因此，SST文件的数据页Page和数据片Slab的大小是固定的，每个数据页Page可以包括64个数据片Slab。

在本实施例中，在SST文件的数据区段Data Segment中，多个键值对的数据内容不同，因此，多个键值对的存储空间大小也是可变的。在本实施例中，每个键值对的存储空间占用至少一个数据片Slab，并且键值对的存储空间的起始位置与数据片Slab对齐。因此，如果键值对的存储空间占用连续的多个数据片Slab，最后一个数据片Slab可能是未填满的。

SST文件的元数据区段Meta Segment包括桶元数据Bucket Meta Data和桶描述符Bucket Descriptor。对于SST文件的数据区段Data Segment中的每个数据桶Bucket，SST文件的元数据区段Meta Segment块存在着相应的一个桶元数据bkti和一个桶描述符di，其中，i表示第i个数据桶Bucket。

在本实施例中，桶元数据Bucket包括数据桶Bucket中的多个数据页Page的页索引Page Index和多个键值对的标签Tag。桶描述符Bucket Descriptor用于描述相应的数据桶Bucket的起始位置和大小。

页索引Page Index是数据页Page相关的索引结构index struct。对于SST文件的数据区段Data Segment中的多个数据页Page，SST文件的元数据区段Meta Segment均会保留相应的一个index struct存放与页索引Page Index中。

索引结构index struct包括索引键index key、标签偏移tag offset、以及数据片位图slab bitmap。索引键index key为数据页Page中第一个键值对的key(原理上indexkey>＝all keys in page或index key<＝all keys in page即可)，用于二分查找。标签偏移tag offset指向数据页中的第一个键值对对应的标签Tag在标签区中的偏移量offset。数据片位图slab bitmap描述了数据页Page中每一个数据片Slab是否是一个新记录的起点。

在本实施例中，SST文件的元数据区段Meta Segment，按照数据桶Bucket、数据页Page和数据片Slab的分级方式索引所述多个SST文件的数据区段中存储的键值对。如果查询键匹配标签Tag，则基于标签偏移tag offset以及数据片位图slab bitmap可以计算出查询键匹配数据的数据片序号和数据片数量。

在数据读取操作时，可以将SST文件的元数据区段Meta Segment、布隆过滤器BF、以及页脚Footer预先加载到内存中。因此，该文件加载方式无需加载SST文件的全部内容，可以节省大量的内存空间。即使数据处理系统的内存空间存在限制，也可以将多个SST文件的索引数据加载到内存中，在单个CPU或单个CPU核的数据处理系统中也可以并行执行多个存储通道的读写操作。

进一步地，根据SST文件的布隆过滤器BF，判断查询键是否匹配SST文件的键集合。根据元数据区段中的页索引Page Index和标签Tag，基于内存数据操作就可以定位键值对在SST文件中的数据片，从而实现达到数据片精度的准确文件内定位。在文件IO操作中仅需要读取特定数据片Slab相关的内容，因而可以提高文件IO效率。

在本实施例中，SST文件中的多个键值对的键分别包括前缀部分和后缀部分。在SST文件中建立第一过滤器和第二过滤器，第一过滤器例如是SST文件中的布隆过滤器，第二过滤器例如是SST文件中元数据区段中的标签过滤器。其中，布隆过滤器是基于所有键值对的键前缀部分构建的集合，标签过滤器包括所有键值对的标签Tag。布隆过滤器用于指示所述查询键与所述多个SST文件中的文件匹配关系。进一步地，标签过滤器用于实现键值对的文件内定位和键值对的排序。

在SST文件中，元数据区段中的标签区作为标签过滤器，其中，多个键值对的标签Tag分别包括根据键计算出的固定长度的两个哈希值(例如，大小分别为1B)。将键的前缀部分和后缀部分计算出的哈希值分别称为前缀标签(Prefix Tag)和后缀标签(Suffix Tag)。例如，前缀标签和后缀标签分别是采用标准哈希算法和保序哈希算法(order-preservinghash)获得的键哈希值。相对于标准哈希算法，采用保序哈希算法获得的键哈希值保留了多个键的顺序关系。采用保序哈希算法计算的哈希值，如果xi<xj，则h(xi)<＝h(xj)，即满足“保序性”(order preserving)。

因此，标签Tag中的前缀标签(Prefix Tag)和后缀标签(Suffix Tag)可以共同作为定位标签，用于指示所述查询键匹配的键值对在所述多个SST文件内的数据片定位。进一步地，后缀标签还作为排序标签，用于指示具有相同前缀标签的多个键值对的顺序。如上所述，与查询键相匹配的具有相同前缀标签的多个键值对，既可能存在于同一SST文件中，也可能存在于多个SST文件中。不论多个键值对位于同一SST文件还是多个SST文件中，采用标签Tag中的后缀标签均可以对多个键值对进行顺序。

在数据读取操作时，根据标签过滤器中的后缀标签对具有相同前缀标签的多个键值对进行排序，可以预先对多个SST文件进行文件筛选，即预先判断对多个SST的哪个文件执行文件IO操作，可以读取最相关的键值对。因此，根据本实施例的存储控制方法可以减少文件IO操作的次数，进一步提高文件IO效率。

图4示出根据本公开实施例的存储控制方法的示意性流程图。该存储控制方法包括与数据读取操作相关的多个步骤S11至S18。

在数据存储系统中，数据读取操作包括根据查询键(query key)，依次在数据存储系统的内存层和持久层中进行查找，以获得与查询键相匹配的查找结果(query result)。该查找结果例如是与查询键相匹配的键值对数据。

在步骤S11中，在打开数据库时，将数据存储系统中的所有SST文件的元数据区段和过滤器加载到内存中。

根据本公开实施例的数据存储系统采用标准化存储单元存储键值对，以及采用双过滤器实现查询键在SST文件中的存储单元定位。

在SST文件的元数据区段按照数据桶、数据页和数据片的分级方式索引所述多个SST文件的数据区段中存储的键值对。因此，与直接加载SST文件的数据区段相比，在内存中加载SST文件的元数据区段和布隆过滤器可以显著减小内存空间。

在数据存储系统具有适当的总内存与硬盘总空间配置下，则在内存中足够存下所有SST文件的元数据区段和布隆过滤器。即，在根据本公开实施例的存储控制方法中，将数据存储系统中的所有SST文件的元数据区段和过滤器常驻内存作为索引数据，无需额外从SSD存储介质上读取。

在基于日志结构化合并树的数据存储系统中，数据更新操作包括内存层和持久层的数据写入过程。在动态的数据更新操作中，数据存储系统中的内存层中的内存表Memtable和不可变内存表Immutable Memtable，以及持久层中的SST文件均可能存储键值对。内存表Memtable中的键值对总是最新的数据。因此，在数据读取操作中，依次在内存层中的内存表Memtable和不可变内存表Immutable Memtable、以及持久层中的SST文件中查找键值对。

在步骤S12中，在内存表Memtable中查找键值对。如果查找到匹配的第一键值对，则将第一键值对的数据添加到结果集中。

在步骤S13中，在不可变内存表Immutable Memtable中查找键值对。如果查找到匹配的第二键值对，则将第二键值对的数据添加到结果集中。

在步骤S14中，采用布隆过滤器过滤键值对，以形成匹配查询键的SST文件集A。

根据SST文件的布隆过滤器BF，可以判断查询键是否匹配SST文件的键集合。在该步骤中，遍历所有SST文件，对于每个SST文件，获取常驻内存的布隆过滤器，采用布隆过滤器过滤键值对，即可以判断该SST文件是否可能包含与查询键匹配的键值对。将所有SST文件中的匹配SST文件构建成SST文件集A。

在本实施例中，SST文件中的多个键值对的键分别包括前缀部分和后缀部分。布隆过滤器是基于所有键值对的键前缀部分构建的集合，采用布隆过滤器过滤键值对可以在多个SST文件获得相有相同前缀标签的多个键值对。

在步骤S15中，判断SST文件集是否为空。如果SST文件集不为空，则确认至少一个SST文件可能包含匹配的键值对，继续执行步骤S16。如果SST文件集为空，则确认所有SST文件均不包含匹配的键值对，继续执行步骤S18。

在步骤S16中，根据标签过滤器中的后缀标签，对SST文件集A中所有的匹配标签进行全局排序，以形成全局标签集。

根据SST文件的标签过滤器，可以实现键值对的文件内定位和键值对的排序。在该步骤中，遍历SST文件集A中的所有SST文件，对于每个SST文件，获取常驻内存的标签过滤器，采用标签过滤器中的后缀标签，可以对所有的匹配标签进行全局排序。

在本实施例中，SST文件中的多个键值对的键分别包括前缀部分和后缀部分。布隆过滤器是在多个SST文件获得相有相同前缀标签的多个键值对，根据标签过滤器的后缀标签可以对多个键值对的标签进行全局排序。此处，术语“全局排序”是指对于SST文件集A中的所有SST文件，对多个键值对的标签排序仅取决于多个键值对的后缀标签，与SST文件的顺序无关。进一步地，根据多个键值对的标签排序，可以获得多个键值对的键排序。

在步骤S17中，根据全局标签集执行文件IO操作，将读取的键值对添加至结果集中。

在全局标签集中，经过排序的多个标签按照所述后缀标签从小到大排序，依次表示最相关的键值对至最不相关的键值对。例如，最相关的键值对是与查询键前缀匹配且后缀大于等于查询键后缀的最小键值对。

对于全局标签集的多个标签，对第一个标签相对应的SST文件进行文件IO操作，可以读取最相关的键值对。进一步地，如果查询键与读取的键值对精确匹配，则将第一个标签相对应的键值对作为文件查找结果。

在步骤S17中，在结果集中取最小值作为查找结果。

上述数据查询操作的结果集包括内存表Memtable、不可变内存表ImmutableMemtable、以及SST文件共计三种来源的查找结果。在结果集中取最小值，可以在三种来源的查找结果中进一步获取最相关的键值对。

根据本公开实施例的存储控制方法，在数据读取操作的上述步骤使用预先加载至内存中的双过滤器，其中，第一过滤器是SST文件的布隆过滤器，第二过滤器是SST文件的元数据区段中的标签过滤器。

在上述的数据读取操作中，采用常驻内存的双过滤器，依次进行文件匹配、文件选择和文件IO操作。在文件匹配阶段，根据SST文件的布隆过滤器BF，判断查询键是否匹配SST文件的键集合，从而可以构建查询键匹配的SST文件集。在文件选择阶段，根据元数据区段中的后缀标签实现多个键值对的全局排序，进而在SST文件集中选择最相关的键值对相对应的SST文件执行文件IO操作，因而可以减少文件IO操作的次数。在文件IO操作阶段，根据元数据区段中的前缀标签和后缀标签标签共同实现键值对的文件内定位，基于内存数据操作就可以定位键值对在SST文件中的数据片，从而实现达到数据片精度的准确文件内定位，因而，在文件IO操作期间仅需要读取特定数据片Slab相关的内容，因而可以提高文件IO效率。

图5和图6分别示出图4所示存储控制方法中对标签进行全局排序的详细流程图，以及进行全局排序后获得的全局标签集的示意图。

根据本公开实施例的存储控制方法，在文件匹配阶段，根据SST文件的布隆过滤器，构建查询键匹配的SST文件集A。参见图6，SST文件集A包括SST文件SST1和SST2。

进一步地，在文件选择阶段，根据SST文件的元数据区段中的标签过滤器，对SST文件集A的全部匹配标签进行全局排序。参见图5，该全局排序包括以下的步骤S31至S34。

在步骤S31中，计算查询键的哈希值以获得SST文件中的数据桶的桶序号。

在步骤S32中，对于SST文件集A中的每个SST文件，根据数据桶的桶序号，在SST文件的桶元数据区中的页索引Page Index进行二分查找以获得页序号。

参见图6，在SST文件集A中的SST文件SST1和SST2中，查找到的页序号分别是pg_n和pg_m。

在步骤S33中，对于SST文件集A中的每个SST文件，对数据页中的标签进行过滤，获得相应的匹配标签集Ai。

根据查询键的前缀部分和后缀部分可以计算出查询键的前缀标签和后缀标签，表示为标签<P，S0>，其中，P表示查询键的前缀标签，S0表示查询键的后缀标签。

进一步地，将查询键的标签<P，S0>与数据页中的多个标签进行比较，选择数据页中的匹配标签形成匹配标签集Ai。此处，查询键的匹配标签的前缀标签均等于查询键的前缀标签，查询键的匹配标签的后缀标签均大于等于查询键的后缀标签。

参见图6，对于SST文件集A中的SST文件SST1，在数据页pg_n中，根据标签过滤器获得的匹配标签集A1包括标签<P，S1>、<P，S2>、<P，S4>，其中匹配标签的后缀标签S1、S2、S4均大于等于查询键的后缀标签。对于SST文件集A中的SST文件SST2，在数据页pg_m中，根据标签过滤器获得的匹配标签集A2包括标签<P，S3>、<P，S4>、<P，S5>，其中匹配标签的后缀标签S3、S4、S5均大于等于查询键的后缀标签。

进一步地，SST文件SST1的匹配标签集A1中的标签<P，S1>、<P，S2>、<P，S4>分别表示SST文件SST1的数据区段中的键值对KV1、KV2、KV4。SST文件SST2的匹配标签集A2中的标签<P，S3>、<P，S4>、<P，S5>分别表示SST文件SST2的数据区段中的键值对KV3、KV5、KV6。

在步骤S34中，对于SST文件集A中的所有SST文件，按照后缀标签对所有的匹配标签进行全局排序，以获得全局标签集B。

在本实施例中，全局标签集不仅是所有SST文件的匹配标签集Ai的全集，而且按照后缀标签对所有匹配标签进行全局排序。

参见图6，全局标签集B包括后缀标签重新排序的所有标签及对应文件，依次为：<P，S1>SST1、<P，S2>SST1、<P，S3>SST2、<P，S4>SST1、<P，S4>SST2、<P，S5>SST2。

对于后缀标签彼此不相等的情形，全局标签集B中的标签顺序可以表征键顺序，例如，SST文件SST1的标签<P，S1>小于标签<P，S2>。对于后缀标签彼此相等的情形，全局标签集B中的标签顺序则不能表征键顺序，例如，SST文件SST1的标签<P，S4>等于SST文件SST2的标签<P，S4>，但SST文件SST1的键值对KV4小于SST文件SST2的键值对KV5。

如下文所述，对于后缀标签彼此相等的情形，还需要进行文件IO操作读取SST文件的数据区段中的键值对，才能获得准确的键顺序。

图7示出图4所示存储控制方法中根据全局标签集执行文件IO操作的详细流程图。

根据本公开实施例的存储控制方法，在文件选择阶段，根据SST文件的元数据区段中的标签过滤器，对SST文件集A的全部匹配标签进行全局排序后获得全局标签集B。

进一步地，在文件IO操作阶段，根据全局标签集执行文件IO操作以读取最相关的键值对。参见图，该文件IO操作包括以下的步骤S41至S46。

在步骤S41中，判断全局标签集B是否为空。

如果全局标签集不为空，则执行步骤S42，开始遍历全局标签集B。如果全局标签集B为空，则执行步骤S46，返回的查找结果为在所有SST文件中未找到键值对。

在步骤S42中，获取全局标签集B中的下一个标签。

由于全局标签集B中的多个标签已经进行全局排序，依次表示最相关的键值对至最不相关的键值对。因此，在全局标签集B的遍历过程，第一个标签表示最相关的键值对。

参见图6，在全局标签集B中，第一个标签<P,S1>SST1表示在第一个标签相关联的SST文件SST1中可能存在最相关的键值对。进一步地，执行下文的步骤S43以读取键值对的数据内容进行查询验证。

在步骤S43中，对标签相关联的SST文件进行文件IO操作，以读取键值对的数据内容。

在该步骤中，根据标签可以计算出查询键匹配数据的数据片序号和数据片数量，从而实现达到数据片精度的准确文件内定位。在文件IO操作中仅需要读取特定数据片Slab相关的内容，即可获取键值对的数据内容。

在步骤S44中，判断查询键与读取的键值对是否匹配。

在该步骤中，将查询键与读取的键值对进行比较以进行查询验证。如果验证失败，则返回步骤S41，继续遍历全局标签集B。如果验证成功，则执行步骤S45，返回读取的键值对作为查找结果。

参见图6，在全局标签集B中，如果第一至第三个标签均未能匹配验证，则全局标签集遍历至第四个标签<P,S4>SST1和第五个标签<P,S4>SST2，两个标签彼此相等。此时，多个键值对的标签顺序不能表示键顺序。在上述的步骤S43中，读取SST文件SST1和SST2中相应的键值对的数据内容，仍然可以实现所述多个键值对的键排序。

图8示出根据本公开实施例的数据存储装置的示意性框图。

参见图8为本申请实施例提供的数据存储装置的示意图。数据存储装置10包括处理器11、内存12、SSD存储装置21至23。在SSD存储装置21至23上，按照日志结构化合并树的方式存储多个SST文件。在数据存储装置运行期间，数据存储装置10将计算机可读指令加载至内存12中，并可在处理器11上运行计算机可读指令，例如基于日志结构化合并树的存储控制程序。处理器11执行计算机可读指令时实现上述基于日志结构化合并树的存储控制方法实施例中的步骤。

本领域技术人员可以理解，图8仅仅是数据存储装置10的示例，并不构成对数据存储装置10的限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件，例如数据存储装置10还可以包括输入输出设备、网络接入设备、总线等。

所称处理器11可以是中央处理单元(Central Processing Unit，CPU)，还可以是其他通用处理器、数字信号处理器(Digital Signal Processor，DSP)、专用集成电路(Application Specific Integrated Circuit，ASIC)、现场可编程门阵列(Field-Programmable Gate Array，FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。通用处理器可以是微处理器或者该处理器11也可以是任何常规的处理器等，处理器11是数据存储装置10的控制中心，利用各种接口和线路连接整个数据存储装置10的各个部分。

内存12可用于存储计算机可读指令，处理器11通过运行或执行存储在内存12内的计算机可读指令或模块，以及调用存储在内存12内的数据，实现数据存储装置10的各种功能。内存12可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序(比如声音播放功能、图像播放功能等)等；存储数据区可存储根据数据存储装置10的使用所创建的数据等。此外，内存12可以包括硬盘、内存、插接式硬盘，智能存储卡(Smart Media Card，SMC)，安全数字(Secure Digital，SD)卡，闪存卡(FlashCard)、至少一个磁盘存储器件、闪存器件、只读存储器(Read-Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)或其他非易失性/易失性存储器件。

数据存储装置10集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请实现上述实施例方法中的全部或部分流程，也可以通过计算机可读指令来指令相关的硬件来完成，计算机可读指令可存储于一计算机可读存储介质中，该计算机可读指令在被处理器执行时，可实现上述各个方法实施例的步骤。其中，计算机可读指令包括计算机可读指令代码，计算机可读指令代码可以为源代码形式、对象代码形式、可执行文件或某些中间形式等。计算机可读介质可以包括：能够携带计算机可读指令代码的任何实体或装置、记录介质、U盘、移动硬盘、磁碟、光盘、计算机存储器、只读存储器(ROM)、随机存取存储器(RAM)等。

本实施例还提供一种计算机存储介质，该计算机存储介质中存储有计算机指令，当该计算机指令在电子设备上运行时，使得电子设备执行上述相关方法步骤实现上述实施例中的基于日志结构化合并树的存储控制方法。

本实施例还提供了一种计算机程序产品，当该计算机程序产品在电子设备上运行时，使得电子设备执行上述相关步骤，以实现上述实施例中的基于日志结构化合并树的存储控制方法。

另外，本申请的实施例还提供一种装置，这个装置具体可以是芯片，组件或模块，该装置可包括相连的处理器和存储器；其中，存储器用于存储计算机执行指令，当装置运行时，处理器可执行存储器存储的计算机执行指令，以使芯片执行上述各方法实施例中的基于日志结构化合并树的存储控制方法。

其中，本实施例提供的电子设备、计算机存储介质、计算机程序产品或芯片均用于执行上文所提供的对应的方法，因此，其所能达到的有益效果可参考上文所提供的对应的方法中的有益效果，此处不再赘述。

通过以上的实施方式的描述，所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，仅以上述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能模块完成，即将装置的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。

在本申请所提供的几个实施例中，应该理解到，所揭露的装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，该模块或单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个装置，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

该作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是一个物理单元或多个物理单元，即可以位于一个地方，或者也可以分布到多个不同地方。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

该集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个可读取存储介质中。基于这样的理解，本申请实施例的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该软件产品存储在一个存储介质中，包括若干指令用以使得一个设备(可以是单片机，芯片等)或处理器(processor)执行本申请各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(Read-Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)、磁碟或者光盘等各种可以存储程序代码的介质。

依照本公开的实施例如上文所述，这些实施例并没有详尽叙述所有的细节，也不限制该发明仅为所述的具体实施例。显然，根据以上描述，可作很多的修改和变化。本说明书选取并具体描述这些实施例，是为了更好地解释本公开的原理和实际应用，从而使所属技术领域技术人员能很好地利用本公开以及在本公开基础上的修改使用。本公开仅受权利要求书及其全部范围和等效物的限制。

Claims (18)

1.一种基于日志结构化合并树的存储控制方法，所述日志结构化合并树包括存储在至少一个存储介质上的多个SST文件，所述存储控制方法包括：

在所述多个SST文件的数据区段中，采用标准化存储单元存储多个键值对；

在所述多个SST文件的元数据区段中，建立文件过滤器和标签过滤器；

采用所述文件过滤器获得查询键匹配的SST文件集；

采用所述标签过滤器对SST文件集中的匹配标签进行全局排序，以生成全局标签集；

根据全局标签集选择SST文件执行文件IO操作以读取键值对，

其中，所述标签过滤器包括所述多个键值对的标签，所述多个键值对的键包括前缀部分和后缀部分，所述多个键值对的标签包括基于所述前缀部分计算出的前缀标签和基于所述后缀部分计算出的后缀标签，

根据所述匹配标签的后缀标签对所述匹配标签进行所述全局排序，用于对所述SST文件集中的多个SST文件进行文件筛选。

2.根据权利要求1所述的存储控制方法，其中，所述文件过滤器包括布隆过滤器和商过滤器中的任意一种。

3.根据权利要求2所述的存储控制方法，其中，所述标签为所述多个键值对的键哈希值。

4.根据权利要求3所述的存储控制方法，其中，所述多个键值对的标签分别占用固定大小的内存空间。

5.根据权利要求3所述的存储控制方法，其中，所述前缀标签和所述后缀标签分别是采用不同的哈希算法进行计算获得的哈希值。

6.根据权利要求5所述的存储控制方法，其中，所述后缀标签是采用保序哈希算法计算的哈希值。

7.根据权利要求1所述的存储控制方法，其中，所述全局标签集中的匹配标签按照所述后缀标签从小到大排序。

8.根据权利要求7所述的存储控制方法，其中，所述匹配标签的前缀标签与所述查询键的前缀标签相等，并且，所述匹配标签的后缀标签大于等于所述查询键的后缀标签。

9.根据权利要求1所述的存储控制方法，其中，根据全局标签集选择SST文件执行文件IO操作的步骤包括：

采用遍历所述全局标签集的方式获取最相关键值对的标签；

对所述最相关键值对的标签关联的SST文件执行文件IO操作，以读取与所述标签相对应的键值对的数据内容；以及

将所述查询键与读取的键值对进行比较以进行查询验证。

10.根据权利要求9所述的存储控制方法，其中，在所述查询验证失败的情形下继续遍历所述全局标签集，在所述查询验证成功的情形下停止遍历所述全局标签集，以及将读取的键值对作为查找结果。

11.根据权利要求9所述的存储控制方法，其中，在所述全局标签集中包括彼此相等的多个匹配标签的情形下，对所述彼此相等的多个匹配标签关联的SST文件执行文件IO操作，以读取所述多个键值对的数据内容，以及根据所述多个键值对的数据内容实现所述多个键值对的键排序。

12.根据权利要求1所述的存储控制方法，其中，在所述多个SST文件的元数据区段中，按照数据桶、数据页和数据片的分级方式索引所述多个SST文件的数据区段中存储的键值对。

13.根据权利要求12所述的存储控制方法，其中，所述多个SST文件的元数据区段分别包括桶元数据区、桶描述符，所述桶描述符用于描述多个数据桶的起始位置和大小。

14.根据权利要求13所述的存储控制方法，其中，所述桶元数据区包括页索引和标签区，在所述标签区中存储所述多个键值对的标签。

15.根据权利要求1所述的存储控制方法，在打开数据库过程中，还包括：将所述数据库的多个SST文件的元数据区段预先加载到内存中。

16.根据权利要求1所述的存储控制方法，在执行文件IO操作以读取键值对的步骤之前，还包括：在内存表和不可变内存表至少之一中查找所述查询键匹配的键值对。

17.根据权利要求16所述的存储控制方法，还包括：

将在所述内存表和不可变内存表至少之一中查找的键值对添加至结果集中；

将执行文件IO操作以读取的键值对添加至结果集中；以及

在所述结果集中取最小值作为查找结果。

18.一种数据存储装置，包括：

多个SSD存储装置，在所述多个SSD存储装置上存储多个SST文件；

处理器和内存，

其中，所述处理器用于执行指令以执行以下步骤：

在所述多个SST文件的数据区段中，采用标准化存储单元存储多个键值对；

在所述多个SST文件的元数据区段中，建立文件过滤器和标签过滤器；

采用所述文件过滤器获得查询键匹配的SST文件集；

采用所述标签过滤器对SST文件集中的匹配标签进行全局排序，以生成全局标签集；

根据全局标签集选择SST文件执行文件IO操作以读取键值对，其中，所述标签过滤器包括所述多个键值对的标签，所述多个键值对的键包括前缀部分和后缀部分，所述多个键值对的标签包括基于所述前缀部分计算出的前缀标签和基于所述后缀部分计算出的后缀标签，

根据所述匹配标签的后缀标签对所述匹配标签进行所述全局排序，用于对所述SST文件集中的多个SST文件进行文件筛选。