SYSTEMS AND METHODS OF LOCATING REDUNDANT DATA USING PATTERNS OF MATCHING FINGERPRINTS

• US 20140279956A1
• Filed: 01/22/2014
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Hitachi Vantara Corporation (Hitachi, Ltd.)
• Inventors: Reiter, Timmie G., Trimble, Ronald Ray, Kennedy, Jon Christopher, Biernacki, David Michael, McMaster, Carey Jay, King, Stefan Merrill
• Granted Patent: US 9,766,832 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• 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]
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

A system configured to compute match potential between first data and second data is provided. The system includes data storage storing the first data and the second data, and at least one processor coupled to the data storage. The at least one processor is configured to identify a first sequence of fingerprints characterizing a first plurality of sections of the first data, the first sequence being ordered according to an order of the first plurality of sections within the first data; identify a second sequence of fingerprints comprising fingerprints that match fingerprints within the first sequence, the second sequence of fingerprints characterizing a second plurality of sections of the second data, the second sequence being ordered according to an order of the second plurality of sections within the second data; quantify a similarity between the first sequence and the second sequence; and adjust the match potential based on the similarity.

Claims

1. A method of computing match potential between first data and second data, the method comprising:

identifying a first sequence of fingerprints characterizing a first plurality of sections of the first data, the first sequence being ordered according to an order of the first plurality of sections within the first data;

identifying a second sequence of fingerprints comprising fingerprints that match fingerprints within the first sequence, the second sequence of fingerprints characterizing a second plurality of sections of the second data, the second sequence being ordered according to an order of the second plurality of sections within the second data;

quantifying a similarity between the first sequence and the second sequence; and

adjusting the match potential based on the quantified similarity.

2. The method according to claim 1, wherein identifying the first sequence of fingerprints includes identifying the first sequence of fingerprints based on a prioritization scheme and identifying the second sequence of fingerprints includes identifying the second sequence of fingerprints based on the prioritization scheme.

3. The method according to claim 1, wherein identifying the first sequence of fingerprints includes identifying a first sequence of fingerprints characterizing a first plurality of sections including one or more sections characterized by fingerprints other than fingerprints included in the second sequence.

4. The method according to claim 1, wherein the first sequence includes a first plurality of subsequences, the second sequence includes a second plurality of subsequences, and quantifying the similarity includes quantifying a similarity between at least one first subsequence of the first plurality of subsequences and at least one second subsequence of the second plurality of subsequences.

5. The method according to claim 4, wherein quantifying the similarly includes quantifying a similarity between subsequences of the first plurality of subsequences that overlap other subsequences of the first plurality of subsequences and subsequences of the second subsequences that overlap other subsequences of the second plurality of subsequences.

6. The method according to claim 4, wherein quantifying the similarity between the at least one first subsequence and the at least one second subsequence includes computing at least one score for at least one first section of the first plurality of sections, the at least one first section being characterized by one or more fingerprints within the at least one first subsequence.

7. The method according to claim 6, wherein the at least one first section is associated with a matching range that identifies at least one first ordinal position within the second data, the at least one first ordinal position being one or more ordinal positions of one or more of the second plurality of sections, the one or more of the second plurality of sections being characterized by one or more fingerprints that match one or more fingerprints characterizing the at least one first section, and wherein computing the at least one score for the at least one first section includes:

selecting a plurality of combinations of sections from a subset of the first data, the subset being characterized by fingerprints included in the at least one first subsequence, each of the plurality of combinations including the at least one first section and at least one second section of the subset, the at least one second section being associated with one or more matching sections within the second plurality of sections, the one or more matching sections being characterized by at least one fingerprint that matches at least one fingerprint characterizing the second section;

computing one or more adjusted ordinal positions for the one or more matching sections based on an ordinal position of the first section, an ordinal position of the second section, and one or more ordinal positions of the one or more matching sections; and

increasing the score for each adjusted ordinal position of the one or more adjusted ordinal positions disposed within the matching range of the at least one first section.

8. The method according to claim 7, further comprising terminating quantification the similarity when the at least one first ordinal position is less than at least one second ordinal position identified in a matching range associated with a section of the first data having an ordinal position that is greater than the at least one first section.

9. The method according claim 7, wherein the at least one first ordinal position includes a plurality of ordinal positions and increasing the score includes increasing the score for each adjusted ordinal position within a matching range that identifies the plurality of ordinal positions.

