Backup of incremental metadata in block based backup systems

• US 7,873,601 B1
• Filed: 06/29/2006
• Issued: 01/18/2011
• Est. Priority Date: 06/29/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Kushwah, Ajay Pratap Singh
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Vo; Truong V
• Application Number:
  US11/479,317
• Time in Patent Office: 1,664 Days
• Field of Search: 707/654
• US Class Current: 707/654
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

Performing a backup is disclosed. A changed portion of a file system tree is determined based at least in part on a stored state of the file system tree at a time a prior block based backup of the file system tree was performed. Incremental metadata associated with the changed portion is obtained. The obtained incremental metadata is stored where there is at least some metadata associated with an unchanged portion of the file system tree that is not stored when storing the obtained incremental metadata.

Claims

1. A method for performing a backup, comprising:

using a processor to determine a changed portion of a file system tree that has changed since a time a prior block based backup of the file system tree was performed, including by;

obtaining a list of one or more blocks, including any file system metadata blocks and any data blocks, that have changed since the prior block based backup was performed, including by recording one or more changes to blocks on media associated with a device being backed up by monitoring commands passed to a media driver since the time the prior block based backup of the file system tree was performed;

determining which of the blocks in the list were identified during some prior backup as file system metadata blocks used by a file system to track file system objects and file system structure;

obtaining inode numbers for those blocks in the list identified as file system metadata blocks during some prior backup; and

determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree;

obtaining incremental metadata associated with the determined changed portion of the file system tree including by obtaining file system metadata used by the file system to track file system objects and file system structure, wherein there is at least some file system metadata associated with an unchanged portion of the file system tree that is not obtained when obtaining the incremental metadata;

storing the obtained incremental metadata, wherein there is at least some file system metadata associated with the unchanged portion of the file system tree that is not stored when storing the obtained incremental metadata; and

determining whether to store incremental metadata based at least in part on a percentage of the file system tree that has changed, wherein;

it is determined to not to store incremental metadata in the event a relatively large percentage of the file system tree has changed and it is determined to store incremental metadata in the event a relatively small percentage of the file system tree has changed;

in the event it is determined to store incremental metadata, obtaining and storing incremental metadata are performed; and

in the event it is determined not to store incremental metadata, file system metadata for the entire file system tree is obtained and stored.

2. A method as recited in claim 1, wherein the prior block based backup comprises at least one of the following:

a full backup or an incremental backup.

3. A method as recited in claim 1, wherein obtaining incremental metadata includes:

determining locations, on media associated with a device being backed up, of file system metadata blocks that have changed; and

retrieving information from the determined locations on the media.

4. A method as recited in claim 1 further comprising:

retrieving the incremental metadata and some metadata associated with the prior block based backup; and

restoring at least some of the file system tree to the current state using the retrieved incremental metadata and metadata associated with the prior block based backup.

5. A method as recited in claim 1 further comprising storing, at the time of the prior block based backup, block location(s) associated with file system metadata for each node in the file system tree.

6. A method as recited in claim 1, wherein determining whether to store incremental metadata is based at least in part on one or more of the following:

a number of levels of hierarchy in the file system tree, an average number of children per directory in the file system tree, or a number of children in a root directory in the file system tree.

7. A method as recited in claim 1, wherein:

in the event the list includes inode numbers, obtaining inode numbers includes obtaining inode numbers from the list; and

in the event the list does not include inode numbers, obtaining inode numbers includes mapping, for each of those blocks in the list determined to be file system metadata blocks, block locations to inode numbers.

8. A method as recited in claim 1, wherein determining which of the blocks in the list are file system metadata blocks includes comparing the list to a list of file system metadata block locations that existed at the time a last full backup was performed.

9. A method as recited in claim 1, wherein determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree that has changed since the time the prior block based backup of the file system tree was performed includes:

determining whether one of the inode numbers corresponds to a directory; and

in the event it is determined that that inode number corresponds to a directory, obtaining incremental metadata includes obtaining file system metadata for that directory and at least that directory'"'"'s immediate children.

10. A system for performing a backup, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

determining a changed portion of a file system tree that has changed since a time a prior block based backup of the file system tree was performed, including by;

obtaining a list of one or more blocks, including any file system metadata blocks and any data blocks, that have changed since the prior block based backup was performed, including by recording one or more changes to blocks on media associated with a device being backed up by monitoring commands passed to a media driver since the time the prior block based backup of the file system tree was performed;

determining which of the blocks in the list were identified during some prior backup as file system metadata blocks used by a file system to track file system objects and file system structure;

obtaining inode numbers for those blocks in the list identified as file system metadata blocks during some prior backup; and

determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree;

obtaining incremental metadata associated with the changed portion of the file system tree including by obtaining file system metadata used by the file system to track file system objects and file system structure, wherein there is at least some file system metadata associated with an unchanged portion of the file system tree that is not obtained when obtaining the incremental metadata;

storing the obtained incremental metadata, wherein there is at least some file system metadata associated with the unchanged portion of the file system tree that is not stored when storing the obtained incremental metadata; and

determining whether to store incremental metadata based at least in part on a percentage of the file system tree that has changed, wherein;

