Sub-block deduplication using sector hashing
AssigneeEMC IP Holding Company LLC
InventorsUri Shabi, Vladimir Shveidel, Maor Rahamim, Ronen Gazit
Life of this patent
Estimating the term…
Abstract
A method of performing deduplication is provided. The method includes (a) selecting, by applying a deterministic selection criterion, a sub-block of a block of data that contains multiple sub-blocks; (b) performing a lookup, into a deduplication table, of a digest generated by hashing the selected sub-block, the lookup matching an entry indexed by the digest in the deduplication table, the entry identifying a previously processed block; and (c) effecting storage of the block, including pointing to the previously processed block. An apparatus, system, and computer program product for performing a similar method are also provided.
Claims18
A method of performing deduplication, the method comprising:
- selecting, by applying a deterministic selection criterion, a sub-block of a block of data that contains multiple sub-blocks;
- performing a lookup, into a deduplication table, of a digest generated by hashing the selected sub-block, the lookup matching an entry indexed by the digest in the deduplication table, the entry identifying a previously processed block;
- effecting storage of the block, including pointing to the previously processed block;
- and
- for another block of data that also contains multiple sub-blocks:
- selecting, by applying the deterministic selection criterion, another sub-block of the other block of data;
- performing another lookup, into the deduplication table, of another digest generated by hashing the other selected sub-block;
- failing to find any entry indexed by the other digest in the deduplication table, and, in response, looking up, in the deduplication table, a block digest generated by hashing the other block in its entirety;
- and
- failing to find any entry indexed by the block digest in the deduplication table, and, in response:
- writing contents of the other block to persistent storage;
- and
- inserting another entry, indexed by the other digest, into the deduplication table, the other entry identifying the other block as having been processed.
An apparatus comprising processing circuitry coupled to memory configured to:
- select, by applying a deterministic selection criterion, a sub-block of a block of data that contains multiple sub-blocks, wherein selecting includes:
- calculating an entropy of each of the multiple sub-blocks of the block;
- and
- selecting a sub-block from the multiple sub-blocks having a highest calculated entropy as the selected sub-block;
- perform a lookup, into a deduplication table, of a digest generated by hashing the selected sub-block, the lookup matching an entry indexed by the digest in the deduplication table, the entry identifying a previously processed block;
- and
- effect storage of the block, including pointing to the previously processed block;
- and
- for another block of data that also contains multiple sub-blocks:
- selecting, by applying the deterministic selection criterion, another sub-block of the other block of data;
- performing another lookup, into the deduplication table, of another digest generated by hashing the other selected sub-block;
- failing to find any entry indexed by the other digest in the deduplication table, and, in response, looking up, in the deduplication table, a block digest generated by hashing the other block in its entirety;
- and
- failing to find any entry indexed by the block digest in the deduplication table, and, in response:
- writing contents of the other block to persistent storage;
- and
- inserting another entry, indexed by the other digest, into the deduplication table, the other entry identifying the other block as having been processed.
A computer program product comprising a non-transitory computer-readable storage medium storing a set of instructions, which, when executed by a computing device cause the computing device to perform deduplication by:
- selecting, by applying a deterministic selection criterion, a sub-block of a block of data that contains multiple sub-blocks;
- performing a lookup, into a deduplication table, of a digest generated by hashing the selected sub-block, the lookup matching an entry indexed by the digest in the deduplication table, the entry identifying a previously processed block;
- and
- effecting storage of the block, including pointing to the previously processed block;
- and
- for another block of data that also contains multiple sub-blocks:
- selecting, by applying the deterministic selection criterion, another sub-block of the other block of data;
- performing another lookup, into the deduplication table, of another digest generated by hashing the other selected sub-block;
- failing to find any entry indexed by the other digest in the deduplication table, and, in response, looking up, in the deduplication table, a block digest generated by hashing the other block in its entirety;
- and
- failing to find any entry indexed by the block digest in the deduplication table, and, in response:
- writing contents of the other block to persistent storage;
- and
- inserting another entry, indexed by the other digest, into the deduplication table, the other entry identifying the other block as having been processed.
Dependencies are inferred from the claim text.