Selective placement and adaptive backups for point-in-time database recovery

Embodiments for optimizing database backups to achieve a Recovery Time Object (RTO). A user-defined RTO configured for one or more databases is received. A backup frequency for initiating backups of the one or more databases is determined based on a continuously predicted recovery time associated with a plurality of factors. The backups of the one or more databases are executed at the determined backup frequency to ensure the user-defined RTO is achieved for the backups of the one or more databases. In some embodiments, a recovery window of the one or more databases may be increased using an RTO-aware tiered or remote storage caching operation for portions of the database, and an RTO-aware re-sharding operation on sharded databases may be performed when the backup frequency exceeds a predetermined threshold such that each shard may be restored within the user-defined RTO.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates generally to the field of computing systems, and more particularly, to database backup and recovery operations.

Description of the Related Art

A Database Management System (DBMS) stores large volumes of data to support diverse workloads and heterogeneous applications. The DBMS is critical to business transaction processing and decision making, and may incorporate strategies that promote keeping the data highly available. However, a DBMS may unexpectedly fail for various reasons, including defects in a hardware or software component within a computer system. To facilitate a quick and efficient recovery to these unexpected failures, various techniques exist to back up the underlying data and operational logs contained within the DBMS so as to restore the databases therein to a prior state. Particularly when integrated into distributed computing models and a cloud environment, these systems may become increasingly complex to maintain and restore, and therefore a continuing need exists to advance the underlying architecture supporting this data.

SUMMARY OF THE INVENTION

Various embodiments for optimizing database backups to achieve a Recovery Time Object (RTO), by a processor are provided. In one embodiment, by way of example only, a method comprises receiving a user-defined RTO configured for one or more databases; determining a backup frequency for initiating backups of the one or more databases, the backup frequency based on a continuously predicted recovery time associated with a plurality of factors; and executing the backups of the one or more databases at the determined backup frequency to ensure the user-defined RTO is achieved for the backups of the one or more databases. In some embodiments, a recovery window of the one or more databases may be increased using an RTO-aware tiered or remote storage caching operation for portions of the database, and an RTO-aware re-sharding operation on sharded databases may be performed when the backup frequency exceeds a predetermined threshold such that each shard may be restored within the user-defined RTO.

In addition to the foregoing exemplary embodiment, various other system and computer program product embodiments are provided and supply related advantages. The foregoing summary has been provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

DETAILED DESCRIPTION OF THE DRAWINGS

A DBMS may perform many complex operations, consisting of multiple steps, such as for example, creating a new table. The amount of work required to complete an operation varies, and may depend upon such factors as the algorithms and architecture chosen by the DBMS vendor to implement product features. In the event of failure, the DBMS may provide a capability to backup the state of the database to recover from a crash or to restore the database to its older state. The database's old state may need to be to restored, for instance, to track down an incorrect operation and remove its effect, to detect an intrusion and take corrective actions. However, to achieve this, the database should be able to recover precisely at the desired time or the database operation (i.e., the type of recovery known as point-in-time recovery). Thus, similar to the amount of work and time required to complete an operation, the time required to recover an operation (i.e., replay from the log) varies by the type of operation. For example, a table reorganization operation is much more complex, i.e., takes more steps to complete, than an operation to insert a row of data in a table, and consequently will take much longer to recover.

A recovery cost is not a simple linear function that is based solely on the amount of data and a number of operations, but is also dependent on the type of workloads and the complexity of the operations that are executed. The nonlinear nature of database operations makes it challenging for an administrator to predict the time it will take to perform a future recovery operation. Consequently, the administrator may often rely on a combination of intuition, trial and error, and experience when designing a recovery plan to meet the business enterprise's Recovery Time Objective (RTO), which may be referred to as a maximum length of time that a DBMS may remain unavailable following a service disruption, or the acceptable timeframe allowable to restore the old state of the database.

The point-in-time recovery mechanism is common among database systems. Some DBMS' use a combination of backup and operation logging to provide the point-in-time recovery functionality. These systems continuously log all the state modifying operations on the database. They also periodically backup the entire state of the database. When a user requests a recovery at a specific point in time, the backup just preceding the recovery point is retrieved and restored, then the operation log is replayed on the restored backup up to the recovery point. Since, log replay is a time consuming process, the periodic back-ups are helpful to reduce the recovery time. They allow the recovery process to jump directly close to the desired recovery point, thus avoiding the replay of the operation log from the beginning. Low recovery time can be achieved by backing up the database state more frequently. However, depending upon the database size frequent backups can be cost prohibitive, and may adversely impact the database performance. Hence, it is important that the interval between backups is set so as not to burden the resources while providing low recovery time. Moreover, the recovery time can be unpredictable based on the recovery point or the characteristics of the database, which makes conforming to the promised RTO challenging.

