Detection and deduplication of backup sets exhibiting poor locality

• US 9,122,639 B2
• Filed: 01/25/2011
• Issued: 09/01/2015
• Est. Priority Date: 01/25/2011
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Sepaton Incorporated (Hitachi, Ltd.)
• Inventors: Kennedy, Jon Christopher, Trimble, Ronald Ray, McMaster, Carey Jay, Petrangelo, John Henry, Sorel, Roland Leo, Grinwald, Patrick James
• Primary Examiner(s): Shmatov, Alexey
• Application Number:
  US13/013,403
• Publication Number:
  US 20120191669A1
• Time in Patent Office: 1,680 Days
• Field of Search: 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 2201/81 Threshold

Abstract

Described are computer-based methods and apparatuses, including computer program products, for detection and deduplication of backup sets exhibiting poor locality. A first set of summaries of a first data set are determined, each summary of the first set of summaries being indicative of a data pattern in the first data set. A second set of summaries of a second data set are determined, each summary of the second set of summaries being indicative of a data pattern in the second data set. A set of comparison metrics are calculated, each comparison metric being based on a first subset of summaries from the first set of summaries and a second subset of summaries from the second set of summaries. A locality metric is calculated based on the set of comparison metrics indicative of whether the first data set and second data set exhibit poor locality.

Claims

1. A computerized method for storing data comprising:

determining, by a computing device, a first set of summaries of a first data set, each summary of the first set of summaries being indicative of a data pattern in the first data set at an associated location in the first data set;

determining, by the computing device, a second set of summaries of a second data set, each summary of the second set of summaries being indicative of a data pattern in the second data set at an associated location in the second data set;

calculating, by the computing device, a set of comparison metrics, each comparison metric being based on a first subset of summaries from the first set of summaries and a second subset of summaries from the second set of summaries;

calculating, by the computing device, a locality metric based on the set of comparison metrics, the locality metric being indicative of a ratio of data within the first data set which is distributed as redundant data within the second data set with distance greater than a predetermined threshold;

adjusting at least one parameter of a deduplication process based on the locality metric, the at least one parameter including at least one of a detection parameter and a deduplication parameter; and

deduplicating the first data set and the second data set using the deduplication process.

2. The method of claim 1 wherein calculating the set of comparison metrics comprises:

identifying a first summary from the first set of summaries that is similar to a second summary and a third summary from the second set of summaries; and

calculating a distance between the second summary and the third summary.

3. The method of claim 2 further comprising:

determining the distance is greater than a predetermined threshold; and

storing, in response to determining the distance is greater than the predetermine threshold, a metric in the set of comparison metrics that indicates the first data and the second data set exhibit poor locality.

4. The method of claim 2 further comprising:

determining the distance is not greater than a predetermined threshold; and

storing, in response to determining the distance is not greater than the predetermine threshold, a metric in the set of comparison metrics that indicates the first data set and the second data set exhibit good locality.

5. The method of claim 1 further comprising:

determining a first summary from the first set of summaries is similar to a plurality of summaries from the second set of summaries; and

not calculating a comparison metric based on the first summary.

6. The method of claim 1 wherein calculating the locality metric comprises calculating a statistic of the set of comparison metrics.

7. The method of claim 6 wherein calculating the statistic comprises:

determining a comparison metric in the set of comparison metrics is greater than a maximum metric; and

filtering the comparison metric from the set of comparison metrics.

8. The method of claim 6 further comprising determining whether the statistic is greater than a predetermined threshold.

9. The method of claim 8 further comprising, if the statistic is greater than the predetermined threshold, calculating a percentage based on a set of comparison metrics that indicate poor locality from the set of comparison metrics and a set of comparison metrics that indicate good locality from the set of comparison metrics.

10. The method of claim 9 further comprising:

determining whether the percentage is greater than a predetermined percentage;

