COMPATIBILITY AND INCLUSION OF SIMILARITY ELEMENT RESOLUTIONS

• US 20150019509A1
• Filed: 07/15/2013
• Published: 01/15/2015
• Est. Priority Date: 07/15/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ARONOVICH, Lior
• Granted Patent: US 10,133,502 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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 one resolution level for a chunk of input data;

using the input similarity elements of the one resolution level 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.

2. The method of claim 1, further including performing one of:

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

configuring the similarity elements of each 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 one resolution level.

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

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

5. The method of claim 4, 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.

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

7. The method of claim 6, further including performing one of:

calculating an aggregated deduplication ratio as a total size of portions of the input chunks covered by data matches out of the total size of the chunks, and

using the aggregated deduplication ratio to determine the resolution level of the input similarity elements.

8. The method of claim 7, further including performing one of:

decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and the average size of the sets of similarity element matches is not lower than two and the current resolution level is higher than the lowest resolution level; and

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.

9. 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 one resolution level for a chunk of input data, and

using the input similarity elements of the one resolution level 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.

10. The system of claim 9, wherein the at least one processor device that performs one of:

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

configuring the similarity elements of each 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 one resolution level.

11. The system of claim 10, 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 chunks of input data.

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

13. The system of claim 12, wherein the at least one processor device that 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.

14. The system of claim 12, wherein the at least one processor device that calculates an average size of the sets of similarity element matches, and using the average size to determine the resolution level of the input similarity elements.

15. The system of claim 14, wherein the at least one processor device that performs one of:

calculating an aggregated deduplication ratio as a total size of portions of the input chunks covered by data matches out of the total size of the chunks, and

using the aggregated deduplication ratio to determine the resolution level of the input similarity elements.

16. The system of claim 15, wherein the at least one processor device that performs one of:

decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and the average size of the sets of similarity element matches is not lower than two and the current resolution level is higher than the lowest resolution level; and

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.

17. 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 computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

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

a second executable portion that calculates input similarity elements in one resolution level for a chunk of input data; and

a third executable portion that uses the input similarity elements of the one resolution level 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.

18. The computer program product of claim 17, further including a fourth executable portion that performs one of:

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

configuring the similarity elements of each 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 one resolution level.

19. The computer program product of claim 17, further including a fourth executable portion that that calculates the similarity elements based on one of maximum values and minimum values of rolling hash values calculated for chunks of input data.

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

21. The computer program product of claim 20, further including a fifth 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.

22. The computer program product of claim 20, further including a fifth executable portion that that calculates an average size of the sets of similarity element matches, and using the average size to determine the resolution level of the input similarity elements.

23. The computer program product of claim 22, further including a sixth executable portion that that performs one of:

calculating an aggregated deduplication ratio as a total size of portions of the input chunks covered by data matches out of the total size of the chunks, and

using the aggregated deduplication ratio to determine the resolution level of the input similarity elements.

24. The computer program product of claim 22, further including a seventh executable portion that performs one of:

decreasing the similarity elements resolution level if the aggregated deduplication ratio is not lower than a predefined threshold and the average size of the sets of similarity element matches is not lower than two and the current resolution level is higher than the lowest resolution level; and

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.