CN114490524A - High-performance distributed key value storage method based on master-slave copy data decoupling - Google Patents

Abstract

The invention discloses a high-performance distributed key value storage method based on master-slave copy data decoupling, which is applied to a storage cluster comprising a plurality of nodes, if any node receives key value data for the ith time, decoupling operation and differentiated storage operation are carried out on ith key value data, so that the ith key value data are written into a log structure merged tree or a two-layer log architecture for storage and management, the key value data in the two-layer log architecture are subjected to sequential adjustable operation, and parallel data recovery operation is carried out on the key value data in a fault node. The invention can improve the overall performance of the distributed key value system and provide a mechanism capable of dynamically adjusting the read-write performance according to the performance requirements of the application, thereby solving the key problem that the unified multi-copy data management scheme in the existing distributed key value storage system aggravates the read-write amplification of the system.

Description

A high-performance distributed key-value storage method based on master-slave replica data decoupling

technical field

The invention belongs to the technical field of computer storage systems, and in particular relates to constructing a differentiated copy data storage mechanism based on master-slave copy data decoupling in a distributed key-value storage system (distributed KV Stores), and designing a The replica data management scheme with dynamically adjustable order, realizes a distributed key-value storage method with high performance and adjustable read and write performance.

Background technique

In order to meet the storage and access requirements of massive unstructured data, and overcome the shortcomings of traditional relational databases and file storage in scalability and performance, key-value storage (referred to as KV storage) system provides a good solution , such as Google's LevelDB, Facebook's RocksDB and other stand-alone key-value storage systems, as well as distributed key-value storage systems derived to support large-scale data storage, such as PingCAP's TiKV, Amazon's DynamoDB, and A Cassandra of the Patch Foundation. The above mainstream key-value storage systems all use a log-structured merge tree (LSM-tree) to manage key-value data (key-value pairs). The advantage of writing is that random writing can be converted into sequential writing, so as to obtain efficient writing performance.

On the other hand, in order to ensure high reliability of data and provide data fault tolerance, the multi-copy fault tolerance mechanism is widely used in distributed key-value storage systems, that is, each key-value data is copied into multiple copies and stored in multiple nodes (when After the data of one node is lost, data recovery can be performed from other nodes). However, the existing multi-copy management solutions of distributed key-value storage systems do not consider the read-write amplification problem existing in the log-structured merge tree (LSM-tree) architecture, and simply use a log-structured merge tree (LSM-tree) on each node. LSM-tree) for unified storage of all replica data.

Therefore, the amount of data stored in the log-structured merge tree (LSM-tree) under the multi-copy mechanism increases exponentially, and the data of different copies will interfere with each other when performing read and write operations, which further aggravates the log-structured merge tree (LSM-tree). tree) read-write amplification problem.

SUMMARY OF THE INVENTION

In order to solve the shortcomings of the above-mentioned prior art, the present invention proposes a high-performance distributed key-value storage method based on the decoupling of master-slave replica data, in order to improve the overall performance of the distributed key-value system and provide The mechanism of dynamically adjusting the read and write performance according to the performance requirements of the application, thus solving the key problem that the unified multi-copy data management scheme in the existing distributed key-value storage system aggravates the system's read and write amplification.

The present invention adopts the following technical scheme in order to achieve the above-mentioned purpose of the invention:

The feature of the high-performance distributed key-value storage method based on the decoupling of master-slave replica data of the present invention is that it is applied to a storage cluster including several nodes. i key-value data for decoupling operations and differentiated storage operations;

The decoupling operations include:

Hash the key in the received i-th key-value data to obtain the i-th hash value, and then calculate the i-th key-value data according to the i-th hash value and the consistent hash ring A node number to which the key in is mapped; if the calculated node number is equal to the node number that currently receives the i-th key-value data, then the i-th key-value data is identified as the primary copy; otherwise, all The i-th key-value data is identified as a slave copy;

The differentiated storage operations include:

If the i-th key-value data is the master copy, write the i-th key-value data into the log structure merge tree of the node for storage and management;

If the i-th key-value data is a slave copy, the i-th key-value data is written into a two-tier log architecture for storage and management.

The high-performance distributed key-value storage method of the present invention is also characterized in that the writing step of the two-layer log architecture includes:

(i) When the two-layer log architecture receives the i-th key-value data, it is judged whether i>Nmax holds, and if so, execute step (ii), otherwise, write the i-th key-value data into the first-layer global log middle;

(ii) For the Nmax key-value data in the first-layer global log, the background thread calculates the node number mapped by the key in each key-value data; and establishes a corresponding local log according to different node numbers, and in each Each local log has several range groups;

(iii) Split Nmax key-value data:

A. Define variable j and initialize j=1;

B. For the jth key-value data, the background thread calculates that the node number mapped by the key in the jth key-value data is L, then maps it to the Lth local log; and judges that in the Lth local log , the range group to which the key of the jth key-value data belongs; and then write the jth key-value data into the corresponding range group in the Lth local log;

C. After assigning j+1 to j, judge whether j>Nmax is true. If it is true, it means that Nmax key-value data are written into different range groups of different local logs respectively, and all the data in each range group are written into different range groups. Several key-value data written are stored in a file to form an ordered segment corresponding to each range group; otherwise, return to step B for execution.

The key-value data in the two-tier log architecture can be adjusted according to the following steps:

If the high-performance distributed key-value storage method is applied to a read-intensive storage system, the merge operation between ordered segments in a range group is increased, that is, when the number of ordered segments in a range group exceeds the threshold Δ ₁ When , all ordered segments in the corresponding range group are merged into one ordered segment, so that the number of ordered segments in the range group is maintained within the threshold Δ ₁ ;

If the high-performance distributed key-value storage method is applied to a write-intensive storage system, the merge operation between ordered segments in a range group is reduced, that is, when the number of ordered segments in a range group exceeds _Δ2 , merge all ordered segments in the corresponding range group into one ordered segment, so as to maintain the number of ordered segments in the range group within the threshold Δ ₂ ; Δ ₁ <Δ ₂ .

Perform parallel data recovery operations on the key-value data in the faulty node as follows:

(i) Use two threads to read data from the log-structured merge tree and the two-layer log on each node in parallel, and based on the read key-value data, calculate the hash value of each key-value data, and put It is stored in each node of the Merkle tree, thereby constructing the Merkle tree on each node;

(ii) Compare the Merkle tree constructed on the faulty node with the Merkle tree constructed by other nodes in turn, and judge whether the fault node and other Merkle trees have the same value at the same position; if they are the same, It means that the key-value data corresponding to the corresponding node is not lost, and the process ends, otherwise, it means that the key-value data corresponding to the corresponding node has been lost;

(iii) Use two threads on the non-faulty node to read the corresponding key-value data on the node where the lost data is located from the log-structured merge tree and the two-layer log in parallel as recovery data, and send it to the faulty node;

(iv) After receiving the recovery data, the faulty node uses two threads to write the recovery data into the log-structured merge tree and the two-layer log in parallel.

Compared with the prior art, the beneficial technical effects of the present invention are embodied in:

1. Lightweight master-slave replica data decoupling: The present invention uses hash calculation combined with a consistent hash ring to decouple the master-slave replica data, so that the master-slave replica decoupling operation is lightweight, It has low overhead and does not affect the data distribution mechanism and consistency protocol of the upper layer of the storage system.

2. Differential storage of master-slave copy data: The present invention uses a log structure merge tree to store the decoupled master copy, and uses a two-layer log structure to store the decoupled slave copy, thereby effectively avoiding the execution of read The mutual interference between the master and slave replica data during write operations overcomes the key problem that the unified multi-copy management scheme in the existing distributed key-value storage system aggravates the system read and write amplification; and the two-tier log architecture design also improves slave Write and read performance of replicas.