One solution that the administrator may often choose is to back up the DBMS more frequently than required, rather than risk a situation where the business may miss the RTO goal or be unable to meet a Service Level Agreement with an end user community. This problem becomes more pronounced in a cloud environment where the volume of data tends to be high, the types of workloads accessing the data tend to be much more diverse, and there tends to be fewer administrators available to manage the installation.

Accordingly, the mechanisms of the present invention implement such functionality as continuously predicting a recovery time during the normal operations of the database system to determine at what interval the database should be backed up. In this way, the RTO (i.e., as defined by a user/administrator) for recovering any particular point in time is ensured for a predefined time window (referred to herein as a “recovery window”, e.g., available backups from the previous 10 days) A dedicated server called a “recovery server” may be deployed to perform the recovery as necessary, and the database backup interval(s) may be adjusted or adapted to be performed from the recovery server to avoid an RTO violation should the database need to be recovered. This model accounts for both the process to restore the database backups and the replay time required to replay the operational logs associated therewith. Additionally, embodiments of the present invention also provide RTO-aware placement techniques for storing the database backups fractionally within local and remote storage locations to extend the recovery window and quickly recover the database state without incurring a high space overhead of storing a large amount of files locally in faster (e.g., NVMe SSD), more expensive storage solutions. It should be noted that the functionality of the present invention may be employed within the context of a non-relational (NoSQL) database, where data is part of the write-ahead log and the log replay time may be predictable. Further, the mechanisms of the present invention may apply to both full database backups and/or incremental backups (i.e., where only modified files of the database are copied to the backup), as one skilled in the art would appreciate.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

FIG. 4, following, is an additional block diagram showing a hardware structure of a data management system400that may be used in the overall context (i.e., as a portion of a distributed computing environment) of performing database recovery functionality according to various aspects of the present invention.

Network460may be a fibre channel (FC) fabric, a fibre channel point-to-point link, a fibre channel over Ethernet (FCoE) fabric or point to point link, a FICON or ESCON I/O interface, any other I/O interface type, a wireless network, a wired network, a LAN, a WAN, heterogeneous, homogeneous, public (i.e. the Internet), private, or any combination thereof. The ISP may provide local or distributed data among one or more locations and may be equipped with any type of fabric (or fabric channel) (not shown inFIG. 4) or network adapter460to the storage controller440, such as Fibre channel, FICON, ESCON, Ethernet, fiber optic, wireless, or coaxial adapters. Network management system400is accordingly equipped with a suitable fabric (not shown inFIG. 4) or network adaptor460to communicate.

To facilitate a clearer understanding of the methods described herein, storage controller440is shown inFIG. 4as a single processing unit, including a microprocessor442, system memory443and nonvolatile storage (“NVS”)416. It is noted that in some embodiments, storage controller440is comprised of multiple processing units, each with their own processor complex and system memory, and interconnected by a dedicated network460within data storage system400.

In a local or remote location, yet connected over network460, storage430(labeled as430a,430b, and430nherein) may be comprised of one or more storage devices, such as storage arrays, which are connected to storage controller440(e.g., by a storage network) as shown.

In some embodiments, the devices included in storage430may be connected in a loop architecture. Storage controller440manages storage430and facilitates the processing of write and read requests intended for storage430. The system memory443of storage controller440stores program instructions and data, which the processor442may access for executing functions and method steps of the present invention for executing and managing storage430as described herein. In one embodiment, system memory443includes, is in association with, or is in communication with the operation software450for performing methods and operations described herein. As shown inFIG. 4, system memory443may also include or be in communication with a cache445for storage430, also referred to herein as a “cache memory,” for buffering “write data” and “read data,” which respectively refer to write/read requests and their associated data. In one embodiment, cache445is allocated in a device external to system memory443, yet remains accessible by microprocessor442and may serve to provide additional security against data loss, in addition to carrying out the operations as described herein.

