Restoration of a data source

Restoring data to a data store that suffered corrupted data over a time period is disclosed. A system may provide an interface to specify a time window and filter conditions for identifying corrupted data in an object in a data store, such as, but not limited to, a corrupted NoSQL table. Corrupted data is identified by applying the filter conditions to change logs for the data object (e.g., the No SQL table) in the data store. Repair operations are determined for individual items identified via the filter conditions. Identified corrupted data for items may be corrected, from change logs or backup data in some instances (e.g., data may be deleted, or updated or replaced with data from a backup of the data store when necessary).

BACKGROUND

Several leading technology organizations are investing in building technologies that sell “software-as-a-service”. Such services provide access to shared storage (e.g., database systems) and/or computing resources to clients, or subscribers. Within multi-tier e-commerce systems, different resources may be allocated to subscribers and/or their applications from whole machines, to CPU, to memory, to network bandwidth, and to I/O capacity.

For example, a data store such as a database system managing large amounts of data on behalf of users may distribute and/or replicate that data across two or more machines, often in different locations, for any of a number of reasons, including security issues, disaster prevention and recovery issues, data locality and availability issues, etc. These machines may be configured in a number of ways, including as a shared resource pool. For example, a database table may be split into two or more partitions, each of which may be replicated, and each replica may be stored on a different machine. Interaction between client applications and database servers typically includes read operations (read-only queries), write operations (to store data), and update operations that can be conceptualized using a read-modify-write workflow.

Clients with large-scale data stores (e.g., such as large-scale databases) may create proprietary backup solutions that scan data from a data store into scalable, durable storage, but these solutions suffer from a number of problems such as taking too much time to perform the backup, interrupting a customer's regular workflow, tying up resources (e.g., scan-based solutions can compete with production workloads for read throughput), and providing only limited options for restoring from static backups (e.g., periods of time between backups may be too long). Additionally, getting a consistent backup across a large number of storage nodes can be hard to do without the customer stopping all writes. Scan-based solutions can be expensive (e.g., a scan backup of a 100 TB table, etc.) both in compute costs and storage costs and may not provide a managed experience (e.g., a managed experience where customers can view characteristics of the backups, manage the backups, etc.).

Some systems perform timed, periodic backups by scanning the data store to create a copy of the data store. But, the period of time in-between backups of a periodic system may be of a length that prohibits restoring the data store to a particular point-in-time of interest (e.g., if the point-in-time of interest falls in-between to backups).

Some database systems require backup of the entire table (e.g., all partitions are backed-up at once, as a coherent whole). Generally, database systems require obtaining a copy of the entire authoritative database in order to generate the next full backup snapshot.

Additionally, even if backups are generated, none of the NoSQL database systems restore data from a backup copy to a corrupted live NoSQL production database table and NoSQL database systems generate change logs suitable for restoration of corrupt data.

DETAILED DESCRIPTION

Introduction

In various circumstances, such as in the case of corrupted data, missing entries, or in the case of a system outage, etc., it may be useful to restore data to a data store. Corrupted data may occur for any of various reasons, such as a bad code push, improper encryption of variables, or execution of faulty scripts, as just a few examples of many more. In some instance, it may be preferable to restore data to the data store while that data store is actively receiving data traffic, such as restoring corrupted entries in a production NoSQL database that continues to accept read and write operations from clients while the restoration is performed, for example, although other particular types of data stores are also contemplated.

Database systems do not provide customers with a way to restore corrupt data in an active production table, certainly not on an item-by-item basis as described herein. For example, undo logs of relational database systems are used to undo failed individual transactions, not restore corrupt data. Additionally, the dependencies among the indexes for items in a relational database system prevent restoration of corrupt data on an element-by-element basis. For instance, for a RDBMS, if a database crashes, the recovery process has to apply all transactions, both uncommitted as well as committed, to the data-files on disk, using the information in the redo log files.

Disclosed are systems, processes and program instructions for restoration of an active data source, while the data store is available to receive traffic (e.g., a live relational database; a key, value object store; a live production NoSQL table that continues to accept read and write operations; etc.). While it may be possible to create a restored secondary table based upon a backup copy or snapshot (necessarily reflective of a point in time prior to the corruption), and then point the processes using the production table away from the production table and to the secondary table, such a switching scheme has pitfalls at least because the production table may still have corrupted data or missing entries, etc., and furthermore, there is no mechanism to replay the good entries from the restored secondary table to the production table, not while the production database that is actively receiving traffic, anyway.

Additionally, such a use of the restored secondary table ultimately includes some amount of data loss, such as loss of the valid changes to the database that happened subsequent to the time of the generated secondary table, and/or loss of valid changes (e.g., live customer traffic) to the database that happened subsequent to the time of corruption. Additionally, at least some amount of inaccessibility is associated with the above-described database table switching scheme (e.g., reestablishment of connections, etc., may prevent writes to a live table).

In an example of the deficiency of the switching scheme, it may not be unusual for a customer to overlook or not become aware of a data corruption for hours or days or even longer after the corruption happens. Because the switching-to-a-restored-secondary-table scheme necessarily requires generating a backup table at a time prior to the corruption, such a scheme may result in hours, days or longer periods of time-worth of lost valid data changes associated with live customer traffic. Techniques described herein may minimize or even eliminate data loss while correcting corruptions in a live data source. For example, the restoration of data to a live NoSQL database table, as described in embodiments herein, can correct the corrupted data, and also keep the live production table up-to-date for the live customer traffic that affected the live production table after the corruption event, unlike other techniques for restoring database tables.

As disclosed herein, various embodiments describe a technique for restoration of an active data source. In embodiments, the system implements an interface (e.g., an application program interface (API) or GUI, or other interface) that receives specification of certain filter conditions from a client. The filter conditions may be used to discover corruptions to the data store. In an example, a NoSQL database table may experience a loss or corruption of data (e.g., for a period of time, and/or associated with data having a particular characteristic—such as data for a particular client, customer, etc.). In embodiments, a restoration process may process a log of transactions for the NoSQL database table that occurred during the period of time and revert all the changes that happened during that period of time. In embodiments, the filter conditions may be applied to entries in the change log to determine which entries are corrupt and should be corrected while leaving other entries not identified as corrupt. In some embodiments, the restoration process may process the log of transactions that occurred during the period of time and revert the corrupt changes that happened during that period of time while giving preference to manual corrections that customers had already made. The manual corrections may be determined via application of the filter conditions, for example (e.g., source IP address or userID associated with change). Filter “conditions” and filter “criteria” may be used herein to indicate similar features of the disclosed invention.

