CN1294514C - Efficient computer file backup system and method - Google Patents

Abstract

A system and method for efficiently backing up and restoring computer files to a central storage system. A hashing key is computed for each file to be backed up on a target computer. The hashing key is compared to a list of hashing keys stored locally to see if the local file has been previously backed up. If the hashing key is not listed locally, then the hashing key is compared to a list of hashing keys of centrally backed up files. Only if the hashing key is not present in both the local and the central list is the file backed up. Backed up files may be renamed to their hashing key for further efficiencies.

Description

Efficient computer file backup system and method

The present invention generally relates to a method for backing up and restoring data files and programs on a computer system, and more particularly, the present invention relates to an efficient method for determining whether a file or program has been previously backed up , or if a backup copy of the file exists, then back up only those programs that were not previously backed up and that do not have a backup copy. Accordingly, the systems and methods enable efficient use of bandwidth for local or remote backup of files of computers and/or computer systems.

Traditional methods for backing up computer programs and data files often use large amounts of expensive network bandwidth and excessive processor (CPU) processing time. Currently, many backup processes back up a computer or computer system's entire program and data repository, causing duplication of backup files and programs, and requiring large amounts of network bandwidth and excess storage media (such as tape or compact disk (CD)).

The networks of many organizations often include data centers ("server farms") for storing and managing large amounts of Internet-accessible data. Data centers often include several computer systems, such as Internet servers, employee workstations, file servers, and so on. Often, such data centers have scalability issues using traditional backup systems. The bandwidth and storage required are insufficient to perform large-scale backups of data center environments. A system that is scalable and able to grow as the organization grows would be beneficial.

Some savings in bandwidth and storage media can be achieved through an incremental backup method that only backs up files that have changed or have been updated. However, these methods do not solve the problem that files residing on different computers on one network, or even on different networks, are often backed up in duplicate, consuming a large amount of storage media.

For example, data files are often shared among many people, and duplicate copies reside on many different computers, resulting in many multiple copies of the file across one or more computer networks. Further, computers often use duplicate program and data files to run operating systems and applications. For example, in a network running Microsoft Windows ^(R) , each computer may have duplicate operating system files and programs. Backing up an entire network using traditional methods can result in many multiple copies of those files and programs, causing excessive waste of storage media. A means of deduplicating backup files and programs would be desirable, with possible benefits resulting in more efficient utilization of storage media, processing time, and network bandwidth.

Further, traditional backup methods implemented by organizations often use many computer servers to perform the backup, often to tape media, which results in distributed storage of data backups, in addition to duplication in both media and processor time and waste.

Still further, a distributed backup process typically entails the need to store many backup tapes, or other similar backup media, and requires a method of keeping track of the multiple media. Such a system is often difficult to restore, especially if incremental backup procedures are used. The correct storage media must be located and must be loaded in the correct order. Tape recovery is a tedious, time-consuming process. Often, the recovery process is so inefficient and error-prone that it is ineffective, resulting in data loss and even loss of productivity because programs must be reinstalled and data must be rebuilt. Organizations using computer systems would benefit from a more efficient and easy-to-use backup system resulting in a more efficient and easier-to-implement recovery process.

The present invention relates to improvements in backup technology, and more specifically, the present invention creates a solution for large-scale server backup in Internet data center and enterprise data center environments, and results in a solution for Solutions for disaster recovery and data protection.

The present invention is an improved system and method for more efficient and effective backup of computer files and computer programs using hash keys of file content.

The first step in the process is to scan the file system on the target machine (the computer system to be backed up) and create a hash key that creates a unique digital code for each file to be backed up. In a preferred embodiment, to reduce processing time, hash keys are only created for files with a modified date attribute, ie more recent than the last backup.

The resulting hash key is stored in a local database—a database on the target computer—for example, for further comparison in current, as well as future backup sessions. The local database also includes the full path to each backup file.

