CN106293537B - A lightweight approach to autonomous block management for data-intensive file systems - Google Patents

Abstract

The invention discloses a light-weight autonomous block management method of a data-intensive file system, which realizes the mapping of data blocks to data storage nodes and the fast data block storage in data storage nodes through Intersected Shifted Declustering (ISD). Search, fast recovery of data blocks when a data storage node fails, and fast redistribution of data blocks when a new data storage node is added, etc., make the master node only responsible for the storage and maintenance of the file namespace in the data-intensive file system, and the data blocks to The storage and maintenance of mapping relationship information of data storage nodes, the replacement of data blocks when data storage nodes fail, and the redistribution of data blocks when new data storage nodes are added are all completed autonomously by data storage nodes. The invention saves the memory space of the master node in the data-intensive file system, improves the processing capability of the master node, and can greatly improve the data block management efficiency of the data-intensive file system in the big data environment.

Description

A lightweight approach to autonomous block management for data-intensive file systems

technical field

The invention relates to computer security technology, in particular to a light-weight autonomous block management method of a data-intensive file system.

Background technique

Data-intensive file system DiFS, such as Google File System GFS, Hadoop Distributed File System HDFS, etc., has become the main file system for big data storage management. The current data-intensive file system DiFS adopts a master-slave architecture. The master node (metadata server) manages all metadata, and the slave node (data storage node) is only responsible for data storage. In order to maintain high availability, these storage systems usually divide data files into blocks of fixed size, each data block usually has 3 copies, and distribute them to different data storage nodes of the cluster. The master node must record the addresses of hundreds or even thousands of data storage nodes, and record the mapping information from the data blocks of all data files to these storage nodes. Moreover, the master node must periodically check the changes of the address mapping information of all data blocks. As the amount of data continues to increase, these metadata information not only occupy the memory space of the master node, affect the processing capability of the master node, but also seriously limit the scalability of the master node.

In order to solve the problems existing in data-intensive file systems, the allocation and maintenance of data file physical blocks are separated from metadata management, and the method of maintaining data block-to-storage node mapping information by each data storage node came into being. Applying this method, the master node does not need to save a large amount of data block metadata information and the mapping table information from data blocks to data storage nodes, but needs to use a set of data blocks to data storage nodes, data storage nodes to data blocks The reversible mapping function of is completed.

Data-intensive file systems manage massive amounts of data, which have the following characteristics: 1) large data volume and rapid growth in total data volume; 2) high data storage performance requirements; 3) high reliability and high recoverability requirements: when data In the event of loss or data storage node failure, the original data can be quickly restored without affecting normal work; 4) It is required to quickly find the storage location of the data block; 5) It is required to occupy as little memory space as possible on the master node and affect the processing capability of the master node as little as possible;

It can be seen from the above analysis that the traditional file system management methods are not suitable for the management of data-intensive file systems. The main reasons are: 1) With the continuous increase of data volume, the storage of file data block address tables will occupy a large amount of storage space ; 2) The master node is responsible for the maintenance of the file data block address table. With the continuous increase of the file data block address table, the processing capacity of the master node is greatly reduced; 3) The continuous increase of the data volume not only takes up a large amount of storage space of the master node , which increases the maintenance cost of metadata such as addresses, and also reduces the scalability of the master node; 4) Each data storage node must first consult the master node when storing and querying, which increases the addressing time.

Contents of the invention

Aiming at the data block storage and query management requirements of the data-intensive file system, the present invention provides a light-weight autonomous block management method of the data-intensive file system, through the distribution, query and related metadata maintenance of physical data blocks Separated from traditional metadata management, it is completed by each data storage node, reducing the overhead and burden of the master node's storage space. The invention can improve the expansibility of the data-intensive file system in the big data environment, reduce the data block addressing time, and greatly improve the performance of the whole system.

