Predictive upload of snapshot data

A snapshot of a volume is taken by proactive uploading of scheduled snapshot data before the scheduled snapshot time has arrived. A volume snapshot schedule of once a day may be set up to a service provider using a speed-limited network connection. Using a determined upload speed of the network connection and a list of changes to the volume since a prior snapshot, a snapshot system may determine an appropriate time to start uploading volume data so that the snapshot may be completed at or after the scheduled snapshot time. By using the list of changes and available bandwidth of the network connection, the snapshot may be completed earlier than had it been started at the time of the snapshot and the available bandwidth of the network connection may be more efficiently used.

BACKGROUND

Many companies and other organizations operate networks that connect computing resources to support their operations, such as with the computing systems being co-located (e.g., as part of a local network) or instead located in multiple distinct geographical locations (e.g., connected via one or more private or public intermediate networks). For example, data centers housing significant numbers of interconnected computing systems have become commonplace, such as private data centers that are operated by and on behalf of a single organization and public data centers that are operated by entities such as businesses to provide computing resources to customers.

Some public data center operators provide network access, power and secure installation facilities for hardware owned by various customers, while other public data center operators provide “full service” facilities that also include hardware resources made available for use by their customers. However, as the scale and scope of public and private data centers have increased, the tasks of provisioning, administering, and managing the physical computing resources have become increasingly complicated.

DETAILED DESCRIPTION

Techniques described and suggested herein include taking a snapshot of a volume by proactive uploading of scheduled snapshot data before the scheduled snapshot time has arrived. For example, a customer may set up a volume snapshot schedule of once a day to an off-site service provider using a speed-limited Internet connection. Using a determined upload speed of the Internet connection and a list of changes to the volume since a prior snapshot, a snapshot system may determine an appropriate time to start uploading volume data so that the snapshot may be completed at or after the scheduled snapshot time. By using the list of changes and available bandwidth of the Internet connection, the snapshot may be completed earlier than had it been started at the time of the snapshot and the available bandwidth of the Internet connection may be more efficiently used.

In one embodiment, a storage appliance is placed at a customer premises. The storage appliance appears as a block storage volume to computing resources at the customer premises. The storage appliance responds to read and write requests from the client computing resources, with the read request receiving a response including the stored data and write requests storing an associated write request data. For write requests, changes to the data of the volume are stored in another data store, which may be termed the working storage. The working storage stores the changes as entries in a queue, with the queue containing at least the entries since a previous snapshot was performed. The storage appliance also interfaces with a service provider over an external network for storage of a snapshot. Using an amount of changed data reflected in the entries since the last snapshot, the amount of upload throughput available to the storage appliance may be used to determine an upload time of how long the changes will take to upload to the service provider. If the amount of upload time is equal to or more than the remaining time to the scheduled snapshot with a delay factor or a buffer factor or no factor, the storage appliance begins uploading the change data described in the entries in the working storage. Changes to already uploaded data may be re-uploaded. Once the scheduled snapshot time occurs, the working storage may mark the last entry of the snapshot. Remaining entries before and including the last entry of the snapshot may be uploaded to the service provider to finish the snapshot. For example, a storage appliance determines the time (TS) until a next snapshot, a throughput (B) to a service provider, an amount (D) of changed data to upload and two factors (K) and (L) representing delay (“postpone”) or advance (“prepone”) of timing. If TS<K*D/B+L, the upload of changed data may be started. In the equation shown, a K<1 represents a postponing of timing and a K>1 represents a preponing of timing. L may also be positive or negative to adjust the postponing or preponing of timing.

In some embodiments, a storage gateway may monitor changes to a data store external to the storage gateway. The data store may field the requests for read and write requests, while the storage gateway monitors the data store and/or the requests. Depending on the embodiment, a write request may be forwarded in part or in whole to the storage gateway, or the storage gateway may review the data store for changes. The storage gateway may track the changes to the data store. Upon determining the tracked changes should be uploaded to a service provider as part of a snapshot, the storage gateway may perform read requests on the tracked data and upload the tracked data to the service provider.

