BACKUP AND RESTORE STRATEGIES FOR DATA DEDUPLICATION

• US 20120233417A1
• Filed: 03/11/2011
• Published: 09/13/2012
• Est. Priority Date: 03/11/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kalach, Ran, Cheung, Chun Ho (Ian), Oltean, Paul Adrian, Dickson, Mathew James
• Granted Patent: US 9,823,981 B2
• Time in Patent Office: Days
• US Class Current: 711/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; and

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

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, the chunk store being excluded from being stored in the backup storage.

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 storing comprises:

selecting a backup technique based on heuristics; and

performing the backup technique to backup the plurality of optimized data streams in the backup storage.

7. The method of claim 6, wherein said selecting a backup technique based on heuristics 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;

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.

8. The method of claim 6, wherein said selecting a backup technique based on heuristics comprises:

determining 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;

determining 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;

selecting 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

selecting 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.

9. The method of claim 6, wherein said selecting a backup technique based on heuristics comprises:

determining a first amount of space as an amount of space to store all of the plurality of data streams identified for backup in un-optimized form;

determining a second amount of space as a sum of an amount of space to store the chunk store and an amount of space to store all of the plurality of data streams identified for backup in optimized form;

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

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

10. 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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

13. The method of claim 10, 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.

14. The method of claim 10, wherein a plurality of data chunk identifiers is 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.

15. The method of claim 10, further comprising;

generating an additional call to the restore application to generated 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.

16. The method of claim 10, 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.

17. 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; 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.

18. The system of claim 17, 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;

an 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 17, wherein the data backup module includes a heuristics module that is configured to select a backup technique based on heuristics, and to enable the backup technique to be performed to backup the plurality of optimized data streams in the backup storage.

20. The system of claim 17, 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.