CN114741028A - A persistent key-value storage method, device and system based on OCSSD - Google Patents

Abstract

The invention discloses a method, a device and a system for storing persistent key values based on OCSSD, belonging to the field of key value storage, wherein the compact operation comprises the following steps: reading SSTable selected from the L layer and SSTable which is overlapped with the selected SSTable in the L +1 layer in a key value range to a memory, and sequencing key value pairs to obtain an ordered key value pair sequence; identifying the key value pair subsequences in the ordered key value pair sequence which are completely the same as the read original data blocks as reusable data blocks, and organizing the rest key value pairs into data blocks to be written back; for the reusable data blocks, allocating first logical addresses for the reusable data blocks, and mapping the first logical addresses to first physical addresses of the corresponding original data blocks in the OCSSD; and for the data block to be written back, writing the data block into a free second physical address in the L +1 layer, allocating a second logical address to the data block, and mapping the data block to the mapping relation of the second physical address. The invention can effectively reduce the data writing amount in the compact operation process, thereby reducing the influence on the writing performance and the SSD life.

Description

A persistent key-value storage method, device and system based on OCSSD

technical field

The invention belongs to the field of key-value storage, and more particularly, relates to an OCSSD-based persistent key-value storage method, device and system.

Background technique

Persistent key-value (KV) stores are an integral part of modern large-scale storage infrastructure for storing large amounts of unstructured data. A log-structured merge-tree (LSM-tree) is one of the most popular data structures in key-value store implementations because it converts random writes to sequential writes while supporting efficient single-point and range queries. To speed up read operations, the LSM-tree key-value store system keeps key-value pairs in a multi-layered structure. When processing write and update operations, the LSM-tree key-value store system first caches incoming updates in an in-memory buffer and dumps the entire buffer into persistent storage in batches when the buffer is full. The write and update operations of the LSM-tree key-value storage system are additionally written in a log-structured manner, and the old data will not be overwritten by the newly written data. Therefore, LSM-tree key-value storage systems are widely used in large-scale production environments, including Google's BigTable and LevelDB, Facebook's Cassandra and RocksDB, and Twitter's HBase.

LSM-tree key-value storage uses SSTable as a node in the tree structure. SSTable is a storage file on the hard disk, including multiple data blocks, and each data block includes multiple key-value pairs; SSTable stores key-value pairs in an orderly manner. In the tree structure of LSM-tree, the SSTable of level 0 is directly and persistently generated by the Immutable Memtable in memory. Because it has not been merged with other files of the current layer, the key values in the SSTable of level 0 will overlap, and the values of the other layers will overlap. SSTable files are merged from the SSTable files of the current layer and the previous layer, and the key values will not overlap. In LSM-tree, when the amount of key-value pair data in one layer reaches its upper limit, the key-value pair will be merged with the key-value pair data in the next layer, which is called a compaction operation. As shown in Figure 1, this operation is divided into three steps: first, it specifies an SSTable in the Li layer (such as the L2 layer), and then reads out the SSTable in the Li+1 layer with overlapping key value ranges to the memory Second, merge and sort the key-value pairs in the SSTable read into the memory. In this process, the key-value pairs with the same key will be merged, the expired key-value pairs will be discarded, the latest key-value pairs will be retained, and according to the deletion mark Discard the invalid key-value pairs, and rewrite the valid key-value pairs into a new SSTable file according to some sort of key (such as lexicographical sorting); finally, write all SSTables back to Li+1. It can be seen that the compaction operation in the LSM-tree key-value store will introduce a lot of extra I/O, resulting in the problem of I/O amplification.

With the rapid development of NAND flash technology, the low access latency, high bandwidth and low cost of SSD make solid-state disk (SSD) gradually replace HDD in LSM-tree key-value storage. However, due to LSM-tree key-value storage When a large number of write/update operations are received, frequent compaction operations will be triggered. Therefore, LSM-tree key-value storage on SSD has high I/O amplification problems in write-intensive workloads, affecting key-value storage. The write performance of the engine, and additional data writes can also affect the life of the SSD.

SUMMARY OF THE INVENTION

In view of the defects and improvement requirements of the prior art, the present invention provides a persistent key-value storage method, device and system based on OCSSD, the purpose of which is to improve the compaction operation of LSM-tree key-value storage due to high I/O amplification. And the problem that affects the write performance of the key-value storage engine and the life of the SSD.

