STREAMING RESTORE OF A DATABASE FROM A BACKUP SYSTEM

• US 20140149355A1
• Filed: 03/11/2013
• Published: 05/29/2014
• Est. Priority Date: 11/26/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: KULESZA, JAKUB, STEFANI, STEFANO, GUPTA, ANURAG WINDLASS, AGARWAL, DEEPAK, SURNA, ALEKSANDRAS, JAIN, TUSHAR, FONG, ZELAINE
• Granted Patent: US 9,449,038 B2
• Time in Patent Office: Days
• US Class Current: 707/652
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

A distributed data warehouse system may maintain data blocks on behalf of clients in multiple clusters in a data store. Each cluster may include a single leader node and multiple compute nodes, each including multiple disks storing data. The warehouse system may store primary and secondary copies of each data block on different disks or nodes in a cluster. Each node may include a data structure that maintains metadata about each data block stored on the node, including its unique identifier. The warehouse system may back up data blocks in a remote key-value backup storage system with high durability. A streaming restore operation may be used to retrieve data blocks from backup storage using their unique identifiers as keys. The warehouse system may service incoming queries (and may satisfy some queries by retrieving data from backup storage on an as-needed basis) prior to completion of the restore operation.

Claims

1. A method, comprising:

performing, by one or more computers;

storing columnar data of a database table in a plurality of physical data blocks in a distributed data storage system on behalf of one or more clients, wherein the distributed data storage system comprises a cluster of one or more nodes, each of which comprises one or more disks on which physical data blocks are stored, and wherein each of the plurality of physical data blocks is associated with a respective unique identifier;

storing a copy of each of the plurality of physical data blocks in a remote key-value durable backup storage system, wherein for each of the plurality of physical data blocks, the respective unique identifier serves as a key to access the data block in the remote key-value durable backup storage system;

detecting a failure in the distributed data storage system affecting at least one of the plurality of physical data blocks in which the columnar data was stored;

in response to said detecting, automatically initiating a restore of the columnar data that was stored in the at least one of the plurality of physical data blocks from the remote key-value durable backup storage system; and

prior to restoring all of the columnar data that was stored in the at least one of the plurality of physical data blocks;

receiving one or more query requests directed to the columnar data of the database table; and

accepting and servicing the one or more query requests, wherein said servicing comprises obtaining at least some of the columnar data of the database table to which the one or more query requests are directed from the remote key-value durable backup storage system using the respective unique identifiers as keys to access data blocks in the remote key-value durable backup storage system comprising the at least some of the columnar data.

2. The method of claim 1, wherein said storing columnar data of a database table comprises storing a portion of the columnar data as a primary copy of the portion of the columnar data in a respective physical data block on a given disk, and storing the portion of the columnar data as one or more secondary copies of the portion of the columnar data in respective physical data blocks on one or more disks other than the given disk.

3. The method of claim 1, wherein said storing columnar data of a database table comprises storing the unique identifier of each of the physical data blocks stored on disks of a given node in a respective entry in a superblock data structure that stores information about the physical data blocks stored on the given node.

4. The method of claim 1, wherein said storing columnar data of a database table comprises storing information indicating a location at which each of the physical data blocks stored on disks of a given node are stored in a respective entry in a superblock data structure that stores information about the physical data blocks stored on the given node.

5. The method of claim 1, wherein said servicing comprises obtaining at least some of the columnar data of the database table to which the one or more query requests are directed from disks in the distributed data storage system.

6. A method, comprising:

performing, by one or more computers;

maintaining data in one or more physical data blocks of a data storage system on behalf of one or more clients, wherein each physical data block is associated with a unique identifier;

performing a backup operation to store a respective copy of data stored in a given physical data block in a key-value storage system that is distinct from the data storage system;

subsequent to storing the respective copy of the data stored in the given physical data block, restoring the data stored in the given physical data block from the key-value storage system to the data storage system while accepting and servicing queries directed to the data maintained on behalf of the one or more clients, wherein said restoring comprises accessing the respective copy of data in the key-value storage system using the unique identifier associated with the given physical data block as a key in the key-value storage system.

7. The method of claim 6, wherein said restoring is performed as part of an operation to restore data stored in multiple physical data blocks from the key-value storage system to the data storage system, and wherein said accepting and servicing queries is performed prior to restoring all of the data stored in the multiple physical data blocks.

8. The method of claim 6, further comprising receiving data representing entries in a database table, wherein said maintaining data in one or more physical data blocks of a data storage system comprises storing data representing one or more columns of data in the database table in each of the one or more physical data blocks.

9. The method of claim 6, wherein said restoring is performed in response to a failure of a storage device on which the data stored in the given physical data block is stored in the data storage system.

