CN114996275A - Key value storage method based on multi-tree conversion mechanism - Google Patents

Abstract

The invention provides a key value storage method based on a multi-tree conversion mechanism, which specifically comprises the following steps: for the written key value data, firstly storing the key value data into a write skip list, and converting the key value data into a read-only skip list to be inserted into a B + tree in the memory device after the size of the key value data reaches the limit; when the size of the B + tree reaches a certain limit, traversing the key value data according to a heat strategy, and persisting the key value data with low heat to a cold tree 0 layer in the external storage device; if the number of the key value data files in the cold tree layer 0 reaches the size limit, triggering the partition operation of the layer 0; when the key value data in the B + tree execute persistence operation, the 0-layer partition only receives the key value data which accords with a set range; if the key value data in the specific range in the cold tree reaches a certain heat degree, transferring the key value data to a hot tree of the external storage device; while key-value data of low heat in the hot tree will be transferred to the cold tree. The method provided by the invention reduces the read amplification by using the heat strategy, ensures the write-in performance and realizes the integral improvement of the performance of the key value storage system.

Description

A key-value storage method based on multi-tree conversion mechanism

technical field

The invention relates to the field of computer storage, in particular to a key-value storage method based on a multi-tree conversion mechanism.

Background technique

With the advent of the era of big data, data reserves have been increasing, and data characteristics have changed significantly. The proportion of unstructured data has reached 80% of the total data. Under such a trend of data changes, key-value storage is widely used, it has no clear restrictions on the data structure, and has high scalability. At present, some excellent key-value storage products have appeared and are widely used, such as Leveldb used by Chrome browser, Rocksdb further improved by facebook based on Leveldb, Redis and Memcached used by Twitter, etc. The data structures used in the current key-value store mainly include hash structure, B-tree and log-structure merge tree (LSM tree). These three structures have different advantages and disadvantages.

Since the LSM tree-based key-value storage system has good write performance and supports range scanning, many related products have appeared. However, due to the inherent structural characteristics of the LSM tree structure (hierarchical structure in external memory), the maintenance and use of this structure will have a negative impact on the performance of the key-value storage system. Taking Leveldb as an example, first of all, the source of Leveldb's write amplification is mainly data rewriting in the inter-layer merge operation. For example, the size of each layer in Leveldb is 10 times that of the previous layer. When merging a file in layer i to layer i+1, in the worst case, 10 files in layer i+1 need to be read , and then write the data back to the i+1 layer after merge sorting, and the write magnification is as high as 10. In this case, if an SST file is moved from the L0 layer to the L6 layer, the maximum write magnification will reach 50. Secondly, there are two main sources of Leveldb's read amplification. On the one hand, when looking for a key-value pair, Leveldb may need to look up in multiple levels, in the worst case, it needs to find 8 files in L0, and each layer needs to find one file in L1-L6 layers, A total of 14 files need to be searched; on the other hand, when searching for a key-value pair in an SST file, Leveldb needs to read multiple metadata blocks of the file, and the actual data read includes index blocks, bloom filter blocks and data block. For example, when looking for a 1KB key-value pair, Leveldb needs to read a 16KB index block, a 4KB filter block, and a 4KB data block, for a total of 24KB of data. In the worst case, 14 SST files need to be read, so the read magnification will be as high as 336.

SUMMARY OF THE INVENTION

The main purpose of the present invention is to overcome the above-mentioned defects in the prior art, and propose a key-value storage method based on a multi-tree conversion mechanism, which uses a heat strategy to reduce read amplification while ensuring write performance, and realizes the performance of the key-value storage system. Overall improvement.

The present invention adopts following technical scheme:

A key-value storage method based on a multi-tree conversion mechanism, comprising:

For the written key-value data, it is first stored in the write skip table. When the size reaches the limit, it is converted into a read-only skip table and inserted into the B+ tree in the memory device; when the size of the B+ tree reaches a certain limit, the keys are traversed. value data;

Judging according to the heat strategy, the key-value data with low heat will be persisted to the 0th layer of the cold tree in the external storage device, and the key-value data with high heat will continue to remain in the B+ tree;

