Landmark chunking of landmarkless regions

• US 8,117,343 B2
• Filed: 10/28/2008
• Issued: 02/14/2012
• Est. Priority Date: 10/28/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David, Czerkowicz, John M., Falkinder, David Malcolm
• Primary Examiner(s): Elchanti, Hussein A
• Application Number:
  US12/260,024
• Publication Number:
  US 20100114980A1
• Time in Patent Office: 1,204 Days
• Field of Search: 709/230, 709/246
• US Class Current: 709/246
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A computer-executed method for forming data chunks from a sequence of data values comprises determining whether processing of the sequence of data values has entered a landmark-free region. If processing has entered a landmark-free region, a data chunk is produced using a specialized landmark chunking technique that is specialized for landmark-free regions. Otherwise, the method comprises producing a data chunk using a standard-data landmark chunking technique.

Claims

1. A computer-executed method for forming data chunks from a sequence of data values comprising:

determining, by a computer, whether processing of the sequence of data values has entered a region that is landmark-free, wherein the landmark-free region is devoid of any landmarks that provide boundaries of the data chunks;

producing, by the computer, a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions in response to determining that the processing of the sequence of data values has entered a landmark-free region; and

producing, by the computer, a data chunk using a first standard-data landmark chunking technique in response to determining that the processing of the sequence of data values has not entered a landmark-free region.

2. The method according to claim 1 wherein determining whether the processing of the sequence of data values has entered a region that is landmark-free comprises:

checking chunk lengths of a number of data chunks produced using the first standard-data landmark chunking technique;

determining whether the chunk lengths of the number of data chunks produced using the first standard-data chunking technique are all equal to a predetermined maximum length; and

determining that the processing has entered into a landmark-free region in response to detecting that the number of data chunks produced using the first standard-data landmark chunking technique are maximum length chunks.

3. The method according to claim 1 wherein determining whether the processing of the sequence of data values has entered a region that is landmark-free comprises:

computing a hash function on a selected portion of the sequence of data values;

comparing the computed hash function to a value known to represent a landmark-free data chunk; and

determining that the processing of the sequence of data values has entered a region that is landmark-free if the computed hash function matches the value known to represent a landmark-free data chunk.

4. The method according to claim 1, wherein the first standard-data chunking technique identifies landmarks in the sequence of data values, and produces plural data chunks from the sequence of data values using the identified landmarks as boundaries of the plural data chunks.

5. The method according to claim 4, wherein the first standard-data chunking technique is used in a region of the sequence that includes landmarks.

6. A computer-executed method for forming data chunks from a sequence of data values comprising:

determining, by a computer, whether processing of the sequence of data values has entered a region that is landmark-free;

producing, by the computer, a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions if determined that the processing of the sequence of data values has entered a landmark-free region; and

producing, by the computer, a data chunk using a first standard-data landmark chunking technique,

wherein producing a data chunk using the specialized landmark chunking technique that is specialized for landmark-free regions comprises using a technique selected from a group consisting of;

a first technique comprising;

producing a selected number of consecutive chunks as maximum-length chunks without inspecting underlying data in the sequence of data values;

producing a first chunk following the maximum-length chunks using a second standard-data landmark chunking technique;

determining whether the first chunk has a length equal to a predetermined maximum length;

if the first chunk length is equal to the predetermined maximum length, looping to producing the selected number of consecutive chunks as maximum-length chunks without inspecting the underlying data in the sequence of data values;

a second technique comprising;

producing a selected number of consecutive chunks as maximum-length chunks without inspecting underlying data in the sequence of data values; and

a third technique comprising;

producing one chunk as a maximum-length chunk without inspecting the underlying data in the sequence of data values;

checking data of a predetermined maximum length immediately following the produced one chunk for characteristics of landmark-free regions;

if the checked data has characteristics of landmark-free regions, looping to producing one maximum-length chunk.

7. A computer-executed method for forming data chunks from a sequence of data values comprising:

determining, by a computer, whether processing of the sequence of data values has entered a region that is landmark-free;

producing, by the computer, a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions if determined that the processing of the sequence of data values has entered a landmark-free region; and

producing, by the computer, a data chunk using a first standard-data landmark chunking technique,

wherein producing a data chunk using the specialized landmark chunking technique that is specialized for landmark-free regions comprises;

computing fingerprint values for positions in the sequence of data values;

computing a first fingerprint value for a first window of bytes in the sequence of data values;

determining whether a second window of bytes is same as the first window of bytes; and

assigning the first fingerprint value to the second window of bytes without fingerprint computation on the bytes in the second window if the second window of bytes is the same as the first window of bytes, otherwise computing a second fingerprint value for the second window of bytes.