3. The order degree of the two-layer log can be adjusted: the present invention designs an order degree adjustment mechanism for data storage, which can dynamically adjust the order degree of the two-layer log structure, and can adjust the two-layer log to be conducive to writing or reading, The order of the two-layer logs can be adjusted according to the different performance requirements of the application, so that the system performance can be improved in different scenarios.

4. Parallel data recovery: when recovering lost data, the present invention uses multiple threads to read and write data from the log structure merge tree and the two-layer log in parallel, which speeds up data recovery operations and shortens data recovery time.

To sum up, the present invention can better solve the The unified multi-copy management scheme in the distributed key-value system aggravates the problem of system read-write amplification, greatly improves the overall read-write performance and data recovery performance of the distributed key-value system, and ensures the high reliability of the system.

Description of drawings

1 is an overall architecture diagram of a high-performance distributed key-value storage method based on master-slave replica data decoupling of the present invention;

2 is a schematic diagram of a decoupling flow of master-slave replica data of the present invention;

Fig. 3 is the schematic diagram of the two-tier log architecture of the present invention;

Fig. 4 is the schematic diagram of data grouping based on scope in the local log of the present invention;

5 is a schematic diagram of an adjustable degree of ordering of data storage of the present invention;

FIG. 6 is a schematic diagram of parallel data recovery according to the present invention.

Detailed ways

In this embodiment, as shown in FIG. 1 , a high-performance distributed key-value storage method based on decoupling of master-slave replica data includes decoupling of master-slave replica data and differential storage of master-slave replica data , storage order adjustment and parallel data recovery. The present invention adopts hash calculation combined with a consistent hash ring to decouple the master-slave replica data, so that the master-slave replica decoupling operation is lightweight and low-cost, and does not affect the data distribution mechanism and consistency of the upper layer. In addition, the present invention first batch appends the data from the replica to the global log of the first layer through the two-layer log structure, and then the background thread divides it into multiple local logs of the second layer, so as to ensure efficient writing from the replica secondly, the present invention designs the data storage order-adjustable technology, which can adjust the two-layer log to be favorable for writing or reading, so that users can meet different performance requirements according to different performance requirements. to adjust the order degree of the two-layer log, so as to improve the overall performance of the key-value storage system in different scenarios; finally, when recovering lost data, the present invention uses multi-threading to merge the tree and the two-layer log from the log structure in parallel Read and write data in the middle to speed up data recovery operations. The following is a detailed description of each operation.

In this embodiment, the high-performance distributed key-value storage method based on the decoupling of master-slave replica data is applied to a storage cluster including several nodes. i key-value data for decoupling operations and differentiated storage operations;

Decoupling operations include:

Hash the key in the received i-th key-value data to obtain the i-th hash value, and then calculate the i-th key-value data according to the i-th hash value and the consistent hash ring. A node number to which the key is mapped; if the calculated node number is equal to the node number that currently receives the i-th key-value data, the i-th key-value data is identified as the primary copy; otherwise, the i-th key-value data is identified as the primary copy; data identified as secondary copies;

FIG. 2 shows a schematic diagram of the decoupling process of master-slave replica data in this embodiment. After distinguishing whether the received key-value data is a master copy or a slave copy, each node first writes the key-value data into the corresponding write-first log and memory cache, and then notifies the client that the key-value data was successfully written. When the cache is full, it is batched into a log-structured merge tree or a two-tier log architecture. The decoupling of master-slave data is lightweight because each node only needs to perform one additional hash computation in the I/O path. Experiments show that the time overhead of decoupling operations is less than 0.4% of the total data writing time. In addition, the decoupling operation of master-slave replica data is performed independently on each node and does not require synchronization across nodes.

Differentiated storage operations include:

If the i-th key-value data is the primary copy, write the i-th key-value data into the log-structured merge tree of the node for storage and management; to preserve the efficient read, write and range scanning of the log-structured merge tree Design features, but in a more lightweight way, since the log-structured merge tree size is significantly reduced after slave replicas are not included in the log-structured merge tree.

If the i-th key-value data is a slave copy, write the i-th key-value data into a two-tier log architecture for storage and management; to support fast slave copy write performance and efficient data recovery performance.

In a specific implementation, the writing steps of the two-tier log architecture include:

(i) When the two-layer log architecture receives the i-th key-value data, it is judged whether i>Nmax holds, and if so, execute step (ii), otherwise, write the i-th key-value data into the first-layer global log Figure 3 shows a schematic diagram of the two-tier log architecture in this embodiment. In order to realize the fast writing of key-value data, each node first writes the received key-value data into the memory cache and sorts it. When the cache is full , and append it to the head of the first-level global log in batches to form a segment file. Since the global log does not maintain any additional index structure, the global log design can guarantee high write performance for key-value data. However, while storing all key-value data in the global log achieves high write performance, it can result in lower data recovery performance. For the key-value data in the global log, their corresponding primary copies may be stored on different nodes. When a node loses data, only part of the key-value data in the global log needs to be read (that is, the corresponding primary copy is located in the faulty node's such key-value data) for recovery. As a result, recovery operations only access part of the data in the global log, causing a lot of random I/O to search the global log. To ensure efficient data recovery performance, a background thread is maintained to continuously split the data in the global log into multiple local logs, see step (ii).

(ii) For the Nmax key-value data in the first-layer global log, the background thread calculates the node number mapped by the key in each key-value data; and establishes a corresponding local log according to different node numbers, and in each Each local log is provided with several scope groups; Fig. 4 provides a schematic diagram of the scope-based data grouping in each local log in this embodiment, each local log is further divided into multiple scope groups, each scope group Corresponds to a range in a consistent hash ring. Note that the different scope groups in each local log do not overlap in keys, so the different scope groups can be managed independently. For example, the node N2 in FIG. 4 has a local log LOG0 that stores a type of key-value data, and its corresponding primary copy resides in the node N0. Since node N0 has two ranges [0, 10] and [51, 60], the local log LOG0 of node N2 contains two range groups, respectively saving [0, 10] and [51, 60]. key-value data.

(iii) Split Nmax key-value data:

A. Define variable j and initialize j=1;

B. For the jth key-value data, the background thread calculates that the node number mapped by the key in the jth key-value data is L, then maps it to the Lth local log; and judges that in the Lth local log , the range group to which the key of the jth key-value data belongs; then the jth key-value data is written into the corresponding range group in the Lth local log; in order to determine the range group to which each key-value data belongs, The keys of the key-value data can be compared to the boundary values of each range in the consistent hash ring to find the corresponding range group. Since each local log only retains the same type of slave copy data (its corresponding master copy is stored on the same node), and each local log further uses range-based data grouping, data recovery operations only require access and failure The key-value data of the corresponding range group in the local log corresponding to the node does not need to access all local logs and all range groups, thereby avoiding a large number of invalid random I/O operations;

C. After assigning j+1 to j, judge whether j>Nmax is true. If it is true, it means that Nmax key-value data are written into different range groups of different local logs respectively, and all the data in each range group are written into different range groups. Several key-value data written are stored in a file to form an ordered segment corresponding to each range group; otherwise, return to step B for execution.

In this embodiment, the key-value data in the two-tier log architecture is subjected to the following steps to perform an orderly adjustable operation:

First, since each range group of each local log may contain multiple ordered segments, and the key-value data among the ordered segments within the range group is not completely ordered. Therefore, reading data from a range group needs to start with the latest ordered segment and check each ordered segment one by one until the queried data is found. If the range group contains too many ordered segments, the read performance of the two-tier log will degrade. Therefore, the number of ordered segments in each range group is adjusted according to the following steps. Figure 5 shows a schematic diagram of the adjustable degree of ordering within a range group:

If the high-performance distributed key-value storage method is applied to a read-intensive storage system, the merge operation between ordered segments in a range group is increased, that is, when the number of ordered segments in a range group exceeds the threshold Δ ₁ , In this embodiment, if Δ ₁ is set to 10, all ordered segments in the corresponding range group are merged into one ordered segment, so that the number of ordered segments in the range group is maintained within the threshold Δ ₁ ;

If the high-performance distributed key-value storage method is used in a write-intensive storage system, the merge operation between ordered segments in a range group is reduced, that is, when the number of ordered segments in a range group exceeds Δ ₂ , this In the embodiment, if Δ ₂ is set to 100, all ordered segments in the corresponding range group are merged into one ordered segment, so that the number of ordered segments in the range group is maintained within the threshold Δ ₂ ; Δ ₁ < Δ ₂ .

The merge operation between ordered segments in a range group is similar to the merge operation in a log-structured merge tree, including the following steps: (i) read all ordered segments from the range group; (ii) merge all the ordered segments in the range group Ordered segments are sorted. If there are multiple key-value data with the same key in different ordered segments, only the key-value data in the latest ordered segment is retained, and the corresponding key-value data in other ordered segments is discarded; (iii) Write the merged valid key-value data back to the corresponding range group.

Through the above-mentioned adjustment operation of the data order degree within the range group, the present invention can improve the read and write performance of the distributed key-value storage system under different workloads and different system configurations. Experiments have verified that the order degree proposed by the present invention can be The adjusted two-layer log design can improve the read and write performance of the distributed key-value storage system by 1.4 times and 2.5 times respectively.

In this embodiment, the parallel data recovery operation is performed on the key-value data in the faulty node according to the following steps. FIG. 6 shows a schematic diagram of the parallel data recovery operation in this embodiment, assuming that the data lost on the faulty node N0 is recovered:

(i) Use two threads to read data from the log-structured merge tree and the two-layer log on each node in parallel, and based on the read key-value data, calculate the hash value of each key-value data, and put It is stored in each node of the Merkle tree, thereby building the Merkle tree on each node; in Figure 6, nodes N0 and N1 use two threads to merge the tree and the log structure from each node in parallel, respectively. Read data from the two layers of logs, and build Merkle trees on nodes N0 and N1 according to the read data;

(ii) Compare the Merkle tree constructed on the faulty node with the Merkle tree constructed by other nodes in turn, and judge whether the fault node and other Merkle trees have the same value at the same position; if they are the same, It means that the key-value data corresponding to the corresponding node is not lost, and the process ends; otherwise, it means that the key-value data corresponding to the corresponding node has been lost; in Figure 6, the Merkle trees constructed on nodes N0 and N1 are compared respectively, Since all the data in node N0 is lost, the Merkle tree constructed on node N0 is empty. After comparing it with the Merkle tree constructed on node N1, it is detected that the key-value data that has been lost on node N0;

(iii) Use two threads on the non-faulty node to read the corresponding key-value data on the node where the lost data is located from the log-structured merge tree and the two-layer log in parallel as the recovery data, and send it to the faulty node; Figure 6 The non-faulty node N1 uses two threads to read the missing key-value data on node N0 detected in step (ii) from the log-structured merge tree and the two-layer log in parallel, such as in the range [11, 20], [21,30] key-value data and send it to the faulty node N0;

(iv) After the faulty node receives the restored data, it uses two threads to write the restored data to the log-structured merge tree and the two-layer log in parallel; in Figure 6, the faulty node N0 receives the restored data from the non-faulty node N1 [11] ,20],[21,30], use two threads to write key-value data in the range of [11,20] and [21,30] to the log-structured merge tree and the two-level log in parallel.

