CN103902735B - Application perception data routing method oriented to large-scale cluster deduplication and system - Google Patents

Abstract

The invention discloses an application-aware data routing method for large-scale cluster deduplication and a large-scale backup storage cluster system for realizing the method. The application-aware data routing method includes: S10) obtaining backup file meta information, S20) perceiving the file application type, S30) calculating the deduplication storage node load, S40) selecting a file routing node, S50) sending the file to the target node and S60) processing the node Steps such as deduplication of internal files; a large-scale backup storage cluster system includes multiple backup clients, a backup server and multiple deduplication storage servers. The data routing method and system of the present invention have the characteristics of high data deduplication rate, high node throughput rate, small system communication overhead and balanced system load.

Description

Application-aware data routing method and system for large-scale cluster deduplication

technical field

The invention belongs to the technical field of information storage and cluster computing, in particular to an application-aware data routing method for large-scale cluster deduplication and a large-scale backup storage cluster system.

Background technique

In many backup storage systems that manage massive data, the data is highly redundant. Cluster Deduplication technology is to realize distributed and parallel data deduplication processing on the backup storage server cluster system, which can meet the capacity and performance of massive backup data management. scalability needs. In order to build an energy-saving, environmentally friendly, and efficient green data center, cluster deduplication has become the core technology of current data center storage management.

In consideration of system overhead, cluster deduplication often chooses a loosely coupled design and does not perform cross-node data deduplication. The data sent by the backup client is first distributed to each deduplication storage server node through data routing, and the deduplication storage server then independently and parallelly deletes the duplicate data content in the node. Data routing directly affects storage space utilization of backup data, system throughput of deduplication storage server nodes, load balancing and communication overhead of deduplication storage server clusters. Therefore, the data routing method is very important to improve the efficiency of cluster deduplication.

At present, there are three main data routing methods for cluster deduplication: block-level data routing methods based on distributed hash tables, super-block-level data routing methods based on state information, and file-level data routing methods based on similarity. A block-level data routing method based on a distributed hash table, such as the USENIX FAST'09 conference paper "HYDRAstor: a Scalable Secondary Storage" (public date: 2009-02-23) and the Chinese invention patent application "Distributed Data Deduplication System and its method" (application number: 201110461322.2, publication date: 2011-12-28), which is to distribute the characteristic value of the data block to different data deduplication nodes according to the distributed hash table. Although this method can effectively improve space utilization and reduce communication overhead, it cannot preserve the data locality in nodes and affect system throughput. The super-block-level data routing method based on state information, such as the USENIX FAST'11 conference paper "Tradeoffs in Scalable Data Routing for Deduplication Clusters" (public date: 2011-02-14), merges many continuous data blocks after division into uniform granularity Before superblock routing, it is necessary to query the number of repetitions between the data blocks contained in it and the existing data blocks in each node, and then try to route the superblock to the node with the largest number of duplicate data blocks under the premise of considering load balancing. This strategy can achieve a high data reduction rate under the premise of load balancing, but its broadcast system communication overhead and frequent block fingerprint query operations in nodes seriously affect system performance. Similarity-based file-level data routing, such as the IEEE/ACM MASCOTS'09 conference paper "Extreme Binning: Scalable, Parallel Deduplication for Chunk based FileBackup" (public date: 2009-09-21), uses Broder's minimum independent permutation theorem Select the minimum value of the fingerprint of the data block in the file as the similar feature of the file, and route similar files to the same deduplication storage server node according to the distributed hash mechanism, but when the similarity in the data stream is low, the file cannot be detected Similarity, the cluster deduplication effect of backup data is poor.

In short, the problems existing in the existing technology are: deduplication for clusters with hundreds or thousands of nodes in the data center, there are defects such as low data deduplication rate, low node throughput rate, large system communication overhead and unbalanced system load.

Contents of the invention

The purpose of the present invention is to provide an application-aware data routing method and system for large-scale cluster deduplication, which has the characteristics of high data deduplication rate, high node throughput rate, small system communication overhead and system load balance.

The technical solution to achieve the purpose of the present invention is: an application-aware data routing method for large-scale cluster deduplication, the large-scale backup storage cluster system includes multiple backup clients (100), a backup server (200) and Multiple deduplication storage servers (300), characterized by comprising the following steps:

S10) Obtaining backup file meta information: the backup client (100) sends a file backup request message including file name, user and size of the file meta information to the backup server (200);

