CN101814045A - Data organization method for backup services - Google Patents

Abstract

The invention discloses a backup service software storage server end data organization method, which is used for improving the data organization and data management efficiency of the storage server end. The method includes: ① initializing storage server storage space into metadata area (including main record, index header and data index) and data area; ② accepting and judging user operation commands, performing backup operations sequentially, and turning to step ④ for restoring operations, and turning to step ④ for deleting operations. Step ⑤; ③ process user backup operation, back up user data to the storage server data area, and use deduplication technology to avoid duplicate data backup; turn to step ②; ④ process recovery operation, and list the recovery data specified by the user in the storage server data Area location search, and then transfer to the client; go to step ②; ⑤ process the delete operation, find the data that the user specifies to delete, and perform corresponding processing according to the backup data block reference count of these data in the storage server data area; go to step ②. The method improves the utilization rate, manageability and system scalability of the storage server end, saves network bandwidth, and improves backup efficiency.

Description

A data organization method for backup service

technical field

The invention belongs to computer data storage and backup methods, and in particular relates to a data organization method for backup services. The method realizes the deletion of block-level repeated data.

Background technique

With the rapid development of the information society, people's daily life and business operations of enterprises are surrounded by increasingly infiltrated information systems, and their dependence is increasing. Especially in industries such as finance, communication, transportation and insurance, once key data is lost or damaged, it will bring immeasurable losses to individuals and enterprises.

The backup service mentioned here is essentially a backup and recovery software system that provides a certain disaster recovery function. It can provide individual and enterprise users with comprehensive data backup, recovery and related management tasks, and can customize various backup strategies according to their actual needs. . At the same time, the backup service here is also a software model. It builds all the network infrastructure and software and hardware operation platforms required for informatization for enterprises, and is responsible for all the early implementation and later maintenance and other services. Enterprises do not need to purchase software and hardware. , building a computer room, and recruiting IT personnel, the information system can be used through the Internet. Just like turning on the tap to get water, companies rent software services based on actual needs.

Data backup and recovery are important measures to ensure information security. The increasing importance of data requires effective and comprehensive protection of data on storage systems. With the emergence and development of new technologies such as high-speed network and communication technology and mass storage technology, basic storage resources have undergone earth-shaking changes compared with the past. The increasing application of various information systems has also increased the amount of data with protection value in a geometric progression, which has put forward higher requirements for the development of data backup and recovery software and related technical research.

When users use backup services, their storage space and data requirements usually include: the ability to increase or decrease the use of storage space according to demand; the ability to use existing space without barriers, that is, as long as there is remaining space and the network is reachable, the data backup task can be executed correctly; the backed up data can be restored at any time. In order to meet these requirements, user space and data are required to have a certain logical independence, so it is necessary to study user space management methods and backup data organization methods. In addition, it is also necessary to design an efficient space allocation and recycling mechanism to fully exploit the coupling of duplicate data storage space while maintaining the logical independence of user data and achieve efficient data search and access.

In the general backup software architecture, the storage server is a physical medium certified by the management console of the data backup software. It can be a hard disk space on the server, a storage device attached to the server, or a disk map on the network. Multiple storage servers can be configured through the management console. Under the unified management of the backup server, the backup client will back up data to the corresponding storage server.

In the design of the previous backup software storage server, most of them adopt the file-level backup method. File-level backup, that is, the backup software can only perceive the file level, and back up all the files on the source disk to another destination medium. Therefore, file-level backup software either relies on the file system interface provided by the operating system to back up files, or has the file system function itself and can identify file system metadata. In short, the mechanism of file-level backup software is to read data in units of files, and then store the read files on another medium. Obviously, this has formed a performance bottleneck for PB-level large-scale storage systems. Since the data unit managed by the storage server is a file, this inevitably results in the backup of a large amount of duplicate data, which also brings great inconvenience to the management of the storage server. , and using block-level deduplication technology for data backup can solve these problems to a large extent.

