System and Method for Data Driven De-Duplication

• US 20110184921A1
• 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, Reiter, Timmie G., McMaster, Carey Jay, Trimble, Ronald Ray, Biernacki, David Michael
• Granted Patent: US 8,495,028 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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 locating redundancy within data, the method comprising:

recording target locations within target data where a summary that identifies a particular pattern within the target data equals a predetermined value;

recording reference locations within reference data where a summary that identifies the particular pattern within the reference data equals the predetermined value;

determining a reference set of summaries of the reference data, each member of the reference set of summaries including a plurality of summaries indicative of patterns of reference data located at recorded reference locations;

determining a target set of summaries of the target data, each member of the target set of summaries including a plurality of summaries indicative of patterns of target data located at recorded target locations; and

identifying a subset of the reference data that is likely to match a subset of the target data by comparing members of the reference set of summaries to members of the target set of summaries.

2. The method according to claim 1, wherein recording the target locations includes recording target locations within the target data where a subset of a rolling hash value taken over a region of the target data equals the predetermined value.

3. The method according to claim 1, wherein determining the reference set of summaries includes calculating a hash value over a portion of the reference data sharing a boundary with at least one recorded reference location.

4. The method according to claim 1, wherein identifying the subset of the reference data includes identifying an area of the target data associated with at least one member of the target set of summaries that matches at least one member of the reference set of summaries.

5. The method according to claim 4, wherein identifying the subset of the reference data includes identifying an area of the reference data associated the at least one member of the reference set of summaries.

6. The method according to claim 1, further comprising adjusting the subset of the reference data after identifying a neighboring area of the reference data associated with at least one other member of the reference set of summaries that matches at least one member of the target set of summaries.

7. The method according to claim 1, further comprising de-duplicating the subset of the target data with reference to the subset of the reference data.

8. A system configured to locate redundancy within data, the system comprising:

data storage storing reference data and target data; and

a processor coupled to the data storage and configured to;

record target locations within the target data where a summary that identifies a particular pattern within the target data equals a predetermined value;

record reference locations within the reference data where a summary that identifies the particular pattern within the reference data equals the predetermined value;

determine a reference set of summaries of the reference data, each member of the reference set of summaries including a plurality of summaries indicative of patterns of reference data located at recorded reference locations;

determine a target set of summaries of the target data, each member of the target set of summaries including a plurality of summaries indicative of patterns of target data located at recorded target locations; and

identify a subset of the reference data that is likely to match a subset of the target data by comparing members of the reference set of summaries to members of the target set of summaries.

9. The system according to claim 8, wherein the processor is configured to record the target locations by recording target locations within the target data where a subset of a rolling hash value taken over a region of the target data equals the predetermined value.

10. The system according to claim 8, wherein the processor is configured to determine the reference set of summaries by calculating a hash value over a portion of the reference data sharing a boundary with at least one recorded reference location.

11. The system according to claim 8, wherein the processor is configured to identify the subset of the reference data by, at least in part, identifying an area of the target data associated with at least one member of the target set of summaries that matches at least one member of the reference set of summaries.

12. The system according to claim 11, wherein the processor is configured to identifying the subset of the reference data includes identifying an area of the reference data associated the at least one member of the reference set of summaries.

13. The system according to claim 8, wherein the processor is further configured to adjust the subset of the reference data after identifying a neighboring area of the reference data associated with at least one other member of the reference set of summaries that matches at least one member of the target set of summaries.

14. The system according to claim 8, wherein the processor is further configured to de-duplicate the subset of the target data with reference to the subset of the reference data.

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 locating redundancy within data, the method comprising:

recording target locations within target data where a summary that identifies a particular pattern within the target data equals a predetermined value;

recording reference locations within reference data where a summary that identifies the particular pattern within the reference data equals the predetermined value;

determining a reference set of summaries of the reference data, each member of the reference set of summaries including a plurality of summaries indicative of patterns of reference data located at recorded reference locations;

determining a target set of summaries of the target data, each member of the target set of summaries including a plurality of summaries indicative of patterns of target data located at recorded target locations; and

identifying a subset of the reference data that is likely to match a subset of the target data by comparing members of the reference set of summaries to members of the target set of summaries.

16. The computer readable medium according to claim 15, wherein the instructions for recording the target locations instruct the processor to perform acts including recording target locations within the target data where a subset of a rolling hash value taken over a region of the target data equals the predetermined value.

17. The computer readable medium according to claim 15, wherein the instructions for determining the reference set of summaries instruct the processor to perform acts including calculating a hash value over a portion of the reference data sharing a boundary with at least one recorded reference location.

18. The computer readable medium according to claim 15, wherein the instructions for identifying the subset of the reference data instruct the processor to perform acts including identifying an area of the target data associated with at least one member of the target set of summaries that matches at least one member of the reference set of summaries.

19. The computer readable medium according to claim 18, wherein the instructions for identifying the subset of the reference data instruct the processor to perform acts including identifying an area of the reference data associated the at least one member of the reference set of summaries.

20. The computer readable medium according to claim 15, wherein the instructions further instruct the processor to perform acts including adjusting the subset of the reference data after identifying a neighboring area of the reference data associated with at least one other member of the reference set of summaries that matches at least one member of the target set of summaries.