The stored hash key is checked against previous hash key entries in the local database. In this way, the hash key is used to verify each local file to determine whether it was previously backed up on the target system. Hash keys not found in the local database key list are used in the next step of the process.

The hash key not found in the local hash key database is checked against the hash key of the file stored on the central storage server. This check is used to determine if a particular file already exists on the central storage server. This file may exist as a backup from another server or system, or as a result of a previous backup operation.

For example, the determination of whether to perform a backup is performed on a file-by-file basis rather than on a block-by-block basis. This strongly reduces the number of comparisons and the size of the local database, and is extremely suitable for group servers where not only data blocks, but often complete files, are duplicated across multiple servers.

A short description of the drawings

Figure 1 is a block diagram showing the main steps of a backup process according to an aspect of the present invention;

Fig. 2 is a block diagram showing the backup decision-making process according to an aspect of the present invention;

Figure 3 is a block diagram showing an implementation of a system for implementing the method of the present invention according to the present invention;

Figure 4 is a block diagram showing a more detailed implementation of the backup subsystem of the present invention;

Traditionally, whether incremental or full backups of computers, servers, or systems are performed, backup solutions dramatically increase network traffic and can use enormous storage capacity. The present invention uses content hash keys to make intelligent decisions about whether to back up certain data, and uses central storage capacity to provide more efficient and effective backup storage and restore activities.

The present invention is a system and method for more efficient and effective backup of computer files and computer programs using hash keys of file content. In this description, the terms "file", "program", "computer file", "computer program", "data file" and "data" are used interchangeably, and depending on the context of use, the use of either Another term might be implied.

The present invention utilizes a process using a hashing mechanism for checking whether a file is unique within the backup system. Only files that are unique and not yet backed up will be stored on the central storage system, which creates efficiencies in the use of network bandwidth and storage media. This process utilizes matching the newly created content key with all previously generated hash keys (using localized and/or centralized lists) to generate a backup verdict, resulting in an overall analysis of performing backups and is more efficient Restoration functions can be accomplished more easily and with less hassle. The resulting method has minimal bandwidth consumption and minimal storage capacity usage by reducing duplication in both network traffic and backup file storage. This is especially useful for backing up operating system files and frequently used applications.

Figure 1 provides an overview of the method for one implementation of the backup process according to the invention. The first step in the process, shown by box 10, is to scan the file system on the target computer/system (the individual computer or computer system to be backed up) and, for example, as shown in box 12, in 32 or 64 byte mode to create a content hash key. The hash key is a unique digital code for each file to be backed up. The hash key is unique for each unique file. Further, the hash key is the same for identical copies of the file. In this way, the hash key becomes a unique identifier for the file and any identical copies. Therefore, if two files have the same hash code, they are the same and can and will be treated alike. Ability to use the industrial hashing process, MD5.

The resulting hash key is stored in local database 404 (FIG. 3) for further comparison in current, as well as future backup sessions. This is represented by box 14 in FIG. 1 . The path and/or filename of the file corresponding to the hash key is stored together with the hash key.

An improvement to this process could be to append the hash key to the computer file itself. In this way, files that have already been hashed can be bypassed by the hashing process, which provides further savings in computer processing. However, such appending is not possible for all files, so this improvement may not be feasible for all computer file types.

The stored hash key is checked against previous hash key entries in the local database 404, as indicated at block 16 in FIG. In this way, the hash key is used to verify that each local file was previously backed up in the target system. Hash keys not found in the local database are used in the next step of the process. Because only those files that have not been logged due to being recently backed up, or at least recently processed, need to undergo further processing. This enables efficient use of computer resources.

The hash keys not found in the local hash key database are now checked against the files stored in the central database 408, as shown in block 18 in FIG. 1 . The path and/or filename of the file corresponding to each hash key is stored with each hash key stored in the local database. The hash key is used to determine whether the corresponding file already exists on the central storage server 400 and therefore does not need to be backed up. The file may exist as a backup from a different target computer 300 or even a different target network. The principle is to store a single copy of each unique file within the central storage system, no matter how many different target computers may contain that same, identical file.

