CN112131140B - SSD-based key-value separation storage method supporting efficient storage space management - Google Patents

Abstract

The present invention relates to an SSD-based key-value separation storage method that supports efficient storage space management, including: dividing the value storage space into segments of equal length, constructing a segment manager to manage the invalidation and valid states of all data segments, and providing data for each Create a value storage invalidation offset set and a key storage invalidation offset set for each segment, and perform available segment caching and semi-invalid segment caching. The value storage invalidation offset set is used to record the invalidation value metadata discarded in the compression operation of the key storage , space reclamation with auxiliary value storage; the key storage invalidation offset set is used to record the offsets in the reclaimed data segment that still exist in the key storage after passive garbage collection, these locations do not need to be recycled, so if the key storage These offsets are collected in , and discarded directly. The present invention builds an efficient value storage space manager by collecting the invalid key-value pairs discarded in the downward compression operation in the key storage part, realizes light garbage collection operation, and further reduces the GC operation in the value storage to the foreground write operation of the system Impact.

Description

SSD-based key-value separation storage method supporting efficient storage space management

technical field

The invention belongs to a computer storage system, and in particular relates to an SSD-based key-value separation storage method supporting efficient storage space management.

Background technique

Persistent key-value stores play a vital role in modern data-intensive storage systems and applications, such as messaging, e-commerce, search indexing, and advertising. Log-structured merge tree (LSM-tree) is a disk-based write-optimized data structure proposed in 1996. It obtains considerable write performance by converting random writes into sequential writes, and guarantees Data is ordered to provide reliable query performance, which is currently one of the data structures used by mainstream persistent key-value storage. Since Google published a paper on the distributed key-value storage system Bigtable in 2006, and subsequently open-sourced the stand-alone key-value storage engine LevelDB, Facebook has optimized it based on LevelDB and proposed an open-source stand-alone key-value storage engine RocksDB. The Hadoop ecosystem is also based on Bigtable implements HBase open source.

The key-value storage system based on LSM-tree is composed of memory components and disk components as a whole, and the data in the two components are in order. The written data is first cached in the memory component. When the data volume of the memory component reaches a certain threshold, the data is persisted to the disk component in batches, and merged and sorted with the data covered by the key range in the disk component. This operation is called Compression. The compression operation merges and sorts the data, and reclaims invalid space while ensuring the order of the data. As the amount of data grows, LSM-tree-based key-value storage systems require a large number of compression operations to maintain data organization and thus provide good query performance. In order to amortize the overhead of compression operations, modern LSM-tree-based key-value storage systems design disk components into a multi-layer structure. However, a large number of compaction operations will seriously affect the system's write performance and cause severe write amplification. Write amplification is defined as the ratio of the total amount of written data performed to the amount of data actually written in the key-value store. Therefore, there have been a large number of optimized LSM-tree-based key-value storage systems, such as HyperLevelDB, bLSM, LSM-trie, Wisckey, TRIAD, PebblesDB, SILK, etc.

Wisckey is a persistent key-value storage system with key-value separation, including two parts: value storage and key storage. Value storage is a reusable log for storing key-value pair data; key storage is an LSM-tree-based key-value storage system for storing data indexes. Wisckey is an SSD-optimized data layout, suitable for application scenarios with large values. It avoids severe write performance impact and write amplification caused by compression operations through key-value separation. When the value storage space is exhausted, Wisckey needs to reclaim the value storage space and reclaim the available space by eliminating invalid data. This operation is called garbage collection. The specific steps of the garbage collection operation are 1) read batches of data continuously in the value storage, 2) look up the keys of these data one by one in the key storage, and judge the validity of the data, 3) rewrite the valid data into the value storage, 4 ) to update the index data to the key store. Garbage collection operations are very expensive, and in a write-intensive environment, frequent garbage collections will cause severe write performance degradation and a large amount of data rewriting.

Contents of the invention

The purpose of the present invention is to provide an SSD-based key-value separation storage method supporting efficient storage space management, which is used to solve the problem of bad influence of garbage on system writing performance in the prior art.

