System and method for segmenting a data stream

• US 8,375,182 B2
• Filed: 02/10/2009
• Issued: 02/12/2013
• Est. Priority Date: 02/10/2009
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Eshghi, Kave, Lillibridge, Mark David
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US12/368,784
• Publication Number:
  US 20100205163A1
• Time in Patent Office: 1,463 Days
• Field of Search: 711/216, 711/E12.018
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup

Abstract

A method of limiting redundant storage of data comprises receiving a data stream and partitioning the data stream into a series of data chunks. At least one content hash value for a set of data chunks is generated based on data content of the set of data chunks. One or more data chunks are grouped into a segment with at least one boundary of the segment defined based on an evaluation of content hash values of data chunks. Content hash values of data chunks of the segment are compared to content hash values of data chunks of segments stored on a backup mass storage device. A pointer to a stored data chunk of an existing segment is stored on the backup mass storage device if a content hash value of a data chunk of the segment matches the content hash value of the stored data chunk.

Claims

1. A method of limiting redundant storage of data for a backup mass storage device, comprising:

receiving a data stream;

partitioning the data stream into a series of data chunks;

generating at least one content hash value for a set of data chunks based on data content of the set of data chunks;

grouping a plurality of data chunks into a particular segment with at least one boundary of the particular segment defined based on an evaluation of content hash values of data chunks;

comparing content hash values of data chunks of the particular segment to content hash values of data chunks of a plurality of segments stored on a backup mass storage device; and

storing a pointer to a stored data chunk of an existing segment of the plurality of segments stored on the backup mass storage device if a content hash value of a data chunk of the particular segment matches the content hash value of the stored data chunk.

2. The method of claim 1, further comprising storing a data chunk of the particular segment on the backup mass storage device if a content hash value of the data chunk of the particular segment does not match content hash values of data chunks of the plurality of segments stored on the mass backup storage device.

3. The method of claim 1, wherein partitioning the data stream into a series of data chunks comprises partitioning the data stream into a series of variable-length data chunks.

4. The method of claim 1, wherein a hash function utilized to define one or more segment boundaries corresponds to a hash function utilized to compare data content of data chunks of the particular segment to data content of stored data chunks.

5. The method of claim 1, wherein defining at least one boundary of the particular segment further comprises:

selecting a desired average segment size; and

defining a boundary of the particular segment at a chunk of data where applying a deterministic function to a content hash of the chunk of data and the desired average segment size returns a predetermined result.

6. The method of claim 1, wherein defining at least one boundary of the particular segment further comprises:

selecting a desired average segment size; and

defining a boundary of the particular segment at a chunk of data that is nearest to an established boundary of the particular segment measured in a predetermined direction, wherein a predetermined result is produced when a deterministic function is applied to a content hash of the chunk of data and the desired average segment size.

7. A system for limiting redundant storage of data to a backup mass storage device, comprising:

a mass storage device;

a backup mass storage device;

a backup module, operable to receive a data stream from the mass storage device and to transmit a modified data stream to the backup mass storage device;

a hash generating module, operable to generate at least one content hash value for a set of data chunks based on data content of the set of data chunks;

a segmentation module, operable to group a plurality of data chunks into a particular segment while defining at least one boundary of the particular segment based on an evaluation of content hash values of data chunks; and

a comparison module, operable to compare content hash values of data chunks of the particular segment to content hash values of data chunks of a plurality of segments stored on the backup mass storage device;

the backup module operable to store a pointer to a stored data chunk of an existing segment of the plurality of segments stored on the mass storage device if a content hash value of a data chunk of the particular segment matches the content hash value of the stored data chunk.

8. The system of claim 7, wherein the backup module is operable to store a data chunk of the particular segment on the backup mass storage device if the content hash value of the data chunk of the particular segment does not match content hash values of data chunks of the plurality of segments stored on the mass storage device.

9. The system of claim 7, wherein the segmentation module is operable to define at least one boundary of the particular segment by:

identifying a desired average segment size; and

defining a boundary of the particular segment at a chunk of data where applying a deterministic function to the content hash of the chunk of data and the desired average segment size returns a predetermined result.

10. The system of claim 7, wherein the segmentation module is operable to define at least one boundary of the particular segment by:

identifying a desired average segment size; and

defining a boundary of the particular segment at a chunk of data that is nearest to an established boundary of the particular segment measured in a predetermined direction, wherein a predetermined result is produced when a deterministic function is applied to a content hash of the chunk of data and the desired average segment size.

11. The system of claim 7, wherein the segmentation module is operable to define at least one boundary of the particular segment by:

identifying a desired minimum segment size and a desired maximum segment size; and

defining a boundary of the particular segment at a chunk of data where;

applying a deterministic function to the content hash of the chunk of data returns a predetermined result, a size of the particular segment is not less than the minimum segment size, and the size of the particular segment is not greater than the maximum segment size.

12. The system of claim 11, wherein an average segment size “

K”

is defined, the minimum segment size is between about 0.2*K and about 0.3*K, and the maximum segment size is between about 4*K and about 10*K.

13. The system of claim 7, wherein the segmentation module is operable to define at least one boundary of the particular segment by:

identifying;

a divisor, a desired minimum segment size, and a desired maximum segment size; and

defining a boundary of the particular segment at a chunk of data where;

dividing a content hash of the chunk of data by the divisor returns an integer, a size of the particular segment is not less than the minimum segment size, and the size of the particular segment is not greater than the maximum segment size.

14. The system of claim 7, wherein a hash function utilized to define segment boundaries corresponds to a hash function utilized to compare data content of data chunks of the particular segment to data content of stored data chunks.

15. The system of claim 7, wherein the segmentation module is operable to partitioning the data stream into a series of variable-length data chunks.