CN106055277A - Decentralized distributed heterogeneous storage system data distribution method - Google Patents

Abstract

The invention discloses a decentralized distributed heterogeneous storage system data distribution method, which comprises the following steps: 1) classifying data objects; 2) classifying storage equipment; 3) putting storage data into different ''placement group clusters'', wherein the type of each kind of storage equipment corresponds to one class of ''placement group cluster''; 4) calculating a ratio for each type of data object to be stored to be placed in different types of ''placement group clusters''; 5) utilizing a Hash algorithm to determine which ''placement group'' in the ''placement group clusters'' does the data object to be stored belongs to; and 6) utilizing a data distribution algorithm of the storage system to store the data objects in each ''placement group'' into multiple pieces of corresponding storage equipment. The method has the advantages that the performance, the load balancing and the expandability of the storage system are kept, the write operation frequency of a solid state disk is reduced, and the service life of the solid state disk is prolonged.

Description

A decentralized distributed heterogeneous storage system data distribution method

technical field

The invention belongs to the technical field of distributed computer storage, and in particular relates to a data distribution method of a decentralized distributed heterogeneous storage system.

Background technique

In big data applications, scientific computing and cloud computing platforms, reliable and scalable storage systems play a vital role in system performance. As the amount of data increases (PB level), the data distribution strategy of the storage system must ensure performance and scalability. Decentralized data distribution strategies, such as Ceph, use the processing power of the storage device itself to provide a reliable object storage system. Solid-state drives (SSDs) have better read and write performance than traditional mechanical hard drives (HDDs), and are more and more widely used in storage systems to form large-scale distributed heterogeneous storage systems. However, the data distribution strategy of the storage system must consider the "write endurance" of the solid-state hard disk, and at the same time ensure the scalability and load balancing of the system, because too many write operations will accelerate the loss of the solid-state hard disk storage medium.

Currently, there are many researches devoted to data distribution and task scheduling in workflow systems. For example, in scientific computing, the "workflow management system" will allocate computing tasks based on the storage resources and computing power of the computing site. According to the dependencies of the tasks in the workflow model, the amount of data required for these tasks can be determined, and then the computing tasks at different stages are allocated to different computing sites. The allocation scheme mainly considers reducing the remote access transmission overhead of different sites. Ceph uses the communication capabilities of the storage device itself to design a new data distribution method. This method is divided into two steps. The first step uses the hash algorithm to map data objects to "placement groups". The input of the hash function It is the globally unique identifier of the data object, and the data objects with the same output result of the hash function are placed in the same "placement group". The second step distributes each "placement group" across multiple storage devices using a pseudo-random hash algorithm. This data distribution method does not consider the heterogeneous characteristics of the storage system, which will lead to intensive write operations on the solid state disk. There are also some works that use solid-state drives to improve centralized storage performance. This centralized data distribution strategy makes the system not scalable and not suitable for ultra-large-scale data applications.

Contents of the invention

Aiming at the deficiencies of the existing technology, the technical problem to be solved by the present invention is to provide a decentralized distributed heterogeneous storage system data distribution method, which maintains the performance and load balance of the storage system by analyzing the access mode of data objects and scalability while reducing write operations to SSDs.

The technical problem to be solved by the present invention is realized by such technical scheme, and it comprises the following steps:

Step 1. During the execution of the program, count the number of times each data object is read/written, convert the number of reads and writes into a weight, and use it as the access mode of the data; classify the data objects according to the access mode of the data;

Step 2. Classify the storage devices according to their capacity and read/write performance;

Step 3. Divide the stored data into different "placement group clusters", where a "placement group cluster" includes multiple "placement groups", and each type of storage device corresponds to a type of "placement group cluster";

Step 4. According to the load balancing target and performance index of the storage system, calculate the proportion of each data object to be stored that should be placed in different types of "placement group clusters";

Step 5. Use the hash algorithm to determine which "placement group" in the "placement group cluster" the data object to be stored belongs to;