In some embodiments, cache445is implemented with a volatile memory and non-volatile memory and coupled to microprocessor442via a local bus (not shown inFIG. 4) for enhanced performance of data storage system400. The NVS416included in data storage controller440is accessible by microprocessor442and serves to provide additional support for operations and execution of the present invention as described in other figures. The NVS416, may also be referred to as a “persistent” cache, or “cache memory” and is implemented with nonvolatile memory that may or may not utilize external power to retain data stored therein. The NVS416may be stored in and with the cache445for any purposes suited to accomplish the objectives of the present invention. In some embodiments, a backup power source (not shown inFIG. 4), such as a battery, supplies NVS416with sufficient power to retain the data stored therein in case of power loss to data storage system400. In certain embodiments, the capacity of NVS416is less than or equal to the total capacity of cache445.

Storage430may be physically comprised of one or more storage devices, such as storage arrays. A storage array is a logical grouping of individual storage devices, such as a hard disk. In certain embodiments, storage430is comprised of a JBOD (Just a Bunch of Disks) array or a RAID (Redundant Array of Independent Disks) array. A collection of physical storage arrays may be further combined to form a rank, which dissociates the physical storage from the logical configuration. The storage space in a rank may be allocated into logical volumes, which define the storage location specified in a write/read request.

In one embodiment, by way of example only, the storage system as shown inFIG. 4may include a logical volume, or simply “volume,” may have different kinds of allocations. Storage430a,430band430nare shown as ranks in data storage system400, and are referred to herein as rank430a,430band430n. Ranks may be local to data storage system200, or may be located at a physically remote location. In other words, a local storage controller may connect with a remote storage controller and manage storage at the remote location. Rank430ais shown configured with two entire volumes,434and436, as well as one partial volume432a. Rank430bis shown with another partial volume432b. Thus volume432is allocated across ranks430aand430b. Rank430nis shown as being fully allocated to volume438—that is, rank430nrefers to the entire physical storage for volume438. From the above examples, it will be appreciated that a rank may be configured to include one or more partial and/or entire volumes. Volumes and ranks may further be divided into so-called “tracks,” which represent a fixed block of storage. A track is therefore associated with a given volume and may be given a given rank.

A network endpoint470is connected through the network460as shown. The network endpoint470is generically intended to refer to any number of network devices, such as a switch, a router, a wireless access point, or another device known generally to one of ordinary skill in the art. As will be further illustrated in the following figures, a user may use a networked device, (e.g., a device connected to network460) to access the network260. The networked device may include computers, tablets, smartphones, television set top boxes, televisions and other video equipment, or even a household appliance such as a refrigerator or a garage door opener, again as one of ordinary skill in the art will appreciate. Ultimately any device having communicative ability to and through network460is anticipated to use the network endpoint470. In one embodiment, the depiction of a network endpoint470serves to provide a point where an input object (data object) is introduced into a distributed computing environment, as will be described.

The storage controller440may include a configuration module455and a provisioning module458, among other functional components. The configuration module455and provisioning module458may operate in conjunction with each and every component of the storage controller440, and storage devices430. The configuration module455and provisioning module458may be structurally one complete module or may be associated and/or included with other individual modules. The configuration module455and provisioning module458may also be located at least partially in the cache445or other components, as one of ordinary skill in the art will appreciate.

The configuration module455and provisioning module458may individually and/or collectively perform various aspects of the present invention as will be further described. For example, the configuration module455may perform various system configuration operations in accordance with aspects of the illustrated embodiments, such as configuring the storage controller440to operate using a given set of definitional information, for example. The analytics module459may use data analytics to compute, identify, organize, create, delete, sequester, or perform other actions on various patterns, trends, and other characteristics identified in the data over the network460and between other distributed computing components in a distributed computing environment. As one of ordinary skill in the art will appreciate, the configuration module455, provisioning module458, and analytics module459may make up only a subset of various functional and/or functionally responsible entities in the data storage system400.

Other ancillary hardware may be associated with the storage system400. For example, as shown, the storage controller440includes a control switch441, a microprocessor442for controlling all the storage controller440, a nonvolatile control memory443for storing a microprogram (operation software)250for controlling the operation of storage controller440, data for control, cache445for temporarily storing (buffering) data, and buffers444for assisting the cache445to read and write data, a control switch441for controlling a protocol to control data transfer to or from the storage devices430, the configuration module455, provisioning module458, or other blocks of functionality, in which information may be set. Multiple buffers444may be implemented with the present invention to assist with the operations as described herein.

