Rapid incremental backup of changed files in a file system

• US 9,430,331 B1
• Filed: 07/16/2012
• Issued: 08/30/2016
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Basov, Ivan, Bono, Jean-Pierre, Clark, Morgan, Stacey, Christopher H.
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): HARMON, COURTNEY N
• Application Number:
  US13/550,481
• Time in Patent Office: 1,506 Days
• Field of Search: 707/646
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1466 to make the backup process non-disruptive
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

Directory attributes are provided so that the time for creating an incremental backup of a file system by a scan of the file system tree is proportional generally to the number of files that change between backups instead of the number of files in the file system. A tree modification attribute indicates whether or not any file in a directory tree has changed since the last backup. If no file has changed in the directory tree, then the entire tree is skipped during the scan for changed files. In addition, a list is compiled of the files in the directory that represent branches having at least one changed file, so that the list is scanned instead of the directory entries. When a file is changed for the first time since the last backup, the file is queued so that the directory attributes are updated in a background process.

Claims

1. A method for use in rapid incremental backup of changed files in a file system, the method comprising:

scanning a file system hierarchy of a file system in a top-down manner for determining a list of changed files for performing incremental backup of the file system;

evaluating a directory tree modification attribute of each directory hierarchy of the file system hierarchy of the file system in the top-down manner, wherein the file system hierarchy includes a set of directory hierarchies, each directory hierarchy including a set of directories, each directory of the set of directories including a set of files, wherein the directory tree modification attribute of each directory hierarchy indicates whether at least one file in respective entire directory hierarchy has changed since a last backup, wherein the directory tree modification attribute is updated upon finding at least one changed file in the respective directory hierarchy since the last backup and without changing a modification time of a directory associated with the respective directory tree hierarchy;

based on the evaluation, determining whether a directory hierarchy of the file system hierarchy has been changed since the last backup; and

based on the determination, skip traversing files included in a directory hierarchy during the scanning of the file system hierarchy upon determining that the directory tree modification attribute associated with the directory hierarchy has not been updated since the last backup.

2. The method as claimed in claim 1, further comprising:

determining that a file of a directory is being changed by a file system access operation for a first time since the last backup, and upon determining that the file is being changed by the file system access operation for the first time since the last backup, placing the file in a queue, and servicing the queue in background to update a directory tree modification attribute of the directory.

3. The method as claimed in claim 1, wherein the directory tree modification attribute of a directory hierarchy indicates a modification time of the directory hierarchy.

4. The method as claimed in claim 3, wherein evaluating the directory tree modification attribute of a directory hierarchy includes comparing the modification time of the directory hierarchy to a time of the last backup to determine whether or not any file in the directory hierarchy has been changed since the last backup.

5. The method as claimed in claim 3, wherein the method further includes a data processor executing a computer instructions to update the modification time of each of the directory hierarchies in response to changes in files in said each of the directory hierarchies so that the modification time of said each of the directory hierarchy indicates a most recent time that any file in said each of the directory hierarchy has been changed.

6. The method as claimed in claim 1, wherein a directory is associated with a directory inode, wherein the directory inode of the directory includes a tree modification time and a pointer to a list of changed files in the directory.

7. The method as claimed in claim 1, further comprising performing an operation in background for copying the list of changed files to a backup storage.

8. A method for use in rapid incremental backup of changed files in a file system, the method comprising:

scanning a file system hierarchy of a file system in a top-down manner for determining a list of changed files for performing incremental backup of the file system;

evaluating a directory tree modification attribute of each directory hierarchy of the file system hierarchy of the file system in the top-down manner, wherein the file system hierarchy includes a set of directory hierarchies, each directory hierarchy including a set of directories, each directory of the set of directories including a set of files, wherein the directory tree modification attribute of each directory hierarchy indicates whether at least one file in respective entire directory hierarchy has changed since a last backup, wherein the directory tree modification attribute is updated upon finding at least one changed file in the respective directory hierarchy since the last backup and without changing a modification time of a directory associated with the respective directory tree hierarchy;

based on the evaluation, determining that a file of a directory hierarchy is being changed by a file system access operation for a first time since the last backup, and upon determining that the file is being changed by the file system access operation for the first time since the last backup, placing the file in a queue, and servicing the queue in background to update a directory tree modification attribute of the directory hierarchy;

based on the determination, determining whether the directory hierarchy has been changed since the last backup; and

based on the determination, determining whether to skip traversing the directory hierarchy during the scanning of the file system hierarchy for determining the list of changed files for performing incremental backup of the file system upon determining that the directory hierarchy has not been changed since the last backup.

9. A system for use in rapid incremental backup of changed files in a file system, the system comprising:

a processor;

first logic, for execution by the processor, to scanning a file system hierarchy of a file system in a top-down manner for determining a list of changed files for performing incremental backup of the file system;

second logic, for execution by the processor, to evaluate a directory tree modification attribute of each directory hierarchy of the file system hierarchy of the file system in the top-down manner, wherein the file system hierarchy includes a set of directory hierarchies, each directory hierarchy including a set of directories, each directory of the set of directories including a set of files, wherein the directory tree modification attribute of each directory hierarchy indicates whether at least one file in respective entire directory hierarchy has changed since a last backup, wherein the directory tree modification attribute is updated upon finding at least one changed file in the respective directory hierarchy since the last backup and without changing a modification time of a directory associated with the respective directory tree hierarchy;

third logic, for execution by the processor, to determine, based on the evaluation, whether a directory hierarchy of the file system hierarchy has been changed since the last backup; and

fourth logic, for execution by the processor, to skip traversing, based on the determination, files included in a directory hierarchy during the scanning of the file system hierarchy upon determining that the directory tree modification attribute associated with the directory hierarchy has not been updated since the last backup.

10. The system of claim 9, further comprising:

fifth logic, for execution by the processor, to determine that a file of a directory is being changed by a file system access operation for a first time since the last backup, and upon determining that the file is being changed by the file system access operation for the first time since the last backup, placing the file in a queue, and servicing the queue in background to update a directory tree modification attribute of the directory.

11. The system of claim 9, wherein the directory tree modification attribute of a directory hierarchy indicates a modification time of the directory hierarchy.

12. The system of claim 11, wherein evaluating the directory tree modification attribute of a directory hierarchy includes comparing the modification time of the directory hierarchy to a time of the last backup to determine whether or not any file in the directory hierarchy has been changed since the last backup.

13. The system of claim 11, wherein the processor includes a data processor executing a computer instructions to update the modification time of each of the directory hierarchies in response to changes in files in said each of the directory hierarchies so that the modification time of said each of the directory hierarchy indicates a most recent time that any file in said each of the directory hierarchy has been changed.

14. The system of claim 11, wherein a directory is associated with a directory inode, wherein the directory inode of the directory includes a tree modification time and a pointer to a list of changed files in the directory.

15. The system of claim 9, further comprising fifth logic, for execution by the processor, to perform an operation in background for copying the list of changed files to a backup storage.