Methods and apparatus for data restore and recovery from a remote data store

• US 9,659,017 B2
• Filed: 08/31/2014
• Issued: 05/23/2017
• Est. Priority Date: 06/30/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lin, Yun, Sorenson, III, James Christopher, Alapati, Nishanth
• Primary Examiner(s): LIAO, JASON G
• Application Number:
  US14/474,158
• Publication Number:
  US 20140372381A1
• Time in Patent Office: 996 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Methods, apparatus, and computer-accessible storage media for restoring data from a snapshot to a data volume. The blocks in the volume may be treated as an implicit tree structure, for example a binary tree; each local block corresponds to a block on the snapshot. A local block on the volume may be marked, for example fingerprinted with metadata, to indicate that the local block has not been restored. Initially, the local block at the root node is marked. To restore a local block, the restore process may generate a list indicating all local blocks on a path from the root node of the tree to the target node that have not been restored. The marks in the local blocks are used in generating the list. For each block indicated in the list, children of the block are fingerprinted, and the block is restored from the snapshot.

Claims

1. A device, comprising:

at least one processor; and

a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to implement a restore process to restore block data to a data volume from a snapshot of the data volume, wherein the snapshot comprises a point-in-time snapshot based on the data volume at a particular point-in-time, and wherein the restore process is configured to;

for at least one local block on the data volume being restored from the snapshot of the data volume, mark the at least one local block, at one or more locations within the at least one local block, to indicate that the at least one local block needs to be restored;

in response to determining that a particular local block on the data volume needs to be restored;

generate a list indicating at least one local block on a path of an implicit tree structure from a root node to the particular local block, the list indicating local blocks on the data volume, wherein the list indicates at least the particular local block; and

for each local block indicated in the list, restore the respective local block in the data volume from the snapshot of the data volume.

2. The device as recited in claim 1, wherein, to restore a local block in the data volume from a snapshot of the data volume, the restore process is further configured to:

fetch a snapshot block corresponding to the local block from the snapshot; and

write data from the snapshot block to the local block in the data volume.

3. The device as recited in claim 1, wherein the restore process is further configured to, for at least one child local block in the tree structure of at least one local block indicated by the list, mark the child local block, within the child local block, to indicate that the child local block needs to be restored.

4. The device as recited in claim 1, wherein, to generate the list indicating one or more local blocks on a path of an implicit tree structure, the restore process is further configured to:

traverse one or more local blocks on the path of the implicit tree structure, wherein the path starts at the root node of the tree structure and extends to the particular local block; and

upon encountering a marked local block on the path being traversed, add an indication of each local block traversed on the path from the marked local block to the particular local block to the list.

5. The device as recited in claim 1, wherein, to determine a local block on the data volume to be restored, the restore process is further configured to receive an indication of a local block on the data volume to be restored.

6. The device as recited in claim 5, wherein the received indication is a read request or a write request for the local block, and wherein the restore process is further configured to allow the read request or the write request to proceed after the respective local block is restored from the snapshot.

7. The device as recited in claim 1, wherein the program instructions are further executable by the at least one processor to implement a storage gateway process that provides an interface between one or more client processes on a local network and a storage service provided by a remote network for accessing client data maintained on a remote data store by the storage service.

8. The device as recited in claim 1, wherein, to mark the local block to indicate that the block needs to be restored, the restore process is further configured to compute fingerprint data for the local block and write the fingerprint data to at least one location of the respective local block.

9. The device as recited in claim 8, wherein, to compute fingerprint data for the local block, the restore process is further configured to compute a cryptographic hash of metadata corresponding to the respective local block.

10. The device as recited in claim 1, wherein, to mark a local block to indicate that the block needs to be restored, the restore process is further configured to write marking data that indicates that the respective local block has not been restored to beginning portion of the respective local block, an end portion of the respective local block, or both.

11. A non-transitory computer-accessible storage medium storing program instructions computer-executable to implement a restore process configured to restore a data volume from a snapshot of the data volume, wherein the snapshot comprises a point-in-time snapshot based on the data volume at a particular point-in-time, and wherein, to implement the restore process, the program instructions cause one or more processors to:

determine mark data for a local block at a root node of an implicit tree structure and write the mark data to at least one location within the respective local block to indicate that the respective local block needs to be restored, wherein each node in the tree structure corresponds to a particular local block on the data volume to be restored;

obtain indications of local blocks on the data volume to be restored;

for each indication of a local block to be restored;

generate a list specifying at least one local block on a path of the implicit tree structure from the root node of the tree structure to the indicated local block, wherein the list includes at least the indicated local block;

for at least one child local block in the tree structure of at least one local block indicated by the list, determine mark data for the child local block and write the mark data to at least one location within the child local block; and

for each local block specified in the list, restore the respective local block in the data volume from the snapshot of the data volume.

12. The non-transitory computer-accessible storage medium as recited in claim 11, wherein each local block corresponds to a snapshot block of the snapshot, wherein the point-in-time snapshot comprises mutated data included in a write log at the particular point-in-time, and wherein, to restore a local block in the data volume from a snapshot of the data volume, the restore process further causes the one or more processors to restore data to the respective local from a corresponding snapshot block.

13. The non-transitory computer-accessible storage medium as recited in claim 11, wherein the tree structure is a binary tree structure, and wherein at least one local block at a position n in the binary tree structure has two child local blocks at positions 2n+1 and 2n+2 in the binary tree structure.

14. The non-transitory computer-accessible storage medium as recited in claim 11, wherein, to generate the list specifying at least one local block, the restore process further causes the one or more processors to:

traverse one or more local blocks on the path of the implicit tree structure, wherein the path starts at a root node of the tree structure and extends to the indicated local block; and

upon encountering a marked local block on the path being traversed, add each local block traversed on the path from the marked local block to the indicated local block to the list.

15. The non-transitory computer-accessible storage medium as recited in claim 11, wherein the indications of local blocks on the data volume to be restored include I/O requests for respective local blocks, and wherein the restore process further causes the one or more processors to allow an I/O request to proceed after the respective local block is restored.

16. The non-transitory computer-accessible storage medium as recited in claim 11, wherein at least some of the indications of local blocks on the data volume to be restored are generated by the restore process restoring the local blocks as indicated by the tree structure starting at the root node and traversing the nodes of the tree structure, wherein traversing each node generates an indication of a corresponding local block.

17. The non-transitory computer-accessible storage medium as recited in claim 11, wherein the program instructions are further executable to implement a storage gateway process that provides an interface between one or more client processes on a local network and a storage service provided by a remote network for accessing client data maintained on a remote data store by the storage service.

18. The non-transitory computer-accessible storage medium as recited in claim 11, wherein, to determine mark data for a local block, the restore process further causes the one or more processors to compute a fingerprint for the local block, wherein the fingerprint is a cryptographic hash of metadata corresponding to the respective local block.

19. The non-transitory computer-accessible storage medium as recited in claim 11, wherein, to write the mark data to at least one location in the respective local block, the restore process further causes the one or more processors to write the mark data at least at the beginning and the end of the respective local block.