In order to achieve the above object, according to an aspect of the present invention, a persistent key-value storage method based on OCSSD is provided, which utilizes LSM-tree to organize data, wherein the compaction operation includes the following steps;

Key-value pair sorting steps: The SSTable selected from the L layer and the SSTable in the L+1 layer whose key value range overlaps with the selected SSTable are read from the OCSSD to the memory, and the SSTable read into the memory is read into the memory. Sort the key-value pairs to obtain an ordered sequence of key-value pairs; the data block in the read SSTable is recorded as the original data block; L and L+1 are the layer sequence numbers in the LSM-tree;

Data detection step: Identify the key-value pair subsequence that is exactly the same as the original data block in the ordered key-value pair sequence as reusable data blocks, and organize the remaining key-value pairs into data blocks to be written back;

Remapping step: for the reusable data block, assign a new first logical address to it, obtain the first physical address of the original data block with the same content in the OCSSD, and establish a relationship between the first logical address and the first physical address. Mapping relations;

Write back step: for the data block to be written back, assign a new second logical address to it, write it into the free second physical address in the L+1 layer, and establish a link between the second logical address and the second physical address. Mapping relations.

In the present invention, after the key-value pairs are sorted on the read SSTable by the compaction operation, data detection is performed, and the data blocks with the same content as the read original data blocks are identified from the sorted key-value pairs sequence, as possible Reuse data blocks. For these reusable data blocks, the newly allocated logical address is mapped to the physical address of the original data block directly through data remapping, without writing these reusable data blocks into OCSSD. It can effectively reduce the amount of data written during the compaction operation, thereby reducing the I/O amplification, thereby reducing the impact on the write performance of the key-value storage engine and the life of the SSD.

Further, identify the key-value pair subsequence that is exactly the same as the original data block in the ordered key-value pair sequence as a reusable data block, including:

Use a sliding window with the same size as the data block to slide on the sequence of ordered key-value pairs. After sliding to a position, determine whether there is an original data block that is the same as the key-value pair subsequence in the sliding window. The key-value pair subsequence in the window is identified as a reusable data block, and the sliding window is made to slide to the next position with the size of the data block as the sliding length; if not, the sliding window is made to slide to the next position with the sliding length of 1.

The present invention uses a sliding window to identify reusable data blocks in the sequence of sorted key-value pairs, that is, data blocks with the exact same content as the original data block. There is no need to perform complex hash value calculation in the process, and the management overhead of the hash value is also avoided. Therefore, the present invention can efficiently identify reusable data blocks, and has low computational cost and low computational cost.

Further, the way of judging whether the key-value pair subsequence in the sliding window is the same as the original data block includes:

Compare the key values of the first and last key-value pairs in the sliding window with the key values of the first and last two key-value pairs of the original data block. If the corresponding key values of the two key-value pairs are equal, then judge The subsequence of key-value pairs in the sliding window is the same as the original data block.

Since the key-value pairs in the SSTable are ordered, when the first and last key-value pairs of the ordered key-value pair sequence in the sliding window are different from the first and last key-value pairs of an original data block read from the SSTable When the key-value correspondences are equal, the sequence of the ordered key-value pairs in the sliding window is exactly the same as the key-value pairs in the original data block, and the present invention uses this as the judgment basis, and can further improve the identification efficiency of the reusable data block.

Further, the OCSSD-based persistent key-value storage method provided by the present invention also includes:

Maintain a reference count for each physical address in the OCSSD, which is used to record the count of logical addresses pointing to the physical address;

When the reference count of a physical address is 0, the physical address is invalidated.

Since the present invention is performing the compaction operation process, for the identified reusable data block, the corresponding original data block is still valid, the present invention maintains the reference count for the physical address, and only when the reference technology of a certain physical address is 0 The physical address is invalidated to ensure that the referenced duplicate data will not be invalidated by other deletion operations.

Further, in the data detection step, after identifying the reusable data block, before organizing the remaining key-value pairs into the data blocks to be written back, the method further includes:

Data alignment of reusable data blocks and remaining key-value pairs according to the flash page size.

