Reduced bandwidth data uploading in data systems

• US 9,116,909 B2
• Filed: 12/29/2010
• Issued: 08/25/2015
• Est. Priority Date: 12/29/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, James Christopher III
• Primary Examiner(s): Joo, Joshua
• Assistant Examiner(s): Naji, Younes
• Application Number:
  US12/981,397
• Publication Number:
  US 20120173656A1
• Time in Patent Office: 1,700 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 67/1085 involving dynamic management of active down- or uploading connections
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data

Abstract

Methods and apparatus for uploading data from a sender to a receiver. A data deduplication technique is described that may reduce the bandwidth used in uploading data from the sender to the receiver. In the technique, the receiver, rather than the sender, maintains a fingerprint dictionary for previously uploaded data. When a sender has additional data to be uploaded, the sender extracts fingerprints for units of the data and sends the fingerprints to the receiver. The receiver checks its fingerprint dictionary to determine the data units to be uploaded and notifies the sender of the identified units, which then sends the identified units of data to the receiver. The technique may, for example, be applied in virtualized data store systems to reduce bandwidth usage in uploading data.

Claims

1. A system, comprising:

one or more hardware devices configured to implement a data receiver of a network-based virtualized data store service, the network-based virtualized data store service configured to provide remote virtualized data storage services over a network for a plurality of virtualized data store customers of the network-based virtualized data store service, wherein the data receiver locally stores fingerprints for data to a fingerprint dictionary, wherein the data comprises a plurality of data units, and wherein each fingerprint in the fingerprint dictionary uniquely identifies a respective data unit in the data; and

one or more hardware devices configured to implement a given customer site for one of the plurality of the virtualized data store customers, the given customer site comprising;

one or more data clients;

a customer network; and

a data sender configured as a virtualized data store gateway between the given customer site and the network-based virtualized data store service, wherein the data sender locally caches a plurality of data units, and wherein the locally cached data units are configured to be accessed over the customer network by the one or more data clients of the given customer site, the data sender configured to;

generate fingerprints for the plurality of data units of locally cached data, wherein each fingerprint uniquely identifies a respective data unit in the locally cached data; and

send the fingerprints to the data receiver via a communications channel;

wherein the data receiver is configured to;

search the fingerprint dictionary for the fingerprints received from the data sender to determine if each of the fingerprints is in the fingerprint dictionary or is not in the fingerprint dictionary, wherein determining that a fingerprint is not in the fingerprint dictionary indicates a corresponding data unit to be uploaded; and

send, to the data sender via the communications channel, an indication of one or more data units to be uploaded as determined by said search the fingerprint dictionary;

wherein the data sender is configured to send, to the data receiver via the communications channel, the indicated one or more data units, wherein only data units corresponding to fingerprints that are not in the fingerprint dictionary are sent to the data receiver.

2. The system as recited in claim 1, wherein the data receiver is further configured to, after said receiving the indicated one or more data units from the data sender:

determine that at least one fingerprint that said search indicated was in the fingerprint dictionary has subsequently been deleted from the fingerprint dictionary;

send, to the data sender via the communications channel, an indication of at least one data unit corresponding to the at least one fingerprint; and

receive, from the data sender via the communications channel, the indicated at least one data unit.

3. The system as recited in claim 1, wherein the communications channel is the Internet.

4. The system as recited in claim 1, wherein the data receiver stores the data in a data store, and wherein the data receiver stores the one or more data units received from the data sender to the data store.

5. The system as recited in claim 4, wherein the network comprises the communications channel, wherein the data receiver provides the data store as a virtualized data store to the plurality of virtualized data store customers via the network, and wherein the data stored in the data store includes customer data for each of the plurality of customers.

6. The system as recited in claim 5, wherein the fingerprint dictionary includes fingerprints for the customer data of the plurality of virtualized data store customers, wherein the data receiver associates a customer identifier with each customer, and wherein, in said search the fingerprint dictionary, the data receiver searches only among the fingerprints corresponding to the respective customer data according to the customer identifier of the respective customer.

7. The system as recited in claim 1, wherein the data sender is communicatively coupled to the customer network of the customer site, wherein the communications channel is a communications channel via a global network, and wherein the data sender:

downloads and locally caches portions of the data from the data receiver via the global network; and

provides local access to the downloaded and locally cached portions of the data to other processes on the customer network including one or more virtual computing systems implemented on other devices on the customer network.