Step 6: Utilize the data distribution algorithm of the storage system to store the data objects in each "placement group" in multiple corresponding storage devices. "Placement Groups" for SSDs are assigned to SSDs, and "Placement Groups" for HDDs are assigned to HDDs.

Technical effect of the present invention:

According to the access mode of the data object, the present invention distributes different types of data to different "placement group clusters". At this time, it is necessary to calculate the ratio of different types of data objects to be stored in different "placement group clusters". To control the load balancing between "placement group clusters", after determining the "placement group cluster" to which each data object belongs, then use the hash algorithm to calculate the "placement group" corresponding to the data object; then put the "placement group "The data objects in " are distributed to the storage device. In this way, the data is evenly distributed to the storage devices, eliminating the centralized data storage structure, which not only maintains the performance, load balance and scalability of the storage system, but also reduces the number of write operations to the solid-state hard disk and prolongs its life.

Description of drawings

The accompanying drawings of the present invention are as follows:

Figure 1 is a flow chart of calculating the ratio of each type of data object to be stored to each "placement group cluster";

Fig. 2 is a data storage process diagram of the present invention;

3 is a schematic diagram of mapping read-intensive data objects to "placement groups";

FIG. 4 is a schematic diagram of mapping write-intensive data objects to "placement groups".

detailed description

Below in conjunction with accompanying drawing and embodiment the present invention will be further described:

The present invention comprises the following steps:

Step 1. During the execution of the program, count the number of times each data object is read/written, convert the number of reads and writes into a weight, and use it as the data access mode; classify the data object according to the data access mode, such as read Intensive, write-intensive and mixed; the classification method can use the common K-Means clustering algorithm, and each type of data object has an attribute value used to represent the average number of writes of this type of data object;

Step 2. Classify storage devices according to their capacity and read/write performance, such as high-speed solid-state drives, low-speed solid-state drives, high-speed mechanical hard drives, and low-speed mechanical hard drives. Each storage device has its own read-write performance parameters, such as average read Write latency, capacity.

Step 3. Divide the stored data into different "placement group clusters", where a "placement group cluster" includes multiple "placement groups", and each type of storage device corresponds to a type of "placement group cluster". "Placement group cluster" is used to combine data objects with similar read and write attributes; "Placement group cluster" is a logical concept, mainly used to aggregate data objects, and "placement group cluster" also has capacity and read The attribute of write performance, the capacity is the capacity of all the hard disks corresponding to the "placement group cluster", and the read and write performance is the average read and write delay of these hard disks.

Step 4. According to the load balancing target and performance index of the storage system, calculate the proportion of each data object to be stored that should be placed in different types of "placement group clusters";

For example, suppose the system has 3 "placement group clusters". For read-intensive data, 20% of the data is placed in the first "placement group cluster", 30% is placed in the second "placement group cluster", and 50% is placed in the second "placement group cluster". Three "placement group clusters", this ratio refers to the ratio of the number of each type of "placement group clusters" to the total data of that type.

The performance index of the storage system is set according to the read and write performance of the storage device. For example, it is required that for all data objects, the average delay of read operations is 0.2 milliseconds, and the average delay of write operations is 0.5 milliseconds. The purpose of setting the proportion of each data object in different types of "placement group clusters" is to ensure that the data is evenly distributed among the "placement group clusters". In extreme cases, all data objects are write-intensive. According to the target of storage device allocation, write-intensive data objects should be allocated to mechanical hard drives to reduce write operations on solid-state drives. However, if all data objects are If it is write-intensive, all of them will be allocated to the "placement group cluster" corresponding to the mechanical hard disk, so that there is no data in the solid-state hard disk. In order to avoid this situation, it is necessary to allocate the same type of data objects to different "placement group clusters", and use this ratio to control the load balancing between "placement group clusters".

Step 5. Use the hash algorithm to determine which "placement group" in the "placement group cluster" the data object to be stored belongs to, because one "placement group cluster" contains multiple "placement groups".

