A receiver-side deduplication architecture for data storage systems, for example remote data storage systems that use block-based data storage and that provide the data storage to client(s) via a network. The architecture may provide network deduplication by reducing bandwidth usage on communications channel(s) between the client(s) and the data storage systems. The architecture may leverage block storage technology of a data store provided to clients by a data store provider and caching technology to implement a deduplication data dictionary. The deduplication data dictionary includes deduplication data blocks stored in the data store and a mapping tier that leverages caching technology to store and maintain a store of key/value pairs that map data block fingerprints to deduplication data blocks in the data store.

BACKGROUND

In many data systems, broadly viewed, a sender (a data source) uploads data to a receiver (a data processor) via a communications channel. An example of such a system is a data storage system; however, these data systems may include any system in which a receiver somehow processes data uploaded from a sender. The uploaded and processed data may include, but is not limited to, any type of textual, graphical, or image data, audio data (e.g., music and voice data), video data, compressed and/or encrypted data, and so on. In many such systems, large amounts of data may need to be uploaded from the sender to the receiver via the communications channel. However, communications channels generally have bandwidth constraints, while a goal of such data systems is to get as much usable data across the communications channel to the receiver as possible.

Data deduplication refers to techniques for reducing or eliminating redundant data in such systems, for example to improve storage utilization in a data storage system (referred to as data deduplication) and/or to reduce bandwidth usage on the communications channel (referred to as network data deduplication, or simply network deduplication). As an example, in at least some data deduplication techniques applied to data storage systems, the storage of duplicate data to a data store may be prevented. To achieve this, units of data that already reside in the data store, and/or units of data that do not reside in the data store, may be identified, and only the units that do not reside in the data store are stored or updated in the data store. Data deduplication in this application may thus reduce required storage capacity since fewer or only one copy of a particular unit of data is retained.

DETAILED DESCRIPTION

Various embodiments of methods and apparatus for receiver-side deduplication are described. Embodiments of a receiver-side deduplication architecture and deduplication techniques are described that may be applied in data storage systems to provide network deduplication by reducing bandwidth usage on the communications channel(s) between data sender(s) and the receiver (the data store provider). While primarily directed to network deduplication rather than data deduplication, some embodiments may also improve storage utilization in the data storage system by reducing the amount of data that is actually stored. For example, embodiments may be applied in remote data storage systems that use block-based data storage and that provide the data storage to client(s) as primary or backend storage.

In receiver-side deduplication, rather than the sender maintaining a fingerprint dictionary and determining data units to be uploaded to the receiver, the receiver maintains the fingerprint dictionary. When a sender has data to be uploaded, the sender extracts fingerprints (e.g., hashes) for the data and sends only the fingerprints to the receiver. The receiver checks its fingerprint dictionary to determine the data units to be uploaded to the receiver and notifies the sender, which then sends only the identified units of data to the receiver. Receiver-side deduplication thus reduces the bandwidth used in uploading data from the sender to the receiver as only the units that are not present in the data store according to the fingerprint dictionary are uploaded. Receiver-side deduplication removes or reduces the requirement for the sender to maintain a large fingerprint dictionary and centralizes deduplication at the receiver, thus allowing deduplication to be applied across data stored for multiple data sources.

However, conventional receiver-side deduplication architectures typically employ dedicated temporary storage, separate from the primary data store in which clients' data is stored, to maintain a backing store for deduplication data.

In embodiments of the receiver-side deduplication architecture and technique describe herein, instead of using separate, dedicated storage to maintain a backing store for deduplication data, the block storage technology of the data store provided by the data store provider and standard or commodity caching technology (e.g., Memcached technology) may be leveraged to implement a deduplication data dictionary.

The following describes embodiments of the receiver-side deduplication architecture as well as receiver-side data deduplication techniques including techniques that may be used to manage the components of the deduplication data dictionary. Embodiments of the receiver-side deduplication architecture and techniques may, for example, be implemented in the context of a service provider that provides remote data storage to clients via a network. For example, the service provider may provide access to the deduplication techniques to its clients that store data to the remote data storage via a deduplication Web service and Web service interface. An example implementation of the receiver-side deduplication architecture and techniques in the context of a service provider that provides remote data storage to clients via a storage service and a gateway appliance is described.

While embodiments of the receiver-side deduplication architecture and technique are generally described herein in reference to data storage system applications, the architecture and technique may be applied in any system in which a receiver receives data uploaded from a sender. The uploaded and processed data may include, but is not limited to, any type of textual, graphical, or image data, audio data (e.g., music or voice data), video data, compressed and/or encrypted data, and so on. In addition, while embodiments are generally described herein in terms of a sender and a receiver that are remotely located and communicate via a wired and/or wireless network such as the Internet, the data deduplication technique may also be applied in applications where the sender and receiver are local devices that communicate, for example, via a wired or wireless local network or direct link, as well as applications where the sender and receiver are hardware and/or software components within a single device or system that communicate via an internal communications channel such as a data bus, direct data link, shared memory transfer, or wireless communications channel.

FIG. 1is a high-level block diagram of a receiver-side deduplication architecture that may implement the deduplication techniques described herein, according to at least some embodiments. The deduplication architecture may, for example, be implemented in the context of a data store provider (receiver100) that provides access via a network (e.g., the Internet) to a block-based data store120, fronted by a data plane110, to one or more clients (e.g., sender150).FIG. 1shows a single sender150; however, there may be more than one sender150. Sender150may, for example, correspond to a single system such as a server, a collection of systems such as a server cluster, or a data center, but in general sender150may correspond to any device or system that may upload data to receiver100. In some implementations, sender data upload process160may be a process of or executing on a storage gateway284as shown inFIG. 7.

Data plane110may comprise one or more network devices (e.g., servers or host systems) that implement data store process(es)114that may provide an interface between the client(s) (e.g., via sender data upload process(es)160on the sender150side) and the data store120, and that may provide management logic (e.g., volume-based storage, data I/O, garbage collection, backup, mirroring, etc.) for the data store120. One or more receiver-side deduplication processes112of the deduplication architecture and technique may be implemented on the data plane110. Note that data store processes114and receiver-side deduplication processes112may be implemented on the same servers or host systems, or on different servers or host systems. In at least some embodiments, receiver100may provide one or more interfaces, for example Web services interfaces or APIs, via which a sender150may access functionality provided by the data plane110, including but not limited to the receiver-side deduplication functionality described herein.