If the number of key-value data files in layer 0 of the cold tree reaches the size limit, the layer-0 partition operation is triggered, and the layer-0 partition operation is equally divided according to the existing key-value data range in the layer. When the number of key-value data files reaches the size limit, the partition operation is triggered again;

When the low-heat key-value data in the B+ tree performs the persistence operation, the 0-tier partition only receives the key-value data that meets the set range; , then transfer the key-value data in this range to the hot tree of the external memory device, and use the B+ tree in the memory device to index the key-value data in the hot tree;

When the size of the hot tree reaches a certain limit, the key-value data is judged according to the heat policy, and one or more key-value data in the low-heat range are transferred to the cold tree partition, and the indexes of these data are deleted from the B+ tree. .

Specifically, the heat strategy is specifically:

When the key-value data in the read-only skip table is inserted into the B+ tree structure, the insertion time field is saved to judge the popularity of the key-value data;

According to the time field recorded in the node, determine whether the key-value data needs to be kept in the B+ tree, if not, it will be persisted to the cold tree partition of the external storage device;

For the key-value data in the external storage device, the global heat table is used to record the operands of the key-value data. When the merge operation in the cold tree is performed, if the operand of a range unit located in the cold tree reaches the threshold, the All key-value data within this range unit is transferred to the hot tree;

When the hot tree reaches a certain size limit, use the global heat table to perform heat judgment on the key-value data in the hot tree, and judge whether the key-value data in the range needs to be retained in the hot tree according to the range of the key-value data. If no retention is required, the key-value data in these ranges in the hot tree is transferred to the cold tree.

Specifically, it also includes a data reading step, specifically:

S11: First, search for the target data in the cache area, if found, go to step S12; if not, go to step S13;

S12: The system completes the user's read request and sends the read target data to the user;

S13: Find the target key and value type in the B+ tree, if found and the value type is the actual value, go to step S12, if found and the value type is address information, go to step S14; if not found, go to step S15;

S14: Read the target data in the hot tree of the external storage device according to the address obtained in the previous step, and go to step S12;

S15: Search the target data from top to bottom in the cold tree of the external storage device, if found, go to step S12; if not, go to step S16;

S16: The system completes the user's read request and sends the result to the user, but the target data is not found.

Specifically, it also includes a data writing step, specifically:

S21: First write into the skip table structure, if the size limit is reached, go to step S22;

S22: Convert this skip table to a read-only skip table, and create a new write skip table structure for data writing;

S23: If the size of the B+ tree does not reach the limit, go to step S25; if it reaches the limit, go to step S24;

S24: Traverse the key-value data in the B+ tree, and persist the key-value data with lower heat to the cold tree of the external storage device, and go to step S25;

S25: Save the key-value data and the current time in the read-only skip table structure to the B+ tree structure;

S26: The system completes the user's writing request, and sends a successful writing information to the user.

Specifically, the storage structure of the application is as follows:

Write skip table, read-only skip table, B+ tree, and cold tree structure and hot tree structure in disk; wherein the cold tree structure is a 3-layer log structure merge tree, including 0-level log structure, 1-level log structure, 2-level log structure Layer log structure, and the 0-layer log structure has a partition structure; the hot tree structure is a single-layer log structure merge tree.

As can be seen from the above description of the present invention, compared with the prior art, the present invention has the following beneficial effects:

(1) The present invention proposes a key-value storage method based on a multi-tree conversion mechanism, which specifically includes: firstly save the key-value data written in the write-in jump table, and when the size reaches the limit, convert it into a read-only jump table Insert the table into the B+ tree in the memory device; when the size of the B+ tree reaches a certain limit, traverse the key-value data; judge according to the heat policy, and persist the key-value data with low heat to 0 of the cold tree in the external storage device Layer, the hot key-value data will continue to remain in the B+ tree; if the number of key-value data files in the cold tree layer 0 reaches the size limit, the 0-layer partition operation is triggered, and the 0-layer partition operation is based on the existing layer in the layer. The range of key-value data is divided equally. If the number of key-value data files in a partition in layer 0 reaches the size limit, the partition operation will be triggered again; The partition only receives key-value data that meets the set range; if the key-value data in the cold tree reaches a certain degree of popularity after being judged by the heat strategy, the key-value data in this range will be transferred to the hot tree of the external storage device and use the B+ tree in the memory device to index the key-value data in the hot tree; when the size of the hot tree reaches a certain limit, the key-value data is judged according to the heat policy, and one or more keys in the low heat range are The value data is moved to the cold tree partition, and the index of this data is removed from the B+ tree. The method provided by the present invention uses a heat strategy to reduce read amplification, and at the same time ensures the write performance, and realizes the overall improvement of the performance of the key-value storage system.

