Deduplicating unaligned data
A technique for performing deduplication identifies representative sub-blocks within candidate blocks and performs sub-block matching to entries in a digest database. When a representative sub-block is matched to a differently-aligned target sub-block that belongs to a target block, the technique effectuates storage of the candidate block using the target block and a block adjacent to the target block.
1. A method of performing data deduplication, the method comprising:
selecting a representative sub-block of a candidate block, the representative sub-block occupying a first position within the candidate block;
matching the representative sub-block to an entry in a digest database, the matching entry identifying a target block that contains the representative sub-block in a second position, and
effectuating storage of the candidate block by referencing the target block and an adjacent block adjacent to the target block,
wherein selecting the representative sub-block of the candidate block includes executing a deterministic function on multiple sub-blocks of the candidate block, and providing the representative sub-block as a sub-block of the multiple sub-blocks for which the deterministic function generates an extremum result.
2. The method of claim 1 , wherein the deterministic function is an entropy function, and wherein the representative sub-block is a highest-entropy sub-block of the multiple sub-blocks.
3. The method of claim 1 , wherein the digest database associates the matching entry with a list of full blocks that contain the representative sub-block.
4. The method of claim 3 , wherein the list of full blocks includes descriptive data about the full blocks, and wherein the method further comprises selecting one of the full blocks based at least in part on the descriptive data for that full block.
5. The method of claim 4 , wherein the descriptive data for one of the full blocks indicates a storage tier on which that full block is placed, and wherein selecting one of the full blocks is based at least in part on the storage tier indicated for that full block.
6. The method of claim 4 , wherein the descriptive data for one of the full blocks includes a reference count that indicates a number of times that the full block has been a target of deduplication, and wherein selecting one of the full blocks is based at least in part on the reference count indicated for that full block.
7. The method of claim 4 , wherein the descriptive data for one of the multiple full blocks includes a sequential-block indicator that indicates whether the full block is part of a sequence of blocks, and wherein selecting one of the full blocks is based at least in part on the sequential block indicator for that full block.
8. The method of claim 1 , wherein matching the representative sub-block to the entry in the digest database includes generating a sub-block hash of the representative sub-block and matching the sub-block hash to a digest in the digest database associated with the matching entry.
9. The method of claim 3 , wherein generating the sub-block hash includes performing at least one of (i) a cryptographic hash, (ii) a semi-cryptographic hash, and (iii) a similarity hash on the representative sub-block.
10. The method of claim 3 , further comprising:
comparing the first position to the second position to determine whether the adjacent block is a preceding block or a following block; and
accessing, based on the comparing, the adjacent block as one of the preceding block and the following block.
11. The method of claim 3 , further comprising:
comparing data of a set of sub-blocks of the adjacent block to a corresponding set of sub-blocks of the candidate block; and
in response to the set of sub-blocks of the adjacent block matching the corresponding set of sub-blocks of the candidate block, (i) comparing a set of additional sub-blocks of the adjacent block to a set of sub-blocks of an adjacent candidate block adjacent to the candidate block and (ii) in response to one or more of the set of additional sub-blocks of the adjacent block matching one or more of the set of sub-blocks of the adjacent candidate block, performing a deduplication operation on the adjacent candidate block.
12. A computerized apparatus, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:
select a representative sub-block of a candidate block, the representative sub-block occupying a first position within the candidate block;
match the representative sub-block to an entry in a digest database, the matching entry identifying a target block that contains the representative sub-block in a second position; and
effectuate storage of the candidate block by referencing the target block and an adjacent block adjacent to the target block,
wherein the control circuitry constructed and arranged to select the representative sub-block of the candidate block is further constructed and arranged to execute a deterministic function on multiple sub-blocks of the candidate block and to provide the representative sub-block as a sub-block of the multiple sub-blocks for which the deterministic function generates an extremum result.
13. A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a computerized apparatus, cause the computerized apparatus to perform a method of performing data deduplication, the method comprising:
selecting a representative sub-block of a candidate block, the representative sub-block occupying a first position within the candidate block;
matching the representative sub-block to an entry in a digest database, the matching entry identifying a target block that contains the representative sub-block in a second position; and
effectuating storage of the candidate block by referencing the target block and an adjacent block adjacent to the target block,
wherein selecting the representative sub-block of the candidate block includes executing a deterministic function on multiple sub-blocks of the candidate block, and providing the representative sub-block as a sub-block of the multiple sub-blocks for which the deterministic function generates an extremum result.
14. The computer program product of claim 13 ,
wherein the digest database associates the matching entry with a list of full blocks that contain the representative sub-block,
wherein the list of full blocks includes descriptive data about the full blocks, and
wherein the method further comprises selecting one of the full blocks based at least in part on the descriptive data for that full block.
15. The computer program product of claim 14 , wherein the descriptive data for one of the full blocks indicates a storage tier on which that full block is placed, and wherein selecting one of the full blocks is based at least in part on the storage tier indicated for that full block.
16. The computer program product of claim 14 , wherein the descriptive data for one of the full blocks includes a reference count that indicates a number of times that the full block has been a target of deduplication, and wherein selecting one of the full blocks is based at least in part on the reference count indicated for that full block.
17. The computer program product of claim 14 , wherein the descriptive data for one of the multiple full blocks includes a sequential-block indicator that indicates whether the full block is part of a sequence of blocks, and wherein selecting one of the full blocks is based at least in part on the sequential block indicator for that full block.
18. The computer program product of claim 13 , wherein matching the representative sub-block to the entry in the digest database includes generating a sub-block hash of the representative sub-block and matching the sub-block hash to a digest in the digest database associated with the matching entry.