Method of Detecting Source Change for File Level Incremental Backup

A computer readable medium with instructions encoded thereon for execution by a processor for performing incremental backups of computer files the instructions when executed by a processor are operable to:

• read 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;
• for each information entry in the file list:
• generate 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
• add 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;
• examine a source node to identify a plurality of source files, with each source file having a source path and source content information;
• 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;
• 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
• 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.

An apparatus, comprising:

• a processor;
• a network interface to communicate over a network with a source node;
• and
• tangible, non-transitory computer readable instructions operable to cause the processor to:
• read 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;
• for each information entry in the file list:
• generate 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
• add 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;
• examine a source node to identify a plurality of source files, with each source file having a source path and source content information;
• 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;
• 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
• 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.