Back to results
US 8,145,863 B2Granted
Efficient data storage using two level delta resemblance
AssigneeEMC Corporation
InventorMing Benjamin Zhu
Life of this patent
Estimating the term…
Abstract
Storage using resemblance of data segments is disclosed. It is determined that a new segment resembles a second prior stored segment wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment. A second delta between the new segment and the prior stored segment is determined. A representation of the new segment based at least in part on the second delta is stored.
Claims21
A system for storage using resemblance of data segments comprising:
- a processor configure to:
- break up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;
- determine that a new segment resembles a second prior stored segment wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, wherein resemblance is based at least in part on a summary feature set, wherein the summary feature set is determined by (a) selecting m subsegments of a first segment;
- (b) selecting n different functions, and wherein n is greater than 1;
- and (c) for function i, wherein i is a value from 1 to n, computing m values fi(subsegmentj) wherein j is a value from 1 to m;
- and (d) selecting a subset of values from the fi(subsegmentj) values, wherein the fi(subsegmentj) values encompass all of the values as a result of applying the n different functions to the m subsegments and
- determine a second delta between the new segment and the second prior stored segment;
- and
- store a representation of the new segment based at least in part on the second delta;
- and
- a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions.
8 more elements
A method for storage using resemblance of data segments, comprising:
- breaking up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;
- determining that a new segment resembles a second prior stored segment wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, wherein resemblance is based at least in part on a summary feature set, wherein the summary feature set is determined by (a) selecting m subsegments of a first segment;
- (b) selecting n different functions, and wherein n is greater than 1;
- and (c) for function i, wherein i is a value from 1 to n, computing m values fi(subsegmentj) wherein j is a value from 1 to m;
- and (d) selecting a subset of values from the fi(subsegmentj) values, wherein the fi(subsegmentj) values encompass all of the values as a result of applying the n different functions to the m subsegments;
- and
- determining a second delta between the new segment and the second prior stored segment;
- and
- storing a representation of the new segment based at least in part on the second delta.
6 more elements
A computer program product for storage using resemblance of data segments, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
- breaking up a new input data stream into a plurality of data segments, wherein a new segment comprises one of the plurality of data segments, and wherein the breaking up of the new input data stream is based at least in part on a hash of content of the data stream;
- determining that a new segment resembles a second prior stored segment wherein the second prior stored segment is represented as a first stored delta and a first prior stored segment, wherein resemblance is based at least in part on a summary feature set, wherein the summary feature set is determined by (a) selecting m subsegments of a first segment;
- (b) selecting n different functions, and wherein n is greater than 1;
- and (c) for function i, wherein i is a value from 1 to n, computing m values fi(subsegmentj) wherein j is a value from 1 to m;
- and (d) selecting a subset of values from the fi(subsegmentj) values, wherein the fi(subsegmentj) values encompass all of the values from applying the n different functions to the m subsegments;
- and
- determining a second delta between the new segment and the second prior stored segment;
- and
- storing a representation of the new segment based at least in part on the second delta.
6 more elements
Dependencies are inferred from the claim text.