S20) Sensing file application types: the backup server (200) classifies the application types of the backup files according to the file meta-information, and queries the application index structure to obtain a list of candidate deduplication storage server (300) nodes that can store corresponding types of application files;

S30) Calculating the load of deduplication storage nodes: the backup server (200) obtains the real-time dynamic load information of each deduplication storage server (300) node by querying the application-aware index structure, and calculates the available load information based on these node load information and backup file meta information A list of low load deduplication storage servers (300) to maintain load balance;

S40) Select file routing nodes: the backup server (200) analyzes the list of candidate deduplication storage server nodes and the list of low-load deduplication storage server nodes, selects a low-load candidate server node storing the same type of application data as the file routing target node, and Return the result to the backup client (100);

S50) Send files to the target node: the backup client (100) sends each file in the backup session to the corresponding routing target deduplication storage server (300) node according to the file routing decision result returned by the backup server (200);

S60) Processing deduplication of files within the node: the deduplication storage server (300) node independently performs data deduplication processing on different types of application files according to differences in the data format and content of the application files.

A large-scale backup storage cluster system for implementing an application-aware data routing method for large-scale cluster deduplication, including multiple backup clients (100), a backup server (200) and multiple deduplication storage servers (300 ), characterized by:

The backup client (100) is configured to send to the backup server (200) a file backup request message containing file meta information such as file name, user, and size,

The backup server (200) is used to perceive the application type of the backup file according to the file meta information, and query the application index structure to obtain a list of node numbers of the candidate deduplication storage server (300) that can store the corresponding type of application file;

The backup server (200) is used to obtain the real-time dynamic load information of each deduplication storage server (300) node by querying the application-aware index structure, and calculate the low-load consumption information that can maintain load balance according to the load information of these nodes and the backup file meta-information. re-storage server (300) node list;

The backup server (200) is used to analyze the list of candidate deduplication storage server nodes and the list of low-load deduplication storage server nodes, select a low-load candidate node storing the same type of application data as the file routing target node, and return the result to the backup client end(100);

The backup client (100) sends each file in the backup session to the corresponding routing target deduplication storage server (300) node according to the file routing decision result returned by the backup server (200);

The deduplication storage server (300) node is used to independently perform data deduplication processing on different types of application files according to differences in the data format and content of the application files.

Compared with the prior art, the present invention has significant advantages:

1. High data deduplication rate: through the application-aware data routing strategy, similar data is allocated to the same deduplication storage server node, reducing data overlap between nodes, and files in the same deduplication storage server node are independent by application Perform data deduplication processing in a timely manner;

2. High node throughput: allocate data based on file granularity, and maintain good locality of data access;

3. System load balancing: dynamically allocate storage resources according to the actual physical storage capacity of each deduplication storage server node, to ensure the load balance of the entire backup storage cluster system;

4. Low communication overhead: The data routing is judged at the granularity of the application, which greatly reduces the message communication overhead of the system.

In a word, the present invention provides an application-aware data routing method that can support a backup storage cluster system with a scale of hundreds or even thousands of nodes for cluster deduplication. It can not only greatly save the storage space usage of backup data, but also optimize the deduplication throughput rate of deduplication storage server nodes, reduce the communication overhead within the cluster system, and maintain the load balance of each deduplication storage server node.

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Description of drawings

FIG. 1 is a schematic structural diagram of a large-scale backup storage cluster system of the present invention.

FIG. 2 is a main flowchart of the application-aware data routing method for large-scale cluster deduplication in the present invention.

Fig. 3 is a schematic diagram of the perception file application type.

FIG. 4 is a flow chart of steps for selecting a file routing node in FIG. 2 .

detailed description

As shown in Figure 1, the large-scale backup storage cluster system of the present invention includes multiple backup clients 100, a backup server 200 and multiple deduplication storage servers 300;

The backup client 100 is used to send a file backup request message containing file meta information such as the name, user and size of the file to the backup server 200; Each file sent to the corresponding routing target deduplication storage server 300 node;

Each backup client 100 includes a file I/O module 101 and a backup request module 102, the backup request module 102 is used to perform a file backup session with the backup server 200, and the file I/O module 101 is used to According to the file routing decision result returned by the backup server 200, each file is backed up to the corresponding deduplication storage server 300;