8. The system as recited in claim 7, wherein the data sender is allocated a portion of bandwidth on the communications channel, and wherein the data sender is configured to request allocation of additional bandwidth on the communications channel as needed, and to release bandwidth on the communications channel when not needed.

9. A device, comprising:

at least one processor; and

a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to implement a virtualized data store gateway of a given customer site, the given customer site comprising one or more data clients connected to the virtualized data store gateway via a customer network, the given customer site for a given one of a plurality of virtualized data store customers of a remote network-based virtualized data store service that provides remote storage services over a network for the plurality of virtualized data store customers, the virtualized data store gateway providing a storage gateway between the given customer site and the remote network-based virtualized data store service, the program instructions further executable to cause the virtualized data store gateway to;

locally cache a plurality of data units from the one or more data clients connected to the virtualized data store gateway via the customer network of the given customer of the plurality of virtualized data store customers of the remote network-based virtualized data store service;

provide access to the locally cached customer data units to the one or more data clients of the given customer of the plurality of virtualized data store customers;

generate fingerprints for the plurality of data units of locally cached data units, wherein each fingerprint uniquely identifies a respective data unit in the locally cached data units;

send the fingerprints to the remote network-based virtualized data store service via the network, wherein the remote network-based virtualized data store service maintains a primary data store of the plurality of data units;

receive, from the remote network-based virtualized data store service via the network, an indication of one or more of the data units that are to be stored to the primary data store; and

send, via the network to the remote network-based virtualized data store service, the one or more data units for storage, by the remote network-based virtualized data store service, to the primary data store.

10. The device as recited in claim 9, wherein, to generate a fingerprint for a data unit, the program instructions are executable by the at least one processor to apply a hash function to the data unit.

11. The device as recited in claim 10, wherein the hash function is a cryptographic one-way hash function.

12. The device as recited in claim 9, wherein the locally cached data units are cached as a plurality of data blocks, wherein the plurality of locally cached data units correspond to one of the plurality of data blocks.

13. The device as recited in claim 12, wherein the one of the plurality of data blocks is marked as dirty to indicate that the locally cached data block has been created or modified and thus requires uploading from the data sender to the primary data store.

14. The device as recited in claim 9, wherein the remote network-based virtualized data store service provides a virtualized data store to the plurality of virtualized data store customers via the network, wherein data stored in the virtualized data store includes customer data for each of the plurality of virtualized data store customers, and wherein the device is associated with one of the plurality of virtualized data store customers.

15. The device as recited in claim 14, wherein the device is communicatively coupled to the customer network of the customer site, and wherein the program instructions are executable by the at least one processor to:

download and locally cache portions of the customer data from the remote network-based virtualized data store service; and

provide local access to the downloaded and locally cached portions of the customer data to other processes on the network including one or more virtual computing systems implemented on other devices on the customer network.

16. The device as recited in claim 15, wherein the downloaded and locally cached portions of the customer data are data blocks according to a block-based storage technique.

17. The device as recited in claim 9, wherein the device is allocated a portion of bandwidth on a communications channel to the remote network-based virtualized data store service via the network, and wherein the program instructions are executable by the at least one processor to request allocation of additional bandwidth on the communications channel for uploading data units to the remote network-based virtualized data store service as needed, and to release bandwidth on the communications channel when not needed.

18. A method, comprising:

providing a virtualized data store gateway between a given customer site of a given customer of a plurality of virtualized data store customers of a remote network-based virtualized data store service that provides remote storage services over a network for the plurality of virtualized data store customers, the given customer site comprising;

one or more data clients connected to a customer network and the virtualized data store gateway, wherein providing the virtualized data store gateway comprises;

locally caching at the virtualized data store gateway, a plurality of data units from the one or more data clients connected to the virtualized data store gateway via the customer network of the given customer of the plurality of virtualized data store customers;

providing access to the locally cached data units to the one or more data clients of the given customer of the plurality of virtualized data store customers;

generating fingerprints for the plurality of data units of locally cached data units, wherein each fingerprint uniquely identifies a respective data unit in the locally cached data units;

sending the fingerprints to the remote network-based virtualized data store service via a communications channel;

receiving, from the remote network-based virtualized data store service via the communications channel, an indication of one or more of the data units that are to be uploaded to the remote network-based virtualized data store service via the communications channel; and

sending, via the communications channel to the remote network-based virtualized data store service, the indicated one or more data units.

