Efficient calculation of similarity search values and digest block boundaries for data deduplication

Patent metadata

Field	Value
Publication number	US-9600515-B2
Application number	US-201514970740-A
Country	US
Kind code	B2
Filing date	Dec 16, 2015
Priority date	Mar 15, 2013
Publication date	Mar 21, 2017
Grant date	Mar 21, 2017

Abstract

For efficient calculation of both similarity search values and boundaries of digest blocks in data deduplication, input data is partitioned into chunks, and for each chunk a set of rolling hash values is calculated. A single linear scan of the rolling hash values is used to produce both similarity search values and boundaries of the digest blocks of the chunk. The rolling hash values are used to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

First claim

What is claimed is:

1. A method for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system using a processor device in a computing environment, comprising:
partitioning input data into data chunks;
calculating a set of rolling hash values for each of the data chunks;
using a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks; and
using each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

2. The method of claim 1 , further including discarding each of the rolling hash values after contributing to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

3. The method of claim 1 , further including corresponding each of the rolling hash values to a consecutive window of bytes in byte offsets.

4. The method of claim 1 , further including using the similarity search values to search for data similar to the input data in a repository of data.

5. The method of claim 1 , further including using the boundaries of the digest blocks to calculate digest values for each of the data chunks for digests matching.

6. The method of claim 1 , further including partitioning the input data into fixed sized data chunks.

7. A system for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system of a computing environment, the system comprising:
the data deduplication system;
a repository in the computing environment in communication with the data deduplication system;
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 data chunks,
calculates a set of rolling hash values for each of the data chunks,
uses a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks, and
uses each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

8. The system of claim 7 , wherein the at least one processor device discards each of the rolling hash values after contributing to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

9. The system of claim 7 , wherein the at least one processor device corresponds each of the rolling hash values to a consecutive window of bytes in byte offsets.

10. The system of claim 7 , wherein the at least one processor device uses the similarity search values to search for data similar to the input data in the repository of data.

11. The system of claim 7 , wherein the at least one processor device uses the boundaries of the digest blocks to calculate digest values for each of the data chunks for digests matching.

12. The system of claim 7 , wherein the at least one processor device the input data into fixed sized data chunks.

13. A computer program product for efficient calculation of both similarity search values and boundaries of digest blocks in a data deduplication system using a processor device in a computing environment, the computer program product comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
an executable portion that partitions input data into data chunks;
an executable portion that calculates a set of rolling hash values for each of the data chunks;
an executable portion that uses a single linear scan of the rolling hash values for producing both the similarity search values and the boundaries of the digest blocks; and
an executable portion that uses each of the rolling hash values to contribute to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

14. The computer program product of claim 13 , further including an executable portion that discards each of the rolling hash values after contributing to the calculation of the similarity search values and to the calculation of the boundaries of the digest blocks.

15. The computer program product of claim 13 , further including an executable portion that corresponds each of the rolling hash values to a consecutive window of bytes in byte offsets.

16. The computer program product of claim 13 , further including an executable portion that uses the similarity search values to search for data similar to the input data in a repository of data.

17. The computer program product of claim 13 , further including an executable portion that uses the boundaries of the digest blocks to calculate digest values for each of the data chunks for digests matching.

18. The computer program product of claim 13 , further including an executable portion that partitions the input data into fixed sized data chunks.

Assignees

• IBM

Inventors

• Akirav Shay H
• Aronovich Lior
• Ben-Dor Shira
• Hirsch Michael
• Leneman Ofer

Classifications

• G06F17/30867

  Physics · mapped topic

• G06F17/30156

  Physics · mapped topic

• G06F17/30371 Primary

  Physics · mapped topic

• G06F17/30159

  Physics · mapped topic

• G06F17/30522

  Physics · mapped topic