Selecting iteration schemes for deduplication

• US 8,775,388 B1
• Filed: 09/29/2010
• Issued: 07/08/2014
• Est. Priority Date: 09/29/2010
• 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., Long, Matthew, Owen, Karl, Ruef, Richard, Shiimkus, Joseph B. Jr.
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US12/893,865
• Time in Patent Office: 1,378 Days
• Field of Search: 707/692, 707/803
• US Class Current: 707/692
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14

Abstract

A method is used in selecting iteration schemes for deduplication. An iteration scheme is selected. Based on the selection, sets of data are iterated. Based on the iteration, a deduplicating technique is applied to the sets of data. Based on the results of applying the deduplicating technique, the iteration scheme is changed. Based on an evaluation of a set of criteria, the iteration scheme is changed.

Claims

1. A method for use in selecting iteration schemes for deduplication, the method comprising:

selecting a deduplication iteration scheme from a list of deduplication iteration schemes, wherein the deduplication iteration scheme indicates a pattern in which sets of data are iterated for applying a deduplicating technique to the sets of data, wherein the deduplication iteration scheme is selected based on a set of criteria;

based on the selection, iterating through the sets of data using the deduplication iteration scheme;

based on the iteration, applying the deduplicating technique to the sets of data; and

based on the results of applying the deduplicating technique, selecting another deduplication iteration scheme from the list of deduplication iteration scheme for the next iteration of the sets of data.

2. The method of claim 1, wherein selecting iteration schemes for deduplication further comprising:

based on an evaluation of a set of criteria, changing the iteration scheme.

3. The method of claim 1, further comprising selecting an iteration scheme from a list of iteration schemes, wherein the list of iteration schemes includes a sequential iteration, a parallel iteration, an iteration scheme supplied by a user and an iteration scheme supplied by an application.

4. The method of claim 1, wherein the set of criteria includes a type of storage device, a type of data, prior history of application of a deduplicating technique.

5. The method of claim 1, wherein each data of the sets of data is selected from the group consisting of a deduplication domain, a storage extent, a LUN and a data block, wherein the data block is a fixed size chunk of a physical disk storage.

6. The method of claim 5, wherein the deduplication domain comprises a set of storage extents, 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.

7. 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.

8. 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.

9. The method of claim 1, further comprising:

computing a digest for each data of the sets of data; and

processing the digest for each data of the sets of data for applying a deduplicating technique to the sets of data.

10. The method of claim 9, wherein the processing of digest further comprising:

comparing the digest 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 a deduplicating technique to the data block;

based on the determination, comparing contents of a 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.

11. The method of claim 10, 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.

12. The method of claim 1, 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.

13. A system for use in selecting iteration schemes for deduplication, the system comprising:

a processor;

first logic selecting a deduplication iteration scheme from a list of deduplication iteration schemes, wherein the deduplication iteration scheme indicates a pattern in which sets of data are iterated for applying a deduplicating technique to the sets of data, wherein the deduplication iteration scheme is selected based on a set of criteria;

second logic iterating, based on the selection, through the sets of data using the deduplication iteration scheme;

third logic applying, based on the iteration, the deduplicating technique to the sets of data; and

fourth logic selecting, based on the results of applying the deduplicating technique, another deduplication iteration scheme from the list of deduplication iteration scheme for the next iteration of the sets of data.

14. The system of claim 13, wherein selecting iteration schemes for deduplication further comprising:

fifth logic changing, based on an evaluation of a set of criteria, the iteration scheme.

15. The system of claim 13, further comprising selecting an iteration scheme from a list of iteration scheme wherein the list of iteration scheme includes a sequential iteration, a parallel iteration, an iteration scheme supplied by a user and an iteration scheme supplied by an application.

16. The system of claim 13, wherein the set of criteria includes a type of storage device, a type of data, prior history of application of a deduplicating technique.

17. The system of claim 13, wherein each data of the sets of data is selected from the group consisting of a deduplication domain, a storage extent, a LUN and a data block, wherein the data block is a fixed size chunk of a physical disk storage.

18. The system of claim 17, wherein the deduplication domain comprises a set of storage extents, 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.