The backup server 200 is used to perceive the application type of the backup file according to the file meta information, and query the application index structure to obtain a list of node numbers of the candidate deduplication storage server 300 that can store the corresponding type of application file; the backup server 200 is the core for realizing the method of the present invention part.

The backup server 200 obtains the real-time dynamic load information of each deduplication storage server 300 nodes by querying the application-aware index structure, and calculates a list of low-load deduplication storage server 300 nodes that can maintain load balance according to the load information of these nodes and the backup file meta-information ;

The backup server 200 analyzes the candidate deduplication storage server node list and the low-load deduplication storage server node list, selects a low-load candidate node storing the same type of application data as the file routing target node, and returns the result to the backup client 100;

The backup server 200 includes a backup session management module 201, an application-aware process module 202, a file routing decision module 203, and a load balancing module 204. The backup session management module 201 is configured to receive a backup request from the backup client 100, and store files by The same backup sessions from the same user are managed in groups, and the file routing decision result is fed back to the backup client 100. The application awareness process module 202 is used to classify files by application type, and the load balancing module 204 is used to maintain System load balancing of the deduplication storage server cluster, the file routing decision module 203 is used to distribute the same type of application files to the same low-load deduplication storage server node, and feed back the file routing target node information to the backup client 100 , and establish a mapping relationship between the application file and the deduplication storage server node for use when the file is restored.

The deduplication storage server 300 node independently performs data deduplication processing on different types of application files according to differences in the data format and content of the application files.

The deduplication storage server 300 includes a data deduplication engine 301, a file metadata management module 302 and a data block management module 303. The data deduplication engine 301 is used to perform deduplication processing on backup files, and according to the characteristics of different applications , independently perform data deduplication on files of each application type, the file metadata management module 302 is used to manage metadata and block fingerprint index information of files stored on nodes, and the data block management module 303 is used to manage deduplication A unique data block whose content is not repeated.

As shown in Figure 2, the application-aware data routing method for large-scale cluster deduplication of the present invention is based on a scalable cluster deduplication system architecture. The large-scale backup storage cluster system is shown in Figure 1, including multiple A backup client 100, a backup server 200, and multiple deduplication storage servers 300.

The application-aware data routing method for large-scale cluster deduplication of the present invention includes the following steps:

S10 ) Acquiring backup file meta information: the backup client 100 sends a file backup request message including file name, user, size and other file meta information to the backup server 200 .

S20) Sensing file application type: the application awareness process module 202 of the backup server 200 classifies the application type of the backup file according to the file meta-information obtained by the backup session management module 201, and queries the application index structure to obtain the application file that can store the corresponding type Candidate deduplication storage server 300 node list.

The step of perceiving file application type (S20) is shown in Figure 3, including:

S21) Obtaining file meta information: the backup server 200 obtains the file meta information in the backup request, including the file name 230, user 231, and size 232 of the file. The file name 230 includes a prefix and a suffix, and the suffix defines the application type; The prefix of Test.doc is Test, the suffix is doc, and the corresponding application type is a Word document in doc format.

S22) Query the application index structure: query the application index structure according to the application type determined by the file name, including index items such as application type 233, node number 234, and data volume 235;

Among them, the application type 233 is the file name suffix corresponding to the backup file, the node number 234 refers to the deduplication storage server node number storing this type of application file, and the data volume 235 refers to the physical data volume of the same type of application file stored on the same node . For example, in the example of the application index structure, the contents of the first and third lines match the doc type.

S23) Obtain candidate deduplication storage server node numbers: find out the deduplication storage server node numbers storing the same application type files from the application index structure, and save the result in the candidate deduplication storage server node list 236—LIST ₁ . As shown in FIG. 3 , it is found that both node 1 and node 2 store application files of doc type.

S30) Calculate the load of deduplication storage nodes: the load balancing module 204 of the backup server 200 obtains the real-time dynamic load information of each deduplication storage server 300 nodes by querying the application-aware index structure, and calculates the A list of 300 nodes of low-load deduplication storage servers capable of maintaining load balance LIST ₂ .

The step of calculating the deduplication storage node load (S30) includes:

S31) Calculate the physical capacity used by the deduplication storage server node: the physical capacity C _i of the deduplication storage server node i can be expressed as:

where i=1,2,...,N;

Among them, N is the number of server nodes in the deduplication storage server cluster, K is the number of application file types stored on node i, and C _ij is the corresponding physical data of application type j stored on deduplication storage server node i obtained by querying the application index structure. capacity;