On the other hand, in the previous backup software, the storage server initially allocates a fixed amount of available storage space to users, which greatly reduces the scalability of the system. In practical applications, the system cannot predict how much storage space each user will eventually use (of course, there may be a maximum available storage capacity limit according to the user's permissions and types), and a large allocation may cause waste and utilization of storage space The rate drops, and a small allocation may bring great restrictions to the user's use.

EMC recently acquired Avamar, whose patented deduplication and global single instance storage technology ensures that backup data segments are stored globally only once. This effectively reduces the amount of data moved and restored by a factor of 300, while also enabling daily full backups and fast restores. For each 24KB data segment, Avamar generates a unique 20-byte ID, using the SHA-1 encryption algorithm. The unique ID is the fingerprint of the data segment, so Avamar's software can use the unique ID to determine whether a data segment has been stored before. However, the calculation of the SHA-1 encryption algorithm is complex and consumes a lot of CPU. At the same time, because the data segment is too small, when the user backs up a large amount of data, the fingerprint space consumed is also large, and there is still a certain scalability problem.

Contents of the invention

The purpose of the present invention is to provide a data organization method for backup service, which can realize block-level duplicate data deletion, and can improve data organization and management efficiency.

The present invention provides a data organization method for backup service, the method includes the following steps:

(1) Initialization:

Partial initialization of metadata information, including assigning initial values to index header information, data index information, and data area metadata information in the metadata area;

Pre-allocate a data space in the data area and prepare to accept the user's backup request;

(2) Receive user commands and determine the type of user commands:

Judge the user command type, if it is a backup operation, then enter step (3), if it is a recovery operation, then proceed to step (4), if it is a delete operation, then proceed to step (5);

(3) Perform backup processing according to the following process:

(3.1) First divide the file to be backed up by the user into blocks, and then use the MD5 algorithm to hash the content of the data block to obtain a fingerprint that uniquely identifies the data block, and the data block is stored in the storage server end element with the fingerprint as an index Data index header and data index;

(3.2) The fingerprint of the data block is transmitted from the backup client to the storage server, and the storage server side inquires whether the data block exists according to the fingerprint;

(3.3) If the fingerprint does not exist, then the backup client sends the data block to the storage server, then the data block is a new backup data block, and the storage server dynamically allocates storage space, and completes the storage of the new backup data block Write operation; if it exists, you only need to update the index information corresponding to the data block on the storage server, and increase its reference count by one;

(3.4) Go to step (2);

(4) When restoring, the backup server checks the Hash list contained in the file to be restored, accesses the metadata information of the storage space according to the Hash list to locate the logical position in the corresponding data space, and then reads the data of the file to be restored from the storage server in turn to the memory buffer, then pass it to the backup client through the socket, and synthesize the required file set, and then turn to step (2);

(5) Delete the backed up files according to the following procedure:

(5.1) check the Hash list that the file to be deleted comprises by the backup server in the backup system software;

(5.2) Search the index header and data index mapping table of the metadata area on the storage server side according to the Hash value, if the Hash value of the entry parameter does not exist, return immediately, and the return value is false;

(5.3) Otherwise, the reference count of the object metadata corresponding to the Hash value is decremented by 1, and the return value is true;

(5.4) Go to step (2) again.

Nowadays, enterprise data is not only diverse and fast-growing, but also highly redundant. There are many identical files or data stored in the system and between systems, and edited files also have a large amount of redundancy, which exists in the file in previous versions. Traditional backup software amplifies this redundancy by backing up this redundant data over and over again. A better solution now is to use data deduplication technology. Data deduplication technology can not only achieve high compression ratio and release storage space, but also reduce the cost of disk-based backup and data management. The present invention is a data organization and management method based on block-level deduplication technology to realize the data organization and management of the storage server. Management and data organization. The present invention can realize global deduplication without affecting the backup and recovery of main users. With the increase of the number of users and the amount of backup data, the effect of deduplication will become more obvious. It can greatly reduce the amount of data required for user backup, saving backup time, network bandwidth and storage space required for backup.

Description of drawings

Fig. 1 is the location process figure of storage data organization and data items used by the inventive method;

Fig. 2 is the block flow diagram of the inventive method;

Fig. 3 is the flowchart of dynamically allocating storage space among the present invention;

Fig. 4 is a flow chart of the write operation in the backup operation of the present invention.

Detailed ways

The present invention will be described in more detail below by means of implementation examples, but the following examples are only illustrative, and the protection scope of the present invention is not limited by these examples.

The backup service system is based on a tripartite architecture and consists of a backup server, a storage server, and a backup client. Wherein, the backup client is responsible for accepting user-customized data backup policies, recovery requests or other requests related to data management. The backup server connects the backup client and the storage server, and is the control center of the entire data backup software. It is responsible for user permission control, global job scheduling, and global storage management. When the backup client initiates a backup/restore job, the backup server guides it to establish a connection with the designated storage server and enter the execution link; on the other hand, the backup server will monitor the computing, transmission and storage pressure of each storage server, and perform load balancing Strategy. User information, storage server status and other basic metadata supporting the operation of the backup server are planned to be stored in a database. The storage server is responsible for performing backup/recovery data transmission with the client, and performs local storage space management and data organization according to the backup server's policy.

The following are the four data structures used in this example that need to be explained: main record area, index header, data index, and data area. The structure is shown in Figure 1.

Main record area: mainly describes the information of the entire storage space, which stores the following information: index header information, data index information, and data area metadata information.

Index header: It is an object hash table, which is used to realize the mapping from the object ID (160-bit Hash value generated by the data content) to the data index table. The object here is the basic unit of data storage in the storage system, which is different from the files and blocks that are the basic components in the traditional storage system. The object is a combination of application data and defined storage attributes (metadata), which contains data and other sufficient information Allow data autonomy and self-management. It uses the Hash value to represent the object ID in object-oriented storage, uses the file content as the storage basis, and establishes the mapping relationship between the content and the object through the Hash value index. Because the Hash value is globally unique in a statistical sense, it has a globally unique namespace, which improves the manageability of system sharing. The system uses the mature MD5 algorithm, and the MD5Hash algorithm transforms the data content of any length into a 128bit (16byte) large integer, namely the object ID.

Data index: It is an array with a size of N (N represents the number of indexes in the data index table, and the value range is 2 ²⁰ to 2 ³⁰ ), each element in the array is a metadata structure of an object, in the metadata structure The information includes: object ID, the starting offset address of the object in the data area (I represents the data space number, J represents the logical data block number in the data space, and K represents the offset address in the logical data block in the data space ), the size of the data corresponding to the object, the number of copies of the data content corresponding to the object, and the position in the object table of the next object that is mapped to the same position in the object hash table as the object, which maps to the object hash Objects at the same location in the table are linked into a linked list.

Data area: used to store the data of the object. The data of the object includes the object ID, the length of the data content and the data content. In order to facilitate the storage space management, the data area is divided into several continuous data spaces (each data space uses a separate data space) file), and each data space is composed of several logical data blocks.

