CN100547555C - A Data Backup System Based on Fingerprint - Google Patents

Abstract

A fingerprint-based data backup system belongs to the technical field of computer storage backup, and aims at reducing the management, storage and network overhead of data backup and improving backup performance. The present invention includes a backup server, a backup agent, a storage server and a Web server, and they communicate with each other through the network to complete data backup and recovery; the present invention adopts the anchor-based file segmentation technology to identify redundant data of backup files, which has modification stability and calculation The overhead is small; the data blocks are stored on the disk array of the storage server with their fingerprints as the index, eliminating the backup of redundant data and saving disk storage space; once the data blocks are stored, they will not be erased and can be continuously added to the disk , Eliminate disk storage fragmentation; adopt effective backup buffer strategy, reduce backup network overhead, improve data backup speed, and reduce the impact of backup on application servers.

Description

A Data Backup System Based on Fingerprint

technical field

The invention belongs to the field of computer storage backup, and in particular relates to a data backup system.

Background technique

In today's information age of knowledge explosion, data is a precious resource for both enterprises and individuals. Data loss can affect the business continuity of the enterprise, causing it to lose a temporary competitive advantage, or it can cause a company to go bankrupt. There are many reasons for data loss, including system software and hardware failures, human error or destruction, and force majeure (natural disasters, wars), etc. In order to protect the data from accidents, the traditional method is to periodically copy the data to removable media such as tapes and optical discs, and then transport them offline to a relatively safe place so that the data can be restored when necessary. It should be pointed out that there are some obvious disadvantages in this traditional data protection method: (1), removable storage media such as tapes, optical discs, etc. will wear out or be damaged as time goes by, so that their storage reliability will be reduced, so they are not suitable for storage. Long-term storage medium for data. (2) As a common storage medium for backing up large-capacity data, the reading and writing speed of magnetic tape is often very slow, and because it is a sequential storage device, frequent mechanical rewinding operations usually occur when restoring data. If the backup data is distributed in On several tapes, time-consuming loading and unloading operations are also required. This makes data backup and recovery using tape a time-consuming task. (3) It is necessary to hire a special person to transport the backup data to the remote site, and ensure the data security during transportation and storage. It can be seen from this that traditional data backup requires manual intervention to complete many tasks, which is a costly and tedious task. In order to improve the efficiency of data backup and recovery and overcome the shortcomings of traditional data protection technologies, some well-known IT companies or research institutions in the world have developed various data backup systems in the past two decades. Including IBM's TotalStorage, HP's OpenView storage mirroring software, CASA, XPCA and EVACA, EMC's SRDF and MirrorView, VERITAS's NetBackup and so on. These commercial systems do not have the function of deduplication. In order to store a large amount of redundant data generated in backup, it is often necessary to use disk-to-tape (D2T) technology, that is, to use high-speed disks as backup buffers to improve online backup efficiency, and then transfer them in the background. The backup data in the disk buffer is migrated to low-speed and large-capacity storage media such as tape library or optical disk library, so the background storage device still needs a lot of manpower and material resources for daily maintenance. Because disk storage has the advantages of convenient management and fast access speed compared with tape storage, with the development of disk storage technology, more and more attention has been paid to the backup system using disk storage data. The current disk storage technology can easily build a TB or even PB disk storage system. The ever-increasing price per bit of disk storage has made permanent archiving of data on disk a reality. For a disk-based data backup system, there are many advantages of permanently storing backup data on the disk without erasing: first, data can be continuously written to the disk, and disk fragmentation will not occur due to space reclamation; The data history is completely preserved, and the user can easily browse any historical version of the file. Third, it is beneficial to protect the user's backup data and prevent the user from deleting important data due to misoperation. However, for a permanent storage disk-based backup system, the biggest challenge comes from users' ever-increasing backup data. Usually, enterprise data has a high degree of redundancy, a large number of duplicate data and files are stored in the system, and there are also a lot of duplicate content among multiple edited versions of a file. The currently widely used file-based backup technology cannot identify redundant data between files, resulting in more and more duplicate data being backed up to the system, which not only reduces the disk space utilization of the backup system, but also transmits a large amount of data through the network for no reason. Redundant data increases the network overhead of data backup and prolongs the data backup time.

It can be seen that it is of positive significance to develop a disk-based backup system for permanent storage, and to use new data backup technology to clear redundant backup data and improve system storage efficiency.

Contents of the invention

The present invention proposes a data backup system based on fingerprints. The system uses disks to permanently store backup data and uses fingerprint-based data backup technology to delete redundant data in the backup. The purpose is to reduce the management, storage and network overhead of data backup and improve backup performance.

A kind of fingerprint-based data backup system of the present invention comprises backup server, backup agent, storage server and Web server, they complete data backup and recovery through network mutual communication, it is characterized in that:

The backup server is equipped with a configuration file and a directory database. The user-defined job object is recorded in the configuration file of the backup server. The job object includes the attributes of the specified system operation job operation. The backup server controls the entire data backup and recovery process through the job object. ;The directory database stores job records, and the job records save the management information of the operation of the job object;

The backup agent is installed on each host that needs to back up data in the network. When backing up, the backup agent reads the file to be backed up from the file system of the host where it is located, performs anchor-based segmentation on the file and calculates the fingerprint of the block , and send the fingerprint and part of the required block data to the storage server through the network; when restoring, the backup agent receives the file data from the storage server through the network and writes it to the specified directory in the file system of the host; the backup agent performs anchor-based The chunking steps are:

(1) Take the first 48 bytes b ₁ , b ₂ ,..., b ₄₈ of the file as a window, and use the formula H ₁ =(b ₁ *p ⁴⁷ +b ₂ *p ⁴⁶ +...+b ₄₈ ) mod M calculates the hash value of the first window of the file; where p is 17, M is 2 ³² , and the hash value is stored in the variable H ₁ ;

