Accelerating transfer protocols

• US 9,917,894 B2
• Filed: 08/06/2014
• Issued: 03/13/2018
• 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): Chan, Wing F
• Assistant Examiner(s): KRISHNAN, RAJESHWARI
• Application Number:
  US14/453,121
• Publication Number:
  US 20160044100A1
• Time in Patent Office: 1,315 Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Techniques and mechanisms described herein facilitate the acceleration of data transfer protocols via client side de-duplication techniques for transmitting data from a client device to a networked storage system while maintaining protocol usage characteristics. while preserving the same presentation semantics to the users. A data chunk may be determined at a client device by parsing a data stream generated at the client device via a network storage protocol. A fingerprint for the data chunk may be identified by applying a hash function to the data chunk. A determination may be made as to whether the chunk is stored at a networked storage system by transmitting the fingerprint to the networked storage system via a network. The client device may transmit a block map update request message including information for updating a block map to the networked storage system.

Claims

1. A method executed by a client device comprising a processor and memory, the method comprising:

identifying a fingerprint for a designated data chunk by applying a hash function to the designated data chunk, the designated data chunk being determined by parsing a data stream at the client device to identify a plurality of data chunks, wherein the designated 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, the data stream generated at the client device via a first network storage protocol;

determining whether a data chunk associated with the fingerprint is stored at a networked storage system by transmitting the fingerprint to the networked storage system via a network, wherein data chunks are stored at the networked storage system according to a second network storage protocol, wherein the networked storage system parses data streams into data chunks via the rolling hash parsing technique used by the client device and the networked storage system determines fingerprints for data chunks using the hash function used by the client device;

responsive to a determination that a data chunk associated with the fingerprint is stored at the networked storage system, transmitting to a virtual file system of the networked storage system, a block map update information for updating a block map at the networked storage system, wherein the block map update information includes a first block map entry that points to the data chunk associated with the fingerprint that is stored at the networked storage system; and

when it is determined that a data chunk associated with the fingerprint is not stored at the networked storage system, transmitting the designated data chunk to the networked storage system for storage, along with a second block map update information including a second block map entry that points to the storage location of the transmitted designated data chunk.

2. The method recited in claim 1, wherein the block map uniquely identifies the plurality of data chunks in order.

3. The method recited in claim 1, wherein the block map includes location information identifying a respective location of each data chunk in either non-volatile memory or secondary storage at the networked storage system.

4. The method recited in claim 1, the method further comprising:

when it is determined that a data chunk associated with the fingerprint is stored at the networked storage system, identifying an existing memory location associated with the data chunk associated with the fingerprint, the existing memory location comprising a location in non-volatile memory or secondary storage at the networked storage system.

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

6. The method recited in claim 5, wherein the fingerprint status message indicates whether the data chunk associated with the fingerprint is stored at the networked storage system.

7. The method recited in claim 1, wherein the rolling hash parsing technique employs a Rabin-Karp algorithm.

8. 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.

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

a Secure Hash Algorithm (SHA) based function and a Message Digest (MD) based function.

10. A device comprising:

memory configured to store a fingerprint for a designated data chunk, the designated data chunk determined by parsing a data stream at the device to identify a plurality of data chunks, the fingerprint determined by applying a hash function to the designated data chunk, wherein the designated data chunk is determined via a designated rolling hash parsing technique operable to generate at least some identical chunks when parsing different but overlapping data streams, the data stream generated at the device via a first network storage;

a processor operable to determine whether a data chunk associated with the fingerprint is stored at a networked storage system by transmitting the fingerprint to the networked storage system via a network, wherein data chunks are stored at the networked storage system according to a second network storage protocol, wherein the networked storage system parses data streams into data chunks via the designated rolling hash parsing technique used by the client device and the networked storage system determines fingerprints for data chunks using the hash function used by the client device; and

a communications interface operable to;

transmit to a virtual file system of the networked storage system, responsive to a determination that a data chunk associated with the fingerprint is stored at the networked storage system, a block map update information for updating a block map at the networked storage system, wherein the block map update information includes a first block map entry that points to the data chunk associated with the fingerprint that is stored at the networked storage system, and

when it is determined that a data chunk associated with the fingerprint is not stored at the networked storage system, transmit the designated chunk to the networked storage system for storage, along with a second block map update information including a second block map entry that points to the storage location of the transmitted designated data chunk.

11. The device recited in claim 10, wherein the block map uniquely identifies the plurality of data chunks in order.

12. The device recited in claim 10, wherein the block map includes location information identifying a respective location of each data chunk in either non-volatile memory or secondary storage at the networked storage system.

13. The device recited in claim 10, wherein the processor is further operable to:

identify an existing memory location associated with the data chunk associated with the fingerprint when it is determined that the data chunk associated with the fingerprint is stored at the networked storage system, the existing memory location comprising a location in non-volatile memory or secondary storage at the networked storage system.

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

15. The device recited in claim 14, wherein the fingerprint status message indicates whether the data chunk associated with the fingerprint is stored at the networked storage system.

16. One or more non-transitory computer readable media having instructions stored thereon to cause a client device comprising a processor and memory to perform operations comprising:

identify a fingerprint for a designated data chunk by applying a hash function to the designated data chunk via the processor, the designated data chunk determined by parsing a data stream at the client device to identify a plurality of data chunks, wherein the designated 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, the data stream generated at the client device via a first network storage protocol;

determine whether a data chunk associated with the fingerprint is stored at a networked storage system by transmitting the fingerprint to the networked storage system via a network, wherein data chunks are stored at the networked storage system according to a second network storage protocol, wherein the networked storage system is configured to parse data streams into data chunks via the rolling hash parsing technique used by the client device and the networked storage system determines fingerprints for data chunks using the hash function used by the client;

responsive to a determination that the designated data chunk is stored at the networked storage system, transmit to a virtual file system of the networked storage system, a block map update information for updating a block map at the networked storage system, wherein the block map update information includes a first block map entry that points to the data chunk associated with the fingerprint that is stored at the networked storage system; and

when it is determined that a data chunk associated with the fingerprint is not stored at the networked storage system, transmitting the designated chunk to the networked storage system for storage, along with a second block map update information including a second block map entry that points to the storage location of the transmitted designated data chunk.