Efficient data storage using two level delta resemblance

• US 7,949,824 B2
• Filed: 04/11/2006
• Issued: 05/24/2011
• Est. Priority Date: 04/11/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Zhu, Ming Benjamin
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Verderamo, III; Ralph A
• Application Number:
  US11/403,146
• Publication Number:
  US 20070239946A1
• Time in Patent Office: 1,869 Days
• Field of Search: 711/154
• US Class Current: 711/112
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

Storage using resemblance of data segments is disclosed. It is determined that a new segment resembles a second prior stored segment wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment. A second 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 second delta is stored.

Claims

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

breaking up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;

determining that the new segment resembles a second prior stored segment, wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, and wherein resembling is based at least in part on a comparison between a subset of values of a set of values calculated by applying one or more functions to at least a portion of the new segment and a plurality of corresponding values calculated by applying the one or more functions to at least a portion of the second prior stored segment, wherein the subset of values comprises one of the following;

a lowest n values of the set of values, a highest m values of the set of values, or a lowest k values of the set of values and a highest l values of the set of values, wherein n, m, k, and l are integers;

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

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

2. A non-transitory computer readable storage medium storing a computer program product comprising computer instructions for:

breaking up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;

determining that the new segment resembles a second prior stored segment, wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, and wherein resembling is based at least in part on a comparison between a subset of values of a set of values calculated by applying one or more functions to at least a portion of the new segment and a plurality of corresponding values calculated by applying the one or more functions to at least a portion of the second prior stored segment, wherein the subset of values comprises one of the following;

a lowest n values of the set of values, a highest m values of the set of values, or a lowest k values of the set of values and a highest l values of the set of values, wherein n, m, k, and l are integers;

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

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

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

break up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;

determine that the new segment resembles a second prior stored segment, wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, and wherein resembling is based at least in part on a comparison between a subset of values of a set of values calculated by applying one or more functions to at least a portion of the new segment and a plurality of corresponding values calculated by applying the one or more functions to at least a portion of the second prior stored segment, wherein the subset of values comprises one of the following;

a lowest n values of the set of values, a highest m values of the set of values, or a lowest k values of the set of values and a highest l values of the set of values, wherein n, m, k, and l are integers;

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

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

4. A system as in claim 3, wherein the second delta comprises a difference between the new segment and the second prior stored segment.

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

6. A system as in claim 3, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to store the new segment in the event that the new segment does not resemble the second prior stored segment.

7. A system as in claim 3, wherein storing the representation of the new segment comprises storing the second delta, an indication of the first stored delta, and an indication of the first prior stored segment.

8. A system as in claim 3, wherein storing the representation of the new segment in the event that the second delta is larger than a predetermined threshold comprises storing the new segment.

9. A system as in claim 3, wherein storing the representation of the new segment in the event that the second delta is larger than a predetermined threshold and the new segment resembles the first prior stored segment comprises storing a third delta and an indication of the first prior stored segment.

10. A system as in claim 9, wherein the third delta comprises a difference between the new segment and the first prior stored segment.

11. A system as in claim 9, wherein determining resemblance comprises comparing a summary feature set of the new segment with a summary feature set of the first prior stored segment.

12. A system as in claim 9, wherein storing the representation of the new segment comprises storing the third delta combined with a fifth delta.

13. A system as in claim 9, wherein storing the representation of the new segment comprises locally compressing the third delta.

14. A system as in claim 9, wherein an identifier is computed for the third delta.

15. A system as in claim 9, wherein an identifier is computed for the third delta and comprises a fingerprint.

16. A system as in claim 9, wherein an identifier is computed for the third delta and comprises a serially generated number.

17. A system as in claim 9, wherein storing the representation of the new segment comprises packing the third delta in a container.

18. A system as in claim 3, wherein storing the representation of the new segment comprises storing the second delta combined with a fourth delta.

19. A system as in claim 3, wherein storing the representation of the new segment comprises locally compressing the new segment.

20. A system as in claim 3, wherein storing the representation of the new segment comprises locally compressing the second delta.

21. A system as in claim 3, wherein an identifier is computed for the new segment.

22. A system as in claim 3, wherein an identifier is computed for the new segment and comprises a fingerprint.

23. A system as in claim 3, wherein an identifier is computed for the new segment and comprises a serially generated number.

24. A system as in claim 3, wherein an identifier is computed for the second delta.

25. A system as in claim 3, wherein an identifier is computed for the second delta and comprises a fingerprint.

26. A system as in claim 3, wherein an identifier is computed for the second delta and comprises a serially generated number.

27. A system as in claim 3, wherein storing the representation of the new segment comprises packing the new segment in a container.

28. A system as in claim 3, wherein storing the representation of the new segment comprises packing the second delta in a container.

29. A system as in claim 3, wherein storing the representation of the new segment comprises storing the representation of the new segment in a backup storage system.

30. A system as in claim 3, wherein resemblance comprises a byte for byte similarity between the new segment and the second prior stored segment.

31. A system as in claim 3, wherein there is no loss of information in storing the new segment.