S32) Search for low-load deduplication storage server nodes: when C _i +S<T _i , determine that node i is a low-load node, and add node number i to LIST ₂ ,

Wherein, T _i is the load threshold of the deduplication storage server node i, S is the size of the backup file, and LIST ₂ is a list of low-load deduplication storage server nodes.

S40) Select file routing nodes: the file routing decision module 203 of the backup server 200 analyzes the candidate deduplication storage server node list LIST ₁ and the low-load deduplication storage server node list LIST ₂ , and selects a low-load candidate node that stores the same type of application data Routing the target node as a file, and returning the result to the backup client 100.

As shown in Figure 4, the step of selecting a file routing node (S40) includes:

S41) Input the candidate deduplication storage server node list LIST ₁ and the low-load deduplication storage server node list LIST ₂ storing the same application file;

S42) Judging whether the intersection LIST ₁ ∩ LIST ₂ of the two node lists is empty, if yes, go to step S43, otherwise go to step S46;

S43) Determine whether the low-load deduplication storage server node list LIST ₂ is empty, if yes, go to step S44, otherwise go to step S45;

S44) Issue a warning that the load of the deduplication storage server cluster is too high, and end the processing process;

S45) Select a node from the low-load deduplication storage server node list LIST ₂ ;

S46) Select one from the low-load candidate node subset LIST ₁ ∩ LIST ₂ as the target node and return.

S50) Sending files to target nodes: the backup client 100 sends each file in the backup session to the corresponding node of the routing target deduplication storage server 300 according to the file routing decision result returned by the backup server 200 .

S60) Processing file deduplication within the node: the deduplication storage server 300 node independently performs data deduplication processing on different types of application files according to differences in the data format and content of the application files.

The data deduplication engine 301 module of the deduplication storage server node 300 independently performs data deduplication optimization on different types of application files according to the differences in the data format and content of the application files, and uses the increased physical capacity of the file storage after deduplication as a message The feedback is updated into the application index structure of the backup server 200 . The file metadata management module 302 and the data block management module 303 respectively manage the metadata (including block fingerprint index information) of the files stored on the node and the unique data blocks whose content is not repeated after deduplication.

The present invention optimizes cluster deduplication processing by developing application awareness, thereby providing a data routing technology that can take into account backup storage space saving and cluster system expansion capability improvement. The invention can be applied to network backup software, distributed file system and cloud storage system software, and can easily realize high-efficiency parallel data deduplication processing.

Of course, the present invention can also have other various embodiments, and those skilled in the art can make various corresponding changes and deformations according to the present invention without departing from the spirit and essence of the present invention. All changes and deformations should belong to the protection scope of the appended claims of the present invention.

Claims (4)