The technical principle of the present invention is that the present invention realizes the autonomous management of data blocks through the intersected shifted division method (ISD, IntersectedShifted Declustering), that is, by using a set of reversible mathematical functions to realize data blocks to data storage nodes, and data storage nodes to data Block mapping, complete distributed storage and fast query of data blocks, etc.

The present invention specifically comprises following several operations:

Operation 1. Data block storage operation;

Operation 2. Data block search operation;

Operation 3. Invalidation data storage node failure processing operation;

Operation 4. Add a new data storage node operation.

(1) The data block storage operation includes the following steps:

Step 1.1. The master node selects the logical group (LG) where the data block is located through a reversible linear hash function;

Step 1.2, the master node selects the data storage node in the logic group through the reversible displacement partition function to store the data block data;

Step 1.3, the data storage node stores data block data and data block address mapping information.

(2) The data block search operation includes the following steps:

Step 2.1, the data storage node where the data block b is located uses a reverse reversible function to calculate the new ID of the logical group where the data block b is located according to its index number;

Step 2.2, the data storage node where the data block b is located uses the reverse reversible function to calculate the physical ID of the data block b according to the logical group ID where the data block b is located, and provides conditions for the file system to recover the complete data file;

Step 2.3, the data storage node obtains the mapping information of the data block on the storage node according to the physical ID of the data block;

Step 2.4, the data storage node fetches the data of data block b according to the mapping information of data block b and sends it to the file system.

(3) The failure processing operation of the failure data storage node includes the following steps:

Step 3.1, determine the logical grouping where the failed data storage node is located;

Step 3.2, select the data storage node with the smallest load in the logical grouping other than the data storage failure node as the backup node;

In step 3.3, multiple backup data storage nodes use the intelligent reorganization mapping method to parallelly copy the data contained in the corresponding failure data storage nodes in each logical group.

(4) The operation of adding a new data storage node includes the following steps:

Step 4.1, calculating the average load COV _ave of data storage nodes in all logical groups in the entire system;

Step 4.2, select a logical group, and calculate the maximum load COV _max among all data storage nodes in the group;

Step 4.3, compare the size of COV _max and COV _ave , if COV _max ≥ COV _ave , replace the data storage node in the logical group with the newly added data storage node. Otherwise, select the next logical group and repeat steps 4.1, 4.2 and 4.3 until the load of the newly added data storage node reaches or approaches the average load of the data storage nodes in the system.

The advantages of this data-intensive approach to file system autonomous block management are:

(1) The storage space overhead of the master node is greatly reduced. The data block to data storage node mapping information is separated from the traditional metadata, and each data storage node independently stores and manages it. The master node does not need to save and maintain a large amount of data block address information, so that the master node saves Metadata information is reduced by more than 90% compared to traditional file systems.

(2) Greatly improve the processing capacity of the master node. The mapping information between data blocks and data storage nodes is independently stored and maintained by each data storage node, eliminating the burden on the master node. Compared with the distributed file system HDFS, this method can improve the processing performance of the master node by more than 30%.

(3) Improve the recoverability and scalability of the system. When the data storage node fails, the intelligent reorganization mapping method is adopted, and the decoupling address mapping method is adopted when adding a new data storage node, so that only a few data blocks can be migrated to complete the recovery of the data of the failed data node and the data of the newly added data node. Replication greatly improves the recoverability and scalability of the system.

Description of drawings

Fig. 1 is the flow chart of concrete operation of the present invention;

Fig. 2 is a schematic diagram of the division of management functions between master nodes and data storage nodes in the present invention;

Figure 3 is an example of the mapping of continuous blocks to data nodes and the lookup of data nodes to blocks;

Figure 4 is an example of a data node failure recovery process;

Figure 5 is an example of the process of adding a new data node.

Detailed ways

In order to make the technical means, creative features, goals and effects achieved by the present invention easy to understand, the following will further explain the autonomous block management of a light-weight data-intensive file system proposed by the present invention in combination with diagrams and specific embodiments method.