Data block: In the backup service system, when performing backup or recovery operations, the processed data is divided into blocks according to a fixed length, and each block is a data block.

Backup data block: When the user uses the backup client to back up specified files and folders, the backup client first divides the data to be backed up into blocks according to a fixed length (the block size in the actual backup service software system is 4M), and each block block is the backup data block

Logical data block: On the storage server side, in order to facilitate management and efficiently utilize storage server storage space, each data space is divided into several sub-storage units, and each sub-storage unit is a logical data block (each logic block in the actual backup service software system The data block size is 1G)

The implementation process of this example will be further described below in conjunction with the accompanying drawings.

As shown in Figure 2, the inventive method comprises the following steps:

(1) Initialization:

Usually stored data is divided into two parts: metadata area and data area. The data actually backed up by the user is stored in the data area, and the relevant information describing these user data is stored in the metadata area. Initialize the metadata area, mainly to assign initial values to the index header information, data index information, and data area metadata information in the metadata area. Set all the index headers, that is, the object hash table, to 0, indicating that all are available, and also set each element in the data index array to zero, indicating that no data has been written at this time. And pre-allocate a data space in the data area ready to accept the user's backup request. The total number of data spaces is defined as S, and the maximum value of S cannot exceed 1000. The number of data spaces currently used by the data area is V, and V<=S. The number of logical data blocks (blocks) pre-allocated in each data space is defined as P, and the maximum value of P does not exceed 10. The maximum number of logical data blocks in each data space is defined as W, and the maximum number of W cannot exceed 1024. In our current backup service software deployment and implementation, each data space consists of 1024 logical data blocks, each logical data block has a size of 1G, and each data space has a maximum size of 1T.

