Deduplicating sets of data blocks

• US 8,805,796 B1
• Filed: 06/27/2011
• Issued: 08/12/2014
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Hu, Ying, Ruef, Richard P.
• Primary Examiner(s): Kerzhner, Aleksandr
• Application Number:
  US13/169,679
• Time in Patent Office: 1,142 Days
• Field of Search: 707/692, 707/999.101
• US Class Current: 707/692
• 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/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method is used in deduplicating sets of data blocks. A collection of data is selected from a set of storage extents. The collection of data is selected based on evaluation of digest information for first and second data blocks of the collection of data. A deduplicating technique is applied to the collection of data.

Claims

1. A method for use in deduplicating sets of data blocks, the method comprising:

determining a first data block from a first collection of data from a set of storage extents and a second data block from a second collection of data from the set of storage extents, wherein the first and second data blocks represent a pair of data blocks for applying a deduplicating technique based on evaluation of digest information of the first and second data blocks;

based on the determination, applying the deduplicating technique for deduplicating a specific number of data blocks residing adjacent to the first data block to the specific number of data blocks residing adjacent to the second data block; and

adjusting the application of the deduplicating technique based on determination of the number of data blocks from the specific number of data blocks that fail to get deduplicated.

2. The method of claim 1, wherein each storage extent of the set of storage extents comprises a set of LUNs, wherein each LUN of the set of LUNs is a logical representation of a subset of a physical disk storage.

3. The method of claim 1, wherein the collection of data comprises a collection of data blocks, wherein the data block is a fixed size chunk of a physical disk storage.

4. The method of claim 1, wherein a digest is associated with a data block, wherein the digest is based on contents of the data block and uniquely identifies the data block.

5. The method of claim 1, wherein an index table comprises a set of index entries, wherein each index entry of the set of index entries is associated with a digest of a data block.

6. The method of claim 1, further comprising:

computing a digest for each data block in a storage extent of the set of storage extents;

comparing the digest for each data block in a storage extent of the set of storage extents with a pattern of data defined by a criterion, wherein the criterion is based on the digest of the data block; and

based on the comparison, adding an index entry to an index table, wherein the index entry is associated with the digest.

7. The method of claim 1, wherein selecting a collection of data from a set of storage extents further comprising:

comparing a digest with one or more index entries of an index table;

determining a pair of matching digest entries, based on whether the digest matches with an index entry of the index table; and

selecting a range of data blocks adjacent to data blocks associated with the pair of matching digest entries for applying the deduplicating technique.

8. The method of claim 1, further comprising:

selecting a first data block and a second data block from the collection of data from the set of storage extents;

comparing contents of the first data block with contents of the second data block; and

based on the comparison, applying the deduplicating technique to the first data block and the second data block.

9. The method of claim 1, wherein applying the deduplicating technique further comprising:

updating an address mapping of a first data block of the collection of data to point to a second data block of the collection of data, wherein the first data block and the second data block contain same content of data, wherein the address mapping indicates a location of a data block on a disk storage; and

deleting the content of the first data block from the disk storage.

10. The method of claim 1, further comprising:

updating a counter based on application of the deduplicating technique to the collection of data;

updating a criteria for selecting the collection of data based on the counter; and

updating a pre-defined number for selecting a range of data blocks for deduplication processing.

11. A system for use in deduplicating sets of data blocks, the system comprising a processor configured to:

determine a first data block from a first collection of data from a set of storage extents organized on a storage system and a second data block from a second collection of data from the set of storage extents, wherein the first and second data blocks represent a pair of data blocks for applying a deduplicating technique based on evaluation of digest information of the first and second data blocks;

applying, based on the determination, the deduplicating technique for deduplicating a specific number of data blocks residing adjacent to the first data block to the specific number of data blocks residing adjacent to the second data block; and

adjusting the application of the deduplicating technique based on determination of the number of data blocks from the specific number of data blocks that fail to get deduplicated.

12. The system of claim 11, wherein each storage extent of the set of storage extents comprises a set of LUNs, wherein each LUN of the set of LUNs is a logical representation of a subset of a physical disk storage.

13. The system of claim 11, wherein the collection of data comprises a collection of data blocks, wherein the data block is a fixed size chunk of a physical disk storage.

14. The system of claim 11, wherein a digest is associated with a data block, wherein the digest is based on contents of the data block and uniquely identifies the data block.

15. The system of claim 11, wherein an index table comprises a set of index entries, wherein each index entry of the set of index entries is associated with a digest of a data block.

16. The system of claim 11, further comprising:

compute a digest for each data block in a storage extent of the set of storage extents;

compare the digest for each data block in a storage extent of the set of storage extents with a pattern of data defined by a criterion, wherein the criterion is based on the digest of the data block; and

based on the comparison, add an index entry to an index table, wherein the index entry is associated with the digest.

17. The system of claim 11, wherein selecting a collection of data from a set of storage extents further comprising:

compare a digest with one or more index entries of an index table;

determine a pair of matching digest entries, based on whether the digest matches with an index entry of the index table; and

select a range of data blocks adjacent to data blocks associated with the pair of matching digest entries for applying the deduplicating technique.

18. The system of claim 11, further comprising:

select a first data block and a second data block from the collection of data from the set of storage extents;

compare contents of the first data block with contents of the second data block; and

based on the comparison, apply the deduplicating technique to the first data block and the second data block.

19. The system of claim 11, wherein applying the deduplicating technique further comprising:

update an address mapping of a first data block of the collection of data to point to a second data block of the collection of data, wherein the first data block and the second data block contain same content of data, wherein the address mapping indicates a location of a data block on a disk storage; and

delete the content of the first data block from the disk storage.

20. The system of claim 11, further comprising:

update a counter based on application of the deduplicating technique to the collection of data;

update a criteria for selecting the collection of data based on the counter; and

update a pre-defined number for selecting a range of data blocks for deduplication processing.