Deduplicating sets of data blocks

• US 9,846,718 B1
• Filed: 03/31/2014
• Issued: 12/19/2017
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Ruef, Richard P., Hu, Ying, Everson, Kurt William
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Allen, Nicholas
• Application Number:
  US14/231,162
• Time in Patent Office: 1,359 Days
• Field of Search: 707692
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A method is used in deduplicating sets of data blocks. A candidate data object is identified for deduplicating a data object. A digest associated with the candidate data object matches a digest associated with the data object. Digest information of a set of data objects is evaluated. The set of data objects are selected for evaluation based on an association between location of the set of data objects and location of the candidate data object. Based on the evaluation, a deduplicating technique is applied for deduplicating the data object.

Claims

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

identifying a candidate data object for deduplicating a data object, wherein a digest associated with the candidate data object matches a digest associated with the data object wherein an index table stores digest information for the candidate data object and digest information for at least one data object residing adjacent to the candidate data object;

upon detecting a digest collision, determining whether to apply a deduplicating technique to the candidate data object and the data object by evaluating digest information of a set of data blocks residing adjacent to the candidate data block, wherein evaluating the digest information of the set of data blocks residing adjacent to the candidate data block includes determining whether a first set of data objects residing adjacent to the data object is identical to a second set of data objects residing at adjacent to the candidate data object, wherein the first and second sets of data objects are selected based on a reference of locality indicating a likelihood of the data object being identical to the candidate data object, wherein whether the first set of data objects is identical to the second set of data objects is determined by evaluating respective digest information of the first and second sets of data objects, wherein each data object of a set of data objects is associated with a respective digest, wherein the digest collision indicates that at least two data objects storing different contents are associated with the same digest; and

based on the determination that the first and second sets of data objects are identical to each other, applying a deduplicating technique to the data object and the candidate data object for deduplicating the data object to the candidate data object.

2. The method of claim 1, wherein a set of data objects resides on a storage extent comprising 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 a data object includes a data block, wherein a data block is a fixed size chunk of physical disk storage.

4. The method of claim 1, wherein a digest associated with a data object includes a checksum value for the data object, wherein the digest is based on contents of the data object and uniquely identifies the data object.

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 object, wherein each index entry of the set of index entries includes a digest of an adjacent data object and information regarding the data object.

6. The method of claim 1, wherein the data object is deduplicated upon receiving a request to write data to the data object.

7. The method of claim 1, wherein the first set of data objects reside adjacent to the candidate data object, wherein the first set of data objects are identical to the second set of data objects residing adjacent to the data object.

8. The method of claim 1, further comprising:

evaluating a list of entries associated with an index entry of an index table, wherein the index entry is associated with the digest of the candidate data object;

determining whether an entry in the list of entries includes a digest for a data block residing adjacent to the candidate data object; and

based on the determination, determining whether the data object adjacent to the candidate data object is identical to a data object adjacent to the data object.

9. The method of claim 8, further comprising:

updating the index table.

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

updating an address mapping of the candidate data object to point to the data object, wherein the candidate data object and the data object contain identical content of data, wherein an address mapping indicates a location of a data object on a disk storage; and

deleting the content of the candidate data object from the disk storage.

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

identify a candidate data object for deduplicating a data object, wherein a digest associated with the candidate data object matches a digest associated with the data object wherein an index table stores digest information for the candidate data object and digest information for at least one data object residing adjacent to the candidate data object;

upon detecting a digest collision, determine whether to apply a deduplicating technique to the candidate data object and the data object by evaluating digest information of a set of data blocks residing adjacent to the candidate data block, wherein evaluating the digest information of the set of data blocks residing adjacent to the candidate data block includes determining whether a first set of data objects residing adjacent to the data object is identical to a second set of data objects residing at adjacent to the candidate data object, wherein the first and second sets of data objects are selected based on a reference of locality indicating a likelihood of the data object being identical to the candidate data object, wherein whether the first set of data objects is identical to the second set of data objects is determined by evaluating respective digest information of the first and second sets of data objects wherein each data object of a set of data objects is associated with a respective digest, wherein the digest collision indicates that at least two data objects storing different contents are associated with the same digest; and

apply, based on the determination that the first and second sets of data objects are identical to each other, a deduplicating technique to the data object and the candidate data object for deduplicating the data object to the candidate data object.

12. The system of claim 11, wherein a set of data objects resides on a storage extent comprising 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 a data object includes a data block, wherein a data block is a fixed size chunk of physical disk storage.

14. The system of claim 11, wherein a digest associated with a data object includes a checksum value for the data object, wherein the digest is based on contents of the data object and uniquely identifies the data object.

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 object, wherein each index entry of the set of index entries includes a digest of an adjacent data object and information regarding the data object.

16. The system of claim 11, wherein the data object is deduplicated upon receiving a request to write data to the data object.

17. The system of claim 11, wherein the first set of data objects reside adjacent to the candidate data object, wherein the first set of data objects are identical to a second set of data objects residing adjacent to the data object.

18. The system of claim 11, further comprising:

evaluate a list of entries associated with an index entry of an index table, wherein the index entry is associated with the digest of the candidate data object;

determine whether an entry in the list of entries includes a digest for a data block residing adjacent to the candidate data object; and

determine, based on the determination, whether the data object adjacent to the candidate data object is identical to a data object adjacent to the data object.

19. The system of claim 18, further comprising:

update the index table.

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

update an address mapping of the candidate data object to point to the data object, wherein the candidate data object and the data object contain identical content of data, wherein an address mapping indicates a location of a data object on a disk storage; and

delete the content of the candidate data object from the disk storage.