Delta compression after identity deduplication

• US 20100125553A1
• Filed: 11/14/2008
• Published: 05/20/2010
• Est. Priority Date: 11/14/2008
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Huang, Mark, Wallace, Grant, Shilane, Philip, Li, Kai, Zhu, Ming Benjamin, Lee, Edward K.
• Granted Patent: US 8,751,462 B2
• Time in Patent Office: Days
• US Class Current: 707/661
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3091 Data deduplication

Abstract

Delta compression after identity deduplication is disclosed. A first data segment is determined to be identical to a first previous data segment. A second data segment, not determined to be identical to a second previous data segment, is then determined to be similar to a third previous data segment.

Claims

1. A system for processing data, comprising:

a deduplicating system for determining that a first data segment is identical to a first previous data segment; and

a delta compression system for determining that a second data segment not determined to be identical to a second previous data segment and is similar to a third previous data segment.

2. A system as in claim 1, wherein the deduplicating system receives a data stream or data block.

3. A system as in claim 2, wherein the deduplicating system breaks the data stream or data block into a plurality of data segments.

4. A system as in claim 1, wherein the deduplicating system further comprises storing a reference to the first previous data segment instead of storing the first data segment.

5. A system as in claim 1, wherein determining that the first data segment is identical comprises:

determining a first data segment ID associated with the first data segment;

determining whether the first data segment ID is identical to a previously stored ID in an ID index.

6. A system as in claim 5, where determining the first data segment ID associated with the first data segment uses one or more of the following:

a fingerprint function, a hash function, a cryptographic hash function, and a digital signature.

7. A system as in claim 1, wherein the delta compression system further comprises computing an encoding of the second data segment.

8. A system as in claim 7, wherein the delta compression system further comprises storing the encoding of the second data segment.

9. A system as in claim 7, further comprising compressing the encoding of the second data segment.

10. A system as in claim 7, further comprising transmitting the encoding of the second data segment.

11. A system as in claim 7, further comprising replicating the encoding of the second data segment.

12. A system as in claim 7, wherein the encoding is based at least in part on the third previous data segment.

13. A system as in claim 7, wherein the encoding comprises an indication of a set of data blocks in the second data segment not present in the third previous data segment and an indication of a set of data blocks in the third previous data segment.

14. A system as in claim 7, wherein the delta compression system further comprises determining whether the encoding is smaller than the second data segment.

15. A system as in claim 1, wherein the second data segment is determined to be similar to the similar third previous data segment using a sketch function.

16. A system as in claim 15, wherein the sketch function comprises a hash function.

17. A system as in claim 15, wherein the sketch function comprises a plurality of hash functions.

18. A system as in claim 15, wherein the sketch function comprises one or more functions that returns a same value for similar data segments.

19. A system as in claim 15, wherein the sketch function comprises one or more functions that returns a similar value for similar data segments.

20. A system as in claim 15, wherein the sketch function comprises one or more functions that may return a same value for similar data segments.

21. A system as in claim 15, wherein the sketch function comprises one or more functions that may return a similar value for similar data segments.

22. A system as in claim 21, wherein sketch function values are determined to be similar based on one or more of the following methods:

numeric difference, hamming distance, locality-sensitive-hashing, or nearest-neighbor-search.

23. A system as in claim 1, wherein the second data segment is similar to one or more previous segments in addition to the third previous data segment.

24. A system as in claim 23, wherein the delta compression system further comprises computing an encoding of the second data segment.

25. A system as in claim 24, wherein the encoding is based at least in part on the third previous data segment and the one or more additional similar previous data segments.

26. A system as in claim 23, wherein the one or more previous data segments and third previous data segment are identified based at least in part on one or more of the following:

temporal locality, spatial locality, ease of access, expected compression, or frequency of selection for other compressed segments.

27. A system as in claim 1, wherein the third previous data segment was stored as an encoding of a fourth previous data segment.

28. A method for processing data, comprising:

determining that a first data segment is identical to a first previous data segment; and

determining that a second data segment not determined to be identical to a second previous data segment is similar to a third previous data segment.

29. A method as in claim 28, further comprising receiving a data stream or data block.

30. A method as in claim 28, further comprising breaking the data stream or data block into a plurality of data segments.

31. A method as in claim 28, further comprising storing a reference to the first previous data segment instead of storing the first data segment.

32. A method as in claim 28, wherein determining that the first data segment is identical comprises:

determining a first data segment ID associated with the first data segment;

determining whether the first data segment ID is identical to a previously stored ID in an ID index.

33. A method as in claim 32, where determining the first data segment ID associated with the first data segment uses one or more of the following:

a fingerprint function, a hash function, a cryptographic hash function, and a digital signature.

34. A method as in claim 28, further comprising computing an encoding of the second data segment.

35. A method as in claim 34, further comprising storing the encoding of the second data segment.

36. A method as in claim 34, further comprising compressing the encoding of the second data segment.

37. A method as in claim 34, further comprising transmitting the encoding of the second data segment.

38. A method as in claim 34, further comprising replicating the encoding of the second data segment.

39. A method as in claim 34, wherein the encoding is based at least in part on the third previous data segment.

40. A method as in claim 34, wherein the encoding comprises an indication of a set of data blocks in the second data segment not present in the third previous data segment and an indication of a set of data blocks in the third previous data segment.

41. A method as in claim 34, further comprising determining whether the encoding is smaller than the second data segment.

42. A method as in claim 34, wherein the second data segment is determined to be similar to the similar third previous data segment using a sketch function.

43. A method as in claim 42, wherein the sketch function comprises a hash function.

44. A method as in claim 42, wherein the sketch function comprises a plurality of hash functions.

45. A method as in claim 42, wherein the sketch function comprises one or more functions that returns a same value for similar data segments.

46. A method as in claim 42, wherein the sketch function comprises one or more functions that returns a similar value for similar data segments.

47. A method as in claim 42, wherein the sketch function comprises one or more functions that may return the same value for similar data segments.

48. A method as in claim 42, wherein the sketch function comprises one or more functions that may return a similar value for similar data segments.

49. A method as in claim 48, wherein sketch function values are determined to be similar based on one or more of the following methods:

numeric difference, hamming distance, locality-sensitive-hashing, or nearest-neighbor-search.

50. A method as in claim 34, wherein the second previous segment is similar to one or more previous segments in addition to the third previous data segment.

51. A method as in claim 50, wherein the delta compression system further comprises computing an encoding of the second data segment.

52. A method as in claim 51, wherein the encoding is based at least in part on the third previous data segment and the one or more additional similar previous data segments.

53. A method as in claim 50, wherein the one or more previous data segments and third previous data segment are identified based at least in part on one or more of the following:

temporal locality, spatial locality, ease of access, expected compression, or frequency of selection for other compressed segments.

54. A method as in claim 28, wherein the third previous data segment was stored as an encoding of a fourth previous data segment.

55. A computer program product for processing data, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

determining that a first data segment is identical to a first previous data segment; and

determining that a second data segment not determined to be identical to a second previous data segment is similar to a third previous data segment.