Region-integrated data deduplication implementing a multi-lifetime duplicate finder

• US 10,394,764 B2
• Filed: 03/29/2016
• Issued: 08/27/2019
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chambliss, David D., Glider, Joseph S., Harnik, Danny, Khaitzin, Ety
• Primary Examiner(s): Savla, Arpan P.
• Assistant Examiner(s): Vo, Cecile H
• Application Number:
  US15/084,413
• Publication Number:
  US 20170286444A1
• Time in Patent Office: 1,246 Days
• Field of Search: 711E12001, 711E12009, 711E12058, 711162, 711170, 711207, 711216, 707711, 707758, 707E17002, 707E17044, 707634, 707638, 707640, 707679, 707708, 707736, 707737, 707780, 707781, 707812
• 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 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

Computer program products, as well as corresponding systems and methods are configured for performing deduplication in conjunction with random read and write operations, and include: receiving a write request comprising data; computing a fingerprint of the data; determining whether a short term dictionary comprises an entry corresponding to the fingerprint; in response to determining the short term dictionary comprises the entry corresponding to the fingerprint, writing the data to a data store in a deduplicating manner; in response to determining the short term dictionary does not comprise the entry, determining whether a long term dictionary corresponding to the namespace comprises the entry; in response to determining the long term dictionary comprises the entry, writing the data to the data store in the deduplicating manner; and in response to determining the long term dictionary does not comprise the entry, writing the data to the data store in a non-deduplicating manner.

Claims

1. A computer program product for performing deduplication in conjunction with random read and write operations across a namespace, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a computer to cause the computer to perform a method comprising:

receiving, at the computer, a write request comprising a data chunk;

computing, by the computer, a fingerprint of the data chunk;

determining, by the computer, whether a short term dictionary corresponding to the namespace comprises an entry corresponding to the fingerprint;

in response to determining the short term dictionary comprises the entry corresponding to the fingerprint, writing, by the computer, the data chunk to a data store corresponding to the namespace in a deduplicating manner;

in response to determining the short term dictionary does not comprise the entry corresponding to the fingerprint, determining, by the computer, whether a long term dictionary corresponding to the namespace comprises the entry corresponding to the fingerprint;

in response to determining the long term dictionary comprises the entry corresponding to the fingerprint, writing, by the computer the data chunk to the data store in the deduplicating manner;

in response to determining the long term dictionary does not comprise the entry corresponding to the fingerprint, writing, by the computer, the data chunk to the data store in a non-deduplicating manner; and

in response to determining the long term dictionary comprises the entry corresponding to the fingerprint, repopulating the short term dictionary with the entry corresponding to the fingerprint,

wherein the short term dictionary comprises a first eviction policy,

wherein the long term dictionary comprises a second eviction policy,

wherein the first eviction policy is configured to evict one or more entries of the short term dictionary in response to a new entry being inserted into the short term dictionary, and

wherein the second eviction policy is configured to evict one or more entries of the long term dictionary in response to a new entry being inserted into the long term dictionary.

2. The computer program product as recited in claim 1,

wherein the namespace comprises a plurality of regions;

wherein the repopulating comprises adding a plurality of entries each corresponding to a data chunk associated with one of the plurality of regions to the short term dictionary; and

wherein the data chunks to which the plurality of entries correspond comprise substantially all data chunks associated with the one of the plurality of regions.

3. The computer program product as recited in claim 2, wherein the plurality of regions are organized according to a predetermined hierarchy;

and

wherein the repopulating comprises adding a plurality of entries each corresponding to a data chunk associated with the one of the plurality of regions to the long term dictionary.

4. The computer program product as recited in claim 1, wherein the namespace comprises a plurality of regions, each region corresponding to one or more logical addresses, and at least one of the regions corresponding to a respective ordered set of addresses, where a representative address for each of the at least one of the regions is a first address within the respective ordered set of addresses.