(2) On the one hand, the present invention determines the persistence operation through the heat strategy, and temporarily keeps the hot data in the memory to avoid additional IO overhead caused by reading from the external storage device; It stores frequently accessed key-value data in the device, accelerates the reading process of key-value data, and improves reading performance.

(3) The present invention uses the B+ tree in the memory to store the address information in the hot tree, and can index all valid data in the hot tree, thereby reducing the number of reads of the hot data, and the B+ tree can ensure a certain range of search performance. By reducing the design of cold tree levels and 0-level partitions, the number of reads of cold data is reduced and read amplification is reduced.

(4) The present invention uses the B+ tree to store hot data, which can avoid multiple persistence operations caused when the key-value data performs an update operation. The inter-layer merge operation of the traditional LSM tree can achieve space reclamation, but it makes the same data repeatedly written. Using the conversion between hot and cold trees to replace the traditional inter-layer merge operation can not only improve the read performance but also reduce the amount of data writing.

Description of drawings

Fig. 1 is a system structure diagram of a key-value storage method based on a multi-tree conversion mechanism;

Fig. 2 is the data reading flow chart of the key-value storage method based on multi-tree conversion mechanism;

FIG. 3 is a data writing flow chart of the key-value storage method based on the multi-tree conversion mechanism.

Detailed ways

The present invention will be further described below through specific embodiments.

Figure 1 is a system structure diagram of a key-value storage method based on a multi-tree conversion mechanism provided by an embodiment of the present invention; the applied storage structure is specifically:

Write skip table, read-only skip table, B+ tree, and cold tree structure and hot tree structure in disk; wherein the cold tree structure is a 3-layer log structure merge tree, including 0-level log structure, 1-level log structure, 2-level log structure Layer log structure, and the 0-layer log structure has a partition structure; the hot tree structure is a single-layer log structure merge tree;

The storage method specifically includes: first saving to the write jump table, when the size reaches the limit, converting it into a read-only jump table and inserting it into the B+ tree in the memory device; when the size of the B+ tree reaches a certain limit, traverse it according to the heat strategy The key-value data to judge;

Persist key-value data with low heat to layer 0 of the cold tree in the external storage device, and key-value data with high heat will continue to remain in the B+ tree;

If the number of key-value data files in the 0th layer of the cold tree reaches the size limit, the data merge operation and the 0th layer partition operation are triggered; the 0th layer partition operation is divided equally according to the existing key value data range in the layer; When the number of key-value data files in a partition reaches the size limit, the data merge operation and partition operation are triggered again;

When the low-heat key-value data in the B+ tree is persisted, the 0-tier partition only receives key-value data that matches its own range. If the key-value data in a certain range in the cold tree reaches a certain degree of heat according to the heat strategy, then all key-value data in this range will be transferred to the hot tree of the external storage device, and the B+ tree in the memory device will be transferred. The insertion key and address information is used to index the key-value data in the hot tree.

When the size of the hot tree reaches a certain limit, the key-value data in it is traversed and judged according to the heat policy, and one or more key-value data in the low-heat range are transferred to the cold tree partition, and these data are deleted from the B+ tree. the index of the data;

Specifically, the heat strategy is specifically:

When the key-value data in the read-only skip table is inserted into the B+ tree structure, the insertion time field is saved to judge the popularity of the key-value data;

According to the time field recorded in the node, determine whether the key-value data needs to be kept in the B+ tree, if not, it will be persisted to the cold tree partition of the external storage device;

For the key-value data in the external storage device, the global heat table is used to record the operands of the key-value data. When the merge operation in the cold tree is performed, if the operand of a range unit located in the cold tree reaches the threshold, the All key-value data within this range unit is transferred to the hot tree;