19. The method as recited in claim 18, wherein generating fingerprints for the plurality of data unit comprises applying a cryptographic one-way hash function to the data units.

20. The method as recited in claim 18, wherein the locally cached data units are cached as a plurality of data blocks, wherein the plurality of data units correspond to one of the plurality of data blocks.

21. The method as recited in claim 20, wherein the one of the plurality of data blocks is marked as dirty to indicate that the locally cached data block has been created or modified and thus requires uploading from the data sender to the network-based virtualized data store service.

22. The method as recited in claim 18, wherein the remote network-based virtualized data store service is a remote data storage service that maintains a primary data store of the plurality of data units.

23. The method as recited in claim 18, wherein the network comprises the communications channel.

24. The method as recited in claim 23, wherein the network-based virtualized data store service provides a virtualized data store to the plurality of virtualized data store customers via the network, and wherein data stored in the virtualized data store includes customer data for each of the plurality of virtualized data store customers, and wherein the virtualized data store gateway is associated with one of the plurality of virtualized data store customers.

25. The method as recited in claim 23, wherein the virtualized data store gateway is communicatively coupled to the customer network of the given customer site, and wherein the method further comprises:

downloading and locally caching portions of the customer data from the network-based virtualized data store service; and

providing local access to the downloaded and locally cached portions of the customer data to other processes on the local network including one or more virtual computing systems implemented on devices on the customer network.

26. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement:

providing a virtualized data store gateway between a given customer site of a given customer of a plurality of virtualized data store customers of a remote network-based virtualized data store service that provides remote storage services over a network for the plurality of virtualized data store customers, the given customer site comprising;

the virtualized data store gateway and one or more data clients connected to the virtualized data store gateway via a local network, wherein to provide the virtualized data store gateway the program instructions are further computer-executable to implement;

locally caching at the virtualized data store gateway a plurality of data units from the one or more data clients connected to the virtualized data store gateway via the local network of the given customer of the plurality virtualized data store customers;

providing access to the locally cached data units to the one or more data clients of the given customer of the plurality of virtualized data store customers;

generating fingerprints for the plurality of data units of locally cached data units, wherein each fingerprint uniquely identifies a respective data unit in the locally cached data units;

sending the fingerprints to the remote network-based virtualized data store service via a communications channel;

receiving, from the remote network-based virtualized data store service via the communications channel, an indication of one or more of the data units that are to be uploaded to the remote network-based virtualized data store service via the communications channel; and

sending, via the communications channel to the remote network-based virtualized data store service, the indicated one or more data units.

27. The non-transitory computer-accessible storage medium as recited in claim 26, wherein, to generate a fingerprint for a data unit, the program instructions are computer-executable to implement applying a hash function to the data unit.

28. The non-transitory computer-accessible storage medium as recited in claim 27, wherein the hash function is a cryptographically strong one-way hash function.

29. The non-transitory computer-accessible storage medium as recited in claim 26, wherein the locally cached data units are cached as a plurality of data blocks, wherein the plurality of data units correspond to one of the plurality of data blocks.

30. The non-transitory computer-accessible storage medium as recited in claim 29, wherein the one of the plurality of data blocks is marked as dirty to indicate that the locally cached data block has been created or modified and thus requires uploading from the data sender to the network-based virtualized data store service.

31. The non-transitory computer-accessible storage medium as recited in claim 26, wherein the network-based virtualized data store service is a remote data storage service that maintains a primary data store of the plurality of data units.

32. The non-transitory computer-accessible storage medium as recited in claim 26, wherein the network comprises the communications channel.

33. The non-transitory computer-accessible storage medium as recited in claim 32, wherein the network-based virtualized data store service provides a virtualized data store to the plurality of virtualized data store customers via the network, wherein data stored in the virtualized data store includes customer data for each of the plurality of virtualized data store customers.

34. The non-transitory computer-accessible storage medium as recited in claim 32, wherein the virtualized data store gateway is communicatively coupled to the local network of the given customer site, and wherein the program instructions are computer-executable to implement:

downloading and locally caching portions of the customer data from the network-based virtualized data store service; and

providing local access to the downloaded and locally cached portions of the customer data to other processes on the local network including one or more virtual computing systems implemented on devices on the local network.

35. The non-transitory computer-accessible storage medium as recited in claim 34, wherein the downloaded and locally cached portions of the customer data are data blocks according to a block-based storage technique.