10. The method according to claim 9, wherein the plurality of ordinal positions includes two ordinal positions, one of the two ordinal positions being a minimum ordinal position of the at least one first section, and another of the two positions being a maximum ordinal position of the at least one first section and increasing the score includes increasing the score for each adjusted ordinal position within a matching range that identifies the minimum ordinal position and the maximum ordinal position.

11. A system configured to compute match potential between first data and second data, the system comprising:

data storage storing the first data and the second data; and

at least one processor coupled to the data storage and configured to;

identify a first sequence of fingerprints characterizing a first plurality of sections of the first data, the first sequence being ordered according to an order of the first plurality of sections within the first data;

identify a second sequence of fingerprints comprising fingerprints that match fingerprints within the first sequence, the second sequence of fingerprints characterizing a second plurality of sections of the second data, the second sequence being ordered according to an order of the second plurality of sections within the second data;

quantify a similarity between the first sequence and the second sequence; and

adjust the match potential based on the quantified similarity.

12. The system according to claim 11, wherein the first sequence includes a first plurality of subsequences, the second sequence includes a second plurality of subsequences, and the at least one processor is configured to quantify the similarity by quantifying a similarity between at least one first subsequence of the first plurality of subsequences and at least one second subsequence of the second plurality of subsequences.

13. The system according to claim 12, wherein the at least one processor is configured to quantify the similarly by quantifying a similarity between subsequences of the first plurality of subsequences that overlap other subsequences of the first plurality of subsequences and subsequences of the second subsequences that overlap other subsequences of the second plurality of subsequences.

14. The system according to claim 12, wherein the at least one processor is configured to quantify the similarity between the at least one first subsequence and the at least one second subsequence by, at least in part, computing at least one score for at least one first section of the first plurality of sections, the at least one first section being characterized by one or more fingerprints within the at least one first subsequence.

15. The system according to claim 14, wherein the at least one first section is associated with a matching range that identifies at least one first ordinal position within the second data, the at least one first ordinal position being one or more ordinal positions of one or more of the second plurality of sections, the one or more of the second plurality of sections being characterized by one or more fingerprints that match one or more fingerprints characterizing the at least one first section, and wherein the at least one processor is configured to compute the at least one score by, at least in part:

selecting a plurality of combinations of sections from a subset of the first data, the subset being characterized by fingerprints included in the at least one first subsequence, each of the plurality of combinations including the at least one first section and at least one second section of the subset, the at least one second section being associated with one or more matching sections within the second plurality of sections, the one or more matching sections being characterized by at least one fingerprint that matches at least one fingerprint characterizing the second section;

computing one or more adjusted ordinal positions for the one or more matching sections based on an ordinal position of the first section, an ordinal position of the second section, and one or more ordinal positions of the one or more matching sections; and

increasing the score for each adjusted ordinal position of the one or more adjusted ordinal positions disposed within the matching range of the at least one first section.

16. The system according to claim 15, wherein the at least one processor is further configured to terminate quantification of the similarity when the at least one first ordinal position is less than at least one second ordinal position identified in a matching range associated with a section of the first data having an ordinal position that is greater than the at least one first section.

17. The system according claim 15, wherein the at least one first ordinal position includes a plurality of ordinal positions and the at least one processor is configured to increase the score by, at least in part, increasing the score for each adjusted ordinal position within a matching range that identifies the plurality of ordinal positions.

18. The system according to claim 17, wherein the plurality of ordinal positions includes two ordinal positions, one of the two ordinal positions being a minimum ordinal position of the at least one first section, and another of the two positions being a maximum ordinal position of the at least one first section.

19. A non-transitory computer readable medium storing computer readable instructions that, when executed by at least one processor, instruct the at least one processor to perform a method of computing match potential between first data and second data, the method comprising:

identifying a first sequence of fingerprints characterizing a first plurality of sections of the first data, the first sequence being ordered according to an order of the first plurality of sections within the first data;

identifying a second sequence of fingerprints comprising fingerprints that match fingerprints within the first sequence, the second sequence of fingerprints characterizing a second plurality of sections of the second data, the second sequence being ordered according to an order of the second plurality of sections within the second data;

quantifying a similarity between the first sequence and the second sequence; and

adjusting the match potential based on the quantified similarity.

20. The computer readable medium according to claim 19, wherein the instructions further instruct the at least one processor to quantify the similarity by computing at least on score for at least one section of the first plurality of sections.