Step 6. Use the data distribution algorithm of the storage system to store the data objects in each "placement group" in multiple corresponding storage devices, and the "placement group" in the "placement group cluster" corresponding to the solid state disk will be allocated to The "Placement Group" in the "Placement Group Cluster" corresponding to the solid state disk and mechanical hard disk will be assigned to the mechanical hard disk.

The reason for a "placement group" to store to multiple storage devices is to make multiple backups of the same data. The number of backups is set by system initialization. Because there are multiple storage devices corresponding to the same "placement group", a mapping algorithm is required to determine which storage device should be placed in each "placement group".

In the above step 4, the algorithm flow chart for calculating the ratio of each type of data object to be stored to each type of "placement group cluster" is shown in Figure 1:

The flow starts at step 801, and then:

In step 802, calculate the total number of all data objects to be stored, that is, the sum of different types of data objects;

In step 803, calculate the total number of existing data objects, that is, in the initial state, the number of data objects stored in all storage devices;

In step 804, according to the load balancing condition, calculate the maximum value of data objects that each "placement group cluster" can store; that is, determine the capacity of each "placement group cluster";

Load balancing is a configuration parameter of the system. When all data objects are evenly distributed, an increase or decrease of 5% according to the capacity of each storage device is considered to be load balancing. For example, if a "placement group cluster" can store 100 data objects in a fully evenly distributed state, and the balance condition of load balancing allows 5% fluctuation, then the "placement group cluster" can store up to 100+100*0.05= 105 data objects;

In step 805, all the data objects to be stored are arranged in ascending order according to the average write times, and the average write times are attributes of different types of data objects;

Assuming that the data objects to be stored are divided into three categories, read-intensive, write-intensive and mixed, the average number of writes for read-intensive data is 10, the average number of writes for write-intensive data is 80, and the average number of writes for mixed The number of times is 50.

In step 806, all "placement group clusters" are arranged in descending order of performance, wherein the performance of "placement group clusters" is the read and write performance of the corresponding storage device, and the read and write performance of the solid state disk is better than that of the mechanical hard disk;

In step 807, initialize the variable i=0, which is used to scan the category of data objects to be stored;

Assuming that the data objects to be stored are divided into 3 categories, i in this process is 1, 2, 3. This is a cyclic iteration process, that is, to scan the data objects of each category to be stored;

In step 808, the variable j=0 is initialized, which is used to scan the "placement group cluster" category;

Assuming that the data "placement group cluster" is divided into 4 categories, j in this process is 1, 2, 3, 4;

In step 809, assign the i-th type of data object to be stored to the j-th type "placement group cluster";

This step is to fill in the number of each type of data objects to be stored in sequence according to the sequence arranged in step 805 and step 806 according to the capacity of the "placement group cluster" calculated in step 804;

In step 810, record the number of data objects to be stored in type i stored in the "placement group cluster" j, for calculating the storage ratio of each type of data objects to be stored;

The total number of each type of data objects to be stored is known, record the number of each type of data objects to be stored in each "placement group cluster", and divide this value by each type of data objects to be stored Enter the total number of recorded data objects to get the ratio.

In step 811, it is judged whether the "placement group cluster" j has reached the maximum storage number, if yes, execute step 812, otherwise execute step 813;

In step 813, it is judged whether all data objects to be stored have been processed, if yes, execute step 816, otherwise, execute step 814;

In step 814, the pointer i used to scan the array of data object categories is moved to the next position, that is, the next type of data object to be stored is processed, and step 809 is performed;

In step 812, the pointer j used to scan the array of "placement group clusters" is moved to the next position, that is, the next "placement group cluster" is processed;

In step 815, it is judged whether all the "placement group clusters" have been processed, if yes, execute step 816, otherwise, execute step 809;

In step 816, according to the number of each type of data object to be stored in each "placement group cluster" recorded in step 810, calculate the ratio of each type of data object to be stored in each type of "placement group cluster";

In step 817, the algorithm for assigning each type of data to be stored to each type of "placement group cluster" ends.

