Techniques for managing deduplication based on recently written extents

• US 8,799,601 B1
• Filed: 06/28/2012
• Issued: 08/05/2014
• Est. Priority Date: 06/28/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Chen, Xiangping, Armangau, Philippe
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US13/536,375
• Time in Patent Office: 768 Days
• Field of Search: 711/162, 711/161, 711/163, 711/167
• US Class Current: 711/162
• 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]

Abstract

A technique is directed to managing deduplication of extents in a data storage apparatus having processing circuitry and memory which stores the extents (e.g., blocks). The technique involves constructing, by the processing circuitry, a recently written extent list which identifies recently written extents stored within the memory. The technique further involves referencing the recently written extent list to bypass (or skip over) extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication. The technique further involves processing the candidate extent for possible deduplication. Here, by identifying frequently overwritten extents on the recently written extent list, the data storage apparatus is able to easily avoid cycles of deduplicating and subsequently splitting frequently overwritten extents.

Claims

1. In a data storage apparatus having processing circuitry and memory which stores extents, a method of managing deduplication of the extents, the method comprising:

constructing, by the processing circuitry, a recently written extent list which identifies recently written extents stored within the memory;

referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication; and

processing the candidate extent for possible deduplication;

wherein the data storage apparatus maintains an extent sharing index table having entries which (i) have existing hash values and (ii) identify extents; and

wherein processing the candidate extent for possible deduplication includes;

digesting the candidate extent to produce a current hash value,

searching the extent sharing index table for an existing entry having an existing hash value which matches the current hash value,

when an existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value,

(i) searching the recently written extent list to confirm that an existing extent, which is identified by the existing entry, is not identified by the recently written extent list,

(ii) when the existing extent is not identified by the recently written extent list, performing a comprehensive compare operation to determine whether to deduplicate the candidate extent with the existing extent, and

(iii) when the existing extent is identified by the recently written extent list, adding a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent, and

when no existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value, adding a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent.

2. A method as in claim 1 wherein the processing circuitry has access to a series of extent identifiers identifying candidate extents;

and wherein referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining the candidate extent for possible deduplication includes;

outputting, as the candidate extent, a first extent identifier of the series of extent identifiers when the first extent identifier is not on the recently written extent list, and

skipping over the first extent identifier and outputting, as the candidate extent, a second extent identifier of the series of extent identifiers when (i) the first extent identifier is on the recently written extent list and (ii) the second extent identifier is not on the recently written extent list.

3. A method as in claim 2 wherein performing the comprehensive compare operation to determine whether to deduplicate the candidate extent with the existing extent includes:

(i) comprehensively comparing the candidate extent with the existing extent, and

(ii) performing an extent sharing operation between the candidate extent and the existing extent only upon a successful comprehensive comparison.

4. A method as in claim 1, further comprising:

performing a cleanup operation to reduce the size of the extent sharing index table based on the recently written extent list.

5. A method as in claim 4 wherein performing the cleanup operation to reduce the size of the extent sharing index table based on the recently written extent list includes:

deleting, from the extent sharing index table, existing entries which identify extents identified by the recently written extent list.

6. In a data storage apparatus having processing circuitry and memory which stores extents, a method of managing deduplication of the extents, the method comprising:

constructing, by the processing circuitry, a recently written extent list which identifies recently written extents stored within the memory;

referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication; and

processing the candidate extent for possible deduplication;

wherein constructing the recently written extent list which identifies the recently written extents includes;

from a lock history database which stores a collection of lock information regarding write locks and other locks imposed on the extents stored in the memory, filtering the collection of lock information to ascertain write locked extents satisfying a predefined policy, and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy.

7. A method as in claim 6 wherein the lock history database includes lock history records, each lock history record identifying a type of lock imposed on a range of extents;

and wherein filtering and building includes;

identifying, as the recently written extents, extents from records of write range locks involving host write operations to ranges of extents, and ignoring records of other types of range locks involving other types of operations on the ranges of extents.

8. A method as in claim 6 wherein the predefined policy identifies a predefined amount of time;

and wherein filtering and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy includes;

on the recently written extent list, (i) listing extents which were modified within the predefined amount of time and (ii) not listing extents which were not modified within the predefined amount of time.

9. A method as in claim 6 wherein the predefined policy identifies (i) a predefined number of times as a write count, and (ii) a predefined amount of time;

and wherein filtering and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy includes;

on the recently written extent list, (i) listing extents which were modified at least the predefined number of times within the predefined amount of time and (ii) not listing extents which were not modified at least the predefined number of times within the predefined amount of time.

10. A data storage apparatus, comprising:

a host interface;

memory; and

processing circuitry coupled to the host interface and the memory, the processing circuitry (i) processing host IO operations received through the host interface and (ii) managing deduplication of extents;

wherein the processing circuitry, when managing deduplication of extents, is constructed and arranged to;

construct, in the memory, a recently written extent list which identifies recently written extents stored within the memory,

reference the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication, and

process the candidate extent for possible deduplication; and

wherein the processing circuitry maintains an extent sharing index table having entries which (i) have existing hash values and (ii) identify extents; and

wherein the processing circuitry, when processing the candidate extent for possible deduplication, is constructed and arranged to;

digest the candidate extent to produce a current hash value,

search the extent sharing index table for an existing entry having an existing hash value which matches the current hash value,

when an existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value,

(i) search the recently written extent list to confirm that an existing extent, which is identified by the existing entry, is not identified by the recently written extent list,

(ii) when the existing extent is not identified by the recently written extent list, perform a comprehensive compare operation to determine whether to deduplicate the candidate extent with the existing extent, and