The present invention is an SSD-based key-value separation storage method that supports efficient storage space management, which includes: dividing the value storage space into segments of equal length, and constructing a segment manager to manage the invalidation and valid states of all data segments, for Each segment establishes a value storage invalidation offset set and a key storage invalidation offset set. There are three types of segments in the value storage space, namely: full invalid segment, partial invalid segment and valid segment; All data is invalid data; the partial invalidation segment indicates that part of the data in the segment is invalid data; the valid segment indicates that all data in the segment is valid data; the available segment cache and the semi-invalid segment cache are performed, and the available segment cache It is used to cache the starting offset of the full invalidation segment and the starting offset of the segment whose space has been reclaimed after the passive garbage collection, and the semi-invalid segment cache is used to cache invalid data to account for the data in the segment For the partially invalid segments that are half or more of the total amount, the value storage offset valid bitmap is used to mark the validity of the data in the data segment in the value storage; the key storage offset valid bitmap is used to mark passive garbage collection Finally, the position of the data segment originally marked as valid data is judged to be a recovered position when collecting the discarded invalidation offset in the key storage.

According to an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention, the segment size is aligned with the page size of the file system and is larger than the size of a single key-value pair.

According to an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention, for the invalidation offset, the offset of invalidated data in the value storage is continuously collected from the compression operation of the key storage.

According to an embodiment of the SSD-based key-value separation storage method supporting high-efficiency storage space management of the present invention, it is divided into active garbage collection and passive garbage collection according to the segment state and value storage space usage state; the active garbage collection Including: when brushing the data in the cache into the SSD, if there is the full failure segment, then writing the data in the cache into the full failure segment; the passive garbage collection includes: when the value storage space is used up Finally, the space reclamation operation is triggered, the batch data segment is selected, the validity of the data is judged by matching the key and offset in the segment with the key-value pair in the key storage, the invalid data is discarded, and the valid data is rewritten into the value In the storage, write the key and new offset of the rewritten data into the key storage, and put the starting offset of the reclaimed segment into the available segment cache.

According to an embodiment of the SSD-based key-value separation storage method supporting high-efficiency storage space management of the present invention, the value storage space is divided into a main data area and a reserved data area, and the effective data generated in the passive garbage collection Data is rewritten to the reserved data area; the main data area is used to store new data; the reserved data area is used to store valid data generated in passive garbage collection.

According to an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention, the main data area needs to be larger than the reserved data area. According to an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention, the main data area needs to be larger than the reserved data area.

According to an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention, wherein the segment manager records the validity state metadata of the data segment in the value storage, so that it can be obtained when the storage system is restored The state of the segment, which periodically persists metadata from the segment manager to disk.

According to an embodiment of the SSD-based key-value separation storage method supporting high-efficiency storage space management of the present invention, the segment state log records the full invalidation segment offset, the half-invalid segment offset and the value storage invalidation offset set, each time Set of offsets and keystore invalidation offsets for segments after passive garbage collection.

According to an embodiment of the SSD-based key-value separation storage method supporting high-efficiency storage space management of the present invention, the discarded invalid key-value pairs are collected from the compression operation in the key storage, and the invalid data in the value storage is extracted therefrom. Offset and length, through the offset and segment granularity, and the segment granularity of the offset percentage, the starting offset and intra-segment offset of the segment to which it belongs are obtained, and the intra-segment offset and length are combined into invalid offset data and inserted into the The value of the segment stores the set of invalidation offsets.

According to an embodiment of the SSD-based key-value separation storage method supporting high-efficiency storage space management of the present invention, when the data in the write cache is flushed back to value storage, the judgment of the write position includes: if the segment in the segment cache is available If the total capacity is greater than the size of the write cache, select the candidate segment, obtain the starting offset, and flush the write cache data back to the candidate segment; if there is no available segment, obtain the write location in the main data area, if the location is not the main data At the end of the area, write to this location; otherwise, a passive garbage collection operation is triggered. After the space recovery is completed, the candidate segment is selected, the starting offset is obtained, and the write cache data is flushed back to the candidate segment.