5. The computer program product as recited in claim 4, comprising program instructions executable by the computer to cause the computer, in response to determining:

the long term dictionary comprises the entry corresponding to the fingerprint; and

the write request is associated with one or more sequential write requests, to repopulate the short term dictionary with a plurality of entries each corresponding to a data chunk associated with the at least one of the regions; and

wherein the plurality of entries correspond to a plurality of data chunks associated with the at least one of the regions and characterized by a sequential progression of logical addresses in the ordered set of addresses corresponding to the at least one of the regions.

6. The computer program product as recited in claim 1, comprising program instructions executable by the computer to cause the computer, in response to determining:

the short term dictionary comprises the entry corresponding to the fingerprint, the long term dictionary comprises the entry corresponding to the fingerprint, or the short term dictionary comprises the entry corresponding to the fingerprint and the long term dictionary comprises the entry corresponding to the fingerprint;

designating the write request a first duplicate write associated with a first prior write; and

repopulating the short term dictionary with a group of entries corresponding to a plurality of prior writes.

7. The computer program product as recited in claim 6, wherein the first duplicate write and each of the plurality of prior writes are proximate to each other with respect to:

write time, virtual address, or write time and virtual address.

8. The computer program product as recited in claim 1, comprising program instructions executable by the computer to cause the computer, in response to writing the data chunk to the data store of the namespace in the non-deduplicating manner, to determine whether the data chunk is representative of one or more regions of the namespace;

and

in response to determining the data chunk is representative of the one or more regions of the namespace, to create an entry in the long term dictionary corresponding to the data chunk.

9. The computer program product as recited in claim 1, wherein entries of the short term dictionary and entries of the long term dictionary each independently comprise a fingerprint associated with a physical location of the data store, the physical location of the data store being the physical location of the data chunk to which the respective entry corresponds.

10. The computer program product as recited in claim 1, wherein each of the short term dictionary and the long term dictionary comprise a data structure selected from a group consisting of:

a simple hash table in one compute node;

a partitioned set of hash tables distributed over multiple nodes;

a set of lists addressed through a local or distributed hash table;

a chain of separate sub-dictionaries; and

a map of separate sub-dictionaries associated with distinct contexts.

11. The computer program product as recited in claim 1, comprising program instructions executable by the computer to cause the computer to insert a limited fraction of entries from the short term dictionary into the long term dictionary based on a predefined insertion policy, the limited fraction of entries inserted into the long term dictionary comprising less than 10% of the entries of the short term dictionary eligible for insertion into the long term dictionary;

and

wherein each of the limited fraction of entries are determined based at least in part on a virtual address of the data chunk to which the entry corresponds.

12. The computer program product as recited in claim 1, wherein a duplicate chunk finder comprises the short term dictionary and the long term dictionary, the duplicate chunk finder being configured to determine:

whether the short term dictionary comprises the entry corresponding to the fingerprint, whether the long term dictionary comprises the entry corresponding to the fingerprint, or whether the short term dictionary comprises the entry corresponding to the fingerprint and the long term dictionary comprises the entry corresponding to the fingerprint;

wherein the duplicate chunk finder comprises a permanent dictionary comprising one entry per region of the namespace, the permanent dictionary being configured to permanently retain valid entries; and

wherein the computer program product comprises program instructions executable by the computer to cause the computer, in response to determining the long term dictionary does not comprise the entry corresponding to the fingerprint, to determine whether the permanent dictionary comprises an entry corresponding to the fingerprint rather than writing the data chunk to the data store of the namespace in the non-deduplicating manner.

13. The computer program product as recited in claim 12, wherein the namespace comprises a plurality of regions;

and

wherein the computer program product comprises program instructions executable by the computer to cause the computer, in response to determining the permanent dictionary comprises the entry corresponding to the fingerprint, to repopulate the short term dictionary with;

the entry corresponding to the fingerprint; and

a plurality of entries associated with the entry corresponding to the fingerprint.

