SYSTEM AND METHOD FOR SAMPLING BASED ELIMINATION OF DUPLICATE DATA

• US 20120197853A1
• Filed: 04/10/2012
• Published: 08/02/2012
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Zheng, Ling, Stager, Roger, Johnston, Craig, Trimmer, Don, Frandzel, Yuval
• Granted Patent: US 9,344,112 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: H03M 7/00 Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of information is represented by a different sequence or number of digits
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/25 with scene description coding, e.g. binary format for scenes [BIFS] compression

Abstract

A technique for eliminating duplicate data is provided. Upon receipt of a new data set, one or more anchor points are identified within the data set. A bit-by-bit data comparison is then performed of the region surrounding the anchor point in the received data set with the region surrounding an anchor point stored within a pattern database to identify forward/backward delta values. The duplicate data identified by the anchor point, forward and backward delta values is then replaced in the received data set with a storage indicator.

Claims

1. A method for removing duplicate data from a data set stored on a storage system, the method comprising:

performing, by a processor, an operation on the data set to identify an anchor within the data set, wherein the anchor is a specific section within the data set that defines a region of interest for potential data de-duplication; and

identifying, by the processor, a forward delta value and a backward delta value which collectively identify a number of consecutive bits of data that match between the data set and the stored data set forward and backward from the identified anchor, respectively.

2. The method of claim 1 further comprising replacing, by the processor, a region of the data set identified by the anchor, the forward delta value and the backward delta value as duplicate data with an indicator to form a modified data set, wherein the modified data set has duplicate data removed.

3. The method of claim 1 wherein the operation comprises a rolling hash on the data set.

4. The method of claim 1 further comprising:

determining whether the identified anchor already exists within an anchor data store; and

in response to determining that the identified anchor does not already exist in the anchor data store, storing the identified anchor in the anchor data store.

5. The method of claim 1 wherein the indicator comprises an anchor identifier field, a forward delta field and a backward delta field.

6. The method of claim 1 wherein identifying the forward delta value and the backward delta value comprises performing a comparison between the data set and a stored data set.

7. The method of claim 6 wherein the stored data set is stored in a pattern data store.

8. The method of claim 1 further comprising forming an anchor hierarchy by performing an operation on a plurality of adjacent anchors within the data set.

9. The method of claim 8 wherein the operation comprises a hash.

10. The method of claim 1 wherein the data set comprises a backup data stream.

11. A system configured to remove duplicate data from a data set stored on a storage system, the system comprising:

a module executed by a processor of the storage system, the module adapted to identify an anchor within the data set and further adapted to determine whether the identified anchor exists within a data store storing a plurality of anchors; and

the module is further adapted to, in response to, determining that the anchor exists within the data store, perform a data comparison between the data set and a stored data set to identify a forward delta value and a backward delta value.

12. The system of claim 11 wherein the module is further adapted to replace a region of the data set with an indicator to form a modified data set, wherein the modified data set has duplicate data removed.

13. The system of claim 12 wherein the indicator indicates a size of the region between the backward delta value and the forward delta value centered on the anchor.

14. The system of claim 11 further comprising a pattern data store configured to store the stored data set.

15. The system of claim 11 wherein the module is adapted to identify the anchor by placing the anchor at a predefined location within the data set.

16. The system of claim 11 wherein the data set comprises a backup data stream.

17. The system of claim 11 wherein the anchor is identified by performing a rolling hash.

18. An non-transitory computer readable medium containing program instructions executed on a processor, comprising:

program instructions that perform an operation on a data set stored on a storage system to identify an anchor within the data set, wherein the anchor is a specific section within the dataset that defines a region of interest for potential data de-duplication; and

program instructions that identify a forward delta value and a backward delta value which collectively identify a number of consecutive bits of data that match between the data set and a stored data set.

19. The non-transitory computer readable medium of claim 18 further comprising program instructions that determine whether the identified anchor exists within an anchor data store

20. The non-transitory computer readable medium of claim 18 further comprising program instructions that perform a rolling hash on the data set to identify the anchor within the data set.