Backup and restore strategies for data deduplication

• US 9,823,981 B2
• Filed: 03/11/2011
• Issued: 11/21/2017
• Est. Priority Date: 03/11/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kalach, Ran, Cheung, Chun Ho (Ian), Oltean, Paul Adrian, Dickson, Mathew James
• Primary Examiner(s): Simonetti, Nicholas
• Application Number:
  US13/045,692
• Publication Number:
  US 20120233417A1
• Time in Patent Office: 2,447 Days
• Field of Search: 711161-162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 3/0641 De-duplication techniques

Abstract

Techniques for backup and restore of optimized data streams are described. A chunk store includes each optimized data stream as a plurality of chunks including at least one data chunk and corresponding optimized stream metadata. The chunk store includes data chunks in a deduplicated manner. Optimized data streams stored in the chunk store are identified for backup. At least a portion of the chunk store is stored in backup storage according to an optimized backup technique, an un-optimized backup technique, an item level backup technique, or a data chunk identifier backup technique. Optimized data streams stored in the backup storage may be restored. A file reconstructor includes a callback module that generates calls to a restore application to request optimized stream metadata and any referenced data chunks from the backup storage. The file reconstructor reconstructs the data streams from the referenced data chunks.

Claims

1. A method for data stream backup, comprising:

identifying for backup a plurality of optimized data streams stored in a chunk store, the chunk store including each optimized data stream as a plurality of chunks and corresponding optimized stream metadata, the plurality of chunks including at least one data chunk, the corresponding optimized stream metadata referencing the at least one data chunk, and the chunk store including all included data chunks in a deduplicated manner before the identification for the backup; and

storing at least a portion of the chunk store in a backup storage to backup the plurality of optimized data streams identified for backup,

wherein said storing comprises

determining whether the plurality of optimized data streams were selected for backup according to an exclude mode or an include mode, the exclude mode being a first backup mode where at least one volume is specifically selected for backup and one or more data streams are specifically selected to be excluded from backup, and the include mode being a second backup mode where at least one data stream is specifically selected for backup; and

selecting the backup technique based on which of the exclude mode or include mode was determined to be selected.

2. The method of claim 1, wherein said storing comprises:

storing the chunk store in its entirety in the backup storage; and

storing a plurality of stream metadata stubs in the backup storage for the plurality of optimized data streams, wherein each stream metadata stub links a data stream to corresponding data in the chunk store.

3. The method of claim 1, wherein said storing comprises:

rehydrating each optimized data stream into a corresponding un-optimized data stream that includes any data chunks referenced by the corresponding optimized stream metadata; and

storing each un-optimized data stream in the backup storage to backup the plurality of optimized data streams.

4. The method of claim 1, wherein said storing comprises:

receiving a first optimized data stream identified for backup;

determining one or more data chunks referenced by the optimized stream metadata of the first optimized data stream and not already stored in the backup storage;

storing the optimized stream metadata of the first optimized data stream in the backup storage; and

storing the determined one or more data chunks in the backup storage.

5. The method of claim 1, wherein said storing comprises:

analyzing the optimized stream metadata corresponding to each optimized data stream to determine a corresponding at least one data chunk identifier for the at least one data chunk referenced by the optimized stream metadata;

storing an optimized stream structure for each optimized data stream in the backup storage with the corresponding at least one data chunk identifier; and

storing one or more chunk containers of the chunk store in the backup storage that store data chunks of the optimized data streams.

6. The method of claim 1, wherein said selecting the backup technique based on which of the exclude mode or include mode was determined to be selected comprises:

selecting the backup technique to be an optimized data stream backup technique if the exclude mode was determined to be selected; and

selecting the backup technique to be an un-optimized data stream backup technique if the include mode was determined to be selected.

7. The method of claim 1, wherein said identifying comprises:

identifying each optimized data stream by file name.

8. The method of claim 1, wherein the include mode includes a lesser number of one or more data streams than the exclude mode.

9. A method for restoring files from backup, comprising:

receiving a request for an optimized data stream to be retrieved from a chunk store in backup storage, the request including an identifier for the optimized stream metadata corresponding to the data stream;

generating a first call to a restore application based on the optimized stream metadata, the first call specifying a file name for a first chunk container in backup storage that stores optimized stream metadata identified by the optimized stream metadata identifier, and specifying an offset for the optimized stream metadata in the first chunk container;

receiving the optimized stream metadata in response to the first call;

determining at least one data chunk identifier referenced in the optimized stream metadata;

generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in backup storage; and

receiving the at least one data chunk in response to the at least one additional call.

10. The method of claim 9, wherein said generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in backup storage comprises:

generating a second call to the restore application based on a corresponding data chunk identifier, the second call specifying a file name for a second chunk container in backup storage that stores a data chunk identified by the data chunk identifier, and specifying an offset for the identified data chunk in the second chunk container.

11. The method of claim 9, wherein said generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in backup storage comprises:

accessing a redirection table to map a first offset included in a data chunk identifier for a data chunk to a second offset;

generating a second call to the restore application based on the data chunk identifier, the second call specifying a file name for a second chunk container in backup storage that stores a data chunk corresponding to the data chunk identifier, and specifying the second offset for the data chunk in the second chunk container.

12. The method of claim 9, wherein the first call specifies the file name for the first chunk container in backup storage that stores the optimized stream metadata as a stream map chunk, the offset for the stream map chunk in the first chunk container, and a header size for the stream map chunk, wherein said generating a first call comprises:

generating the first call to obtain a stream map header for the stream map chunk;

determining a size of the stream map chunk from the stream map header; and

generating a second call to obtain the stream map chunk, the second call specifying the file name for the first chunk container in backup storage that stores the stream map chunk, the offset for the stream map chunk in the first chunk container, and the size of the stream map chunk.

13. The method of claim 9, wherein a plurality of data chunk identifiers are referenced in the optimized stream metadata, the method further comprising:

sorting the plurality of data chunk identifiers based on a determined chunk container as a first sort key and a chunk offset as a second key; and

wherein said generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in backup storage comprises;

generating a plurality of additional calls to the restore application corresponding to the plurality of data chunk identifiers in an order defined by said sorting.

14. The method of claim 9, further comprising;

generating an additional call to the restore application to generate a sorted list of chunk containers;

wherein said generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in backup storage comprises;

generating a plurality of additional calls to the restore application corresponding to the plurality of data chunks in an order defined by the sorted list.

15. The method of claim 9, further comprising:

generating an additional call to the restore application that includes a list of all data chunks of the data stream to be restored and associated with at least one chunk container, and includes at least one of a file name of a container, a chunk offset in the container for at least one data chunk, and a data chunk size for the at least one data chunk in the container.

16. A system, comprising:

a data backup module that receives an identification of a plurality of optimized data streams stored in a chunk store for backup, the chunk store including each optimized data stream as a plurality of chunks and corresponding optimized stream metadata, the plurality of chunks including at least one data chunk, the corresponding optimized stream metadata referencing the at least one data chunk, the chunk store including all included data chunks in a deduplicated configuration before the identification for the backup; and

the data backup module being configured to store at least a portion of the chunk store in a backup storage to backup the plurality of optimized data streams identified for backup, determine a first amount of space in the chunk store consumed by data chunks that are not referenced by the plurality of optimized data streams identified for backup, determine a second amount of space as an amount of space to store all of the plurality of optimized data streams in un-optimized form minus an amount of space to store all of the plurality of optimized data streams in optimized form, and select a backup technique based on the determined first and second amounts of space.

17. The system of claim 16, wherein the data backup module is further configured to:

select the backup technique to be an optimized data stream backup technique if the determined first amount of space is less than the determined second amount of space; and

select the backup technique to be an un-optimized data stream backup technique if the determined first amount of space is greater than the determined second amount of space.

18. The system of claim 16, wherein the data backup module comprises at least one of

an optimized file backup module configured to store the chunk store in its entirety in the backup storage;

a rehydrating backup module configured to rehydrate each optimized data stream into a corresponding un-optimized data stream that includes any data chunks referenced by the corresponding optimized stream metadata, and to store each un-optimized data stream in the backup storage;

an item level backup module configured for each optimized data stream to determine one or more data chunks referenced by the optimized stream metadata of the optimized data stream and not already stored in the backup storage, to store the optimized stream metadata of the optimized data stream in the backup storage, and to store the determined one or more data chunks in the backup storage;

or

a data chunk identifier backup module configured to analyze the optimized stream metadata of each optimized data stream to determine a corresponding at least one data chunk identifier for the at least one data chunk referenced by the optimized stream metadata, to store each optimized data stream in the backup storage with the corresponding at least one data chunk identifier, and to store one or more chunk containers of the chunk store in the backup storage that store data chunks of the optimized data streams.

19. The system of claim 16, further comprising:

a file reconstructor that receives a request for a data stream to be retrieved from a chunk store in the backup storage, the request including an identifier for optimized stream metadata corresponding to the data stream;

the file reconstructor including a callback module that generates a first call to a restore application based on the optimized stream metadata identifier, the first call specifying a file name for a first chunk container in the backup storage that stores optimized stream metadata identified by the optimized stream metadata identifier, and specifying an offset for the optimized stream metadata in the first chunk container;

the file reconstructor receiving the optimized stream metadata in response to the first call, and determining at least one data chunk identifier referenced in the optimized stream metadata;

the callback module generating at least one additional call to the restore application corresponding to the at least one data chunk identifier to obtain at least one data chunk from at least one chunk container in the backup storage; and

the file reconstructor receiving the at least one data chunk in response to the at least one additional call, and combining the at least one data chunk to restore the data stream.

20. The system of claim 16, wherein the data backup module identifies each optimized data stream by file name.