In some instances, the corrupt data may be discovered and identified by a manual process performed by a customer (e.g., administrative personnel) of the service provider. In embodiments, an automated corrupt data discovery process may include application of filter conditions to items in a change log stream to identify that data in the data store has been corrupted. For example, system alarms based on the filter conditions may identify corrupt data. In one particular example, an application that uses data and that stops working due to corruption of the data might send an error that identifies the corruption.

In some instances, the time window may be determined by an automated corruption discovery process. For example, a corruption discovery process may apply filter conditions, such as those described herein to the change logs in a process that is synchronous (in real-time with the changes being published) or asynchronous (e.g., periodically) with the publishing of the changes by the change log stream service. Corrupt data discovered by the filter conditions may trigger a start of a time window. An end of discovery of the corrupt data may indicate an end of the time window. A corrupt data alert may be initiated and/or sent to the client, in some embodiments. In some instances, the process for restoration of a data source may be automatically triggered by the discovery process.

The filter conditions may operate on any of the table columns and may have additional variable (e.g., outside table columns) such as IP address, region, time, etc. (a non-exhaustive list). Then, for example, a repair process may include iterating over the stream of changes made to the data store and, for a change that satisfies one or more of the above-noted conditions, a correct entry may be pulled from the restored secondary table (or from the change log, in some embodiments) and made as a change to the active data store.

In some embodiments described herein, a repair manager provides an interface for the system to receive a time window (e.g., entered by an administrator of a client, the service provider, or determined otherwise, such as via an automated corruption discovery process, described below) during which items in a data store were corrupted. Filter conditions, used to identify corrupt entries, may also be received via an interface. A non-exhaustive list of example filter conditions includes a data value or data value range for one or more attributes of items in the data store, a data type for one or more attributes of items in the data store, or a metadata value for items in the data store. An example metadata value may specify a source identifier (e.g., an internet protocol (IP) address, a user identifier, account identifier) or location identifier for an item change.

To identify corrupt entries in the data store, the repair manager may examine items in a portion of a change log for the data store (e.g., the portion of the change log may indicate changes made to items in the data store during the time window). Examination of the items from the change log may include the repair manager applying filter conditions to each item, or to metadata for each item, to identify individual items that are corrupted. In embodiments, the repair manager may determine a repair operation for each individual item identified to be corrupted and instruct or perform the repair operation to the data store while the data store continues to accept read and write operations from one or more clients of the data store.

Determination of Repair Operation

In embodiments, the repair manager may determine a change type and corresponding repair operation (e.g., insert, modification, remove) from an entry of the change log for the item (e.g., as illustrated inFIG. 5, described below). For example, some data logging systems or services may report both the before and after images for a changed item. In an embodiment, the repair manager may determine, based on the entry in the change log that indicates the change type is an item insert, the repair operation to be a delete of the item from the data store. Similar logic may be applied to other operations. For example, the repair manager may, in response to a determination that the change type is an item modification, determine the repair operation to be an update of the item in the data store. In another example, the repair manager may, in response to a determination that the change type for the entry in the change log is an item remove, determine the repair operation to be an insert to the item in the data store.

Source of Data for Repair Operation

The data used to repair the corruption may be come from any of various sources. For example, in systems that generate change logs for changes to objects in data stores and report both before and after images of the entry in the change log, the data used to correct the corruption may come from the change log (e.g., illustrated inFIG. 1, described below) for the corresponding object in the data store. In some instances, for corruptions that repeatedly affected the same entry, the repair manager may use the filter conditions to identify which one of the multiple changes to an entry was the most recent valid entry. For example, a filter criterion based on a particular data type for an entry may eliminate a number of modifications for the same item that were of the incorrect data type and perform a single restoration with the non-corrupt entry that is of the correct data type.

In data storage systems that create backup copies of the data store (e.g., archival snapshots of objects such as tables, etc.) the snapshots may act as a source for the data used to correct the item entries (e.g., illustrated inFIG. 3A, described below).

The repair manager may perform the repairs based on the change type. For example, the repair manager may, in response to a determination that the repair operation is an update operation, determine non-corrupt data from the change log for the item that is valid prior to the time window. In at least some such cases, the repair manager may perform the update operation to the data store to update the item in the data store with the determined data. Other examples based on similar logic apply without departing from the scope of the disclosure. For example, the repair manager may, in response to a determination that the repair operation is an insert operation, determine data for the item that is valid prior the time window from the change log. The repair manager may perform the insert operation to the data store to insert the item in the data store with the determined valid data.

In an example where a restored copy of the data object acts as a source of the non-corrupt data, the repair manager may request creation of a restored copy of the data object restored at a time immediately prior to the time window. In response to a determination that the repair operation is an update operation, the repair manager may determine a value or other data for the item that is valid prior the time window from the restored copy of the data object. The repair manager may perform the update operation to the data store to update the item in the data store with the determined data. Similar logic for other operations are applicable. For example, for an insert operation, the repair manager may request the creation of the restored copy, and use the data for the item from the restored copy that is valid prior to the time window to correct the corrupt data.

In various embodiments, a data object may be repaired with or without using the filter criteria. For example, using a NoSQL database table as one example of many types of data objects, the system may determine a time window during which one or more items in a NoSQL database table were corrupted (e.g., determine via receipt of the time window via an interface) and select a corresponding portion of a change log for the NoSQL database table. The corresponding portion of the change log may indicate changes made to items in the NoSQL database table during the time window. For individual items from the portion of the change log the repair manager may determine a repair operation for the individual item, and perform the repair operation to the NoSQL database table while the NoSQL database table continues to accept read and write operations from one or more clients of the NoSQL database table.

An Example Source of Data for Restorations: A Data Protection System

As described herein, a system may perform a technique of restoration that restores corrupt entries in a data object while leaving or retaining entries that were changed after the corruption happened. Such a technique is an improvement or prior systems at least because, as described in the introduction, above, data loss is minimized if not eliminated altogether. In embodiments, the technique performs restoration at an item-level granularity, instead of rolling back all the changes regardless of whether the changes caused data corruption or not. A data protection system, like that described below, may act as a source for the non-corrupt data, in embodiments.