In some embodiments, further optimizations may be performed. In one embodiment, data collisions in the working storage may be removed from a snapshot so that only the latest change represented by an entry is uploaded to the service provider. In another embodiment, the upload may be delayed such that data collisions are given more time to be resolved before upload to improve the efficiency of the use of the upload bandwidth. In yet another embodiment, only portions of a block or object may be uploaded and the service provider may update stored information with the portion.

In some embodiments, the storage appliance and the service provider may use differing storage technologies. Conversion may be needed for the storage technologies. The conversion may occur at the client side before upload or the service provider side after upload. For example, a storage appliance uses block storage and a service provider uses object storage. In this example, optimum storage of the object store is 4 megabyte objects, while the data store uses 4 kilobyte blocks. If a service provider does not have a method to update objects, any change within a 4 megabyte object may necessitate a re-upload of the 4 megabyte object. However, if the storage service is able to update or mutate objects, only the changes to the object may be uploaded. For example, a service provider, using object storage with immutable objects, uses a storage helper that receives the update from the storage appliance. A new object is created by using an old object referenced in the update and merging the changes into the new object. A reference to the old object (as part of a snapshot) may be updated to reflect the new object.

It should be noted that a snapshot or a backup is used in some embodiments for the purpose of example clarity. However, it should be recognized that a process or system can be used for either a backup and/or a snapshot. In many embodiments in which a snapshot is discussed, a backup may also be applicable. Similarly, in many embodiments in which a backup is discussed, a snapshot may also be applicable.

Turning now toFIG. 1, an illustrative example of an environment100is shown, in which a predictive snapshot may be implemented in accordance with at least one embodiment. A client data center102is connected to a storage service104through an external network106, such as the Internet or private network capacity. The client data center102may back up data, such as a data store snapshot, to the storage service104over the external network106. The external network106may include limitations, such as available bandwidth or throughput.

The client data center102may contain multiple client computing systems108that store information through a storage gateway110. The storage gateway110may be configured to appear as a block storage device to the client computing systems108such that the client computing systems108may read and write data to the storage gateway110. The storage gateway110may store the data in a data store112. For each write to the data store, an entry documenting the change may be stored in a second data store that may be called working storage114. In some embodiments, the working storage is a queue that receives and/or organizes changes in order.

A snapshot may be represented in the queue as a difference between a prior snapshot and a set of entries in the working storage. For example, a prior snapshot was taken at entry number5in the working storage. A new snapshot is requested when the latest entry in the working storage was at entry number20. Thus, the new snapshot should contain the prior snapshot updated with the information in entries6through20. If the snapshot is remotely located, such as in a service provider104over an external network106, only the changes in entries6through20need be transferred to the service provider104to save on expended external network106usage. The working storage114may continue to accept entries, such as entries21through40, as the new snapshot is known to end at entry20.

The storage gateway110may communicate with a storage service104through an interface115to the storage service104, such as an application programming interface (API). The received data may be placed directly into storage116and associated with a snapshot or further processed through a storage helper118configured to further process incoming data. In some embodiments a storage helper118performs a task of linking stored data with a specific snapshot. In other embodiments, a storage helper118converts block data information into object data information. In yet other embodiments, a storage helper118creates a new object to store by updating a prior object from storage116with data received from storage gateway110, reducing the amount of information transferred over the external network106. In some embodiments, multiple storage helpers118are used. The storage helpers118may be modules, code, processes, hardware, software, plugins or other computing tools used together with, excuting on or separately from the storage service104.

