Deduplicating storage with enhanced frequent-block detection

• US 9,767,140 B2
• Filed: 08/25/2015
• Issued: 09/19/2017
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chambliss, David D., Constantinescu, Mihail C., Glider, Joseph S., Lu, Maohua
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US14/835,268
• Publication Number:
  US 20150363457A1
• Time in Patent Office: 756 Days
• Field of Search: 707692, 711118, 711E12009
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

Detecting data duplication includes maintaining a fingerprint directory including one or more entries. Each entry includes a data fingerprint and a data location for a data chunk. A shadow list including a record of fingerprint values not contained in the fingerprint directory is maintained. Each entry is associated with a seen-count attribute, which is an indication of how often a data fingerprint has been seen in arriving data chunks to be written in a storage system, and distinguishes multiply-seen entries for data fingerprints present in at least two data chunks from once-seen entries for data fingerprints present in no more than a single data chunk. Each entry retrieved from the shadow list relates to twice-seen fingerprints.

Claims

1. A method for detecting data duplication, comprising:

maintaining a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk;

maintaining a shadow list comprising a record of fingerprint values removed from the fingerprint directory, wherein the shadow list comprises an allocation of resources with associated methods to insert fingerprints and to look up fingerprints, and to return a result of a lookup in the shadow list;

associating each said entry with a seen-count attribute which is an indication of how often a data fingerprint has been seen in arriving data chunks to be written in a storage system, and distinguishes multiply-seen entries for data fingerprints present in at least two data chunks from once-seen entries for data fingerprints present in no more than a single data chunk; and

retrieving entries from the shadow list such that each entry retrieved from the shadow list comprises twice-seen fingerprints.

2. The method of claim 1, wherein:

the shadow list does not retain storage locations, consumes less storage space per fingerprint value than the fingerprint directory and comprises a probabilistic set-object data structure.

3. The method of claim 1, further comprising:

performing a lookup in the shadow list for a particular fingerprint, wherein a return result of the lookup comprises a positive or negative result.

4. The method of claim 3, wherein:

a negative return result for the lookup means that the particular fingerprint was never inserted in the shadow list, was deleted after a last insertion in the shadow list, or was evicted after the last insertion in the shadow list; and

a positive return result for the lookup means that the particular fingerprint was inserted in the shadow list and was neither deleted nor evicted after it the last insertion in the shadow list, or the positive return result is an instance of an inaccurate positive return result.

5. The method of claim 1, further comprising:

depopulating specific entries from the shadow list based on at least one of;

age of entry, a random eviction, or an age-biased random eviction,

wherein depopulating specific entries is not specific to individual fingerprints, and reduces a number of fingerprint values for which a lookup in the shadow list would result in a positive return result.

6. The method of claim 1, wherein a policy is applied for distinguishing multiple seen-count categories based on tracking data access ages of entries in the fingerprint directory for different seen-count categories.

7. The method of claim 1, further comprising:

detecting that the data fingerprint for a new chunk is contained in the shadow list;

removing the data fingerprint for said new chunk from the shadow list; and

adding to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk,

wherein the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry.

8. The method of claim 1, further comprising:

retaining higher-frequency entries, while also taking into account recency of data accesses for the higher-frequency entries based on the seen-count attribute and the data access age.

9. A computer program product for detecting data duplication, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:

maintain, by the processor, a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk;

maintain, by the processor, a shadow list comprising a record of fingerprint values removed from the fingerprint directory, wherein the shadow list comprises an allocation of resources with associated methods to insert fingerprints and to look up fingerprints, and to return a result of a lookup in the shadow list;

associate, by the processor, each said entry with a seen-count attribute which is an indication of how often a data fingerprint has been seen in arriving data chunks to be written in a storage system, and distinguishes multiply-seen entries for data fingerprints present in at least two data chunks from once-seen entries for data fingerprints present in no more than a single data chunk; and

retrieve, by the processor, entries from the shadow list such that each entry retrieved from the shadow list comprises twice-seen fingerprints.

10. The computer program product of claim 9, wherein:

the shadow list does not retain storage locations, consumes less storage space per fingerprint value than the fingerprint directory and comprises a probabilistic set-object data structure.

11. The computer program product of claim 10, further comprising:

perform, by the processor, a lookup in the shadow list for a particular fingerprint, wherein a return result of the lookup comprises a positive or negative result; and

depopulate, by the processor, specific entries from the shadow list based on at least one of;

age of entry, a random eviction, or an age-biased random eviction,

wherein depopulating specific entries is not specific to individual fingerprints, and reduces a number of fingerprint values for which a lookup in the shadow list would result in a positive return result;

wherein;

a negative return result for the lookup means that the particular fingerprint was never inserted in the shadow list, was deleted after a last insertion in the shadow list, or was evicted after the last insertion in the shadow list; and

a positive return result for the lookup means that the particular fingerprint was inserted in the shadow list and was neither deleted nor evicted after it the last insertion in the shadow list, or the positive return result is an instance of an inaccurate positive return result.

12. The computer program product of claim 11, further comprising:

detecting that the data fingerprint for a new chunk is contained in the shadow list;

removing the data fingerprint for said new chunk from the shadow list;

adding to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk; and

retaining higher-frequency entries, while also taking into account recency of data accesses for the higher-frequency entries based on the seen-count attribute and the data access age;

wherein the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry, and a policy is applied for distinguishing multiple seen-count categories based on tracking data access ages of entries in the fingerprint directory for different seen-count categories.

13. A system for detecting data duplication, comprising:

a memory device;

a fingerprint controller coupled to the memory device, the fingerprint controller configured to;

maintain a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk, and

associate each said entry with a seen-count attribute which is an indication of how often a data fingerprint has been seen in arriving data chunks to be written in a storage system, and distinguishes multiply-seen entries for data fingerprints present in at least two data chunks from once-seen entries for data fingerprints present in no more than a single data chunk; and

a shadow list controller configured to maintain a shadow list comprising a record of fingerprint values removed from the fingerprint directory, and to retrieve entries from the shadow list such that each entry retrieved from the shadow list comprises twice-seen fingerprints, wherein the shadow list comprises an allocation of system resources with associated methods to insert fingerprints and to look up fingerprints, and to return a result of a lookup in the shadow list.

14. The system of claim 13, wherein:

the shadow list comprises a probabilistic set-object data structure, does not retain storage locations, and consumes less storage space per fingerprint value than the fingerprint directory.

15. The system of claim 13, wherein the shadow list controller is configured to perform a lookup in the shadow list for a particular fingerprint, and a return result of the lookup comprises a positive or negative result.

16. The system of claim 14, wherein:

a negative return result for the lookup means that the particular fingerprint was never inserted in the shadow list, was deleted after a last insertion in the shadow list, or was evicted after the last insertion in the shadow list; and

a positive return result for the lookup means that the particular fingerprint was inserted in the shadow list and was neither deleted nor evicted after the last insertion in the shadow list, or the positive return result is an instance of an inaccurate positive return result.

17. The system of claim 13, wherein:

the shadow list controller is configured to add to the shadow list the data fingerprint for a new chunk whose data fingerprint was not found in the fingerprint directory.

18. The system of claim 13, wherein the shadow list controller is configured to depopulate specific entries from the shadow list based on at least one of:

age of entry, a random eviction, or an age-biased random eviction, a depopulation of specific entries is not specific to individual fingerprints, and reduces a number of fingerprint values for which a lookup in the shadow list would result in a positive return result.

19. The system of claim 13, wherein the fingerprint controller is configured to apply a policy to distinguish multiple seen-count categories based on tracking data access ages of entries in the fingerprint directory for different seen-count categories.

20. The system of claim 13, wherein:

the fingerprint controller is configured to detect that the data fingerprint for a new chunk is contained in the shadow list;

the shadow list controller is configured to remove the data fingerprint for said new chunk from the shadow list;

the fingerprint controller is further configured to add to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk, the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry; and

the fingerprint controller is further configured to retain higher-frequency entries in the fingerprint directory, while also taking into account recency of data accesses for the higher-frequency entries based on the seen-count attribute and the data access age.