In embodiments, a data protection system captures all of the changes happening on the data store (e.g., a database) and periodically builds system snapshots (sometimes referred to as copies, herein) by applying logs on the closest system snapshot.

For example, the system may be able to apply transaction logs to a previous logical backup to create a new point-in-time logical backup, without losing any customer data, in some instances. For example, system snapshots may be built at a partition level (e.g., for systems that partition data) by applying the change logs to prior snapshots. In some such embodiments, the data protection system generates backups without any additional queries or scanning of the client's production data store by relying on prior snapshots and change log data to create new snapshots, instead. Accumulation of change log data for a table, as well as generation of updates to snapshots for the table may be performed independently for each partition (e.g., at a different time) of a same table, based 15 on characteristics particular to each partition for example, in some embodiments.

Backup and Restore Via Log-Apply

In embodiments, a log apply service of the data protection system is responsible for at least two core functionalities to support backup and restore. During a conversion process, the log apply service may convert partition snapshots (sometimes referred to as backups) from a physical format (e.g., mysql) to a logical format snapshot. The log apply service may also create subsequent point-in-time logical partition snapshots by applying transaction logs to a previous logical partition snapshot, and create a complete user backup, for example.

In some embodiments, continuous capture of individual changes to a table provide for a more fine-grained availability of those individual changes at a later time. For example, the accumulation of individual changes to the data—data that constitutes a state of the database table at a time, in embodiments, may be used to more accurately take the table—or partition—back to a particular state at any point-in-time along a continuum. Such features contrast with prior systems that could only take the system back to a select few points-in-time when snapshots of the system were taken. In some such prior systems, the snapshots added additional burden to the client's production system because the snapshots were created from scans of the production database, interrupting or delaying production services. Additionally, scan-based snapshots take relatively more time to create, and fail to provide as accurate a view of the database as the techniques disclosed herein, at least because, by the time the scan completes (at least for large data sets), data that has already been scanned may have been changed.

Additionally, in at least some embodiments, the techniques described herein are applied on a partition-by-partition basis. For example, snapshots and change log data for a particular partition may be kept in an uncoordinated manner, with respect to the other partitions of the table (e.g., according to different schedules). A relatively inactive partition of a table may have a snapshot generated based on a maximum duration of time threshold, while another relatively active partition of that same table may have snapshots generated more often, based on an amount of accumulated changes, as just one example of many. The times at which the snapshots are created for either partition may not have any relationship, and may be based upon the particular characteristics of that partition, in embodiments.

The above-noted process may be triggered when a customer enables backups for a given table. In embodiments, the data protection manager312(illustrated inFIG. 3) may initiate the first complete backup of the table, during the initial backup process. For example, for all partitions of the table, the data protection manager or service may store the snapshots by exporting data from storage nodes to storage-level physical format into a durable storage.

In embodiments, a log apply process is used whenever the data protection manager or service decides a new logical partition snapshot is required to bound the time taken for creating point-in-time backups. Log apply may also be used during restore to apply logs to a backup.

In some systems, log applying backups is an expensive operation (e.g., when there is a relatively greater amount of time and greater number of changes between backups). By relying on pre-existing incremental partition images to define a backup, the system may significantly reduce the load on the log apply service, saving compute costs. Additionally, by relying upon incremental partition images to define a backup, the system may allow users to create many backups partially sharing the same set of logs and base partition images, which may translate into storage costs savings.

In some embodiments, a periodicity at which system snapshots of the partitions are built is decided based on an amount of logs accumulated. For example, the periodicity may be based on a threshold amount of logs accumulated. In another example, the periodicity may be based upon a rate of change of the logs accumulated. For instance, if the system is becoming more active more changes are being generated . . . the increase in the rate of change of the number of logs may be used as a trigger to increase the periodicity. In some embodiments, the log apply service applies logs for a single partition on a single host. In some circumstances (e.g., large tables) each partition may be log applied in parallel to reduce the time to apply the logs for the table, e.g., by respective parallel processes.

In embodiments, both the newly-created snapshots as well as the change logs are stored to durable storage. In some such embodiments, the snapshots and the durably-stored change logs may be used to restore the partition. In some embodiments, the continuous data protection backup service provides an interface and functionality supporting unified management of the data, while optimizing customer costs and restore times via periodic log application and trimming.

Another benefit of some embodiments is a predictable time to recovery, by accurately identifying continuous backups, which, if restored, would cause the system to break SLAs and take appropriate action to bring the system back into compliance.

The systems and methods described herein may be employed in various combinations and in various embodiments to implement a network-based service that provides data storage services to storage service clients (e.g., user, subscribers, or client applications that access the data storage service on behalf of users or subscribers). The service may, in some embodiments, support data protection of tables that are maintained on behalf of clients in a data store, e.g., a non-relational database or other type of database. The service may provide a high level of durability and availability through replication, in some embodiments. For example, in some embodiments, the data storage service may store data in multiple partitions (e.g., partitions that each contain a subset of the data in a table being maintained on behalf of a client), and may store multiple replicas of those partitions on respective storage devices or virtual storage volumes of different storage nodes.

In some embodiments, the data storage systems described herein may provide mechanisms for backing up a database table as a synchronous operation while the database continues to receive, accept, and service read and/or write operations that are directed to the table. In some embodiments, in response to a request to back up a table, the system may create a backup of each individual partition independently and (in some cases) in parallel (i.e., substantially concurrently). In embodiments, when a request to back up a table is received, the system may guarantee that all write operations that were directed to the table up to that point are included in the backup. In some embodiments, such a guarantee may not be made.

In some embodiments, backup operations may be initiated by data storage service users (e.g., customers, service subscriber, and/or client applications) using a “CreateBackup” application programming interface (API). In some embodiments, the systems described herein may support the scheduling of backups (e.g., every day at a particular time, or according to a published, but not necessarily periodic, schedule). In response to receiving a request to back up a table, these systems may back up each partition of the table as an individual item in a remote storage system (e.g., a key-value durable storage system), and may store metadata about the backup that is subsequently usable when restoring the backup to a new database (e.g., a new database table). In some embodiments, the system may be configured to initiate separate backup operations for each of the partitions of a table automatically (e.g., programmatically and without user intervention) in response to a request to back up the table, and to manage those backup operations on a per-partition basis (again, without user involvement).

