Data storage device and storage control method based on log-structured merge tree

1 . A storage control method based on a log-structured merge tree, said log-structured merge tree comprising a plurality of SST (Sorted String Table) files stored on at least one storage device, said storage control method comprising:

using continuous data slabs to store a plurality of key-value pairs in data segments of the plurality of SST files, wherein the data segments of the plurality of SST files respectively comprises a plurality of continuous data buckets, and each data bucket comprises a plurality of continuous data page, wherein each of the at least one data page comprises at least one continuous data slab;

establishing, in metadata segment of each the plurality of SST files, a file filter and tag filter;

using the file filter to obtain the plurality of SST files match a query key;

using the tag filter to obtain a location of data slabs that matches the query key; and performing file IO (Input Output) operations on the plurality of SST files matched the query key, to obtain query results, according to the location of the data slabs;

wherein the tag filter includes multiple tags of a multiple key-value pairs, where the multiple tags are hash values of keys of the multiple key-value pairs, and the location of the data slabs includes matching the tags in the tag section to obtain sequence numbers and quantities of the data slabs corresponding to the multiple key-value pairs.

2 . The storage control method according to claim 1 , wherein a size of the data page is equal to a fixed physical page size of a storage device.

3 . The storage control method according to claim 1 , wherein each data slab has a fixed size, order of magnitude smaller than a size of the page and serves as the standardized storage unit.

4 . The storage control method according to claim 3 , wherein a plurality of key-value pairs are respectively stored in the at least one continuous data slab, and the starting positions of the plurality of key-value pairs are aligned to the slab size.

5 . The storage control method according to claim 3 , wherein the file filter is a bloom filter, or a quotient filter.

6 . The storage control method according to claim 5 , wherein the tags of the plurality of key-value pairs respectively occupy memory spaces of a fixed size.

7 . The storage control method according to claim 3 , wherein the key-value pairs stored in the data segments of the plurality of SST files are indexed in a hierarchical manner in the metadata segments of the plurality of SST files according to data buckets, data pages, and data slabs.

8 . The storage control method according to claim 7 , wherein the metadata segments of the plurality of SST files respectively comprise a bucket metadata area and a bucket descriptors area, and bucket descriptors are used to describe start positions and the sizes of a plurality of data buckets.

9 . The storage control method according to claim 8 , wherein the bucket metadata area comprises a page index area and a tag area, and the tags of the plurality of key-value pairs are stored in the tag area.

10 . The storage control method according to claim 5 , wherein the steps of using the tag filter to obtain the location of the data slabs matching the target key comprise:

calculating a hash value of the target key to obtain a bucket ID;

performing a binary search on the page index area in the bucket metadata area to obtain a page ID; and

performing tag matching on the tag area to obtain starting data slab IDs and the quantity of the data slabs.

11 . The storage control method according to claim 1 , further comprises: during the process of opening a database, preloading the metadata segments of the plurality of SST files of the database into the memory.

12 . The storage control method according to claim 1 , before using the target key to match the SST files, further comprises: searching for key-value pairs matching the target key in at least one of a memory table and an immutable memory table.

13 . A data storage device comprising:

a plurality of SSD storage devices, storing a plurality of SST files;

a processor and memory,

wherein, the processor is used to execute instructions to perform the steps of:

using continuous data slabs to store a plurality of key-value pairs, in data segments of the plurality of SST files, wherein the data segments of the plurality of SST files respectively comprises a plurality of continuous data buckets, and each data bucket comprises a plurality of continuous data page, wherein each of the at least one data page comprises at least one continuous data slab;

establishing a file filter and a tag filter, in metadata segments of the plurality of SST files;

obtaining an SST file by using the file filter;

obtaining a location of the data slabs storing the target key using the tag filter; and

performing file IO operations on the matching SST files to obtain the query result, according to the location of the storage units.