Systems and methods for efficient data searching, storage and reduction

• US 10,282,257 B2
• Filed: 07/25/2016
• Issued: 05/07/2019
• Est. Priority Date: 09/15/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aronovich, Lior, Asher, Ron, Bachmat, Eitan, Bitner, Haim, Hirsch, Michael, Klein, Shmuel T.
• Primary Examiner(s): Willoughby, Alicia M
• Application Number:
  US15/219,127
• Publication Number:
  US 20160335285A1
• Time in Patent Office: 1,016 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A computer program product for searching a repository of binary uninterpretted data, according to one embodiment, includes a computer readable storage medium having program instructions executable by a computer to cause the computer to perform a method comprising: analyzing, by the computer, segments of each of the repository and input data to determine a repository segment that is similar to an input segment, the analyzing including searching an index of representation values of the repository data for matching representation values of the input in a time independent of a size of the repository and linear in a size of the input data; and analyzing, by the computer, the similar repository segment with respect to the input segment to determine their common data sections while utilizing at least some of the matching representation values for data alignment, in a time linear in a size of the input segment.

Claims

1. A computer program product for searching a data storage system repository of binary uninterpretted data for a location of common data to an input data, the computer program product comprising a computer readable storage medium having program instructions executable by a processor to cause the processor to perform a method comprising:

analyzing, by the processor, segments of each of the repository and input data to determine a repository segment that is similar to an input segment, wherein the analyzing the segments includes;

searching an index of repository representation values for representation values which match input representation values, wherein the searching the index is performed in an amount of time which is independent of a size of the repository and which is linear in a size of the input data; and

specifying locations in the repository and input data of distinguishing characteristics corresponding to the matching representation values as matched values, wherein the amount of time which the searching the index is performed reduces an amount of processing time consumed by the processor during the searching and the specifying; and

analyzing, by the processor, the similar repository segment with respect to the input segment to determine their common data sections, wherein at least some of the matching representation values are utilized for data alignment, wherein the analyzing is performed in an amount of time which is linear in a size of the input segment.

2. The computer program product of claim 1, wherein the analyzing the segments includes:

determining whether a number of matched values is in a range; and

identifying a repository segment corresponding to the matched values as the similar repository segment with respect to the input segment in response to determining that the number of matched values is in a range,

wherein the index is stored in a memory faster than a memory storing the repository itself, wherein the searching involves only the faster memory, wherein the index is stored in RAM.

3. The computer program product of claim 1, wherein the program instructions are executable by the processor to cause the processor to perform the method comprising:

managing a storage location of each of the repository segments based on a number of references made to each of the repository segments,

wherein managing the storage location of each of the repository segments includes;

storing a subset of the repository segments which are most referenced on a magnetic disk; and

storing a subset of the repository segments which are least referenced on a magnetic tape.

4. The computer program product of claim 1, wherein analyzing the similar repository segment with respect to the input segment to determine their common data sections includes:

identifying data which is uncommon between the similar repository segment and the input segment, wherein identifying the data which is uncommon between the similar repository segment and the input segment reduces an effective size of the input segment,

wherein the program instructions are executable by the processor to cause the processor to perform the method comprising;

storing the uncommon data, wherein the reduced effective size of the input segment reduces an amount of memory consumed during the storing.

5. The computer program product of claim 4, wherein identifying data which is uncommon between the similar repository segment and the input includes:

determining one or more exact differences between the similar repository and input segments by comparing the full data of the respective segments using a binary difference algorithm and/or a byte-wise factoring algorithm,

wherein the representation values are such that a number of matches indicates a degree of similarity.

6. The computer program product of claim 1, wherein the similarity searching includes a threshold number of matching representation values for a declared similarity.

7. The computer program product of claim 6, wherein the threshold varies in response to a statistical analysis of prior results of the searching.

8. The computer program product of claim 1, wherein the repository representation values are determined by:

applying a modular hash function to each of the segments of the repository to generate a plurality of hashes, each of the hashes including a hash value and a hash position in the respective segment of the repository;

applying a first function to the plurality of generated hash values of the hashes to identify a first subset of hashes;

applying a second function to the hash positions of the hashes of the first subset to identify a second subset of the plurality of generated hashes; and

defining the second subset of hashes as the repository representation values.

9. The computer program product of claim 8, wherein applying the first function includes:

selecting a number of the largest hash values and/or selecting a number of the smallest hash values, wherein applying the second function includes;