In various embodiments, the data storage service described herein may provide an application programming interface (API) that includes support for some or all of the following operations on the data in a table maintained by the service on behalf of a storage service client: put (or store) an item, get (or retrieve) one or more items having a specified primary key, delete an item, update the attributes in a single item, query for items using an index, and scan (e.g., list items) over the whole table, optionally filtering the items returned. The amount of work required to satisfy service requests that specify these operations may vary depending on the particular operation specified and/or the amount of data that is accessed and/or transferred between the storage system and the client in order to satisfy the request.

Another API may allow consumers to update the current settings for a table within the database service, for example, to enable or disable the continuous backups and modify the duration of time to retain backups.

In various embodiments, the systems described herein may store data in replicated partitions on multiple storage nodes (which may be located in multiple data centers) and may implement a single master failover protocol. For example, each partition may be replicated on two or more storage nodes (or storage devices thereof) in a distributed database system, where those replicas make up a replica group. In some embodiments, membership in various replica groups may be adjusted through replicated changes, and membership and other updates in the system may be synchronized by synchronizing over a quorum of replicas in one or more data centers at failover time.

As described herein, when a database table is created or restored from backup, various resources may be provisioned for the implementation of that table, including storage resources (e.g., disk capacity), and throughput capacity (which may, e.g., be specified in terms of input/output requests per second, or IOPS, for read operations and/or write operations). If the table is divided into two or more partitions (e.g., if various data items are stored on different ones of the partitions according to their primary key values), the provisioned resources may also be divided among the partitions. For example, if a database table is divided into two partitions, each partition may have access to half of the total amount of storage and/or throughput resources that are provisioned and/or committed for the implementation of the table.

In some embodiments of the distributed database systems described herein, each storage node may include multiple storage devices or logical volumes, each of which stores various partition replicas. For example, in one embodiment, each storage node of the distributed database system may include five storage devices or logical storage volumes. In some embodiments, one or more mechanisms may be implemented on each of the storage nodes for determining, on a local level (e.g., on a storage node basis) whether and/or how to split a partition or move a partition (or a given replica of a partition), based on the current utilization of provisioned resources and/or other information. For example, one of the storage nodes may be configured to determine that a partition for which a replica is stored on one of its storage devices (e.g., disks) or logical storage volumes should be split into two new partitions, and may divide the data in the partition by hash ranges, by key space ranges, or using other criteria to divide the data between the two new partitions. In another example, a storage node may be configured to determine that one or more partitions (or replicas thereof) should be moved from a given storage device or logical storage volume to another storage device or logical storage volume, e.g., in order to reduce the amount of provisioned storage capacity or throughput capacity on the given storage device or logical storage volume.

As noted above, from a user's perspective, a backup operation generally operates to create a backup of a whole table, but internally, the system may back up each partition of the table independently, such that consistency is guaranteed only up to a particular transaction or write operation on a per partition basis (rather than across the whole table). In some embodiments, the system may be configured to maintain metadata about the table (e.g., to keep track of the table schema, and the state of the world from the perspective of the table and of each partition). In some embodiments, this metadata may be stored in the data storage system itself, and a copy of the metadata may also be stored in the remote storage system into which tables are backed up.

DETAILED DESCRIPTION OF FIGURES

FIG. 1is a block diagram illustrating logical relationships between components of a system for restoration of a NoSQL database table, according to some embodiments. Techniques similar to those illustrated in at leastFIGS. 2, 4A-B, and5may be performed by one or more components illustrated inFIG. 1, in embodiments.FIG. 2is a process diagram illustrating a technique for performing restoration of a NoSQL database table, according to some embodiments. Features illustrated inFIG. 2may be performed by components of the system illustrated inFIG. 1, in embodiments.

The system illustrated inFIG. 1is a service provider100that provides services (e.g., a NoSQL database service) to clients102A-N via one or more networks104.FIG. 1illustrates that NoSQL database120provides uninterrupted servicing of read/write operations117from clients102A-N (e.g., read/write operations directed to tables122A-N) while restoration requests, restoration processing and/or restoration responses119are handled by the repair manager110. In the illustrated embodiment, client(s)102A-N may include processes (internal or external to the service provider100) operating on behalf of a customer of the service provider100that send read/write operations117to NoSQL database120. In the illustrated embodiment, client(s)102A-N also include an administrative client of the customer that makes requests of the repair manager via interface112(illustrated inFIG. 6, described below). In some embodiments, the restoration described herein may be performed on objects of the data store while the data store continues to receive read and write operations for those objects (e.g., an active or live, production data store that is available to receive or is actively receiving read and write operations.). For example, repair manager110may include a repair controller114that may perform the restoration using data from a change log of change logs132A-N of change log stream store130to update an entry in the corresponding table in NoSQL database120.

In at least the illustrated embodiment, the disclosed restoration technique illustrated inFIG. 2relies upon data from a change log for the NoSQL database table as a source of data to use to correct corrupt entries in the table (other sources of correct data may be used, in embodiments). For instance, at block202, a time window is determined during which items in a NoSQL database table were corrupted (e.g., a repair manager110may implement an interface112like that illustrated inFIG. 6, described below for receiving specification of the time window). At block204, a portion of a change log (e.g., change log132A) is selected for the NoSQL table (e.g., table122A) that indicates changes made to items in the table during the time window. In embodiments, there may be a one-to-one relationship between objects of a data store and a respective change log for the data store. In some embodiments, a group of change logs (e.g., change logs of various dates) may include changed to items in the same data object. The repair manager110may select the portion of the change log (e.g., suitable for the time period) from a change log data stream store130. The change log stream store may be implemented variously. For example, the change log stream store may be implemented as a feature or service of the data store (e.g., a data stream service of the data store that reports changes to objects in the data store), or may be implemented as a stand-alone data logging service, such as a data streaming service.

At block206, an item may be selected from the change log, and at block208a repair option for the item is determined (by the repair manager110, for example). An example technique for determining repair options is illustrated inFIG. 5, described below. Repair options may vary (e.g., delete, insert, update, etc.). At block210, data from the change log stream store (e.g.,130) may be used to perform the repair option to the NoSQL database table while the table continues to accept read and wrote operations from one or more clients of the table, for example. Blocks206,208and210may be repeated for each of the items in the change log. For example, if there are more items in the change log (block212, yes) the process may return to block206and repeat. If all the items from the change log have been examined (block212, no) an indication that the restoration is complete may be transmitted (block214). For example, an indication that restoration is complete may be sent to the interface illustrated inFIG. 6, described below, or otherwise.

