SYSTEM AND METHOD FOR SEGMENTING A DATA STREAM

• US 20100205163A1
• Filed: 02/10/2009
• Published: 08/12/2010
• Est. Priority Date: 02/10/2009
• 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, Eshghi, Kave
• Granted Patent: US 8,375,182 B2
• Time in Patent Office: Days
• US Class Current: 707/698
• 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 one or more data chunks into a segment with at least one boundary of the segment defined based on an evaluation of content hash values of data chunks;

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

storing a pointer to a stored data chunk of an existing segment 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.

2. The method of claim 1, further comprising storing a data chunk of the segment on the backup mass storage device if a content hash value of the data chunk of the segment does not match content hash values of data chunks of existing 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 segment to data content of stored data chunks.

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

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

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

selecting a desired average segment size; and

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

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

selecting a predetermined result, a desired minimum segment size, and a desired maximum segment size; and

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

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

8. The method of claim 7, further comprising selecting an average segment size “

K,” and

;

defining the minimum segment size as between about 0.2*K and about 0.3*K; and

defining the maximum segment size as between about 4*K and about 10*K.

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

selecting;

a first deterministic function, a first predetermined result, a second deterministic function a second predetermined result, a desired minimum segment size, and a desired maximum segment size; and

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

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

10. 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 segment while defining at least one boundary of the 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 segment to content hash values of data chunks 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 stored on the 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.

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

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

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

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

Identifying a desired average segment size; and

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

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

identifying a predetermined result, a desired minimum segment size, and a desired maximum segment size; and

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

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

15. The system of claim 14, 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.

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

identifying;

a first predetermined result, a second predetermined result, a desired minimum segment size, and a desired maximum segment size; and

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

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

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

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