(2) Slide one byte backward, calculate the second window b ₂ , b ₃ ,..., b ₄₉ of the file with the formula H ₂ =(p*H ₁ +b ₄₉ -b ₁ *p ⁴⁸ )mod M The hash value of is stored in the variable _H2 ;

(3) By analogy, calculate the hash values of all windows of the file;

(4) For the hash value of each window, take its lower 13 bits to form a binary number. If the number is equal to 61, then determine the corresponding window as an anchor, and use the anchor as the boundary to divide the file into data of different sizes piece;

The storage server is equipped with a large-capacity disk array, and the large-capacity disk array is the destination of data backup. When backing up, it receives fingerprints or data blocks from the corresponding backup agent through the network, stores the data blocks on the disk, and creates a file index; when restoring, the file is reconstructed from the large-capacity disk array according to the file index, and the file data is sent to the corresponding backup agent through the network;

The Web server is the B-S mode web page user management interface of the system. By logging into the Web server, the user can designate the system to complete interactive backup or restore jobs, monitor the operation of the system's automatic scheduling type job, and can also modify the settings of the backup server. Configure files, customize job objects, and manage devices.

The fingerprint-based data backup system is characterized in that the backup server includes a backup server initialization module, a command monitoring module, a command processing module, a job processing module and a network communication module;

The backup server initialization module performs initialization work, including reading configuration files, establishing resource linked lists in memory, checking directory database status, ensuring data consistency and integrity of configuration files and directory databases, starting command monitoring ports, accepting data from Web User commands of the server, initializing the job queue and user command queue, loading job objects into the job queue, starting jobs and network monitoring services;

The command monitoring module is a network monitoring thread generated by the system, which authenticates the connection request of the Web server, ensures that only the Web server authorized by the system can connect to the system, and monitors the command request sent by the authenticated Web server; When a command request is received, add the command request to the user command queue and wait for the system to process it;

The command processing module includes a user command queue and N command worker threads. When the user command queue overflows, the command monitoring module goes into a sleep state; these command worker threads constantly read and execute commands from the user command queue, according to the Different execution commands perform different functions; when the command monitoring module adds a command to the user command queue, if there is no idle command worker thread and the number of active command worker threads does not reach N, a new command is generated Worker thread; the command worker thread checks the status of the command monitoring module every time it reads a command from the user command queue, and wakes it up if it is in a sleep state;

The job processing module includes a job queue, L job working threads and a job queue loading thread, when the job queue overflows, the job queue loading thread enters a sleep state; the job working thread constantly gets the job object from the job queue and executes , call different resources and implement different functions according to different job object attributes; the job queue loads threads to perform job scheduling, checks the scheduling policy attributes of each job object in the job resource chain, and adds the job objects that need to be scheduled to run into the job queue , if there is currently no idle job worker thread and the number of active job worker threads does not reach L, a new job worker thread is generated; every time a job worker thread reads a job object from the job queue, it checks the job queue loading The state of the thread, waking it up if it is asleep;

The network communication module encapsulates a standard network communication application programming interface, provides a network communication interface to the command worker thread and the job worker thread, and the network communication interface realizes the data transmission protocol between the backup server, the backup agent and the storage server.

The fingerprint-based data backup system is characterized in that the backup agent includes a backup agent initialization module, a request monitoring module, a job processing module, a file block module and a network communication module;

The backup agent initialization module performs initialization work, including reading the backup agent configuration file, establishing a memory resource linked list, initializing the job queue, and starting the backup server request monitoring module;

The request monitoring module monitors the connection request of the backup server on the network, authenticates the connected backup server, and generates a network connection socket to communicate with the backup server and join the job queue after passing the authentication;

Described job processing module comprises a job queue and M job worker threads, when job queue overflows, request monitor module to transfer to sleep state; After job worker thread takes out a network connection socket from job queue, at first establishes for job A job control record, which links the network connection socket into the member variable of the job control record, and then interacts with the backup server through the network connection socket, and assigns the relevant attributes of the backup server job object to the job control record after transformation The corresponding member variable; then use the job ticket obtained from the backup server to connect to the corresponding storage server, generate a network connection socket for communication with the storage server and link it into the member variable of the job control record; when the request monitor When the module adds a network connection socket to the job queue, if there is no idle job worker thread and the number of active job worker threads does not reach M, a new job worker thread is generated; the job worker thread starts from When fetching a network connection socket in the job queue, check the status of the request monitoring module, and wake it up if it is in a sleeping state;

The file chunking module accepts the command of the job worker thread in the job processing module to execute the file chunking task of the backup job, opens each file in the file set on the client file system, performs anchor-based chunking on the file and calculates the chunking task. Block fingerprints, coordinating with the corresponding storage server to execute the backup algorithm of the first backup process;

The network communication module is composed of job network connection sockets, and each job of the backup agent has two network connection sockets, which are respectively used for communication with the backup server job and the storage server job corresponding to the job.

The fingerprint-based data backup system is characterized in that the storage server includes a storage server initialization module, a connection monitoring module, a job ticket table, a job processing module and a network communication module, as well as an index buffer, a block buffer, block hash table and disk log;

The storage server initialization module performs initialization work, including parsing the storage server configuration file, establishing a memory resource list, and starting related service threads;

Described connection monitoring module monitors the connection request of backup server and backup agent, and the backup server of connection is authenticated, and after authentication is passed, generate a network connection socket and communicate with this backup server and join in the job queue; To the backup agent of connection, Check the job ticket table according to the job ticket it presents to authenticate it, and generate a network connection socket to communicate with the backup agent and link to the member variable of the corresponding job control record after the authentication is passed;