The present invention aligns the reusable data blocks and other key-value pairs in the sorted ordered key-value pairs according to the size of the flash memory pages, which can avoid the situation of spanning physical pages when the logical page is written, thereby avoiding the misalignment Additional read and write overhead caused.

Further, the size of the data block in the SSTable is the same as the size of the physical page in the OCSSD.

The present invention sets the size of the data block in the SSTable in a manner consistent with the size of the physical page in the OCSSD, which can reduce the extra times of reading and writing flash memory.

Further, the physical blocks of flash memory in the OCSSD are managed by superblocks.

The present invention manages the entire flash memory with a super block, and each write request is sent to each parallel unit in turn, so that the parallelism of the OCSSD can be maximized.

According to another aspect of the present invention, a persistent key-value storage device based on OCSSD is provided, which uses LSM-tree to organize data, including: a key-value pair sorting module and a data detection module implemented in the LSM-tree KV storage engine, And the data remapping module and data write-back module implemented in the host FTL;

The key-value pair sorting module is used to read the SSTable selected from the L layer and the SSTable in the L+1 layer with overlapping key value ranges with the selected SSTable in the compaction operation from the OCSSD. Sort the key-value pairs in the SSTable read into the memory to obtain an ordered sequence of key-value pairs; the data block in the read SSTable is recorded as the original data block; L and L+1 are the layer numbers in the LSM-tree;

The data detection module is used to identify the subsequence of key-value pairs in the sequence of ordered key-value pairs that are exactly the same as the original data block as reusable data blocks, and organize the remaining key-value pairs into data blocks to be written back;

The remapping module is configured to assign a new first logical address to the reusable data block, obtain the first physical address in the OCSSD of the original data block with the same content as the reusable data block, and establish the first logical address to the first physical address. The mapping relationship of the address;

The write-back module is used to assign a new second logical address to the data block to be written back, write the data block to be written back to the second physical address that is free in the L+1 layer, and establish the second logical address to the second physical address. Physical address mapping.

Further, the user-mode file system BlobFS is used in the LSM-tree KV storage engine, and the host FTL uses the user-mode driver SPDK.

The present invention adopts the user-mode file system BlobFS and the user-mode driver SPDK to manage the host-side FTL, shortens the software IO stack, and reduces the host-side delay.

According to another aspect of the present invention, a persistent key-value storage system is provided, including an OCSSD and an OCSSD-based persistent key-value storage device provided by the present invention.

In general, through the above technical solutions conceived by the present invention, the following beneficial effects can be achieved:

(1) In the process of compaction operation, the present invention identifies reusable data blocks from the sorted sequence of key-value pairs, and maps the logical addresses of the reusable data blocks to the original data in OCSSD by means of address remapping. The physical address of the block, instead of writing these reusable data blocks into the OCSSD, can effectively reduce the amount of data written during the compaction operation, thereby reducing the I/O amplification, thereby reducing the write to the key-value storage engine. Impact on performance and SSD life.

(2) The present invention realizes remapping and management of duplicate data by FTL on the host side based on OCSSD, and eliminates the semantic isolation between deduplication and KV storage engine.

(3) The present invention adopts the user-mode file system BlobFS and the user-mode driver SPDK to manage the host-side FTL, shortens the software IO stack, and reduces the host-side delay.

Description of drawings

Figure 1 is a schematic diagram of the execution process of the compaction operation in the existing LSM-tree key-value store;

2 is a flowchart of an OCSSD-based persistent key-value storage method provided in Embodiment 1 of the present invention;

3 is a logical diagram of an OCSSD-based persistent key-value storage method provided in Embodiment 1 of the present invention;

4 is a schematic diagram of a method for identifying a reusable data block provided in Embodiment 1 of the present invention;

5 is a schematic diagram of data alignment provided in Embodiment 1 of the present invention;

6 is a schematic diagram of an address remapping process for a reusable data block provided by Embodiment 1 of the present invention;

Fig. 7 is the IO stack of address remapping provided by Embodiment 1 of the present invention;

8 is a schematic diagram of an OCSSD-based persistent key-value storage device provided by Embodiment 2 of the present invention and a persistent key-value storage system provided by Embodiment 3.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not conflict with each other.

In the present invention, the terms "first", "second" and the like (if present) in the present invention and the accompanying drawings are used to distinguish similar objects, and are not necessarily used to describe a specific order or sequence.