it is determined to not to store incremental metadata in the event a relatively large percentage of the file system tree has changed and it is determined to store incremental metadata in the event a relatively small percentage of the file system tree has changed;

in the event it is determined to store incremental metadata, obtaining and storing incremental metadata are performed; and

in the event it is determined not to store incremental metadata, file system metadata for the entire file system tree is obtained and stored.

11. A system as recited in claim 10, wherein the memory is configured to provide the processor with further instructions for:

retrieving the incremental metadata and some metadata associated with the prior block based backup; and

restoring at least some of the file system tree to the current state using the retrieved incremental metadata and metadata associated with the prior block based backup.

12. A system as recited in claim 10, wherein the memory is configured to provide the processor with further instructions for storing, at the time of the prior block based backup, block location(s) associated with file system metadata for each node in the file system tree.

13. A system as recited in claim 10, wherein determining whether to store incremental metadata is based at least in part on one or more of the following:

a number of levels of hierarchy in the file system tree, an average number of children per directory in the file system tree, or a number of children in a root directory in the file system tree.

14. A system as recited in claim 10, wherein:

in the event the list includes inode numbers, obtaining inode numbers includes obtaining inode numbers from the list; and

in the event the list does not include inode numbers, obtaining inode numbers includes mapping, for each of those blocks in the list determined to be file system metadata blocks, block locations to inode numbers.

15. A system as recited in claim 14, wherein determining which of the blocks in the list are file system metadata blocks includes comparing the list to a list of file system metadata block locations that existed at the time a last full backup was performed.

16. A system as recited in claim 10, wherein determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree that has changed since the time the prior block based backup of the file system tree was performed includes:

determining whether one of the inode numbers corresponds to a directory; and

in the event it is determined that that inode number corresponds to a directory, obtaining incremental metadata includes obtaining file system metadata for that directory and at least that directory'"'"'s immediate children.

17. A non-transitory computer readable storage medium for performing a backup, the non-transitory computer readable storage medium comprising computer instructions for:

determining a changed portion of a file system tree that has changed since a time a prior block based backup of the file system tree was performed, including by;

obtaining a list of one or more blocks, including any file system metadata blocks and any data blocks, that have changed since the prior block based backup was performed, including by recording one or more changes to blocks on media associated with a device being backed up by monitoring commands passed to a media driver since the time the prior block based backup of the file system tree was performed;

determining which of the blocks in the list were identified during some prior backup as file system metadata blocks used by a file system to track file system objects and file system structure;

obtaining inode numbers for those blocks in the list identified as file system metadata blocks during some prior backup; and

determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree;

obtaining incremental metadata associated with the determined changed portion of the file system tree including by obtaining file system metadata used by the file system to track file system objects and file system structure, wherein there is at least some file system metadata associated with an unchanged portion of the file system tree that is not obtained when obtaining the incremental metadata;

storing the obtained incremental metadata, wherein there is at least some file system metadata associated with the unchanged portion of the file system tree that is not stored when storing the obtained incremental metadata; and

determining whether to store incremental metadata based at least in part on a percentage of the file system tree that has changed, wherein;

it is determined to not to store incremental metadata in the event a relatively large percentage of the file system tree has changed and it is determined to store incremental metadata in the event a relatively small percentage of the file system tree has changed;

in the event it is determined to store incremental metadata, obtaining and storing incremental metadata are performed; and

in the event it is determined not to store incremental metadata, file system metadata for the entire file system tree is obtained and stored.

18. A computer readable storage medium as recited in claim 17 further comprising computer instructions for:

retrieving the incremental metadata and some metadata associated with the prior block based backup; and

restoring at least some of the file system tree to the current state using the retrieved incremental metadata and metadata associated with the prior block based backup.

19. A computer readable storage medium as recited in claim 17 further comprising computer instructions for storing, at the time of the prior block based backup, block location(s) associated with file system metadata for each node in the file system tree.

20. A non-transitory computer readable storage medium as recited in claim 17, wherein determining whether to store incremental metadata is based at least in part on one or more of the following:

a number of levels of hierarchy in the file system tree, an average number of children per directory in the file system tree, or a number of children in a root directory in the file system tree.

21. A non-transitory computer readable storage medium as recited in claim 17, wherein:

in the event the list includes inode numbers, obtaining inode numbers includes obtaining inode numbers from the list; and

in the event the list does not include inode numbers, obtaining inode numbers includes mapping, for each of those blocks in the list determined to be file system metadata blocks, block locations to inode numbers.

22. A non-transitory computer readable storage medium as recited in claim 21, wherein determining which of the blocks in the list are file system metadata blocks includes comparing the list to a list of file system metadata block locations that existed at the time a last full backup was performed.

23. A non-transitory computer readable storage medium as recited in claim 17, wherein determining, based at least in part on the obtained inode numbers, the changed portion of the file system tree that has changed since the time the prior block based backup of the file system tree was performed includes:

determining whether one of the inode numbers corresponds to a directory; and

in the event it is determined that that inode number corresponds to a directory, obtaining incremental metadata includes obtaining file system metadata for that directory and at least that directory'"'"'s immediate children.