Receiver-side data deduplication in data systems

• US 10,180,953 B2
• Filed: 01/26/2015
• Issued: 01/15/2019
• 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, III, James Christopher
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/605,843
• Publication Number:
  US 20150169665A1
• Time in Patent Office: 1,450 Days
• Field of Search: 707610, 707624- 7, 707632- 7, 707640, 707661, 707674, 707999204, 718 1
• 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/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/23 Updating

Abstract

Methods and apparatus for receiving uploaded data from a sender at 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:

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 remote multi-tenant data store service configured to;

store data for two or more clients to a data store of the remote multi-tenant data store service that is remote from the two or more clients, wherein each of the two or more clients are located on respective client sites;

store fingerprints to a fingerprint dictionary of the remote multi-tenant data store service, wherein respective fingerprints in the fingerprint dictionary uniquely identify respective data units of data stored in the data store at the multi-tenant data store service;

receive, from a gateway device via a network, at least one fingerprint corresponding to a respective data unit of a data volume, wherein the gateway device is located at a client site of a given one of the two or more clients, and wherein the data volume is generated or modified on the gateway device by a client device at the client site of the given client;

search the fingerprint dictionary for the at least one fingerprint to determine whether the fingerprint is in or is not in the fingerprint dictionary, wherein determining that the fingerprint is not in the fingerprint dictionary indicates the corresponding data unit is to be uploaded;

send, to the gateway device via the network, an indication of one or more data units to be uploaded as determined by said search; and

receive, from the gateway device via the network, the indicated one or more data units to store at the multi-tenant data store service.

2. The system as recited in claim 1, wherein each fingerprint is a hash of a respective data unit.

3. The system as recited in claim 2, wherein the hash is generated according to a cryptographically strong one-way hash function applied to the respective data unit.

4. The system as recited in claim 1, wherein the multi-tenant data store service is further configured to update the fingerprint dictionary with the fingerprint corresponding to each data unit received from the gateway device and stored to the multi-tenant data store service.

5. The system as recited in claim 1, wherein the data is stored at the multi-tenant data store service as data blocks, and wherein each data block comprises two or more data units.

6. The system as recited in claim 1, wherein the program instructions are executable by the at least one processor to provide the multi-tenant data store service 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, and wherein the gateway device locally caches at least a portion of the customer data of the respective customer from the data store.

7. The system as recited in claim 1, wherein the indication of one or more data units to be uploaded indicates data units for which a fingerprint was not found in the fingerprint dictionary by said search.

8. A method, comprising:

performing, by a remote multi-tenant data store service implemented on one or more computing devices;

storing data for two or more clients to a data store of the remote multi-tenant data store service that is remote from the two or more clients, wherein each of the two or more clients are located on respective client sites;

storing fingerprints for data stored in the data store to a fingerprint dictionary of the remote multi-tenant data store service, 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 stored in the data store;

receiving, from a device via a network, one or more fingerprints each corresponding to a different data unit of a data volume, wherein the device is located at a client site of a given one of the two or more clients, the client site being remote from the multi-tenant data store service, and wherein the data volume is generated or modified on the device by a client device at the client site of the given client;

searching the fingerprint dictionary for each of the one or more fingerprints received from the device to determine whether the fingerprint is in 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;

sending, to the device via the network, an indication of one or more data units to be uploaded as determined by said searching the fingerprint dictionary;

receiving, from the device via the network, the indicated one or more data units, wherein each received data unit corresponds to a fingerprint that is not in the fingerprint dictionary; and

storing the one or more data units received from the device to the data store.

9. The method as recited in claim 8, wherein each fingerprint is a hash of a respective data unit.

10. The method as recited in claim 9, wherein the hash is generated according to a cryptographically strong one-way hash function applied to the respective data unit.

11. The method as recited in claim 8, further comprising updating the fingerprint dictionary with fingerprints corresponding to the one or more data units received from the device and stored to the data store.

12. The method as recited in claim 8, wherein the multi-tenant data store service is configured to provide the data store as a virtualized data store to two or more clients via the network.

13. The method as recited in claim 8, further comprising:

associating a client identifier with each of two or more clients of the multi-tenant data store service; and

wherein said searching the fingerprint dictionary for each of the one or more fingerprints received from the device comprises searching only among the fingerprints corresponding to a given client according to the client identifier of the given client.

14. The method as recited in claim 8, further comprising:

after said receiving the indicated one or more data units from the device, determining that at least one fingerprint that said searching indicated was in the fingerprint dictionary has subsequently been deleted from the fingerprint dictionary;

in response to said determining, sending, to the device via the network, an indication of at least one data unit corresponding to the at least one fingerprint; and

receiving, from the device via the network, the indicated at least one data unit.

15. A non-transitory computer-accessible storage medium storing program instructions that when executed by one or more computers implement a remote multi-tenant data store service configured to:

store data for two or more clients to a data store of the remote multi-tenant data store service that is remote from the two or more clients, wherein each of the two are more clients are located on respective client sites;

store fingerprints for data stored in the data store to a fingerprint dictionary of the remote multi-tenant data store service, 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 stored in the data store;

receive, from a device via a network, one or more fingerprints each corresponding to a different data unit of a data volume, wherein the device is located at a client site of a given one of the two or more clients, the client site being remote from the multi-tenant data store service, and wherein the data volume is generated or modified on the device by a client device at the client site of the given client;

search the fingerprint dictionary for each of the one or more fingerprints received from the device to determine whether the fingerprint is in 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;

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

receive, from the device via the network, the indicated one or more data units, wherein each received data unit corresponds to a fingerprint that is not in the fingerprint dictionary; and

store the one or more data units received from the device to the data store.

16. The non-transitory computer-accessible storage medium as recited in claim 15, wherein each fingerprint is a hash of a respective data unit.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the hash is generated according to a cryptographically strong one-way hash function applied to the respective data unit.

18. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the multi-tenant data store service is further configured to update the fingerprint dictionary with the fingerprint corresponding to each data unit received from the device.

19. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the data comprises a plurality of data blocks, and wherein each data block comprises two or more of the plurality of data units.

20. The non-transitory computer-accessible storage medium as recited in claim 15, wherein the multi-tenant data store service is configured to provide the data store as a virtualized data store to two or more clients of the multi-tenant data store service via the network.