The compaction operation in the LSM-tree key-value storage will introduce a large amount of extra I/O, leading to the problem of I/O amplification, affecting the write performance of the key-value storage engine and the service life of the SSD. In order to improve this problem, the present invention provides A persistent key-value storage method, device and system based on OCSSD, the overall idea of which is: in the process of compaction operation, reusable data blocks are identified, that is, the sorted sequence of key-value pairs is the same as the read data block. Data blocks whose key-value pairs of the original data blocks are exactly the same. For these data blocks, the validity of the original data blocks in the SSD is retained, and these data blocks are not rewritten to the SSD. Compared with the traditional compaction operation, the reduction is effectively reduced. This reduces the amount of data written, thereby improving the problem of write amplification and reducing the impact on SSD life.

Before explaining the technical solutions of the present invention in detail, the related technical terms involved in the present invention are briefly introduced as follows:

FTL (Flash translation layer), that is, the flash memory translation layer, establishes the connection relationship between the flash memory storage medium and the device master, and is used to manage the flash memory storage medium;

OCSSD (Open-Channel SSD), that is, open channel SSD, which opens internal channels and implements FTL on the host side;

SDPK (Storage Performance Development Kit) is a user-mode NVMe driver published by Intel; SPDK supports OCSSD and host-side flash conversion layer;

BlobFS, is a simple, flat filesystem that can be mounted and unmounted, and blobs can be accessed via operations such as "open", "read", "stat", and "mmap".

The following are examples.

Example 1:

A persistent key-value storage method based on OCSSD, using LSM-tree to organize data.

Referring to FIG. 2 and FIG. 3, in this embodiment, the compaction operation includes the following steps;

Key-value pair sorting steps: The SSTable selected from the L layer and the SSTable in the L+1 layer whose key value range overlaps with the selected SSTable are read from the OCSSD to the memory, and the SSTable read into the memory is read into the memory. Sort the key-value pairs to obtain an ordered sequence of key-value pairs; the data block in the read SSTable is recorded as the original data block; L and L+1 are the layer sequence numbers in the LSM-tree;

Data detection step: Identify the key-value pair subsequence that is exactly the same as the original data block in the ordered key-value pair sequence as reusable data blocks, and organize the remaining key-value pairs into data blocks to be written back;

Remapping step: for the reusable data block, assign a new first logical address to it, obtain the first physical address of the original data block with the same content in the OCSSD, and establish a relationship between the first logical address and the first physical address. Mapping relations;

Write back step: for the data block to be written back, assign a new second logical address to it, write it into the free second physical address in the L+1 layer, and establish a link between the second logical address and the second physical address. Mapping relations.

In the process of the traditional compaction operation shown in Figure 1, the SSTable of the Li+1 layer that has the key value range overlapping with the selected Li-layer SSTable is selected and merged with the SSTable as the granularity. This is a coarse-grained selection method. , this coarse-grained selection method leads to a large number of key-value pairs that do not overlap with the key-value range of the Li-layer SSTable in the selected SSTable of the Li+1 layer, that is, no key-value pairs. These non-key-value pairs only participate in the sorting, and then Directly writing back to the Li+1 layer causes a large amount of data to be repeatedly written; this cross-layer rewriting will cause a lot of extra I/O, hurting the write performance of the key-value storage engine and the lifespan of the SSD.

As shown in FIG. 3, it is an example of using the steps provided by this embodiment to perform the compaction operation, wherein the selected SSTable is located at the second layer of the LSM-tree; referring to FIG. 3, it can be seen that in this embodiment, through the data detection step and The remapping step will identify the data blocks with the same content as the original data block read from the sorted sequence of key-value pairs as reusable data blocks. The key-value pairs in these reusable data blocks are no key values. Yes, for the identified reusable data blocks, the newly allocated logical address is directly mapped to the physical address of the original data block through data remapping without writing these reusable data blocks into OCSSD;

Comparing the operation process shown in Figure 1 and Figure 3, it can be seen that this embodiment can effectively reduce the amount of data written during the compaction operation, thereby reducing the I/O amplification, thereby reducing the write performance of the key-value storage engine and SSD. impact on lifespan.