(2) Receive user commands and determine the type of user commands:

Judge the user command type, if it is a backup operation, then enter step (3), if it is a recovery operation, then proceed to step (4), if it is a delete operation, then proceed to step (5);

(3) Perform backup processing according to the following process:

(3.1) First divide the file to be backed up by the user into blocks (the defined data block size is b, and the value of b is 1M---4M, and the value of b is 4M when the backup service software is actually deployed), and then divide the data The content of the block is hashed with the MD5 algorithm to obtain a fingerprint that uniquely identifies the data block, and the data block is stored in the index header and data index of the server-side metadata with the fingerprint as an index;

(3.2) The fingerprint of the data block is transmitted from the backup client to the storage server, and the storage server side inquires whether the data block exists according to the fingerprint;

(3.3) If the fingerprint does not exist, the backup client sends the data block to the storage server, dynamically allocates storage space on the storage server side, and completes the write operation of the data block; if it exists, there is no need to transmit the data, only It is necessary to update the index information corresponding to the data block on the storage server, and increase the reference count by one.

(3.4) Go to step (2);

In the above step (3.3), the storage space can be dynamically allocated according to the process shown in Figure 3, and the specific steps are as follows:

(a1) judge whether in the P logic data blocks of current data space, whether there is the remaining available space that can satisfy the designated size backup data block, if yes, enter step (a5), otherwise, enter step (a2);

(a2) Judging whether P<W is established, if established, enter step (a6), otherwise, enter step (a3);

(a3) judge whether other data spaces in the storage server master record have the remaining available space that can satisfy the backup data block of designated size, if yes, enter step (a5), otherwise, enter step (a4);

(a4) Judging whether V<S is established, if established, then increase a data space on the storage server, allocate a data index for the backup data block to be written in the new data space, and then turn to step (a8), otherwise, Go to step (a7);

(a5) allocate a data index for the backup data block to be written in the remaining free space, and then proceed to step (a8);

(a6) increase the space of a backup data block size for the data space on the storage server, then allocate a data index for the backup data block, then proceed to step (a8);

(a7) Because there is no remaining free space that can satisfy the backup data block of the specified size, the dynamic allocation is declared to be failed;

(a8) End the dynamic allocation process.

The write operation can also be completed as shown in Figure 4, and the steps are as follows:

(b1) Dynamically search for available storage space on the storage server side, and find out whether there is a logical data block that meets the conditions;

(b2) Return failure if there is no available logical data block;

(b3) If there is available storage space that meets the size of the new backup data block, create a new data index, write the new backup data block to the corresponding storage server location, and then write the corresponding index header and data index metadata into the main record area .

(4) When restoring, the backup server in the backup system software checks the Hash list contained in the file to be restored, accesses the metadata information of the storage space according to the Hash list to locate the logical position in the corresponding data space, and then reads it from the storage server in turn The file data to be restored is stored in the memory buffer, and then transmitted to the backup client through the socket, and the required file set is synthesized, and then the step (2) is performed.

