Systems and methods for restoring a file

• US 9,104,621 B1
• Filed: 11/05/2014
• Issued: 08/11/2015
• Est. Priority Date: 09/30/2010
• Status: Active Grant

• Current Assignee: eFolder, Inc.
• Original Assignee: Axcient
• Inventors: Caputo, Vito
• Primary Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US14/534,017
• Time in Patent Office: 279 Days
• Field of Search: 707/684, 707/685
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• 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 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

Systems and methods for restoring files and metadata records associated with files are provided herein. Some of the methods include identifying a version of the file, evaluating one or more reverse incremental delta increments, and restoring an arbitrary version of the file based on an arbitrary time reference by assembling the arbitrary version of the file based on the one or more reverse incremental delta increments.

Claims

1. A method for restoring a file, the method comprising:

receiving a time reference;

locating a nearest mirror that is previous to the time reference, the nearest mirror including all blocks of data corresponding to the file at a time previous to the time reference;

locating all intervening delta increments between the time reference and the nearest mirror, the intervening delta increments including both inherited blocks of data and literal blocks of data, the inherited blocks of data including;

data that has not changed relative to a temporally previous delta increment, or

data that has not changed since the creation of the nearest mirror when the delta increment is temporally adjacent to the nearest mirror,

the literal blocks of data indicative of;

data that has changed since the creation of a temporally adjacent delta increment, or

data that has changed since the creation of the nearest mirror when the delta increment is temporally adjacent to the nearest mirror;

opening the located intervening delta increments such that all intervening delta increments are open at the same time;

determining offsets and lengths for both the inherited blocks and the literal blocks in each of the opened intervening delta increments, while all intervening delta increments are open;

analyzing each of the intervening delta increments in reverse chronological order beginning with the intervening delta increment temporally adjacent to the time reference, while all intervening delta increments are open;

inheriting the inherited blocks in reverse chronological order based on the analysis of each of the delta increments in turn, until encountering a literal block in either an intervening delta increment or the nearest mirror, while all intervening delta increments are open; and

copying the encountered literal block into a restored file.

2. The method of claim 1, wherein the inherited blocks of data include only metadata indicative of an offset and length of data to be copied from the nearest mirror or a previous delta increment.

3. The method of claim 1, further comprising:

generating sparse run-time indices of the opened intervening delta increments at run-time based on the analysis of each of the delta increments; and

storing the generated sparse run-time indices in memory.

4. The method of claim 3, wherein the generated sparse run-time indices are stored in non-volatile memory.

5. The method of claim 3, wherein parsing further comprises deferring inheritance of a particular node if the next node in a preceding differential metadata record occurs before the node that is currently being iterated.

6. The method of claim 3, further comprising generating the restored file from blocks assembled according to the run-time indices.

7. The method of claim 1, further comprising arranging the opened intervening delta increments in an array of incremental file handles prior to determining the offsets and the lengths of the inherited blocks.

8. The method of claim 7, further comprising ordering the file handles in reverse chronological order.

9. A system for restoring a file at an arbitrary time reference preceding a data loss event, the system comprising:

a file locator module configured for identifying;

a mirror that is a complete backup of the file at a time before the arbitrary time reference,

a plurality of reverse incremental delta increments indicative of changes to the mirror subsequent to the mirror and preceding the arbitrary time reference, the reverse incremental delta increments including;

literal blocks each comprising an indication of data that has changed since creation of a preceding temporally adjacent reverse incremental delta increment, and

inherited blocks each comprising metadata indicating an offset and a length of a block of data that has not been modified relative to the mirror, and

a prime delta increment being a reverse incremental delta increment of the plurality of reverse incremental delta increments that is temporally adjacent to the arbitrary time reference;

a parsing module configured for;

opening the mirror,

opening the plurality of the reverse incremental delta increments such that they are all open at the same time as the mirror,

evaluating the open reverse incremental delta increments and the mirror in reverse chronological order for blocks of data comprising the literal blocks and the inherited blocks, and

determining offsets and lengths of each of the inherited and the literal blocks; and

a restoration module for;

receiving the parsed data from the parsing module,

assembling a single representative reverse incremental delta increment that represents the plurality of open reverse incremental delta increments,

deleting the plurality of reverse incremental delta increments represented by the single representative reverse incremental delta increment, and

restoring the file from the mirror and the single representative reverse incremental delta increment.

10. The system of claim 9, wherein assembling the single representative reverse incremental delta increment comprises:

inheriting each of the inherited blocks in reverse chronological order backwards in time towards the mirror; and

combining the literal blocks of data with the inherited blocks of data.

11. The system of claim 9, wherein the restoration module is further configured for:

processing unresolved blocks of data; and

assembling the single representative reverse incremental delta increment using the processed unresolved blocks of data.

12. The system of claim 9, wherein the parsing module is further configured for:

generating sparse run-time indices of the plurality of the reverse incremental delta increments; and

storing the sparse run-time indices.

13. The system of claim 12, wherein the restoration module is further configured for:

assembling the literal and the inherited blocks according to the sparse run-time indices; and

generating a restored file from the assembled blocks.

14. The system of claim 9, wherein the parsing module is further configured for:

using the determined offsets and lengths of the literal and the inherited blocks to generate sparse run-time indices that are indicative of the open reverse incremental delta increments; and

storing the sparse run-time indices in non-volatile memory.

15. The system of claim 9, wherein the parsing module is further configured for:

generating sparse run-time indices of the plurality of the reverse incremental delta increments at run-time; and

storing the sparse run-time indices in non-volatile memory.

16. A method for generating a restored file at an arbitrary time reference, the method comprising:

locating all intervening incremental delta increments between the arbitrary time reference and a mirror of the file to be restored, the mirror including all blocks of data corresponding to the file to be restored, the intervening incremental delta increments including both inherited blocks of data and literal blocks of data;

after locating all intervening incremental delta increments, opening the located intervening incremental delta increments and the mirror such that all intervening incremental delta increments are open at the same time as the mirror;

after opening all the located intervening incremental delta increments and the mirror, analyzing each of the intervening incremental delta increments and the mirror in turn in reverse chronological order while the mirror and all intervening incremental delta increments are open;

after analyzing the intervening incremental delta increments and the mirror, identifying locations of the inherited and the literal blocks of data in the open intervening incremental delta increments and the mirror that are to be copied into the restored file based on the analysis; and

after identifying all the locations of the inherited and the literal blocks of data, copying the identified inherited and the identified literal blocks of data from the identified locations into the restored file.

17. The method of claim 16, further comprising:

generating sparse run-time indices of the opened intervening incremental delta increments at run-time based on the analysis of each of the intervening incremental delta increments; and

storing the generated sparse run-time indices in non-volatile memory.

18. The method of claim 16, wherein analyzing each of the intervening incremental delta increments in turn in reverse chronological order includes beginning with the intervening incremental delta increment temporally adjacent to the time reference and ending with the mirror.

19. The method of claim 16, wherein the identified locations of the blocks of data include offsets and lengths.

20. The method of claim 16, wherein:

the inherited blocks of data include;

data that has not changed relative to a temporally previous delta increment, or

data that has not changed since the creation of the mirror when the delta increment is temporally adjacent to the mirror; and

the literal blocks of data are indicative of;

data that has changed since the creation of a temporally adjacent delta increment, or

data that has changed since the creation of the mirror when the delta increment is temporally adjacent to the mirror.