Continuing toFIG. 5, a block diagram depicting a recovery model500of a point-in-time database recovery system is illustrated. Model500includes an operations log502along a (horizontal) time axis. At certain intervals, database backups504A-504nare created using database data (e.g., files) commensurate with their operations log502. When a user (e.g., an administrator), application, and/or other service requests that the database be restored to a particular point in time, the most recent backup is retrieved and the logged operations thereof are re-played over the backup to the specific restore point. In the instant example in model500, to restore the database to the restore point506, the backup-2504B is loaded and the logged operations of the operations log502are replayed until the restore point506to create the restored database508.

FIG. 6illustrates an additional block diagram of an architecture600of the point-in-time database recovery system modeled inFIG. 5. The architecture600includes a primary server602storing a database604. The database604is associated with the operations log502and one or more of the database backups504A-n. The database backups504A-n are sent through a streaming platform610(e.g., a central storage environment) to a recovery server612which stores log data of the operations log502and the one or more backups504A-n (or portions thereof). The recovery server612and the streaming platform610may also communicate with an object storage616. As previously mentioned, a recovery window618is also depicted as encompassing database backups504B-n, which indicate these (least recent) backups are within a predefined time window able to be retrieved for recovery of the database604.

In one implementation, the primary server602is the server that runs the database service and serves the database requests. The recovery server612is reserved solely for the purpose of recovering the database's past states. As the database processes the operations, any state modifying operations, such as, insert, update, delete, are also synchronously logged onto the storage in form of a journal, so that all operations can be recovered in case of a server failure. The journaling feature may additionally be leveraged to log each operation to another storage that is accessible from the recovery server, referred to as a recovery store. This could either be a local to the recovery server612or network attached on-premise storage. In addition to the database operations, the state of the database may also be incrementally backed up on the recovery store. Each backup restore point is marked with a timestamp, which is later used for recovery. The files included in the incremental backup only represent a part of the state required to restore the backup, and therefore, also maintained is a list of files required to restore the backup. All the files that are required to restore to any point within the recovery window618are kept on the backup store. While as the recovery window618slides forward with time, the unnecessary files are deleted from the store. Moreover, any backup restore points can also be backed up into the object storage616for long-term storage.

To recover to a specific time in the past, first is determined the backup restore point just preceding the desired recovery point. The list of files required to restore to that point is then referred to, to determine which files are necessary for the restore. The database604verifies the checksum of the backed up files to ensure correctness of the restore state, and subsequently, the log file (e.g., operations log502) is retrieved succeeding the restore point and the operations are re-played on the database604until an operation is encountered having a desired timestamp.

In various implementations, the time to recover to any prior state of the database604consists of backup restore time and operation log replay time, which may be represented by the equation: Trecovery=Trestore+Treplay. Thus, to predict the frequency and intervals of future backups, the Trecovery time is used to continuously determine the most efficient backup schedule while maintaining the user-defined RTO. The restore time is the time required to restore the database604to a specific backup restore point (e.g., restore point506). The database restore process consists of the following steps: 1) Loading all the required database files from the storage616used for storing backups (note that the set files required for restore are not simply the files that were copied during a specific incremental backup, but additionally includes all the required files); 2) Calculation of the checksum to ensure the integrity of the backup; and 3) Writing the database files to the recovery server612. Since the previous steps are performed in parallel, the slowest step dictates the re-store time. In addition to the amount of data restored, the restore time of a database604also depends upon the characteristics of the recovery system, namely read bandwidth of the backup storage, write bandwidth of the recovery server's storage, CPU used for calculating the checksum, etc. The system may be profiled to consider these system characteristics, such that, for example, on the primary server602, the restore time may be continuously predicted using the given recovery system profile. This restore time may be represented by the equation: Trestore=Max (BWread/SZ, α.SZ, BWwrite/SZ), where

SZ=Amount of required data to be restored.

Similarly, the replay time is the time required to replay the operations log502in order. Since every operation is tagged with a timestamp, only the operations with the timestamp older than the desired recovery point are replayed. The operations log502replay consists of the following steps: 1) Loading of the log file from the storage; 2) Replaying of the operations on the database604; and 3) Persisting the operations to the recovery server's storage. Since, again, each of these steps are performed in parallel, the slowest step dictates the replay time of the operations log502. On the primary server602, in addition to the backup restore time, the replay time since the last database backup504A-n is maintained. Again similar to the restore time, the replay time of an operation depends upon the type of operation, number of operations, record size and the system parameters, such as CPU and storage bandwidth. The following equation shows the model used for predicting the recovery time, expressed as: Treplay=Max(Tload, Texecution, Tpersist).

