Optimized prepopulation of a client side cache in a deduplication environment

• US 8,214,428 B1
• Filed: 05/18/2010
• Issued: 07/03/2012
• Est. Priority Date: 05/18/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Christiaens, Mark
• Primary Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US12/782,648
• Time in Patent Office: 777 Days
• Field of Search: 709/202, 709/203, 709/216, 709/219, 709/226, 709/248, 707/610, 707/633, 707/640, 707/649, 707/654, 711/162
• US Class Current: 709/203
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A backup cache on a client is prepopulated with fingerprints corresponding to data stored on a backup server. A plurality of fingerprints of data are received from the client, each received fingerprint corresponding to data present on the client which is subject to backup to the server. For each received fingerprint, an attempt is made to locate data corresponding to the received fingerprint stored on the backup server. Responsive to locating data corresponding to a received fingerprint stored on the backup server, data stored on the backup server considered to be “in the neighborhood” of the located data is identified. Fingerprints (e.g., hashes) identifying data stored on the backup server in the neighborhood of the located data are created and transmitted to the client, for prepopulating the backup cache on the client.

Claims

1. A computer implemented method for prepopulating a backup cache on a client with fingerprints corresponding to data stored on a server for backups in a deduplication environment, the method comprising the steps of:

receiving a plurality of first fingerprint data at the server from the client, each of the first fingerprints generated from data present on the client subject to backup on the server;

locating neighboring server data corresponding to each of the first fingerprints and stored on the server, the neighboring server data comprising server data having a predetermined relationship to the client data used to generate the first fingerprints;

generating a plurality of second fingerprints corresponding to the neighboring server data on the server; and

transmitting the plurality of second fingerprints to the client, for prepopulating the backup cache on the client with the plurality of second fingerprints which are indicative of the neighboring server data.

2. The method of claim 1 wherein locating neighborhood server data further comprises:

identifying a storage unit on the server storing data; and

classifying all data stored in the storage unit as being in the neighborhood of the located data.

3. The method of claim 2 wherein the storage unit further comprises:

a container file.

4. The method of claim 1 wherein locating neighboring server data further comprises:

identifying a storage unit on the server storing data corresponding to at least one of the plurality of first fingerprints; and

classifying all data stored in the storage unit as neighboring server data.

5. The method of claim 1 wherein identifying data in the neighborhood of the located data further comprises:

identifying data stored on the server within a predetermined tolerance to be stored also on the client, based on at least one of the first fingerprints.

6. The method of claim 1 wherein generating the plurality of second fingerprints further comprises:

creating a hash of identified data stored on the server that is in the neighborhood of the located data.

7. The method of claim 1 further comprising:

responsive to locating data corresponding to at least one of the fingerprints stored on the server, transmitting the corresponding second fingerprint to the client, for prepopulating the backup cache on the client.

8. A computer implemented method for prepopulating a backup cache on a client with fingerprints corresponding to data stored on a backup server in a deduplication environment, the method comprising the steps of:

selecting a limited sample of data present on the client, said data present on the client being subject to backup to the server;

generating a plurality of first fingerprints corresponding to the selected data present on the client;

transmitting the plurality of first fingerprints to the server, for locating neighboring server data present on the server, the neighboring server data comprising server data having a predetermined relationship to the client data used to generate the first fingerprints;

in response to transmitting the plurality of first fingerprints to the backup server, receiving, from the server, a plurality of second fingerprints generated by the server and corresponding to the neighboring server data stored on the server; and

prepopulating the client backup cache with the plurality of second fingerprints which are indicative of the neighboring server data.

9. The method of claim 8 wherein creating a fingerprint corresponding to selected data present on the client further comprises:

creating a hash of selected data present on the client.

10. The method of claim 8 further comprising:

in response to transmitting the plurality of first fingerprints to the server, receiving, from the server, an indication that data corresponding to the plurality of first fingerprints is stored on the server; and

prepopulating the backup cache on the client with the plurality of second fingerprints.

11. At least one non-transitory computer readable storage medium storing a computer program product for prepopulating a backup cache on a client with fingerprints corresponding to data stored on a backup server in a deduplication environment, the computer program product comprising:

program code for receiving a plurality of first fingerprint data at the server from the client, each of the first fingerprints generated from data present on the client subject to backup on the server;

locating neighboring server data corresponding to each of the first fingerprints and stored on the server, the neighboring server data comprising server data having a predetermined relationship to the client data used to generate the first fingerprints;

generating a plurality of second fingerprints corresponding to the neighboring server data on the server; and

program code for transmitting the plurality of second fingerprints to the client, for prepopulating the backup cache on the client with the plurality of second fingerprints which are indicative of the neighboring server data.

12. The computer program product of claim 11 wherein the program code for locating neighborhood server data further comprises:

program code for identifying a storage unit on the server storing data; and

program code for classifying all data stored in the storage unit as being in the neighborhood of the located data.

13. The computer program product of claim 12 wherein the storage unit further comprises:

a container file.

14. The computer program product of claim 11 wherein the program code for locating neighboring server data further comprises:

program code for identifying a storage unit on the server storing data corresponding to at least one of the plurality of first fingerprints; and

program code for classifying all data stored in the storage unit as neighboring server data.

15. The computer program product of claim 11 wherein the program code for identifying data in the neighborhood of the located data further comprises:

program code for identifying data stored on the server within a predetermined tolerance to be stored also on the client, based on at least one of the first fingerprints.

16. The computer program product of claim 11 wherein the program code for generating the plurality of second fingerprints further comprises:

program code for creating a hash of identified data stored on the server that is in the neighborhood of the located data.

17. The computer program product of claim 11 further comprising:

program code for, responsive to locating data corresponding to at least one of the fingerprints stored on the server, transmitting the corresponding second fingerprint to the client, for prepopulating the backup cache on the client.

18. The computer program product of claim 11 further comprising:

program code for selecting a limited sample of data present on the client, said data present on the client being subject to backup to the server;

generating a plurality of first fingerprints corresponding to the selected data present on the client;

program code for transmitting the plurality of first fingerprints to the server, for locating neighboring server data present on the server, the neighboring server data comprising server data having a predetermined relationship to the client data used to generate the first fingerprints;

program code for, in response to transmitting the plurality of first fingerprints to the backup server, receiving, from the server, a plurality of second fingerprints generated by the server and corresponding to the neighboring server data stored on the server; and

program code for prepopulating the client backup cache with the plurality of second fingerprints which are indicative of the neighboring server data.

19. The computer program product of claim 18 wherein the program code for creating a fingerprint corresponding to selected data present on the client further comprises:

program code for creating a hash of selected data present on the client.

20. The computer program product of claim 18 further comprising:

program code for, in response to transmitting the plurality of first fingerprints to the server, receiving, from the server, an indication that data corresponding to the plurality of first fingerprints is stored on the server; and

program code for prepopulating the backup cache on the client with the plurality of second fingerprints.