System and methods for efficiently managing incremental data backup revisions

• US 20050246398A1
• Filed: 05/02/2004
• Published: 11/03/2005
• Est. Priority Date: 05/02/2004
• Status: Active Grant

• Current Assignee: Datamills Limited
• Original Assignee: Datamills Limited
• Inventors: Barzilai, Yoram, Barzilai, Orly
• Granted Patent: US 7,536,424 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

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.

Claims

1. A system for managing backup revisions on a backup system comprising:

means to hold the stored elements that are needed by the backup revisions;

means that hold the meta data of the backup revisions;

at least one mean that references stored elements that have a non-zero probability of becoming redundant when a backup revision expires.

2. The system of claim 1 wherein an additional mean exist that associates each stored element with the backup groups that need it.

3. A system for managing backup revisions on a backup system comprising:

means to hold the stored elements that are needed by the backup revisions;

means that hold the meta data of the backup revisions;

mean that associates each stored element with the backup groups that need it.

4. The system of claim 3 wherein an additional mean exist that holds stored elements that have a non-zero probability of becoming redundant when a backup revision expires.

5. A method of managing backup revisions on a backup system, each backup revision has at least one stored data element that it needs, at least one backup group exists on the backup system, each said backup group contains at least one backup revision that belongs to the same backup set, each backup set defines a collection of data sets that are located on a digital processing apparatus, and each backup set has its own backup group, wherein a backup session that produces a backup revision for a certain backup set comprising the steps of:

storing data element for each data set, which is defined by the backup set and which said data set has changed since the previous backup session;

producing a meta data that portraits the backup set during the backup session;

identifying delete candidate data elements that have a non-zero probability of becoming redundant when a backup revision that belongs to the same backup group as the current backup session expires.

6. The method of claim 5 wherein, a delete candidate data element, which is identified in said step of identifying data elements, is any stored element that is needed by a data set that was a part of the backup set during a non-expired backup revision that belongs to that backup group, provided that the content of this data set has changed in the backup session taken subsequently to said non-expired backup revision.

7. The method of claim 5 wherein, a delete candidate data element, which is identified in said step of identifying data elements, is any stored element that is needed by a data set that was a part of the backup set during a non-expired backup revision that belongs to that backup group, provided that the content this data set is not consistent over the other non-expired backup revision available for this backup group.

8. The method of claim 5 wherein, said step of identifying delete candidate data elements, results in adding to the backup group'"'"'s delete candidate data elements, any data element which is needed by a data set that exists in the previously taken backup revision available for this backup group, provided that the content of this data set has changed in the current backup session.

9. The method of claim 5 wherein said step of identifying delete candidate data elements results in the following two steps:

adding to the previously identified delete candidate data elements any data element, which needs a data set that was part of the backup set during the previous backup session on said backup set, provided that its content has changed in the current backup revision;

removing from the previously identified delete candidate data elements any data element that needs a data set, which was a part of the backup set during the current backup session.

10. The method of claim 5 wherein said step of adding to the previously identified delete candidate data elements any data element, which needs a data set that was part of the backup set during the previous backup session;

further includes adding such a delete candidate data element only if no other data set with an identical content was part of said backup set during the current backup session.

11. The method of claim 5 further includes a step of associating to each identified delete candidate data element, a set of backup revisions, which belong to the same backup group as the currently taken backup revision, provided that they need said delete candidate stored element.

12. The method of claim 11, wherein said step of associating to each identified delete candidate data element, a set of backup revisions, which belong to the same backup group as the currently taken backup revision, provided that they need said delete candidate stored element, results in:

appending references of every backup revision that was taken since the recent backup revision in which a data set that need said delete candidate stored element turned out in the backup set.

13. The method of claim 5 wherein, for every backup group a set of data elements is managed, and this set includes every data element which is needed by any of the backup revisions that belong to that backup group.

14. The method of claim 5 wherein for every backup group a set of data elements that are needed by the backup revisions that belong to this backup group is managed;