The job ticket table is used to store a ticket for authenticating the backup proxy job;

Described job processing module comprises a job queue and W job worker threads, and when job queue overflows, connection monitor module changes over to " reject backup server connection request " state; Job worker thread takes out a network connection socket from job queue Finally, first create a job control record for the job, link the network connection socket into the member variable of the job control record, and then interact with the backup server through the network connection socket, and transfer the relevant attributes of the backup server job object through transformation Afterwards, it is assigned to the corresponding member variable of the job control record, and a job ticket ticket is randomly generated and registered in the job ticket table, and the job ticket ticket is sent to the job object of the backup server; when the connection monitoring module adds a network connection socket to the job queue word, if there is no idle job worker thread and the number of active job worker threads does not reach W, a new job worker thread is generated; every time the job worker thread fetches a network connection socket from the job queue Check the state of the connection monitoring module, if it is in the state of "rejecting the backup server connection request", cancel this state so that it accepts the backup server connection request;

Described network communication module is made up of the network connection socket of job, and each job of storage server all has two network connection sockets, is respectively used for and the backup server job corresponding to this job and backup agent job communication;

The index buffer is the infrastructure for the storage server job to execute the first backup process and the second backup process. The index buffer is implemented as a memory hash table and is used to store the job instance Job _x (t _n ) in the job chain. All the fingerprints contained in the previous job instance Job _x (t _n-1 ) and the newly generated fingerprints during the running of this job;

The block buffer is the infrastructure for the storage server job to execute the first backup process and the second backup process. The block buffer is implemented with an independent disk array to temporarily store its fingerprints in the index buffer during the first backup process. Data blocks not found in the zone;

The block hash table is the infrastructure for the storage server job to execute the second backup process. The block hash table is implemented with an independent disk array, and is used to establish the block fingerprint to the storage address of the block in the disk log. mapping;

The disk log is the infrastructure for the storage server job to execute the second backup process, and the disk log is implemented as an independent disk array to store data blocks and file indexes stored in blocks.

The advantages of the present invention are:

1. Use the anchor-based file block technology to divide the file into blocks of variable length to identify redundant data within the file or between files. It has modification stability. The modification of a file only affects the adjacent data in the modification area. block, the boundaries of other data blocks will not move. In this way, when incrementally backing up a file, only a few data blocks that have been modified need to be backed up, and other data blocks can be shared with the previous backup file; using window sliding calculation, the calculation overhead is small.

2. The data block is stored on the disk array of the storage server with its fingerprint as an index, and the data storage address is associated with the content, which changes the traditional concept of separating the data storage address and content, eliminates the backup of redundant data, and saves disk storage space;

3. Once the data block is stored, it will not be erased, and the data block can be continuously appended to the disk, eliminating disk storage fragmentation; the user's data history is completely preserved, and the user can easily browse any historical version of the file; Avoid user misoperation and delete important data.

4. Adopting an effective backup buffer strategy reduces the network overhead of backup, improves the data backup speed, and reduces the impact of backup on the application server.

Description of drawings

Fig. 1 is a structural representation of the present invention;

Fig. 2 is a schematic diagram of the structure of the backup server;

Fig. 3 is a schematic diagram of the backup agent structure;

FIG. 4 is a schematic structural diagram of a storage server;

Fig. 5 is the storage diagram of file on the disk log;

Fig. 6 is a schematic diagram of multiple file sharing data blocks/index blocks on the disk log;

Fig. 7 is the index buffer structural diagram of the present invention;

FIG. 8 is a schematic diagram of file segmentation in the anchor-based file segmentation technology.

Detailed ways

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

1. The overall structure of the system

Fig. 1 is a schematic diagram of the system system of the present invention. The present invention includes a backup server, a backup agent, a storage server and a Web server, which communicate with each other through a network to complete data backup and recovery.

Figure 2 is a schematic diagram of the backup server structure; the backup server includes a backup server initialization module, a command monitoring module, a command processing module, a job processing module and a network communication module; configuration files and a directory database are also installed.

The backup server is the command center of the entire network backup system, and it controls the entire process of data backup and recovery through job objects. The job object of the backup server provides a window for the user to customize the backup/restore job. A job object contains a number of attributes that specify how the system handles the job run. For example, the backup proxy attribute specifies which host the job will back up/restore data from; the file set attribute specifies the directory to be backed up/restored by the job; the scheduling policy attribute specifies the system scheduling strategy for the job to run, and so on. Denote a job object as Job _x , and when the job object is scheduled to run at time t, a running instance Job _x (t) is generated. The job object Job _x is composed of a sequence of running instances Job _x (t ₀ ), Job _x (t ₁ ), ... Job _x (t _n ) (t ₀ <t ₁ <...<t _n ) in chronological order A job chain of this job object is recorded as Job _x (t ₀ , t ₁ ,...t _n ). The backup server also maintains a directory database for recording the management information of Job _x (t). Specifically, the management information of Job _x (t) is stored in the job record Job _x (t).Record of this job in the directory database.

Directory database: used to store the management information of job operation, that is, Job _x (t).Record. Job _x (t).Record mainly stores the root block of the files included in this job, the fingerprint file Job _x (t).FF, etc. of this job. Each completed job Job _x (t) saves a fingerprint file Job _x (t).FF in the directory database, and Job _x (t).FF stores all fingerprints contained in the job Job _x (t). Job _x (t _n ).FF is used to initialize the index buffer of the job Job _x (t _n+1 ).

Figure 3 is a schematic diagram of the backup agent structure; the backup agent includes a backup agent initialization module, a request monitoring module, a job processing module, a file block module and a network communication module.

