Low-overhead means of performing data backup

• US 7,761,425 B1
• Filed: 03/29/2007
• Issued: 07/20/2010
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: DeWispeleare, Wim, Erickson, Mark
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US11/693,370
• Time in Patent Office: 1,209 Days
• Field of Search: 707/204, 707/104.1, 707/649, 711/162
• US Class Current: 707/649
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A system and method for data backup. A computer system includes clients coupled to backup server and single instance store via a network. Prior to requesting an initial data backup, a new client segments and fingerprints the data to be backed up. The new client creates a sorted list of hash values and removes duplicate values in the list. In response to receiving the sorted list, a backup server may further reduce the sorted list to a unique list by removing hash values corresponding to data segments already residing on the single instance store. In response to receiving the unique list, the new client may transmit corresponding data segments to the backup server via the network. The transmitted data segments are added to a single instance store.

Claims

1. A computer system comprising:

a plurality of clients; and

a backup server coupled to a single-instance data store, said single-instance store being configured to store backup data for each of the plurality of clients, wherein said backup data includes only a single instance of any data that is stored on the plurality of clients with no duplication in the single-instance store;

wherein a client of said clients requesting data backup is configured to;

identify a plurality of data segments to be backed up;

generate a first list of fingerprints including a fingerprint for each of the plurality of data segments;

remove duplicate fingerprints from the first list; and

convey the first list to the backup server;

wherein in response to receiving the first list, the backup server is configured to;

identify first fingerprints included in the first list which match fingerprints of data segments stored in the single-instance data store; and

convey a second list to the client, the second list comprising the fingerprints of the first list without the first fingerprints;

wherein the client is configured to convey for backup, data segments of the plurality of data segments identified by the second list.

2. The computer system of claim 1, wherein the client is further configured to convey a corresponding fingerprint for each of the data segments conveyed for backup when conveying the data segments of the plurality of data segments identified by the second list.

3. The computer system of claim 1, wherein for each data segment stored in the single-instance data store, there is stored a batch number used to identify a corresponding backup operation in which an associated entry storing the data segment was created.

4. The computer system of claim 2, wherein the client is further configured to convey the metadata for all data segments on the client when conveying the data segments of the plurality of data segments identified by the second list.

5. The computer system as recited in claim 4, wherein in response to receiving the corresponding fingerprints and the conveyed data segments from the client, the backup server is further configured to add the corresponding fingerprints and the conveyed data segments to the single-instance data store.

6. The computer system as recited in claim 1, wherein for each data segment stored in the single-instance data store, there is stored a fingerprint that identifies the data segment and a reference to each client from which a copy of the data segment was received for backup.

7. The computer system as recited in claim 6, wherein the fingerprints identifying the data segments are encrypted.

8. A method for backing up data, the method comprising:

identifying a plurality of data segments of a client to be backed up;

generating a first list of fingerprints including a fingerprint for each of the plurality of data segments;

removing duplicate fingerprints in the client from the first list;

conveying the first list to a backup server;

identifying first fingerprints included in the first list which match fingerprints of data segments stored in a single-instance data store, said single-instance store being configured to store backup data for each of a plurality of clients including said client, wherein said backup data includes only a single instance of any data that is stored on the plurality of clients with no duplication in the single-instance store;

conveying a second list from a backup server to the client, the second list comprising the fingerprints of the first list without the first fingerprints; and

conveying for backup from the client, data segments of the plurality of data segments identified by the second list.

9. The method of claim 8, further comprising conveying a corresponding fingerprint for each of the data segments conveyed for backup when conveying the data segments of the plurality of data segments identified by the second list.

10. The method of claim 8, wherein for each data segment stored in the single-instance data store, there is stored a batch number used to identify a corresponding backup operation in which an associated entry storing the data segment was created.

11. The method of claim 9, further comprising the client conveying the metadata for all data segments on the client when conveying the data segments of the plurality of data segments identified by the second list.

12. The method as recited in claim 11, wherein in response to receiving the corresponding fingerprints and the conveyed data segments from the client, the method further comprises the backup server adding the corresponding fingerprints and the conveyed data segments to the single-instance data store.

13. The method as recited in claim 8, wherein for each data segment stored in the single-instance data store, there is stored a fingerprint that identifies the data segment and a reference to each client from which a copy of the data segment was received for backup.

14. The method as recited in claim 13, wherein the fingerprints identifying the data segments are encrypted.

15. A plurality of computer readable storage media comprising program instructions which are executable to:

identify a plurality of data segments of a client to be backed up;

generate a first list of fingerprints including a fingerprint for each of the plurality of data segments;

remove duplicate fingerprints from the first list;

convey the first list to a backup server;

identify first fingerprints included in the first list which match fingerprints of data segments stored in a single-instance data store, said single-instance store being configured to store backup data for each of a plurality of clients including said client, wherein said backup data includes only a single instance of any data that is stored on the plurality of clients with no duplication in the single-instance store;

convey a second list from a backup server to the client, the second list comprising the fingerprints of the first list without the duplicate fingerprints; and

convey for backup from the client, data segments of the plurality of data segments identified by the second list.

16. The storage media of claim 15, wherein the program instructions are further configure to convey a corresponding fingerprint for each of the data segments conveyed for backup when conveying the data segments of the plurality of data segments identified by the second list.

17. The storage media of claim 15, wherein for each data segment stored in the single-instance data store, there is stored a batch number used to identify a corresponding backup operation in which an associated entry storing the data segment was created.

18. The storage media of claim 16, further comprising the client conveying the metadata for all data segments on the client when conveying the data segments of the plurality of data segments identified by the second list.

19. The storage media as recited in claim 18, wherein in response to receiving the corresponding fingerprints and the conveyed data segments from the client, the method further comprises the backup server adding the corresponding fingerprints and the conveyed data segments to the single-instance data store.