Locality-based stream segmentation for data deduplication

• US 7,504,969 B2
• Filed: 07/11/2006
• Issued: 03/17/2009
• Est. Priority Date: 07/11/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Data Domain, Inc. (Dell Technologies Inc.)
• Inventors: Maheshwari, Umesh, Patterson, R. Hugo
• Primary Examiner(s): JEANGLAUDE, JEAN BRUNER
• Application Number:
  US11/484,881
• Publication Number:
  US 20080013830A1
• Time in Patent Office: 980 Days
• Field of Search: 341/50, 341/51, 704/235, 345/649
• US Class Current: 341/51
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques

Abstract

Selecting a segment boundary comprises determining a segmentation window is determined and computing a plurality of values associated with candidate boundaries within the segmentation window. Selecting a segment boundary further comprises selecting one of the candidate boundaries based at least in part on a comparison between two or more of the computed values and determining a boundary within the segmentation window.

Claims

1. A method for selecting a segment boundary comprising:

determining a segmentation window;

computing a plurality of values associated with candidate boundaries within the segmentation window;

selecting one of the candidate boundaries based at least in part on a comparison between two or more of the computed values; and

determining a boundary within the segmentation window.

2. A method as in claim 1, wherein the segmentation window is within a data stream.

3. A method as in claim 1, wherein the segmentation window is within a data block.

4. A method as in claim 1, wherein determining the segmentation window includes determining a location corresponding to a minimum segment length.

5. A method as in claim 1, wherein determining the segmentation window includes determining a location corresponding to a maximum segment length.

6. A method as in claim 1, wherein computing a plurality of values associated with candidate boundaries within the segmentation window includes determining a plurality of windows where each window is associated with a location within the segmentation window.

7. A method as in claim 1, wherein computing a plurality of values associated with candidate boundaries within the segmentation window includes determining a plurality of windows where each window is associated with a candidate boundary within the segmentation window.

8. A method as in claim 1, wherein computing each value includes determining a value of a function based at least in part on one or more data values within one of a plurality of windows.

9. A method as in claim 1, wherein computing each value includes determining a value of a function, wherein the function comprises one or more of the following:

a hash function, a hash function combined with a masking function, SHA-1 (Secure Hash Algorithm

     1), SHA-256, SHA-384, SHA-512, MD5 (Message-Digest algorithm

     5), RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest 160-bit version), a Rabin hash, a fingerprint, a CRC (Cyclic Redundancy Check), a sum, or an xor.

10. A method as in claim 1, wherein selecting a candidate boundary comprises selecting a location within the segmentation window with an associated value that is one of the following:

an extrema value compared to the plurality of values, a minimum value compared to the plurality of values, a maximum value compared to the plurality of values, a value with the longest run of 1 bits in its value compared to the plurality of values, or a value with the most 1 bits in its value compared to the plurality of values.

11. A method as in claim 1, wherein the segment boundary location is determined such that a segment is defined.

12. A method as in claim 11, wherein the segment represents a segment in a sequence of segments.

13. A method as in claim 11, wherein the segment enables reconstruction of data values of a segment in a sequence of segments.

14. A method as in claim 11, wherein the segment enables identification of a difference between a first segment and a second segment.

15. A method as in claim 11, wherein the segment enables identification of a similarity between a first segment and a second segment.

16. A method as in claim 11, wherein the segment enables elimination of duplicate segments.

17. A method as in claim 11, wherein the segment enables one of the following:

a storage system, a backup storage system, or a transmission system.

18. A method as in claim 1, further comprising storing a computed value in an ordered stack of values, wherein the ordered stack of values includes ordered values computed since a last extrema value.

19. A method as in claim 18, wherein storing the value in the ordered stack of values includes comparing the computed value with values from the ordered stack of values.

20. A method as in claim 18, wherein storing the value in the ordered stack of values includes removing a value from the ordered stack of values.

21. A method as in claim 18, further comprising determining a boundary location based at least in part on the ordered stack of values.

22. A method as in claim 18, further comprising determining a boundary location based at least in part on the ordered stack of values, wherein the boundary location is offset an offset distance from a location associated with a value in the ordered stack of values.

23. A method as in claim 18, wherein the last extrema value comprises a last minimum value.

24. A method as in claim 18, wherein the last extrema value comprises a last minimum value and wherein placing the value in the ordered stack of values includes removing a value from the ordered stack of values in the event that the computed value is less than or equal to the value from the ordered stack of values.

25. A method as in claim 18, wherein the last extrema value comprises a last minimum value and wherein a boundary location is determined based on the lowest value in the ordered stack of values associated with a position within a segmentation window.

26. A method as in claim 18, wherein the last extrema value comprises a last maximum value.

27. A method as in claim 18, wherein the last extrema value comprises a last maximum value and wherein placing the value in the ordered stack of values includes removing a value from the ordered stack of values in the event that the computed value is greater than or equal to the value from the ordered stack of values.

28. A method as in claim 18, wherein the last extrema value comprises a last maximum value and wherein a boundary location is determined based on the highest value in the ordered stack of values associated with a position within a segmentation window.

29. A system for selecting a segment boundary 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 a segmentation window;

compute a plurality of values associated with candidate boundaries within the segmentation window;

select one of the candidate boundaries based at least in part on a comparison between two or more of the computed values; and

determine a boundary within the segmentation window.

30. A computer program product for selecting a segment boundary, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

determining a segmentation window;

computing a plurality of values associated with candidate boundaries within the segmentation window;

selecting one of the candidate boundaries based at least in part on a comparison between two or more of the computed values; and

determining a boundary within the segmentation window.