The storage gateway110may use the working storage information to gain an advantage in time on a future scheduled backup. The storage gateway110may determine a throughput of the external network106of data that may be transferred to the storage service104. This determination may be performed by historical analysis, estimated load, test measurements, expected throughput or other estimation or determination of speed. The storage gateway110may then determine the amount of changes that must be uploaded to the storage service104by examining the entries in the working storage114. The time remaining before the scheduled backup may also be determined. Using the throughput and amount of changes, a determination on the amount of time required for the transfer may be determined. If the amount of time for the transfer is equal to or less than the time remaining before the scheduled backup, the backup may be started. In some embodiments, the time remaining or time for the transfer may be further altered with a factor to postpone or prepone the start of upload to data in the working storage114. Any uploaded data that is further changed may be replaced by a second upload of the changed data. Upon a scheduled time for the scheduled backup, the last working storage114entry may be noted. Further changes may be stored in the working storage114for further scheduled backups. However, the uploading of the remaining entries in the working storage114up to the last working storage114entry may be uploaded to make the backup complete.

Turning now toFIG. 2, an illustrative example is shown of an alternate environment200in which a predictive snapshot may be implemented in accordance with at least one embodiment. In the example shown, a client data center204is connected to a service provider214providing a storage service via the Internet213. The client data center204may include multiple client computing resources, such as servers202, connected through internal networking206to a gateway210to the Internet213, a storage gateway212and a data store208. The servers202may read and write information to the data store208. The storage gateway212may receive change information about the writes to the data store208, such as by receiving copies of the writes or by monitoring the data store208. The storage gateway212may store the tracking information in entries in working storage215to identify changed data of the data store208. Using the working storage, the storage gateway may determine an efficient time to start upload of the data from the data store208identified in the entries in working storage215since a last snapshot. The efficient time may include historical data, upload speed, historical loads, amount of data to upload and time remaining until a next scheduled snapshot and probabilities of data collisions in the time remaining. The data may be uploaded over a secure channel to the service provider214. The service provider214may store the data as related to a snapshot in object storage216or further process the data through a storage helper218to store in object storage216. In the example shown inFIG. 2, the data will need to be converted from block storage to object storage, as the data store208and object storage216are of different storage types. At the time of the scheduled snapshot, a last entry may be marked such that an end of the changes to upload for a snapshot is known. The storage gateway212may then complete the snapshot by finishing the upload of any entries not yet uploaded to the service provider214.

Turning now toFIG. 3, an illustrative diagram of systems involved in a predictive snapshot in accordance with at least one embodiment is shown. The predictive snapshot may be seen as three phases, a change management phase300, an optimization phase301and a transmission phase302. The optimization phase301and transmission phase302may also operate during two stages of uploading data to a service provider318: an upload of predictive pre-snapshot data and an upload of post-snapshot data. These phases, however, may operate at the same time and in any order. In the change management phase300, changes are stored in working storage312as the changes are made to a local data store308. A client computing resource303, such as a server process, sends a change304, such as a write request, to a storage gateway306. The storage gateway306causes the change304to be written to the local data store308and the working storage312as a change entry310. In some embodiments, the change entry310includes the changed data. In other embodiments, the change entry310is a reference to the local data store308.

The local data store may prevent the overwriting of information that is in a closed snapshot but that is not yet uploaded to the service provider318. An open snapshot may be represented by entries in a working storage312that form part of a future snapshot. A closed snapshot may be represented by entries in a working storage312that form part of a past snapshot and occur before or at a last entry of the snapshot. The snapshot may close at or near the time of the scheduled snapshot. Closing the snapshot may be based at least in part on the time of the scheduled backup, which may mean that the time is selected from a set of times that is limited by the scheduled time (e.g. it has to be within 2 hours of the scheduled time). In one embodiment, changes that would affect an entry in the working storage312that forms part of a closed snapshot may be stored in a journal that is applied after the uploading of the snapshot is complete. For example, a write request is received from a client server to the storage gateway306. The storage gateway306may review the working storage312to see if the location of the write is protected by an entry that is part of a closed snapshot. If not, the write may occur. If the write is protected by an entry, the entry may be stored on a journal to be applied after the snapshot upload is complete. In another embodiment, changes to the local data store308are directly stored in the working storage, such that any changes to the local data store308may be immediately applied. In yet another embodiment, a link between working storage entry and a set of local storage blocks is created where the local storage blocks are marked dirty along with latest working storage entry that corresponds to the local storage block. When a working storage entry is processed and uploaded, the corresponding local storage blocks that don't have any other later updates will be marked ‘clean.’ In some cases, the local store may not have all the data such as when the local store is operating in a caching mode.

