Representing de-duplicated file data

• US 8,396,839 B1
• Filed: 06/25/2010
• Issued: 03/12/2013
• Est. Priority Date: 06/25/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Huang, Mark
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US12/803,393
• Time in Patent Office: 991 Days
• Field of Search: 707/664, 707/692, 707/999.107, 707/999.204, 711/161, 711/162
• US Class Current: 707/664
• 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 subset of de-duplicated is outputted. In some embodiments, the output includes a subset of data stored in de-duplicated form in a plurality of containers each including a plurality of data segments comprising the data. For each container that includes one or more data segments comprising the subset, a corresponding container data is included in the output. Each container may include one or more segments not included in the subset. For each container the corresponding container data of which is included in the output, a corresponding value in a data structure including for each container stored on the de-duplicated storage system a data value indicating whether or not the corresponding container data has been included in the output is updated.

Claims

1. A method comprising:

receiving an indication of an input identifying a subset of data to be provided as output, wherein the subset of data has been stored in de-duplicated form;

identifying a plurality of containers that includes one or more data segments comprising the subset of data, wherein each of the plurality of containers may include one or more segments not included in the subset of data;

determining, for each of the plurality of containers, whether corresponding container data has already been included in an output stream based at least in part on a data structure comprising for each of at least a subset of container stored on the de-duplicated storage system an indication of whether or not the corresponding container data has been included in the output stream;

retrieving a corresponding de-duplicated container data for each container that is determined to comprise container data that has not been previously included in the output stream;

providing to the output stream the retrieved container data for each container that includes container data that has not been previously included in the output stream; and

for each container from which corresponding container data is included in the output, updating the corresponding value in the data structure.

2. The method of claim 1, wherein the container data is included in the output in a same form in which it is stored in the de-duplicated storage system.

3. The method of claim 1, further comprising receiving an identification of the subset of de-duplicated data to be provided as output.

4. The method of claim 1, further comprising determining for each of a plurality of files or other objects comprising the subset a set of one or more containers each of which includes one or more segments comprising the file or other object.

5. The method of claim 1, wherein data is stored on the de-duplicated storage in compressed and de-duplicated form.

6. The method of claim 1, wherein the data structure comprises a bit mask.

7. The method of claim 5, wherein the bit mask comprises for each of said plurality of containers a corresponding bit.

8. The method of claim 1, further comprising writing the output to a tape or other removable storage media.

9. The method of claim 1, further comprising identifying a container as including one or more segments comprising the subset and reading from the data structure the data value corresponding to the container to determine whether the corresponding container data has or has not already been included in the output.

10. The method of claim 8, further comprising reading the corresponding container data and writing the corresponding container data to an output stream associated with the output if it is determined by reading the data value corresponding to the container that the corresponding container data has not already been included in the output.

11. The method of claim 1, further comprising receiving the output at a destination deduplication storage.

12. The method of claim 10, wherein the container data included in the output as stored in a de-duplicated storage system comprises compressed data and the destination deduplication storage is configured to write the container data included in the output to disk without decompressing the container data.

13. The method of claim 11, wherein the destination deduplication storage is further configured to index the segments comprising the container data included in the output.

14. The method of claim 1, further comprising receiving the output at a destination system configured to read a segment reference associated with a file comprising the subset;

look up a corresponding offset within the output of a container data comprising the segment;

read and decompress the container data comprising the segment; and

write the segment data to the file as stored on the destination system.

15. The method of claim 13, wherein the destination system is further configured to record in a container offset map, for each set of container data encountered in the output, a corresponding offset or other location of the container data within the output.

16. The method of claim 1, further comprising receiving the output at a destination system configured to cache container data included in the stream.

17. The method of claim 16, wherein the destination system is configured to generate and store an index of segments comprising the cached container data.

18. The method of claim 17, wherein the destination system is configured to read a segment reference in the output and use the index of segments comprising the cached container data to read a segment data associated with the segment reference from the cached container data.

19. A data storage system, comprising:

a processor configured to provide as output a subset of de-duplicated data stored in de-duplicated form in a plurality of containers each comprising a plurality of data segments comprising the de-duplicated data, including by;

receiving an indication of an input identifying a subset of data to be provided as output, wherein the subset of data has been stored in de-duplicated form;

identifying a plurality of containers that includes one or more data segments comprising the subset of data, wherein each of the plurality of containers may include one or more segments not included in the subset of data;

determining, for each of the plurality of containers, whether corresponding container data has already been included in an output stream based at least in part on a data structure comprising for each of at least a subset of container stored on the de-duplicated storage system an indication of whether or not the corresponding container data has been included in the output stream;

retrieving a corresponding de-duplicated container data for each container that is determined to comprise container data that has not been previously included in the output stream;

providing to the output stream the retrieved container data for each container that includes container data that has not been previously included in the output stream;

for each container from which corresponding container data is included in the output, updating the corresponding value in the data structure comprising; and

a memory coupled to the processor and configured to store the data structure.

20. The system of claim 19, wherein the processor is further configured to determine for each of a plurality of files or other objects comprising the subset a set of one or more containers each of which includes one or more segments comprising the file or other object.

21. The system of claim 19, further comprising a storage device configured to store said corresponding container data.

22. The system of claim 19, wherein the processor is further configured to identify a container as including one or more segments comprising the subset and read from the data structure the data value corresponding to the container to determine whether the corresponding container data has or has not already been included in the output.

23. The system of claim 22, wherein the processor is further configured to read the corresponding container data and write the corresponding container data to an output stream associated with the output if it is determined by reading the data value corresponding to the container that the corresponding container data has not already been included in the output.

24. A computer program product for providing as output a subset of data stored in de-duplicated form in a plurality of containers each comprising a plurality of data segments comprising the data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving an indication of an input identifying a subset of data to be provided as output, wherein the subset of data has been stored in de-duplicated form;

identifying a plurality of containers that includes one or more data segments comprising the subset of data, wherein each of the plurality of containers may include one or more segments not included in the subset of data;

determining, for each of the plurality of containers, whether corresponding container data has already been included in an output stream based at least in part on a data structure comprising for each of at least a subset of container stored on the de-duplicated storage system an indication of whether or not the corresponding container data has been included in the output stream;

retrieving a corresponding de-duplicated container data for each container that is determined to comprise container data that has not been previously included in the output stream;

providing to the output stream the retrieved container data for each container that includes container data that has not been previously included in the output stream; and

for each container from which corresponding container data is included in the output, updating the corresponding value in the data structure.