System and Method for Summarizing Data

• US 20110184966A1
• Filed: 09/08/2010
• Published: 07/28/2011
• Est. Priority Date: 01/25/2010
• Status: Active Grant

• Current Assignee: Hitachi Vantara, LLC (Hitachi, Ltd.)
• Original Assignee: Sepaton Incorporated (Hitachi, Ltd.)
• Inventors: Kennedy, Jon Christopher, King, Stefan Merrill, McMaster, Carey Jay, Trimble, Ronald Ray, Reiter, Timmie G., Biernacki, David Michael
• Granted Patent: US 8,620,939 B2
• Time in Patent Office: Days
• 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 being 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 5 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 of the plurality of location identifiers; and

determining a first plurality of summaries associated with the at least one of the plurality of location identifiers, at least one summary of the first plurality of summaries indicating a pattern of stored data included in the first portion.

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 of the plurality of location identifiers.

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

4. The method according to claim 3, wherein determining the first plurality of summaries includes selecting at least one summary associated with another 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 of the plurality of location identifiers.

6. The method according to claim 1, wherein determining the first plurality of 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, further comprising:

storing the first plurality of summaries as a first member of a set of summaries;

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

determining a second plurality of summaries associated with the at least one other of the plurality of location identifiers, at least one summary of the second plurality of summaries indicating another pattern of stored data included in the second portion;

storing the second plurality of summaries as a second member of the set of summaries; and

identifying a subset of the set of summaries based on values of summaries included in the set of summaries.

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

9. 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

a 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 of the plurality of location identifiers; and

determine a first plurality of summaries associated with the at least one of the plurality of location identifiers, at least one summary 5 of the first plurality of summaries indicating a pattern of stored data included in the first portion.

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

11. The system according to claim 9, wherein the processor is configured to determine the first plurality of summaries by calculating a hash value from the stored data.

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

13. The system according to claim 12, wherein the 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 of the plurality of location identifiers.

14. The system according to claim 9, wherein the processor is configured to determine the first plurality of 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.

15. The system according to claim 9, wherein the processor is further configured to:

store the first plurality of summaries as a first member of a set of summaries;

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

determine a second plurality of summaries associated with the at least one other of the plurality of location identifiers, at least one summary of the second plurality of summaries indicating a another pattern of stored data included in the second portion;

store the second plurality of summaries as a second member of the set of summaries; and

identify a subset of the set of summaries based on values of summaries included in the set of summaries.

16. The system according to claim 15, wherein the processor is configured to identify the subset of the set of summaries by identifying at least one member of the set of summaries including a summary with a value that is higher than values of summaries included in other members of the set of summaries.

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 characterizing data being 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 of the plurality of location identifiers; and

determining a first plurality of summaries associated with the at least one of the plurality of location identifiers, at least one summary of the first plurality of summaries indicating a pattern of stored data included in the first portion.

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

19. The computer readable medium according to claim 17, wherein the instructions further instruct the at least one processor to perform acts including:

storing the first plurality of summaries as a first member of a set of summaries;

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

determining a second plurality of summaries associated with the at least one other of the plurality of location identifiers, at least one summary of the second plurality of summaries indicating another pattern of stored data included in the second portion;

storing the second plurality of summaries as a second member of the set of summaries; and

identifying a subset of the set of summaries based on values of summaries included in the set of summaries.

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