Accelerated deduplication

• US 9,569,456 B2
• Filed: 10/20/2014
• Issued: 02/14/2017
• 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/518,063
• Publication Number:
  US 20150039571A1
• Time in Patent Office: 848 Days
• Field of Search: 707/692
• US Class Current: 1/1
• 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 system comprising:

a processor configured to maintain a state machine providing a scatter-gather vector, the scatter-gather vector designating a plurality of memory areas for chunk boundary identification and chunk fingerprinting for a data stream, wherein the processor does not perform deduplication; and

a deduplication accelerator configured to access the memory areas designated in the scatter-gather vector to delineate a respective chunk boundary in a single pipeline stage and determine a respective chunk fingerprint for each of a plurality of data chunks in the same pipeline stage, the deduplication accelerator being a specially configured hardware accelerator separate from the processor and specifically configured for deduplication.

2. The system recited in claim 1, the system further comprising:

a deduplication dictionary configured to indicate whether a designated chunk has previously been written to persistent storage.

3. The system recited in claim 2, wherein the system is configured to communicate to the processor a final destination direct memory address for the designated chunk when it is determined that the designated chunk has not previously been written to persistent storage.

4. The system recited in claim 2, wherein the deduplication dictionary includes a plurality of chunk identifiers corresponding to a plurality of storage locations for the plurality of data chunks.

5. The system recited in claim 1, wherein chunk boundary calculation and chunk fingerprint calculation are performed in a single pass.

6. The system recited in claim 1, wherein the processor is configured to perform data stream optimization without performing chunk boundary calculation and chunk fingerprint calculation on the data stream.

7. The system recited in claim 1, wherein determining the respective chunk fingerprint comprises calculating a hash for the respective chunk delineated by identified chunk boundaries.

8. The system recited in claim 1, wherein the deduplication accelerator is an application specific integrated circuit (ASIC).

9. The system recited in claim 1, wherein the deduplication accelerator is a programmable logic device.

10. A method comprising:

maintaining, by a processor, a state machine providing a scatter-gather vector, the scatter-gather vector designating a plurality of memory areas for chunk boundary identification and chunk fingerprinting for a data stream, wherein the processor does not perform deduplication; and

accessing the memory areas designated in the scatter-gather vector with a deduplication accelerator to delineate a respective chunk boundary in a single pipeline stage and determine a respective chunk fingerprint for each of a plurality of data chunks in the same pipeline stage, the deduplication accelerator being a specially configured hardware accelerator separate from the processor and specifically configured for deduplication.

11. The method recited in claim 10, the method further comprising:

accessing a deduplication dictionary to indicate whether a designated chunk has previously been written to persistent storage.

12. The method recited in claim 11, the method further comprising:

communicating to the processor a final destination direct memory address for the designated chunk when it is determined that the designated chunk has not previously been written to persistent storage.

13. The method recited in claim 11, wherein the deduplication dictionary includes a plurality of chunk identifiers corresponding to a plurality of storage locations for the plurality of data chunks.

14. The method recited in claim 10, wherein chunk boundary calculation and chunk fingerprint calculation are performed in a single pass.

15. The method recited in claim 10, wherein the processor is configured to perform data stream optimization without performing chunk boundary calculation and chunk fingerprint calculation on the data stream.

16. The method recited in claim 10, wherein determining the respective chunk fingerprint comprises calculating a hash for the respective chunk delineated by identified chunk boundaries.

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

18. The method recited in claim 10, wherein the deduplication accelerator is a programmable logic device.

19. One or more computer readable media having instructions stored thereon for performing a method, the method comprising:

maintaining, by a processor, a state machine providing a scatter-gather vector, the scatter-gather vector designating a plurality of memory areas for chunk boundary identification and chunk fingerprinting for a data stream, wherein the processor does not perform deduplication; and

accessing the memory areas designated in the scatter-gather vector with a deduplication accelerator to delineate a respective chunk boundary in a single pipeline stage and determine a respective chunk fingerprint for each of a plurality of data chunks in the same pipeline stage, the deduplication accelerator being a specially configured hardware accelerator separate from the processor and specifically configured for deduplication.

20. The one or more computer readable media recited in claim 19, the method further comprising:

accessing a deduplication dictionary to indicate whether a designated chunk has previously been written to persistent storage.