If there is no match in the central database for a given hash key, the hash key is added to the central database 408 and the corresponding file is uploaded (box 20 in FIG. 1 ) to the central database. The central storage system 400 (box 22), the central storage system 400 manages the list of files and hash keys. A record of the process can be kept by the server (see log archive box 22a). If desired, the files to be archived are encrypted for security reasons (box 24) and compressed to reduce storage media requirements (box 28). For example, an encryption key can be generated by using the hash key and transforming it by a known but secure algorithm.

Finally, the scheduling process follows (block 30 in Figure 1). Based on the hash key, the scheduling process will decide in which location the file needs to be scheduled and on which storage device (32a, 32b, 32c, 32d...32n) it should be stored . The storage devices may be centrally located for increased efficiency, but the invention is also capable of using distributed, or even remotely located devices. The hash key can be used to schedule files into different locations in the storage network.

In a preferred embodiment, the stored files are renamed using said hash key as the file name. This makes file retrieval easier and faster. When restoring, the original file names will be restored by cross-referencing the hash key with the file names and/or file paths on the restored machine.

The flowchart in Fig. 2 shows the process of making the file backup decision in more detail. Local scanning is shown by the steps in box 100 . The document is scanned in step 102 and a hash key is formed by step 104 . In a preferred embodiment, hash keys are only calculated for files with a modification or creation date attribute, ie more recent than the last backup date. Each hash key is compared to a locally stored list of hash keys in local database 404 . The local database 404 contains a record for each file that has been previously backed up, the record including the hash key and the full path and name of the file (step 106). Those files with a match will not be backed up (step 110), while those files with hash keys that do not match the local list (step 106) require further processing (step in block 200). For at least each non-matching file, a new record is stored in the local database, the new record including the hash key and the full path and name of the file. The hash keys for non-matching files are collected for forwarding (step 108) and forwarded out for comparison with a centrally stored (central database 408) list of keys (step 202). If the key matches a previously centrally stored hash key (step 204), then the file is not backed up (step 210). However, the file is backed up only if there is no match (step 204). The hash key will be stored in the central database 408 and the file may undergo processing (ie, encryption and compression) as described above before being backed up or archived in memory.

A further improvement on the above process can be achieved by keeping a historical copy of the file, and of the hash lists 404, 408, so that any individual machine can be restored to the state of its file system at a given moment in the past. Obviously, realizing this improvement requires an additional storage medium in the central storage system 400, so as to save these "snapshots" at an appropriate time. The only limit to how far one can back archive filesystems is the amount of storage dedicated to the task. Thus, if a historical snapshot of a computer's file system is not desirable for a particular implementation, one can save capital expense by not implementing this feature of the present invention.

Restoring files from a system is basically performed by reversing the process. Because each target computer 300 or system has a local database 404 that includes a record of the hash keys of processed files, those hash keys on the local database can be used to convert the required files on the target computer 300 to The recovered files are identified by the path indicated in this record. A backup copy of the local database should also be stored on a different machine, or even backed up centrally, so that a list of hash keys and corresponding paths can be obtained to reconstruct the file system in the crashed machine.

The system restores the crashed machine's file system by restoring each file listed on the local computer's database 404, the files stored in the central storage system 400 corresponding to their hash keys. Further, the local database 404 itself may be stored in the central storage system 400 to keep a record of the state of the computer file system, or this local database may be backed up in the central storage system 400 .

Similarly, if it is intended to implement this feature, to restore the computer system to a previous historical file system state, it is only necessary to obtain the local database for that moment, and then restore the file system files from the historical local database. A local database of the history can be stored locally, centrally, or preferably both.

