Accelerated deduplication

• US 8,892,528 B2
• Filed: 08/26/2013
• Issued: 11/18/2014
• Est. Priority Date: 07/11/2011
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Dell Products LP (Dell Technologies Inc.)
• Inventors: Rao, Goutham, Jayaraman, Vinod
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US14/010,495
• Publication Number:
  US 20140032508A1
• Time in Patent Office: 449 Days
• Field of Search: 707/692, 707/687, 707/690, 707/698
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

Mechanisms are provided for accelerated data deduplication. A data stream is received an input interface and maintained in memory. Chunk boundaries are detected and chunk fingerprints are calculated using a deduplication accelerator while a processor maintains a state machine. A deduplication dictionary is accessed using a chunk fingerprint to determine if the associated data chunk has previously been written to persistent memory. If the data chunk has previously been written, reference counts may be updated but the data chunk need not be stored again. Otherwise, datastore suitcases, filemaps, and the deduplication dictionary may be updated to reflect storage of the data chunk. Direct memory access (DMA) addresses are provided to directly transfer a chunk to an output interface as needed.

Claims

1. A method, comprising:

performing, by using a processor, chunk boundary calculation and chunk fingerprint calculation on a data stream at a deduplication accelerator in a single pipeline stage, wherein chunk boundary calculation delineates a first chunk and chunk fingerprint calculation determines a chunk identifier for the first chunk, wherein chunk boundary calculation and chunk fingerprint calculation are used to perform deduplication on the data stream; and

accessing a deduplication dictionary using the chunk identifier to determine whether a first chunk has previously been written to persistent storage.

2. The method of claim 1, wherein chunk boundary calculation and chunk fingerprint calculation are performed in a single pass.

3. The method of claim 2, wherein a processor is operable to maintain a state machine used by the deduplication accelerator for chunk boundary calculation and chunk fingerprint calculation.

4. The method of claim 1, wherein the deduplication dictionary includes a plurality of chunk identifiers corresponding to a plurality of storage locations for a plurality of data chunks.

5. The method of claim 1, wherein chunk fingerprint calculation comprises calculating a hash for the first chunk delineated by identified chunk boundaries.

6. The method of claim 1, wherein the processor maintains a state machine and implements data stream optimization without performing chunk boundary calculation and chunk fingerprint calculation on the data stream.

7. The method of claim 1, wherein the processor uses direct memory access to transfer data to target addresses.

8. The method of claim 1, wherein the deduplication accelerator is an application specific integrated circuit (ASIC).

9. The method of claim 1, wherein the deduplication accelerator is a programmable logic device.

10. A deduplication accelerator, comprising:

an input interface configured to read a data stream;

a memory configured to maintain the data stream; and

logic configured to perform chunk boundary calculation and chunk fingerprint calculation for the data stream in a single pass read to perform data deduplication on the data stream, wherein chunk boundary calculation delineates a first chunk and chunk fingerprint calculation determines a chunk identifier for the first chunk, wherein the chunk identifier is used to access a deduplication dictionary to determine whether the first chunk has previously been written to persistent storage.

11. The deduplication accelerator of claim 10, wherein chunk boundary calculation and chunk fingerprint calculation are performed in a single pass.

12. The deduplication accelerator of claim 11, wherein a processor is operable to maintain a state machine used for chunk boundary calculation and chunk fingerprint calculation.

13. The deduplication accelerator of claim 10, wherein the deduplication dictionary includes a plurality of chunk identifiers corresponding to a plurality of storage locations for a plurality of data chunks.

14. The deduplication accelerator of claim 10, wherein chunk fingerprint calculation comprises calculating a hash for the first chunk delineated by identified chunk boundaries.

15. The deduplication accelerator of claim 10, wherein the processor maintains a state machine and implements data stream optimization without performing chunk boundary calculation and chunk fingerprint calculation on the data stream.

16. The deduplication accelerator of claim 10, wherein the processor uses direct memory access to transfer data to target addresses.

17. The deduplication accelerator of claim 10, wherein the deduplication accelerator is an application specific integrated circuit (ASIC).

18. The deduplication accelerator of claim 10, wherein the deduplication accelerator is a programmable logic device.

19. A system, comprising:

a deduplication accelerator configured to perform chunk boundary calculation and chunk fingerprint calculation on a data stream in a single pipeline stage, wherein chunk boundary calculation delineates a first chunk and chunk fingerprint calculation determines a chunk identifier for the first chunk, wherein chunk boundary calculation and chunk fingerprint calculation are used to perform deduplication on the data stream, wherein the data stream is maintained in memory; and

wherein a deduplication dictionary is accessed using the chunk identifier to determine whether a first chunk has previously been written to persistent storage.

20. The system of claim 19, wherein chunk boundary calculation and chunk fingerprint calculation are performed in a single pass.