REGION-INTEGRATED DATA DEDUPLICATION IMPLEMENTING A MULTI-LIFETIME DUPLICATE FINDER

• US 20170286444A1
• Filed: 03/29/2016
• Published: 10/05/2017
• 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
• Granted Patent: US 10,394,764 B2
• Time in Patent Office: Days
• 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; and

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.

2. 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 long term dictionary comprises the entry corresponding to the fingerprint, to repopulate the short term dictionary with the entry corresponding to the fingerprint.

3. The computer program product as recited in claim 2, 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 the region 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 region.

4. The computer program product as recited in claim 3, wherein the namespace comprises a plurality of regions 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 region to the long term dictionary.

5. 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 regions is a first address within the respective ordered set of addresses.

6. The computer program product as recited in claim 5, 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 region; and

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

7. The computer program product as recited in claim 1, wherein the namespace comprises a plurality of regions, each region having associated therewith at least one representative data chunk.

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.

9. The computer program product as recited in claim 8, comprising program instructions executable by the computer to cause the computer, 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.

10. The computer program product as recited in claim 1, wherein entries of the short term dictionary and entries of the long term dictionary each 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 entry corresponds.

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

12. 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 comprising less than 10% of the entries of the short term dictionary eligible for insertion into the long term dictionary.

13. The computer program product as recited in claim 12, 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.

14. The computer program product as recited in claim 1, wherein a duplicate chunk finder of the namespace comprises the short term dictionary and the long term dictionary, the duplicate chunk finder being configured to determine whether the short term dictionary and/or the long term dictionary comprise the entry corresponding to the fingerprint.

15. The computer program product as recited in claim 14, wherein the duplicate chunk finder comprises a permanent dictionary comprising one entry per region of the namespace and the permanent dictionary being configured to permanently retain valid entries.

16. The computer program product as recited in claim 15, comprising program instructions executable by the computer to cause the computer, in response to determining the long term 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.

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

and

the computer program product comprising 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 a region of the entry corresponding to the fingerprint.

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

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

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.

20. 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 and/or 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

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.