In some embodiments, the repair manager110includes a filter engine (not illustrated inFIG. 1). In embodiments, the filter engine may receive filter condition (e.g., via the interface112, or otherwise) and may be apply the filter condition to items in the change log to identify which items in the corresponding data object are corrupt such that the repair controller can restore the corrupt item with non-corrupt data.

FIG. 3is a data flow diagram illustrating data flows between components of a system for restoration of a data source, according to some embodiments. The illustrated components may perform techniques like the techniques illustrated inFIGS. 4A-B,5and6, in various embodiments.

InFIG. 3, a data store120stores objects302A-N on behalf of clients102A-N and a data protection manager304that may perform some of the techniques described above as part of the data protection system for protecting items in data objects302A-N. For instance, data store120may produce change logs132A-N that are stored at a change log stream store302and the data protection manager304may use the change logs132A-N, in combination with archived copies of objects302A-N stored in data store archive306to generate restored copies of the objects302A-N (e.g., copies restored to a point-in-time just before a corruption event). The restored copies may serve as a source of non-corrupt data for the restoration processes described herein. Various parts of the restoration may be performed by components of the repair manager110. For example, the interface112may receive an indication of the time window and/or the filter condition for the filter engine116to apply to the items in the change log, and the repair controller114may perform the repair portions of the restoration, in embodiments.

Various embodiments described herein are performed on an “active” or “live” data store. For example, an active data store may be a production data store that is actively engaged in receiving and processing requests (e.g., read and write requests). Some active data stores may be available to accept read and write requests, but may not be actively accepting read and write request simply because no requests are coming in, in embodiments. Some such data stores may still be considered live or active, in embodiments. Embodiments are contemplated where the restoration is performed on a data store that is not active. An inactive data store may not be available to accept read and write operations, for example.

The source of the non-corrupt data for performing the restoration may come from various sources.FIG. 4Ais a flow chart illustrating a technique for restoration of an active data source using data from a change log, according to some embodiments.FIG. 4Bis a flow chart illustrating a technique for restoration of an active data source using data from a restored copy of the data store, according to some embodiments.FIG. 4Cis a data flow diagram illustrating the flow of data during the restoration process, in accordance with various embodiments. The techniques and data flows illustrated inFIGS. 4A-Cmay be performed by components illustrated inFIGS. 1, 3, 6 and 7in embodiments.

At block402a time window during which items in a data object in a data store were corrupted is determined. For example, the time window may be received via interface112(e.g., illustrated inFIG. 6, described below) of repair manager110from an administrator for the system, or the system may automatically determine the time window by an automated corrupt data detection process that relies upon applying filter condition to change logs to determine corruption events.

A change log for the data object in the data store that indicates changes to items in the data object during the time window is obtained (block404). For instance, the filter engine116may obtain or identify the change log (e.g., one of change logs132A-N) from change log stream store130and obtain the portion of that change log that corresponds to the time window.

An item may be selected from the change log and examined (e.g., by the filter engine116) based on application of filter conditions that identifies the item as corrupt (block408). For an item that is determined to be corrupt (e.g., identified by the filter conditions, block408, yes) a repair operation for the item may be determined. For example, the repair manager may determine the repair option in accordance with the technique illustrated inFIG. 5, described below. At block412, if needed (e.g., to correct a delete operation that corrupted the item) data for the item from the change log may be used to perform the repair operation to the data object while the data store continues to accept read and write operations for the data object from a client or clients of the data store. For example, the repair manager110may perform the repair operation to a live, production data store. In at least some embodiments (e.g., when the repair operation is a delete operation that does not require data to perform the restoration) the system may perform the repair operation without determining data for the item. The process may then continue to block414. If the item is not determined to be corrupt (e.g., is not identified by the filter conditions, (408, no)) the process may proceed to block414.

At block414, a determination is made as to whether there are more items in the change log. For example, the repair manager110may attempt to obtain another item from the change log. If there are more items (414, yes) the process may return to block406and repeat until all the items in the change log have been examined. If there are no more items in the change log (e.g., if all of the items have been examined for the time period (414, no)) the system may indicate that the repair is complete. For instance, the repair manager may send a message that the restoration process is complete in response to the request to perform the restoration.

FIG. 4Bis a flow chart illustrating a technique for restoration of an active data source using data from a restored copy of the data store, according to some embodiments. At block420, a time window during which items in a data object of a data store were corrupted is determined. At block422generation of a restored copy of the data object restored to a time immediately prior to the time window is requested. For example, repair controller114may transmit a request to data protection manager304requesting generation of the restored copy and the data protection manager304may apply a change log from change log stream store130to a copy of the object to generate the restored copy of the object at a time just prior to the time window (e.g., just prior to the data becoming corrupted). In some embodiments, the repair manager may perform the functionality attributed to the data protection manager304.

At block424, a portion of a change log associated with the data object and that indicates changes made to items in the data object during the time window is selected (e.g., by the repair manager110). In some embodiments, the repair manager may request the data protection manager to obtain the portion of the change log. Block426illustrates that an item from the change log is selected and block428illustrates that a determination of whether an item is identified as corrupt based on an examination that includes application of the filter conditions. If the data is identified as corrupt (block428, yes), a repair operation for the item is determined. For example, repair manager110may apply a technique similar to the technique illustrated inFIG. 5to determine the repair operation. Block432illustrates that, if needed (e.g., to correct a delete that corrupted the item) data from the restored copy is used to perform the repair operation while the data store continues to accept read and write operations from a client or clients of the data store for the data object. In at least some embodiments (e.g., when the repair operation is a delete operation that does not require data to perform the restoration) the system may perform the repair operation without determining data for the item. The process may then proceed to block434. In the case where the item is not identified as corrupt by the filter conditions (block428, no) the process may then proceed to block434. At block434, if there are more items in the change log (block434, yes) the process may return to block426and iterate. If there are not more items in the change log (block434, no) completion of the repair is indicated. For example, the interface may indicate the restoration process is complete. In instances where the restoration process is unable to complete the restoration, an error message may be transmitted or displayed via the interface.

