A method, comprising: providing a virtualized data store provider (110, 210, 300) comprising a data store (112, 216, 316) providing a virtualized data store to a plurality of customers via a network (200, 300) and a virtualized data store service (114, 212, 312), wherein the virtualized data store is accessed via the virtualized data store service and is configured to store data for the plurality of customers; storing fingerprints for data to a fingerprint dictionary of the virtualized data store service, wherein the data comprises a plurality of data units, wherein customer identifiers are associated with the fingerprints in the dictionary, and wherein each fingerprint in the fingerprint dictionary uniquely identifies a respective data unit in the data; receiving, from a virtualized data store gateway device of a customer of the plurality of customers via the network, one or more fingerprints each corresponding to a different data unit cached at the virtualized data store gateway device; searching, based on a customer identifier of the customer, the fingerprints associated with the customer identifier in the fingerprint dictionary for each of the one or more fingerprints received from the virtualized data store gateway 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 virtualized data store; sending, to the virtualized data store gateway 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 virtualized data store gateway 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 virtualized data store gateway device to the data store. providing a virtualized data store provider (110, 210, 300) comprising a data store (112, 216, 316) providing a virtualized data store to a plurality of customers via a network (200, 300) and a virtualized data store service (114, 212, 312), wherein the virtualized data store is accessed via the virtualized data store service and is configured to store data for the plurality of customers; storing fingerprints for data to a fingerprint dictionary of the virtualized data store service, wherein the data comprises a plurality of data units, wherein customer identifiers are associated with the fingerprints in the dictionary, and wherein each fingerprint in the fingerprint dictionary uniquely identifies a respective data unit in the data; receiving, from a virtualized data store gateway device of a customer of the plurality of customers via the network, one or more fingerprints each corresponding to a different data unit cached at the virtualized data store gateway device; searching, based on a customer identifier of the customer, the fingerprints associated with the customer identifier in the fingerprint dictionary for each of the one or more fingerprints received from the virtualized data store gateway 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 virtualized data store; sending, to the virtualized data store gateway 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 virtualized data store gateway 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 virtualized data store gateway device to the data store.