In order to efficiently identify reusable data blocks, in this embodiment, a key-value pair subsequence that is exactly the same as the original data block in the ordered key-value pair sequence is identified as a reusable data block, including:

Use a sliding window with the same size as the data block to slide on the sequence of ordered key-value pairs. After sliding to a position, determine whether there is an original data block that is the same as the key-value pair subsequence in the sliding window. The key-value pair subsequence in the window is identified as a reusable data block, and the sliding window is made to slide to the next position with the size of the data block as the sliding length; if not, the sliding window is made to slide to the next position with 1 as the sliding length;

Considering that the key-value pairs in the SSTable are ordered, therefore, when the first and last key-value pairs of the ordered key-value pair sequence in the sliding window are the same as the first and last key-value pairs of an original data block read from the SSTable When the corresponding key-values are equal, the sequence of ordered key-value pairs in the sliding window is exactly the same as the key-value pairs in the original data block. Based on this, this embodiment uses this as a judgment basis to judge the key-value pairs in the sliding window. Whether the subsequence is the same as the original data block, as follows:

Compare the key values of the first and last key-value pairs in the sliding window with the key values of the first and last two key-value pairs of the original data block. If the corresponding key values of the two key-value pairs are equal, then judge The subsequence of key-value pairs in the sliding window is the same as the original data block.

Taking FIG. 4 as an example, the above-mentioned identification process of the reusable data block is further described. As shown in Figure 4, each data block includes four key-value pairs; in the compaction operation, the key values of the four original data blocks read out are D1=(A0, A1, A2, A3), D2=( B0, B1, B2, B3), D3=(A1, A2, A3, A4) and D4=(A5, A6, A7, A8), after merging and sorting key-value pairs, the resulting sequence of ordered key-value pairs for:

(A0, A1, A2, A3, A4, A5, A6, A7, A8, B0, B1, B2, B3);

Use a sliding window of length 4 to slide over the sequence of ordered key-value pairs;

At the initial moment, the key-value pair subsequence in the sliding window is (A0, A1, A2, A3). The key value of the value pair is equal, and the subsequence in the sliding window at this time is identified as a reusable data block;

The sliding window is slid backward by 4 key-value pairs. At this time, the subsequence of key-value pairs in the sliding window is (A4, A5, A6, A7), and there is no original data block identical to it;

Make the sliding window slide backward by 1 key-value pair. At this time, the key-value pair subsequence in the sliding window is (A5, A6, A7, A8), and the key value of the first and last key-value pair of the key-value pair subsequence is The key values of the first and last key-value pairs in the original data block D4 are respectively equal, and the subsequence in the sliding window at this time is identified as a reusable data block;

Make the sliding window slide backward by 4 key-value pairs. At this time, the key-value pair subsequence in the sliding window is (B0, B1, B2, B3), and the key value of the first and last key-value pairs of the key-value pair subsequence The key values of the first and last key-value pairs in the original data block D2 are respectively equal, and the subsequence in the sliding window at this time is identified as a reusable data block.

This embodiment uses a sliding window to identify reusable data blocks in the sorted sequence of key-value pairs, that is, data blocks with exactly the same content as the original data block. Compared with the traditional method based on deduplication, this embodiment There is no need to perform complex hash value calculation in the identification process, and the management overhead of the hash value is also avoided. Therefore, this embodiment can efficiently identify reusable data blocks, and has low computational cost and low computational overhead.

After the reusable data block is detected, this embodiment will further perform data alignment to ensure that the starting offset and length of the reusable data block and the data block to be written back in the new and old SSTables must be based on the size of the flash memory page. aligned;

Figure 5 is an example, the original data blocks read are (A, B, C, E), (G, H, I, J), (R, T, X, Z), (A, C, D, E), (L, M, N, P) and (Q, S, U, Y), after key-value merging and sorting, the sequence of ordered key-value pairs obtained is:

(A, B, C, D, E, G, H, I, J, L, M, N, P, Q, S, U, Y, Z);

The identified reusable data blocks are (G, H, I, J) and (L, M, N, P), respectively. After data alignment is performed according to the flash page size, as shown in Figure 5, the blank position is 0. filling;

Aligning the reusable data blocks and other key-value pairs in the sorted ordered key-value pairs according to the flash page size can avoid the situation of spanning physical pages when writing logical pages, thereby avoiding the misalignment caused by Additional read and write overhead.