In addition, the following equation calculates the time to load the operations log502. This time depends upon the size of the operations log502and the read bandwidth of the storage: Tload=BWread/SZ.

In this step, the operation is executed and the changes are captured in the database's in-memory state and in the journal to provide crash consistency. The operations log502consists of different types of operations. Therefore, for each operation type, execution time is calculated separately and combined to calculate the total execution time. The execution time is a function of number of operations and the record size, expressed as: Texecution=ft (Nops, SZrec), t ∈ Operation Type.

The following equation calculates the time required to persist the data recorded in form of operations to the recovery server's storage: Tpersist=BWwrite/SZ, where

Nrec=Number of operations; and

It should be noted that the recovery server612may periodically (i.e., at certain defined intervals) replay portions of the write ahead logs to verify that the predicted time to replay the portion of the write ahead logs matches the actual time taken for replay. This data is then used as feedback to the primary server602to correct and adjust the model used for prediction.

To further predict the frequency and intervals of various backups, often the database workloads show known and predictable patterns. For instance, request surge is expected during a certain period of a day, while the activity slows down during the night. Such workload behaviors can be captured in form of profiles and can be used to schedule the backup so as to minimize its interference with workload. This workload profile may be analyzed to determine the best time to perform backup, with the goal to minimize its adverse impact on the workload, while not overstepping the bounds set by the proposed model to ensure the RTO. This may mean taking a backup ahead of time to avoid it being performed in the middle of an expected surge. Since the backup is a file copy operation, it is primarily a network-bound process. The decision to perform the backup ahead of time is a function of the amount of data to be transferred during the backup and the availability of network bandwidth, and thus, various thresholds may be defined associated with the network bandwidth to determine a best possible backup timeframe of the database604.

Continuous backups and logging the database604operations generate large amount of data. To recovery to any point in time in the recovery window618, all the required files and the operations logs need to be stored. Therefore, the recovery window618size is limited by the amount of available storage for storing the database backups504A-n and operations log502. For fast recovery, high bandwidth storage can be used, however this increases the storage cost. The cost can be reduced by using large amount of cheaper, slower storage, but it can also increase the recovery time. Therefore, in addition to using storage tiering techniques, the placement of files of the database backups504A-n may be distributed amongst local and remote storage systems to maximize the recovery window618size, while keeping the storage cost low.

First, any files that are no longer required by all recovery points within a recovery window for a given database backup504A-n are garbage collected (referred to as garbage collection614) on the recovery server612to reduce the overall storage space needed for storage therein. Next, the database604files are distributed across local and remote storage applications such that only a fraction (e.g., a portion) of files for each restore point are present on either the local or remote storage servers. This fraction is determined so as not to violate the RTO guarantee. In other words, at least a portion of the files required for any particular point-in-time recovery restore point of the database backups504A-n are cached within local storage, while a remaining portion of these files are stored on a remote storage server. The local storage may be storage which is local to the recovery server612and the remote storage may comprise any storage remotely located to the recovery server612(e.g., object storage616). Local and remote recovery is modeled such that the checksum verifications and remote reads of the files from the remote storage is performed in parallel such that a full local restore is equivalent to a fractional restore.

In another embodiment, as an alternative or in addition to the local and remote storage of the file portions, the files may be distributed across faster and slower storage devices such as in a tiered storage environment. In tiered storage, the database files are distributed across different tiers so that only a fraction of files for each restore point are present on specific tier. The fraction is determined so as not to violate the RTO guarantee (i.e., the fraction of files on the slower storage can be retrieved in same time as the fraction stored on the faster storage). Thus, in tiered storage, the operation log segments are distributed across tiers so that the segments with higher load time to execution time ratio are kept on the slower storage devices (e.g., tape, disk drives, etc.) while the segments with lower load time to execution time ratio are kept on the faster storage devices (e.g., solid state drives (SSDs), etc.). This is performed because the segments with small average record size take longer to execute than to load. Therefore, since the loading and execution of operation log segments happens in parallel, for such segments the load time does not account towards the total replay time. Accordingly, for each segment stored in the slower storage devices, the segment must meet the criterion of Texecution<Tload.

For each recovery point (e.g., restore point506), the fraction of files stored remotely on the remote storage may be expressed as, for Sz=f1.Sz+f2.Sz, each restore point maintains: f1.(Sz/B)<f2.(Sz/C) within the remote storage location, where

