Utilizing global digests caching in similarity based data deduplication

Patent metadata

Field	Value
Publication number	US-9891857-B2
Application number	US-201313941742-A
Country	US
Kind code	B2
Filing date	Jul 15, 2013
Priority date	Jul 15, 2013
Publication date	Feb 13, 2018
Grant date	Feb 13, 2018

Abstract

Input data is partitioned into data chunks and digest values are calculated for each of the data chunks. The positions of similar repository data are found in a repository of data for each of the data chunks. The repository digests of the similar repository data are located and loaded into the global digests cache. The global digests cache contains digests previously loaded by other deduplication processes. The input digests of the input data are matched with the repository digests contained in the global digests cache for locating data matches. The processor prefers to match the input digests of the input data with the repository digests contained in the global digests cache which are of the similar repository data, rather than repository digests which are of other repository data that was not determined as similar to the input data chunks.

First claim

What is claimed is:

1. A method for utilizing a global digests cache in similarity based data deduplication in a data deduplication system using a processor device in a computing environment, comprising:
partitioning input data into input data chunks, each of the input data chunks having a size of at least 16 Megabytes (MB);
calculating input digest values for each of the input data chunks;
finding positions of similar repository data in a repository of data for each of the input data chunks;
locating and loading repository digests of the similar repository data into the global digests cache, wherein the global digests cache contains, prior to the loading of the repository digests of the similar repository data, at least a plurality of digests previously loaded by a plurality of deduplication processes;
matching input digests of the input data and the repository digests contained in the global digests cache for locating data matches;
preferring to match the input digests of the input data with the repository digests contained in the global digests cache which are of the similar repository data, rather than repository digests which are of other repository data that was not determined as similar to the input data chunks; and
using the positions of the similar repository data to locate and linearly load into the global digests cache, digests and digest block boundaries of the similar repository data in a sequence corresponding to a placement order of calculated values of the digests of the similar repository data, the placement order of the calculated values of the digests of the similar repository data correlative to an order in which the input digest values were individually calculated such that the digests of the similar repository data are each individually stored in the global digests cache based on a calculation time and order of when each of the input digests were first calculated when in un-deduplicated form, thereby storing the digests of the similar repository data in a linear and sequential form independent of a deduplicated form by which data the digests describe is stored, wherein the global digest cache comprises a pool of a plurality of sequential arrays of digest entries of the digests and a hash table for pointing to contents within the plurality of sequential arrays.

2. The method of claim 1 , wherein the global digests cache contains the plurality of digests previously loaded by the plurality of deduplication processes.

3. The method of claim 2 , further including reusing at least one of the plurality of sequential arrays of digest entries of the global digests cache according to a least recently used (LRU) policy.

4. The method of claim 3 , further including applying the LRU policy on the plurality of sequential arrays of digest entries of the digest entries of the plurality of digests in the global digests cache.

5. The method of claim 4 , further including searching for the input digests by considering both the plurality of digests previously loaded by the plurality of deduplication processes and the digests of the similar repository data currently loaded into the global digests cache.

6. The method of claim 1 , further including performing one of:
calculating similarity values for each of the input data chunks,
searching for matching similarity values in a search structure containing the similarity values, and
matching the digest values of the input data with the repository digest values of the repository digests loaded into the global digests cache for locating the data matches.

7. The method of claim 1 , further including matching input digests of the input data and repository digests contained in the global digests cache for finding data matches if the search for the similar repository data in the repository finds the similar repository data.

8. A system for utilizing a global digests cache in similarity based data deduplication in a data deduplication system of a computing environment, the system comprising:
the data deduplication system;
the global digests cache in association with the data deduplication system;
a repository operating in the data deduplication system in communication with the global digests cache; and
at least one processor device operable in the computing storage environment for controlling the data deduplication system, wherein the at least one processor device:
partitions input data into input data chunks, each of the input data chunks having a size of at least 16 Megabytes (MB),
calculates input digest values for each of the input data chunks,
finds positions of similar repository data in a repository of data for each of the input data chunks,
locates and loads repository digests of the similar repository data into the global digests cache, wherein the global digests cache contains, prior to the loading of the repository digests of the similar repository data, at least a plurality of digests previously loaded by a plurality of deduplication processes,
matching input digests of the input data and the repository digests contained in the global digests cache for locating data matches,
prefers to match the input digests of the input data with the repository digests contained in the global digests cache which are of the similar repository data, rather than repository digests which are of other repository data that was not determined as similar to the input data chunks, and
uses the positions of the similar repository data to locate and linearly load into the global digests cache, digests and digest block boundaries of the similar repository data in a sequence corresponding to a placement order of calculated values of the digests of the similar repository data, the placement order of the calculated values of the digests of the similar repository data correlative to an order in which the input digest values were individually calculated such that the digests of the similar repository data are each individually stored in the global digests cache based on a calculation time and order of when each of the input digests were first calculated when in un-deduplicated form, thereby storing the digests of the similar repository data in a linear and sequential form independent of a deduplicated form by which data the digests describe is stored, wherein the global digest cache comprises a pool of a plurality of sequential arrays of digest entries of the digests and a hash table for pointing to contents within the plurality of sequential arrays.

9. The system of claim 8 , wherein the global digests cache contains the plurality of digests previously loaded by the plurality of deduplication processes.

10. The system of claim 9 , wherein the at least one processor device reuses at least one of the plurality of sequential arrays of digest entries of the global digests cache according to a least recently used (LRU) policy.

11. The system of claim 10 , wherein the at least one processor device applies the LRU policy on the plurality of sequential arrays of digest entries of the digest entries of the plurality of digests in the global digests cache.

12. The system of claim 11 , wherein the at least one processor device searches for the input digests by considering both the plurality of digests previously loaded by the plurality of deduplication processes and the digests of the similar repository data currently loaded into the global digests cache within a time window reflected by the global digests cache, wherein the global digests cache reflects a window of time backwards from a current time.

13. The system of claim 8 , wherein the at least one processor device performs one of:
calculating similarity values for each of the

Assignees

• IBM

Inventors

• Akirav Shay H
• Aronovich Lior

Classifications

• G06F12/0848 Primary

  Partitioned cache, e.g. separate instruction and operand caches · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F12/0875

  with dedicated cache, e.g. instruction or stack · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title