Cluster storage using subsegmenting

• US 20080256143A1
• Filed: 06/29/2007
• Published: 10/16/2008
• Est. Priority Date: 04/11/2007
• 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, Lee, Edward K., Reddy, Sazzala
• Granted Patent: US 8,005,861 B2
• Time in Patent Office: Days
• US Class Current: 707/204
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Cluster storage is disclosed. A data stream or a data block is received. The data stream or the data block is broken into segments. For each segment, a cluster node is selected, and a portion of the segment smaller than the segment is identified that is a duplicate of a portion of a segment already managed by the cluster node.

Claims

1. A method for cluster storage comprising:

receiving a data stream or a data block;

breaking the data stream or the data block into segments; and

for each segment;

selecting a cluster node; and

identifying a portion of the segment smaller than the segment that is a duplicate of a portion of a segment already managed by the cluster node.

2. A method as in claim 1, further comprising storing the segment using one or more of the following:

a representation of the portion of the segment and segment data that is not a duplicate of previously stored data.

4. A method as in claim 1, wherein managing a segment includes one or more of the following:

enabling finding duplicates for portions of the segment within other segments being managed and storing a deduplicated representation of the segment.

6. A method as in claim 1, wherein the cluster node manages a portion of the segments stored in the cluster.

7. A method as in claim 1, wherein identifying whether a portion of the segment smaller than the segment is a duplicate of a portion of a segment already managed by the cluster node includes breaking the segment into a plurality of subsegments and identifying a subsegment that has already been stored.

8. A method as in claim 1, wherein a subsegment is stored on more than one node so that subsegments can be read sequentially.

9. A method as in claim 1, wherein a subsegment reference is stored on more than one node so that subsegment references can be read sequentially.

10. A method as in claim 1, wherein breaking the data stream or the data block into segments is based at least in part on one or more of the following:

content of the data stream or the data block and file boundaries within the data stream or the data block.

12. A method as in claim 1, wherein breaking the data stream or the data block into segments is based at least in part on an anchoring function, wherein the anchoring function includes one or more of the following:

determining if the computed hash meets one or more predetermined criteria, using a value of a function calculated for a plurality of windows within a segmentation window, and establishing a boundary in an algorithmic manner in or around a sliding window of bytes.

15. A method as in claim 1, wherein breaking the data stream or the data block into segments comprises identifying a plurality of subsegments, wherein the plurality of subsegments are contiguous or overlapping, and grouping the plurality of subsegments into segments.

16. A method as in claim 15, wherein identifying the plurality of subsegments comprises identifying the plurality of subsegments within a window and selecting a boundary based at least in part on a hash value of a predetermined number of bytes of each of the plurality of subsegments.

17. A method as in claim 16, wherein the boundary is selected based on one or more of the following:

a maximum hash value of each of the plurality of subsegments and on a minimum hash value of each of the plurality of subsegments.

19. A method as in claim 15, wherein identifying the plurality of subsegments is based at least in part on the data stream or the data block content.

20. A method as in claim 15, wherein identifying the plurality of subsegments includes one or more of the following:

calculating a function which meets a predetermined condition to select a boundary, selecting a boundary using anchors, selecting a boundary based at least in part on a minimum value or a maximum value of a function within a window.

23. A method as in claim 1, wherein selecting the cluster node is based at least in part on one or more of the following:

a hash of at least a portion of a content of the segment a sketch of the segment, a content tag associated with the segment, at least a portion of a content of the segment and the cluster node'"'"'s remaining storage capacity.

28. A method as in claim 1, further comprising storing one or more tags associated with the segment.

29. A method as in claim 28, wherein the one or more tags include one or more fingerprints.

30. A method as in claim 1, wherein a plurality of tags associated with a plurality of segments are stored together on a cluster node.

31. A method as in claim 1, wherein a plurality of tags associated with a plurality of subsegments are stored together on a cluster node.

32. A method as in claim 1, wherein identifying a portion of the segment smaller than the segment that is a duplicate of a portion of a segment already managed by the cluster node includes identifying one or more previously stored similar segments and determining if an already stored portion of the one or more previously stored similar segments is a duplicate of the portion of the segment.

33. A method as in claim 32, wherein the one or more previously stored similar segments is identified using a tag of the segment.

34. A method as in claim 1, wherein the cluster node includes a summary data structure that is used in the process of assigning a segment to a cluster node.

35. A method as in claim 1, wherein selecting the cluster node is based at least in part on one or more of the following:

one or more segments that are already stored on the node, one or more similar segments already managed by the node, and one or more identical subsegments already managed by the node.

3. (Canceled)

5. (Canceled)

11. (Canceled)

13. (Canceled)

14. (Canceled)

18. (Canceled)

21. (Canceled)

22. (Canceled)

24. (Canceled)

25. (Canceled)

26. (Canceled)

27. (Canceled)

36. (Canceled)

37. (Canceled)

38. A system for cluster storage 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;

an interface for receiving a data stream or a data block;

a sepmenter for breaking the data stream or the data block into segments; and

for each segment;

a selector for selecting a cluster node; and

a processor for identifying a portion of the segment smaller than the segment that is a duplicate of a portion of a segment already managed by the cluster node.

39. A computer program product for cluster storage, the computer program product being embodied in a computer readable medium and comprising computer instructions for:

receiving a data stream or a data block;

breaking the data stream or the data block into segments; and

for each segment;

selecting a cluster node; and

identifying a portion of the segment smaller than the segment that is a duplicate of a portion of a segment already managed by the cluster node.