The present invention provides an SSD-based key-value separation storage method that supports efficient storage space management, and constructs an efficient value storage space management by collecting invalid key-value pairs discarded in the downward compression operation (Compaction) in the key storage part The device implements lightweight garbage collection (Garbage Collection, GC) operations, and further reduces the impact of GC operations in value storage on foreground write operations in the system. In the key store, the value of the key-value pair discarded in the Compaction operation is the offset of the invalid data in the value store. In order to effectively utilize the collected invalidation offsets, the value storage space is divided into segments of equal length, the invalidation offsets are managed in units of segments, and the GC operation of the value storage space is performed in units of segments. The present invention can improve write performance and reduce write amplification under the workload that triggers intensive GC.

Description of drawings

Figure 1 is the system architecture and read/write flowchart of Wisckey;

Figure 2 is a prototype architecture diagram of SRKV;

Figure 3 is an organizational chart of the value storage space;

Figure 4 is a diagram of the passive garbage collection operation process;

Figure 5 is an example diagram of the change of the value storage invalidation offset set and the key storage invalidation offset set of a single segment in the segment manager after two garbage collection operations are performed;

FIG. 6 is a process diagram of judging the writing location of write cache data.

Detailed ways

In order to make the purpose, content, and advantages of the present invention clearer, the specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

Wisckey's persistent key-value storage based on LSM-tree, such as LevelDB's compression operation will cause serious read/write amplification and write performance degradation, and proposes a persistent key-value storage system for SSD-optimized key-value separation , suitable for scenarios with large key-value pairs. Wisckey includes two parts: value storage and key storage. Value storage is a reusable log for storing key-value pair data; key storage is an LSM-tree-based key-value storage system for storing data indexes. Figure 1 is the system architecture and read/write flowchart of Wisckey, as shown in Figure 1,

When writing data, first write the data into the value storage, and then write the index data into the key storage. The specific steps are as follows:

Write the data into the write cache. If the write cache is full, first flush the data in the write cache back to the disk, perform steps (2)-(3), and then write the data into the write cache;

Flush the data in the write cache back to the disk, extract the key, offset and length of the data, and generate index data <key, <offset, length>>;

Write the batch index data into the write cache (called Memtable) of the key storage. If the Memtable is full, perform steps (4)-(5). After this step, the system background operation generated by writing data;

If the Memtable is full, convert the Memtable to an immutable Memtable and generate a new Memtable to receive data;

Brush the immutable Memtable back to the first layer of the LSM-tree disk component (called L0 layer), if the number of files in the L0 layer reaches the threshold, the compression operation is triggered, and step (6) is performed;

Select all the files with key range coverage in the L0 layer and the files with the key range coverage in the L1 layer to merge and sort, and write the results back to the L1 layer; if the size of the L1 layer reaches the threshold, the compression operation of the L1 layer is triggered. The lower layer compresses the data.

When reading data, first look up the key in the key storage, obtain the offset and length of the data corresponding to the key, and then read the data in the value storage. The order of searching data in the key storage is: 1) Memtable, 2) immutable Memtable, 3) all files covered by the key range in the L0 layer, and search for these files in the order of new and old, 4) L1 layer and below At most one file covered by a key range exists in the hierarchy. Search the key in order, if found, return its value, including data offset and data length; if not found, return that the key cannot be found.

When the value storage space is exhausted, Wisckey needs to reclaim the value storage space and reclaim the available space by eliminating invalid data. This operation is called garbage collection. The specific steps of the garbage collection operation are as follows:

Continuously read bulk data (eg, 64MB) from the beginning of the garbage collection operation in the value store log;

Find the keys of these data one by one in the key storage, and match the offset of the key in the two storages. If they are the same, it means that the data is valid, and if they are different, it means that the data is invalid;

