Patent ID: 8832039

Claim:
A method, comprising: restoring, by a restore process implemented on one or more computing devices, a data volume from a snapshot of the data volume, wherein the data volume comprises a plurality of data blocks as local blocks, wherein the snapshot comprises a plurality of data blocks as snapshot blocks, and wherein each snapshot block corresponds to one local block of the data volume; wherein said restoring the data volume from the snapshot comprises: for at least one local block on the data volume, computing fingerprint data for the local block and writing the fingerprint data to at least one location in the respective local block to indicate that the respective local block has not been restored; receiving a request for a local block on the data volume; generating a restore block list that indicates at least one local block on a path of an implicit tree structure of the local blocks on the data volume, wherein the restore block list indicates at least the requested local block; for each local block indicated in the restore block list: for each local block in the tree structure that is a child of the current local block indicated in the restore block list, computing fingerprint data for the child local block and writing the fingerprint data to at least one location in the child local block; retrieving a snapshot block corresponding to the current local block from the snapshot; and writing data from the snapshot block to the current local block in the data volume; and proceeding with the request for the local block on the data volume.