The data storage process of the above step 5 and step 6 is shown in Figure 2. The "placement group" of the storage system is divided into different "placement group clusters", and each "placement group cluster" contains multiple "placement groups". When storing data objects, it is necessary to first determine which "placement group cluster" the data belongs to based on the category of each data object and the distribution ratio of the data objects of this category in the "placement group cluster". This process must go through the process in Figure 1 To calculate the ratio of different types of objects placed in different "placement group clusters" to control the load balance between "placement group clusters", and then use the hash algorithm to determine that the data object belongs to this "placement group cluster" Which "placement group". Step 6 uses a pseudo-random hash algorithm (CRUSH) to map this "placement group" to different storage devices.

(1), the embodiment of the flowchart shown in Figure 1

Assuming that the storage system has five types of storage devices, and each type of storage device corresponds to a "placement group cluster", then the system has five "placement group clusters". All placement group clusters have been sorted from high to low performance (corresponding to step 806 ). As shown in Table 1.

surface Properties of System Storage Devices

Placement group cluster Types of capacity load Average Read Latency (ms) Average Write Latency (ms) 1 SSD 1000 60 0.12 0.22 2 SSD 1500 260 0.66 0.35 3 mechanical hard drive 2000 300 5.20 7.84 4 mechanical hard drive 2500 530 6.58 8.70 5 mechanical hard drive 3000 700 8.30 9.20

The total capacity of the storage system is: 1000+1500+2000+2500+3000=10000

Assuming that the data objects to be stored are divided into three categories, the average number of reads and writes and the number of objects of each category are shown in Table 2. Each type has been sorted according to the number of writes (corresponding to step 805).

surface All attributes to be stored in the data object

target type average readings average write times quantity A 100 10 350 B 40 30 150 C 30 50 200

According to the process shown in Figure 1, the operation process of the algorithm is as follows:

In step 802, the total number of all data objects to be stored is 350+150+200=700;

In step 803, calculate the total number of existing data objects as 60+260+300+530+700=1850;

The total number of data objects is: 700+1850=2500;

In step 804, assuming that the balance factor e=0.001 of the system load balancing, then for each "placement group cluster" the corresponding maximum value RMAX that can be accommodated is calculated, and the calculation formula is as follows:

"Placement group cluster" 1: RMAX.1: (1+0.001)*(1000*(700+1850))/10000=255;

"Placement group cluster" 2: RMAX.2: (1+0.001)*(1500*(700+1850))/10000=383;

"Placement group cluster" 3: RMAX.3: (1+0.001)*(2000*(700+1850))/10000=511;

"Placement group cluster" 4: RMAX.4: (1+0.001)*(2500*(700+1850))/10000=638;

"Placement group cluster" 5: RMAX.5: (1+0.001)*(3000*(700+1850))/10000=766;

Therefore, for the five "placement group clusters", assuming that the data is evenly distributed, the maximum capacity RMAX is respectively: 255,383,511,638,766.

In step 807, i is initialized to 0, and is used to scan the three types of data objects to be stored in A, B, and C.

In step 808, j is initialized to 0 for scanning "placement group clusters" 1, 2, 3, 4, 5.

The allocation at step 809 and the recording process at step 810 are as follows:

When classifying the three types of data objects, class A with the least average write times and more read times is preferentially allocated to OSD.1 with small write delay and small read delay.

1. The load of the placement group cluster 1 itself is 60, the calculated maximum capacity is 255, and the capacity is 255-60=195.

Therefore, 195 data objects of type A can be allocated to placement group cluster 1. At this time, 350-195=155 of type A remain.

Placement group cluster 1 is full.

load A B C RMAX Placement group cluster 1 60 195 0 0 255 Placement group cluster 2 260 0 0 0 383 Placement group cluster 3 300 0 0 0 511 Placement group cluster 4 530 0 0 0 638 Placement group cluster 5 700 0 0 0 766

2. The load of the placement group cluster 2 itself is 260, the calculated maximum capacity is 383, and the capacity is 383-260=123.

