US 2019/0095286 A1Published application

Method of Detecting Source Change for File Level Incremental Backup

AssigneeArcserve (USA) LLC

InventorsZhenqiu Fang, Lei Li, Zhonghua Dang, Guangju Li

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method are presented that identify new, modified, unchanged, and deleted files in an incremental backup through a file list maintained on the backup destination. The FileList is a flat file in which file information about each file on a source node is stored sequentially into the file. During a subsequent incremental backup, the FileList is read sequentially from the backup destination and is used to generate a search tree. A hash value based on the file path is the key to the search tree, with the file's modified time and size being hashed together to form the value of the tree's key-value pair. Files are examined on the source and compared to the key-value pairs in the search tree. Status information in the search tree is modified to indicate discovered files. Unmodified status information identifies files that have been deleted since the previous backup.

Claims20

Dependent claims

A method for backing up a source node to a backup destination comprising:

a) performing a full backup of the source node by:
i) creating an empty file list,
ii) identifying a first set of source files available to be backed up on the source node at a first time, and
iii) for each file in the first set of source files:
(1) appending an information entry to the file list containing full path information and content information for the file, and
(2) backing up the file to the backup destination;
b) after the full backup is performed, performing an incremental backup of the source node by:
i) reading the file list, and for each information entry in the file list:
(1) generating a key-value pair, with the key being determined by hashing the full-path information in the information entry, and the value being based on the content information for the information entry, and
(2) adding the key-value pair to a self-balancing binary search tree according to the key, wherein the resulting search tree contains key-value pairs for all information entries in the file list,
ii) identifying a second set of source files available to be backed up on the source node at a second time, each source file in the second set of source files having a source path and source content information,
iii) for each source file in the second set of source files, searching the search tree to find a matching key-value pair, using as search input the result of hashing the source path of the source file, and then comparing the source content information to the value in the matching key-value pair,
iv) for source files where the searching step did not find a matching key-value pair, identifying the source file as a new file and then backing up the new file to the backup destination;
v) for source files where the searching step found the matching key-value pair and further wherein the value of the matching key-value pair did not match the source file content information, identifying the source file as a changed file and then backing up the changed-file to the backup destination, and
vi) for source files where the searching step found the matching key-value pair and further wherein the value of the matching key-value pair matched the source file content information, identifying the source file as unchanged and not backup up the unchanged file.

12 more elements

A method for performing incremental backups of computer files comprising:

a) reading a file list containing a plurality of information entries, with each information entry containing data relating to a file backed up during a prior backup session, each information entry comprising full-path information and file content information;
b) for each information entry in the file list:
i) generating a key-value pair, with the key being determined by hashing the full-path information, and the value being based on the content information for the information entry, and
ii) adding the key-value pair to a search tree according to the key, wherein the resulting search tree contains key-value pairs for all information entries in the file list;
c) examining a source node to identify a plurality of source files, with each source file having a source path and source content information;
d) for each of the plurality of identified source files, searching the search tree to find a matching key-value pair, using as search input the result of hashing the source path of the source file, and then comparing the source content information to the value in the matching key-value pair;
e) for source files where the searching step did not find a matching key-value pair, identifying the source file as a new file and then backing up the new file to the backup destination;
and
f) for source files where the searching step found the matching key-value pair and further wherein the value of the matching key-value pair did not match the source file content information, identifying the source file as a changed file and then backing up the changed-file to the backup destination.

6 more elements

A backup server comprising:

a) a processor;
b) random access memory;
c) a network interface to communicate over a network with a source node;
and
d) backup software programming comprising instructions causing the processor to perform:
i) a full backup of the source node by:
(1) creating an empty file list,
(2) identifying a first set of source files available to be backed up on the source node at a first time, and
(3) for each file in the first set of source files, appending an information entry to the file list containing full path information and content information for the file and then backing up the file to a backup destination, and
ii) an incremental backup of the source node by:
(1) reading the file list, and for each information entry in the file list:
(i) generating a key-value pair, with the key being determined by hashing the full-path information in the information entry, and the value being based on the content information for the information entry, and (ii) adding the key-value pair to a self-balancing binary search tree according to the key, wherein the resulting search tree contains key-value pairs for all information entries in the file list,
(2) identifying a second set of source files available to be backed up on the source node at a second time, each source file in the second set of source files having a source path and source content information,
(3) for each source file in the second set of source files, searching the search tree to find a matching key-value pair, using as search input the result of hashing the source path of the source file, and then comparing the source content information to the value in the matching key-value pair,
(4) for source files where the searching step did not find a matching key-value pair, identifying the source file as a new file and then backing up the new file to the backup destination;
(5) for source files where the searching step found the matching key-value pair and further wherein the value of the matching key-value pair did not match the source file content information, identifying the source file as a changed file and then backing up the changed-file to the backup destination, and
(6) for source files where the searching step found the matching key-value pair and further wherein the value of the matching key-value pair matched the source file content information, identifying the source file as unchanged and not backup up the unchanged file.

14 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/714,366Filed 25 Sep 2017
Published: 28 Mar 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 11/1451
Management of the data involved in backup or backup restore: by selection of backup contents
G06F 11/1464
Management of the backup or restore process: for networked environments
G06F 11/1466
Management of the backup or restore process: to make the backup process non-disruptive
G06F 2201/84
Indexing scheme relating to error detection, to error correction, and to monitoring: using snapshots, i.e. a logical point-in-time copy of the data