When the hot tree reaches a certain size limit, use the global heat table to perform heat judgment on the key-value data in the hot tree, and judge whether the key-value data in the range needs to be retained in the hot tree according to the range of the key-value data. If no retention is required, the key-value data in these ranges in the hot tree is transferred to the cold tree.

Figure 2 is a data reading flow chart of the key-value storage method based on the multi-tree conversion mechanism.

101. A read request sent by the user to the system, go to 102.

102. Search for the target data in the buffer area, if found, obtain the target data, go to 103, otherwise go to 104.

103. Return the query result to the user.

104. Search for the target data in the B+ tree, if not found, go to 105, otherwise go to 106.

105. Search for data layer by layer from top to bottom in the cold tree, if found, obtain the target data, go to 103, otherwise, return the result if it does not exist, go to 103.

106. Determine whether the value type is address information, if not, obtain the target data, go to 103, otherwise go to 107.

107. Obtain target data according to the address information found in the previous step, and go to 103.

Figure 3 is a data writing flow chart of the key-value storage method based on the multi-tree conversion mechanism.

201. A write request sent by the user to the system, go to 202.

202. Determine whether the write skip table is full, if not, go to 211, otherwise go to 203.

203. Convert the write skip table to a read-only skip table, and go to 204.

204. Determine whether the size of the buffer area is full, if not, go to 205, otherwise go to 206.

205. Create a new write skip table, go to 202.

206. Determine whether the size of the B+ tree reaches the limit, if so, go to 207, otherwise go to 208.

207. Determine whether the number of files in the cold tree layer 0 partition reaches the limit, if so, go to 209, otherwise go to 210.

208. Insert the read-only skip list into the B+ tree, and go to 204.

209. Perform a merge operation and a partition operation on the 0 layer of the cold tree, and go to 210.

210. Persist the low-heat data in the B+ tree to the cold tree according to the heat strategy, and go to 206.

211. Write data into the write skip table, go to 212.

212. Return the writing result to the user.

(1) The present invention proposes a key-value storage method based on a multi-tree conversion mechanism, which specifically includes: firstly save the key-value data written in the write-in jump table, and when the size reaches the limit, convert it into a read-only jump table Insert the table into the B+ tree in the memory device; when the size of the B+ tree reaches a certain limit, traverse the key-value data; judge according to the heat policy, and persist the key-value data with low heat to 0 of the cold tree in the external storage device Layer, the hot key-value data will continue to remain in the B+ tree; if the number of key-value data files in the cold tree layer 0 reaches the size limit, the 0-layer partition operation is triggered, and the 0-layer partition operation is based on the existing layer in the layer. The range of key-value data is divided equally. If the number of key-value data files in a partition in layer 0 reaches the size limit, the partition operation will be triggered again; The partition only receives key-value data that meets the set range; if the key-value data in the cold tree reaches a certain degree of popularity after being judged by the heat strategy, the key-value data in this range will be transferred to the hot tree of the external storage device and use the B+ tree in the memory device to index the key-value data in the hot tree; when the size of the hot tree reaches a certain limit, the key-value data is judged according to the heat policy, and one or more keys in the low heat range are The value data is moved to the cold tree partition, and the index of this data is removed from the B+ tree. The method provided by the present invention uses a heat strategy to reduce read amplification, and at the same time ensures the write performance, and realizes the overall improvement of the performance of the key-value storage system.

(2) On the one hand, the present invention determines the persistence operation through the heat strategy, and temporarily keeps the hot data in the memory to avoid additional IO overhead caused by reading from the external storage device; It stores frequently accessed key-value data in the device, accelerates the reading process of key-value data, and improves reading performance.

(3) The present invention uses the B+ tree in the memory to store the address information in the hot tree, and can index all valid data in the hot tree, thereby reducing the number of reads of the hot data, and the B+ tree can ensure a certain range of search performance. By reducing the design of cold tree levels and 0-level partitions, the number of reads of cold data is reduced and read amplification is reduced.

(4) The present invention uses the B+ tree to store hot data, which can avoid multiple persistence operations caused when the key-value data performs an update operation. The inter-layer merge operation of the traditional LSM tree can achieve space reclamation, but it makes the same data repeatedly written. Using the conversion between hot and cold trees to replace the traditional inter-layer merge operation can not only improve the read performance but also reduce the amount of data writing.

