Back to results
US 8,751,462 B2Granted
Delta compression after identity deduplication
AssigneeEMC Corporation
InventorsMark Huang, Edward K. Lee, Kai Li, Philip Shilane, Grant Wallace, Ming Benjamin Zhu
Life of this patent
Estimating the term…
Abstract
Delta compression after identity deduplication is disclosed. A first data segment is determined to be identical to a first previous data segment. A second data segment, not determined to be identical to a second previous data segment, is then determined to be similar to a third previous data segment.
Claims43
A system for processing data, comprising:
- a deduplicating system, wherein the deduplicating system comprises a processor and a storage unit, wherein the deduplicating system is configured for determining, using the processor, whether a first data segment is identical to a first previously stored data segment in the storage unit, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in the storage unit;
- and
- a delta compression system is configured for determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first data segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function and the sketch function comprises one or more functions that returns a same value for similar data segments;
- wherein in the event that the first data segment is determined to be similar to the second previously stored data segment, the delta compression system is further configured for computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment;
- and
- wherein in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, the delta compression system is further configured for storing the first data segment in the storage unit.
3 more elements
A method for processing data, comprising:
- determining, using a processor, whether a first data segment is identical to a first previously stored data segment, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in a storage unit;
- and
- determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first data segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function, wherein the sketch function comprises one or more functions that returns a same value for similar data segments;
- in the event that the first data segment is determined to be similar to the second previously stored data segment, computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment;
- and
- in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, storing the first data segment in the storage unit.
3 more elements
A computer program product for processing data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
- determining, using a processor, whether a first data segment is identical to a first previously stored data segment, wherein in the event that the first data segment is determined to be identical to the first previously stored data segment, a reference to the first data segment is stored in a storage unit;
- and
- determining, only in the event that the first data segment is determined not to be identical to the first previously stored data segment, whether the first segment is similar to a second previously stored data segment, wherein the first data segment is determined to be similar to the second previously stored data segment using a sketch function and the sketch function comprises one or more functions that returns a same value for similar data segments;
- in the event that the first data segment is determined to be similar to the second previously stored data segment, computing an encoding of the first data segment, wherein the encoding comprises determining one or more differences between the first data segment and the second previously stored data segment, and storing, in the storage unit, the first data segment using a sequence comprising the one or more differences, one or more first sequence locations corresponding to each of the one or more differences, a reference to the second previously stored data segment, and one or more second sequence references, wherein the one or more second sequence references corresponding to a sequence of data from within the second previously stored segment identifying the subset of the second previously stored segment;
- and
- in the event that the first data segment is not determined to be similar to the second previously stored data segment and that the first data segment is determined not to be identical to the first stored data segment, storing the first data segment in the storage unit.
3 more elements
Dependencies are inferred from the claim text.