Figure 4 is a schematic diagram of the storage server structure; the storage server includes a storage server initialization module, a connection monitoring module, a job ticket table, a job processing module, and a network communication module, as well as an index buffer, a block buffer, a block hash table, and a disk log .

The storage server manages a large-capacity disk array (RAID) to store data blocks. Chunks are stored on the disk array indexed by their fingerprints. Once the data blocks are written to the disk, they will not be erased, so that the entire disk array is like a log, and the data blocks are appended to the disk without intervals, eliminating the fragmentation of disk storage. The disk used to store chunks of data is called a disk journal. The storage server uses a dedicated disk array to store the block hash table, and the block hash table is used to establish a mapping from the block fingerprint to the storage address of the block in the disk log. All data blocks of a backup file are indexed through index blocks, and all index blocks of a file form an index tree. At the same time, each file has a unique block called the root block, which stores the index of the root of the index tree of the file, and the metadata and some management information of the file are also stored on the root block. The file's root block and index blocks are also stored as data blocks on the disk journal. The storage server adopts the backup buffer strategy to improve the data backup speed of the system. Specifically: (1) Use the memory index buffer to store all the fingerprints contained in the previous job instance Job _x (t _n-1 ) of this job instance Job _x (t _n ) in this job chain and the new fingerprints during the running of this job. Generated fingerprints. (2) A dedicated disk array is used as a block buffer to temporarily store data blocks whose fingerprints are not found in the index buffer during the backup process. (3) The backup process of a job is completed in two phases, and these two phases are recorded as the first backup process and the second backup process respectively. In the first backup process, the backup agent and the storage server interact with each other to complete the backup of the file blocks, use the index buffer to find the block fingerprints, and use the block buffer to store the data blocks whose fingerprints are not found in the index buffer search process. For the backup agent, the backup process of the job ends after the first backup process is completed. Because this process uses the memory index buffer for fingerprint query, eliminating the time-consuming block hash table query, so the speed is very fast. The second backup process is run by the storage server when the system is relatively idle. This process transfers the data temporarily stored in the block buffer to the disk log in blocks, and uses the block hash table for fingerprint query. This process also builds an index tree of files on the disk journal. Since the second backup process is independently completed by the storage server in the background, it has no impact on the application server running the backup agent. When restoring a file, the storage server reconstructs the file according to the file index and sends the file data to the corresponding backup agent through the network.

Web server: the present invention adopts B-S mode to provide a web page user interface. Users can log in to the management interface of the system through a web browser at any place to specify the system to complete interactive backup or recovery jobs, monitor the running status of the system's automatic scheduling jobs, customize jobs, configure backup servers, and perform device management.

2. Storage server disk log

In the present invention, the backup data block is stored on the disk log of the storage server with its fingerprint as an index. This ensures that no two identical blocks are stored on disk at the same time, thereby eliminating redundant data backups. Once the block is stored, it will not be erased, so that the block can be continuously appended to the disk log, eliminating disk storage fragmentation. The data block to which the backup file belongs is indexed by the index block. Index blocks for files are also stored on the disk journal.

2.1, block header

For aspect management, each data chunk is preceded by a chunk header. Block headers provide the necessary information for system management, including integrity checks, file indexing, and block hash table reconstruction. The block header is 39 bytes in total and consists of the following parts:

magic: 6-character block header flag;

fingerprint: the fingerprint of this block, a total of 20 bytes;

type: the type of the data block, there are three different types of data blocks, namely the data block, the index block and the root block of the file, respectively recorded as: dc, ic, rc;

size: The size of this data block, not including the block header. For the index block, the system stipulates that its size cannot exceed 16KB;

offset: The storage address of this data block on the disk log.

2.2, file index

Figure 5 shows the storage structure of files on the disk log. The data block to which the file belongs is indexed by the index block, and the index block is also stored on the disk log. All index blocks of a file form an index tree; each file has a unique root block stored on the disk log, and the root The block stores the index of the root of the file index tree, and also stores the metadata of the file and some management information of the file. After the file backup is completed, its root block is also stored in the job record of the directory database as the management information of the job. In Fig. 5, F ₀ represents a file, D _i represents a data block, I _i represents an index block, an index block is composed of index items, P(X) represents an index item, and it is a triple <H(X), offset, type>, where X is the indexed data block, H(X) represents the fingerprint of data block X, offset represents the storage address of data block X on the disk log, type represents the type of data block X, X can be an index block I _i or a data block D _i , the arrows in the figure indicate the corresponding relationship between the indexed block and its index items, and M(F ₀ ) indicates the metadata and some management information of the file F ₀ , index block I ₀ , I ₁ and I ₂ constitute the index tree of file F ₀ , index block I ₀ is the root of this index tree, R ₀ represents the root block of file F ₀ , which consists of M(F ₀ ) and a An index entry P(I ₀ ) pointing to the root I ₀ of the index tree of the file. All data blocks and index blocks on the disk log can be shared by different files. FIG. 6 shows the situation that different files share data blocks and index blocks. The meanings of the symbols in the figure are the same as those in FIG. 5 .

3. Storage server block hash table

The block hash table of the storage server in the present invention is used to establish the mapping from the block fingerprint to the storage address of the block in the disk log, and the block hash table is composed of buckets of the same size. The number of buckets contained in the block hash table is determined according to the size of the disk log. The larger the capacity of the disk log, the more buckets the block hash table contains, so as to reduce the probability of hash collision of the buckets. probability. According to the number of buckets in the hash table, the system takes the first n digits of the fingerprint as the bucket number and maps the fingerprint to the corresponding bucket in the hash table. Each fingerprint is stored in the bucket in the form of triple <fingerprint, offset, type>, where fingerprint represents the fingerprint of this block, offset represents the storage address of the block corresponding to this fingerprint on the disk log, and type represents this fingerprint The corresponding block type. If a bucket has a hash collision, the triplet of the fingerprint is stored in an adjacent bucket.