FIG. 4Cis a data flow diagram illustrating the flow of data during the restoration process, in accordance with various embodiments. The data flow depicted inFIG. 4Cmay be performed by components inFIGS. 1, 3, and 7, in embodiments.

The data flow illustrated inFIG. 4Cis illustrated at a high-level and corresponds to the process illustrated inFIGS. 2, 4A-B, and5, leaving out some steps, in some embodiments. Generally, a three-step process is illustrated where (1) the repair manager examines items in a change log from the change log stream store130using filter criteria to determine which items in the log are associate with a corrupt entry in the current online object120A. For identified corrupt items in the change log, the repair manager may (2) obtain non-corrupt data values (if necessary, no data may be necessary of the restoration operation is a delete) from a restored copy of the object120B. The restored copy of the object120B may include data for the item at a state prior to the corruption322. The repair manager110may delete or write the value obtained from the restored copy of the object to the currently on-line object120A which includes both corrupt and non-corrupt data320, at least until the restoration process is complete.

FIG. 5is an example technique of determining repair operations for restoration of an active NoSQL database table, according to some embodiments. In some embodiments, the technique illustrated inFIG. 5is similar to the functionality illustrated in blocks208,210,410,412,430,432ofFIGS. 2, 4A and 4B. The functionality may be performed by components illustrated inFIGS. 1, 3 and 7, for example.

At block504, the system determines whether an entry in the change log indicates a change type of “insert”, “modification”, or “remove.”FIG. 5illustrates that for the “Insert” change type, the repair operation is determined to be “delete” (block506) and performance of the operation includes performing a delete operation for the item in the data object (block508).

FIG. 5illustrates that for the “Modification” change type the repair operation is determined to be “update” (block510) that non-corrupt data for the item is retrieved for the item from a corresponding log or from a corresponding restored object (block512). Performance of the operation includes performance of the insert operation for the item in the data object (block514).

FIG. 5illustrates that for the “Remove” change type the repair operation is determined to be “insert” (block516) and non-corrupt data for the item is retrieved from a corresponding log or from a corresponding restored object (block518). Performance of the operation includes performing the insert operation for the item in the data object (block520). Other change types and other repair operations are contemplated without departing from the scope of this disclosure.

FIG. 6is an example of a graphical user interface for receiving information for and initiating restoration of an active data source, according to some embodiments. Other types of interfaces are contemplated for achieving similar functionality, such as command line interfaces or APIs, etc.FIG. 6illustrates a data store repair interface610that includes several sections. In the repair time window section, start and end times for a repair window may be specified. The system may receive the specified start and end times for the repair window and use them to determine a portion of a change log to apply filter criteria to identify corrupt data while leaving non-corrupt updates, for example. In some embodiments, an automated corrupt data identification service may identify start and end times for the restoration.

A filter criteria section of data store repair interface610illustrates that one or more filter criterion may be specified. The interface may include interface elements for specifying a filter category, such as whether the filter is applied to data or metadata, in embodiments. The illustrated embodiment depicts an entry for filter criteria and a non-exhaustive list of example includes an Internet Protocol address, a userID, and an accountID. Other interface elements indicate that additional filter criteria may be added.

A target section of data store repair interface610illustrates that one or more interface elements may obtain information that identifies the object to be restored.

FIG. 7is a block diagram illustrating a service provider network that implements restoration of an active data source, according to some embodiments. Depicted is a repair service110similar to the functionality provided by repair manager110illustrated inFIGS. 1 and 3that may perform some of the steps illustrated in at leastFIGS. 2, 4A-C,5and6. The repair service110is illustrated as part of service provider network100that includes database service120, storage service790, compute service740, client(s)760as well as other storage services710and other services720. In at least the illustrated embodiment, the service provider network100is communicatively coupled to client networks160A and clients160via network(s)104. Service provider network100may provide one or more services to a plurality of distinct customers, each distinct customer comprising a distinct customer network, in embodiments. One or more of the components inFIG. 7may be implemented by one or more of the computing nodes1200illustrated inFIG. 12, in embodiments.