The uploading of data to the service provider318can be separated into two stages of uploading. The first stage is a predictive pre-snapshot upload in which data predicted to be in a future snapshot is proactively uploaded before the snapshot is taken. The second stage is an upload of data that forms part of snapshot request in the past. The two phases are separated by the scheduled snapshot request. Predicting which data will form part of a future snapshot is useful during the first stage. The prediction process may be optimized by determining a probability that an entry310will be overwritten in the remaining time before the snapshot is taken. In some embodiments, the entries310are prioritized for upload based on the smallest probability first (or the greatest probability of not being overwritten). In other embodiments, entries310that fail to meet or exceed a probability threshold are skipped and entries310that meet or exceed a probability threshold are included in the upload before the snapshot is taken. On the other hand, in the second stage of upload, all data forming the snapshot (such as those identified by the write log) must be uploaded to the service provider318in order to consider the snapshot complete.

As part of the two stages of uploading, the uploading may be accomplished by an optimization phase301and a transmission phase302. In the optimization phase301, a determination is made of which data to transmit to the service provider318at what point in time. In the embodiment shown, a storage gateway306determines a time315to begin uploading data. This time315may be based on factors that include network speed, time remaining until a scheduled snapshot and an amount of data to transmit over the network. The working storage312may be examined for data collisions. A data collision is an overwrite of a prior write to a data store. Colliding entries316may be removed from the working storage312and the last entry310may be selected, as long as the colliding entry is completely overwritten.

In the transmission phase302, snapshot data is transmitted to the service provider318according to the determinations made in the optimization phase. The storage gateway306uploads information from the working storage314according to optimizations from the optimization phase301. Here, colliding entries316are skipped because of the optimzation performed in the optimization phase301. Entries other than the colliding entries316are retrieved from the local data store308and sent by the storage gateway306to the service provider318over a communication channel. Communications channels may include secure or insecure HTTP, HTTPS, FTP, TCP, IP, ethernet, token ring, RS232 or other communications technology hardware and/or software.

Turning now toFIG. 4, an illustrative diagram of systems involved in a predictive restore in accordance with at least one embodiment is shown. In one embodiment, the predictive restore may be used to synchronize a remote volume to a snapshot that is not yet complete. The predictive restore may cause data from a predictive snapshot to be proactively sent to a remote volume before a snapshot is taken such that the predictive restore may complete faster than if the restore happened after the snapshot was taken. The predictive restore may be seen as three phases, a change management phase400, an optimization phase402and a transmission phase404. These phases, however, may operate at the same time and in any order. In the change management phase400, changes are stored in working storage412as the changes are made to a local data store308. A client computing resource303, such as a server process, sends a change304, such as a write request, to a storage gateway306to cause the change304to be written to the local data store308and the working storage412as a change entry410.

In the optimization phase402, a determination is made of which data to send to the service provider318and restore volume406at what point in time. The information will not only be uploaded to the service provider318, but also the restore volume406. In the embodiment shown, a storage gateway306determines a time415to begin uploading data to the service provider318and the restore volume406. This time415may be based on factors that include network speed, time remaining until a scheduled restore and an amount of data to transmit over the network. The working storage412may be examined for data collisions. A data collision is an overwrite of a prior write to a data store. Colliding entries416may be removed from the working storage412to form non-colliding working storage414and the earliest change entry410selected, as long as the colliding entry is completely overwritten.