The hash code itself can be used to ensure the integrity of the file during the backup and restore process. By running the hashing process on the backed up and/or restored files, a hash code is generated which is comparable to the original hash code. If the keys are not identical, file errors occur and the integrity of the file cannot be guaranteed. If they are identical, the integrity of the file is ensured.

FIG. 3 shows a possible high-level overview of the implementation of a system for practicing the method according to the invention. The target computer or target system 300 is the system to be backed up. Backup agent 402 can be run either on the target system, or on a server of which the target system is a client. Additionally, the backup agent can be run remotely. The backup agent 402 implements the file scanning and hashing functions discussed above. The backup agent 402 also uses a local database 404 that contains a record for each file that has been previously backed up, and implements a local comparison operation (block 100 in FIG. 2 ) to determine the files on the target 300 Whether it has been backed up previously.

For greater efficiency or to avoid overhead on the target computer, the backup agent 402 can run on a dedicated server, optimized for this function. The backup agent 402 may also include a recovery function, or a separate module can implement the recovery function. The backup agent 402 and/or the restore agent can use a World Wide Web (web) interface to allow file backup of the target system via a Wide Area Network (WAN) such as the Internet, or locally via a Local Area Network (LAN) or other network Manage remotely. Alternatively or in parallel, the backup server 406 to be discussed below can also be managed via the same or similar web interface. This can allow the backup and/or restore operations to be controlled remotely regardless of where access to the proxy 402 and/or the server 406 may be provided.

The central storage system 400 is utilized to implement the centralized backup function, including the centralized comparison operation in block 200 in FIG. 2 . Although described as a centralized system, it will be understood that the functions and/or components described for such a centralized system are distributed or located remotely, depending on the desired implementation of the invention.

Backup and restore server 406 is used to direct the centralized backup operations. The server 406 receives from the proxy 402 a list of hash keys representing files not listed in the local key list. The server 406 then compares the mismatched key list with the key list stored in the central hash key database 408 (of the previous backup file). It will be appreciated that this database can be stored, if desired, in one or more of the storage devices 414 discussed below. If the file is not currently backed up in said central device 414 , then there will be no match to the hash key contained in the central key database 408 . This means that the corresponding files need to be backed up. In this case, the server 406 obtains the corresponding file from the proxy 402, or alternatively, the server may obtain the file itself and rename it to its hash key, forwarding the renamed file to To the encryption and compression module 410 (if encryption and/or compression is required), this implements the encryption and compression steps described above. It will be appreciated that the encryption and/or compression modules can be run on the server 406, or by a separate computer/server, if desired.

The encrypted and compressed file is then forwarded to the file scheduler 412 which, based on the hash key or other indicator of where the file should be stored, directs the file to to the appropriate storage device 414a, 414b...414n. These databases 414n may be located centrally or distributed, as desired.

To recover a unique file, the target server 300 requests a hash key for the file from a local database (on the target server), and retrieves the file from the central storage server 406 using that name.

It is possible to place the centralized backup system 400 remotely or locally with respect to the target system 300 . The backup system 400 can be provided remotely by a service provider using an ASP or XSP business model, wherein the central system is provided to a paying client running the target system 300 . Such a system can use a public WAN, such as the Internet, to provide network connectivity between the central system and target clients. Alternatively, a private network (WAN or LAN, etc.) can connect the two systems. You can also take advantage of a virtual private network (VPN) on a public network. Furthermore, clients may wish to implement such a system locally in order to ensure local control and autonomy, especially if the information to be stored may be particularly sensitive, valuable and/or privately owned. However, if such considerations are not a priority, a more cost-effective service can be marketed in which the central system is provided by a service provider. In this case, Internet connectivity may be cost-effective, and as noted above, a web-based management system would also be useful and easily adapted in accordance with the present invention.

