Systems and methods for restoring deduplicated data

• US 8,433,689 B1
• Filed: 05/02/2012
• Issued: 04/30/2013
• Est. Priority Date: 10/02/2009
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Zhang, Xianbo, Paulzagade, Sudhakar
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): KINSAUL, DANIEL W
• Application Number:
  US13/462,367
• Time in Patent Office: 363 Days
• Field of Search: None
• US Class Current: 707/679
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

A method for restoring deduplicated data may include receiving a request to restore a set of deduplicated data segments to a client system, where each data segment in the set of deduplicated data segments is referred to by one or more deduplication references. The method may also include procuring reference data that indicates, for each data segment in the set of deduplicated data segments, the number of deduplication references that point to the data segment. The method may further include using the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching, caching the one or more data segments in a cache on the client system, and restoring the one or more data segments from the cache on the client system. Various other methods, systems, and computer-readable media are also disclosed.

Claims

1. A computer-implemented method for restoring deduplicated data, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

receiving a request to restore a set of deduplicated data segments to a client system, wherein each data segment in the set of deduplicated data segments is referred to by one or more deduplication references;

procuring reference data that indicates, for each data segment in the set of deduplicated data segments, a number of deduplication references on the client system that point to the data segment, wherein the number of deduplication references that point to the data segment comprises a total count of how many individual deduplication references, collections of deduplication references, or both, point to the data segment;

using the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching;

caching at least one of the one or more data segments or references to the one or more data segments in a cache on the client system;

restoring the one or more data segments from the client system wherein restoration comprises at least one of restoring the one or more data segments from the cache on the client system or querying the cache to determine where the one or more data segment are stored on the client system.

2. The computer-implemented method of claim 1, further comprising:

creating a mapping table of the one or more data segments.

3. The computer-implemented method of claim 2, wherein creating the mapping table of the one or more data segments comprises:

calculating a fingerprint for each of the one or more data segments;

mapping the fingerprint of each of the one or more data segments to the content of each of the one or more data segments.

4. The computer-implemented method of claim 2, wherein creating the mapping table of the one or more data segments comprises at least one of:

creating the mapping table during a deduplication process;

creating the mapping table during a data restoration process;

creating the mapping table based on deduplication metadata of a backup of the set of deduplicated data segments.

5. The computer-implemented method of claim 2, further comprising:

updating the mapping table by replacing a least-used deduplicated segment in the mapping table with a more-used deduplicated segment.

6. The computer-implemented method of claim 5, wherein replacing the least-used deduplicated segment comprises at least one of:

replacing a least-frequently used deduplicated segment;

replacing a least-recently used deduplicated segment.

7. The computer-implemented method of claim 1, wherein caching the one or more data segments in the cache on the client system comprises creating a pointer to at least one copy of a segment that has already been restored.

8. A system for restoring deduplicated data, the system comprising:

at least one processor;

an interface module programmed to direct the processor to receive a request to restore a set of deduplicated data segments to a client system, wherein each data segment in the set of deduplicated data segments is referred to by one or more deduplication references;

a selection module programmed to direct the processor to;

procure reference data that indicates, for each data segment in the set of deduplicated data segments, a number of deduplication references on the client system that point to the data segment, wherein the number of deduplication references that point to the data segment comprises a total count of how many individual deduplication references, collections of deduplication references, or both, point to the data segment;

use the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching;

a cache module programmed to direct the processor to cache at least one of the one or more data segments or references to the one or more data segments in a cache on the client system;

a restoration module programmed to direct the processor to restore the one or more data segments from the client system wherein restoration comprises at least one of restoring the one or more data segments from the cache on the client system or querying the cache to determine where the one or more data segments are stored on the client system.

9. The system of claim 8, wherein procuring the reference data comprises:

summing a number of data objects on the client system that point to the data segment to procure a count of how many deduplication references point to the data segment.

10. The system of claim 9, wherein;

the number of data objects that point to the data segment comprises a count of how many original data objects point to the data segment plus a count of how many data object revisions point to the data segment;

the original data objects comprise data objects that represent first versions of data segments;

the data object revisions comprise data objects that represent revised versions of data segments.

11. The system of claim 9, wherein the number of data objects that point to the data segment comprises a count of a total number of collections of references that point to the data segment, wherein each collection of the collections of references comprises a plurality of data objects that represent sets of data segments.

12. The system of claim 8, wherein procuring the reference data comprises:

weighting one or more components of the reference count to provide a weighted sum of deduplication references that point to the data segment.

13. The system of claim 8, wherein the selection module is programmed to use the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching by selecting data segments whose reference counts are higher than a predetermined threshold for client-side caching.

14. The system of claim 8, wherein:

the selection module is programmed to use the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching by selecting a predetermined number of data segments whose reference counts are high relative to data segments that were not selected for client-side caching;

the predetermined number of data segments is defined by an amount of space available on the cache on the client system.

15. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

receive a request to restore a set of deduplicated data segments to a client system, wherein each data segment in the set of deduplicated data segments is referred to by one or more deduplication references;

procure reference data that indicates, for each data segment in the set of deduplicated data segments, a number of deduplication references on the client system that point to the data segment, wherein the number of deduplication references that point to the data segment comprises a total count of how many individual deduplication references, collections of deduplication references, or both, point to the data segment;

use the reference data to select one or more data segments from the set of deduplicated data segments for client-side caching;

cache at least one of the one or more data segments or references to the one or more data segments in a cache on the client system;

restore the one or more data segments from the client system wherein restoration comprises at least one of restoring the one or more data segments from the cache on the client system or querying the cache to determine where the one or more data segments are stored on the client system.

16. The non-transitory computer-readable-storage medium of claim 15, wherein the one or more computer-executable instructions are further programmed to cause the computing device to create a mapping table of the one or more data segments.

17. The non-transitory computer-readable-storage medium of claim 16, wherein the one or more computer-executable instructions are programmed to cause the computing device to create the mapping table of the one or more data segments by:

calculating a fingerprint for each of the one or more data segments;

mapping the fingerprint of each of the one or more data segments to the content of each of the one or more data segments.

18. The non-transitory computer-readable-storage medium of claim 16, wherein the one or more computer-executable instructions are programmed to cause the computing device to create the mapping table of the one or more data segments my performing at least one of:

creating the mapping table during a deduplication process;

creating the mapping table during a data restoration process;

creating the mapping table based on deduplication metadata of a backup of the set of deduplication data segments.