System and method for summarizing data

• US 8,620,939 B2
• Filed: 09/08/2010
• Issued: 12/31/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): Corrielus, Jean M
• Application Number:
  US12/877,731
• Publication Number:
  US 20110184966A1
• Time in Patent Office: 1,210 Days
• Field of Search: 711/159, 711/202, 711/162, 707/770, 707/705, 707/637, 707/698, 707/609, 707/699, 707/828, 707/692, 707/758
• US Class Current: 707/758
• 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 characterizing data associated with a plurality of location identifiers, each location identifier of the plurality of location identifiers identifying a location within the data where a particular pattern of data is stored, the method comprising:

identifying a first portion of the data based on a location of the first portion relative to a location identified by at least one first location identifier of the plurality of location identifiers;

identifying a second portion of the data based on a location of the second portion relative to a location identified by at least one second location identifier of the plurality of location identifiers;

determining one or more first summaries associated with the at least one first location identifier, at least one summary of the one or more first summaries indicating a pattern of stored data included in the first portion;

determining one or more second summaries associated with the at least one second location identifier, at least one summary of the one or more second summaries indicating another pattern of stored data included in the second portion;

identifying at least one fingerprint summary for the data based on values of summaries included in a set of summaries comprising the one or more first summaries and the one or more second summaries; and

storing an association between the at least one fingerprint summary and the data.

2. The method according to claim 1, wherein identifying the first portion includes identifying a portion having a boundary sharing the location identified by the at least one first location identifier.

3. The method according to claim 1, wherein determining the one or more first summaries includes calculating a hash value from the stored data.

4. The method according to claim 3, wherein determining the one or more first summaries includes selecting at least one summary associated with another location identifier of the plurality of location identifiers.

5. The method according to claim 4, wherein selecting the at least one summary includes selecting at least one prior summary associated with a prior location identifier of the plurality of location identifiers, the prior location identifier identifying a location in the data prior to the location identified by the at least one first location identifier.

6. The method according to claim 1, wherein determining the one or more first summaries includes:

calculating a first hash value using a first hashing method; and

calculating a second hash value using a second hashing method.

7. The method according to claim 1, wherein identifying the at least one fingerprint summary includes identifying at least one member of the set of summaries with a value that is higher than values of other members of the set of summaries.

8. A system configured to characterize data, the system comprising:

data storage storing the data and a plurality of location identifiers, each of the plurality of location identifiers identifying a location within the data where a particular pattern of data is stored; and

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

identify a first portion of the data based on a location of the first portion relative to a location identified by at least one first location identifier of the plurality of location identifiers;

identify a second portion of the data based on a location of the second portion relative to a location identified by at least one second location identifier of the plurality of location identifiers;

determine one or more first summaries associated with the at least one first location identifier, at least one summary of the one or more first summaries indicating a pattern of stored data included in the first portion;

determine one or more second summaries associated with the at least one second location identifier, at least one summary of the one or more second summaries indicating another pattern of stored data included in the second portion;

identify at least one fingerprint summary for the data based on values of summaries included in a set of summaries comprising the one or more first summaries and the one or more second summaries; and

store an association between the at least one fingerprint summary and the data.

9. The system according to claim 8, wherein the at least one processor is configured to identify the first portion by identifying a portion having a boundary sharing the location identified by the at least one first location identifier.

10. The system according to claim 8, wherein the at least one processor is configured to determine the one or more first summaries by calculating a hash value from the stored data.

11. The system according to claim 10, wherein the at least one processor is configured to determine the one or more first summaries by selecting at least one summary associated with another location identifier of the plurality of location identifiers.

12. The system according to claim 11, wherein the at least one processor is configured to select the at least one summary by selecting at least one prior summary associated with a prior location identifier of the plurality of location identifiers, the prior location identifier identifying a location in the data prior to the location identified by the at least one first location identifier.

13. The system according to claim 8, wherein the at least one processor is configured to determine the one or more first summaries, by at least in part:

calculating a first hash value using a first hashing method; and

calculating a second hash value using a second hashing method.

14. The system according to claim 8, wherein the at least one processor is configured to identify the at least one fingerprint summary by identifying at least one member of the set of summaries with a value that is higher than values of other members of the set of summaries.

15. 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 characterizing data associated with a plurality of location identifiers, each location identifier of the plurality of location identifiers identifying a location within the data where a particular pattern of data is stored, the method comprising:

identifying a first portion of the data based on a location of the first portion relative to a location identified by at least one first location identifier of the plurality of location identifiers;

identifying a second portion of the data based on a location of the second portion relative to a location identified by at least one second location identifier of the plurality of location identifiers;

determining one or more first summaries associated with the at least one first location identifier, at least one summary of the one or more first summaries indicating a pattern of stored data included in the first portion;

determining one or more second summaries associated with the at least one second location identifier, at least one summary of the one or more second summaries indicating another pattern of stored data included in the second portion;

identifying at least one fingerprint summary for the data based on values of summaries included in a set of summaries comprising the one or more first summaries and the one or more second summaries; and

storing an association between the at least one fingerprint summary and the data.

16. The computer readable medium according to claim 15, wherein the instructions for determining the one or more first summaries instruct the at least one processor to perform acts including selecting at least one summary associated with another location identifier of the plurality of location identifiers.

17. The computer readable medium according to claim 15, wherein the instructions for identifying the at least one fingerprint summary instruct the at least one processor to perform acts including identifying at least one member of the set of summaries with a value that is higher than values of other members of the set of summaries.

18. The computer readable medium according to claim 15, wherein the instructions for identifying the first portion instruct the at least one processor to perform acts including identifying a portion having a boundary sharing the location identified by the at least one first location identifier.

19. The computer readable medium according to claim 15, wherein the instructions for determining the one or more first summaries instruct the at least one processor to perform acts including calculating a hash value from the stored data.

20. The computer readable medium according to claim 16, wherein the instructions for selecting the at least one summary instruct the at least one processor to perform acts including selecting at least one prior summary associated with a prior location identifier of the plurality of location identifiers, the prior location identifier identifying a location in the data prior to the location identified by the at least one first location identifier.