Continue to allocate 123 data objects of type A to placement group cluster 2, leaving 155-123=32 of type A.

Placement group cluster 2 is full.

load A B C RMAX Placement group cluster 1 60 195 0 0 255 Placement group cluster 2 260 123 0 0 383 Placement group cluster 3 300 0 0 0 511 Placement group cluster 4 530 0 0 0 638 Placement group cluster 5 700 0 0 0 766

3. The load of cluster 3 of the placement group is 300, the calculated maximum capacity is 511, and the capacity is 511-300=211;

Continue to allocate 32 data objects of type A to placement group cluster 3, type A is allocated and 0 remains;

The remaining capacity of the placement group cluster 3 is 211-32=179;

Allocate type B, and preferentially allocate to placement group cluster 3 with relatively small read and write delays;

Allocate all 150 data objects of type B to placement group cluster 3. At this time, the remaining capacity of the placement group cluster 3 is 179-150=29;

For allocation of type C, it is still preferentially allocated to placement group cluster 3 with relatively small read and write delays;

Allocate 29 data objects of type C into placement group cluster 3, leaving 200-29=171 of type C.

Placement group cluster 3 is full.

load A B C RMAX Placement group cluster 1 60 195 0 0 255 Placement group cluster 2 260 123 0 0 383 Placement group cluster 3 300 32 150 29 511 Placement group cluster 4 530 0 0 0 638 Placement group cluster 5 700 0 0 0 766

4. The load of the placement group cluster 4 itself is 530, the calculated maximum capacity is 638, and the capacity is 638-530=108;

Continue to allocate 108 data objects of type C to placement group cluster 4, leaving 63=171-108 of type C.

Placement group cluster 4 is full.

load A B C RMAX Placement group cluster 1 60 195 0 0 255 Placement group cluster 2 260 123 0 0 383 Placement group cluster 3 300 32 150 29 511 Placement group cluster 4 530 0 0 108 638 Placement group cluster 5 700 0 0 0 766

5. The load of the placement group cluster 5 itself is 700, the calculated maximum capacity is 766, and the capacity is 766-700=66;

Allocate 63 data objects of type C to placement group cluster 5, allocating type C and leaving 0.

The remaining capacity of placement group cluster 5 is still 66-63=3.

load A B C RMAX Placement group cluster 1 60 195 0 0 255 Placement group cluster 2 260 123 0 0 383 Placement group cluster 3 300 32 150 29 511 Placement group cluster 4 530 0 0 108 638 Placement group cluster 5 700 0 0 63 766

In step 816, according to the final result, calculate the ratio of each type of data object to be stored to each "placement group cluster":

A B C Placement group cluster 1 195/350=0.56 0/150=0 0/200=0 Placement group cluster 2 123/350=0.35 0/150=0 0/200=0 Placement group cluster 3 32/350=0.09 150/150=1 29/200=0.145 Placement group cluster 4 0/350=0 0/0=0 108/200=0.54 Placement group cluster 5 0/350=0 0/0=0 63/200=0.315

(2). The following describes how step 5 of the present invention maps different types of data objects to different "placement groups".

In this embodiment, it is assumed that the system has 100 "placement groups", numbered from 1 to 100. According to the type of system storage device, these "placement groups" are divided into three "placement group clusters": 1-20 is the first "placement group cluster", 21-50 is the second "placement group cluster", No. 51-100 is the third "placement group cluster".

As shown in FIG. 3 , a read-intensive data object is mapped to a “placement group” 13 . Assume that the distribution ratio (Distribution Ratio) of read-intensive data objects in the three "placement group clusters" is 6:2:2 through the process algorithm shown in Figure 1, that is, the "placement groups" of numbers 1-20 are For the first "placement group cluster", 60% of the read-intensive data belongs to the first "placement group cluster", and "placement group" No. 21-50 is the second "placement group cluster", with 20% Read-intensive data belongs to the second "placement group cluster", No. 51-100 "placement group" belongs to the third "placement group cluster", and 20% of the read-intensive data belongs to the third "placement group cluster". Since the result of the current read-intensive data object’s identification through the hash function is 50, within the scope of the first “placement group cluster”, the hash algorithm is used to calculate the target “placement” of the data object. group" is 13.

