Efficient method to identify changed objects for large scale file system backup

Abstract

One example method includes identifying changed objects in a filesystem. Entry lists of a previous backup and a current backup are processed at the same time. The comparison allows objects in the filesystem to be identified as unchanged, modified, new, or deleted relative to a previous backup.

1 . A method, comprising:
 for a current entry list and a previous entry list that each contain a plurality of entries, each entry corresponding to an object in a system, performing an entry checking operation by comparing pairs of entries in the current entry list and the previous entry list, wherein each comparison includes:
 determining an entry state of an entry in the current entry list by evaluating the entry in the current entry list with an entry in the previous entry list, wherein the current entry list is associated with a current backup of a filesystem and the previous entry list is associated with a previous backup of the filesystem; and 
 performing an operation on the entry based on the entry state; 
   finding a first differential pair that includes an entry from the current entry list and an entry from the previous entry list and inferring, from the first differential pair, whether objects have been added to or deleted from the system; and   performing a data protection operation on objects that are changed from the previous backup relative to the current backup based on the entry checking operation.   
     
     
         2 . The method of  claim 1 , further comprising crawling the file system to generate the current entry list in a deterministic manner, wherein the previous entry list was previously generated in the deterministic manner. 
     
     
         3 . The method of  claim 2 , wherein the deterministic manner is depth-first. 
     
     
         4 . The method of  claim 1 , further comprising generating a current stack used in the entry checking operation and associated with the current entry list and generating a previous stack associated with the previous entry list. 
     
     
         5 . The method of  claim 1 , wherein the system comprises a file system. 
     
     
         6 . The method of  claim 1 , further comprising skipping entries in the previous entry list associated with deleted objects and skipping entries in the current entry list associated with newly added objects. 
     
     
         7 . The method of  claim 4 , further comprising finding the first differential pair based on a comparison of the previous stack and the current stack. 
     
     
         8 . The method of  claim 1 , further comprising populating fields in the entries of the current entry list, the fields including a hash of a combination of object metadata, a next field, a flag field, a parent field. 
     
     
         9 . The method of  claim 8 , further comprising generating the hash from two or more of an object full path, an object size, a modify time. 
     
     
         10 . The method of  claim 1 , further comprising performing iterations by the entry checking operation, wherein each iteration compares and entry from the previous entry list and an entry from the current entry list. 
     
     
         11 . The method of  claim 10 , wherein the operation is one of:
 determining that an object for the entry is unchanged, wherein a previous hash of the object's content is added to the entry and a previous pointer for the previous entry list and a current pointer for current entry list are both are advanced;   determining that the object for the entry is modified, wherein a flag is set in a flag field and the current pointer and the previous pointer are advanced;   determining that the object for the entry is new, wherein a flag is set in the flag field, the current pointer is moved to skip over children entries, and the previous pointer is not advanced; or   determining that an object has been deleted, wherein the previous pointer is moved using the next field to skip entries associated with deleted objects and the current pointer is not moved.   
     
     
         12 . A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
 for a current entry list and a previous entry list that each contain a plurality of entries, each entry corresponding to an object in a system, performing an entry checking operation by comparing pairs of entries in the current entry list and the previous entry list, wherein each comparison includes:
 determining an entry state of an entry in the current entry list by evaluating the entry in the current entry list with an entry in the previous entry list, wherein the current entry list is associated with a current backup of a filesystem and the previous entry list is associated with a previous backup of the filesystem; and 
 performing an operation on the entry based on the entry state; 
   finding a first differential pair that includes an entry from the current entry list and an entry from the previous entry list and inferring, from the first differential pair, whether objects have been added to or deleted from the system; and   performing a data protection operation on objects that are changed from the previous backup relative to the current backup based on the entry checking operation.   
     
     
         13 . The non-transitory storage medium of  claim 12 , wherein the system comprises a filesystem, further comprising crawling the file system to generate the current entry list in a deterministic manner, wherein the previous entry list was previously generated in the deterministic manner. 
     
     
         14 . The non-transitory storage medium of  claim 12 , further comprising generating a current stack used in the entry checking operation and associated with the current entry list and generating a previous stack associated with the previous entry list. 
     
     
         15 . The non-transitory storage medium of  claim 14 , further comprising skipping entries in the previous entry list associated with deleted objects and skipping entries in the current entry list associated with newly added objects. 
     
     
         16 . The non-transitory storage medium of  claim 14 , further comprising finding the first differential pair based on a comparison of the previous stack and the current stack. 
     
     
         17 . The non-transitory storage medium of  claim 12 , further comprising populating fields in the entries of the current entry list, the fields including a hash of a combination of object metadata, a next field, a flag field, a parent field. 
     
     
         18 . The non-transitory storage medium of  claim 17 , further comprising generating the hash from two or more of an object full path, an object size, a modify time. 
     
     
         19 . The non-transitory storage medium of  claim 12 , further comprising performing iterations by the entry checking operation, wherein each iteration compares and entry from the previous entry list and an entry from the current entry list. 
     
     
         20 . The non-transitory storage medium of  claim 19 , wherein the operation is one of:
 determining that an object for the entry is unchanged, wherein a previous hash of the object's content is added to the entry and a previous pointer for the previous entry list and a current pointer for current entry list are both are advanced;   determining that the object for the entry is modified, wherein a flag is set in a flag field and the current pointer and the previous pointer are advanced;   determining that the object for the entry is new, wherein a flag is set in the flag field, the current pointer is moved to skip over children entries, and the previous pointer is not advanced; or   determining that an object has been deleted, wherein the previous pointer is moved using the next field to skip entries associated with deleted objects and the current pointer is not moved.