14. The computer program product as recited in claim 1, wherein evicted entries are chosen by the first eviction policy and the second eviction policy based at least in part on:

whether the one or more entries have previously been detected as a prior for a duplicate write to the namespace; and

a recency with which the one or more entries have previously been detected as the prior for the duplicate write to the namespace.

15. The computer program product as recited in claim 1, wherein the namespace is divided into a plurality of non-overlapping regions according to one or more proximity criteria.

16. The computer program product as recited in claim 1, wherein the first eviction policy is invoked in response to determining a number of vacancies in the short term dictionary is less than a predetermined minimum vacancy threshold;

and

wherein the second eviction policy is invoked in response to determining a number of vacancies in the long term dictionary is less than the predetermined minimum vacancy threshold.

17. The computer program product as recited in claim 1, wherein each entry in the short term dictionary is associated with a first lifetime parameter configured to enforce an age distribution among all entries in the short term dictionary;

and

wherein each entry in the long term dictionary is associated with a second lifetime parameter configured to enforce an age distribution among all entries in the long term dictionary.

18. A computer-implemented method for performing deduplication in conjunction with random read and write operations across a namespace, the method comprising:

receiving a write request comprising a data chunk;

computing a fingerprint of the data chunk;

determining whether a short term dictionary corresponding to the namespace comprises an entry corresponding to the fingerprint;

in response to determining the short term dictionary comprises the entry corresponding to the fingerprint, writing the data chunk to a data store corresponding to the namespace in a deduplicating manner;

in response to determining the short term dictionary does not comprise the entry corresponding to the fingerprint, determining whether a long term dictionary corresponding to the namespace comprises the entry corresponding to the fingerprint;

in response to determining the long term dictionary comprises the entry corresponding to the fingerprint;

writing the data chunk to the data store in the deduplicating manner; and

repopulating the short term dictionary with the entry corresponding to the fingerprint; and

in response to determining the long term dictionary does not comprise the entry corresponding to the fingerprint, writing the data chunk to the data store in a non-deduplicating manner,

wherein the short term dictionary comprises a first eviction policy,

wherein the long term dictionary comprises a second eviction policy,

wherein the first eviction policy is configured to evict one or more entries of the short term dictionary in response to a new entry being inserted into the short term dictionary, and

wherein the second eviction policy is configured to evict one or more entries of the long term dictionary in response to a new entry being inserted into the long term dictionary.

19. A deduplicating storage system configured to perform deduplication in conjunction with random read and write operations across a namespace, the system comprising:

a processor and logic integrated with the processor, executable by the processor, or integrated with and executable by the processor, the logic being configured to cause the processor to perform a method comprising;

receiving a write request comprising a data chunk;

computing a fingerprint of the data chunk;

determining whether a short term dictionary corresponding to the namespace comprises an entry corresponding to the fingerprint;

in response to determining the short term dictionary comprises the entry corresponding to the fingerprint, writing the data chunk to a data store corresponding to the namespace in a deduplicating manner;

in response to determining the short term dictionary does not comprise the entry corresponding to the fingerprint, determining whether a long term dictionary corresponding to the namespace comprises the entry corresponding to the fingerprint;

in response to determining the long term dictionary comprises the entry corresponding to the fingerprint;

writing the data chunk to the data store in the deduplicating manner; and

repopulating the short term dictionary with the entry corresponding to the fingerprint; and

in response to determining the long term dictionary does not comprise the entry corresponding to the fingerprint, writing the data chunk to the data store in a non-deduplicating manner,

wherein the short term dictionary comprises a first eviction policy,

wherein the long term dictionary comprises a second eviction policy,

wherein the first eviction policy is configured to evict one or more entries of the short term dictionary in response to a new entry being inserted into the short term dictionary, and

wherein the second eviction policy is configured to evict one or more entries of the long term dictionary in response to a new entry being inserted into the long term dictionary.