Remote backup and restore
View Patent ↗In one embodiment of the present invention, a data-backup method includes partitioning a fingerprint namespace among a cluster of backup servers, the fingerprint namespace comprising fingerprints for representing units of data, each backup server of the cluster of backup servers managing units of data having fingerprints corresponding to an assigned partition of the fingerprint namespace. The method further includes receiving backup information from a client computing device for a block of data comprising units of data, the backup information including at least a fingerprint for each of the units of data and client-specific backup information. In addition, the method includes, utilizing the fingerprint for each of the units of data, deduplicating the units of data in parallel at the cluster of backup servers in accordance with the partitioning step, the deduplicating step comprising identifying ones of the units data already stored by the cluster of backup servers.
1. A method comprising:
receiving backup information from a client computing device for a block of data comprising chunks of data, the backup information including at least a fingerprint for each of the chunks and client-specific backup information, the client-specific backup information having been created on the client computing device using a process comprising:
dividing data files of the block of data into the chunks;
applying a cryptographic hash to each of the chunks, thereby creating a fingerprint of contents of each of the chunks;
creating a chunk tree of the block of data, wherein each chunk tree includes at least a root chunk;
compiling and preserving file metadata using a process that includes at least, for each file data of the block of data, packaging the root chunk of a corresponding chunk tree with metadata about the data file; and
creating a backup tree for the block of data based on a result of the compiling and preserving; and
utilizing the fingerprint for each of the chunks of data, deduplicating the chunks of data in parallel at a cluster of backup servers in accordance with a fingerprint namespace comprising a universe of fingerprints for representing data chunks, each backup server of the cluster of backup servers managing data chunks having fingerprints corresponding to an assigned partition of the fingerprint namespace, the deduplicating comprising identifying ones of the chunks of data already stored by the cluster of backup servers.
2. The method of claim 1 , wherein the deduplicating comprises requesting and storing ones of the chunks of data not already stored by the cluster of backup servers.
3. The method of claim 1 , the method comprising designating a backup server in the cluster of backup servers as a cluster master, the cluster master being a central point of contact for the cluster of backup servers.
4. The method of claim 3 , the method comprising designating a backup server in the cluster of backup servers as a client master for the client computing device, the client master managing client-specific backup information for the client computing device.
5. The method of claim 4 , the method comprising partitioning a client namespace of a universe of possible names for client computing devices among the cluster of backup servers, each backup server of the cluster of backup servers managing client-specific backup information for an assigned partition of the client namespace.
6. The method of claim 1 , the method comprising:
at each backup server in the cluster of backup servers, preserving locality information for chunks of data having fingerprints in the assigned partition of the fingerprint namespace; and
wherein the preserving comprises maintaining a plurality of backup buckets, the plurality of backup buckets encapsulating chunks of data based at least in part on a likelihood that the encapsulated chunks of data will be accessed in close proximity.
7. The method of claim 6 , the method comprising:
at each backup server in the cluster of backup servers, maintaining a universal index of data chunks managed by the backup server in accordance with the partitioning; and
wherein the deduplicating comprises utilizing a data-access hierarchy to restrict demand on the universal index.
8. The method of claim 7 , wherein the utilizing the data access hierarchy comprises:
determining absence of a chunk of data within the universal index of data chunks via a Bloom filter;
consulting a cache of chunks of data in response to a result of the determining being inconclusive; and
checking the universal index of data chunks in response to the chunk of data not being found within the cache of chunks of data.
9. The method of claim 8 , the method comprising adding the chunk of data to the cache of chunks of data.
10. The method of claim 9 , the method comprising adding chunks of data within a same backup bucket as the chunk of data to the cache of chunks of data.
11. The method of claim 1 , the method comprising sharing deduplication information for the cluster of backup servers among a plurality of client computing devices utilizing the cluster of backup servers for backup services without contacting the cluster of backup servers.
12. The method of claim 1 , the method comprising:
wherein the backup information is generated by the client computing device; and
wherein the backup information represents a deduplication of the chunks of data within the block of data.
13. The method of claim 1 , wherein the client computing device is a virtual machine and the block of data is a virtual image from the virtual machine.
14. The method of claim 1 , the method comprising:
restoring the block of data using the client-specific backup information responsive to a request.
15. The method of claim 1 , the method comprising:
adding a new backup server to the cluster of backup servers; and
responsive to the adding, partitioning the fingerprint namespace among the cluster of backup servers, each backup server of the cluster of backup servers managing chunks of data having fingerprints corresponding to an assigned partition of the fingerprint namespace.
16. A computer-program product comprising a non-transitory computer-usable medium having computer-readable program code embodied therein, the computer-readable program code configured to be executed to implement a data-backup method comprising:
receiving backup information from a client computing device for a block of data comprising chunks of data, the backup information including at least a fingerprint for each of the chunks and client-specific backup information, the client-specific backup information having been created on the client computing device using a process comprising:
dividing data files of the block of data into the chunks;
applying a cryptographic hash to each of the chunks, thereby creating a fingerprint of contents of each of the chunks;
creating a chunk tree of the block of data, wherein each chunk tree includes at least a root chunk;
compiling and preserving file metadata using a process that includes at least, for each file data of the block of data, packaging the root chunk of a corresponding chunk tree with metadata about the data file; and
creating a backup tree for the block of data based on a result of the compiling and preserving; and
utilizing the fingerprint for each of the chunks of data, deduplicating the chunks of data in parallel at a cluster of backup servers in accordance with a fingerprint namespace comprising a universe of fingerprints for representing data chunks, each backup server of the cluster of backup servers managing data chunks having fingerprints corresponding to an assigned partition of the fingerprint namespace, the deduplicating comprising identifying ones of the chunks of data already stored by the cluster of backup servers.
17. The computer-program product of claim 16 , wherein the deduplicating comprises requesting and storing ones of the chunks of data not already stored by the cluster of backup servers.
18. The computer-program product of claim 16 , the data-backup method comprising designating a backup server in the cluster of backup servers as a cluster master, the cluster master being a central point of contact for the cluster of backup servers.
19. The computer-program product of claim 18 , the data-backup method comprising designating a backup server in the cluster of backup servers as a client master for the client computing device, the client master managing client-specific backup information for the client computing device.
20. The computer-program product of claim 19 , the data-backup method comprising partitioning a client namespace of a universe of possible names for client computing devices among the cluster of backup servers, each backup server of the cluster of backup servers managing client-specific backup information for an assigned partition of the client namespace.
21. The computer-program product of claim 16 , the data-backup method comprising:
at each backup server in the cluster of backup servers, preserving locality information for chunks of data having fingerprints in the assigned partition of the fingerprint namespace; and
wherein the preserving comprises maintaining a plurality of backup buckets, the plurality of backup buckets encapsulating chunks of data based at least in part on a likelihood that the encapsulated chunks of data will be accessed in close proximity.
22. The computer-program product of claim 21 , the data-backup method comprising:
at each backup server in the cluster of backup servers, maintaining a universal index of data chunks managed by the backup server in accordance with the partitioning; and
wherein the deduplicating comprises utilizing a data-access hierarchy to restrict demand on the universal index.
23. The computer-program product of claim 22 , wherein the utilizing the data-access hierarchy comprises:
determining absence of a chunk of data within the universal index of data chunks via a Bloom filter;
consulting a cache of chunks of data in response to a result of the determining being inconclusive; and
checking the universal index of data chunks in response to the chunk of data not being found within the cache of chunks of data.
24. The computer-program product of claim 23 , the data-backup method comprising adding the chunk of data to the cache of chunks of data.
25. The computer-program product of claim 24 , the data-backup method comprising adding chunks of data within a same backup bucket as the chunk of data to the cache of chunks of data.
26. The computer-program product of claim 16 , the data-backup method comprising sharing deduplication information for the cluster of backup servers among a plurality of client computing devices utilizing the cluster of backup servers for backup services without contacting the cluster of backup servers.
27. The computer-program product of claim 16 , the data-backup method comprising:
wherein the backup information is generated by the client computing device; and
wherein the backup information represents a deduplication of the chunks of data within the block of data.
28. The computer-program product of claim 16 , wherein the client computing device is a virtual machine and the block of data is a virtual image from the virtual machine.
29. The computer-program product of claim 16 , the data-backup method comprising:
restoring the block of data using the client-specific backup information responsive to a request.
30. The computer-program product of claim 16 , the data-backup method comprising:
adding a new backup server to the cluster of backup servers; and
responsive to the adding, partitioning the fingerprint namespace among the cluster of backup servers, each backup server of the cluster of backup servers managing chunks of data having fingerprints corresponding to an assigned partition of the fingerprint namespace.