if the percentage is greater than the predetermined percentage, setting the locality metric to indicate the first data set and second data set exhibit poor locality; and

if the percentage is not greater than the predetermined percentage, setting the locality metric to indicate the first data set and second data set do not exhibit poor locality.

11. The method of claim 8 further comprising, if the statistic is not greater than the predetermined threshold, setting the locality metric to indicate the first data set and second data set do not exhibit poor locality.

12. The method of claim 1 further comprising determining the locality metric is indicative of the first data set and second data set exhibiting poor locality, and wherein adjusting the at least one parameter comprises adjusting the at least one parameter in response to determining the locality metric is indicative of the first data set and second data set exhibiting poor locality.

13. The method of claim 12 wherein the first set of summaries and the second set of summaries are calculated based on a predetermined amount of data, and wherein adjusting comprises reducing the predetermined amount of data.

14. The method of claim 12 wherein a predetermined number of characterizations are calculated for each summary in the first set of summaries and the second set of summaries, and wherein adjusting comprises at least one of (a) reducing the predetermined number of characterizations or (b) increasing the predetermined number of characterizations.

15. The method of claim 1, further comprising determining the first data set, the second data set, or both, are multiplexed backup data sets.

16. The method of claim 1 further comprising:

determining a third set of summaries of a third data set, each summary of the third set of summaries being indicative of a data pattern in the third data set at an associated location in the third data set;

calculating a set of comparison metrics, each comparison metric being based on the first subset of summaries and a third subset of summaries from the third set of summaries; and

calculating a locality metric based on the set of comparison metrics, the locality metric being indicative of whether data within the first data set is distributed differently from redundant data within the third data set.

17. A computer program product, tangibly embodied in a non-transitory computer readable medium, the computer program product including instructions being configured to cause a data processing apparatus to:

determine a first set of summaries of a first data set, each summary of the first set of summaries being indicative of a data pattern in the first data set at an associated location in the first data set;

determine a second set of summaries of a second data set, each summary of the second set of summaries being indicative of a data pattern in the second data set at an associated location in the second data set;

calculate a set of comparison metrics, each comparison metric being based on a first subset of summaries from the first set of summaries and a second subset of summaries from the second set of summaries;

calculate a locality metric based on the set of comparison metrics, the locality metric being indicative of a ratio of data within the first data set which is distributed as redundant data within the second data set with distance greater than a predetermined threshold;

adjust at least one parameter of a deduplication process based on the locality metric, the at least one parameter including at least one of a detection parameter and a deduplication parameter; and

deduplicate the first data set and the second data set using the deduplication process.

18. The computer program product of claim 17 wherein the instructions are further configured to cause the data processing apparatus to calculate the set of comparison metrics by:

identifying a first summary from the first set of summaries that is similar to a second summary and a third summary from the second set of summaries; and

calculating a distance between the second summary and the third summary.

19. An apparatus comprising a processor and memory configured to:

determine a first set of summaries of a first data set, each summary of the first set of summaries being indicative of a data pattern in the first data set at an associated location in the first data set;

determine a second set of summaries of a second data set, each summary of the second set of summaries being indicative of a data pattern in the second data set at an associated location in the second data set;

calculate a set of comparison metrics, each comparison metric being based on a first subset of summaries from the first set of summaries and a second subset of summaries from the second set of summaries;

calculate a locality metric based on the set of comparison metrics, the locality metric being indicative of a ratio of data within the first data set which is distributed as redundant data within the second data set with distance greater than a predetermined threshold;

adjust at least one parameter of a deduplication process based on the locality metric, the at least one parameter including at least one of a detection parameter and a deduplication parameter; and

deduplicate the first data set and the second data set using the deduplication process.

20. The apparatus of claim 19 wherein the apparatus is configured to calculate the set of comparison metrics by:

identifying a first summary from the first set of summaries that is similar to a second summary and a third summary from the second set of summaries; and

calculating a distance between the second summary and the third summary.