Optmizing data deduplication

Abstract

Techniques for processing data may include: receiving a candidate block; performing partial deduplication processing of the candidate block; receiving a second candidate block subsequent to performing partial deduplication processing for the candidate block; and performing first processing to determine whether to perform promotion processing for the entry, The partial deduplication processing may include: partially deduplicating at least one sub-block of the candidate block; and creating an entry in a deduplication database for the candidate block, wherein the entry includes a digest of the candidate block and the entry denotes a potential target block having the digest, and wherein the entry includes a counter that tracks a number of missed full block deduplications between the potential target block and subsequently processed candidate blocks. The promotion processing promotes the potential target block, having the first digest of the entry, to a new target block.

What is claimed is: 
     
       1. A method of processing data comprising:
 receiving a first candidate block including a plurality of uniformly-sized sub-blocks; 
 performing partial deduplication processing of the first candidate block, wherein the partial deduplication processing includes:
 partially deduplicating at least one sub-block of the first candidate block; and 
 creating a first entry in a deduplication database for the first candidate block, wherein the first entry includes a first digest of the first candidate block and the first entry denotes a potential target block having the first digest, and wherein the first entry includes a counter that tracks a number of missed full block deduplications between the potential target block and subsequently processed candidate blocks; 
 
 receiving a second candidate block subsequent to performing partial deduplication processing for the first candidate block; and 
 performing first processing to determine whether to perform promotion processing for the first entry, wherein said promotion processing promotes the potential target block, having the first digest of the first entry, to a new target block. 
 
     
     
       2. The method of  claim 1 , further comprising:
 determining whether a second digest of the second candidate block matches the first digest of the first entry; and 
 responsive to determining the second digest of the second candidate block matches the first digest of the first entry, incrementing the counter of the first entry. 
 
     
     
       3. The method of  claim 2 , wherein the first processing includes:
 determining whether the counter of the first entry is less than a specified threshold; and 
 responsive to determining the counter of the first entry is not less than the specified threshold, performing said promotion processing for the first entry. 
 
     
     
       4. The method of  claim 3 , wherein the counter of the first entry is not less than the specified threshold and promotion processing is performed for the first entry, wherein the promotion processing for the first entry includes:
 storing a data block having the first digest on persistent storage; and 
 updating a reference field of the first entry to identify a location including content of the data block. 
 
     
     
       5. The method of  claim 4 , wherein the location is in a cache. 
     
     
       6. The method of  claim 4 , wherein the location is in the persistent storage. 
     
     
       7. The method of  claim 4 , further comprising:
 receiving a third candidate block; and 
 performing data deduplication processing for the third candidate block including:
 determining that the third candidate block is a duplicate of the data block having the first digest of the first entry; and 
 storing the third candidate block as a duplicate of the data block having the first digest of the first entry. 
 
 
     
     
       8. The method of  claim 7 , wherein the data deduplication processing for the third candidate block includes:
 computing a third digest for the third candidate block; 
 comparing the third digest to the first digest of the first entry; and 
 determining that the third digest matches the first digest. 
 
     
     
       9. The method of  claim 8 , further comprising:
 performing a comparison of data content of the third candidate block and data content of the data block having the first digest of the first entry. 
 
     
     
       10. The method of  claim 4 , wherein the second digest of the second candidate block matches the first digest of the first entry and the method includes:
 performing full block deduplication on the second candidate block where the second candidate block is stored as a duplicate of the data block having the first digest of the first entry. 
 
     
     
       11. The method of  claim 1 , wherein the method is performed as part of inline processing of one or more data blocks, including the first candidate block and the second candidate block, in connection with an I/O path or data path when servicing one or more I/Os accessing the one or more data blocks. 
     
     
       12. The method of  claim 1 , wherein the method is performed offline and the method is not performed as part of inline processing of one or more data blocks, including the first candidate block and the second candidate block, in connection with an I/O path or data path when servicing one or more I/Os accessing the one or more data blocks. 
     
     
       13. A system comprising:
 a processor; and 
 a memory comprising code stored thereon, that when executed, performs a method of processing data comprising:
 receiving a first candidate block including a plurality of uniformly-sized sub-blocks; 
 performing partial deduplication processing of the first candidate block, wherein the partial deduplication processing includes:
 partially deduplicating at least one sub-block of the first candidate block; and 
 creating a first entry in a deduplication database for the first candidate block, wherein the first entry includes a first digest of the first candidate block and the first entry denotes a potential target block having the first digest, and wherein the first entry includes a counter that tracks a number of missed full block deduplications between the potential target block and subsequently processed candidate blocks; 
 receiving a second candidate block subsequent to performing partial deduplication processing for the first candidate block; and 
 performing first processing to determine whether to perform promotion processing for the first entry, wherein said promotion processing promotes the potential target block, having the first digest of the first entry, to a new target block. 
 
 
 
     
     
       14. A computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising:
 receiving a first candidate block including a plurality of uniformly-sized sub-blocks; 
 performing partial deduplication processing of the first candidate block, wherein the partial deduplication processing includes:
 partially deduplicating at least one sub-block of the first candidate block; and 
 creating a first entry in a deduplication database for the first candidate block, wherein the first entry includes a first digest of the first candidate block and the first entry denotes a potential target block having the first digest, and wherein the first entry includes a counter that tracks a number of missed full block deduplications between the potential target block and subsequently processed candidate blocks; 
 
 receiving a second candidate block subsequent to performing partial deduplication processing for the first candidate block; and 
 performing first processing to determine whether to perform promotion processing for the first entry, wherein said promotion processing promotes the potential target block, having the first digest of the first entry, to a new target block. 
 
     
     
       15. The computer readable medium of  claim 14 , where the method further comprises:
 determining whether a second digest of the second candidate block matches the first digest of the first entry; and 
 responsive to determining the second digest of the second candidate block matches the first digest of the first entry, incrementing the counter of the first entry. 
 
     
     
       16. The computer readable medium of  claim 15 , wherein the first processing includes:
 determining whether the counter of the first entry is less than a specified threshold; and 
 responsive to determining the counter of the first entry is not less than the specified threshold, performing said promotion processing for the first entry. 
 
     
     
       17. The computer readable medium of  claim 15 , wherein the counter of the first entry is not less than the specified threshold and promotion processing is performed for the first entry, wherein the promotion processing for the first entry includes:
 storing a data block having the first digest on persistent storage; and 
 updating a reference field of the first entry to identify a location including content of the data block. 
 
     
     
       18. The computer readable medium of  claim 17 , wherein the location is in a cache. 
     
     
       19. The computer readable medium of  claim 17 , wherein the location is in the persistent storage. 
     
     
       20. The computer readable medium of  claim 17 , wherein the method further comprises:
 receiving a third candidate block; 
 performing data deduplication processing for the third candidate block including:
 determining that the third candidate block is a duplicate of the data block having the first digest of the first entry; and 
 storing the third candidate block as a duplicate of the data block having the first digest of the first entry.