Reduced Bandwidth Data Uploading in Data Systems

• US 20120173656A1
• Filed: 12/29/2010
• Published: 07/05/2012
• Est. Priority Date: 12/29/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sorenson, James Christopher III
• Granted Patent: US 9,116,909 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• 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 devices implementing a data receiver, 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 devices implementing a data sender configured to;

generate fingerprints for a 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 searching 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 searching 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 communications channel is a network, wherein the data receiver provides the data store as a virtualized data store to a plurality of customers via the network, wherein the data stored in the data store includes customer data for each of the plurality of customers, wherein the data sender corresponds to one of the plurality of customers, and wherein the data sender locally caches at least a portion of the customer data of the respective customer from the data store.

6. The system as recited in claim 5, wherein the fingerprint dictionary includes fingerprints for the customer data of the plurality of customers, wherein the data receiver associates a customer identifier with each customer, and wherein, in said searching 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 a local network of a 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 locally cached data to other processes on the local network including one or more virtual computing systems implemented on other devices on the local 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;

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

send the fingerprints to a remote data storage service via a network, wherein the remote data storage service maintains a primary data store of the data;

receive, from the remote data storage 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 data storage service, the one or more data units for storage, by the remote data storage 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 cryptographically strong one-way hash function.

12. The device as recited in claim 9, wherein the locally cached data is cached as a plurality of data blocks, wherein the plurality of 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 locally cached data to the primary data store.

14. The device as recited in claim 9, wherein the remote data storage service provides a virtualized data store to a plurality of customers via the network, wherein data stored in the virtualized data store includes customer data for each of the plurality of customers, wherein the device is associated with one of the plurality of customers, and wherein the program instructions are executable by the at least one processor to locally cache at least a portion of the customer data of the respective customer from the data store.

15. The device as recited in claim 14, wherein the device is communicatively coupled to a local network of a 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 data storage service; and

provide local access to the locally cached customer data to other processes on the local network including one or more virtual computing systems implemented on other devices on the local 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 data storage 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 data storage service as needed, and to release bandwidth on the communications channel when not needed.

18. A method, comprising:

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

sending the fingerprints to a data service via a communications channel;

receiving, from the data service via the communications channel, an indication of one or more of the data units that are to be uploaded to the data service via the communications channel; and

sending, via the communications channel to the data service, the indicated one or more data units.

19. The method as recited in claim 18, wherein, to generate a fingerprint for a data unit, the program instructions are computer-executable to implement applying a cryptographically strong one-way hash function to the data unit.

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

22. The method as recited in claim 18, wherein the data service is a remote data storage service that maintains a primary data store of the data.

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

24. The method as recited in claim 23, wherein the data service provides a virtualized data store to a plurality of customers via the network, wherein data stored in the virtualized data store includes customer data for each of the plurality of customers, wherein the device is associated with one of the plurality of customers, and wherein the program instructions are computer-executable to implement locally caching at least a portion of the customer data of the respective customer from the data store.

25. The method as recited in claim 23, wherein the device is communicatively coupled to a local network of a customer site, and wherein the program instructions are computer-executable to implement:

downloading and locally caching portions of the customer data from the data service; and

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

21. The method as recited in claim 21, 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 locally cached data to the data service.

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

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

sending the fingerprints to a data service via a communications channel;

receiving, from the data service via the communications channel, an indication of one or more of the data units that are to be uploaded to the data service via the communications channel; and

sending, via the communications channel to the data 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 is 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 locally cached data to the data service.

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

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

33. The non-transitory computer-accessible storage medium as recited in claim 32, wherein the data service provides a virtualized data store to a plurality of customers via the network, wherein data stored in the virtualized data store includes customer data for each of the plurality of customers, wherein the device is associated with one of the plurality of customers, and wherein the program instructions are computer-executable to implement locally caching at least a portion of the customer data of the respective customer from the data store.

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

downloading and locally caching portions of the customer data from the data service; and

providing local access to the locally cached customer data to other processes on the local network including one or more virtual computing systems implemented on other 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.