Rewrite valid data to the start position of write data in the value storage log;

Generate index data for rewritten data, and update index data to key storage in batches.

According to the above method, an embodiment of the SSD-based key-value separation storage method supporting efficient storage space management of the present invention includes:

Segment granularities include:

Divide the storage space of the value storage log into segments of equal length. The segment size should be aligned with the page size of the file system (that is, 4KB), and must be larger than the size of a single key-value pair. In order to adapt to the application environment of variable-length key-value size, set Segment granularity aligns the write cache size (eg 1MB).

Segment metadata includes:

Maintain the metadata information of all segments in memory, including the starting offset of each segment, the number of key-value pairs in the segment, and the failure offset set in the segment;

Collect the invalid key-value pairs discarded by the compression operation in the LSM-tree-based key storage, extract the value from them, obtain the offset and length of the invalid data in the value storage, and obtain the starting offset of the segment according to the data offset, Combines the in-segment offset and length as a failure offset to insert into the failure offset set for that segment.

Active garbage collection includes:

When all data in a segment is invalid, the data is flushed back to the segment in the upcoming write cache flush operation.

Passive garbage collection includes:

When the log space of the value storage is used up, the passive garbage collection operation is triggered, and the recovery space threshold is such as 64MB, and some invalid segments that meet the capacity are selected, and the validity of the data is judged by matching the key-value pairs in the key storage, and rewritten valid data, this will cause two problems: 1) the rewritten data is not aligned with the segment size, therefore, when implementing SRKV, the value storage space should be divided into two parts, one part is used to store new data, that is, the main The data area, the other part is used to store the rewritten data after the passive garbage collection operation, that is, the reserved data area; 2) the index data of these data in the key storage has been invalidated, but has not been discarded yet, in the subsequent compression process will be collected, therefore, when implementing SRKV, it is also necessary to add the failure offset set of the segment in the key storage to the segment metadata. Finally, the index data that generates the rewritten data is written to the key store.

Figure 2 is the prototype architecture diagram of SRKV. As shown in Figure 2, the key-value separation storage architecture of SRKV: 1) A segment manager is added between the key storage and the value storage to maintain the status information of all segments, manage and use segments In order to achieve efficient storage space management; 2) divide the original reusable log into the main data area and the reserved data area; 3) increase the segment status log, and periodically persist the status change of the segment, which is used to restore the segment status when restoring the database .

The specific implementation of SRKV is as follows:

Build a segment manager to maintain and manage the metadata and status of all data segments in the main data area, including segment granularity, segment metadata array, available segment cache, and half-invalid segment cache. According to the capacity of the main data area and the granularity of the segment, the number of segments can be obtained. The metadata of each segment includes the total amount of data in the segment, the value store invalidation offset set, and the key store invalidation offset set.

Fig. 3 is an organizational structure diagram of the value storage space. As shown in Fig. 3, the value storage space is divided into a main data area and a reserved data area. The main data area is used to store new data, which is recycled and reused in units of segments; the reserved data area is used to store valid data generated in passive garbage collection operations, set the head/tail pointers, and write additionally according to the traditional log and recycling space recycling. In order to provide enough time to accumulate failure offsets, the main data area must be larger than the reserved data area, such as dividing the value storage space by 7:3.

The segment status log records the offset of the full invalid segment, the offset of the half invalid segment, and the invalid offset set of the value storage, and the offset of the segment and the invalid offset set of the key storage after each passive garbage collection.

Collect the discarded invalid key-value pairs from the compression operation in the key store, and extract the offset and length of the invalid data in the value store from it, through the hash method: 1) offset/segment granularity, 2) offset% segment granularity , get the start offset and intra-segment offset of the segment to which it belongs, and combine the intra-segment offset and length into invalidation offset data and insert the value of this segment to store the invalidation offset set.