1. An application-aware data routing method for large-scale cluster deduplication, the method is implemented in a large-scale backup storage cluster system, including multiple backup clients (100), a backup server (200) and multiple deduplication A storage server (300), comprising the steps of: S10) obtain the backup file meta-information: the backup client (100) sends a file backup request message including the name of the file, the user and the file meta-information such as the size to the backup server (200); S20) Sensing file application types: the backup server (200) classifies the application types of the backup files according to the file meta information, and queries the application index structure to obtain a list of candidate deduplication storage server (300) nodes that can store corresponding types of application files; S30) Calculate the load of deduplication storage nodes: the backup server (200) obtains the real-time dynamic load information of each deduplication storage server (300) node by querying the application-aware index structure, and calculates the available load information based on these node load information and the backup file meta-information A low load deduplication storage server (300) node list for maintaining load balance; S40) select file routing nodes: the backup server (200) analyzes the list of candidate deduplication storage server nodes and the list of low-load deduplication storage server nodes, selects a low-load candidate node storing the same type of application data as the file routing target node, and The result is returned to the backup client (100); S50) Send files to the target node: the backup client (100) sends each file in the backup session to the corresponding routing target deduplication storage server (300) node according to the file routing decision result returned by the backup server (200); S60) Processing deduplication of files in the node: the deduplication storage server (300) node independently performs data deduplication processing on different types of application files according to the difference in the data format and content of the application files; It is characterized in that the step of perceiving file application type (S20) includes: S21) Obtaining file meta information: the backup server (200) obtains the file meta information in the backup request, including the name, user and size of the file, the file name includes a prefix and a suffix, and the application type is defined by the suffix; S22) Query the application index structure: query the application index structure according to the application type determined by the file name, and the application index includes index items such as application type, node number and data volume; S23) Obtain candidate deduplication storage server node numbers: find out the deduplication storage server node numbers storing the same application type files from the application index structure, and save the result to the candidate deduplication storage server node list. 2. The application-aware data routing method according to claim 1, wherein the step of calculating and deduplication storage node load (S30) comprises: S31) Calculate the physical capacity used by the deduplication storage server node: the physical capacity C _i of the deduplication storage server node i can be expressed as, where i=1,2,...,N; Among them, N is the number of server nodes in the deduplication storage server cluster, K is the number of application file types stored on node i, and C _ij is the corresponding physical data of application type j stored on deduplication storage server node i obtained by querying the application index structure. capacity; S32) Searching for a low-load deduplication storage server node: when C _i +S<T _i , determine that node i is a low-load node, and add node number i to the low-load deduplication storage server node list; Wherein, T _i is the load threshold of the deduplication storage server node i, and S is the size of the backup file. 3. The application-aware data routing method according to claim 1, wherein the step of selecting a file routing node (S40) comprises: S41) Input the candidate deduplication storage server node list LIST ₁ and the low load deduplication storage server node list LIST ₂ that have the same application file; S42) judge whether the intersection LIST1 ∩ LIST ₂ of these two node lists is empty, if so then go to step S43, otherwise go to step S46; S43) judging whether the low-load deduplication storage server node list LIST ₂ is empty, if so, turn to step S44, otherwise turn to step S45; S44) issue a warning that the load of the deduplication storage server cluster is too high, and end the processing process; S45) Select a node from the low-load deduplication storage server node list LIST ₂ ; S46) Select one of the low-load candidate node subsets LIST ₁ ∩ LIST ₂ as the target node and return. 4. A large-scale backup storage cluster system for realizing the application-aware data routing method described in claim 1, comprising multiple backup clients (100), a backup server (200) and multiple deduplication storage servers ( 300), characterized in that: The backup client (100) is used to send a file backup request message containing file meta-information such as file name, user and size to the backup server (200); The backup server (200) is used to perceive the application type of the backup file according to the file meta information, and query the application index structure to obtain a list of node numbers of the candidate deduplication storage server (300) that can store the corresponding type of application file; The backup server (200) is used to obtain the real-time dynamic load information of each deduplication storage server (300) node by querying the application-aware index structure, and calculate the low-load consumption information that can maintain load balance according to the load information of these nodes and the backup file meta-information. Heavy storage server (300) node list; The backup server (200) is used to analyze the candidate deduplication storage server node list and the low-load deduplication storage server node list, select a low-load candidate node storing the same type of application data as the file routing target node, and return the result to the backup client end(100); The backup client (100) sends each file in the backup session to the corresponding routing target deduplication storage server (300) node according to the file routing decision result returned by the backup server (200); The deduplication storage server (300) node is used to independently perform data deduplication processing on different types of application files according to the differences in the data format and content of the application files; Each backup client (100) includes a file I/O module (101) and a backup request module (102), and the backup request module (102) is used to perform a file backup session with the backup server (200), The file I/O module (101) is used for backing up each file to a corresponding deduplication storage server (300) according to the file routing decision result returned by the backup server (200); The backup server (200) includes a backup session management module (201), an application awareness process module (202), a file routing decision module (203) and a load balancing module (204), and the backup session management module (201) is used for Receive the backup request of the backup client (100), manage the files in groups according to the same backup session from the same user, and feed back the file routing decision result to the backup client (100), and the application awareness process module (202) uses For classifying files according to application types, the load balancing module (204) is used to maintain system load balance of the deduplication storage server cluster, and the file routing decision module (203) is used to distribute the same type of application files to the same The low-load deduplication storage server node feeds back the information of the file routing target node to the backup client (100), and establishes a mapping relationship from the application file to the deduplication storage server node for use when the file is restored; The deduplication storage server (300) includes a data deduplication engine (301), a file metadata management module (302) and a data block management module (303), and the data deduplication engine (301) is used to perform backup files Deduplication processing, and according to the characteristics of different applications, independently perform data deduplication on files of each application type, and the file metadata management module (302) is used to manage metadata and block fingerprint index information of files stored on nodes , the data block management module (303) is used for managing the unique data block whose content is not repeated after deduplication.