Single-ended deduplication using cloud storage protocol

• US 9,317,377 B1
• Filed: 03/23/2011
• Issued: 04/19/2016
• Est. Priority Date: 03/23/2011
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Wu, David Tze-Si, Cho, John S.
• Primary Examiner(s): Keehn, Richard G
• Assistant Examiner(s): Ahmed, Mohammed
• Application Number:
  US13/070,064
• Time in Patent Office: 1,854 Days
• Field of Search: 709/217
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A single-ended optimized storage protocol enables storage clients or other devices to direct a remote data storage to copy data. In response to commands via the protocol, a remote data storage can copy portions of a data stream at the remote data storage to destination storage locations within the same or a different data stream. The protocol may be utilized for optimized transfer of data via a network to a remote data storage. An initial data stream is divided into segments. Redundant segments are removed from the data stream to form an optimized data stream, which is transferred to the remote data storage. Commands are issued to the remote data storage using the protocol to direct the remote data storage to reconstruct the initial data stream at the remote data storage using the optimized data stream and optionally segments from other data streams previously transferred to the remote data storage.

Claims

1. A method of transferring data to a remote data storage, the method comprising:

dividing, at a first network location, at least a portion of a first data stream into segments;

identifying a first segment in the first data stream that is a duplicate of a second segment in a second data stream, wherein the second data stream is stored in a remote data storage at a second network location;

removing, at the first network location, at least the first segment from the first data stream to form an optimized data stream;

recording, at the first network location, an identity and location of at least the first segment within the first data stream;

transferring the optimized data stream from the first network location to the remote data storage at the second network location;

generating, at the first network location, a copy command that at least identifies the second data stream, a source location of the second segment within the second data stream, a source length of the second segment, and a destination location of the removed first segment within the optimized data stream, wherein the recorded identity and location of the first segment within the first data stream is used to generate the copy command; and

sending the copy command from the first network location to the remote data storage at the second network location, wherein the remote data storage executes the copy command which causes the remote data storage to copy the second segment from the source location in the second data stream to the destination location in the optimized data stream, thereby reconstructing the first data stream in the remote data storage at the second network location without transferring any portion of the optimized data stream or the first segment back to the first network location, and wherein the remote data storage does not require an optimization device to reconstruct the first data stream.

2. The method of claim 1, wherein the identified second data stream is the first data stream, and wherein, upon receiving the copy command, the remote data storage copies the second segment stored by the remote data storage to at least one destination location in the optimized data stream.

3. The method of claim 2, wherein the first segment is included in the optimized data stream.

4. The method of claim 2, wherein the first segment is included in a second data stream previously transferred to the remote data storage.

5. The method of claim 2, wherein the first segment is protected from modification and deletion by an additional storage client.

6. The method of claim 2, wherein the first segment is hidden from an additional storage client.

7. The method of claim 1, wherein identifying the portion of segments that are redundant comprises:

determining a data characterization for each of the segments of the first data stream; and

comparing the data characterizations with data characterizations of previously processed segments to identify segments of the first data stream matching previously processed segments.

8. The method of claim 7, wherein comparing the data characterizations of previously processed segments comprises:

accessing first records of the data characterizations stored at the first network location.

9. The method of claim 8, wherein the first records are associated with second records identifying storage locations at the remote data storage of the previously processed segments.

10. The method of claim 7, wherein comparing the data characterizations of previously processed segments comprises:

accessing metadata including the data characterizations from the remote data storage, wherein the metadata is associated with previously processed segments stored by the remote data storage.

11. The method of claim 10, wherein the metadata identifies the previously processed segments stored by the remote data storage.

12. The method of claim 1, wherein identifying the portion of segments that are redundant comprises:

comparing contents of the segments of the first data stream with contents of previously processed segments to identify segments of the first data stream matching previously processed segments.

13. The method of claim 1, wherein removing at least the first segment from the first data stream to form an optimized data stream comprises:

replacing the first segment with easily compressed data.

14. The method of claim 13, wherein the easily compressed data is equal in size to its corresponding segment that is removed from the first data stream.

15. The method of claim 1, wherein the first network location is connected with the second network location including the remote data storage via a wide-area network.

16. The method of claim 1, wherein the copy command does not include any portion of the first data stream.

17. The method of claim 2, wherein the copy command includes a source offset and a source ending offset instead of a source location and source length, respectively, of the first segment in the second data stream.

18. The method of claim 2, wherein the copy command includes at a destination offset specifying the destination location.

19. The method of claim 1, wherein the copy command is communicated via a web services protocol.

20. The method of claim 1, wherein the first data stream is received from a storage client.

21. The method of claim 20, wherein the first data stream is received via a web services protocol.

22. The method of claim 20, wherein the first data stream is received via a file protocol.

23. The method of claim 22, wherein the first data stream is received via a block based storage protocol.

24. The method of claim 2, wherein a single generated copy command is to restore a single data segment to the optimized data stream.

25. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for transferring data to a remote data storage, the method comprising:

dividing, at a first network location, at least a portion of a first data stream into segments;

identifying a first segment in the first data stream that is a duplicate of a second segment in a second data stream, wherein the second data stream is stored in a remote data storage at a second network location;

removing, at the first network location, at least the first segment from the first data stream to form an optimized data stream;

recording, at the first network location, an identity and location of at least the first segment within the first data stream;

transferring the optimized data stream from the first network location to the remote data storage at a second network location;

generating, at the first network location, a copy command that at least identifies data stream, a source location of the second segment within the second data stream, a source length of the second segment, and a destination location of the removed first segment within the optimized data stream, wherein the recorded identity and location of the first segment within the first data stream is used to generate the copy command; and

sending the copy command from the first network location to the remote data storage at the second network location, wherein the remote data storage executes the copy command which causes the remote data storage to copy the second segment from the source location in the second data stream to the destination location in the optimized data stream, thereby reconstructing the first data stream in the remote data storage at the second network location without transferring any portion of the optimized data stream or the first segment back to the first network location, and wherein the remote data storage does not require an optimization device to reconstruct the first data stream.

26. An apparatus for transferring data to a remote data storage, the apparatus comprising:

a processor; and

a memory storing instructions executable by the processor, the instructions comprising;

instructions to divide, at a first network location, at least a portion of a first data stream into segments;

instructions to identify a first segment in the first data stream that is a duplicate of a second segment in a second data stream, wherein the second data stream is stored in a remote data storage at a second network location;

instructions to remove, at the first network location, at least the first segment from the first data stream to form an optimized data stream;

instructions to record, at the first network location, an identity and location of at least the first segment within the first data stream;

instructions to transfer the optimized data stream from the first network location to the remote data storage at the second network location;

instructions to generate, at the first network location, a copy command that at least identifies the second data stream, a source location of the second segment within the second data stream, a source length of the second segment, and a destination location within the optimized data stream, wherein the recorded identity and location of the first segment within the first data stream is used to generate the copy command; and

instructions to send the copy command from the first network location to the remote data storage, wherein the remote data storage executes the copy command which causes the remote data storage to copy the second segment from the source location in the second data stream to the destination location in the optimized data stream, thereby reconstructing the first data stream in the remote data storage at the second network location without transferring any portion of the optimized data stream or the first segment back to the first network location, and wherein the remote data storage does not require an optimization device to reconstruct the first data stream.