Efficient building of restore list

• US 10,013,424 B2
• Filed: 04/02/2015
• Issued: 07/03/2018
• Est. Priority Date: 09/30/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Bachu, Kiran, Varma, Venu
• Primary Examiner(s): Le, Miranda
• Application Number:
  US14/677,795
• Publication Number:
  US 20150378834A1
• Time in Patent Office: 1,188 Days
• 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/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: G06F 16/17 Details of further file system functions
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A system for building a restore list for a restore includes a processor and a memory. The processor is configured to determine whether a next sibling record of a directory index record of a root directory includes a subdirectory or a file, wherein the content of the directory index is determined from an incremental backup of the root directory. In the event that the next sibling record comprises a subdirectory of the root directory, the processor is configured to push a directory path associated with the next sibling record onto a directory stack. In the event that the next sibling record comprises a file, the processor is configured to add the latest index record associated with the file to a restore list in the event that the file is not already in the restore list. The restore list is provided for a restore of the state of data of the root directory at a desired time.

Claims

1. A system for building a restore list for a restore, comprising:

a processor configured to;

determine a root directory and a time of a restore;

receive a directory index for the root directory, wherein the content of the directory index is determined from a most recent incremental backup of the root directory at the time of the restore;

add subdirectories in the directory index to a list of directories to traverse; and

add one or more files in the directory index to a restore list in response to the one or more files being not already present on the restore list, comprising;

selecting a file of the one or more files in the directory index;

determining whether the file is already present on the restore list, and in response to the file being not already present on the restore list, adding the file to the restore list, wherein the restore list is ordered by a storage location of each backup file associated with a file in the restore list, and comprises a backup version the file is stored in, an offset within the backup version, and a file size; and

determining whether the file and another file in the restore list are stored adjacently in a same backup version, and in response to the file and the another file being stored adjacently in the same backup version as the file is added to the restore list or after at least a portion of the restore list has been built, determining a coalesced file offset as either a file offset of the file or as another file offset of the another file and a coalesced file size to be the sum of a file size of the file and another file size of the another file; and

removing one of the subdirectories on the list of directories to traverse from the list of directories to traverse after processing;

in response to the list of directories to traverse being empty, indicating that the entire root directory structure for the incremental backup of the root directory has been traversed; and

creating a synthetic full backup of data in the root directory at the time of the restore based at least in part on the restore list; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. A system as in claim 1, wherein the processor is further configured to receive a subdirectory index for one of the subdirectories on the list of directories to traverse, wherein the content of the subdirectory index is determined from a most recent incremental backup.

3. A system as in claim 2, wherein the processor is further configured to add a subdirectory file in the subdirectory index to the restore list in response to the file in the subdirectory index being not already present on the restore list.

4. A system as in claim 2, wherein the one of the subdirectories on the list of directories to traverse is removed from the list of directories to traverse after processing.

5. A system as in claim 4, wherein the processor is further configured to, in response to the list of directories to traverse being empty, indicate that the entire root directory structure for the incremental backup of the root directory has been traversed.

6. A system as in claim 4, wherein the processor is further configured to, in response to the list of directories to traverse being empty, indicate that every file and every file location within the incremental backup of the root directory is included on the restore list.

7. A system as in claim 3, wherein the restore list comprises a backup version the subdirectory file in the subdirectory index is stored in.

8. A system as in claim 3, wherein the restore list comprises a file size of the subdirectory file in the subdirectory index.

9. A system as in claim 7, wherein the restore list comprises an offset within the backup version the subdirectory file in the subdirectory index is stored in.

10. A system as in claim 1, wherein determining whether the file and the another file in the restore list are stored adjacently in the same backup version occurs as the file is added to the restore list.

11. A system as in claim 1, wherein determining whether the file and the another file in the restore list are stored adjacently in the same backup version occurs after the entire restore list has been built.

12. A system as in claim 1, wherein determining whether the file and the another file in the restore list are stored adjacently in the same backup version occurs after at least a portion of the restore list has been built.

13. A system as in claim 1, wherein the restore list is ordered by a storage location of a file within each backup file in the restore list.

14. A system as in claim 1, wherein the restore list is ordered by a storage location of each backup file associated with a file in the restore list.

15. A system as in claim 1, wherein the processor is further configured to provide the restore list for use in restoring data in the root directory at the time of the restore or in creating a synthetic full backup of data in the root directory at the time of the restore.

16. A system as in claim 1, wherein the processor is further configured to recover the state of data of the root directory at the time of the restore based at least in part on the restore list.

17. A system as in claim 1, wherein the processor is further configured to create a synthetic full backup of data in the root directory at the time of the restore based at least in part on the restore list.

18. A method for building a restore list for a restore, comprising:

determining, using a processor, a root directory and a time of a restore;

receiving a directory index for the root directory, wherein the content of the directory index is determined from a most recent incremental backup of the root directory at the time of the restore;

adding subdirectories in the directory index to a list of directories to traverse; and

adding one or more files in the directory index to a restore list in response to the one or more files being not already present on the restore list, comprising;

selecting a file of the one or more files in the directory index;

determining whether the file is already present on the restore list, and in response to the file being not already present on the restore list, adding the file to the restore list, wherein the restore list is ordered by a storage location of each backup file associated with a file in the restore list, and comprises a backup version the file is stored in, an offset within the backup version, and a file size; and

determining whether the file and another file in the restore list are stored adjacently in a same backup version, and in response to the file and the another file being stored adjacently in the same backup version as the file is added to the restore list or after at least a portion of the restore list has been built, determining a coalesced file offset as either a file offset of the file or as another file offset of the another file and a coalesced file size to be the sum of a file size of the file and another file size of the another file; and

removing one of the subdirectories on the list of directories to traverse from the list of directories to traverse after processing;

in response to the list of directories to traverse being empty, indicating that the entire root directory structure for the incremental backup of the root directory has been traversed; and

creating a synthetic full backup of data in the root directory at the time of the restore based at least in part on the restore list.

19. A computer program product for building a restore list for a restore, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

determining, using a processor, a root directory and a time of a restore;

receiving a directory index for the root directory, wherein the content of the directory index is determined from a most recent incremental backup of the root directory at the time of the restore;

adding subdirectories in the directory index to a list of directories to traverse; and

adding one or more files in the directory index to a restore list in response to the one or more files being not already present on the restore list, comprising;

selecting a file of the one or more files in the directory index;

determining whether the file is already present on the restore list, and in response to the file being not already present on the restore list, adding the file to the restore list, wherein the restore list is ordered by a storage location of each backup file associated with a file in the restore list, and comprises a backup version the file is stored in, an offset within the backup version, and a file size; and

determining whether the file and another file in the restore list are stored adjacently in a same backup version, and in response to the file and the another file being stored adjacently in the same backup version as the file is added to the restore list or after at least a portion of the restore list has been built, determining a coalesced file offset as either a file offset of the file or as another file offset of the another file and a coalesced file size to be the sum of a file size of the file and another file size of the another file; and

removing one of the subdirectories on the list of directories to traverse from the list of directories to traverse after processing;

in response to the list of directories to traverse being empty, indicating that the entire root directory structure for the incremental backup of the root directory has been traversed; and

creating a synthetic full backup of data in the root directory at the time of the restore based at least in part on the restore list.