Cluster storage using delta compression

• US 20080294660A1
• Filed: 04/09/2008
• Published: 11/27/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: Li, Kai, Maheshwari, Umesh, Patterson, R. Hugo, Zhu, Ming Benjamin, Lee, Edward K., Reddy, Sazzala Venkata
• Granted Patent: US 7,962,520 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 in the event that a similar segment to the segment is identified that is already managed by the selected cluster node, a reference to the similar segment and a delta between the similar segment and the segment is caused to be stored on the selected 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

in the event that a similar segment to a segment is identified that is already managed by the cluster node, causing a reference to the similar segment and a delta between the similar segment and the segment to be stored.

2. A method as in claim 1, further comprising in the event that a similar segment to the segment is not identified that is already managed by the cluster node, causing the segment to be stored as a new segment of the cluster node.

3. A method as in claim 2, wherein the new segment is caused to be stored as a new base segment and a new delta.

4. A method as in claim 1, wherein managing a segment includes enabling finding similar segments within the segments being managed.

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

6. A method as in claim 1, wherein identifying whether a segment is similar to a segment already managed by the cluster node includes using a tag.

7. A method as in claim 6 wherein a tag comprises a sketch.

8. A method as in claim 6, wherein a tag comprises summary feature set.

9. A method as in claim 6, wherein a tag comprises a hash of some of the segment.

10. A method as in claim 6, wherein a tag comprises a fingerprint of some of the segment.

11. A method as in claim 1, wherein breaking the data stream or the data block into segments is based at least in part on content of 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 file boundaries within the data stream or the data block.

13. 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 determining if the computed hash meets one or more predetermined criteria.

14. 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 uses a value of a function calculated for a plurality of windows within a segmentation window.

15. A method as in claim 14, where the anchoring function uses a minimum value for the plurality of windows.

16. A method as in claim 14, where the anchoring function uses a maximum value for the plurality of windows.

17. A method as in claim 14, where the anchoring function uses a value with the most 1'"'"'s for the plurality of windows.

18. 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 establishing a boundary in an algorithmic manner in or around a sliding window of bytes.

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

20. A method as in claim 1, wherein selecting the cluster node is based at least in part on a hash of at least a portion of a content of the segment.

21. A method as in claim 1, wherein selecting the cluster node is based at least in part on a sketch of the segment.

22. A method as in claim 1, wherein selecting the cluster node is based at least in part on a content tag associated with the segment.

23. A method as in claim 1, wherein selecting the cluster node is based at least in part on at least a portion of a content of the segment.

24. A method as in claim 1, wherein selecting the cluster node does not depend on a content of any segment previously stored on any cluster node.

25. A method as in claim 1, wherein selecting the cluster node is based at least in part on the cluster node'"'"'s remaining storage capacity.

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

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

28. 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.

29. A method as in claim 1, wherein selecting the cluster node is based at least in part on one or more segments that are already stored on the node.

30. A method as in claim 1, wherein selecting the cluster node is based at least in part on one or more similar segments already managed by the node.

31. A method as in claim 1, wherein the segment is associated with the data stream and wherein the segment is caused to be stored on the selected cluster node such that the segment can be retrieved efficiently with other segments associated with the data stream that are stored on the selected cluster node.

32. A method as in claim 31, wherein the data stream associated with the segment comprises one or more of the following:

a file, a plurality of files that are related to each other, a directory of files, or a plurality of segments that are related to each other.

33. A method as in claim 31, wherein an indication identifying the data stream associated with the segment is provided to the selected cluster node storing the segment.

34. A method as in claim 31, wherein segments associated with the data stream that are caused to be stored on the selected cluster node are caused to be stored by causing one or more delta and base segment pairs to be stored and wherein the segments associated with the data stream that are caused to be stored on the selected cluster node such that the segments can be retrieved together efficiently.

35. A method as in claim 1, wherein the delta is caused to be stored for efficient retrieval with the similar segment referred to by the reference.

36. A method as in claim 1, wherein the reference and the delta are caused to be stored by the selected cluster node.

37. A method as in claim 1, wherein the reference and the delta are caused to be stored by a replica system.

39. A system as in claim 37, wherein the processor comprises a client processor.

40. A system as in claim 37, wherein the reference and the delta are caused to be stored by the selected cluster node.

41. A system as in claim 37, wherein the reference and the delta are caused to be stored by a replica system.

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;

receive a data stream or a data block;

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

for each segment;

select a cluster node; and

in the event that a similar segment to a segment is identified that is already managed by the cluster node, cause a reference to the similar segment and a delta between the similar segment and the segment to be stored.

42. 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

in the event that a similar segment to a segment is identified that is already managed by the cluster node, causing a reference to the similar segment and a delta between the similar segment and the segment to be stored.