10. The method of claim 6, wherein said restoring is performed in response to a failure of a node comprising a storage device on which the data stored in the given physical data block is stored in the data storage system.

11. The method of claim 6, wherein said restoring is performed in response to a failure of a cluster of one or more nodes comprising a storage device on which the data stored in the given physical data block is stored in the data storage system.

12. The method of claim 6, wherein said restoring is performed in response to an explicit request from one of the one or more clients to perform a restore operation.

13. The method of claim 6,

wherein said maintaining data in one or more physical data blocks of a data storage system comprises maintaining a data structure that stores a mapping between the data maintained on a particular node in a cluster of one or more nodes and a location in the data storage system at which the data is stored in a physical data block on the particular node, wherein the data structure is maintained on the particular node, and wherein each entry in the data structure stores a mapping for a particular physical data block and the unique identifier associated with the particular physical data block;

and

wherein the method comprises, prior to said restoring, restoring the data structure on the particular node in response to a failure of the node or a failure of the cluster of nodes.

14. A non-transitory computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

storing one or more data blocks in a data warehouse system;

creating a respective entry for each of the one or more data blocks in a data structure that stores information about data blocks stored in the data warehouse system, wherein each of the respective entries for the one or more data blocks comprises a unique identifier for the data block and an indication that the data block has not yet been backed up;

performing a backup operation for a plurality of data blocks stored in the data warehouse system, including the one or more data blocks, wherein said performing comprises;

storing a backup copy of the data structure in a remote key-value storage system;

storing, for each data block stored in the data warehouse system for which a corresponding entry in the data structure indicates that it has not yet been backed up, a backup copy of the data block in the remote key-value storage system; and

updating the entries in the data structure corresponding to each data block that was backed up by the backup operation to indicate that the data block has been backed up.

15. The non-transitory computer-readable storage medium of claim 14, wherein said storing one or more data blocks in a data warehouse system comprises storing two or more copies of each of the one or more data blocks on different storage devices in the data warehouse system.

16. The non-transitory computer-readable storage medium of claim 14, wherein said storing one or more data blocks in a data warehouse system comprises generating the unique identifier for each of the one or more data blocks.

17. The non-transitory computer-readable storage medium of claim 14, wherein when executed on one or more computers, the program instructions further cause the one or more computers to perform:

receiving a query directed to data in one of the one or more data blocks; and

in response to receiving the query, accessing the backup copy of the one of the one or more data blocks in the remote key-value storage system using the unique identifier for the one of the one or more blocks as an access key in the remote key-value storage system.

18. A computing system, comprising:

one or more computing nodes, each of which comprises at least one processor and a memory, wherein the one or more computing nodes are configured to collectively implement a database service; and

an interface to a remote key-value storage system;

wherein the database service is configured to maintain data on behalf of one or more subscribers to the database service;

wherein the one or more computing nodes are configured to store the data maintained on behalf of the one or more subscribers in a plurality of physical data blocks on one or more storage devices, wherein each of the plurality of physical data blocks is associated with a unique identifier;

wherein the database service is configured to perform a backup operation for the data maintained on behalf of the one or more subscribers, wherein to perform the backup operation, the database service is configured to send to the remote key-value storage system, via the interface, a copy of each of the plurality of physical data blocks for storage in the remote key-value storage system, and the unique identifiers associated with each of the plurality of physical data blocks to be used as access keys for copies of the plurality of physical data blocks in the remote key-value storage system.

19. The computing system of claim 18,

wherein the one or more computing nodes comprise a leader node that is configured to maintain one or more query maps and a mapping between the data maintained on behalf of the one or more subscribers and the locations at which the data is stored by the database service on the one or more computing nodes.

20. The computing system of claim 18,

wherein subsequent to performing the backup operation, the database service is configured to perform a restore operation;

wherein to perform the restore operation, the database service is configured to retrieve from the remote key-value storage system, via the interface, the copies of each of the plurality of physical data blocks, using the unique identifiers associated with each of the plurality of physical data blocks as access keys for the copies of the plurality of physical data blocks in the remote key-value storage system; and

wherein during performance of the restore operation, the database service is further configured to accept and service query requests directed to the data maintained on behalf of the one or more subscribers.

21. The computing system of claim 20, wherein to service query requests directed to the data maintained on behalf of the one or more subscribers, the database service is configured to retrieve at least some of the data targeted by the query requests from the remote key-value storage system prior to completion of the restore operation.

22. The computing system of claim 18, wherein the remote key-value storage system is configured to apply replication, parity, erasure coding, or another error correction technique to the copies of the plurality of physical data blocks in the remote key-value storage system.