8. A data processing apparatus comprising:

a computer; and

a logic executable in the computer to;

form data chunks from a sequence of data values including;

determining whether processing of the sequence of data values has entered a landmark-free region, wherein the landmark-free region is devoid of any landmarks that provide boundaries of the data chunks,

in response to the logic determining that the processing has entered a landmark-free region, produce a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions, and

in response to the logic determining that the processing has not entered a landmark-free region, produce a data chunk using a first standard-data landmark chunking technique.

9. The data processing apparatus according to claim 8 further comprising:

an interface coupled to the computer and configured to receive the sequence of data values; and

a data store coupled to the computer.

10. The data processing apparatus according to claim 8 wherein the determining of whether the processing of the sequence of data values has entered a landmark-free region comprises:

checking chunk lengths of a number of data chunks produced using the first standard-data landmark chunking technique,

determining whether the chunk lengths of the number of data chunks produced using the first standard-data chunking technique are all equal to a predetermined maximum length, and

determining that the processing has entered into the landmark-free region in response to detecting that the number of the data chunks produced using the first standard-data landmark chunking technique are maximum length chunks.

11. The data processing apparatus according to claim 8 wherein the specialized landmark chunking technique produces a selected number of consecutive chunks as maximum-length chunks without inspecting underlying data in the sequence of data values,

produces a first chunk following the maximum-length chunks using a second standard-data landmark chunking technique,

determines whether the first chunk has a length equal to a predetermined maximum length,

if the first chunk length is equal to the predetermined maximum length the logic loops to produce the selected number of consecutive chunks as maximum-length chunks without inspecting the underlying data in the sequence of data values.

12. The data processing apparatus according to claim 8 wherein the specialized landmark chunking technique produces a selected number of consecutive chunks as maximum-length without inspecting underlying data in the sequence of data values.

13. The data processing apparatus according to claim 8 wherein the specialized landmark chunking technique produces one chunk as a maximum-length chunk without inspecting underlying data in the sequence of data values,

checks data of a predetermined maximum length immediately following the produced one chunk for characteristics of landmark-free regions,

if the checked data has characteristics of landmark-free regions, loops to produce one maximum-length chunk.

14. The data processing apparatus according to claim 8 wherein the determining of whether the processing of the sequence of data values has entered a landmark-free region comprises:

computing a hash function on a selected portion of the sequence of data values,

comparing the computed hash function to a value known to represent a landmark-free data chunk, and

determining that the processing has entered into a landmark-free region if the computed hash function matches the value known to represent the landmark-free data chunk.

15. The data processing apparatus according to claim 8, wherein the first standard-data chunking technique identifies landmarks in the sequence of data values, and produces plural data chunks from the sequence of data values using the identified landmarks as boundaries of the plural data chunks.

16. The data processing apparatus of claim 15, wherein the logic is executable to use the first standard-data chunking technique in a region of the sequence that includes landmarks.

17. A data processing apparatus comprising:

a computer; and

a logic executable in the computer to;

form data chunks from a sequence of data values including;

determining whether processing of the sequence of data values has entered a landmark-free region,

in response to the logic determining that the processing has entered a landmark-free region, produce a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions, and

in response to the logic determining that the processing has not entered a landmark-free region, produce a data chunk using a first standard-data landmark chunking technique,

wherein the specialized landmark chunking technique;

computes fingerprint values for positions in the sequence of data values including a first fingerprint value for a first window of bytes in the sequence of data values,

determines whether a second window of bytes is same as the first window of bytes, and

assigns the first fingerprint value to the second window of bytes without fingerprint computation on the bytes in the second window if the second window of bytes is the same as the first window of bytes, otherwise computing a second fingerprint value for the second window of bytes.

18. An article of manufacture comprising:

a non-transitory computer-usable medium storing a computer readable program code for forming data chunks from a sequence of data values, the computer readable program code executable by a computer to cause the computer to;

determine whether processing of the sequence of data values has entered a landmark-free region, wherein the landmark-free region is devoid of any landmarks that provide boundaries of the data chunks;

produce a data chunk using a specialized landmark chunking technique that is specialized for landmark-free regions in response to determining that the processing has entered the landmark-free region; and

produce a data chunk using a standard-data landmark chunking technique in response to determining that the processing of the sequence of data values has not entered a landmark-free region.

19. The article of manufacture according to claim 18, wherein the standard-data chunking technique identifies landmarks in the sequence of data values, and produces plural data chunks from the sequence of data values using the identified landmarks as boundaries of the plural data chunks.