Back to results
US 8,943,023 B2Granted
Receiver-side data deduplication in data systems
AssigneeAmazon Technologies, Inc.
InventorJames Christopher Sorenson, III
Life of this patent
Estimating the term…
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.
Claims29
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 data store service configured to:
- store data for two or more clients of the data store service to a data store;
- store fingerprints for the data stored in the data store 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 stored in the data store;
- receive, from a device via a network, one or more fingerprints each corresponding to a different data unit cached at the device, wherein the device is a device of a given one of the two or more clients, wherein the data store service serves as a primary data store for data of the given client, and wherein the device locally caches only a portion of a the data of the given client stored remotely in the data store, wherein the locally cached data is configured to be accessed by one or more other devices 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 to the data store;
- 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.
8 more elements
A method, comprising:
- performing, by a data store service implemented on one or more computing devices:
- storing data for two or more clients of the data store service to a data store;
- storing fingerprints for the data stored in the data store 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 stored in the data store;
- receiving, from a device via a network, one or more fingerprints each corresponding to a different data unit cached at the device, wherein the device is a device of a given one of the two or more clients, wherein the data store service serves as a primary data store for data of the given client, and wherein the device locally caches only a portion of the data of the given client stored remotely in the data store, wherein the locally cached data is configured to be accessed by one or more other devices of the given client;
- searching the fingerprint dictionary for each of the one or more fingerprints received from the device to determine if the fingerprint 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 to the data store;
- 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;
- and
- 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.
5 more elements
A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement a data store service configured to:
- store data for two or more clients of the data store service to a data store;
- store fingerprints for the data stored in the data store 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 stored in the data store;
- receive, from a device via a network, one or more fingerprints each corresponding to a different data unit cached at the device, wherein the device is a device of a given one of the two or more clients, wherein the data store service serves as a primary data store for data of the given client, and wherein the device locally caches only a portion of the data of the given client stored remotely in the data store, wherein the locally cached data is configured to be accessed by one or more other devices of the given client;
- search the fingerprint dictionary for each of the one or more fingerprints received from the device to determine if the fingerprint 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 to the data store;
- send, 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;
- and
- 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.
4 more elements
Dependencies are inferred from the claim text.