As shown in FIG. 4 , a write-intensive data object is mapped to a "placement group" 62 . Assuming that the distribution ratio of write-intensive data objects in the three "placement group clusters" is 1:3:6, the result of the identification of the data object after the hash function is also 50, but 50 belongs to the third "placement group cluster" "(Because the ratio of read-intensive data and write-intensive data to each placement group cluster is different, the hash value in the middle of Figure 4 lists the placement ratios of the three "placement group clusters", and the hash value is 1 Data objects with -10 can be considered as being placed in the first type of "placement group cluster", data objects with a hash value of 11-40 are placed in the second type of "placement group cluster", and data with a hash value of 41-100 Objects are placed into the third category "Placement Group Cluster"), so this object is finally mapped into "Placement Group" 62.

Claims (4)

1. A decentralized distributed heterogeneous storage system data distribution method, characterized in that it comprises the following steps: Step 1. During the execution of the program, count the number of times each data object is read/written, convert the number of reads and writes into a weight, and use it as the access mode of the data; classify the data objects according to the access mode of the data; Step 2. Classify the storage devices according to their capacity and read/write performance; Step 3. Divide the stored data into different "placement group clusters", where a "placement group cluster" includes multiple "placement groups", and each type of storage device corresponds to a type of "placement group cluster"; Step 4. According to the load balancing target and performance index of the storage system, calculate the proportion of each data object to be stored that should be placed in different types of "placement group clusters"; Step 5. Use the hash algorithm to determine which "placement group" in the "placement group cluster" the data object to be stored belongs to; Step 6: Utilize the data distribution algorithm of the storage system to store the data objects in each "placement group" in multiple corresponding storage devices. 2. A decentralized distributed heterogeneous storage system data distribution method according to claim 1, characterized in that, in said step 4, calculating the placement of each type of data object to be stored in each "placement group" The steps for "cluster" ratio include: Step 802, calculating the total number of all data objects to be stored; Step 803, calculating the total number of existing data objects; Step 804, according to the load balancing condition, calculate the maximum value of data objects that each "placement group cluster" can store; Step 805, arrange all the data objects to be stored in ascending order according to the average write times; Step 806, arrange all "placement group clusters" in descending order of performance; Step 807, initialize the variable i=0, which is used to scan the category of data objects to be stored; Step 808, initialize the variable j=0, which is used to scan the "placement group cluster" category; Step 809, assign the i-th type of data object to be stored to the j-th type of "placement group cluster"; Step 810, recording the number of data objects to be stored in type i stored in the "placement group cluster" j; Step 811, judging whether the "placement group cluster" j has reached the maximum storage number, if yes, go to step 812, otherwise go to step 813; Step 813, judging whether all data objects to be stored have been processed, if yes, execute step 816, otherwise, execute step 814; Step 814, process the next type of data object to be stored, and execute step 809; Step 812, process the next "placement group cluster"; Step 815, judging whether all the "placement group clusters" have been processed, if yes, execute step 816, otherwise, execute step 809; Step 816, according to the number of each type of data object to be stored stored in each "placement group cluster" recorded in step 810, calculate the proportion of each type of data object to be stored in each type of "placement group cluster". 3. A decentralized distributed heterogeneous storage system data distribution method according to claim 2, characterized in that, in the step 809, the i-th type of data object to be stored is assigned to the j-th type " The method of "placement group cluster" is: according to the order arranged in step 805 and step 806, according to the capacity of "placement group cluster" calculated in step 804, the number of each type of data objects to be stored is filled in turn. 4. A decentralized distributed heterogeneous storage system data distribution method according to claim 1, characterized in that: in step 6, the pseudo-random hash algorithm is used to map this "placement group" to different storage in the device.