Figure 4 shows the operation process diagram of passive garbage collection. As shown in Figure 4, with the continuous accumulation of invalidation offsets, segments in three states appear in the segment manager: 1) full invalid segment, 2) partially invalid segment , 3) Effective segment. When the number of invalidation offsets in the value storage invalidation offset set of a segment is equal to the total amount of data in the segment, when it is judged as a full invalidation segment, the starting offset of the segment is put into the available segment cache. Wait until the next time the write cache data is flushed back to trigger an active garbage collection operation. When flashing back the write cache data, if it is found that the space in the main data area of the value storage is exhausted, a passive garbage collection operation is triggered, and some invalid segments that meet the recovery space threshold (such as 64MB) are selected from the semi-invalid segment cache; If the capacity is less than the threshold of passive garbage collection, the remaining invalid segments are selected by traversing the segment metadata data; all data in the segment is read and traversed, skipping the positions that appear in the value storage invalidation offset set, and obtaining keys, Intra-segment offset and data length, put the intra-segment offset and length into the key storage invalidation offset set, search the key in the key storage, if the offset and length of the value in the found key-value pair are equal to the value If it is the same in the storage, it is judged that the data is valid; the valid data is rewritten to the end pointer of the reserved data area, and new index data is generated and written into the key storage; the starting offset of the segment after space recovery is placed in Enter the available segment cache and reset its metadata: clear the total amount of data in the segment, and clear the value storage invalidation offset set. Figure 5 is an example diagram of changes in the value storage invalidation offset set and the key storage invalidation offset set of a single segment in the segment manager after two garbage collection operations are performed, as shown in Figure 5 .

Figure 6 is a diagram of the process of judging the write location of write cache data. As shown in Figure 6, the two garbage collection strategies make the refresh operation of the write cache also changed. If the available segment cache is not empty, select the starting point of a segment If there is no available segment, get the write position in the main data area, and if the position is not the end of the main data area, write to this position; otherwise, trigger passive garbage collection operation, in After the space reclamation is completed, select a segment start offset, and flush the data back to this location.

The SRKV database instance recovery process includes:

The key storage adopts LSM-tree-based key-value storage with built-in recovery function;

Value store recovery for normal system exits:

Read all the segment status from the segment status log, keep the latest status of each segment; get the head/tail pointer of the reserved data area from the key storage.

In case of system or equipment failure, the value storage recovery of the system crash:

Read all the segment status from the segment status log, and keep the latest status of each segment; get the last segment operation, if the write cache operation is not completed, read the key in the segment and match the data in the key storage, If it cannot be found and the segment is a full invalid segment, it is considered that the data has not been written back and is lost; if the offset is different, it means that the value is stored as new data, and the index data has not been updated, and the index data update operation is performed; if it is a passive garbage collection operation Not completed, get all candidate blocks, re-run the GC operation, get the head pointer of the reserved data area from the key storage, and write valid data to this location.

The present invention aims at efficient storage space management technology of key-value separation storage in write-intensive environment, especially update-intensive applications, and implements a new key-value separation storage SRKV based on the technology. SRKV adds a segment manager between the existing key-value separation storage architecture that includes key storage and value storage to collect invalidation offsets from the key storage and assist GC in the value storage operate. Based on the segment state, two space recovery strategies, active GC and passive GC, are designed. Since the rewritten data during passive GC cannot be aligned with the segment size, the value storage is divided into the main data area and the reserved data area. The main data area stores new data, and the reserved data area stores the data rewritten after passive GC.

The present invention builds a key-value separation store (Segment-conscious recycled key-value separation store, SRKV) that recycles and reuses the value storage space at the granularity of the data segment. In terms of storage architecture, a segment manager is added between key storage and value storage to collect invalidation offsets from key storage and assist GC operations in value storage; the value storage space is divided into main data areas and reserved Data area to distinguish between storing hot data and rewriting data after garbage collection operations. The present invention can improve write performance and reduce write amplification under the workload that triggers intensive garbage collection operations.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the technical principle of the present invention, some improvements and modifications can also be made. It should also be regarded as the protection scope of the present invention.

Claims (8)