and for each such data element, the number of the data sets that need it among those data sets that were present on the backup set during the current backup session is also managed.

15. The method of claim 13 wherein said management includes only updates that result from the changes to data sets that are defined by the backed up backup set, wherein said data sets changes is in comparison to the previous backup session.

16. The method of claim 13 wherein said number of data element is used to determine whether a data set bearing a certain signature no longer exists on said backup set during the current backup session.

17. The method of claim 5 further includes a step of managing for each data element a set of backup groups that need it.

18. The method of claim 17 results, for every stored data element that is needed by a data set that was added to the backup set during the current backup session, in the following step:

wherein if the backup group that the current backup session belongs to is not already referenced for said stored data element, adding a reference of said backup group to said stored element.

19. The method of claim 5, wherein said produced meta data that portraits the backup set during the backup session includes both a full backup set inventory and a change backup set inventory.

20. The method of claim 5, wherein the produced meta data that portraits the backup set during a backup session, which is not the first one taken that backup set, includes only a change backup set inventory.

21. The method of claim 20, wherein said change backup set inventory details the data sets that have been either added, modified, or deleted in the current backup session in comparison to the previous one.

22. The method of claim 5 wherein said step of storing data element for each data set, further includes storing each such data element to a location that reflects a result of a hash function, which is performed on the data set content.

23. The method of claim 5 wherein the stored data element in said step of storing data element for each data set, is the content of said data set.

24. The method of claim 5 wherein the stored data element in said step of storing data element for each data set, is the encrypted content of said data set.

25. The method of claim 21 further includes storing said data element only if a data element is not located on the backup system in a place which corresponds to said hash result.

27. The method of claim 5 wherein each backup group can have several types of backup revisions for the same backup set.

28. The method of claim 27 wherein each said type of a backup revision can be a result of a backup done on an intra-daily, daily, weekly, monthly, or a yearly basis.

29. The method of claim 27 wherein a predetermined schedule exists on the backup system, which invokes the expiration of a certain backup revision type.

30. The method of claim 27 wherein the expiration of the oldest backup revision of a certain type is invoked after each backup session of the same type.

26. A system for storing data elements in an incremental backup system comprising:

means to store the data elements;

stored data elements, each located in a storage place that is a function of it content.

31. A method of managing backup revisions on a backup system, at least one backup group exists on the backup system, each said backup group contains at least one backup revision of a backup set, and for each such backup group there is at least one data element stored in a computer readable storage, a mean holding the meta data of each backup revision exist, and a set of delete candidate data elements exist for each backup group comprising the steps of:

requesting to expire a backup revision;

locating which of the delete candidate data elements are redundant stored elements.

32. The method of claim 31 wherein said step of locating which of the delete candidate data elements are redundant stored elements further includes:

searching if there is a data set which needs said delete candidate data element in all the other backup revisions which are available for any backup group;

wherein if such a data set is not found in any of the searched backup revisions, then said delete candidate data element is recognized as redundant.

33. The method of claim 31 wherein said step of locating the redundant stored elements further includes:

checking that said delete candidate data element is not needed by other backup revisions that belongs to the same backup group;

wherein if said delete candidate data element does not have other backup revisions that belongs to the same backup group that need it, checking that said delete candidate data element does not have other backup groups that need it;

wherein if said delete candidate data element does not have other backup groups that need it, then said delete candidate data element is recognized as redundant.

34. The method of claim 33 wherein said step of checking that said delete candidate data element is not needed by other backup revisions that belongs to the same backup group, is performed on a mean that holds for every data element only the backup revisions that need the data element provided that they belong to the same backup group.

35. The method of claim 33 wherein said step of checking that said delete candidate data element does not have other backup groups that need it, is performed on a mean that holds for every data elements the backup groups that need them.

36. The method of claim 31 wherein said redundant data elements are deleted form said computer readable storage.

37. The method of claim 31 wherein said redundant data elements are both deleted from said computer readable storage, and are copied to another storage facility.