Efficient data storage using resemblance of data segments

• US 7,562,186 B2
• Filed: 04/11/2006
• Issued: 07/14/2009
• 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 Benjamin
• Primary Examiner(s): Elmore; Reba I
• Application Number:
  US11/402,631
• Publication Number:
  US 20070239945A1
• Time in Patent Office: 1,190 Days
• Field of Search: 711/112, 711/156, 711/162, 711/172
• US Class Current: 711/112
• 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, using a processor, 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, wherein the segment stored previously is one of a plurality of previously stored segments and wherein at least one segment of the plurality of previously stored segments is required to reconstruct a plurality of data files;

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

storing on a storage device 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, wherein the segment stored previously is one of a plurality of previously stored segments and wherein at least one segment of the plurality of previously stored segments is required to reconstruct a plurality of data flies;

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 wherein the segment stored previously is one of a plurality of previously stored segments and wherein at least one segment of the plurality of previously stored segments is required to reconstruct a plurality of data files;

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.

24. A system as in claim 23, wherein the representation of the new segment is stored on a remote restorer system.

25. A system as in claim 23, wherein the representation of the new segment is stored on a local restorer system.

26. A system as in claim 23, wherein the delta comprises a difference between the new segment and the prior stored segment.

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

28. A system as in claim 23, 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 a new segment does not resemble the prior stored segment.

29. A system as in claim 23, wherein storing the representation of the new segment comprises storing the delta and an indication of the prior stored segment.

30. A system as in claim 23, 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.

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

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

33. A system as in claim 23, wherein storing the representation of the new segment comprises locally compressing the delta.

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

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

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

37. A system as in claim 23, wherein an identifier is computed for the delta.

38. A system as in claim 23, wherein an identifier is computed for the delta and comprises a fingerprint.

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

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

41. A system as in claim 23, wherein storing the representation of the new segment comprises packing the delta in a container.

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

43. A system as in claim 23, wherein new segment is associated with a first input data stream and the prior stored segment is associated with a second input data stream.

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

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