Rather than using separate, dedicated storage to maintain a backing store for deduplication data units in the deduplication data dictionary, embodiments of the deduplication architecture and technique may leverage block storage technology of the data store120provided by the data store provider and caching technology to implement a deduplication data dictionary102. The deduplication data dictionary102includes the data store120that stores data units (data blocks124) stored in chunks122and a mapping tier104that leverages the caching technology to store and maintain key/value pairs132that map data block fingerprints (e.g., hashes) to deduplication data units (data blocks124) in the data store120. A chunk may be defined as a collection of data blocks. Each data block124thus represents a fraction of a chunk122in the data store120. As a non-limiting example, chunk size may be 4 megabytes (mB) and data block size may be 4 kilobytes (kB). In this example, there are 1 k (1000) data blocks124per chunk122. However, other chunk sizes and/or data block sizes may be used. The fingerprints (e.g., hashes) may uniquely identify the data units in the data storage system. In at least some embodiments, a fingerprint may be any type of cryptographically strong one-way hash function, for example a Secure Hash Algorithm (SHA)-256 hash function. The use of a cryptographically strong one-way hash function may provide security, and may help to avoid collisions, as collisions using such a hash function are highly unlikely. A collision is when two units of data produce the same fingerprint. However, in some embodiments, fingerprints may be generated according to any hashing technique, or other techniques than hashing may be used to generate fingerprints.

As noted, the data units stored in the data store120(e.g., chunks122) are used as the backing data store for the deduplication functionality. Advantages to using the chunks122in the data store120directly as the deduplication data store over using a separate, dedicated storage may include, but are not limited to:Cost per unit data in the deduplication dictionary102may be reduced when compared to conventional deduplication systems.Management logic for the deduplication data store may be significantly simplified. In particular, there may be no need for an eviction mechanism and free space management logic for the deduplication data store; existing management logic for the data store120may handle these and other data management functionalities for the data stored in data store120.Scalability, reliability, security, and other concerns may be inherently provided by the data store120management logic and thus do not have to be separately managed for the deduplication data store.

Note that the data store120is not the deduplication data store; instead, the data units (chunks122) of the data store120are leveraged to implement the deduplication data store. In other words, the deduplication data store is maintained within the data store120by using locations in the chunks122as storage locations for deduplication data blocks124. Note that data that is not in the deduplication data store may also be stored in the chunks122in data store120.

In at least some embodiments, the chunks122in data store120may be immutable. That is, the chunks122are guaranteed to be valid if they are present in data store120. To achieve immutability, when a portion (e.g., a data block124) or all of a given chunk122is changed by a client, a new chunk122is created and stored to the data store120by the data plane110, rather than overwriting or updating the original chunk122. A garbage collection process may periodically or aperiodically detect and delete (or invalidate) stale chunks122from the data store120.

In at least some embodiments, the mapping tier104may be implemented according to high-performance caching technology, and may be used to maintain a mapping between fingerprints (e.g., hashes) of data blocks124that are part of the data dictionary and the locations in the data store120at which the data blocks124are stored. For example, the location of a data dictionary data block124in data store120may be indicated by a chunk identifier that identifies the chunk122in which the respective deduplication data block124is stored, an offset into the chunk122at which the respective deduplication data block124is stored, and a size. Note that other information for and/or methods of identifying the location of a deduplication data block124may be used in some embodiments. For example, in some implementations of a data store, chunks may be versioned, and a chunk version identifier may be included in the information for each data block124. The fingerprints (e.g., hashes) and location information (also referred to herein as indexes) may be stored as key/value pairs132in mapping cache(s)130. In at least some embodiments, cache(s)130may be implemented according to high-speed caching technology, for example an in-memory cache.

In at least some embodiments, a cache service provided by a service provider may be leveraged to implement the mapping tier104of the deduplication data dictionary102. A service provider that provides “cloud” storage to clients via the data store120and a storage service may also provide a cache service for deploying, operating, and scaling, an in-memory cache in the cloud. The cache service may improve the performance of web applications by allowing the client to retrieve information from a fast, managed, in-memory caching system, instead of relying entirely on slower disk-based databases. For example, a cache service may be provided that is protocol-compliant with Memcached caching technology. Memcached is an open source, high-performance, distributed memory object caching system. Note, however, that the cache service may be implemented according to other caching technologies. Advantages of using the cache service provided by the service provider to implement the mapping tier104may include, but are not limited to:The cache service may provide a fast, managed, in-memory caching system that can be leveraged to implement the mapping cache(s)130.The cache service's cache management algorithm and cache management interface can be leveraged.The cache service provides mechanisms to scale up and scale down the mapping tier fleet.

However, some embodiments of the deduplication architecture may use other caching technologies to implement the mapping tier104. For example, a mapping tier104using other high-performance caching technology may be implemented, for example if such a cache service is not provided, or if custom cache eviction logic or other custom cache management logic that may not be provided by a cache service is necessary or desired.

FIGS. 2 through 4are flowcharts of an embodiment of a deduplication technique implemented according to the receiver-side deduplication architecture, for example as illustrated inFIG. 1.

FIG. 2is a flowchart of a technique for using the mapping cache to check for deduplication data blocks, according to at least some embodiments. As indicated at200, a sender150(e.g., a client of a service provider that provides data store120) sends fingerprints for data blocks in a chunk to the receiver100(e.g., the service provider) data plane110. For example, the sender150may need to upload a chunk of data to a primary data store or backing data store implemented on data store120, or may need to update a chunk of data already stored in data store120. To take advantage of the deduplication technique, a sender data upload process160may generate fingerprints (e.g., hashes) for at least one data block of the chunk that may need to be uploaded and send the fingerprint(s) to a receiver-side deduplication process112running on a host system on data plane110. In some implementations, sender data upload process160may be a process of or executing on a storage gateway284as shown inFIG. 7.