4. Storage server index buffer

Figure 7 shows the structure of the index buffer. The index buffer is a memory hash table, which consists of a bucket group and many data linked lists. The bucket group has a total of 1024*1024 buckets. The number of the bucket is from 00000H to FFFFFH. The bucket may be empty. If the bucket is not empty, the inside Contains a pointer to the data linked list, corresponding to a data linked list, and the entries of the data linked list store the fingerprint information that is hashed into the bucket. When hashing, take the first 20 bits of the fingerprint as the bucket number and hash the fingerprint into the data linked list pointed to by the corresponding bucket.

The entry structure of the data linked list is:

tag: identifier, occupying 4 bits, used to indicate the state of this fingerprint in the first backup process and the second backup process;

fingerprintTail: the last 140 bits of the fingerprint of this block, because the first 20 bits are implied in the bucket number, so only the last 140 bits of the fingerprint need to be stored here;

offset: storage address, occupying 64 bits, if this item is not empty, it means the storage address of the data block corresponding to this fingerprint in the disk log;

next: occupies 32 bits, and points to the pointer to the next entry.

"One fingerprint" in Figure 7 shows a fingerprint 7E54F36A4EC62...3B is hashed into the index buffer, step (1) uses the first 20 bits of the fingerprint "7E54F" as the bucket number (bucketNo) to find the number 7E54FH Bucket, step (2) finds the entry whose fingerprintTail is "36A4EC62...3B" in the data link list pointed to by this bucket. If found, it indicates that the fingerprint 7E54F36A4EC62...3B has been stored in the index buffer. If not found, create A new entry stores information about this fingerprint.

The tag of the data link list entry in the index buffer has three different values, the meanings of which are as follows:

0000: The fingerprint comes from the fingerprint file of the previous job, and is not hit during this backup process;

1000: The fingerprint comes from the fingerprint file of the previous job and is hit during this backup process;

1100: The fingerprint is newly generated during this backup.

After a backup job Jobx(t _n-1 ) is completed, all fingerprints contained in this job are represented by the binary group <fingerprint, offset> (where fingerprint represents the fingerprint of the block, and offset represents the storage address of the block on the disk log) The form of is saved in the file Jobx(t _n-1 ).FF, and the file Jobx(t _n-1 ).FF is stored in the job record Jobx(t _n-1 ).Record of the directory database. Jobx(t _n-1 ).FF is used to initialize the index buffer of job Jobx(t _n ). Since adjacent jobs in the same job chain usually share a large number of files or data, using Jobx(t _n-1 ).FF to initialize the index buffer of job Jobx(t _n ) will improve the fingerprint hit rate of the buffer.

5. Backup process

For convenience, the following notations are defined:

BS: backup server job worker thread;

BA: backup agent job worker thread;

SS: storage server job worker thread;

F: a file;

H: a fingerprint;

M(F): metadata of file F;

R(F): the root block of file F;

H(D): the fingerprint of data block D;

D(H): the data block/index block corresponding to fingerprint H;

F.Index: build the memory buffer of the index tree of file F;

index cache: index buffer;

chunk cache: block buffer;

hash table: block hash table;

Job _x (t _n ).FileSet: the file set of the job object Job _x (t _n );

I(F, level): A collection of index blocks contained in the level of the index tree F.Index. The leaf of the index tree is defined as level 0, the parent node of the leaf node is the first level of the tree, and so on.

I _w (F, level): I(F, level) is currently used to store the working node of the triplet <H, offset, type>;

<H, offset, type>: triplet, H: fingerprint, offset: storage address of block D(H) on the disk log, type: type of block D(H);

5.1, the first backup process

The first backup process is mainly completed by the cooperation of the backup agent job worker thread and the storage server job worker thread, and its steps are:

(1) SS: use Job _x (t _n-1 ).FF to initialize index cache;

(2) BA: if (Job _x (t _n ).FileSet is empty) turn to (20), else read a file F _i from Job _x (t _n ).FileSet;

(3) BA: send M(F _i ) to SS;

(4) SS: Cache M(F _i ) to the chunk cache;

(5) BA: perform anchor-based file segmentation on F _i ;

(6) BA: Calculate the fingerprint of each block and send the fingerprint set composed of these fingerprints to SS;

(7) SS: if (fingerprint set is empty) turn to (17), else take out a fingerprint H _j from the fingerprint set and query this fingerprint in the index cache;

(8) SS: if (fingerprint H _j found in index cache) {

(9) SS: if(tag==0000){tag=1000; cache <H _j , offset> to chunkcache;}

(10) SS: else if (tag==1000) cache <H _j , offset> to chunkcache;

(11) SS: else if (tag==1100) cache <H _j , null> to the chunk cache;}

(12) SS: else {cache H _j to index cache, tag=1100, offset=null;

(13) SS: request BA to transmit D(H _j );

(14) BA: Send D(H _j ) to SS;

(15) SS: Cache <H _K , D(H _K )> to the chunk cache;}

(16) SS: return to step (7);

(17) SS: notify BA to back up the next file;

(18) BA: return to step (2);

(19) BA: Report the end status of Job _x (t _n ) to BS and SS and exit.

(20) SS: after receiving the job end signal from BA, end the first backup process and turn to the second backup process;

(21) BS: After receiving the job end signal from BA, it disconnects from BA, and waits for SS to execute the second backup process.

5.1.1 Anchor-based file chunking

In the step (5) of the first backup process, based on the anchor, the file segmentation is completed by the backup agent job worker thread calling the backup agent file segmentation module, and its steps are:

(1) Take the first 48 bytes b ₁ , b ₂ ,..., b ₄₈ of the file as a window, and use the formula H ₁ =(b ₁ *p ⁴⁷ +b ₂ *p ⁴⁶ +...+b ₄₈ )mod M computes the hash of the first window of the file. In the above formula, p is a certain prime number, which can be 17, and M is a constant, which can be 2 ³² . The hash value is stored in variable _H1 .

(2) Slide one byte backward, calculate the second window b ₂ , b ₃ ,..., b ₄₉ of the file with the formula H ₂ =(p*H ₁ +b ₄₉ -b ₁ *p ⁴⁸ )mod M The hash value of is stored in variable _H2 .

(3) By analogy, calculate the hash values of all windows of the file.

(4) For the hash value of each window, take its lower 13 bits to form a binary number, if this number is equal to a predetermined number (such as 61), then determine its corresponding window as an anchor, with the anchor as the boundary Divide the file into chunks of varying sizes.

The above-mentioned anchor-based file chunking follows the following three conventions: a) If the file is smaller than 48 bytes, the anchor-based file chunking algorithm will be exited, and the entire file is a data block; b) If a byte stream contains If there are too many anchors, some anchors are discarded so that the smallest block is not less than 2KB (a block at the end of the file is the only block that may be smaller than 2KB); c) if there are no anchors in the continuous 64KB byte stream, Then take this 64KB as a block;

In the present invention, the anchor-based file segmentation has the following two characteristics: (1) has modification stability, that is to say, the modification of a file only affects the adjacent data blocks in the modification area, and the boundaries of other data blocks will not occur move. In this way, when a file is incrementally backed up, only a few data blocks that have been modified need to be backed up, and other data blocks can be shared with the previous backup file. The modification stability also ensures that the similarity of data within files and between files will not be missed due to bit offsets, thereby maximally detecting duplicate data in files. (2) The sliding window has the advantage of convenient calculation, and the hash value of the next window can be easily calculated from the hash value of the previous window, so that the anchor-based file partitioning has the advantage of small computational overhead, The time complexity of the whole algorithm is O(n), where n is the number of bytes contained in the file.

Fig. 8 shows the change of the block of a file when the file is edited after block. It can be seen from the figure that the anchor-based file partitioning has modification stability, that is to say, the modification of a file only affects the adjacent data blocks in the modification area, and the boundaries of other data blocks will not move. Line a shows that a file is divided into 8 blocks of different sizes from B ₁ to B ₈ by anchors, and the part with teeth on the border of each block is a 48-byte anchor. The behaviors b, c, and d show the changes in blocks after the 1st, 2nd, and 3rd modification of the file, and the shaded part is the modified part. Line b: the first modification to the file occurs in block B ₄ , no new block is generated after the modification, only block B ₄ becomes block B ₉ , and other blocks are not changed. At this time, the file backup only needs to back up the block B ₉ to replace the original block B ₄ in the past. Line c: the second modification to the file occurs in block B ₅ , a new anchor is generated after the modification, and block B ₅ is divided into two blocks B ₁₀ and B ₁₁ , and other blocks are not changed. At this time, the file backup only needs to back up blocks B ₁₀ and B ₁₁ to replace the original block B ₅ . Line d: The third modification to the file occurs at the boundary between blocks B ₂ and B ₃ , as a result, the anchor between B ₂ and B ₃ is lost, and the two blocks are merged into one block B ₁₂ . At this time, the file backup only needs to back up the block B ₁₂ to replace the original blocks B ₂ and B ₃ .

5.2, the second backup process

The second backup process is mainly completed by the storage server job worker thread when the system is relatively idle, and the steps are as follows:

(1) SS: if (Job _x (t _n ).FileSet is empty) turn to (19), else get a file name F _i from Job _x (t _n ).FileSet;

(2) SS: Create a memory buffer F _i .Index for the file F _i , and create R(F _i ) in F _i .Index, and then save M(F _i ) in the chunk cache to R(F _i ) ;

(3) SS: if (there is no tuple related to F _i in the chunk cache) turn to (14), else read a tuple related to F _i from the chunk cache;

(4) SS: if (is <H _j , offset>), go to step (12);

(5) SS: else if (is <H _j , D(H _j )>){

(6) SS: query H _j in the hash table;

(7) SS: if (found) write the "offset" value into the table entry corresponding to H _j in the index cache, then go to step (12);

(8) SS: else {append D(H _j ) to the disk log, and update the hash table at the same time;

(9) SS: Write the "offset" value into the entry corresponding to H _j in the index cache, and go to step (12);}}

(10) SS: else if (is <H _j , null>)

(11) SS: read the "offset" value from the entry corresponding to H _j in the index cache;

(12) SS: insert(<H _j , offset, dc>, 0, F _i .Index);

(13) SS: return to step (3);

(14) SS: storeRemain(F _i .Index, R(F _i ));

(15) SS: Append R(F _i ) to the disk log and update the hash table at the same time;

(16) SS: Send R(F _i ) to BS;

(17) BS: transfer R(F _i ) to the directory database and store it in Job _x (t _n ).Record;

(18) SS: return to step (1);

(19) SS: create the file Job _x (t _n ).FF;

(20) SS: read index cache, write <H, offset> to the file Job _x (t _n ).FF for each entry that meets the conditions (tag==1000 ortag==1100);

(21) SS: Send the file Job _x (t _n ).FF to BS;

(22) BS: transfer the file Job _x (t _n ).FF to the directory database and store it in Job _x (t _n ).Record;

(23) SS: report the end status of the job Job _x (t _n ) to the BS;