In the transmission phase404, snapshot data is uploaded to the service provider318and restore volume406according to the determinations made in the optimization phase. Prior snapshot information from the data store308may be copied to the restore volume406. The storage gateway306uploads information from the working storage414according to optimizations from the optimization phase402. Here, colliding entries416are skipped because of the optimization performed in the optimization phase402. Entries other than the colliding entries416are retrieved from the local data store308and uploaded by the storage gateway306from the service provider318over a communication channel. Communications channels may include secure or insecure HTTP, HTTPS, FTP, TCP, IP, ethernet, token ring, RS232 or other communications technology hardware and/or software. The storage gateway404receives the data and applies the data to the restore volume406.

In another embodiment, this mechanism of predictive restore is part of asynchronous replication between two remote volumes. A second volume is updated via ‘commit points’ or ‘snapshot points’ from a first volume. The second volume is updated on a continuous basis such that each snapshot point from the first volume is restored onto the second volume in less time than if the entire snapshot were transferred between the volumes after the snapshot was taken. In some cases, a snapshot may complete transfer approximately at the same time snapshot is taken.

Turning now toFIG. 5,FIG. 5shows an illustrative example of an environment500in which a predictive snapshot is used with a block storage system and an object storage system in accordance with at least one embodiment. A storage system501tracks changes to block storage506using a working storage502. The working storage502and block storage504may be built upon a storage system503, such as a hard drive, solid state storage, virtual storage system, database or other storage technologies. The working storage502includes entries504identifying changes to the block storage506in the order the changes were accomplished. A snapshot510is represented by a grouping of changes to the block storage since a prior snapshot.

The storage system501may compile information to send as part of a snapshot to a service provider516. In the embodiment shown, the service provider516uses object-based storage518, but does not have a storage helper520based for conversion from block storage506. The storage system501retrieves an entry504from the working storage502and retrieves necessay information from the block storage506to compile an object512for storage with the service provider516. The object512is sent over an external network514to the service provider516for storage. For example, in the embodiment shown, the entry504identifies a change at block location4for a length of 2 blocks. As an object is four blocks and always starts at a boundary of four, the object is created by retrieving blocks1-3and the modified4block508. The object512is then sent to the service provider516.

Turning now toFIG. 6,FIG. 6shows an illustrative example of an environment600in which a predictive snapshot is used with a block storage system to mutate an object within an object storage system in accordance with at least one embodiment. As seen inFIG. 5, the working storage502tracks changes of the block storage506in order to create a snapshot510. However, if the service provider516has a mutate helper602, only block4(508) is retrieved and sent over the external network514. The mutate helper602requests an old object606containing the old block4from the object storage604. The mutate helper602then creates an object608to hold the old object blocks1-3and the current block4(508). The object608is then stored in object storage604as associated with the new snapshot. This mutate help602allows for a reduction in the amount of redundant data transferred over the external network514.

In another embodiment, a smaller object may be created with metadata instructing that changes in the smaller object be applied to a prior larger object. For example, a change to a prior object is stored as a new object with a corresponding change in metadata to reflect that the new object is now included in the volume as applied to the prior object. This allows a system to create a strongly consistent data store from eventually consistent data stores such as object data stores.

Turning now toFIG. 7, an illustrative example of a process700that may be used to perform a predictive snapshot in accordance with at least one embodiment is shown. The process may be performed by a system such as seen inFIG. 1, including a storage service104, a storage gateway110, data store112and working storage114. The storage gateway110may track702changes to a data store112since a last snapshot and determine704available throughput to a storage service104. Using the available throughput and a scheduled snapshot time, the storage service104may cause706an upload of the changes to the data store112to begin before a scheduled snapshot. After the time of the scheduled snapshot, remaining changes to the data store112may be uploaded708to complete the snapshot. By leveraging the prior snapshot and changes since the snapshot to the data store112, the bandwidth and time used to upload the changed data to the storage service104may be reduced as compared to upload of a full snapshot.

