Compatibility and inclusion of similarity element resolutions

• US 10,133,502 B2
• Filed: 07/15/2013
• Issued: 11/20/2018
• Est. Priority Date: 07/15/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aronovich, Lior
• Primary Examiner(s): Kerzhner, Aleksandr
• Assistant Examiner(s): Cheung, Eddy
• Application Number:
  US13/941,999
• Publication Number:
  US 20150019509A1
• Time in Patent Office: 1,954 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

For adaptive similarity search resolution in a data deduplication system using a processor device in a computing environment, multiple resolution levels are configured for a similarity search. Input similarity elements are calculated in one resolution level for a chunk of input data. The input similarity elements of the one resolution level are used to find similar data in a repository of data where similarity elements of the stored similar repository data are of the multiple resolution levels.

Claims

1. A method for adaptive similarity search using compatibility and inclusion of similarity element resolutions in a data deduplication system using a processor device in a computing environment, comprising:

configuring a plurality of resolution levels for a similarity search;

calculating input similarity elements in a certain one of the plurality of resolution levels for a chunk of input data, wherein each resolution level is determined by identifying a number of the input similarity elements calculated in relation to a size of the chunk of input data;

using the input similarity elements of the certain one of the plurality of resolution levels to find similar data in a repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels, for locating and reducing duplicate data within the data deduplication system;

defining the plurality of resolution levels to be between a highest resolution level and a lowest resolution level;

configuring the similarity elements of each one of the plurality of resolution levels which are lower than the certain one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the certain one of the plurality of resolution levels;

calculating an aggregated deduplication ratio as a total size of input chunks of data received over a certain time period covered by matches with repository data out of the total size of the input chunks relative to a total size of output data subsequent to deduplicating all of the input chunks of data received over the certain time period; and

using the aggregated deduplication ratio to determine the resolution level of the input similarity elements by decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and an average size of calculated sets of similarity element matches is not lower than two and a current resolution level is higher than the lowest resolution level.

2. The method of claim 1, further including calculating the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for the input chunks.

3. The method of claim 1, further including calculating a resolution level for the similarity elements of an input chunk based on the calculated sets of similarity element matches and on a calculated deduplication ratio.

4. The method of claim 3, further including storing the input similarity elements in the calculated resolution level in a similarity search structure, and using the similarity search structure to find similarity elements of similar repository data.

5. The method of claim 3, further including calculating the average size of the sets of similarity element matches, and using the average size to determine the resolution level of the input similarity elements.

6. The method of claim 5, further including

increasing the similarity elements resolution level if the aggregated deduplication ratio is lower than a predefined threshold and the current resolution level is lower than the highest resolution level.

7. A system for adaptive similarity search using compatibility and inclusion of similarity element resolutions in a data deduplication system of a computing environment, the system comprising:

the data deduplication system;

a repository operating in the data deduplication system;

a memory in the data deduplication system;

a similarity search structure in association with the memory in the data deduplication system; 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;

configuring a plurality of resolution levels for a similarity search,

calculating input similarity elements in a certain one resolution of the plurality of levels for a chunk of input data, wherein each resolution level is determined by identifying a number of the input similarity elements calculated in relation to a size of the chunk of input data,

using the input similarity elements of the certain one of the plurality of resolution levels to find similar data in the repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels, for locating and reducing duplicate data within the data deduplication system,

defining the plurality of resolution levels to be between a highest resolution level and a lowest resolution level,

configuring the similarity elements of each one of the plurality of resolution levels which are lower than the certain one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the certain one of the plurality of resolution levels,

calculating an aggregated deduplication ratio as a total size of input chunks of data received over a certain time period covered by matches with repository data out of the total size of the input chunks relative to a total size of output data subsequent to deduplicating all of the input chunks of data received over the certain time period; and

using the aggregated deduplication ratio to determine the resolution level of the input similarity elements by decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and an average size of calculated sets of similarity element matches is not lower than two and a current resolution level is higher than the lowest resolution level.

8. The system of claim 7, wherein the at least one processor device that calculates the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for the input chunks.

9. The system of claim 7, wherein the at least one processor device calculates a resolution level for the similarity elements of an input chunk based on the calculated sets of similarity element matches and on a calculated deduplication ratio.

10. The system of claim 9, wherein the at least one processor device stores the input similarity elements in the calculated resolution level in the similarity search structure, and using the similarity search structure to find similarity elements of similar repository data.

11. The system of claim 9, wherein the at least one processor device calculates the average size of the sets of similarity element matches, and uses the average size to determine the resolution level of the input similarity elements.

12. The system of claim 11, wherein the at least one processor device that

increases the similarity elements resolution level if the aggregated deduplication ratio is lower than a predefined threshold and the current resolution level is lower than the highest resolution level.

13. A computer program product for adaptive similarity search using compatibility and inclusion of similarity element resolutions in a data deduplication system using a processor device in a computing environment, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

an executable portion that configures a plurality of resolution levels for a similarity search;

an executable portion that calculates input similarity elements in a certain one of the plurality of resolution levels for a chunk of input data, wherein each resolution level is determined by identifying a number of the input similarity elements calculated in relation to a size of the chunk of input data;

an executable portion that uses the input similarity elements of the certain one of the plurality of resolution levels to find similar data in a repository of data where similarity elements of the stored similar repository data are of the plurality of resolution levels, for locating and reducing duplicate data within the data deduplication system;

an executable portion that defines the plurality of resolution levels to be between a highest resolution level and a lowest resolution level;

an executable portion that configures the similarity elements of each one of the plurality of resolution levels which are lower than the certain one of the plurality of resolution levels to be a subset of the similarity elements of each one of the plurality of resolution levels which are higher than the certain one of the plurality of resolution levels;

an executable portion that calculates an aggregated deduplication ratio as a total size of input chunks of data received over a certain time period covered by matches with repository data out of the total size of the input chunks relative to a total size of output data subsequent to deduplicating all of the input chunks of data received over the certain time period; and

an executable portion that uses the aggregated deduplication ratio to determine the resolution level of the input similarity elements by decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and an average size of calculated sets of similarity element matches is not lower than two and a current resolution level is higher than the lowest resolution level.

14. The computer program product of claim 13, further including an executable portion that that calculates the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for the input chunks.

15. The computer program product of claim 13, further including an executable portion that that calculates a resolution level for the similarity elements of an input chunk based on the calculated sets of similarity element matches and on a calculated deduplication ratio.

16. The computer program product of claim 15, further including an executable portion that that stores the input similarity elements in the calculated resolution level in a similarity search structure, and using the similarity search structure to find similarity elements of similar repository data.

17. The computer program product of claim 15, further including an executable portion that that calculates the average size of the sets of similarity element matches, and uses the average size to determine the resolution level of the input similarity elements.

18. The computer program product of claim 17, further including an executable portion that

increases the similarity elements resolution level if the aggregated deduplication ratio is lower than a predefined threshold and the current resolution level is lower than the highest resolution level.