As indicated at202, after receiving the fingerprints, the data plane110may request the mapping tier104to search for the fingerprints. For example, the receiver-side deduplication process112may query a cache manager process of mapping tier104with the fingerprints, requesting a cache search and return of any cache “hits” in the cache130.

As indicated at204, the mapping tier104checks the mapping cache130using the fingerprints as keys. The check of the mapping cache130may result in no cache hits, or may result in one or more cache hits. In some embodiments, the mapping tier104may update an entry in a data structure for each cache entry for which there is a hit. This information may be used by a cache maintenance process to evict stale cache entries. In at least some embodiments, stale cache entries include cache entries that have not been accessed for a specified period and/or cache entries for which there has not been at least a threshold amount of activity for a specified period. The section Mapping cache implementations and optimizations describes implementations of the mapping tier104and mapping cache130in more detail, including methods for cache eviction. At206, if there are no cache hits on the fingerprints, then the mapping tier104may return an indication of no cache hits to the data plane110. In this case, there is no deduplication data in the deduplication data dictionary for the fingerprints sent from the sender data upload process160to the data plane110, and the method may go to element210.

At206, if there are cache hits on at least some of the fingerprints, then as indicated at208, for each cache hit, the mapping tier104retrieves the corresponding index from the mapping cache130. The mapping tier104then returns the located index(es) to the data plane110. In at least some embodiments, the mapping tier104may also return an indication of fingerprint(s) for which there was not a hit in the cache130.

As indicated at210, the data plane110validates the presence of the chunk(s)122indicated by the indexes returned from the mapping tier104in the data store120. As previously mentioned, in some implementations of data store120, the chunks122may be immutable (guaranteed to be valid if they are present in data store120). However, stale chunks122may have been garbage collected. Thus, the cache hits as indicated by the index(es) returned from the mapping cache104need to be validated against the data store120to determine if the chunks storing the deduplication data blocks indicated by the index(es) are still present in the data store120. If a respective chunk is not present, then the data block(s) that were in that chunk are no longer in the deduplication data store102, and thus these data blocks may need to be uploaded by the sender150. In addition, the mapping cache130needs to be updated to avoid future false positive hits.

FIG. 3is a flowchart of a technique for validating the presence of data blocks indicated by mapping cache hits in the deduplication data dictionary that may be used at element210ofFIG. 2in at least some embodiments. In at least some embodiments, the technique ofFIG. 3may be applied by the data plane110for each index returned from the mapping tier104. As indicated at300, the data plane110may check the data store120for presence of the chunk indicated by the index. For example, each index may include at least a chunk identifier, and the receiver-side deduplication process112may query a block data store process114with the chunk identifier to determine if the chunk122is present in data store120.

If a chunk122indicated by an index is not present in the data store120, then the deduplication data block that was previously stored in the chunk122is not present in the deduplication data dictionary102, and thus the corresponding cache entry need to be deleted to prevent further false positive hits. In addition, the respective data block may need to be uploaded from the client. At302, if it is determined that a chunk122indicated by an index returned from the mapping tier104is not present in the data store120, then the corresponding entry may be deleted from the mapping cache130, as indicated at304. For example, a receiver-side deduplication process112may direct the mapping tier104to delete the key/value pair(s)132corresponding to the chunk122that was determined to be not present in data store120. As indicated at306, an indication may be recorded that the respective data block is not in the deduplication data dictionary102. At302, if it is determined that a chunk122indicated by an index is present in the data store120, an indication may be recorded that the respective data block is in the deduplication data dictionary102.

Thus, the data plane110now may have the following information for the fingerprints that it received from the sender150:A list of fingerprints of data blocks that are not in the deduplication data dictionary102. This list may include fingerprints for which there was no hit in the cache130and/or fingerprints for which there was a hit in the cache130, but for which the respective deduplication data blocks were found to not be present in the data store120; andA list of fingerprints of data blocks that are in the deduplication data dictionary102. This list includes fingerprints for which there was a hit in the cache130and for which the respective deduplication data blocks were found to be present in the data store120.

Note that in some cases, one (but not both) of the above two lists may be empty. That is, it may be the case that none of the data blocks indicated by the fingerprints are in the deduplication data dictionary102, or that all of the data blocks indicated by the fingerprints are in the deduplication data dictionary102.

Referring again toFIG. 2, as indicated at212, the data plane110(e.g., a receiver-side deduplication process112) may return information to the sender150(e.g., to sender data upload process160) identifying one or more data blocks that need to be uploaded. This information may, for example, include the fingerprints of data blocks for which there is deduplication data in the deduplication data dictionary102. Alternatively, this information may include the fingerprints of data blocks for which there is no deduplication data in deduplication data dictionary102. As another alternative, this information may include all of the fingerprints with an indication for each as to whether there is corresponding deduplication data in deduplication data dictionary102. Note that only the blocks for which there is no deduplication data in deduplication data dictionary102may need to be uploaded.

In some embodiments, instead of returning some or all of the fingerprints, other information may be returned to indicate which data blocks need to be uploaded. For example, in some embodiments, a binary string or byte string may be returned that indicates, for all of the data blocks in a chunk, which data blocks need to be uploaded and which do not need to be uploaded. As a non-limiting example, a “1” at position n of the string may indicate that the data block at position n of the chunk is not in the data deduplication dictionary102and thus needs to be uploaded, while a “0” at position n of the string may indicate that the data block at position n of the chunk is in the data deduplication dictionary102and thus does not need to be uploaded.

As indicated at214, the sender150uploads the data blocks that were identified as needing to be uploaded to the data plane110. For example, sender data upload process160may send the data blocks in one or more packets to a block data store process114. The data plane110then constructs and uploads a new chunk to the data store120. The new chunk may include the data blocks received from the sender150and deduplication data blocks retrieved from the data store120. In at least some embodiments, a new data block may be stored in data store120while leaving the previous data block in the data store120. The previous data block120may later be garbage collected. Alternatively, in some embodiments, the new data block may overwrite the previous data block that is being updated. An example technique for constructing and storing new data blocks to the data store120is given inFIG. 4.

