DEDUPLICATING DATA AT SUB-BLOCK GRANULARITY

• US 20200133928A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Armangau, Philippe, Faibish, Sorin, Gonczi, Istvan, Bassov, Ivan, Vankamamidi, Vamsi K.
• Granted Patent: US 10,963,436 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

A technique for performing data deduplication operates at sub-block granularity by searching a deduplication database for a match between a candidate sub-block of a candidate block and a target sub-block of a previously-stored target block. When a match is found, the technique identifies a duplicate range shared between the candidate block and the target block and effects persistent storage of the duplicate range by configuring mapping metadata of the candidate block so that it points to the duplicate range in the target block.

Claims

1. A method of performing data deduplication, the method comprising:

receiving, by a data storage system, an I/O (Input/Output) request that specifies a write of a set of data to the data storage system, the data storage system defining a candidate block from at least a portion of the set of data, the candidate block including multiple uniformly-sized sub-blocks, the sub-blocks including a candidate sub-block;

searching a deduplication database for a target sub-block that matches the candidate sub-block; and

in response to finding a matching entry in the deduplication database for the target sub-block, (i) accessing, based on a reference stored in the matching entry, a previously-stored target block that contains the target sub-block, (ii) identifying a shared range between the candidate block and the target block for which a duplicate range R_DUP of the candidate block matches a target range R_TARG of the target block, and (iii) effecting persistent storage of the duplicate range R_DUP of the candidate block by configuring mapping metadata of the candidate block to reference the target range R_TARG of the target block.

2. The method of claim 1, further comprising, in response to finding the matching entry in the deduplication database for the target sub-block:

identifying a unique range R_UQ of the candidate block that does not match any range of the target block; and

persistently storing the unique range R_UQ of the candidate block in a storage extent.

3. The method of claim 2, wherein identifying the duplicate range R_DUP of the candidate block includes locating a boundary between the duplicate range R_DUP and the unique range R_UQ by comparing the candidate block with the target block in increments smaller than a sub-block.

4. The method of claim 3, wherein configuring the mapping metadata for the candidate block to reference the target range R_TARG of the target block includes specifying, in the mapping metadata, an offset and length of the target range R_TARG in the target block.

5. The method of claim 3, wherein searching the deduplication database includes:

computing a digest of the candidate sub-block; and

searching the deduplication database for an entry that corresponds to the computed digest.

6. The method of claim 5 wherein, when computing the digest of the candidate block, the method includes:

computing a digest of each of the sub-blocks of the candidate block; and

searching the deduplication database for respective entries that correspond to the computed digest of one or more of the sub-blocks.

7. The method of claim 6, wherein the sub-blocks of the candidate block consist of first through last contiguous sub-blocks, and wherein the method further comprises:

creating a new entry in the deduplication database for the first sub-block, the new entry indexed based on the digest of the first sub-block and including a reference to a location of the candidate block in the data storage system; and

creating a new entry in the deduplication database for the last sub-block, the new entry for the last sub-block indexed based on the digest of the last sub-block and including a reference to the location of the candidate block in the data storage system.

8. The method of claim 6, further comprising:

receiving, by the data storage system, additional sets of data, the data storage system defining additional candidate blocks from the additional sets of data;

for each of the additional candidate blocks, (i) creating a new entry in the deduplication database for a first sub-block of the respective candidate block, (ii) creating a new entry in the deduplication database for a last sub-block of the respective candidate block, and (ii) creating no new entries for any sub-blocks between the first sub-block and the last sub-block.

9. The method of claim 5, wherein the matching entry in the deduplication database further specifies a sub-block position, the sub-block position indicating a position of the target sub-block within the target block, and wherein locating the boundary between the duplicate range R_DUP and the unique range R_UQ includes applying the sub-block position in selecting a direction in which to proceed when comparing the candidate block with the target block.

10. The method of claim 5, further comprising:

identifying a second unique range R_UQ2 of the candidate block that does not match any range of the target block and that is discontiguous with the unique range R_UQ within the candidate block; and

persistently storing the second unique range R_UQ2 along with the unique range R_UQ in the storage extent.

11. The method of claim 10, further comprising configuring mapping metadata that identifies a boundary in the storage extent between the unique range R_UQ and the second unique range R_UQ2.

12. The method of claim 5, further comprising:

identifying a second duplicate range R_DUP2 of the candidate block, the second duplicate range R_DUP2 matching a sub-block of a second target block; and

effecting persistent storage of the second duplicate range R_DUP2 by configuring mapping metadata to reference the sub-block of the second target block.

13. The method of claim 5, further comprising:

identifying a second duplicate range R_DUP2 of the candidate block, the second duplicate range R_DUP2 matching a second sub-block of the target block; and

effecting persistent storage of the second duplicate range R_DUP2 by configuring mapping metadata to reference the second sub-block of the target block.

14. The method of claim 5, further comprising:

providing a first block virtualization structure (BVS) for the candidate block, the first BVS including a pointer to a location in where the unique range R_UQ of the candidate block is persistently stored; and

providing a second BVS for the target block, the second BVS including a pointer to a location where the target range R_TARG of the target block is persistently stored.

15. The method of claim 14, further comprising storing, in a metadata block that contains the first BVS, the mapping metadata that references the range R_TARG of the target block.

16. The method of claim 14, further comprising:

providing a leaf indirect block (IB) that includes a block pointer to the first BVS; and

storing, in the leaf IB, the mapping metadata that points to the range R_TARG of the target block.

17. The method of claim 5, wherein each of the sub-blocks has a size of one sector (512 Bytes).

18. The method of claim 17, wherein computing the digest of the candidate sub-block provides the digest as a hash value having fewer than 128 bits, and wherein, when comparing the candidate block with the target block, the method further comprises confirming that the matching entry is not a hash collision.

22. The method of claim 1, wherein the candidate block and the target block are each blocks in the data storage system, wherein a block is the smallest unit of storage space that can be allocated.

19. A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:

define, by a data storage system, multiple uniformly-sized sub-blocks of a candidate block, the sub-blocks including a candidate sub-block;

search a deduplication database for a target sub-block that matches the candidate sub-block; and

in response to finding a matching entry in the deduplication database for the target sub-block, (i) access, by following a pointer stored in the matching entry, a previously-stored target block that contains the target sub-block, (ii) identify a shared range between the candidate block and the target block for which a duplicate range R_DUP of the candidate block matches a target range R_TARG of the target block, and (iii) effect persistent storage of the duplicate range R_DUP of the candidate block by configuring mapping metadata of the candidate block to reference the target range R_TARG of the target block.

20. A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a data storage system, cause the control circuitry to perform a method of performing data deduplication, the method comprising:

defining, by a data storage system, multiple uniformly-sized sub-blocks of a candidate block, the sub-blocks including a candidate sub-block;

searching a deduplication database for a target sub-block that matches the candidate sub-block; and

in response to finding a matching entry in the deduplication database for the target sub-block, (i) accessing, by following a pointer stored in the matching entry, a previously-stored target block that contains the target sub-block, (ii) identifying a shared range between the candidate block and the target block for which a duplicate range R_DUP of the candidate block matches a target range R_TARG of the target block, and (iii) effecting persistent storage of the duplicate range R_DUP of the candidate block by configuring mapping metadata of the candidate block to reference the target range R_TARG of the target block.

21. The computer program product of claim 20, wherein data deduplication is performed on the duplicate range R_DUP of the candidate block without first persistently storing the candidate block in the data storage system, such that the deduplication of the duplicate range R_DUP is an inline deduplication.