# US 11,112,987 B2 · Optmizing data deduplication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,112,987 B2 - Document ID: US11112987B2 - Status: Granted - Kind: B2 - Application number: 16/392,913 - Filed: 2019-04-24 - Published: 2020-10-29 - Granted: 2021-09-07 - Earliest claimed: 2019-04-24 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Istvan Gonczi; Philippe Armangau; Sorin Faibish; Ivan Bassov - Web page: https://patentgrep.com/patent/US11112987B2 ## CPC - G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/0653: {Monitoring storage devices or systems} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 3) 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. ### Claim 5 (depends on 4) The method of claim 4, wherein the location is in a cache. ### Claim 6 (depends on 4) The method of claim 4, wherein the location is in the persistent storage. ### Claim 7 (depends on 4) 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 4) 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. ### Claim 11 (depends on 1) 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. ### Claim 12 (depends on 1) 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. ### Claim 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. ### Claim 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. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 17) The computer readable medium of claim 17, wherein the location is in a cache. ### Claim 19 (depends on 17) The computer readable medium of claim 17, wherein the location is in the persistent storage. ### Claim 20 (depends on 17) 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.