A lightweight autonomous block management method for data-intensive file systems, which implements the mapping from data blocks to data nodes and from data nodes to data blocks through a set of reversible mathematical functions. As shown in Figure 2, the specific functions of each node in the present invention are divided: the master node is only responsible for the maintenance of the system namespace, the distribution of data blocks to data storage nodes, and the management of each data storage node; each data storage node is responsible for the consistency of data blocks Consistency check, data block recovery, and mapping information storage and maintenance of data storage nodes.

As shown in Figure 1, the autonomous block management method described in the present invention specifically includes the following operations:

Operation 1. Data block storage operation;

Operation 2. Data block search operation;

Operation 3. Invalidation data storage node failure processing operation;

Operation 4. Add a new data storage node operation.

(1) Data block storage operation, including the following steps:

Step 1.1. The master node selects the logical group (LG) where the block is located through a reversible linear hash function;

Step 1.2, the master node selects the data storage node in the logic group through the reversible displacement partition function to store the data block data;

Step 1.3, the data storage node stores data block data and data block address mapping information.

In step 1.1 of the data block storage operation, the logic group (LG) formula where the data block is selected is selected through a reversible linear hash function:

Among them, g is the logical group ID to be mapped, x is the current number of groups in the system, X is the number of logical groups in the system at the beginning, b is the block ID of the file in which the data block is to be stored, and s is the newly added number of logical groups,

In step 1.2 of the data block storage operation, the process of selecting data storage nodes in the logic group through a reversible displacement partition function includes:

A) Calculate the new block identifier after data block b is mapped to logical group g, its formula:

Among them, a is the new identifier of the data block in the logical group g, x is the current logical group number, X is the initial logical group number, b specifies the data block ID, s is the newly added logical group number,

B) Calculate the index ID of data block b mapped to the data storage node in logical group g, its formula:

d=node(a,i)=(a+i)%4 (3)

Among them, a is the new data block identifier of data block b in logical group g, i is the copy number of data block b (value 0, 1, 2), and d is the data storage node selected by data block b in logical group Index (values 0, 1, 2, 3).

The said copy number means that the intensive file system provides three copies for each data block to fully guarantee its availability, and its number is 0, 1, 2; the index of the data storage node refers to the The numbers of all data storage nodes, each logic group in the present invention includes 4 data storage nodes, and their index numbers are 0, 1, 2, and 3 respectively.

(2) The data block search operation includes the following steps:

Step 2.1, the data storage node where the data block b is located uses a reverse reversible function to calculate the new ID of the logical group where the data block b is located according to its index number;

Step 2.2, the data storage node where the data block b is located uses the reverse reversible function to calculate the physical ID of the data block b according to the logical group ID where the data block b is located, and provides conditions for the file system to recover the complete data file;

Step 2.3, the data storage node obtains the mapping information of the data block on the storage node according to the physical ID of the data block;

Step 2.4, the data storage node obtains the data of the data block b according to the mapping information of the data block b and sends it to the file system.

Step 2.1 in the data block search operation calculates the new ID of the logical group where the data block b is located according to the index number d of the data storage node using a reverse reversible function, the formula:

d=(a+i)%4→reversible operation→a=4·j+(d-i)%4 (4)

Where i represents the copy number of the data block, which can be 0, 1, 2 iteratively, and j can be 0, 1, 2, ..., n, etc.;

The step 2.2 in the data block lookup operation calculates the physical ID of the data block b with a reverse reversible function, its formula:

where g is the index containing the logical group of given datastore nodes,

Figure 3(a) shows that continuous data blocks are mapped to each logical group through linear hash, and the distributed storage of data blocks in each data storage node in the logical group is realized through migration and division; Figure 3(b) is based on data node 2 As an example, demonstrate the process of reversely finding data blocks through reversible functions.

(3) The failure processing operation of the failure data storage node includes the following steps:

Step 3.1, determine the logical grouping where the failed data storage node is located;

Step 3.2, select the data storage node with the smallest load in the logical grouping other than the data storage failure node as the backup node;

In step 3.3, multiple backup data storage nodes use the intelligent reorganization mapping method to parallelly copy the data contained in the corresponding failure data storage nodes in each logical group.

The intelligent reorganization mapping method is to select the number of backup data storage nodes to be equal to the number of logical groups containing failure data storage nodes. A failure data storage node may be included in multiple logic groups, and each backup data storage node is only responsible for Part of the data in the failed data storage node in a corresponding logical group is copied.

Fig. 4 takes the failure of data node 2 as an example to demonstrate the replacement and recovery process of data node 2 by each logical group.

(4) The operation of adding a new data storage node mainly adopts the method of decoupling address mapping, including the following steps:

Step 4.1, calculating the average load COV _ave of data storage nodes in all logical groups in the entire system;

Step 4.2, select a logical group, and calculate the maximum load COV _max among all data storage nodes in the group;

Step 4.3, compare the size of COV _max and COV _ave , if COV _max ≥ COV _ave , replace the data storage node with the largest load in the logic group with the newly added data storage node. Otherwise, select the next logical group and repeat steps 4.1, 4.2 and 4.3 until the load of the newly added data storage node reaches or approaches the average load of the data storage nodes in the system.

FIG. 5 demonstrates the data block migration process of the entire system when a new data node node ₁₂₈ is added to the system to form a new logical group LG ₁₀₀₀ .

It can be seen from Figure 4 and Figure 5 that the system adopts the reversible function and adopts the intelligent reorganization mapping method and the decoupling address mapping method, so that when data nodes fail and new data nodes are added, only a few data blocks are migrated, which fully guarantees System stability and availability to users.

The method is illustrated below with an example.

Choose HDFS as the data-intensive file system. By simulating 10,000 data nodes and a large data environment with 1,000,000 data blocks, when using the lightweight data-intensive file system’s autonomous block management method and not using this method, the master node The memory usage is shown in Table 1, and the CPU usage of the master node is shown in Table 2. Among them, 1,000,000 data blocks are evenly distributed among 10,000 data nodes, and the size of each data block is 64MB.

Table 1 Memory usage of master node management data blocks

Number of data nodes 1000 2000 5000 7000 9000 10000 Optimized memory usage (MB) 15 20 27 36 42 50 Unoptimized memory usage (MB) 180 186 189 192 194 196

Table 2 CPU usage of the master node management data block

Number of data nodes 500 2000 3000 4000 5000 Optimized CPU usage (%) 1.4 2.3 2.5 3.1 4.2 Unoptimized CPU usage (%) 6.3 12.1 16.6 19.8 23.2

It can be seen from Table 1 and Table 2 that after adopting the autonomous block management method of the lightweight data-intensive file system, the memory usage and CPU usage of the master node are significantly better than those without the lightweight data-intensive file system The case of the autonomous block management method.

Although the content of the present invention has been described in detail through the above preferred embodiments, it should be understood that the above description should not be considered as limiting the present invention. Various modifications and alterations to the present invention will become apparent to those skilled in the art upon reading the above disclosure. Therefore, the protection scope of the present invention should be defined by the appended claims.

Claims (6)

