Cluster storage using delta compression

• US 7,962,520 B2
• Filed: 04/09/2008
• Issued: 06/14/2011
• Est. Priority Date: 04/11/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Zhu, Ming Benjamin, Reddy, Sazzala Venkata, Li, Kai, Maheshwari, Umesh, Patterson, R. Hugo, Lee, Edward K.
• Primary Examiner(s): Woo; Isaac M
• Application Number:
  US12/082,244
• Publication Number:
  US 20080294660A1
• Time in Patent Office: 1,161 Days
• Field of Search: 707600-831
• US Class Current: 707/791
• 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;

identifying a similar segment to the segment, the similar segment being already managed by the cluster node; and

in the event the similar segment is identified, causing a reference to the similar segment and a delta between the similar segment and the segment to be stored instead of the segment.

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

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

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

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

6. The method as in claim 1, wherein identifying the similar segment includes using a tag.

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

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

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

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

11. The 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. The 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. The 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. The 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. The method as in claim 14, where the anchoring function uses a minimum value for the plurality of windows.

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

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

18. The 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. The 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. The 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. The method as in claim 1, wherein selecting the cluster node is based at least in part on a sketch of the segment.

22. The 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. The 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. The 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. The 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. The method as in claim 1, further comprising storing one or more tags associated with the segment.

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

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

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

30. The 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. The 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, wherein the other segments are stored on the selected cluster node.

32. The 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 related files, a directory of files, or a plurality of related segments.

33. The 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. The method as in claim 31, wherein segments associated with the data stream are caused to be stored on the selected cluster node by causing one or more delta and base segment pairs to be stored such that the segments can be retrieved together efficiently.

35. The 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. The method as in claim 1, wherein the reference and the delta are caused to be stored by the selected cluster node.

37. The method as in claim 1, 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;

identify a similar segment to the segment, the similar segment being already managed by the cluster node; and

in the event the similar segment is identified, cause a reference to the similar segment and a delta between the similar segment and the segment to be stored instead of the segment.

39. The system as in claim 38, wherein the processor comprises a client processor.

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

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

42. A computer program product for cluster storage, the computer program product being embodied in a computer readable storage 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;

identifying a similar segment to the segment, the similar segment being already managed by the cluster node; and

in the event the similar segment is identified, causing a reference to the similar segment and a delta between the similar segment and the segment to be stored instead of the segment.