Turning now toFIG. 8, an illustrative example is shown of a process800that may be used to perform a predictive snapshot upload based at least in part on a time to upload changes in accordance with at least one embodiment. The process may be performed by a system such as seen inFIG. 1, including a storage service104, a storage gateway110, data store112and working storage114. The storage gateway110may track802changes to a data store112since a last snapshot and determine804available throughput to a storage service104. The storage gateway110may also determine806a time remaining until a next snapshot. Using the working storage114, the storage gateway110may determine an amount of changes needed to be uploaded808to the storage service104. Using the determined throughput, remaining time and amount of changes, the storage gateway110may begin810the upload of changes to the data store when the time required for the upload equals or is greater than the time to the next snapshot plus or minus a delay. This allows the storage gateway110to “get a head start” on the uploading of changes to the data store that make up the snapshot so that the snapshot may be marked as completed more quickly. This proactive uploading also allows the storage gateway110to make use of potentially expensive upload bandwidth that would be potentially wasted if not used. The upload bandwidth of the storage gateway110to the storage service104is potentially more expensive because longer distance communications are often slower and more expensive than short distance, local communications. When the time for the snapshot arrives, the last change or entry in the working storage114may be marked812. The changes may be uploaded814to the storage service104until the snapshot is complete. Once the marked entry is uploaded along with the other changes between the prior snapshot last entry and the marked entry, the snapshot is complete.

Turning now toFIG. 9, an illustrative example is shown of a process900that may be used to perform a predictive snapshot based at least in part on predicted collisions in accordance with at least one embodiment. The process may be performed by a system such as seen inFIG. 1, including a storage service104, a storage gateway110, data store112and working storage114. The storage gateway110may track902changes to a data store112since a last snapshot. Using information such as the available throughput and a scheduled snapshot time, the storage service104may cause904an upload of the changes to the data store112to begin before a scheduled snapshot. Optimizations may be made such as removing collisions from the queue906in the working storage114. The storage gateway110may determine908a probability that each entry will be overwritten before the snapshot is closed. Using these probabilities, such as computed by a “heat map” technique, the data associated with the least probability of change may be selected to be uploaded first910to avoid a re-upload of data that is overwritten. If possible, the amount of data sent to the storage service104over the external network is minimized by determining912to send only the changed data as a mutation to data existing in the storage service104; otherwise a collection may be determined to be sent. The selected data is then sent914to the storage service104. If the scheduled snapshot time has not yet arrived916, the process may be repeated starting at906using the steps to update information as necessary (such as step908if a collision has occurred). Once the snapshot time passes916, the remaining data for the snapshot may be uploaded918according to the working storage114.

Turning now toFIG. 10, an illustrative example is shown of a process1000that may be used to perform a predictive snapshot by prioritizing uploads in accordance with at least one embodiment. The process may be accomplished by a system such as seen inFIG. 1, including a storage service104, a storage gateway110, data store112and working storage114. The storage gateway110may still track changes to a data store112since a last snapshot. The storage gateway110may determine1002a time remaining until a next snapshot (“TS”). The storage gateway110may determine1004available throughput to a storage service104(“B”). Using the working storage114, the storage gateway110may determine1006an amount of changes needed to be uploaded to the storage service104(“D”). Using1008a delay coefficient (“K”) and a delay factor (“L”), the determined throughput B, remaining time TS and amount of changes D, the storage gateway110may begin1010the upload of changes to the data store when TS<K*D/B+L (or the time required for the upload adjusted by the delay coefficient and delay factor is greater than the time to the next snapshot). If the upload of the scheduled snapshot has started, but the snapshot is1012still open (the time for the scheduled snapshot has not yet arrived), a next change identified in the working storage114may selected for upload1014. The next change may be examined to determine1016the probability that the change will be overwritten in the remaining time to the next snapshot (P). Using1018the maximum acceptable probability threshold for upload (PT), the storage gateway110determines1020if P<PT. If so, the data is uploaded1022. If not, the data is skipped and the working storage114is checked to see if the snapshot is still open1012. If the snapshot is1012still open1012, the process of1014-1022may be repeated. If the snapshot is1012closed, the remaining data for the snapshot is uploaded to the storage service1024.