1. A light-weight autonomous block management method for data-intensive file systems, characterized in that the data-intensive file system realizes autonomous management of data blocks through a cross-migration division method, that is, by using a set of reversible mathematical functions, Realize the mapping from data blocks to data storage nodes, and from data storage nodes to data blocks, and complete the distributed storage and search of data blocks; Realizing data block storage operations through the autonomous block management method includes the following steps: Step 1.1. The master node selects the logical group where the data block is located through a reversible linear hash function; Step 1.2, the master node selects a data storage node in the logical group through a reversible displacement partition function; Step 1.3, storing the data of the data block and the address mapping information of the data block at the selected data storage node; The failure processing operation of the failure data storage node is realized through the autonomous block management method, including the following steps: Step 3.1, determine the logical grouping where the failed data storage node is located; Step 3.2, select the data storage node with the smallest load in the logical grouping other than the data storage failure node as the backup node; Step 3.3, multiple backup data storage nodes adopt the intelligent reorganization mapping method, and copy the data contained in the corresponding failure data storage nodes in each logical group in parallel; The intelligent reorganization mapping method is to make the number of selected backup data storage nodes equal to the number of logic groups containing failure data storage nodes, one failure data storage node is included in multiple logic groups, and each backup data storage node only Partial data of the failed data storage node in a corresponding logical group is copied. 2. the autonomous block management method of lightweight data-intensive file system as claimed in claim 1, is characterized in that, Realizing the data block search operation through the autonomous block management method includes the following steps: Step 2.1, the data storage node where the data block is located uses the reverse reversible function to calculate the new ID of the logical group where the data block is located according to its index number; Step 2.2, the data storage node where the data block is located calculates the physical ID of the data block with a reverse reversible function according to the new ID of the logical group where the data block is located; Step 2.3, the data storage node obtains the mapping information of the data block on the storage node according to the physical ID of the data block; Step 2.4, the data storage node obtains the data of the data block and sends it to the data-intensive file system according to the mapping information of the data block. 3. The autonomous block management method of the lightweight data-intensive file system as claimed in claim 1 or 2, characterized in that, The operation of adding a new data storage node is realized through the autonomous block management method, wherein a decoupling address mapping method is adopted, including the following steps: Step 4.1, calculating the average load COV _ave of data storage nodes in all logical groups in the entire system; Step 4.2, select any logical group, and calculate the maximum load COV _max among all data storage nodes in the logical group; Step 4.3, compare the size of COV _max and COV _ave , if COV _max ≥ COV _ave , replace the data storage node with the largest load in the logical group with the newly added data storage node; otherwise, select the next logical group, and repeat steps 4.1, Step 4.2 and Step 4.3, until the load of the newly added data storage node reaches or approaches the average load of the data storage nodes in the system. 4. the autonomous block management method of lightweight data-intensive file system as claimed in claim 1, is characterized in that, In step 1.1, the formula for selecting the logical group where the data block is located is selected through a reversible linear hash function: Among them, g is the logical group ID, x is the current logical group number in the system, X is the initial logical group number in the system, b is the data block ID of the data block to be stored in its file, and s is the newly added logic Number of groups, In step 1.2, the process of selecting data storage nodes in a logical group through a reversible displacement partition function includes: A) Calculate the new block identifier after data block b is mapped to logical group g, its formula: Among them, a is the new identifier of data block b in logical group g; B) Calculate the index ID of data block b mapped to the data storage node in logical group g, its formula: d=node(a,i)=(a+i)%4 (3) Wherein, i is the copy number of the data block b, and d is the index number of the data storage node selected by the data block b in the logic group. 5. the autonomous block management method of lightweight data-intensive file system as claimed in claim 4, is characterized in that, In step 2.1, the new ID of the logical group where the data block b is located is calculated with a reverse reversible function; a=4·j+(d-i)%4 (4) This formula is obtained by carrying out reversible operation to d=(a+i)%4; Wherein, the iteration number i of the data block is 0, 1, 2, and j is zero or a positive integer; In step 2.2, use the reverse reversible function to calculate the physical ID of data block b: 6. the autonomous block management method of lightweight data-intensive file system as claimed in claim 1, is characterized in that, In the data-intensive file system, system namespace maintenance, distribution of data blocks to data storage nodes, and management of each data storage node are performed through the master node; And, each data storage node is responsible for the consistency check of the data block, the recovery of the data block, and the storage and maintenance of the mapping information of the data storage node.