f1=Fraction of data stored remotely;

f2=Fraction of data stored locally;

C=Rate of checksum (MB/s); and

Sz=Size of total required data.

In case of a database failure, all serialized operations may be stored in write ahead log (WAL). The WAL is used to recover the database604to its consistent state by replaying uncommitted records in the WAL. In some embodiments, WAL load and replay may be performed in parallel. The WAL recovery time is equal to the maximum of the load time and the replay time of the WAL, however, the time to load the WAL from slower storage (i.e., remote storage) can be masked if the replay time is slower than the load time. Thus, as depicted in the recovery model700ofFIG. 7, WAL segments may be selectively placed on local or remote storage (and/or faster or slower storage devices) such that only the WAL segments having a load time higher than a replay time are stored locally on the recovery server612. As depicted in model700, segment-1702and segment-3706are stored remotely, as they have a higher replay time than load time—thus indicating that the slower replay time will mask the load time it takes to retrieve the segments from the remote storage. Segment-2704, however, has a higher load time than replay time, and thus is stored locally so as to unencumber the playback of operations by mitigating the load time by retrieving the segment locally.

Reviewing the illustrated concepts,FIGS. 8A, 8B, and 9illustrate methods800and900, respectively, for optimizing database backups to achieve an RTO. The methods800and900may be performed in accordance with the present invention in any of the environments depicted inFIGS. 1-4, among others, in various embodiments. Of course, more or less operations than those specifically described inFIGS. 8A, 8B, and 9may be included in methods800and900, as would be understood by one of skill in the art upon reading the present descriptions.

Referring now toFIGS. 8A and 8B, the method800begins (step802) by receiving a user-defined RTO configured for one or more databases (step804). An amount of data required to restore the previous backup is measured by the recovery server612(step806). From this measurement value, the recovery time may be computed according to the formula prescribed supra. Periodically (i.e., according to defined intervals, randomly, etc.) a fraction of the captured operations log502is replayed on the recovery server612to determine whether the predicted replay time matches the actual replay time of the log (step808). The log information generated from the replayed operations log502is then used to calculate the actual recovery time (step810), such that the replay of the operations log502is used as feedback to the primary server602to adjust the known recovery time.

Continuing, a backup frequency for initiating backups of the one or more databases is determined based on the continuously predicted recovery time associated with a plurality of factors (including the feedback comparison of the actual recovery time vs. the predicted recovery time) (step812). The backups of the one or more databases are then executed at the determined backup frequency to ensure the user-defined RTO is achieved for the backups of the one or more databases (step814). According to this data (i.e., the determined backup frequency), a re-sharding operation (i.e., splitting a shard into multiple shards) is initiated if the backup frequency is above a predefined threshold (step816). The method800ends (step818).

As mentioned, a database shard is a partition of the data based on the key contents. For instance, in range-based partitioning, the records are divided into shards based on the distinct range to which they belong. Other commonly used sharding is a hash based sharding, where a hash function divides the keys into different buckets which act like shards. Sharding allows the database load to be spread across multiple machines (i.e., much like a distributed computing environment). More shards can be added to scale out the database as the load increases. Even though sharding balances the load across multiple machines, based on the sharding method used and the workload characteristics, certain shards can receive relatively higher load than the other shards, thus causing a skew.

When recovering a sharded system, the entire system may not be operational until all the shards have been recovered. Without any control of the recovery process, each shard recovers at its own pace, thus the slowest recovering shard dictating the recovery of the database. Therefore, considering the disparate nature of the shards, the present recovery system independently models the recovery time for each shard. Each shard independently follows its backup process, so allowing the shards to comply with the given RTO. The timestamps of the backups and operations in the operations log502therefore provide a consistent cut across the shards, so that during recovery, all shards represent respective states at the desired recovery point.

Referring now toFIG. 9, the method900begins (step902) by reducing space overhead at recovery and/or remote servers by garbage collecting files not required by all recovery points within the given recovery window of a particular point-in-time database backup (step904). A fraction of files from each recovery point are stored on local storage, and local and remote recovery of the database backups associated with the files are modeled such that checksum verification and remote reads from the remote storage are performed in parallel (step906). The remaining portion of the files associated with each recovery point of the database backups are stored in a remote storage location according to a remote read bandwidth, a rate of checksum, and a size of the total required data to complete the database restore (step908). The method900ends (step910).