Cluster storage using subsegmenting for efficient storage
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.
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, wherein breaking the data stream or the data block into segments is based at least in part on a value of a function calculated for a plurality of windows of bytes within the data stream or the data block; and
for each segment from the data stream or the data block:
selecting a cluster node, wherein the cluster node comprises an index that stores an indication of a set of segments stored on and managed by the cluster node, and wherein a cluster comprises a plurality of nodes, wherein each node comprises a data storage system that stores data by storing segments that are deduplicated; and
determining whether a portion of the segment from the data stream or the data block smaller than the segment is a duplicate of a portion of a segment already managed by the cluster node;
in the event that the portion of the segment from the data stream or the data block smaller than the segment is a duplicate of the portion of the segment already managed by the cluster node, storing a reference to the portion of the segment already managed by the cluster node that is used later to reconstruct the segment; and
in the event that the portion of the segment from the data stream or the data block smaller than the segment is not a duplicate of the portion of the segment already managed by the cluster node, newly storing the portion of the segment and a reference to the newly stored portion of the segment that is used later to reconstruct the segment.
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.
3. 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.
4. A method as in claim 1 , wherein the cluster node manages a portion of the segments stored in the cluster.
5. 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.
6. A method as in claim 1 , wherein a subsegment is stored on more than one node so that subsegments can be read sequentially.
7. 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.
8. 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.
9. 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.
10. 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.
11. A method as in claim 10 , 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.
12. A method as in claim 11 , 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.
13. A method as in claim 10 , wherein identifying the plurality of subsegments is based at least in part on the data stream or the data block content.
14. A method as in claim 10 , 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.
15. 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.
16. A method as in claim 1 , further comprising storing one or more tags associated with the segment.
17. A method as in claim 15 , wherein the one or more tags include one or more fingerprints.
18. A method as in claim 1 , wherein a plurality of tags associated with a plurality of segments are stored together on a cluster node.
19. A method as in claim 1 , wherein a plurality of tags associated with a plurality of subsegments are stored together on a cluster node.
20. 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.
21. A method as in claim 20 , wherein the one or more previously stored similar segments is identified using a tag of the segment.
22. 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.
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: 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.
24. A system for cluster storage comprising:
a processor configured to:
receive a data stream or a data block;
break the data stream or the data block into segments, wherein breaking the data stream or the data block into segments is based at least in part on a value of a function calculated for a plurality of windows of bytes within the data stream or the data block; and
for each segment from the data stream or the data block:
select a cluster node, wherein the cluster node comprises an index that stores an indication of a set of segments stored on and managed by the cluster node, and wherein a cluster comprises a plurality of nodes, wherein each node comprises a data storage system that stores data by storing segments that are deduplicated; and
determining whether a portion of the segment from the data stream or the data block smaller than the segment is a duplicate of a portion of a segment already managed by the cluster node;
in the event that the portion of the segment from the data stream or the data block smaller than the segment is a duplicate of the portion of the segment already managed by the cluster node, storing a reference to the portion of the segment already managed by the cluster node that is used later to reconstruct the segment; and
in the event that the portion of the segment from the data stream or the data block smaller than the segment is not a duplicate of the portion of the segment already managed by the cluster node, newly storing the portion of the segment and a reference to the newly stored portion of the segment that is used later to reconstruct the segment; and
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions.
25. 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, wherein breaking the data stream or the data block into segments is based at least in part on a value of a function calculated for a plurality of windows of bytes within the data stream or the data block; and
for each segment from the data stream or the data block:
selecting a cluster node, wherein the cluster node comprises an index that stores an indication of a set of segments stored on and managed by the cluster node, and wherein a cluster comprises a plurality of nodes, wherein each node comprises a data storage system that stores data by storing segments that are deduplicated; and
determining whether a portion of the segment from the data stream or the data block smaller than the segment is a duplicate of a portion of a segment already managed by the cluster node;
in the event that the portion of the segment from the data stream or the data block smaller than the segment is a duplicate of the portion of the segment already managed by the cluster node, storing a reference to the portion of the segment already managed by the cluster node that is used later to reconstruct the segment; and
in the event that the portion of the segment from the data stream or the data block smaller than the segment is not a duplicate of the portion of the segment already managed by the cluster node, newly storing the portion of the segment and a reference to the newly stored portion of the segment that is used later to reconstruct the segment.
26. A system as in claim 24 , wherein the processor is further configured to store 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.
27. A system as in claim 24 , 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.
28. A system as in claim 24 , wherein the cluster node manages a portion of the segments stored in the cluster.
29. A system as in claim 24 , 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.
30. A system as in claim 24 , wherein a subsegment is stored on more than one node so that subsegments can be read sequentially.
31. A system as in claim 24 , wherein a subsegment reference is stored on more than one node so that subsegment references can be read sequentially.
32. A system as in claim 24 , 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.
33. A system as in claim 24 , 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.
34. A system as in claim 24 , 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.
35. A system as in claim 34 , 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.
36. A system as in claim 34 , 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.
37. A system as in claim 34 , wherein identifying the plurality of subsegments is based at least in part on the data stream or the data block content.
38. A system as in claim 34 , 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.
39. A system as in claim 24 , 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.
40. A system as in claim 24 , further comprising storing one or more tags associated with the segment.
41. A system as in claim 40 , wherein the one or more tags include one or more fingerprints.
42. A system as in claim 24 , wherein a plurality of tags associated with a plurality of segments are stored together on a cluster node.
43. A system as in claim 24 , wherein a plurality of tags associated with a plurality of subsegments are stored together on a cluster node.
44. A system as in claim 24 , 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.
45. A system as in claim 44 , wherein the one or more previously stored similar segments is identified using a tag of the segment.
46. A system as in claim 24 , wherein the cluster node includes a summary data structure that is used in the process of assigning a segment to a cluster node.
47. A system as in claim 24 , 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.