(24) BS: interrupt the connection with SS, write the end status of the job Job _x (t _n ) into the Job _x (t _n ).Record of the directory database, and end the operation of the job Job _x (t _n ).

In the above algorithm, the algorithms of the two functions of steps (12) and (14) are as follows:

Step (12) Algorithm

insert(<H, offset, type>, level, F. Index)

{//Store triple <H, offset, type> to F.Index.

//level: Stores the layer number of the index node of the triple <H, offset, type> in the index tree F.Index.

{ create _Iw (F, level); store <H, offset, type> into _Iw (F, level); return; }

else if(I _w (F, level) is not full)

{ store <H, offset, type> into I _w (F, level); return; }

else if(I _w (F, level) is full)

{ compute H(I _w (F, level));

Query H(I _w (F, level)) in the hash table;

if not found

Append I _w (F, level) to the disk log and update the hash table at the same time;

insert(<H(I _w (F, level)), offset, ic>, level+1, F.Index);

Create a new index node I _w (F, level);

store <H, offset, type> into I _w (F, level); return;

}

}

Step (14) Algorithm

storeRemain(F.Index, R(F))

{//Store the working index nodes of each layer in F.Index to the disk log.

int level:=0;

loop: Calculate H(I _w (F, level));

Query H(I _w (F, level)) in the hash table;

if not found

Append I _w (F, level) to the disk log and update the hash table at the same time;

If(|I(F, level)|＝1)

{store <H(I _w (F, level)), offset, ic> into R(F); return; }

else

{insert(<H(I _w (F, level)), offset, ic>, level+1, F.Index);

level:=level+1; goto loop;

}

}

Claims (4)

1. the data backup system based on fingerprint comprises backup server, backup agent, storage server and Web server, and they intercom mutually by network and finish data backup and recovery, it is characterized in that:

Described backup server is equipped with configuration file and catalog data base, the manipulating object of recording user definition in the configuration file of backup server, manipulating object comprises the attribute of appointing system operation task operation, and backup server is being controlled the process of whole data backup and recovery by manipulating object; Catalog data base storage operation record, charge book is preserved the management information of manipulating object operation;

Described backup agent is installed on that each needs on the main frame of Backup Data in the network, from the file system of place main frame, read the file that needs backup by backup agent during backup, file is carried out based on the piecemeal of anchor and calculates the fingerprint of piecemeal, and the block data that fingerprint and part are needed is sent to storage server by network; Backup agent receives file data and writes the file system of place main frame under the designated directory from storage server by network during recovery; Backup agent carries out based on the piecemeal step of anchor file:

(1) with the beginning 48 byte b of file ₁, b ₂..., b ₄₈Be a window, with formula H ₁=(b ₁* p ⁴⁷+ b ₂* p ⁴⁶+ ...+b ₄₈) cryptographic hash of first window of mod M calculation document; P is 17 in the formula, and M is 2 ³², cryptographic hash is stored in variable H ₁In;

(2) slide backward a byte, with formula H ₂=(p*H ₁+ b ₄₉-b ₁* p ⁴⁸) second window b of mod M calculation document ₂, b ₃..., b ₄₉Cryptographic hash, be stored in variable H ₂In;

(3) by that analogy, the cryptographic hash of all windows of calculation document;

(4) to the cryptographic hash of each window, get its low 13 and form a binary number, if this number equals 61, determine that then its corresponding window is an anchor, be that the border is divided into data block not of uniform size to file with the anchor;

Above-mentioned file block based on anchor is observed following three agreements: if a) file is less than 48 bytes, then withdraw from the file block algorithm based on anchor, whole file is a data block; B) if in a certain section byte stream, comprise too much anchor, then give up some anchors and make minimum piecemeal be not less than 2KB, a piecemeal of end of file be unique may be less than the piecemeal of 2KB; C) if all do not have anchor in the byte stream of continuous 64KB, then getting this 64KB is a piecemeal;

Described storage server is equipped with the large capacity disc array, and the large capacity disc array is the destination of data backup, receives fingerprint or deblocking by network from corresponding backup agent during backup, deblocking is stored on the disk, and set up the index of file; During recovery then from the large capacity disc array according to file index reconstruct file, and file data delivered to corresponding backup agent by network;

Described Web server is the B-S pattern webpage subscriber administration interface of native system, by the login Web server, the user both can appointing system finishes the ruuning situation of interactively back up or restore operation, the operation of surveillance scheduling type automatically, can also revise configuration file, the customization manipulating object of backup server, carry out equipment control.

2. the data backup system based on fingerprint as claimed in claim 1 is characterized in that, described backup server comprises backup server initialization module, order monitoring module, command processing module, operation processing module and network communication module;

Described backup server initialization module is carried out initial work, comprises reading configuration file, set up resource chained list in the internal memory, check catalog data base state, the data consistency that guarantees configuration file and catalog data base and integrality, startup command policing port, accepting user command, initialization job queue and user command formation, load operations object, initiating task and network monitoring service in job queue from Web server;

It is a network monitoring thread that is generated by system that module is monitored in described order, connection request to Web server authenticates, assurance has only the Web server ability connected system through system authorization, monitors the command request of having sent by the Web server that authenticates; Receive orders when asking, command request is joined in the user command formation wait for system handles;

Described command processing module comprises a user command formation and N command job thread, and when the user command formation was overflowed, order was monitored module and changed sleep state over to; Constantly reading order and the execution from the user command formation of these command job threads finished different functions according to the difference of performed order; When order is monitored module adds an order in the user command formation,, just generate a new command job thread if when the number of current command job thread that does not have a free time and active command job thread does not reach N; The command job thread all checks from the user command formation that at every turn order monitors the state of module during reading order, if it is in sleep state then wakes it up;

