System and methods for efficiently managing incremental data backup revisions

Abstract

A system and methods for building an efficient incremental data backup system capable of managing high frequency backups sessions, and capable of efficiently expiring backup revisions and locating the useless data elements is disclosed. A reduced set of data elements that have a non-zero probability of becoming redundant when a backup revision expires is prepared while each backup revision is being processed by the backup system. The backup system also maintains data structures, which reduce the number of searches that should be performed for each such data element before it can be realized that the data element is exclusively needed to support the expired backup revision, and therefore could be removed from the second tier storage.

1 . A method for managing incremental backup revisions in a computer system, said method using a computer executable program running on a computer, said computer executable program comprising instructions for managing said incremental backup revisions comprising:
 identifying a backup set comprising a data set that changed since a previous backup session;   storing at least one data element for said data set;   producing meta data that portraits said data set changes during said previous backup session; and   identifying said at least one stored data element in a backup group comprising backup revisions as a delete candidate data element.   
   
   
       2 . The method of  claim 1  wherein said delete candidate data element is needed by said data set and is a part of said backup set during a non-expired backup revision belonging to said backup group, provided that said content of said data set has changed in a subsequent backup session to said non-expired backup revision. 
   
   
       3 . The method of  claim 1  wherein said delete candidate data element is needed by said data set and a part of said backup set during a non-expired backup revision belonging to said backup group, provided that said content of said data set is inconsistent over said other non-expired backup revision available for said backup group. 
   
   
       4 . The method of  claim 1  wherein said identifying step results in adding to said delete candidate data element each data element needed by a data set from said previous backup revision available for said backup group, provided that said content of said data set has changed in said current backup session. 
   
   
       5 . The method of  claim 1  further comprising:
 adding to said identified delete candidate data elements each data element which needs a data set and that was part of said backup set during said previous backup session of said backup set, provided that its content has changed in said current backup revision;   removing from said previously identified delete candidate data elements each data element that needs a data set that was a part of said backup set during said current backup session.   
   
   
       6 . The method of  claim 5  wherein said step of adding to said previously identified delete candidate data elements further comprises identifying each data element that references a data set that was part of said backup set during said previous backup session; and
 adding said delete candidate data element when said data set is unique to said backup set during said current backup session.   
   
   
       7 . The method of  claim 1  further comprising a step of:
 associating to each identified delete candidate data element a set of backup revisions belonging to said same backup group as said backup revision, provided that said group requires said delete candidate data element.   
   
   
       8 . The method of  claim 7  wherein said step of:
 associating to each identified delete candidate data element a set of backup revisions belonging to said backup group as said currently taken backup revision, provided that said delete candidate stored element, which results in:
 appending references to every backup revision that was taken since said recent backup revision in which a data set that need said delete candidate stored element turned out in said backup set. 
   
   
   
       9 . The method of  claim 1  wherein for every backup group a set of data elements is managed, said set of data elements comprising every data element required by each previous version of said backup revisions belonging to said backup group. 
   
   
       10 . The method of  claim 9  wherein said management comprises updates that result from said changes to said data sets in said backup set, further wherein changes to said data sets are in comparison to said previous backup session. 
   
   
       11 . The method of  claim 9  wherein said number of data element is used to determine whether a data set bearing a certain signature was removed from said backup set during said current backup session. 
   
   
       12 . The method of  claim 1  further
 wherein for each backup group, managing a set of data elements needed by said backup revisions that belong to said backup group; and   for each said data element, managing said number of said data sets that need it among those data sets that were present on said backup set during said current backup session.   
   
   
       13 . The method of  claim 1  further comprising a step of managing for each data element a set of backup groups that need it. 
   
   
       14 . The method of  claim 13  wherein results for every stored data element that is needed by a data set that was added to said backup set during said current backup session in said following step:
 adding a reference of said backup group to said stored data element.   
   
   
       15 . The method of  claim 1  wherein said produced meta data that portraits said backup set during said backup session comprises both a full backup set inventory and a change backup set inventory. 
   
   
       16 . The method of  claim 1  wherein said produced meta data that portraits said backup set during a backup session further comprises a change backup set inventory. 
   
   
       17 . The method of  claim 16  wherein said change backup set inventory details said data sets that have been either added, modified, or deleted in said current backup session in comparison to said previous backup session. 
   
   
       18 . The method of  claim 1  wherein said step of storing a data element for each data set further comprises storing each such data element to a location that reflects a result of a hash function performed on said data set content. 
   
   
       19 . The method of  claim 18  further includes storing said data element when said data element is absent from said backup system at a location corresponding to said hash result. 
   
   
       20 . The method of  claim 1  wherein said stored data element in said step of storing data element for each data set is an encrypted representation of said data set.