As shown in Figure 2, the process of accessing the metadata information of the storage space according to the Hash list to locate the logical position in the corresponding data space is as follows:

(4.1) Let m be the number of digits of the pre-set index header, the index header is indexed by the first m bits of the data Hash value, and the content of the index header constitutes the data index number.

Usually, each index header occupies two bytes, and there are 2 ^m in total, and the value of m usually ranges from 20 to 30.

(4.2) Address the data index through the index header. The data index addresses the data items of an operation, which specifically includes three parts:

(4.2.1) Find the specific data space number by the structure member I of the data index (I is the data space number);

(4.2.2) Find the block number in the data space through the structure member J of the data index (J is the logical data block number in the data space);

(4.2.4) Find the offset address of the data item in the logical data block through the structure member K of the data index (K is the offset address in the logical data block in the data space), which is equivalent to three-level addressing. The data header and data entity of the data item can thus be located.

(4.4) After obtaining the above three-level logical data block address information, the corresponding data area can be located to read data.

(5) Delete the backed up files according to the following procedure:

(5.1) check the Hash list that the backup file to be deleted contains by the backup server in the backup system software;

(5.2) Search the index header and data index mapping table of the metadata area on the storage server side according to the Hash value, if the Hash value of the entry parameter does not exist, return immediately, and the return value is false;

(5.3) Otherwise, the reference count of the object metadata corresponding to the Hash value is decremented by 1, and the return value is true;

(5.4) Go to step (2) again.

Since we provide an online backup service, the backup server and storage server are always running in the background as daemon processes, so there is no end situation, and they are always waiting to receive user operation requests. The backup client is an operation interface for users to use the online backup service. Users can log in to the backup client at any time to perform specified operations, such as backup, recovery, and deletion.

Example:

The running support environment of the backup service system application is:

1. Hardware environment and supporting environment

The backup client requires the host to have a memory of 512M or above and a network throughput of 10Mbps or above.

The scheduling server requires the host to have a memory of 2GB or above and a network throughput of 1000Mbps or above.

The storage server requires the host to have 4GB or more memory and TB-level external storage capacity, and a network throughput capacity of 1000Mbps or more.

The scheduling server and the host where the storage server software are located have GB-level network exchange capabilities, and the client and server software hosts have network connectivity capabilities. The environment where the server host is located is required to have redundant power supply guarantee, redundant communication link guarantee, temperature control system, fire prevention system and other basic conditions to ensure the normal operation of the host.

2. Software operating environment

The backup client program runs on the Windows XP and later version operating system or the operating system platform based on the Linux 2.6 kernel.

The scheduling server and storage server run on the Windows Server 2003 operating system platform.

In the online backup service system currently implemented and running normally, the size of each data space on the storage server side is 1T, and the maximum number of data spaces is 20. Each data space is divided into 1024 logical data blocks, and the size of each logical data block is 1G.

The above description is only a preferred embodiment of the present invention, but the present invention should not be limited to the content disclosed in this embodiment and the accompanying drawings. Therefore, all equivalents or modifications that do not deviate from the spirit disclosed in the present invention fall within the protection scope of the present invention.

Claims (4)

1. a data organization method that is used for backup services is characterized in that, this method comprises the steps:

(1) initialization:

The metadata information partially-initialized comprises that indexing head information, data directory information, the data field metadata information to meta-data region composed initial value;

Prepare to accept user's backup request in data space of data field predistribution;

(2) receive user command and judge the user command type:

Judge the user command type, if backup operation enters step (3), if recovery operation then changes step (4) over to, if deletion action then changes step (5) over to;

(3) carry out back-up processing according to following process:

(3.1) file block at first that the user is to be backed up, then the content of data piecemeal is carried out Hash with the MD5 algorithm, obtain the fingerprint of a unique identification data piecemeal, deblocking is that index stores is in the indexing head and data directory of storage server end member data with the fingerprint;

