# US 10,768,843 B2 · Optmizing metadata management in data deduplication > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,768,843 B2 - Document ID: US10768843B2 - Status: Granted - Kind: B2 - Application number: 16/266,306 - Filed: 2019-02-04 - Published: 2020-08-06 - Granted: 2020-09-08 - Earliest claimed: 2019-02-04 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Sorin Faibish; Philippe Armangau; Istvan Gonczi; Ivan Bassov; Anton Kucherov - Web page: https://patentgrep.com/patent/US10768843B2 ## CPC - G06F 3/0641: {De-duplication techniques} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 3/0673: {Single storage device} - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Techniques for data processing may include: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored from a first offset to a second offset corresponding to the first location; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein a tag descriptor describing the tag is stored and associated with the candidate block, such as in block-level metadata of the candidate block. The tag descriptor may include tag content and tag location information. ## Claims ### Claim 1 A method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location, wherein a tag descriptor includes tag content and includes location information identifying the first location in the candidate block, and wherein the tag content is stored at the first location in the candidate block; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein the tag descriptor describing the tag is stored and associated with the candidate block. ### Claim 2 (depends on 1) The method of claim 1, wherein the tag descriptor is included in block-level metadata of the candidate block. ### Claim 3 (depends on 1) The method of claim 1, wherein the tag has a corresponding size that is less than a size of one of the plurality of sub-blocks of the candidate block. ### Claim 4 (depends on 1) The method of claim 1, wherein the tag is a logically contiguous region located at the first location in the candidate block. ### Claim 5 (depends on 4) The method of claim 4, wherein the logically contiguous region spans two logically adjacent sub-blocks of the candidate block. ### Claim 6 (depends on 1) The method of claim 1, wherein the location information of the tag descriptor includes a starting offset identifying a starting location in the candidate block where the tag is stored, and a length denoting a length of the tag. ### Claim 7 (depends on 1) The method of claim 1, further comprising: receiving a request to read a first block, wherein at least a first sub-block of the first block has been deduplicated whereby the first sub-block is a duplicate of a first target sub-block, and wherein at least a second sub-block of the first block has not been deduplicated; performing first processing to construct the first block comprising: storing the first target sub-block and the second sub-block in a buffer; and overwriting specified locations in the buffer with a second tag having an associated second tag descriptor stored in metadata of the first block; and returning the buffer to a client that requested the first block. ### Claim 8 (depends on 7) The method of claim 7, wherein the first processing includes decompressing the first target sub-block and the second sub-block and storing corresponding decompressed forms of the first target sub-block and the second sub-block in the buffer. ### Claim 9 (depends on 1) The method of claim 1, wherein the method is performed inline as part of the I/O or data path, and the candidate block is written in connection with a write I/O operation. ### Claim 10 (depends on 1) The method of claim 1, wherein said data deduplication processing includes: searching a deduplication database for a target sub-block that matches a first sub-block of the candidate block; responsive to finding a matching entry in the deduplication database for the target sub-block matching the first sub-block of the candidate block, performing first processing including: identifying a portion of a previously stored target block that corresponds to the target sub-block; identifying a target range of the target block that matches a duplicate range of the first sub-block of the candidate block; and configuring mapping metadata of the candidate block to reference the target range of the target block as corresponding to deduplicated data stored at the duplicate range of the first sub-block of the candidate block. ### Claim 11 (depends on 10) The method of claim 10, wherein the deduplication database is stored in cache is a first deduplication database, and wherein the first deduplication database stored in cache includes a portion of entries of a second larger deduplication database that is stored on non-volatile storage. ### Claim 12 (depends on 11) The method of claim 11, wherein the first deduplication database stored in cache is indexed using keys of a first size and the second larger deduplication database stored on non-volatile storage is indexed using keys of a second size larger than the first size. ### Claim 13 (depends on 12) The method of claim 12, wherein the second larger deduplication database uses keys of the second size generated using a hash function and wherein keys of the first deduplication database are truncated hash values generated using the hash function. ### Claim 14 (depends on 1) The method of claim 1, wherein the tag is a difference or delta region identified in the candidate block that, except for the tag, is identical to an existing target block stored in a deduplication database. ### Claim 15 A method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein a tag descriptor describing the tag is stored and associated with the candidate block, and wherein the method includes performing first processing that determines whether the candidate block has the tag, said first processing including: scanning the candidate block from a right-most sub-block and determining the second offset at which a difference is detected between the candidate block and a target block; scanning the candidate block from a left-most sub-block and determining the first offset at which a difference is detected between the candidate block and the target block; determining whether a distance between the first offset and the second offset is less than a maximum tag size; and responsive to determining the distance is less than the maximum tag size, determining that the candidate block has the tag with an associated tag location from the first offset to the second offset in the candidate block. ### Claim 16 (depends on 15) The method of claim 15, wherein the first processing determines that the candidate block, excluding content located from the first offset to the second offset, is a duplicate of the target block. ### Claim 17 A system comprising: at least one processor; and a memory comprising code stored thereon that, when executed, performs a method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location, wherein a tag descriptor includes tag content and includes location information identifying the first location in the candidate block, and wherein the tag content is stored at the first location in the candidate block; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein the tag descriptor describing the tag is stored and associated with the candidate block. ### Claim 18 A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location, wherein a tag descriptor includes tag content and includes location information identifying the first location in the candidate block, and wherein the tag content is stored at the first location in the candidate block; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein the tag descriptor describing the tag is stored and associated with the candidate block. ### Claim 19 (depends on 18) The non-transitory computer readable medium of claim 18, wherein the tag descriptor is included in block-level metadata of the candidate block. ### Claim 20 A system comprising: at least one processor; and a memory comprising code stored thereon that, when executed, performs a method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein a tag descriptor describing the tag is stored and associated with the candidate block, and wherein the method includes performing first processing that determines whether the candidate block has the tag, said first processing including: scanning the candidate block from a right-most sub-block and determining the second offset at which a difference is detected between the candidate block and a target block; scanning the candidate block from a left-most sub-block and determining the first offset at which a difference is detected between the candidate block and the target block; determining whether a distance between the first offset and the second offset is less than a maximum tag size; and responsive to determining the distance is less than the maximum tag size, determining that the candidate block has the tag with an associated tag location from the first offset to the second offset in the candidate block. ### Claim 21 A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing data comprising: receiving a candidate block including a plurality of uniformly-sized sub-blocks, wherein a tag is stored at a first location in the candidate block; performing data deduplication processing of the candidate block, wherein the data deduplication processing excludes content stored at the first location, and wherein a first offset to a second offset of the candidate block corresponds to the first location; determining whether at least one sub-block of the candidate block has been deduplicated by the data deduplication processing; and responsive to determining that at least one sub-block of the candidate block has been deduplicated, storing the candidate block as a deduplicated data block having at least one sub-block matching an existing target sub-block, wherein a tag descriptor describing the tag is stored and associated with the candidate block, and wherein the method includes performing first processing that determines whether the candidate block has the tag, said first processing including: scanning the candidate block from a right-most sub-block and determining the second offset at which a difference is detected between the candidate block and a target block; scanning the candidate block from a left-most sub-block and determining the first offset at which a difference is detected between the candidate block and the target block; determining whether a distance between the first offset and the second offset is less than a maximum tag size; and responsive to determining the distance is less than the maximum tag size, determining that the candidate block has the tag with an associated tag location from the first offset to the second offset in the candidate block.