FIG. 4is a flowchart of a technique for constructing and uploading new chunks to the data store, according to at least some embodiments. As indicated at400, the data plane110retrieves chunk(s)122that include the deduplication data blocks from the data store120. For example, a block data store process114that received the data blocks uploaded from sender150may also have access to the cache hit information (e.g., the indexes) obtained from the mapping tier104at element304. The block data store process114may retrieve each chunk122indicated by the indexes from the data store120. Note that, in retrieving a chunk122, a copy of the chunk122may be downloaded from the data store120; the chunk122remains in the data store120.

As indicated at402, the data plane110extracts the deduplication data blocks124indicated by the cache hit information from the chunk(s) retrieved from the data store120. For example, each index may include, in addition to a chunk identifier, at least an offset into the chunk122at which the respective data block124is stored. In some implementations, the index may also include a size (e.g., in bytes) of the data block124. The block data store process114may use this information from the index to extract the data block124from the chunk122.

In some embodiments, instead of downloading the entire chunk(s) from data store120and extracting the deduplication data blocks, only the deduplication data blocks may be downloaded from the data store120.

As indicated at404, the data plane110may retrieve data blocks from a chunk in the data store120that is being updated by the sender150. In some embodiments, this may be performed by downloading a copy of the entire chunk from the data store120and extracting the needed data blocks. Alternatively, instead of downloading a copy of the entire chunk from data store120and extracting the data blocks, only the necessary data blocks may be downloaded from the data store120.

Note that, in most cases, deduplication data blocks for a chunk being updated may be stored in one or more other chunks in the data store120. However, in some cases, for example on a first update of a chunk that was previously uploaded by the sender150, all of the deduplication data blocks for a chunk may actually be in the chunk itself, as indicated by the mapping cache130which was updated with fingerprints and indexes for all of the data blocks in the chunk when the chunk was originally uploaded.

As indicated at406, the data plane110(e.g., the block data store process114) constructs a new chunk122that may, but does not necessarily, include one or more deduplication data blocks124extracted from the chunk(s) retrieved from the data store120, one or more data blocks retrieved from the chunk being updated, and one or more data blocks received from the sender150. As indicated at408, the data plane110uploads the new chunk122to the data store120. Note that, in uploading the new chunk122, a chunk identifier may be assigned to the chunk122. In at least some embodiments, a new data block may be stored in data store120while leaving the previous data block in the data store120. The previous data block120may later be garbage collected. Alternatively, in some embodiments, the new data block may overwrite the previous data block that is being updated.

As indicated at410, the data plane110updates the mapping cache130via the mapping tier104with fingerprints and indexes for all of the data blocks124in the new chunk122. For example, a data plane110process (e.g., a block data store process114) may generate fingerprints for each data block124in the new chunk122, construct an index (e.g., chunk identifier, offset, size) for each data block124, and send the fingerprints and corresponding indexes to the mapping tier104. The mapping tier104then writes the fingerprints and indexes as new key/value pairs132to the cache130.

FIGS. 5A through 5Hgraphically illustrate data flow in the receiver-side deduplication architecture and technique, according to at least some embodiments. Referring toFIG. 5A, receiver100implements a deduplication data dictionary that includes a mapping tier104and data store120, and includes a data plane110that implements block data store processes and receiver-side deduplication processes, as described herein.

Sender data upload process160may act as an interface between sender150and data plane110. Sender data upload process160may be implemented in hardware, software, or a combination thereof. In some implementations, sender data upload process160may be a process of or executing on a storage gateway284as shown inFIG. 7. The communications channel(s) between sender data upload process160and data plane110may be a relatively high-bandwidth connection or communications channel, as large amounts of data may need to be transferred across the network (e.g., the Internet) between sender data upload process160and data plane110.