By designing the above parallel data recovery operation, the present invention greatly improves the data recovery performance, and experiments show that the parallel data recovery operation designed by the present invention can reduce the data recovery time by about half.

Claims (4)

1. A high-performance distributed key-value storage method based on master-slave replica data decoupling, characterized in that it is applied to a storage cluster comprising several nodes, if any node receives the key-value data for the i-th time, then The i-th key-value data performs decoupling operations and differentiated storage operations; The decoupling operations include: Hash the key in the received i-th key-value data to obtain the i-th hash value, and then calculate the i-th key-value data according to the i-th hash value and the consistent hash ring A node number to which the key in is mapped; if the calculated node number is equal to the node number that currently receives the i-th key-value data, the i-th key-value data is identified as the primary copy; otherwise, all The i-th key-value data is identified as a slave copy; The differentiated storage operations include: If the i-th key-value data is the master copy, write the i-th key-value data into the log structure merge tree of the node for storage and management; If the i-th key-value data is a slave copy, the i-th key-value data is written into a two-tier log architecture for storage and management. 2. The high-performance distributed key-value storage method according to claim 1, wherein the writing step of the two-tier log architecture comprises: (i) When the two-layer log architecture receives the i-th key-value data, it is judged whether i>Nmax holds, and if so, execute step (ii), otherwise, write the i-th key-value data into the first-layer global log middle; (ii) For the Nmax key-value data in the first-layer global log, the background thread calculates the node number mapped by the key in each key-value data; and establishes a corresponding local log according to different node numbers, and in each Each local log has several range groups; (iii) Split Nmax key-value data: A. Define variable j and initialize j=1; B. For the jth key-value data, the background thread calculates that the node number mapped by the key in the jth key-value data is L, then maps it to the Lth local log; and judges that in the Lth local log , the range group to which the key of the jth key-value data belongs; and then write the jth key-value data into the corresponding range group in the Lth local log; C. After assigning j+1 to j, judge whether j>Nmax is true. If it is true, it means that Nmax key-value data are written into different range groups of different local logs respectively, and all the data in each range group are written into different range groups. Several key-value data written are stored in a file to form an ordered segment corresponding to each range group; otherwise, return to step B for execution. 3. The high-performance distributed key-value storage method according to claim 2, wherein the key-value data in the two-layer log architecture is subjected to an orderly adjustable operation according to the following steps: If the high-performance distributed key-value storage method is applied to a read-intensive storage system, the merge operation between ordered segments in a range group is increased, that is, when the number of ordered segments in a range group exceeds the threshold Δ ₁ When , all ordered segments in the corresponding range group are merged into one ordered segment, so that the number of ordered segments in the range group is maintained within the threshold Δ ₁ ; If the high-performance distributed key-value storage method is applied to a write-intensive storage system, the merge operation between ordered segments in a range group is reduced, that is, when the number of ordered segments in a range group exceeds _Δ2 , merge all ordered segments in the corresponding range group into one ordered segment, so as to maintain the number of ordered segments in the range group within the threshold Δ ₂ ; Δ ₁ <Δ ₂ . 4. The high-performance distributed key-value storage method according to claim 1, wherein a parallel data recovery operation is performed on the key-value data in the faulty node according to the following steps: (i) Use two threads to read data from the log-structured merge tree and the two-layer log on each node in parallel, and based on the read key-value data, calculate the hash value of each key-value data, and put It is stored in each node of the Merkle tree, thereby constructing the Merkle tree on each node; (ii) Compare the Merkle tree constructed on the faulty node with the Merkle tree constructed by other nodes in turn, and judge whether the fault node and other Merkle trees have the same value at the same position; if they are the same, It means that the key-value data corresponding to the corresponding node is not lost, and the process ends, otherwise, it means that the key-value data corresponding to the corresponding node has been lost; (iii) Use two threads on the non-faulty node to read the corresponding key-value data on the node where the lost data is located from the log-structured merge tree and the two-layer log in parallel as recovery data, and send it to the faulty node; (iv) After receiving the recovery data, the faulty node uses two threads to write the recovery data into the log-structured merge tree and the two-layer log in parallel.

Images