It is possible to implement a system utilizing the present invention using a self-service model, which enables client network administrators to backup and restore client systems. In this case, the network administrator would access the service via an interface such as the web-based implementation described above. Alternatively, centralized management can be implemented to offload backup responsibilities from clients. Such a system would be useful for IDC server farms and for operating systems integrated with DataCenter technology. Additionally, the system can utilize numerous other open standards such as XML/SOAP, HTTP, and FTP.

Figure 4 shows a more detailed potential implementation of the backup subsystem in the system overview given in Figure 3, showing various components of the client and system servers. This figure corresponds to a more detailed description (given below) of one potential implementation of the method of the invention.

According to a more detailed potential implementation of the system, a user would access a GUI to configure a backup job with an additional schedule. This backup job will include the selection of files/directories to be backed up, OS specific backup options and schedule options. When the backup is performed manually, or caused by the schedule:

(1) A file system scan generates files that are existing on the target server 300 and will be stored in the local database 404 as a "current_backup" table. For each file in this table, store the file's location, attributes and last modification time.

(II) Next, the table "current_backup" is compared with the table "previous_backup" in the database 404 which stores the previous backup history. The result of the comparison will be files that have changed their last modification time.

(III) Generate the content checksum of the changed file and store it in the “current_backup” table in the local database 404 .

(IV) These checksums are then verified against a global repository of checksums physically residing in the central database 408 on the central storage server 400 . The result set of this check is a list of missing checksums.

(V) These legacy checksums represent files that need to be transferred to the central storage server 400 . Each file with a missing checksum will have a backup process including data synchronization with the storage server, physical transfer of its content, compression, encryption and integrity checks during the different stages, In order to ensure the successful receipt of the file.

(VI) When the file has been successfully backed up, the file will be marked as successfully backed up in the local database 404 .

(VII) After the backup process, data synchronization between the client and the storage server 400 produces a central backup history for all target servers (clients).

The restore process can be performed in a variety of ways based on the different locations where the backup history is stored. By default, recovery is performed from the history stored in the local database 404 . A subset of the previous backup set of files selected by the operator. This list contains for each file: origin location, content key, and file attributes. Based on this information, the agent can obtain the file from the vault, decompress and decrypt the contents, restore the file to its original location, and subsequently restore attributes about the restored file.

The second way to restore files is to get the backup history from snapshot files. This is a plain text file that is created during the backup process and contains a list of files. During backup, the content key and file attributes are stored next to each file's original location. When we provide such a file to an agent on a client computer, said agent is able to restore these files based on the above instructions.

Snapshot files may also be created from the backup history stored in the central database 408 , which resides on the central storage server 400 .

Claims (15)

1. one kind is used to judge whether the specific file on the object computer (300) should be backuped to the method for centralized storage system (400), and described method comprises step:

Calculate specific hash key according to the content of described specific file;

Verify that whether Already in described specific hash key in the local data base (404), wherein, for each computer documents on the described object computer (300), that before backed up, described local data base all comprises a record, and described record comprises:

File hash key according to described computer documents calculating; And

In described object computer, described computer documents should be restored to the there the local file path, described file path is associated with described file hash key;

If described specific hash key is not present in the described local data base, then described specific file is backed up by carrying out following steps:

A. create backup file, described backup file is duplicating of described specific file;

B. with the described specific hash key of described backup file RNTO;

C. the backup file with described rename is stored in the described centralized storage system (400); And

D. in described local data base (404) storage new record, this new record comprise described specific hash key and in described object computer (300), described specific file should be restored to the there particular path; And

If described specific hash key is present in the described local data base (404), then described specific file backup is not arrived in the described centralized storage system (400).

2. the method for claim 1 further comprises step:

Verify that described specific hash key is whether Already in according at least one central database (408) that has been backed up in the file hash key that the computer documents in the described centralized storage system (400) derives; And

And if only if, and described specific hash key is not present in described at least one central database (408) of described centralized storage system (400), just described specific file is backed up.