The methods described herein may in various embodiments be implemented by any combination of hardware and software. For example, in one embodiment, the methods may be implemented by program instructions executed on or across a distributed computer system that includes multiple processors. The program instructions may be configured to implement the functionality described herein (e.g., the functionality of various servers and other components that implement the restoration of a data source described herein.

FIG. 8is a block diagram illustrating a computing node configured to implement at least a portion of the technique for restoration of a data source, according to various embodiments described herein. For example, computing node800may represent a computing node that implements one or more of the techniques or components described herein for providing restoration of a data source, according to various embodiments. In various embodiments, computing node800may be configured to implement any or all of the components of a system that implements a system for restoration of a data source, and a corresponding continuous data protection system, or multiple computing nodes similar to or different from computing node800may collectively provide this functionality. For example, in various embodiments, one or more computing nodes800may implement database service120, repair manager110, change log stream store130, data store archive306, or clients160. Additionally, any number of storage node instances may each host one or more replicas of various data partitions and/or metadata associated therewith. For example, any given storage node instance may host a replica acting as master replica for its replica group and/or a replica acting as a slave replica in its replica group.

Similarly, one or more computing nodes800may implement a key-value durable backup storage system (or an interface or other component thereof), in different embodiments. Computing node800may be any of various types of devices, including, but not limited to, a personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, handheld computer, workstation, network computer, a consumer device, application server, storage device, telephone, mobile telephone, or in general any type of computing device.

In some embodiments that include multiple computing nodes800, all of the computing nodes800may include the same or similar hardware components, software components, and functionality, while in other embodiments the computing nodes800comprising a computing system configured to implement the functionality described herein may include a wide variety of hardware components, software components, and functionality. In some embodiments, multiple computing nodes800that collectively implement restoration of a data source may be components of a larger shared resource system or grid computing system. It is noted that different elements of the system described herein may be implemented by different computing nodes800. For example, a computer system that supports the functionality described herein for performing restoration of a data source may be implemented on the same computing nodes800on which clients (through which a customer or subscriber may access the system) execute, or on one or more other computing nodes800, in different embodiments. In another example, different subsystems (e.g., a Web service interface, an admission control subsystem, a service request subsystem; and/or one or more Web servers or other components) may be implemented on or across multiple ones of the computing nodes, and each of the computing nodes may be similar to computing node800.

In the illustrated embodiment, computing node800includes one or more processors810(any of which may include multiple cores, which may be single or multi-threaded) coupled to a system memory820via an input/output (I/O) interface830. Computing node800further includes a network interface840coupled to I/O interface830. In various embodiments, computing node800may be a uniprocessor system including one processor810, or a multiprocessor system including several processors810(e.g., two, four, eight, or another suitable number). Processors810may be any suitable processors capable of executing instructions. For example, in various embodiments, processors810may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors810may commonly, but not necessarily, implement the same ISA. Similarly, in a distributed computing system such as one that collectively implements a scalable database service or a remote storage service in which tables are baked up, each of the computing nodes may implement the same ISA, or individual computing nodes and/or replica groups of nodes may implement different ISAs.

The computing node800also includes one or more network communication devices (e.g., network interface840) for communicating with other systems and/or components over a communications network (e.g. Internet, LAN, etc.). For example, a client application executing on computing node800may use network interface840to communicate with a server application executing on a single server or on a cluster of servers that implement a distributed system. In another example, an instance of a server application executing on computing node800may use network interface840to communicate with other instances of the server application that may be implemented on other computer systems.

In the illustrated embodiment, computing node800also includes one or more persistent storage devices860and/or one or more I/O devices880. In various embodiments, persistent storage devices860may correspond to disk drives, tape drives, solid state memory, other mass storage devices, or any other persistent storage device. Computing node800(or a distributed application or operating system operating thereon) may store instructions and/or data in persistent storage devices860, as desired, and may retrieve the stored instruction and/or data as needed.

Computing node800includes one or more system memories820that are configured to store instructions and/or data (shown as program instructions825and data store845, respectively) that are accessible by processor(s)810. In various embodiments, system memories820may be implemented using any suitable memory technology, (e.g., one or more of cache, static random-access memory (SRAM), DRAM, RDRAM, EDO RAM, DDR 10 RAM, synchronous dynamic RAM (SDRAM), Rambus RAM, EEPROM, non-volatile/Flash-type memory, or any other type of memory). System memory820may contain program instructions825that are executable by processor(s)810to implement the methods and techniques described herein for restoration of a data source.

In the illustrated embodiment, program instructions and data implementing desired functions, methods or techniques (such as functionality for restoration of a data source using any or all of the mechanisms described herein), are shown stored within system memory820as program instructions825. For example, program instruction825may include program instructions that when executed on processor(s)810implement any or all of data store120, repair manager110, various data stores and archives, and/or any other components, modules, or sub-modules of a system that provides the data storage system and services described herein. Program instructions825may also include program instructions configured to implement additional functionality of a system that implements a data storage service not described herein. In some embodiments, program instructions825may include program instructions configured to implement functionality of a key-value durable backup storage system or another type of remote storage system suitable for restoration of a data sources, as describe herein. In some embodiments, program instructions825may implement multiple separate clients, server nodes, and/or other components.

It is noted that in some embodiments, program instructions825may include instructions and data implementing desired functions that are not directly executable by processor(s)810but are represented or encoded in an abstract form that is translatable to instructions that are directly executable by processor(s)810. For example, program instructions825may include instructions specified in an ISA that may be emulated by processor810, or by other program instructions825executable on processor(s)810. Alternatively, program instructions825may include instructions, procedures or statements implemented in an abstract programming language that may be compiled or interpreted in the course of execution. As non-limiting examples, program instructions825may be encoded in platform native binary, any interpreted language such as Java™ byte-code, or may include code specified in a procedural or object-oriented programming language such as C or C++, a scripting language such as perl, a markup language such as HTML or XML, or any other suitable language or in any combination of languages.

In other embodiments, program instructions and/or data as described herein for implementing a data storage service that employs the techniques described above may be received, sent or stored upon different types of computer-readable media or on similar media separate from system memory820or computing node800. Program instructions and data stored on or across one or more computer-readable storage medium may be transmitted to a computing node800for execution on a processor810(or across multiple processors) by transmission media or signals such as electrical, electromagnetic, or digital signals, which may be conveyed via a communication medium such as a network and/or a wireless link, such as may be implemented via network interface840. In some embodiments, system memory820may include data in data store845and/or program instructions825and/or special purpose instructions826, which may be configured as described herein. In some embodiments, data store845may store the snapshots, or the change stream items, for example. In some embodiments, special purpose program instructions826may include instructions that implement the repair manager110, the data store120, or the change log stream store130, for example.

In some embodiments, system memory820may include data store845, which may be configured as described herein. For example, the information described herein as being stored by the scalable, distributed data storage system (e.g., table data, metadata for tables, partitions and backups, transaction information, configuration information for tables and/or partitions, or other information used in performing the methods described herein may be stored in data store845or in another portion of system memory820on one or more nodes, in persistent storage860, and/or in remote storage870, in various embodiments. In some embodiments, and at various times, system memory820(e.g., data store845within system memory820), persistent storage860, and/or remote storage870may store copies of table data (e.g., partition data) backup copies of table and/or partition data, metadata associated with tables, partitions, backups, transactions and/or their states, database configuration information, and/or any other information usable in implementing the methods and techniques described herein. In some embodiments, remote storage870may be a key-value durable storage system in which tables (and/or partitions thereof) are backed up and from which they are restored, as described herein.

Data store845may in various embodiments include collections of data maintained by a data storage service on behalf of its clients/users, and/or metadata used by a computing system that implements such a service, as described herein (including, but not limited to, tables managed and maintained on behalf of clients/users of the service, metadata tables, business rules, partition maps, routing tables, indexes, namespaces and/or partitions thereof, service level agreement parameter values, subscriber preferences and/or account information, performance data, resource capacity data, resource usage data, provisioned resource utilization data, reserved resource data, resource reservation IDs, resource reservation timeout period values, parameter values for various partition management policies, limits, or constraints, and/or information about candidate partition management operations).

In one embodiment, I/O interface830may be configured to coordinate I/O traffic between processor(s)810, system memory820and any peripheral devices in the system, including through network interface840or other peripheral interfaces. In some embodiments, I/O interface830may perform any necessary protocol, timing or other data transformations to convert data signals from one component (e.g., system memory820) into a format suitable for use by another component (e.g., processor810). In some embodiments, I/O interface830may include support for devices attached through various types of peripheral buses, such as a variant of the Peripheral Component Interconnect (PCI) bus standard or the Universal Serial Bus (USB) standard, for example. In some embodiments, the function of I/O interface830may be split into two or more separate components, such as a north bridge and a south bridge, for example. Also, in some embodiments, some or all of the functionality of I/O interface830, such as an interface to system memory820, may be incorporated directly into processor810.

Network interface840may be configured to allow data to be exchanged between computing node800and other devices attached to a network, such as other computer systems890(which may implement one or more server nodes and/or clients of a scalable, distributed data storage system and/or a remote key-value durable storage system), for example. In addition, network interface840may be configured to allow communication between computing node800and various I/O devices850and/or remote storage870), or between other nodes in a system providing shared computing services. In general, network interface840may be configured to allow data to be exchanged between computing node800and any of a variety of communication devices, external storage devices, input/output devices and/or other computing devices, in different embodiments.

Input/output devices850may, in some embodiments, include one or more display terminals, keyboards, keypads, touchpads, scanning devices, voice or optical recognition devices, or any other devices suitable for entering or retrieving data by one or more computing nodes800. Multiple input/output devices850may be present in computing node800or may be distributed on various nodes of a distributed system that includes computing node800. In some embodiments, similar input/output devices may be separate from computing node800and may interact with one or more nodes of a distributed system that includes computing node800through a wired or wireless connection, such as over network interface840. Network interface840may commonly support one or more wireless networking protocols (e.g., Wi-Fi/IEEE 802.11, or another wireless networking standard). However, in various embodiments, network interface840may support communication via any suitable wired or wireless general data networks, such as other types of Ethernet networks, for example. Additionally, network interface840may 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. In various embodiments, computing node800may include more, fewer, or different components than those illustrated inFIG. 8(e.g., displays, video cards, audio cards, peripheral devices, other network interfaces such as an ATM interface, an Ethernet interface, a Frame Relay interface, etc.)

Storage service clients (e.g., users, subscribers and/or client applications) may interact with a data storage service such as that described herein in various ways in different embodiments, such as to submit requests for service (including, but not limited to, requests to create and/or partition tables, requests to store, retrieve and/or update items in tables, or requests to split, move, or otherwise repartition a table), and to receive results. For example, some subscribers to the service may have physical access to computing node800, and if so, may interact with various input/output devices850to provide and/or receive information. Alternatively, other clients/users may use client computing systems to access the system, such as remotely via network interface840(e.g., via the Internet and/or the World Wide Web). In addition, some or all of the computing nodes of a system providing the service may provide various feedback or other general types of information to clients/users (e.g., in response to user requests) via one or more input/output devices850.

It is noted that any of the distributed system embodiments described herein, or any of their components, may be implemented as one or more web services. For example, a front-end module or administrative console of a Web services platform may present data storage services and/or database services to clients as web services. In some embodiments, a web service may be implemented by a software and/or hardware system designed to support interoperable machine-to-machine interaction over a network. A web service may have an interface described in a machine-processable format, such as the Web Services Description Language (WSDL). Other systems may interact with the web service in a manner prescribed by the description of the web service's interface. For example, the web service may define various operations that other systems may invoke, and may define a particular application programming interface (API) to which other systems may be expected to conform when requesting the various operations.

In various embodiments, a web service may be requested or invoked through the use of a message that includes parameters and/or data associated with the web services request. Such a message may be formatted according to a particular markup language such as Extensible Markup Language (XML), and/or may be encapsulated using a protocol such as Simple Object Access Protocol (SOAP). To perform a web services request, a web services client may assemble a message including the request and convey the message to an addressable endpoint (e.g., a Uniform Resource Locator (URL)) corresponding to the web service, using an Internet-based application layer transfer protocol such as Hypertext Transfer Protocol (HTTP).

Those skilled in the art will appreciate that computing node800is merely illustrative and is not intended to limit the scope of embodiments. In particular, the computing system and devices may include any combination of hardware or software that can perform the indicated functions, including computers, network devices, internet appliances, PDAs, wireless phones, pagers, etc. Computing node800may also be connected to other devices that are not illustrated, in some embodiments. In addition, the functionality provided by the illustrated components may in some embodiments be combined in fewer components or distributed in additional components. Similarly, in some embodiments the functionality of some of the illustrated components may not be provided and/or other additional functionality may be available.

Note that while several examples described herein are directed to the application of various techniques in systems that include a non-relational database, in other embodiments these techniques may be applied in systems in which the distributed data store is implemented using a different storage paradigm.

The various methods as illustrated in the figures and described herein represent example embodiments of methods. The methods may be implemented manually, in software, in hardware, or in a combination thereof. The order of any method may be changed, and various elements may be added, reordered, combined, omitted, modified, etc.

Those skilled in the art will appreciate that in some embodiments the functionality provided by the methods discussed above may be provided in alternative ways, such as being split among more software modules or routines or consolidated into fewer modules or routines. Similarly, in some embodiments illustrated methods may provide more or less functionality than is described, such as when other illustrated methods instead lack or include such functionality respectively, or when the amount of functionality that is provided is altered. In addition, while various operations may be illustrated as being performed in a particular manner (e.g., in serial or in parallel) and/or in a particular order, those skilled in the art will appreciate that in other embodiments the operations may be performed in other orders and in other manners. Those skilled in the art will also appreciate that the data structures discussed above may be structured in different manners, such as by having a single data structure split into multiple data structures or by having multiple data structures consolidated into a single data structure. Similarly, in some embodiments illustrated data structures may store more or less information than is described, such as when other illustrated data structures instead lack or include such information respectively, or when the amount or types of information that is stored is altered. The various methods as depicted in the figures and described herein represent illustrative embodiments of methods. The methods may be implemented in software, in hardware, or in a combination thereof in various embodiments. Similarly, the order of any method may be changed, and various elements may be added, reordered, combined, omitted, modified, etc., in various embodiments.

From the foregoing it will be appreciated that, although specific embodiments have been described herein for purposes of illustration, various modifications may be made without deviating from the spirit and scope of the appended claims and the elements recited therein. In addition, while certain aspects are presented below in certain claim forms, the inventors contemplate the various aspects in any available claim form. For example, while only some aspects may currently be recited as being embodied in a computer readable storage medium, other aspects may likewise be so embodied.