Client-side deduplication with local chunk caching

• US 10,459,886 B2
• Filed: 08/06/2014
• Issued: 10/29/2019
• Est. Priority Date: 08/06/2014
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Tripathy, Tarun K., Smith, Brian R., Dinkar, Abhijit S.
• Primary Examiner(s): Tsui, Daniel D
• Application Number:
  US14/453,158
• Publication Number:
  US 20160041777A1
• Time in Patent Office: 1,910 Days
• Field of Search: None
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

Techniques and mechanisms described herein facilitate the transmission of a data stream from a client device to a networked storage system. According to various embodiments, a fingerprint for a data chunk may be identified by applying a hash function to the data chunk via a processor. The data chunk may be determined by parsing a data stream at the client device. A determination may be made as to whether the data chunk is stored in a chunk file repository at the client device. A block map update request message including information for updating a block map may be transmitted to a networked storage system via a network. The block map may identify a designated memory location at which the chunk is stored at the networked storage system.

Claims

1. A method, comprising:

at a client device comprising a processor and memory, identifying a fingerprint for a data chunk by applying a hash function to the data chunk via the processor, the data chunk determined by parsing a data stream at the client device, the data stream designated for storage at a networked storage system, using functions in a custom communications protocol interface, the custom communications protocol interface including a parser and a fingerprinter for facilitating client-side deduplication, the custom communications protocol interface being at the client device and being operable to communicate with at least one other module at the client device via a standard communications protocol, the custom communications protocol interface at the client device being operable to communicate with the networked storage system using at least one non-standard interaction;

determining whether the data chunk is stored in a local chunk cache at the client device;

verifying that the data chunk is correctly identified by comparing a first length of the data chunk determined by parsing the data stream with a second length of the data chunk stored in the local chunk cache; and

in response to a determination that the data chunk is not stored in the local chunk cache, determining whether the data chunk is stored at the networked storage system by transmitting the fingerprint to the networked storage system via the network;

in response to receiving a message from the networked storage system that the data chunk is not stored at the networked storage system, transmitting the data chunk and a block map update request message to the networked storage system via a network, the block map update request message including information to update a block map at the networked storage system, the block map identifying a designated memory location at which the data chunk is to be stored at the networked storage system; and

after the block map update request message is transmitted to the network storage system, storing the data chunk in a local chunk cache.

2. The method recited in claim 1, wherein determining whether the chunk is stored at the networked storage system further comprises receiving a fingerprint status message from the networked storage system, the fingerprint status message indicating whether the chunk associated with the fingerprint is stored at the networked storage system.

3. The method recited in claim 1, wherein determining whether the data chunk is stored in the local chunk cache comprises comparing the fingerprint for the data chunk with a fingerprint index associated with the local chunk cache.

4. The method recited in claim 1, wherein the designated memory location identifies an existing memory location associated with the data chunk when it is determined that the data chunk is stored at the networked storage system at the existing memory location.

5. The method recited in claim 1, wherein the data chunk is determined via a rolling hash parsing technique operable to generate at least some identical chunks when parsing different but overlapping data streams.

6. The method recited in claim 1, wherein the networked storage system is operable to store deduplicated data based on storage requests received via the network.

7. The method recited in claim 1, wherein the data stream is generated at the client device via a network storage protocol.

8. The method recited in claim 7, wherein the network storage protocol is a communications protocol selected from the group consisting of:

the Network File System (NFS) protocol, the Common Internet File System (CIFS) protocol, and the Open Storage (OST) protocol.

9. The method recited in claim 1, wherein the hash function is selected from a group consisting of:

MD5 and SHA-1.

10. A device comprising:

memory operable to store a fingerprint for a data chunk generated by applying a hash function to the data chunk, the data chunk determined by parsing a data stream at the device, the data stream designated for storage at a networked storage system;

a processor operable to;

determine whether the data chunk is stored in a local chunk cache at the client device;

verify that the data chunk is correctly identified by comparing a first length of the data chunk determined by parsing the data stream with a second length of the data chunk stored in the local chunk cache; and

in response to a determination that the data chunk is not stored in the local chunk cache, determine whether the data chunk is stored at the networked storage system by transmitting the fingerprint to the networked storage system via the network; and

a custom communications protocol interface operable to transmit a the data chunk and block map update request message to the networked storage system via a network in response to receiving a message from the networked storage system that the data chunk is not stored at the networked storage system, the block map update request message including information for updating a block map at the networked storage system, the block map identifying a designated memory location at which the data chunk is stored at the networked storage system, the custom communications protocol interface including a parser and fingerprinter for facilitating client-side deduplication, the custom communications protocol interface being at the client device and being operable to communicate with at least one other module at the client device via a standard communications protocol, the custom communications protocol interface at the client device being operable to communicate with the networked storage system using at least one non-standard interaction,

wherein the processor is further configured to store the data chunk in the local chunk cache, after the block map update request message is transmitted to the network storage system.

11. The device recited in claim 10, wherein determining whether the data chunk is stored at the networked storage system further comprises receiving a fingerprint status message from the networked storage system, the fingerprint status message indicating whether the chunk associated with the fingerprint is stored at the networked storage system.

12. The device recited in claim 10, wherein determining whether the data chunk is stored in the local chunk cache comprises comparing the fingerprint for the data chunk with a fingerprint index associated with the chunk cache.

13. The device recited in claim 10, wherein the designated memory location identifies an existing memory location associated with the data chunk when it is determined that the data chunk is stored at the networked storage system at the existing memory location.

14. One or more non-transitory computer readable media having instructions stored thereon for performing a method, the method comprising:

at a client device comprising a processor and memory, identifying a fingerprint for a data chunk by applying a hash function to the data chunk via a processor, the data chunk determined by parsing a data stream at the client device, the data stream designated for storage at a networked storage system, using functions in a custom communications protocol interface, the custom communications protocol interface including a parser and fingerprinter for facilitating client-side deduplication, the custom communications protocol interface being at the client device and being operable to communicate with at least one other module at the client device via the standard communications protocol, the custom communications protocol interface at the client device being operable to communicate with the networked storage system using at least one non-standard interaction;

determining whether the data chunk is stored in a local chunk cache at the client device;

verifying that the data chunk is correctly identified by comparing a first length of the data chunk determined by parsing the data stream with a second length of the data chunk stored in the local chunk cache;

in response to a determination that the data chunk is not stored in the local chunk cache, determining whether the data chunk is stored at the networked storage system by transmitting the fingerprint to the networked storage system via the network; and

in response to receiving a message from the networked storage system that the data chunk is not stored at the networked storage system, transmitting the data chunk and a block map update request message to the networked storage system via a network, the block map update request message including information to update a block map at the networked storage system, the block map identifying a designated memory location at which the data chunk is to be stored at the networked storage system;

wherein after the block map update request message is transmitted to the network storage system, storing the data chunk in a local chunk cache.

15. The one or more non-transitory computer readable media recited in claim 14, the method further comprising:

when it is determined that the data chunk is not stored in the local chunk cache, determining whether the data chunk is stored at the networked storage system by transmitting the fingerprint to the networked storage system via the network.