The above are only specific embodiments of the present invention, but the design concept of the present invention is not limited to this, and any non-substantial modification of the present invention by using this concept should be regarded as an act of infringing the protection scope of the present invention.

Claims (5)

1. a key-value storage method based on multi-tree conversion mechanism, is characterized in that, comprises: For the written key-value data, it is first stored in the write skip table. When the size reaches the limit, it is converted into a read-only skip table and inserted into the B+ tree in the memory device; when the size of the B+ tree reaches a certain limit, the keys are traversed. value data; Judging according to the heat strategy, the key-value data with low heat will be persisted to the 0th layer of the cold tree in the external storage device, and the key-value data with high heat will continue to remain in the B+ tree; If the number of key-value data files in layer 0 of the cold tree reaches the size limit, the layer-0 partition operation is triggered, and the layer-0 partition operation is equally divided according to the existing key-value data range in the layer. When the number of key-value data files reaches the size limit, the partition operation is triggered again; When the low-heat key-value data in the B+ tree performs the persistence operation, the 0-tier partition only receives the key-value data that meets the set range; , then transfer the key-value data in this range to the hot tree of the external memory device, and use the B+ tree in the memory device to index the key-value data in the hot tree; When the size of the hot tree reaches a certain limit, the key-value data is judged according to the heat policy, and one or more key-value data in the low-heat range are transferred to the cold tree partition, and the indexes of these data are deleted from the B+ tree. . 2. a kind of key-value storage method based on multi-tree conversion mechanism according to claim 1, is characterized in that, described heat strategy is specifically: When the key-value data in the read-only skip table is inserted into the B+ tree structure, the insertion time field is saved to judge the popularity of the key-value data; According to the time field recorded in the node, determine whether the key-value data needs to be kept in the B+ tree, if not, it will be persisted to the cold tree partition of the external storage device; For the key-value data in the external storage device, the global heat table is used to record the operands of the key-value data. When the merge operation in the cold tree is performed, if the operand of a range unit located in the cold tree reaches the threshold, the All key-value data within this range unit is transferred to the hot tree; When the hot tree reaches a certain size limit, use the global heat table to perform heat judgment on the key-value data in the hot tree, and judge whether the key-value data in the range needs to be retained in the hot tree according to the range of the key-value data. If no retention is required, the key-value data in these ranges in the hot tree is transferred to the cold tree. 3. a kind of key-value storage method based on multi-tree conversion mechanism according to claim 1 and 2, is characterized in that, also comprises data reading step, is specially: S11: First, search for the target data in the cache area, if found, go to step S12; if not, go to step S13; S12: The system completes the user's read request and sends the read target data to the user; S13: Find the target key and value type in the B+ tree, if found and the value type is the actual value, go to step S12, if found and the value type is address information, go to step S14; if not found, go to step S15; S14: Read the target data in the hot tree of the external storage device according to the address obtained in the previous step, and go to step S12; S15: Search the target data from top to bottom in the cold tree of the external storage device, if found, go to step S12; if not, go to step S16; S16: The system completes the user's read request and sends the result to the user, but the target data is not found. 4. a kind of key-value storage method based on multi-tree conversion mechanism according to claim 1 and 2, is characterized in that, also comprises data writing step, is specially: S21: First write into the skip table structure, if the size limit is reached, go to step S22; S22: Convert this skip table to a read-only skip table, and create a new write skip table structure for data writing; S23: If the size of the B+ tree does not reach the limit, go to step S25; if it reaches the limit, go to step S24; S24: Traverse the key-value data in the B+ tree, and persist the key-value data with lower heat to the cold tree of the external storage device, and go to step S25; S25: Save the key-value data and the current time in the read-only skip table structure to the B+ tree structure; S26: The system completes the user's writing request, and sends a successful writing information to the user. 5. a kind of key-value storage method based on multi-tree conversion mechanism according to claim 1 and 2, is characterized in that, the storage structure of application is specifically: Write skip table, read-only skip table, B+ tree, and cold tree structure and hot tree structure in disk; wherein the cold tree structure is a 3-layer log structure merge tree, including 0-level log structure, 1-level log structure, 2-level log structure Layer log structure, and the 0-layer log structure has a partition structure; the hot tree structure is a single-layer log structure merge tree.

Images