(3.2) by the fingerprint of backup client to storage server transmission deblocking, whether the storage server end is inquired about this piecemeal according to fingerprint and is existed;

(3.3) if this fingerprint does not exist, then backup client transmits this deblocking and gives storage server, and then this deblocking is new Backup Data piece, in storage server end memory space dynamic allocation, and finishes the write operation of this new Backup Data piece; If exist, then only need the pairing index information of updated stored this deblocking of server end, its reference count is added one;

(3.4) change step (2) over to;

When (4) recovering, check in the Hash tabulation for the treatment of that recovery file comprises by backup server, the storage space metadata information was positioned at the logical place in the corresponding data space between tabulation was visited according to Hash, read to treat that from the storage server end recovery file data are to core buffer successively then, pass to backup client by socket then, and synthetic required file set, change step (2) again over to;

(5) delete backup file by following process:

(5.1) check in the Hash tabulation for the treatment of that deleted file comprises by backup server in the standby system software;

(5.2) search the indexing head and the data directory mapping table of the meta-data region of storage server end according to hash value, if the suction parameter hash value does not exist, then return at once, rreturn value is false;

(5.3) otherwise the reference count of the object metadata of hash value correspondence is subtracted 1, rreturn value is true;

(5.4) change step (2) again over to.

2. the data organization method that is used for backup services according to claim 1, it is characterized in that, in the above-mentioned steps (3.3), make P represent the preallocated logic data block number of each data space, W represents the largest logical data block number that can hold in each data space, the data space number that V has represented to use, S represents the data space sum;

The concrete steps of memory space dynamic allocation are as follows:

(a1) judge whether the residue free space that can satisfy the big or small Backup Data piece of appointment is arranged,, enter step (a5) in P the logic data block in current data space if having, otherwise, step (a2) entered;

(a2) judge whether P＜W sets up, enter step (a6) if set up, otherwise, step (a3) entered;

(a3) judge whether other data space in the storage server master record has the residue free space that can satisfy the Backup Data piece of specifying size, if having, enters step (a5), otherwise, step (a4) entered;

(a4) whether interpretation V＜S sets up, if set up, then increases a data space on storage server, for Backup Data piece to be written in the new data space distributes a data index, changes step (a8) then over to, otherwise, enter step (a7);

(a5) for Backup Data piece to be written in the residue free space distributes a data index, change step (a8) then over to.

(a6) on storage server, increase the space of a logical data block size, for data index of Backup Data piece distribution, change step (a8) then over to again for this data space;

(a7) announce the dynamic assignment failure;

(a8) finish dynamic allocation procedure.

3. the data organization method that is used for backup services according to claim 1 is characterized in that write operation comprises the steps:

(b1) dynamically seek free memory at the stores service end, search whether the logic data block that satisfies condition is arranged;

(b2) if do not have the utilogic data block then return failure;

(b3) if the free memory that satisfies new Backup Data block size is arranged, this creates a new data index, and new Backup Data piece is write the respective stored server location, then respective index head and data directory metadata is write the master record district.

4. the data organization method that is used for backup services according to claim 1 is characterized in that, the process that is positioned at the logical place in the corresponding data space according to storage space metadata information between Hash tabulation visit is as follows:

(4.1) according to the figure place m of predefined indexing head, indexing head is carried out index, the content composition data call number of indexing head by the preceding m position of data hash value;

(4.2) by indexing head to the data indexed addressing, by data directory the data item of single job is carried out addressing again, specifically comprise three partial contents:

(4.2.1) find concrete data space number by the data space among the structure member of data directory numbering;

(4.2.2) find piece number in the data space by the logical data block number in the data space among the structure member of data directory;

(4.2.4) find the offset address of data item in logic data block, the data head of locator data item and data entity by the offset address in the logic data block in the data space among the structure member of data directory;

(4.4) utilize the address information that obtains, navigate to corresponding data field reading of data.

Images