Sender100may locally cache, store, or obtain data; receiver100may serve as a primary store or backing store for the data. As a non-limiting example, to improve data access times for users, rather than retrieving data from a data store120maintained by receiver100on demand, large blocks or chunks of data, even entire volumes of data, may be locally cached or stored at sender150as local data170. As another example, sender100may maintain local data170as a local primary data store and use data store120as a backing or mirroring data store for the local primary data store. Sender100may include physical data storage and/or memory on which local data170may be cached and/or stored. The data store120maintained by receiver100may thus serve as a primary data store or as a backing or mirroring data store for the client (sender100. In either case, sender data upload process160may communicate with data plane110to periodically, aperiodically, or continuously upload new or modified data in local data170to the data store120provided by the receiver100.

Sender data upload process160may, in at least some embodiments, maintain local data170in relatively large blocks or chunks, e.g. 4-megabyte chunks or 10-megabyte chunks, although larger or smaller chunk sizes may be used. Note that the chunk size used in local data170of sender150may be, but is not necessarily, the same as the chunk size used in data store120. When a chunk174(e.g., chunk174A) is accessed by a user or process at sender100, e.g. to create new data or modify existing data, the chunk174A may be marked as dirty. However, the access may have changed only a small portion of the chunk174A. Thus, as shown inFIG. 5A, the sender data upload process160may generate fingerprints180for units (data blocks) of the dirty chunk174A, for example by applying a hash function to each data block, or to only some of the data blocks, in the dirty chunk174A. In block-based data systems (for example, block storage systems), a unit of data may, for example, be a 128 k-byte data block, a 256 k-byte data block, a 1024 k-byte data block, or some other fixed or variable sized data block. (In file-based systems, a data block may be a file, or a portion of a file similar to the data blocks of a chunk in a block-based data system). As shown inFIG. 5A, the sender data upload process160may send the fingerprints180that were generated for the dirty chunk174A to the data plane110of the receiver100.

Referring toFIG. 5B, in response to receiving the fingerprints180from the sender150, the data plane110of the receiver100may query the mapping tier104with the fingerprints180. Mapping cache130stores previously received fingerprints134and data indexes136as key/value pairs. In at least some embodiments, standard or commodity caching technology (e.g., Memcached technology) may be leveraged to implement mapping tier104and mapping cache130. The mapping tier104checks mapping cache130for hits on the fingerprints180. If a fingerprint134in mapping cache130matches a fingerprint180received from sender150, the corresponding data index136is returned to data plane110as an index hit182. Note that there may be hits on one or more, or all, of the fingerprints180. However, in some cases, there may be no hits on the fingerprints180.

Referring toFIG. 5C, the data plane110validates the presence of the chunk(s)122indicated by the index hits182in the data store120. As previously mentioned, in some implementations of data store120, the chunks122may be immutable (guaranteed to be valid if they are present in data store120). However, stale chunks122may have been garbage collected. Referring toFIG. 5D, if it is determined that a chunk or chunks122indicated by the index hits182are not present in the data store120, then the data plane110may direct the mapping tier104to delete the key/value pair(s) in mapping cache130corresponding to the chunk(s)122that are not present in data store120. Note that, if a chunk122indicated by an index is not present in the data store120, the corresponding cache entries need to be deleted to prevent further false positive hits. In addition, the respective data blocks may need to be uploaded from the sender150.

Referring toFIG. 5E, the data plane110may determine, from the index hits182and according to the check for presence of chunks132as shown inFIGS. 5C and 5D, which of the data blocks need to be uploaded to the receiver100by the sender150. The data plane may then send indications of the data blocks to be uploaded to the sender data upload process160. The sender data upload process160may then extract the indicated data blocks (shown as new data blocks) from local data170(e.g., from data block174A) and send the new data blocks to data plane110.

Referring toFIG. 5F, the data plane110retrieves one or more chunks122including chunk(s) that include the deduplication data blocks indicated by the index hits182from the data store120. The data plane110may also retrieve the chunk being updated from the data store120. For example, if chunk122C is the chunk being updated by the sender150, and chunks122A and122B include deduplication data blocks as indicated by the index hits182, then the data plane110may retrieve chunks122A,122B, and122C from the data store120. Note that, in retrieving a chunk122, a copy of the chunk122may be downloaded from the data store120; the chunk122remains in the data store120. The data plane110extracts the deduplication data blocks indicated by the index hits182from the chunk(s) retrieved from the data store120. For example, each index hit182may include, in addition to a chunk identifier, at least an offset into the chunk122at which the respective data block is stored. In some implementations, the index hit182may also include a size (e.g., in bytes) of the data block. The data plane110may use this information from the index hits182to extract the data block(s) from the chunk(s) retrieved from data store120. The data plane110may also extract other data blocks from the chunk being updated. In some embodiments, instead of retrieving the entire chunks and extracting the data blocks from the retrieved chunks122, only the data blocks and/or the deduplication data blocks may be retrieved from chunks122in the data store.

Referring toFIG. 5G, the data plane110constructs a new chunk122that includes the deduplication data blocks extracted from the chunk(s) retrieved from the data store120, the other data blocks extracted from the chunk being updated, and the new data blocks received from the sender data upload manger160. The data plane110uploads the new chunk122to the data store120. Note that, in uploading the new chunk, a chunk identifier may be assigned to the chunk (the new chunk is shown as chunk122D in data store120). As shown inFIG. 5G, the new chunk122may be written as a new chunk122D while leaving the chunk being updated (e.g., chunk122C) in the data store. Alternatively, the chunk being updated (e.g., chunk122C) may be overwritten with the new chunk122.

Referring toFIG. 5H, the data plane110updates the mapping cache130via the mapping tier104with fingerprints and indexes for all of the data blocks in the new chunk122D. For example, a data plane110process may generate fingerprints (e.g., hashes) for each data block in the new chunk122D, construct an index (e.g., chunk identifier, offset, size) for each data block, and send the fingerprints and corresponding indexes to the mapping tier104. The mapping tier104then writes the fingerprints and indexes as new key/value pairs to the cache130.

Mapping Cache Implementations and Optimizations

In at least some embodiments of the receiver-side deduplication architecture, a cache service provided by a service provider may be leveraged to provide the mapping tier of the deduplication data dictionary. In at least some embodiments, the mapping cache may be implemented according to high-speed caching technology, for example an in-memory cache. In at least some embodiments, standard or commodity caching technology (e.g., caching Memcached technology) may be leveraged to implement the mapping cache and mapping tier.

In at least some embodiments, the deduplication technique may use information about the age or activity of a chunk to be replaced to mitigate cache updates. For example, the deduplication data dictionary may prioritize data blocks that do not change constantly. In at least some embodiments, an eviction mechanism used with the mapping cache may be driven by how recently fingerprints (e.g., hash values) were looked up or updated in the cache. In at least some embodiments of the cache eviction mechanism, more recent fingerprints may be retained in the cache, while fingerprints that have not been active for a specified period may be evicted from the cache. Note that other cache eviction techniques may be implemented in some embodiments.

FIG. 6is a flowchart of a cache eviction method, according to at least some embodiments. This method may be based on the assumption that, if there have been few or no deduplication hits for an entry in the past, then it is likely that there will be few or no deduplication hits for the entry in the future. For example, when checking the mapping cache for entries as indicated at500, the mapping tier may update a data structure in which the mapping tier tracks hits to mapping cache entries as indicated at502. At least some mapping cache entries that do not get hit often (more than a certain threshold) or that aren't hit for a specified period (i.e., are stale) may be evicted from the cache according to the tracking information in the data structure, for example by a background cache maintenance process that periodically or aperiodically checks the data structure as indicated at504.

To process a deduplication data upload request from a sender, the data plane may download at least one large (e.g., 4 mB) chunk from the data store, create a new chunk, and upload the new chunk to the data store, even if the deduplication data for the request is small (e.g., just one or a few data blocks, e.g. one or a few 4 kB data blocks). In at least some embodiments of the receiver-side deduplication architecture and technique, on every data upload request from a sender (including deduplication requests and regular data write requests), after the new chunk(s) are written to the data store, the data plane computes the fingerprint (e.g., hash) for every data block on the new chunk(s) and updates the mapping tier with this information. (See, e.g.,FIG. 5H). There may be many data blocks in a chunk. For example, with a chunk size of 4 mB and a data block size of 4 kB, every chunk upload to the data store will result in 1 k (1000) cache put operations to the mapping cache. If there are many upload requests, a bottleneck could occur in bandwidth between the data plane and the mapping tier and/or at the mapping cache due to the large volume of cache update operations that would result. In at least some embodiments, one or more of several techniques as described below may be implemented to help prevent or reduce these potential bottlenecks by reducing the overhead of updating all cache entries on every chunk write to the data store. These techniques may be in place all the time, or alternatively may only be invoked at times of high activity when such a bottleneck has occurred or may potentially occur.

One technique that may be used in at least some embodiments is to reduce the ratio of the data block size to the chunk size, for example by reducing the chunk size, to thus reduce the number of data blocks per chunk, which would reduce the number of cache updates per chunk write to the data store. For example, reducing the number of data blocks per chunk from 1000 to 500 would cut the number of cache updates in half.

In at least some embodiments, the deduplication data upload technique may only be used for chunks for which some threshold portion of the chunk may be deduplicated. Otherwise, the sender just sends the data via a normal data upload operation that does not use the deduplication technique. For example, with a chunk size of 4 mB and a block size of 4 kB, the deduplication technique may only be used if there are 16, 32, or some other threshold number of data blocks that may be deduplicated, or alternatively if there is 64 kB, 128 kB, or some other threshold amount of data that may be deduplicated.

In at least some embodiments, the deduplication technique may employ a “best effort” cache update process to update the mapping cache for new chunks uploaded to the data cache. The cache update process may attempt to update the mapping cache for all chunk uploads to the data store, but at peak times the process may skip the cache update for at least some chunks. For example, in some embodiments, the cache update process may be implemented as a background process. When uploading new chunks, the chunks may be uploaded to the data store and separately queued (e.g., to a FIFO queue) for handling by the cache update process on the data plane. If the queue gets full, one or more of the chunks in the queue may be discarded; the cache is not updated for the discarded chunks. Note that this does not cause a problem with or any corruption in the deduplication data dictionary.

In at least some embodiments, the deduplication technique may limit cache updates to larger write requests. For example, if only a relatively small portion (e.g., only one or a few data blocks, below some specified threshold) of a chunk is “dirty” and needs to be uploaded, the deduplication process may be skipped for this data upload, and a normal (non-deduplication) data upload may be used instead. Thus, the mapping cache may not be checked or updated for relatively small writes.

In at least some embodiments, the mapping cache may be implemented as a two-tiered or two-stage cache. In this implementation, instead of each index in the key/value pairs stored in the cache including a chunk identifier that identifies the chunk in which the respective deduplication data block is stored, each index includes a pointer or reference (e.g., a key) to a location in the cache that stores the chunk identifier. Thus, in at least some cache updates, only the location that includes the chunk identifier for multiple key/value pairs may need to be updated, instead of the index in each of the key/value pairs for the respective chunk.

Thus, in the two-stage cache, there are two types of cache entries. The first type of cache entry are the key/value pairs that each maps a fingerprint to a data block location within a chunk, and also points to one of the second type of cache entry. Each of the second type of cache entry identifies a particular chunk within the data store in which deduplication data blocks are stored. The key/value pairs may be referred to as first-level cache entries, and the cache entries identifying the chunks within the data store may be referred to as second-level cache entries.

As an example of using the two-stage cache described above, a deduplication data upload request may be received for one data block of a chunk. The data plane retrieves the chunk from the data store, builds the new chunk including the new data block, and then uploads the new chunk to the data store. The data plane has knowledge of the original chunk, and thus can determine which cache entries will be invalidated by the update. For example, the data plane may calculate the fingerprint (e.g., hash) for the old data block (the one being replaced by the new data block), invalidate that particular cache entry via the mapping tier, update the mapping cache with the fingerprint and index information of the new data block in the new chunk, and upload the new chunk to the data store. For the new chunk, the data plane knows that all data blocks except for the new data block are valid. The data plane then updates the second level entry in the cache to indicate the new chunk. All of the key/value pairs for the chunk point to this updated second level entry except for the key/value pair for the new data block.

In at least some embodiments, when updating a chunk, if only a small part of the chunk is being replaced (e.g., fewer than a specified number of data blocks), then the following method may be used to update the two-stage cache:The data blocks that are being changed are identified, and their fingerprints are calculated.Current first level cache entries corresponding to those fingerprints are deleted from the cache.The second level cache entry corresponding to the chunk is modified to reflect the replacement of the old version of the chunk with the new version of the chunk.First level cache entries for the new data blocks in the chunk are added to the cache.

In at least some embodiments, when updating a chunk, if a relatively large part of the chunk is being replaced (e.g., more than a specified number of data blocks), then the following method may be used to update the two-stage cache:All of the current first level cache entries corresponding to data blocks in the chunk may be deleted.The second level cache entry corresponding to the chunk is modified to reflect the replacement of the old version of the chunk with the new version of the chunk.First level cache entries for the all of the data blocks in the chunk are added to the cache.

In at least some embodiments, the cache eviction algorithm may be tuned so that the second level entries are preferentially NOT evicted.

Mapping Cache Updates and Snapshots

A service provider that provides a data store may allow clients to create snapshots of volumes on the data store. The snapshots may, for example, be used to create or recover local volumes on the client's network from the remotely stored snapshots. When a snapshot of a volume is taken, a snapshot manifest file that describes the snapshot may be created. A snapshot may be viewed as an immutable, point-in-time capture of a corresponding volume; a snapshot includes the snapshot data and a snapshot manifest that indicates where the snapshot data (chunks) is located. In some implementations, when a snapshot of a volume is taken, the snapshot data is not copied to another location but is instead made immutable within the volume. Alternatively, when or after a point-in-time snapshot of a volume is taken, the snapshot data from the volume may be copied to new locations in the data store, essentially creating a new and separate point-in-time snapshot of the volume. A snapshot manifest file for a snapshot may include entries that map the storage locations of all of the snapshot objects (chunks) stored in the data store to the blocks/chunks of the volume.

As previously noted, the chunks in the data store may be immutable (guaranteed to be valid if they are present in the data store). Thus, when updating a chunk via the deduplication process, a chunk is created and uploaded to the data store as a new chunk, and the respective “old” chunk is not overwritten or updated However, stale chunks may be periodically or aperiodically garbage collected. A motivation for updating the mapping cache for each new chunk to be uploaded to the data store is that the respective old chunks in the data store may be discarded (e.g., by a garbage collection process), and thus the cache entries for the old chunk may be stale as well.

However, if these old chunk(s) are part of a snapshot, the old chunks are not considered stale and are not likely to be garbage collected soon. Thus, in at least some embodiments, the deduplication cache update process may check to see if old chunks are part of any snapshot (e.g., by querying a snapshot maintenance process or by checking the snapshot manifests). If an old chunk is part of a snapshot, then the mapping cache entries for data blocks in the chunk that are not affected by the respective deduplication data upload do not have to be updated.

Data Object Versioning

In some block-based data storage systems, the data objects (e.g., chunks) may be versioned. For example, there may be a version identifier as well as a chunk identifier for each chunk. When a new chunk is created, a new value for a version identifier may be given to the new chunk. Thus, there may be one or more older versions and a newest version of a chunk in the data store. Note that all of these chunks would have the same chunk identifier, but each may have a different version identifier. In these implementations, the indexes stored in the mapping cache may also include a version identifier. In deduplication operations such as validating the presence of chunks in the data store according to index hits retrieved from the mapping cache, the version identifier may be used in addition to the chunk identifier.

As previously mentioned, embodiments of the receiver-side deduplication architecture and deduplication techniques may provide network deduplication by reducing bandwidth usage on the communications channel(s) between data sender(s) and the receiver (the data store provider). However, while primarily directed to network deduplication rather than data deduplication, some embodiments may also improve storage utilization in the data storage system by reducing the amount of data that is actually stored.

In some embodiments, to provide data deduplication in addition to network deduplication, instead of retrieving copies of the chunks from the data store, extracting the deduplication data blocks from the chunks, and building new chunks that include the deduplication data blocks and the new data blocks uploaded from the sender as shown inFIGS. 5F and 5G, references to the locations of the deduplication data blocks in the chunks in the data store may be stored in the new chunk. Note that the reference information is available in the index information obtained from the mapping tier.

In this case, since references are stored to the new chunk and not the data blocks themselves, then the chunk(s) that are referenced should not be garbage collected. In some embodiments, to prevent the referenced chunks from being garbage collected, a mechanism may be provided that increments or decrements a reference count for each referenced chunk. Chunks that have a reference count higher than zero may not be garbage collected.

Example Implementation

Embodiments of the receiver-side deduplication architecture and technique may, for example, be implemented in the context of a service provider that provides remote, volume-based block storage to one or more service client networks or data centers as a remote data store. The service provider may provide, via a local storage gateway over an intermediate network such as the Internet, a storage service to one or more customers of the service provider. The storage service interface may be implemented as a Web service interface. The storage gateway may be implemented as a virtual or physical appliance that is installed on-premise at a client's data center and may act as a gateway between the client's data center and the storage service. The storage gateway may, for example, be configured as an interface to and local cache for a primary storage provided remotely via the storage service and/or as an interface that shadows primary storage implemented on the client's network to remote storage provided by the storage service. The storage gateway may present standard data access interfaces to the client's applications at the front-end of the appliance, convert the data accesses into storage service requests at the back-end of the appliance, and transfer the data over the network to the storage service according to the storage service interface. The storage service may store the client's data in the remote data store according to block storage technology. The storage gateway may expose block storage protocols (e.g., iSCSI, GNBD (Global Network Block Device), etc.), file storage protocols (e.g., NFS (Network File Storage), CIFS (Common Internet File System), etc.), and/or object storage protocols (e.g., REST (Representational State Transfer)) at the front-end to the client's applications. A block storage protocol such as iSCSI may be used to enable direct access to the underlying data blocks of the remote data store. Files written by an application to a remote data store via file storage protocols such as NFS or CIFS exposed by the storage gateway may be stored to the remote data store according to block storage technology. Through an exposed file storage protocol such as NFS and CIFS, the storage gateway presents the client's data, stored in the remote data store according to block storage technology, to the client's applications as files before they are transmitted from the gateway over the client network to the client's applications. The exposed block storage protocol, e.g. iSCSI, transfers the blocks to the client's applications, thus requiring the application to handle interpretation of the data blocks into whatever format the application expects.

Embodiments of the receiver-side deduplication architecture and techniques may be implemented on the service provider network to provide deduplication for data uploaded from storage gateways at the client's data centers. In some embodiments, receiver-side deduplication may be provided to the clients as a deduplication service that provides access to the deduplication techniques described herein to clients that store data to the remote data storage provided by the service provider via storage gateways at the client data centers. Alternatively, access to the deduplication techniques may be provided as part of the storage service. In at least some embodiments, access to the deduplication service or to the deduplication techniques may instead or also be provided to other client data processes that upload data to the remote data store.

FIG. 7is a high-level block diagram of an example networking environment that includes an example service provider and an example client or service customer in which embodiments of the receiver-side deduplication architecture and techniques may be implemented. A storage gateway284may be installed, activated, and configured as a virtual or physical appliance in the service customer local network or data center (e.g., client network280) to provide one or more of several remote data storage functionalities to customer process(es)288on the client network280. A customer process288may be any hardware, software, and/or combination thereof that exists on the client network280and that can connect to and communicate with the storage gateway284via the data protocol of the gateway284's data ports (e.g., the iSCSI protocol). The storage gateway284may, for example, serve as an on-premise storage device and/or as an interface between the customer process(es)288on the client network280and a storage service264provided by service provider260. The storage service264may at least be partially implemented on a data plane270of the service provider260network. Note that, in addition to a storage service264, the service provider260may also provide other services to customers of the service provider260, including but not limited to a hardware virtualization service, a cache service as previously described herein, and/or a deduplication service that provides access to the deduplication techniques described herein to its customers that store data to the remote data storage. Alternatively, access to the deduplication techniques may be provided as part of the storage service264.

A customer of the service provider260may be referred to as a service customer or simply customer, and may be any entity that implements a computer network or networks, coupled to an intermediate network250such as the Internet, to provide networked computing services to one or more users on a local network or network, including one or more services remotely provided by service provider260. A service customer may be a business enterprise, an educational entity, a government entity, or in general any entity that implements a computer network or networks that provide networked computing services to users. WhileFIG. 7shows a single client network280, there may be multiple client networks280. Each client network280may correspond to a different service customer, or two or more client networks280may correspond to different data centers or localities of the same service customer, for example different regional offices of a business enterprise or different campuses of a school system. In at least some embodiments, each customer of the service provider260may have an account with the service provider260, and may be provided with security credentials (e.g., an account name and/or identifier, password, etc.) via which one or more customer representatives (e.g., a client network administrator) may log in to interfaces (e.g., Web pages) to the service provider260to manage the customer's resources provided by one or more services, including but not limited to a storage service, offered by the service provider260.

Embodiments of storage gateway284may be implemented in hardware, software, or a combination thereof. In at least some embodiments, storage gateway284may be implemented as a virtual appliance that may, for example, execute within a virtual machine instantiated on a host system. In at least some embodiments, storage gateway284may be implemented as a virtual appliance that may be downloaded or otherwise installed, activated, and configured on one or more computing devices such as server systems coupled to a local network infrastructure at a service customer's data center (e.g., client network280). Alternatively, storage gateway284may be implemented as a dedicated device or appliance that may be coupled to a local network infrastructure at a service customer's data center (e.g., client network280); the dedicated device or appliance may include software and/or hardware that implements the functionality of the storage gateway284.FIG. 8illustrates an example computer system on which embodiments of a storage gateway284may be implemented. In at least some implementations, storage gateway284communicates with the service provider260network via an intermediate network250(e.g., the Internet) through firewall282technology. Note that the service provider260network may also include front end262technology (e.g., firewall technology, border router technology, load balancer technology, etc.) through which network traffic from and to intermediate network250passes.

Embodiments of the storage gateway284may be installed, activated, and configured for use with a storage service264to provide one or more of several data store266functionalities. For example, a storage gateway284may be installed, activated, configured, and employed with a storage service264to serve as:A file system gateway. In this configuration, the storage gateway serves as a NAS storage interface (e.g., using CIFS or NFS protocols) to the storage service264. The remote data store266may be presented to the customer by the gateway284as an object store (e.g., REST), while the data store266is implemented according to block storage technology. In this configuration, the remote data store266may be presented to the customer as a virtualized file system to which the customer can write files and from which the customer can read files.A cloud volume gateway. In this configuration, the storage gateway284serves as an interface to volume(s) implemented on remote data store266via the storage service264. The remote data store266may be implemented using block storage technology. The gateway284provides local network access points, with the volume(s) on remote data store266(which may also be referred to as a cloud volume) serving as backend storage that provides flexible and essentially unlimited primary storage capacity. In this configuration, the remote data store266may be presented to the customer as a cloud volume system from which the customer can locally mount volumes for reading and writing data.A shadowing gateway. In this configuration, the storage gateway284acts as a “bump in the wire” between a customer's applications (e.g., customer process(es)288) and the customer's local data store286to provide shadowing of the customer's write data (e.g., iSCSI writes) to remote data store266via the storage service284. The remote data store266may be implemented using block storage technology. In this configuration, the storage gateway284may serve as a shadowing appliance that shadows the customer's local data store to snapshot(s) on the remote data store266. This shadowing may be performed transparently from the perspective of users on the local network. When necessary or desired, the customer may request or access snapshot(s) of the customer's data on the remote data store266, for example to restore, recover, or copy portions or all of the customer's data from the snapshot(s) to a local store286.

Note that the file system gateway and the cloud volume gateway are similar in that both serve as gateways to a remote data store, and both may locally cache data, e.g. frequently and/or recently used data. In both the file system gateway and the cloud volume gateway, data reads from customer processes may be serviced from the local cache, if possible, or from the remote data store if not. In contrast, in the shadowing gateway, data reads are passed through the gateway to the customer's local data store. The file system gateway and cloud volume gateway may collectively be referred to as cached gateways to distinguish these implementations from the shadowing gateway.

As shown inFIG. 7, service provider260network may implement an embodiment of the receiver-side deduplication architecture and techniques as described herein. One or more deduplication processes272may be implemented on data plane270(e.g., on host systems or servers), and a mapping tier274that includes and manages a mapping cache may be implemented as part of the deduplication data dictionary that includes the data chunks stored in remote data store266. Data uploads from the storage gateway284may be handled according to the deduplication techniques, for example as described in reference toFIGS. 1 through 6. Referring toFIGS. 1 and 5A through 5H, the sender data upload process160may be a process of or executing on the storage gateway284, and may be implemented in software, hardware, or a combination thereof. Referring toFIGS. 5A through 5H, local data170may be data cached on storage gateway284or data in local data store286.

Illustrative System

In at least some embodiments, a server that implements a portion or all of one or more of the technologies, including but not limited to the data storage system technologies and deduplication technologies as described herein, may include a general-purpose computer system that includes or is configured to access one or more computer-accessible media, such as computer system1000illustrated inFIG. 8. In the illustrated embodiment, computer system1000includes one or more processors1010coupled to a system memory1020via an input/output (I/O) interface1030. Computer system1000further includes a network interface1040coupled to I/O interface1030.

System memory1020may be configured to store instructions and data accessible by processor(s)1010. In various embodiments, system memory1020may be implemented using any suitable memory technology, such as static random access memory (SRAM), synchronous dynamic RAM (SDRAM), nonvolatile/Flash-type memory, or any other type of memory. In the illustrated embodiment, program instructions and data implementing one or more desired functions, such as those methods, techniques, and data described above for data storage system technologies and deduplication technologies, are shown stored within system memory1020as code1025and data1026.

Network interface1040may be configured to allow data to be exchanged between computer system1000and other devices1060attached to a network or networks1050, such as other computer systems or devices as illustrated inFIGS. 1 through 7, for example. In various embodiments, network interface1040may support communication via any suitable wired or wireless general data networks, such as types of Ethernet network, for example. Additionally, network interface1040may support communication via telecommunications/telephony networks such as analog voice networks or digital fiber communications networks, via storage area networks such as Fibre Channel SANs, or via any other suitable type of network and/or protocol.

CONCLUSION