Locality-based stream segmentation for data deduplication
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.
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.