SYSTEM AND METHOD FOR ACCELERATING ANCHOR POINT DETECTION

• US 20080301134A1
• Filed: 05/31/2007
• Published: 12/04/2008
• Est. Priority Date: 05/31/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Miller, Steven C., Stager, Roger
• Granted Patent: US 8,762,345 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A sampling based technique for eliminating duplicate data (de-duplication) stored on storage resources, is provided. According to the invention, when a new data set, e.g., a backup data stream, is received by a server, e.g., a storage system or virtual tape library (VTL) system implementing the invention, one or more anchors are identified within the new data set. The anchors are identified using a novel anchor detection circuitry in accordance with an illustrative embodiment of the present invention. Upon receipt of the new data set by, for example, a network adapter of a VTL system, the data set is transferred using direct memory access (DMA) operations to a memory associated with an anchor detection hardware card that is operatively interconnected with the storage system. The anchor detection hardware card may be implemented as, for example, a FPGA is to quickly identify anchors within the data set. As the anchor detection process is performed using a hardware assist, the load on a main processor of the system is reduced, thereby enabling line speed de-duplication.

Claims

1. A method for anchor detection, the method comprising the steps of:

detecting, by anchor detection circuitry, a location of a set of anchors in a received data set;

transferring the location of the set of anchors to a de-duplication module;

identifying, by the de-duplication module, duplicate data within the received data set; and

removing the identified duplicate data from the received data set prior to storage of the received data set on a storage device.

2. The method of claim 1 wherein the anchor detection circuitry comprises a programmable logic device.

3. The method of claim 2 wherein the programmable logic device comprises a field programmable gate array.

4. A method for anchor detection, the method comprising the steps of:

receiving a new data set;

transferring the new data set to anchor detection circuitry;

detecting, by the anchor detection circuitry, a location of a set of anchors in the new data set; and

transferring the location of the set of anchors to a de-duplication module.

5. The method of claim 4 wherein the new data set comprises a tape backup data set.

6. The method of claim 4 wherein the step of receiving the new data set comprises the step of receiving the data set by a network adapter of a storage system.

7. The method of claim 4 wherein the step of transferring the new data set to the anchor detection circuitry comprises the step of performing a direct memory access operation.

8. The method of claim 4 wherein the step of detecting the set of anchor location further comprises the step of performing a rolling hash on the new data set.

9. The method of claim 4 further comprising the step of using the set of anchor locations to eliminate duplicate data from the data set.

10. A system for anchor detection, the system comprising:

anchor detection hardware configured to (i) receive a data stream, (ii) identify a set of anchor locations in the data stream, and (iii) forward the set of anchor locations to a de-duplication module.

11. The system of claim 10 wherein the anchor detection hardware comprises a field programmable gate array.

12. The system of claim 10 wherein the anchor detection hardware comprises a card operatively interconnected with a system bus.

13. The system of claim 10 further comprising a network adapter of a storage system configured to receive the data stream from a network and to transfer the data stream to the anchor detection hardware.

14. The system of claim 13 wherein the network adapter transfers the data stream using direct memory access.

15. The system of claim 10 wherein the data stream comprises a tape backup data stream.

16. The system of claim 10 wherein the anchor detection hardware identifies the set of anchor locations by performing a rolling hash on the data stream.

17. The system of claim 10 wherein the de-duplication module comprises a portion of a virtual tape library module.

18. The system of claim 10 wherein the de-duplication module utilizes the set of anchor locations to de-duplicate the data stream.

19. The system of claim 18 wherein de-duplication of the data stream occurs without storing the data stream on persistent storage prior to de-duplication of the data stream.

20. A system for anchor detection, the system comprising:

means for receiving a new data set;

means for transferring the new data set to anchor detection hardware;

means for detecting, by the anchor detection hardware, a location of a set of anchors in the new data set; and

means for transferring the location of the set of anchors to a de-duplication module.

21. The system of claim 20 wherein the new data set comprises a tape backup data set.

22. A method for anchor detection, the method comprising the steps of:

transferring a data set to anchor detection hardware;

detecting, by the anchor detection hardware, a location of a set of anchors in the new data set;

transferring the location of the set of anchors to a de-duplication module; and

de-duplicating the data set using the set of anchors in the data set.

23. The method of claim 22 wherein the data set comprises a tape backup data set.

24. The method of claim 22 wherein the step of transferring the data set to the anchor detection hardware comprises the step of performing a direct memory access operation.