3. method as claimed in claim 2, wherein said object computer (300) is connected with LAN, and described in addition centralized storage system (400) is connected with described LAN by WAN.

4. as the described method of one of claim 1 to 3, wherein a plurality of object computers (300) are connected with described centralized storage system (400), in addition, if as the result who backs up from arbitrary object computer, in the Already in described centralized storage of the described specific file system, then do not back up described specific file.

5. method as claimed in claim 4, described specific hash key is depended in the position of the backup file of wherein said rename in described centralized storage system (400).

6. method as claimed in claim 5, wherein said centralized storage system comprise a plurality of memory devices (414a, 414b, 414n).

7. method that is used for specific file is returned to object computer (300), described method comprises step:

From local data base (404), ask specific hash key corresponding to described specific file for a previous hash key that calculates of each computer documents that has backed up storage;

The specific path position that request is associated with described specific hash key from described local data base (404);

Use described specific hash key to come retrieval backup file from Center Storage Server (400), described backup file is duplicating of described specific file; And

Described backup file is saved in described specific path position on the described object computer (300),

The title that wherein said backup file has been stored in described Center Storage Server under it depends on described hash key.

8. method as claimed in claim 7, described hash key is depended in the position of wherein having stored described backup file in described Center Storage Server.

9. system that is used for the specific file on the backup target computing machine (300) comprises:

Be used for calculating the device of specific hash key according to the content of described specific file;

Be used for verifying the whether Already in device of local data base (404) of described specific hash key, wherein, for each computer documents on the described object computer (300), that before backed up, described local data base all comprises a record, and described record comprises:

File hash key according to described computer documents calculating; And

In described object computer, described computer documents should be restored to the there the local file path, described file path is associated with described file hash key;

Be used for not being present in the device that under the situation of described local data base described specific file is backed up at described specific hash key, described backup may further comprise the steps:

A. create backup file, described backup file is duplicating of described specific file;

B. with the described specific hash key of described backup file RNTO;

C. the backup file with described rename is stored in the described centralized storage system (400); And

D. in described local data base (404) storage new record, this new record comprise described specific hash key and in described destination server, described specific file should be restored to the there particular path;

Wherein, if described specific hash key is present in the described local data base (404), then do not back up described specific file.

10. system as claimed in claim 9 is a centralized storage system, and further comprises:

Be used for verifying the whether device of at least one central database (408) of Already in described centralized storage system (400) of described specific hash key, described central database (408) comprises the file hash key of deriving according to the computer documents that has been backed up in the described centralized storage system, wherein only when described specific hash key is not present in described at least one central database, just carry out the described device that is used to back up.

11. system as claimed in claim 10 is characterized in that described object computer is connected with LAN, in addition, described centralized storage system is connected with described LAN by WAN.

12. as the described system of one of claim 9 to 11, wherein a plurality of object computers are connected with described centralized storage system, in addition, if as the result who backs up from arbitrary object computer, in the Already in described centralized storage of the described specific file system, then do not back up described specific file.

13. system as claimed in claim 12, described specific hash key is depended in the position of the backup file of wherein said rename in described centralized storage system (400).

14., further comprise as the described system of one of claim 9 to 11:

Be used for described specific file comprising from the device that described centralized storage system (400) returns to described object computer (300):

Be used for from the device of described central database request corresponding to the described specific hash key of described specific file;

Be used for from the device of the described specific path position that is associated with described specific hash key of one of described local data base and described central database request;

Be used to use described specific hash key to retrieve the device of described backup file from described system; And

Be used for will the described backup file on described object computer being saved in the device of described specific path position.

15. system as claimed in claim 14, wherein during described backup, if described specific hash key is not present in the described local data base (404), before then in described backup file being stored into described centralized storage system, with the described specific hash key of described backup file RNTO, in addition, between described convalescence, before described backup file is saved in described object computer, with the title of the described specific file of described backup file RNTO.

Images