# US 2017/0286444 A1 · Region-integrated data deduplication implementing a multi-lifetime duplicate finder

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0286444 A1
- Document ID: US20170286444A1
- Status: Published application
- Kind: A1
- Application number: 15/084,413
- Filed: 2016-03-29
- Published: 2017-10-05
- Earliest claimed: 2016-03-29
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: David D. Chambliss; Joseph S. Glider; Danny Harnik; Ety Khaitzin
- Web page: https://patentgrep.com/patent/US20170286444A1

## CPC

- G06F 16/1752: {based on file chunks}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 1)

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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 1)

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.

### Claim 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.

### Claim 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.
