Merging of incremental data streams with prior backed-up data

• US 7,797,279 B1
• Filed: 12/31/2007
• Issued: 09/14/2010
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Smolenski, Michael, Starling, Jennifer, Ogata, Scott
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US11/968,061
• Time in Patent Office: 988 Days
• Field of Search: 707/200, 707/204, 707/641, 711/162
• US Class Current: 707/641
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

New full backups are generated by combining an incremental backup with a previous full backup. A previous full backup is stored in a backup server in a hash file system format. A file server generates an incremental backup of a data set on the file server by identifying and dumping files/directories of the data set that are new/modified into a tar file that is sent to an accelerator. The accelerator parses the incremental backup tar file and converts it to a hash file system format that includes metadata, hash values, and new/modified data atomics. The accelerator merges the incremental backup into the previous full backup to generate a new full backup by altering metadata and hash values of a copy of the previous full backup such that the resulting metadata and hash values describe and point to new/modified directories and files as well as unmodified directories and files.

Claims

1. A method of generating new full backups from an incremental backup and a previous full backup, the method comprising:

receiving an incremental backup in a sequential access format stream from a file server;

parsing the sequential access format stream into one or more directories and files that are modified or new as of a dump date of a previous full backup of the file server, wherein the incremental backup is stored in randomly accessible storage;

generating incremental backup metadata describing the organization of the one or more directories and files of the incremental backup;

receiving metadata for the previous full backup from a backup server, the previous full backup metadata describing the organization of one or more directories and files on the file server as of the dump date; and

merging the incremental backup metadata into the previous full backup metadata to generate metadata for a new full backup, the new full backup metadata describing the organization of all directories and files on the file server, including the one or more directories and files that are modified or new as of the dump date of the previous full backup, as of a dump date of the incremental backup.

2. The method of claim 1, further comprising, storing data from the incremental backup on the backup server as one or more data atomics, wherein data for the previous full backup is also stored on the backup server as one or more data atomics.

3. The method of claim 2, wherein the metadata for the new full backup includes pointers that point to all of the one or more data atomics of the incremental backup and one or more data atomics of the previous full backup.

4. The method of claim 3, wherein merging the incremental backup metadata into the previous full backup metadata comprises:

for a new directory or file, adding metadata corresponding to the new directory or file to the previous full backup metadata, the new metadata pointing to one or more corresponding new data atomics; and

for a modified directory or file, updating metadata corresponding to the modified directory or file to point to one or more corresponding modified data atomics.

5. The method of claim 1, wherein the sequential access format comprises one or more of tar format, emctar format, pax format, and px format.

6. The method of claim 1, further comprising, receiving a history stream from the file server, the history stream containing a list of all files and directories on the file server as of a dump date of the incremental backup.

7. The method of claim 6, further comprising, merging the history stream into the new full backup metadata, wherein merging the history stream into the new full backup metadata comprises:

comparing the list of all files and directories in the history stream to files and directories in the new full backup metadata; and

if a file or directory is identified in the new full backup metadata but is not included in the list of all files and directories in the history stream, deleting the metadata for the file or directory from the new full backup metadata.

8. The method of claim 1, further comprising, storing the new full backup metadata in the backup server, wherein the backup server additionally stores the previous full backup metadata and metadata for one or more additional previous full backups, each having a different dump date.

9. The method of claim 8, wherein metadata for one of the one or more additional previous full backups is generated from a full backup in a sequential access format stream received from the file server and wherein metadata for the previous full backup and all but the one of the one or more additional previous full backups are generated in the same manner as the new full backup by merging metadata of an incremental backup into metadata of a previous full backup.

10. The method of claim 8, further comprising, restoring data to the file server to a particular point in time in one operation using any one of the new full backup, the previous full backup, or a single one of the one or more additional previous full backups.

11. A method of generating subsequent full backups using previous full backups and incremental backups, the method comprising:

receiving, from a file server, an incremental backup of a data set on the file server in a sequential access format, the incremental backup including one or more directories and files that are new or modified as of a dump date of a previous full backup of the data set;

parsing the incremental backup into the one or more directories and files that are new or modified;

converting the parsed incremental backup into a hash file system format that includes metadata describing the organization of the one or more directories and files that are new or modified, a plurality of data atomics making up one or more new or modified directories and files, and hash values for use as pointers to the plurality of data atomics; and

merging the incremental backup in the hash file system format into the previous full backup in the hash file system format to generate a new full backup in the hash file system format.

12. The method of claim 11, further comprising, receiving a history stream from the file server, the history stream containing a list of all files and directories in the data set on the file server as of a dump date of the incremental backup.

13. The method of claim 12, further comprising, merging the history stream into the new full backup in the hash file system format.

14. The method of claim 13, wherein merging the history stream into the new full backup in the hash file system format comprises:

comparing the list of all files and directories in the history stream to files and directories described and pointed to in the new full backup; and

if a file or directory is described or pointed to in the new full backup but is not included in the history stream, deleting from the new full backup any metadata, hash values, or both that describe or point to the file or directory not included in the history stream.

15. The method of claim 11, further comprising, prior to receiving the incremental backup in the sequential access format:

receiving, from the file server, the previous full backup of the data set in the sequential access format;

parsing the previous full backup into one or more directories and files making up the data set;

converting the parsed previous full backup to the hash file system format that includes metadata describing the organization of the one or more directories and files, a plurality of data atomics into which the data set is separated, and hash values for use as pointers to the plurality of data atomics; and

storing the previous full backup in the hash file system format in a backup server.

16. The method of claim 15, wherein merging the incremental backup in the hash file system format into the previous full backup in the hash file system format comprises:

receiving, from the backup server, a copy of the metadata and hash values of the previous full backup; and

performing one or more of the following;

for a modified directory made up of one or more modified files, data atomics, or both, changing the copy of the metadata and hash values describing and pointing to one or more corresponding unmodified files, data atomics, or both, of the corresponding unmodified directory in the previous full backup to describe and point to the one or more modified files, data atomics, or both;

for a new directory made up of one or more new files, data atomics, or both, adding metadata and hash values describing and pointing to the one or more new files, data atomics, or both, to the copy of the metadata and hash values of the previous full backup;

for a modified file made up of one or more modified data atomics, changing the copy of the metadata and hash values describing and pointing to one or more corresponding unmodified data atomics of the corresponding unmodified file in the previous full backup to describe and point to the one or more modified data atomics; and

for a new file made up of one or more new data atomics, adding metadata and hash values describing and pointing to the one or more new data atomics to the metadata and hash values of the previous full backup.

17. The method of claim 11, wherein the method is performed by one or more of a backup server and an accelerator node.

18. The method of claim 11, wherein the new full backup has a dump date corresponding to a dump date of the incremental backup, the method further comprising:

receiving a subsequent incremental backup of the data set on the file server, the incremental backup including one or more directories and files that are new or modified as of the dump date of the new full backup;

parsing the subsequent incremental backup into the one or more directories and files that are new or modified as of the dump date of the new full backup;

converting the parsed subsequent incremental backup into the hash file system format; and

merging the subsequent incremental backup in the hash file system format into the new full backup in the hash file system format to generate a subsequent new full backup in the hash file system format.

19. The method of claim 18, further comprising, restoring all or a portion of the data set to a particular point in time in one operation using any one of the previous full backup, the new full backup, or the subsequent new full backup.

20. The method of claim 11, wherein:

the hash file system format includes composites for reconstructing a file or directory from one or more underlying data atomics, composites, or both; and

merging the incremental backup in the hash file system format into the previous full backup in the hash file system format to generate a new full backup in the hash file system format comprises;

receiving a copy of the previous full backup; and

adding composites for new files or directories to the copy of the previous full backup, or replacing composites in the copy of the previous full backup for corresponding unmodified files or directories with composites for the modified files or directories.