After data alignment, for the reusable data block, directly map its logical address to the physical address of the corresponding original data block in the OCSSD; for the data block to be written back, assign a new physical address in the OCSSD, Write the data block to be written back to the physical address, and map the logical address of the data block to be written back to the newly allocated physical address, as shown in Figure 6;

In FIG. 6 , from the logical point of view, the compaction operation in this embodiment is the same as the traditional compaction operation, which will invalidate the original file, that is, the original SSTable, but from the physical point of view, the reusable data will not be targeted. Writeback operation of the block.

Since the original SSTable will be invalidated after the compaction operation is completed, in order to prevent the reusable data blocks from becoming invalid due to other delete operations, this embodiment further maintains a reference count for each physical address in the OCSSD, which is used for record the count of logical addresses pointing to this physical address;

When the reference count of a physical address is 0, the physical address is invalidated.

As a preferred implementation, in this embodiment, the size of the data block in the SSTable is set to be consistent with the size of the physical page in the OCSSD, which can reduce the number of additional reads and writes of the flash memory;

And, use the super block to manage the flash physical blocks in the OCSSD;

In this embodiment, the super block is used to manage the entire flash memory, and multiple physical blocks of the flash memory are organized into one super block, so that each write request is sent to each parallel unit in turn, so that the parallelism of the OCSSD can be maximized;

Optionally, in this embodiment, when the free super blocks are less than 5%, garbage collection is started; specifically, a greedy garbage collection strategy is adopted, and garbage collection is preferentially performed on the super blocks with the most invalid data.

As an optional implementation manner, in this implementation, the user-mode file system BlobFS and the user-mode driver SPDK are used to manage the host-side FTL, so as to realize the above-mentioned various operations; wherein, the IO stack when performing the data remapping step is as shown in the figure As shown in Fig. 7, it can be seen that this embodiment adopts the combination of BlobFS and SPDK, which effectively shortens the software IO stack and reduces the delay on the host side.

Example 2:

An OCSSD-based persistent key-value storage device that utilizes LSM-tree to organize data.

Referring to Figure 8, the key-value storage device includes an LSM-tree KV storage engine and a host FTL, and the LSM-treeKV storage engine implements a key-value pair sorting module and a data detection module, and the host FTL implements a data remapping module and data Write back to the module; where:

The key-value pair sorting module is used to read the SSTable selected from the L layer and the SSTable in the L+1 layer with overlapping key value ranges with the selected SSTable in the compaction operation from the OCSSD. Sort the key-value pairs in the SSTable read into the memory to obtain an ordered sequence of key-value pairs; the data block in the read SSTable is recorded as the original data block; L and L+1 are the layer numbers in the LSM-tree;

The data detection module is used to identify the subsequence of key-value pairs in the sequence of ordered key-value pairs that are exactly the same as the original data block as reusable data blocks, and organize the remaining key-value pairs into data blocks to be written back;

The remapping module is configured to assign a new first logical address to the reusable data block, obtain the first physical address in the OCSSD of the original data block with the same content as the reusable data block, and establish the first logical address to the first physical address. The mapping relationship of the address;

The write-back module is used to assign a new second logical address to the data block to be written back, write the data block to be written back to the second physical address that is free in the L+1 layer, and establish the second logical address to the second physical address. The mapping relationship of physical addresses;

As a preferred implementation, in this embodiment, the user-mode file system BlobFS is used in the LSM-tree KV storage engine, and the host FTL uses the user-mode driver SPDK;

In this embodiment, reference may be made to the description in Embodiment 1 above for the specific implementation of each module, which will not be repeated here.

Example 3:

A persistent key-value storage system, as shown in FIG. 8 , includes an OCSSD and the OCSSD-based persistent key-value storage device provided in Embodiment 2 above.

Those skilled in the art can easily understand that the above are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, etc., All should be included within the protection scope of the present invention.

Claims (10)

1. A persistent key value storage method based on OCSD organizes data by using LSM-tree, and is characterized in that the compact operation comprises the following steps:

key value pair sorting step: reading the SSTable selected from the L layer and the SSTable which is overlapped with the selected SSTable in the L +1 layer in the key value range from the OCSSD to a memory, and sequencing the key value pairs in the SSTable read into the memory to obtain an ordered key value pair sequence; the read data blocks in the SSTable are marked as original data blocks; l and L +1 are layer serial numbers in the LSM-tree;

a data detection step: identifying key value pair subsequences which are completely the same as the original data blocks in the ordered key value pair sequences as reusable data blocks, and organizing the rest key value pairs into data blocks to be written back;

a remapping step: for the reusable data block, allocating a new first logical address to the reusable data block, obtaining a first physical address of an original data block with the same content in the OCSSD, and establishing a mapping relation from the first logical address to the first physical address;

a write-back step: and for the data block to be written back, allocating a new second logical address to the data block to be written back, writing the new second logical address into a free second physical address in the L + 1-th layer, and establishing a mapping relation from the second logical address to the second physical address.

2. The OCSSD-based persistent key value storage method of claim 1, wherein identifying a pair sequence of key value pairs in the ordered sequence of key value pairs that is identical to an original data block as a reusable data block comprises:

sliding the ordered key value pair sequences by using a sliding window with the same size as the data blocks, judging whether an original data block which is the same as the key value pair subsequence in the sliding window exists after the original data block slides to one position, if so, identifying the key value pair subsequence in the sliding window as a reusable data block, and sliding the sliding window to the next position by using the size of the data block as the sliding length; if not, the sliding window is made to slide to the next position by taking 1 as the sliding length.

3. The OCSSD-based persistent key value storage method of claim 2, wherein the manner of determining whether the key value pair subsequence in the sliding window is the same as the original data block comprises:

and comparing the key values of the head and tail key value pairs in the sliding window with the key values of the head and tail key value pairs of the original data block respectively, and if the key values of the two key value pairs are correspondingly equal, judging that the key value pair subsequence in the sliding window is the same as the original data block.

4. The ocsd-based persistent key value storage method of claim 1, further comprising:

maintaining a reference count for each physical address in the OCSSD for recording a count of logical addresses pointing to the physical address;

when the reference count of a certain physical address is 0, the physical address is set to be invalid.

5. The OCSSD-based persistent key value storage method according to any one of claims 1 to 4, wherein in the data detection step, after identifying the reusable data block and before organizing the remaining key value pairs to be written back to the data block, further comprising:

and performing data alignment on the reusable data blocks and the rest key value pairs according to the size of the flash page.

6. The OCSSD-based persistent key value storage method according to any one of claims 1 to 4, wherein a data block size in SSTable is consistent with a physical page size in the OCSSD.

7. The OCSSD-based persistent key value storage method according to any one of claims 1 to 4, wherein a flash memory physical block in the OCSSD is managed by using a super block.

8. An OCSD-based persistent key value storage device that organizes data using an LSM-tree, comprising: the system comprises a key value pair sorting module and a data detection module which are realized in an LSM-tree KV storage engine, and a data remapping module and a data write-back module which are realized in a host FTL;

the key value pair sequencing module is used for reading the SSTable selected from the L layer and the SSTable with the key value range overlapping with the selected SSTable in the L +1 layer from the OCSSD to the memory in the compact operation, and sequencing the key value pairs in the SSTable read into the memory to obtain an ordered key value pair sequence; the read data blocks in the SSTable are marked as original data blocks; l and L +1 are layer serial numbers in the LSM-tree;

the data detection module is used for identifying the key value pair subsequences which are completely the same as the original data blocks in the ordered key value pair sequences as reusable data blocks and organizing the rest key value pairs into data blocks to be written back;

the remapping module is configured to allocate a new first logical address to the reusable data block, obtain a first physical address of an original data block having the same content as the reusable data block in the ocsd, and establish a mapping relationship between the first logical address and the first physical address;

the write-back module is configured to allocate a new second logical address to the data block to be written back, write the data block to be written back into a free second physical address in the L +1 th layer, and establish a mapping relationship between the second logical address and the second physical address.

9. The ocsd-based persistent key-value storage device of claim 8, wherein a user-state file system blob fs is employed in the LSM-tree KV storage engine, and the host FTL employs a user-state driver SPDK.

10. A persistent key-value storage system comprising an ocsd and the ocsd-based persistent key-value storage device of claim 8 or 9.

Images