Fast incremental backup method and system

• US 7,366,859 B2
• Filed: 10/06/2005
• Issued: 04/29/2008
• Est. Priority Date: 10/06/2005
• Status: Active Grant

• Current Assignee: MidCap Financial Trust
• Original Assignee: Acronis, Inc. (Acronis AG)
• Inventors: Beloussov, Serguei M., Tormasov, Alexander G., Lyadvinsky, Maxim V., Tsypliaev, Maxim V., Per, Yuri S.
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US11/244,298
• Publication Number:
  US 20070083722A1
• Time in Patent Office: 936 Days
• Field of Search: None
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

A method of incremental backup of a storage device includes reading descriptors of logical storage units of the storage device; comparing the descriptors of the logical storage units of the storage device with descriptors of archived logical storage units; for logical storage units of the storage device whose descriptors are not identical to the descriptors of the archived logical storage units, backing up contents of physical storage units that correspond to those logical storage units of the storage device; and, for logical storage units of the storage device whose descriptors are identical, performing a comparison step to check if these logical storage units need to be backed up. The logical storage units can be files. The comparison step can be, e.g., (1) bit-wise comparison of the logical blocks, (2) comparing control sums of the logical blocks, and (3) comparing log files relating to the logical storage units The physical storage units can be blocks. The descriptors can be, e.g., MFT entries, hash function values, timestamps, checksums, and file metadata. The descriptors can be compared on a physical storage unit basis. The method further can optionally include generating a bitmap of the physical storage units of the storage device; marking, in the bitmap, those physical storage units that correspond to logical storage units with different descriptors; and archiving content of the physical storage units marked in the bitmap. The method can further optionally include archiving logical storage units of the storage device having the same name as corresponding archived logical storage units of the storage device, but different time stamps.

Claims

1. A method of incremental backup of a storage device, comprising:

(a) generating a bitmap of selected physical storage units of a storage device, with all selected physical storage units marked;

(b) selecting an area of the storage device for backup;

(c) reading descriptors of logical storage units of the selected area;

(d) comparing hash function values of the descriptors of the logical storage units of the selected area with hash function values of descriptors of already archived logical storage units;

(e) for physical storage units related to logical storage units of the selected area whose descriptors are not identical to the descriptors of the archived logical storage units, based on step (d), checking if these physical storage units need to be backed up and unmarking, in the bitmap, those physical storage units that correspond to the archived logical storage units with coincident descriptors; and

(f) backing up contents of physical storage units identified as marked in the bitmap in step (e).

2. The method of claim 1, further comprising backing up contents of physical storage units of the storage device outside the selected area.

3. The method of claim 1, wherein the logical storage units are files.

4. The method of claim 1, wherein the physical storage units are blocks or clusters.

5. The method of claim 1, wherein the descriptors are MFT entries.

6. The method of claim 1, wherein, step (e) further comprises generating hash function values for physical storage units and comparing the hash function values of the physical storage units for physical storage units of the storage device and already archived physical storage units, having the same addresses.

7. The method of claim 6, wherein the hash function value is generated for group of physical storage units.

8. The method of claim 6, wherein hash function generates relatively short hash function value, further comprising comparing blocks having identical hash function values.

9. The method of claim 6, wherein a control sum is used as a hash function value.

10. The method of claim 6, wherein hash function generates a long hash function value, further comprising step of comparing blocks from group with different hash function values.

11. The method of claim 1, wherein the descriptors include timestamps.

12. The method of claim 1, wherein the descriptors include checksums.

13. The method of claim 1, wherein the descriptors include file metadata.

14. The method of claim 1, wherein descriptors being content of some physical storage units, further comprising comparing the descriptors on a physical storage unit basis.

15. The method of claim 1, further comprising backing up content of at least some used physical storage units of the storage device lying outside the selected area.

16. The method of claim 15, wherein used physical storage units relate to the logical storage units of the storage device having the same name as corresponding archived logical storage units, but different time stamps.

17. The method of claim 1, further comprising archiving physical storage units of the logical storage units of the storage device having names that are not present the storage device wherein the archived physical storage units are not included to the selected area.

18. The method of claim 1, wherein step (d) comprises bit-wise comparison of the content physical storage units.

19. A system for incremental backup of a storage device, comprising:

(a) means for generating a bitmap of the selected physical storage units of the storage device, with all selected physical storage units marked;

(b) means for selecting an area of the storage device for backup;

(c) means for reading descriptors of logical storage units of the selected area;

(d) means for comparing hash function values of the descriptors of the logical storage units of the selected area with hash function values of the descriptors of already archived logical storage units;

(e) for physical storage units related to logical storage units of the selected area whose descriptors are not identical to the descriptors of the archived logical storage units, based on the comparison in (d), means for checking if these physical storage units need to be backed up and for unmarking, in the bitmap, those physical storage units that correspond to the archived logical storage units with coincident descriptors; and

(f) means for backing up contents of physical storage units identified in (e) as marked in the bitmap.

20. A system for incremental backup, comprising:

a main storage that includes physical storage units and logical storage units;

a bitmap of the selected physical storage units of the storage device, with all selected physical storage units marked;

an archive of a previous state of the main storage; and

a plurality of descriptors corresponding to the logical storage units,

wherein, for those logical storage units for those logical storage units whose hash function values of their descriptors are the same as hash function values of descriptors of archived logical storage units, are unmarked in the bitmap, and for those logical storage units whose hash function values of descriptors are not the same as hash function values of descriptors of archived logical storage units, an incremental backup is performed of corresponding physical storage units that are marked in the bitmap.