System and method for identifying locations within data

• US 8,495,312 B2
• Filed: 09/08/2010
• Issued: 07/23/2013
• Est. Priority Date: 01/25/2010
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Sepaton Incorporated (Hitachi, Ltd.)
• Inventors: Reiter, Timmie G., McMaster, Carey Jay, Trimble, Ronald Ray, King, Stefan Merrill, Biernacki, David Michael, Kennedy, Jon Christopher
• Primary Examiner(s): Farrokh, Hashem
• Application Number:
  US12/877,725
• Publication Number:
  US 20110185133A1
• Time in Patent Office: 1,049 Days
• Field of Search: 711/156, 711/108
• US Class Current: 711/156
• CPC Class Codes: G06F 11/1453 using de-duplication of the data

Abstract

Described are computer-based methods and apparatuses, including computer program products, for removing redundant data from a storage system. In one example, a data delineation process delineates data targeted for de-duplication into regions using a plurality of markers. The de-duplication system determines which of these regions should be subject to further de-duplication processing by comparing metadata representing the regions to metadata representing regions of a reference data set. The de-duplication system identifies an area of data that incorporates the regions that should be subject to further de-duplication processing and de-duplicates this area with reference to a corresponding area within the reference data set.

Claims

1. A computer implemented method of marking data for processing, the method comprising:

determining a rolling summary that identifies a particular pattern of stored data included in each respective region of a plurality of overlapping regions;

comparing at least one proper subset of the rolling summary to a predetermined value;

recording a location identifier that identifies a location within the data where the at east one proper subset equals the predetermined value,

determining a metric that indicates a frequency with which location identifiers are recorded for the data;

comparing the metric to a predetermined threshold; and

adjusting, responsive to the metric transgressing the predetermined threshold, a characteristic of the at least one proper subset.

2. The method according to claim 1, wherein determining the rolling summary includes calculating a hash value from the stored data.

3. The method according to claim 2, wherein calculating the hash value includes calculating a rolling XOR hash value.

4. The method according to claim 3, wherein comparing the at least one proper subset includes comparing the predetermined value to a value derived from 11 bits of the rolling XOR hash value.

5. The method according to claim 4, wherein recording the location identifier includes recording a location of a boundary of a respective region of the plurality of overlapping regions.

6. The method according to claim 1, wherein comparing the at least one proper subset of the rolling summary to a predetermined value includes comparing the entire rolling summary to the predetermined value.

7. The method according to claim 1, wherein determining the metric includes calculating a location identifier rate that equals the number of location identifiers recorded per an amount of the data.

8. The method according to claim 7, wherein ad sting the characteristic of the at least one proper subset includes adjusting the cardinality of the at least one proper subset.

9. A system configured to mark data for processing, the system comprising:

data storage storing the data, the data including a plurality of overlapping regions; and

a processor coupled to the data storage and configured to;

determine a rolling summary of each respective region of the plurality of overlapping regions based on stored data included in each respective region, the rolling summary identifying a particular pattern of the stored data;

compare at least one proper subset of the rolling summary o a predetermined value;

record a location identifier that identifies a location within the data where the at least one proper subset equals the predetermined value;

determine a metric that indicates a frequency with which location identifiers are recorded for the data;

compare the metric to a predetermined threshold and

adjust, responsive to the metric transgressing the predetermined threshold, a characteristic of the at least one proper subset.

14. The system according to claim 9, wherein the processor is further configured to compare the at least one proper subset of the rolling summary to a predetermined value by comparing the entire rolling summary to the predetermined value.

15. The system according to claim 9, wherein the processor is configured to determine the metric by calculating a location identifier rate that equals the number of location identifiers recorded per an amount of the data.

16. The system according to claim 15, wherein the processor is configured to adjust the characteristic of the at least one proper subset by adjusting the cardinality of the at least one proper subset.

10. The system according to claim, wherein the processor is configured to determine the rolling summary by calculating a hash value from the stored data.

11. The system according to claim 10, wherein the processor is configured to calculate a hash value by calculating a rolling XOR hash value.

12. The system according to claim 11, wherein the processor is configured to compare the at least one proper subset by comparing the predetermined value to a value derived from 11 bits of the rolling XOR hash value.

13. The system according to claim 12, wherein the processor is configured to record the location identifier by recording a location of a boundary of a respective region of the plurality of overlapping regions.

17. 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 marking data for processing, the method comprising:

determining a rolling summary that identifies a particular pattern of stored data included in each respective region of a plurality of overlapping regions;

comparing at least one proper subset of the rolling summary to a predetermined value;

recording a location identifier that identifies a location within the data where the at least one proper subset equals the predetermined value;

determining a metric that indicates a frequency with which location identifiers are recorded for the data;

comparing the metric to a predetermined threshold; and

adjusting, responsive to the metric transgressing the predetermined threshold, a characteristic of the at least one proper subset.

18. The computer readable medium according to claim 17, wherein the instructions for determining the rolling summary instruct the at least one processor to perform acts including calculating a rolling XOR hash value from the stored data.

19. The computer readable medium according to claim 17 wherein the instructions for recording the location identifier instruct the at least one processor to perform acts including recording a location of a boundary of a respective region of the plurality of overlapping regions.

20. The computer readable medium according to claim 17, wherein the instructions further instruct the at least one processor to perform acts including comparing the at least one proper subset of the rolling summary to a predetermined value by comparing the entire rolling summary to the predetermined value.