1. The SSD-based key value separation storage method supporting efficient storage space management is characterized by comprising the following steps: dividing a value storage space into equal-length segments, constructing a segment manager to manage failure and valid states of all data segments, and establishing a value storage failure offset set and a key storage failure offset set for each segment, wherein the value storage space has three types of segments which are respectively: full failure section, partial failure section and effective section, wherein the full failure section represents that all data in the section are invalid data; the partial failure section indicates that partial data in the section is invalid data; the effective section indicates that all data in the section are effective data;

performing available segment cache and semi-invalidation segment cache, wherein the available segment cache is used for caching the initial offset of the full invalidation segment and the initial offset of the segment of the reclaimed space after passive garbage reclamation, the semi-invalidation segment cache is used for caching the partial invalidation segment of which the quantity of invalidation data accounts for half or more of the total quantity of data in the segment, and the value storage offset valid bitmap is used for marking the validity of the data in the data segment in the value storage; the key storage offset valid bitmap is used for marking the position of the data segment originally marked as valid data after passive garbage collection, and judging whether the position is a recovered position or not when the invalid offset discarded in the key storage is collected;

wherein,,

according to the segment state and the value storage space use state, the method is divided into active garbage collection and passive garbage collection;

the active garbage collection includes: when the data in the cache is brushed into the SSD, if the full failure section exists, the data in the cache is written into the full failure section;

the passive waste recycling includes: when the value storage space is used up, triggering space recovery operation, selecting batch data segments, judging the validity of data by matching keys and offset in the segments with key value pairs in the key storage, discarding invalid data, rewriting valid data into the value storage, writing the key of the rewritten data and new offset into the key storage, and putting the initial offset of the recovered segments into an available segment cache;

dividing a value storage space into a main data area and a reserved data area, and rewriting effective data generated in the passive garbage collection into the reserved data area; the main data area is used for storing new data; the reserved data area is used for storing effective data generated in passive garbage collection.

2. The SSD-based key value split storage method supporting efficient storage space management of claim 1, wherein a segment size is aligned with a page size of a file system and is larger than a single key value pair size.

3. The SSD-based key value separation storage method supporting efficient storage space management of claim 1, wherein for failure offsets, offsets of failure data in the value store are continuously collected from compression operations of the key store.

4. The SSD-based key value separation storage method supporting efficient storage space management of claim 1, wherein the main data area is larger than the reserved data area.

5. The SSD-based key value separation storage method supporting efficient storage space management of claim 1, wherein validity state metadata of the data segments in the value store is recorded in the segment manager so that the state of the segments can be acquired when the storage system is restored, the metadata in the segment manager being periodically persisted to the disk.

6. The SSD-based key value separation storage method supporting efficient storage space management of claim 1, wherein the segment state log records a full failure segment offset, a half failure segment offset, and a value storage failure offset set, the offset of the post segment and the key storage failure offset set each time passive garbage collection.

7. The SSD-based key value separation storage method supporting efficient storage space management of claim 6, wherein discarded invalid key value pairs are collected from compression operations in the key store, wherein offsets and lengths of invalid data in the value store are extracted therefrom, wherein a starting offset and an intra-segment offset of the segment of interest are obtained by the offsets and the segment granularity, and the segment granularity of the offset percentage, and wherein the intra-segment offsets and the lengths are combined into a value store invalidation offset set in which invalidation offset data is inserted into the segment.

8. The SSD-based key value separation storage method supporting efficient storage space management of claim 1, wherein when the data in the write cache is swished back to the value storage, the determining of the write location includes: if the total capacity of the middle section of the available section buffer is larger than the write buffer, selecting a candidate section, obtaining a starting offset, and brushing write buffer data back to the candidate section; if no segment is available, a writing position is obtained in the main data area, and if the writing position is not at the tail part of the main data area, the writing position is written; otherwise, triggering passive garbage collection operation, selecting a candidate segment after space collection is completed, obtaining initial offset, and brushing write cache data back into the candidate segment.

Images