System and method for accelerating anchor point detection

• US 8,762,345 B2
• Filed: 05/31/2007
• Issued: 06/24/2014
• Est. Priority Date: 05/31/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Miller, Steven C., Stager, Roger
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US11/756,044
• Publication Number:
  US 20080301134A1
• Time in Patent Office: 2,581 Days
• Field of Search: 707/661, 707/662, 707/664, 707/665, 707/692
• US Class Current: 707/664
• 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, comprising:

receiving a data set at a storage system;

in response to receiving the data set, detecting one or more anchor locations in the data set by an anchor detection circuitry of the storage system, wherein the anchor detection circuitry is a hardware device dedicated to detecting the one or more anchor locations;

transferring each anchor locations to a data de-duplication module executed by a processor of the storage system;

determining if the anchor location is located in a database;

if the anchor location is not located in the database, adding the anchor location to the database;

if the anchor location is located in the database, examining, by the de-duplication module executed by the processor, bits preceding the anchor location utilizing a first delta value and the bits following the anchor location utilizing a second delta value to identify duplicate data; and

in response to identifying the duplicate data, removing the duplicate data from the data set prior to storing the data set on a storage device operatively connected to the storage system.

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, comprising:

receiving a data set from a client by a storage system;

in response to receiving the data set, transferring the data set to an anchor detection circuitry of the storage system, wherein the anchor detection circuitry is a hardware device dedicated to detecting the one or more anchor locations;

detecting one or more anchor locations of the data set by the anchor detection circuitry;

transferring each anchor locations to a de-duplication module executed by a processor of the storage system;

determining if the anchor location is located in a database;

if the anchor location is not located in the database, adding the anchor location to the database; and

if the anchor location is located in the database, performing the data de-duplication for the data set utilizing the anchor location, wherein the anchor detection circuitry and the processor are separate hardware devices.

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

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

7. The method of claim 4 further comprising utilizing a direct memory access operation to transfer the data set to the anchor detection circuitry.

8. The method of claim 4 wherein detecting the one or more anchor locations further comprises performing a rolling hash on the data set.

9. A system, comprising:

anchor detection hardware configured to receive a data stream, the anchor detection hardware further configured to identify one or more anchor locations of the data stream where the anchor detection hardware is a hardware device dedicated to identifying each anchor location, the anchor detection hardware further configured to transfer the anchor location to a de-duplication module executed by a processor of the storage system; and

the de-duplication module executed by the processor and configured to;

(i) determine if the anchor location is located in a database, (ii) add the anchor location to the database if the anchor location is not located in the database, and (iii) identify duplicate data using the anchor location and remove the duplicate data from the received data stream if the anchor location is located in the database, wherein the anchor detection hardware and the processor are separate hardware devices.

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

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

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

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

14. The system of claim 9 wherein the data stream comprises a tape backup data stream.

15. The system of claim 9 wherein the anchor detection hardware identifies the one or more anchor locations by performing a rolling hash on the data stream.

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

17. The system of claim 9 wherein the one or more anchor locations are stored in a data store, and wherein the de-duplication module utilizes the one or more anchor locations in the data store to perform the data de-duplication on the data stream.

18. The system of claim 9 wherein the data de-duplication of the data stream occurs prior to storing the data stream on a storage device.

19. A system comprising:

means for receiving a data set from a client;

means for transferring the data set to an anchor detection hardware of a storage system in response to receiving the data set;

means for detecting one or more anchor locations in the data set by the anchor detection hardware that is a hardware device dedicated for detecting anchor locations;

means for transferring each anchor location from the anchor detection hardware to a de-duplication module executed by a processor of the storage system, wherein the anchor detection hardware and the processor are separate hardware devices; and

means for determining if the anchor location is located in a database in response to transferring the anchor location;

means for adding the anchor location to the database if the anchor location is not located in the database;

means for examining bits preceding the anchor location utilizing a first delta value and means for examining the bits following the anchor location utilizing a second delta value to identify duplicate data if the anchor location is located in the database; and

means for removing the duplicate data from the data set prior to storing the data set on a storage device operatively connected to the storage system.

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