Efficient data storage using resemblance of data segments

• US 20070239945A1
• Filed: 04/11/2006
• Published: 10/11/2007
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Li, Kai, Maheshwari, Umesh, Yang, Zheng, Zhu, Ming
• Granted Patent: US 7,562,186 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 16/1756 based on delta files

Abstract

Storage using resemblance of data segments is disclosed. It is determined that a new segment resembles a prior stored segment. The prior stored segment comprises a segment stored previously from any location in an input data stream. A delta between the new segment and the prior stored segment is determined. A representation of the new segment based at least in part on the delta is stored.

Claims

1. A method of storage using resemblance of data segments comprising:

determining that a new segment resembles a prior stored segment, wherein the prior stored segment comprises a segment stored previously from any location in an input data stream;

determining a delta between the new segment and the prior stored segment; and

storing a representation of the new segment based at least in part on the delta.

2. A method as in claim 1, wherein the delta comprises a difference between the new segment and the prior stored segment.

3. A method as in claim 1, wherein determining resemblance comprises comparing a summary feature set of the new segment with a summary feature set of the prior stored segment.

4. A method as in claim 1, further comprising in the event that a new segment does not resemble the prior stored segment, storing the new segment.

5. A method as in claim 1, wherein storing the representation of the new segment comprises storing the delta and an indication of the prior stored segment.

6. A method as in claim 1, wherein storing the representation of the new segment in the event that the delta is larger than a predetermined threshold comprises storing the new segment.

7. A method as in claim 1, wherein storing the representation of the new segment comprises storing the delta combined with a second delta.

8. A method as in claim 1, wherein storing the representation of the new segment comprises locally compressing the new segment.

9. A method as in claim 1, wherein storing the representation of the new segment comprises locally compressing the delta.

10. A method as in claim 1, wherein an identifier is computed for the new segment.

11. A method as in claim 1, wherein an identifier is computed for the new segment and comprises a fingerprint.

12. A method as in claim 1, wherein an identifier is computed for the new segment and comprises a serially generated number.

13. A method as in claim 1, wherein an identifier is computed for the delta.

14. A method as in claim 1, wherein an identifier is computed for the delta and comprises a fingerprint.

15. A method as in claim 1, wherein an identifier is computed for the delta and comprises a serially generated number.

16. A method as in claim 1, wherein storing the representation of the new segment comprises packing the new segment in a container.

17. A method as in claim 1, wherein storing the representation of the new segment comprises packing the delta in a container.

18. A method as in claim 1, wherein storing the representation of the new segment comprises storing the representation of the new segment in a backup storage system.

19. A method as in claim 1, wherein new segment is associated with a first input data stream and the prior stored segment is associated with a second input data stream.

20. A method as in claim 1, wherein resemblance comprises a byte for byte similarity between the new segment and the prior stored segment.

21. A method as in claim 1, wherein there is no loss of information in storing the new segment.

22. A computer program product for storage using resemblance of data segments, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

determining that a new segment resembles a prior stored segment, wherein the prior stored segment comprises a segment stored previously from any location in an input data stream;

determining a delta between the new segment and the prior stored segment; and

storing a representation of the new segment based at least in part on the delta.

23. A system for storage using resemblance of data segments comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

determine that a new segment resembles a prior stored segment, wherein the prior stored segment comprises a segment stored previously from any location in an input data stream;

determine a delta between the new segment and the prior stored segment; and

store a representation of the new segment based at least in part on the delta.