Described operation processing module comprises that a job queue, a L work operations thread and a job queue load thread, and when the operation formation was overflowed, job queue loaded thread and enters sleep state; The work operations thread is constantly got manipulating object and is carried out from job queue, call different resources, realize different functions according to the difference of manipulating object attribute; Job queue loads thread and carries out job scheduling, check the scheduling strategy attribute of each manipulating object in the operation resource chain, the manipulating object that needs management and running is added in the job queue, if when the current number that does not have idle work operations thread and an active work operations thread does not reach L, just generate a new work operations thread; The work operations thread all checks from job queue that at every turn job queue loads the state of thread during the reading operation object, if it is in sleep state then wakes it up;

Described network communication module encapsulates the network communication applications DLL (dynamic link library) of standard, provide network communication interface to command job thread and work operations thread, network communication interface is realized the Data Transport Protocol between backup server, backup agent and the storage server.

3. the data backup system based on fingerprint as claimed in claim 1 is characterized in that, described backup agent comprises backup agent initialization module, request monitoring module, operation processing module, file block module and network communication module;

Described backup agent initialization module is carried out initial work, comprises reading the backup agent configuration file, setting up the memory source chained list, the initialization job queue, start backup server requests and monitor module;

Described request is monitored the connection request that module is monitored backup server on the network, authenticates the backup server of connection, and authentication is communicated by letter with this backup server by a network connection of back generation socket and added in the job queue;

Described operation processing module comprises a job queue and M work operations thread, and when the operation formation was overflowed, request monitoring module changed sleep state over to; The work operations thread takes out a network connection socket from job queue after, at first set up a job control record for operation, network is connected the socket chain goes in the member variable of job control record, connect socket by this network then and backup server mutual, the relevant attribute of backup server manipulating object by conversion after assignment to the corresponding member variable of job control record; Use the operation bill ticket that obtains from backup server to connect corresponding storage server then, produce a network and be connected socket and it chain is gone in the member variable of job control record with storage server communication; When request monitoring module adds network when connecting socket in job queue,, just generate a new work operations thread if when the current number that does not have idle work operations thread and an active work operations thread does not reach M; The work operations thread is got the state of all checking request monitoring module when a network connects socket at every turn from job queue, if it is in sleep state then wakes it up;

Described file block module is accepted the file block task of the command execution backup job of work operations thread in the operation processing module, each file that on client file systems, opens file concentrated, file is carried out based on the piecemeal of anchor and calculates the piecemeal fingerprint and corresponding storage server coordinates to carry out the backup algorithm of first backup procedure;

Described network communication module is made up of the network connection socket of operation, and each operation of backup agent all has two networks and connects sockets, is respectively applied for the backup server operation and the storage server operation of this operation correspondence and communicates by letter.

4. the data backup system based on fingerprint as claimed in claim 1, it is characterized in that, described storage server comprises the storage server initialization module, connects monitoring module, operation bill table, operation processing module and network communication module, and index buffer zone, blocking and buffering district, piecemeal Hash table and Disk Logs;

Described storage server initialization module is carried out initial work, comprises resolving the storage server configuration file, sets up the memory source chained list, starts the related service thread;

The connection request of described connection monitoring module monitoring backup server and backup agent authenticates the backup server that connects, and authentication generates a network by the back and connects socket and communicate by letter with this backup server and add in the job queue; To the backup agent that connects, then check operation bill table so that it is authenticated according to its operation bill ticket that shows, authentication is communicated by letter with this backup agent by a network connection of back generation socket and is linked in the member variable of corresponding job control record;

Described operation bill table is used to store the bill that operation authenticates to backup agent;

Described operation processing module comprises a job queue and W work operations thread, when the operation formation is overflowed, connects monitoring module and changes " refusal backup server connection request " state over to; The work operations thread takes out a network connection socket from job queue after, at first set up a job control record for operation, network is connected the socket chain goes in the member variable of job control record, mutual by this network connection socket and backup server then, the relevant attribute of backup server manipulating object by conversion after assignment give the corresponding member variable of job control record, and generate an operation bill ticket at random and register in the operation bill table and and transmit this operation bill ticket to the backup server manipulating object; In job queue, adds a network when connecting socket when connecting monitoring module,, just generate a new work operations thread if when the number of current work operations thread that does not have a free time and active work operations thread does not reach W; The work operations thread is got from job queue at every turn and is all checked the state that connects monitoring module when a network connects socket, if it is in " refusal backup server connection request " state then cancels this state so that it accepts the backup server connection request;

Described network communication module is made up of the network connection socket of operation, and each operation of storage server all has two networks and connects sockets, is respectively applied for the backup server operation and the backup agent operation of this operation correspondence and communicates by letter;

Described index buffer zone is the infrastructure that first backup procedure and second backup procedure are carried out in the storage server operation, and the index buffer zone is realized with an internal memory Hash table, is used for storing this job instances of this activity chain Job _x(t _n) previous job instances Job _x(t _N-1) all fingerprints that comprise and newly-generated fingerprint in this job run process;

Described blocking and buffering district is the infrastructure that first backup procedure and second backup procedure are carried out in the storage server operation, the blocking and buffering district does not have found deblocking with an independently disk array realization in order to its fingerprint in interim storage first backup procedure in the index buffer zone;

Described piecemeal Hash table is the infrastructure that second backup procedure is carried out in the storage server operation, and the piecemeal Hash table is with an independently disk array realization, in order to set up the piecemeal fingerprint to the mapping of this piecemeal in the memory address of Disk Logs;

Described Disk Logs is the infrastructure that second backup procedure is carried out in the storage server operation, and Disk Logs is with an independently disk array realization, in order to the file index of storing deblocking and storing with block form.

Images