determining other hash positions as a function of the hash positions of the hashes of the first subset; and

identifying the hashes at the other hash positions as the second subset of hashes.

10. The computer program product of claim 1, wherein the index includes a location within the repository of the similarity matched portion.

11. The computer program product of claim 1, wherein the processor includes:

a central processing unit; and

an input/output module,

wherein the input/output module includes a hard drive and/or an optical drive,

wherein the input/output module includes a network interface.

12. A computer program product for searching a data storage system repository of binary uninterpretted data for a location of common data to an input data, the computer program product comprising a computer readable storage medium having program instructions executable by a processor to cause the processor to perform a method comprising:

analyzing, by the processor, segments of each of the repository and input data to determine a repository segment that is similar to an input segment, wherein the analyzing includes;

searching an index of repository representation values for representation values which match input representation values, wherein the searching the index is performed in an amount of time which is independent of a size of the repository and which is linear in a size of the input data; and

specifying locations in the repository and input data of distinguishing characteristics corresponding to the matching representation values as matched values, wherein the amount of time which the searching the index is performed reduces an amount of processing time consumed by the processor during the searching and the specifying; and

analyzing, by the processor, the similar repository segment with respect to the input segment to determine their common data sections, wherein the specified locations are utilized for data alignment, wherein the analyzing is performed in an amount of time which is linear in a size of the input segment; and

using the determined common data sections to align the similar repository and input segments.

13. The computer program product of claim 12, the program instructions executable by the processor to cause the processor to perform the method comprising:

defining data intervals in each of the repository and input data based on the specified locations.

14. The computer program product of claim 12, wherein the processor includes:

a central processing unit; and

an input/output module,

wherein the input/output module includes a hard drive and/or an optical drive,

wherein the input/output module includes a network interface.

15. The computer program product of claim 13, wherein analyzing the similar repository segment with respect to the input segment to determine their common data section includes:

identifying data which is uncommon between the similar repository segment and the input segment by performing a binary difference process on the defined intervals, wherein sliding windows of the difference process for each of the repository and input data are at least sometimes positioned in non-matching offsets, wherein identifying the data which is uncommon between the similar repository segment and the input segment reduces an effective size of the input segment,

wherein the program instructions are executable by the processor to cause the processor to perform the method comprising;

storing the uncommon data, wherein the reduced effective size of the input segment reduces an amount of memory consumed during the storing.

16. The computer program product of claim 13, wherein the data intervals defined for the repository data are of a different size than the data interval defined for the input data.

17. The computer program product of claim 16, wherein the data intervals defined for one of the repository data and the input data is one byte, while the data intervals for the other of the repository data and the input data is multiple bytes.

18. The computer program product of claim 16, wherein the index is stored in a memory faster than a memory storing the repository itself, wherein the similarity searching includes a threshold number of matching representation values for a declared similarity, wherein the threshold varies in response to a statistical analysis of prior results of the searching.

19. A data storage system comprising:

magnetic disk;

magnetic tape;

a repository of binary uninterpretted data, wherein the repository data is stored on the magnetic disk and/or the magnetic tape; and

a processor;

wherein the processor is configured to perform a method of searching for a location of repository data which is common to input data, the method comprising;

analyzing, by the processor, segments of each of the repository data and the input data to determine a repository segment that is similar to an input segment, wherein the analyzing the segment includes;

searching an index of repository representation values for representation values which match input representation values, wherein the searching the index is performed in an amount of time which is independent of a size of the repository, and which is linear in a size of the input data; and

determining that at least one repository segment is similar to at least one input segment in response to finding at least n matches between the repository representation values of the at least one repository segment and the input representation values of the at least one input segment, wherein the amount of time which the searching the index is performed reduces an amount of processing time consumed by the processor during the searching and the determining; and

in response to determining a repository segment that is similar to an input segment, analyzing, by the processor, the similar repository segment with respect to the input segment to determine their common data sections, wherein at least some of the matching representation values are utilized for data alignment, wherein the analyzing is performed in an amount of time which is linear in a size of the input segment.

20. The data storage system of claim 19, wherein analyzing the similar repository segment with respect to the input segment to determine their common data sections includes:

identifying data which is uncommon between the similar repository segment and the input segment, wherein identifying the data which is uncommon between the similar repository segment and the input segment reduces an effective size of the input segment,

wherein the method comprises;

storing the uncommon data, wherein the reduced effective size of the input segment reduces an amount of memory consumed during the storing.