(iii) when the existing extent is identified by the recently written extent list, add a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent, and

when no existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value, add a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent.

11. A data storage apparatus as in claim 10 wherein the processing circuitry has access to a series of extent identifiers identifying candidate extents;

and wherein the processing circuitry, when referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining the candidate extent for possible deduplication, is constructed and arranged to;

output, as the candidate extent, a first extent identifier of the series of extent identifiers when the first extent identifier is not on the recently written extent list, and

skip over the first extent identifier and outputting, as the candidate extent, a second extent identifier of the series of extent identifiers when (i) the first extent identifier is on the recently written extent list and (ii) the second extent identifier is not on the recently written extent list.

12. A data storage apparatus as in claim 10 wherein the processing circuitry is further constructed and arranged to:

perform a cleanup operation to reduce the size of the extent sharing index table based on the recently written extent list.

13. A data storage apparatus, comprising:

a host interface;

memory; and

processing circuitry coupled to the host interface and the memory, the processing circuitry (i) processing host IO operations received through the host interface and (ii) managing deduplication of extents;

wherein the processing circuitry, when managing deduplication of extents, is constructed and arranged to;

construct, in the memory, a recently written extent list which identifies recently written extents stored within the memory,

reference the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication, and

process the candidate extent for possible deduplication; and

wherein the processing circuitry, when constructing the recently written extent list which identifies the recently written extents, is constructed and arranged to;

from a lock history database which stores a collection of lock information regarding write locks and other locks imposed on the extents stored in the memory, filter the collection of lock information to ascertain write locked extents satisfying a predefined policy, and build the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy.

14. A data storage apparatus as in claim 13 wherein the lock history database includes lock history records, each lock history record identifying a type of lock imposed on a range of extents;

and wherein the processin circuitry, when filtering and building, is constructed and arranged to;

identify, as the recently written extents, extents from records of write range locks involving host write operations to ranges of extents, and ignore records of other types of range locks involving other types of operations on the ranges of extents.

15. A data storage apparatus as in claim 13 wherein the predefined policy identifies (i) a predefined number of times as a write count, and (ii) a predefined amount of time;

and wherein the processing circuitry, when filtering and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy, is constructed and arranged to;

on the recently written extent list, (i) list extents which were modified at least the predefined number of times within the predefined amount of time and (ii) not list extents which were not modified at least the predefined number of times within the predefined amount of time.

16. A computer program product having a non-transitory computer readable medium storing a set of instructions which, when carried out by a computerized device, directs the computerized device to manage deduplication of extents by performing a method comprising:

constructing, by the computerized device, a recently written extent list which identifies recently written extents stored within memory of the computerized device;

referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication; and

processing the candidate extent for possible deduplication;

wherein the computerized device maintains an extent sharing index table having entries which (i) have existing hash values and (ii) identify extents; and

wherein processing the candidate extent for possible deduplication includes;

digesting the candidate extent to produce a current hash value,

searching the extent sharing index table for an existing entry having an existing hash value which matches the current hash value,

when an existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value,

(i) searching the recently written extent list to confirm that an existing extent, which is identified by the existing entry, is not identified by the recently written extent list,

(ii) when the existing extent is not identified by the recently written extent list, performing a comprehensive compare operation to determine whether to deduplicate the candidate extent with the existing extent, and

(iii) when the existing extent is identified by the recently written extent list, adding a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent, and

when no existing entry in the extent sharing index table is found to have an existing hash value which matches the current hash value, adding a new entry to the extent sharing index table, the new entry having the current hash value and identifying the candidate extent.

17. A computer program product as in claim 16 wherein the computerized device has access to a series of extent identifiers identifying candidate extents;

and wherein referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining the candidate extent for possible deduplication includes;

outputting, as the candidate extent, a first extent identifier of the series of extent identifiers when the first extent identifier is not on the recently written extent list, and

skipping over the first extent identifier and outputting, as the candidate extent, a second extent identifier of the series of extent identifiers when (i) the first extent identifier is on the recently written extent list and (ii) the second extent identifier is not on the recently written extent list.

18. A computer program product as in claim 16 wherein the method further comprises:

performing a cleanup operation to reduce the size of the extent sharing index table based on the recently written extent list.

19. A computer program product having a non-transitory computer readable medium storing a set of instructions which, when carried out by a computerized device, directs the computerized device to manage deduplication of extents by performing a method comprising:

constructing, by the computerized device, a recently written extent list which identifies recently written extents stored within memory of the computerized device;

referencing the recently written extent list to bypass extents identified by the recently written extent list when obtaining a candidate extent for possible deduplication; and

processing the candidate extent for possible deduplication;

wherein constructing the recently written extent list which identifies the recently written extents includes;

from a lock history database which stores a collection of lock information regarding write locks and other locks imposed on the extents stored in the memory, filtering the collection of lock information to ascertain write locked extents satisfying a predefined policy, and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy.

20. A computer program product as in claim 19 wherein the lock history database includes lock history records, each lock history record identifying a type of lock imposed on a range of extents;

and wherein filtering and building includes;

identifying, as the recently written extents, extents from records of write range locks involving host write operations to ranges of extents, and ignoring records of other types of range locks involving other types of operations on the ranges of extents.

21. A computer program product as in claim 19 wherein the predefined policy identifies (i) a predefined number of times as a write count, and (ii) a predefined amount of time;

and wherein filtering and building the recently written extent list based only on the ascertained write locked extents satisfying the predefined policy includes;

on the recently written extent list, (i) listing extents which were modified at least the predefined number of times within the predefined amount of time and (ii) not listing extents which were not modified at least the predefined number of times within the predefined amount of time.