Deduplicating data at sub-block granularity
AssigneeEMC IP Holding Company LLC
InventorsPhilippe Armangau, Sorin Faibish, Istvan Gonczi, Ivan Bassov, Vamsi K. Vankamamidi
Life of this patent
Estimating the term…
Abstract
A technique for performing data deduplication operates at sub-block granularity by searching a deduplication database for a match between a candidate sub-block of a candidate block and a target sub-block of a previously-stored target block. When a match is found, the technique identifies a duplicate range shared between the candidate block and the target block and effects persistent storage of the duplicate range by configuring mapping metadata of the candidate block so that it points to the duplicate range in the target block.
Claims21
A method of performing data deduplication, comprising:
- providing a deduplication database in a data storage system, the deduplication database configured to store multiple entries that associate digest values computed from respective sub-blocks of data blocks with references to locations in the data storage system where data blocks containing the respective sub-blocks can be found;
- implementing a policy for adding entries to the deduplication database, the policy specifying creation of new entries for first sub-blocks and last sub-blocks of data blocks but not for intermediate sub-blocks of those data blocks;
- and
- processing a new data block for deduplication by (i) identifying multiple sub-blocks of the new data block, (ii) computing respective new digest values from the sub-blocks of the new data block, (iii) matching one of the new digest values to an entry in the deduplication database, and (iv) storing the new data block at least in part by reference to a target data block whose location is referenced by the matching entry.
A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:
- provide a deduplication database, the deduplication database configured to store multiple entries that associate digest values computed from respective sub-blocks of data blocks with references to locations in the data storage system where data blocks containing the respective sub-blocks can be found;
- implement a policy for adding entries to the deduplication database, the policy specifying creation of new entries for first sub-blocks and last sub-blocks of data blocks but not for intermediate sub-blocks of those data blocks;
- and
- process a new data block for deduplication by (i) identifying multiple sub-blocks of the new data block, (ii) computing respective new digest values from the sub-blocks of the new data block, (iii) matching one of the new digest values to an entry in the deduplication database, and (iv) storing the new data block at least in part by reference to a target data block whose location is referenced by the matching entry.
A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a data storage system, cause the control circuitry to perform a method of performing data deduplication, the method comprising:
- providing a deduplication database, the deduplication database configured to store multiple entries that associate digest values computed from respective sub-blocks of data blocks with references to locations in the data storage system where data blocks containing the respective sub-blocks can be found;
- implementing a policy for adding entries to the deduplication database, the policy specifying creation of new entries for first sub-blocks and last sub-blocks of data blocks but not for intermediate sub-blocks of those data blocks;
- and
- processing a new data block for deduplication by (i) identifying multiple sub-blocks of the new data block, (ii) computing respective new digest values from the sub-blocks of the new data block, (iii) matching one of the new digest values to an entry in the deduplication database, and (iv) storing the new data block at least in part by reference to a target data block whose location is referenced by the matching entry.
Dependencies are inferred from the claim text.