Iterating in parallel for deduplication

• US 8,977,812 B1
• Filed: 03/30/2011
• Issued: 03/10/2015
• Est. Priority Date: 03/30/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Chen, Xiangping, de Forest, Miles A., Zhou, Siyu, Mullis, Samuel L., Spadafora, Brian M., Wan, Li
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/075,487
• Time in Patent Office: 1,441 Days
• Field of Search: 711/112, 711/E12.002, 707/692
• US Class Current: 711/112
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• 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 iterating in parallel for deduplication. Based on an iteration scheme, a collection of sections is selected from a set of storage extents. Each section of the collection of sections includes subset of the contents of a storage extent of the set of storage extents. Based on the iteration scheme, each section of the collection of sections is arranged in an ordered arrangement. Based on the ordered arrangement, a deduplicating technique is applied in parallel to each section of the collection of sections.

Claims

1. A method for use in iterating in parallel for deduplication, the method comprising:

selecting a collection of sections from a set of storage extents based on an iteration scheme, wherein a deduplication domain includes the set of storage extents, wherein each storage extent of the set of storage extents is apportioned into a set of sections, wherein each section of the collection of sections includes subset of the contents of a storage extent of the set of storage extents, wherein the contents of a storage extent includes a set of data blocks;

arranging each section of the collection of sections in an ordered arrangement based on the iteration scheme selected from a list of iteration schemes for applying a deduplicating technique, wherein the list of iteration schemes include a parallel iteration scheme, wherein each iteration scheme of the list of iteration schemes indicates a manner in which the set of storage extents is iterated for applying the deduplicating technique, wherein the ordered arrangement indicates an order in which each section of the collection of sections is processed for applying the deduplicating technique; and

based on the ordered arrangement, applying the deduplicating technique in parallel to each section of the collection of sections, wherein data blocks in each section of the collection of sections are deduplicated in parallel based on the ordered arrangement, wherein a number of sections of the collection of sections selected for applying the deduplicating technique in parallel are based on a set of processes used for deduplication, wherein each section of the number of sections is iterated by a process of the set of processes.

2. The method of claim 1, wherein each section of the collection of sections includes a set of data blocks, wherein each data block of the set of data blocks is a fixed size chunk of a physical disk storage.

3. The method of claim 1, wherein each storage extent of the set of storage extents comprises a set of LUNs, each LUN of the set of LUNs is a logical representation of a subset of a physical disk storage, each LUN of the set of LUNs includes a set of data blocks, wherein each data block of the set of data blocks is a fixed size chunk of the physical disk storage.

4. The method of claim 1, wherein a logical address space of each storage extent of the set of storage extents is apportioned into a set of sections, wherein each section of the set of sections is equal in size.

5. The method of claim 4, further comprising:

arranging each section of the set of sections in the ordered arrangement based on the iteration scheme.

6. The method of claim 5, further comprising:

a) based on the ordered arrangement, selecting the collection of sections from the set of sections;

b) iterating each section of the collection of sections in parallel for deduplication;

c) adding a section from the set of sections to the collection of sections based on the ordered arrangement; and

repeating steps a-c until each section from the set of sections is added to the collection of sections for iterating in parallel for deduplication.

7. The method of claim 1, further comprising:

storing an iterator on a persistent storage, wherein the iterator indicates a last section to which the deduplicating technique has been applied; and

applying a deduplicating technique to a section based on the iterator.

8. The method of claim 2, 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.

9. The method of claim 2, 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.

10. The method of claim 2, further comprising:

computing a digest for each data block of each section of the collection of sections; and

processing the digest for each data block of each section of the collection of sections for applying the deduplicating technique to the collection of sections.

11. The method of claim 10, wherein the processing of digest of a data block further comprising:

comparing the digest of the data block with one or more index entries of the index table;

determining, based on whether the digest matches with an index entry of the index table, whether to apply the deduplicating technique to the data block;

based on the determination, comparing contents of the data block associated with the digest with contents of a data block associated with the matching index entry; and

based on the comparison, applying the deduplicating technique to the data block associated with the digest and the data block associated with the matching index entry.

12. The method of claim 11, further comprising:

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

13. The method of claim 2, wherein applying the deduplicating technique further comprising:

updating an address mapping of a first data block to point to a second data block, 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.

14. A system for use in iterating in parallel for deduplication, the system comprising a processor configured to:

select a collection of sections from a set of storage extents based on an iteration scheme, wherein a deduplication domain includes the set of storage extents, wherein each storage extent of the set of storage extents is apportioned into a set of sections, wherein each section of the collection of sections includes subset of the contents of a storage extent of the set of storage extents, wherein the contents of a storage extent includes a set of data blocks;

arrange each section of the collection of sections in an ordered arrangement based on the iteration scheme selected from a list of iteration schemes for applying a deduplicating technique, wherein the list of iteration schemes include a parallel iteration scheme, wherein each iteration scheme of the list of iteration schemes indicates a manner in which the set of storage extents is iterated for applying the deduplicating technique, wherein the ordered arrangement indicates an order in which each section of the collection of sections is processed for applying the deduplicating technique; and

apply, based on the ordered arrangement, the deduplicating technique in parallel to each section of the collection of sections, wherein data blocks in each section of the collection of sections are deduplicated in parallel based on the ordered arrangement, wherein a number of sections of the collection of sections selected for applying the deduplicating technique in parallel are based on a set of processes used for deduplication, wherein each section of the number of sections is iterated by a process of the set of processes.

15. The system of claim 14, wherein each section of the collection of sections includes a set of data blocks, wherein each data block of the set of data blocks is a fixed size chunk of a physical disk storage.

16. The system of claim 14, wherein each storage extent of the set of storage extents comprises a set of LUNs, each LUN of the set of LUNs is a logical representation of a subset of a physical disk storage, each LUN of the set of LUNs includes a set of data blocks, wherein each data block of the set of data blocks is a fixed size chunk of the physical disk storage.

17. The system of claim 14, wherein a logical address space of each storage extent of the set of storage extents is apportioned into a set of sections, wherein each section of the set of sections is equal in size.

18. The system of claim 17, further comprising:

arrange each section of the set of sections in the ordered arrangement based on the iteration scheme.

19. The system of claim 18, further comprising:

a) select, based on the ordered arrangement, the collection of sections from the set of sections;

b) iterate each section of the collection of sections in parallel for deduplication;

c) add a section from the set of sections to the collection of sections based on the ordered arrangement; and

repeating steps a-c until each section from the set of sections is added to the collection of sections for iterating in parallel for deduplication.

20. The system of claim 14, further comprising:

store an iterator on a persistent storage, wherein the iterator indicates a last section to which the deduplicating technique has been applied; and

apply a deduplicating technique to a section based on the iterator.