Incremental computer file backup using check words

• US 5,559,991 A
• Filed: 06/27/1995
• Issued: 09/24/1996
• Est. Priority Date: 11/04/1991
• Status: Expired due to Term

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kanfi, Arnon
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US08/495,242
• Time in Patent Office: 455 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/488, 395/489, 395/600, 395/182.04-182.06, 395/182.11
• US Class Current: 711/162
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A facility is provided for storing in a backup memory only those blocks of a file, or disk partition, which differ from corresponding blocks forming an earlier version of the file. Specifically, a file is divided into a number of blocks and a "signature" is generated for each such block. A block is then stored in the backup memory only if its associated signature differs from a signature generated for an earlier version of the block. In addition, if two blocks of the current version of the file have identical signatures and are to be stored in the backup memory, then only one of the two blocks is stored in the memory and a simple message indicating that the other block is equal to the one block is stored in the memory for the other block. Further, the application of such signatures is advantageously applied to the opposite case of restoring a file using copies of previous versions of the file that are stored in the backup memory.

Claims

1. Apparatus for storing a file in an archive memory comprising

means for dividing said file into a plurality of blocks and for assigning respective block numbers to said blocks, each of said blocks containing a predetermined number of data bytes,

means for generating for each of said blocks of said file a current check word determined as a function of the current contents of the respective block of said file and for storing each said current check word in said archive memory, and

means for storing in said archive memory each of said current blocks of said file having a current check word different from a check word that was generated for a correspondingly numbered block of a prior version of said file stored in said archive memory, wherein different groups of stored blocks of said data bytes form respective versions of is said file, and wherein said apparatus further comprises

a global bit map comprising a plurality of bit locations corresponding to respective ones of said block numbers,

means, responsive to one of said blocks being unloaded from said memory, for setting in said bit map the bit whose location corresponds with the block number of said one block, and

means, operative prior to unloading another one of said stored blocks of a respective one of said groups, for preventing the unloading of said other one of said blocks if the corresponding bit in said bit map for said other one of said blocks had been set as a result of unloading a correspondingly numbered block of another one of said groups.

2. The apparatus set forth in claim 1 wherein said means for storing each of said current blocks includes means for causing said current block to be stored in said memory if said check word for said correspondingly numbered block does not exist.

3. The apparatus set forth in claim 2 wherein said file is the contents of a memory device.

4. The apparatus set forth in claim 1 wherein the current block of said file and blocks of said prior version of said file are assigned respective time stamps.

5. The apparatus set forth in claim 1 further comprising means for storing said current check word in a table identified by a time stamp assigned to said file, said current check word being stored in said table in the order that said current check word is generated.

6. The apparatus set forth in claim 1 wherein said means for storing includes means operative if the current check words respectively generated for first and second blocks of said file equal one another for then storing in said memory in place of said second block a message indicating that the contents of said second block equals the contents of said first block, in which said first and second blocks are not necessarily adjacent blocks in said file.

7. The apparatus set forth in claim 6 wherein the blocks of said file and blocks of said prior version of said file are assigned respective time stamps.

8. The apparatus set forth in claim 7 further comprising

computer means communicating with said archive memory, said computer means comprising

means responsive to receipt of a request to restore said file for unloading from said memory the blocks of said file representing respective earlier version of said file stored in said memory and supplying the unloaded blocks to a user such that said unloading is based on the reverse order that said versions were stored in said memory.

9. The apparatus set forth in claim 8 wherein said means for unloading the blocks of said file representing respective earlier versions of said file includes

means, responsive to the unloading of said message indicating that the contents of said first and second blocks are equal, for then unloading said first block and supplying that block to said user as said second block.

10. The apparatus set forth in claim 7 wherein said means for unloading the blocks of said file representing respective earlier versions of said file further includes

a local bit map comprising a plurality of bits corresponding with respective ones of the block numbers of the blocks forming a group of blocks currently being unloaded, said group of blocks currently being unloaded including said message indicating that the contents of said first and second blocks are equal,

means, responsive to one of said blocks of the group of blocks currently being unloaded from said memory, for setting in said local bit map the bit whose location corresponds with the block number of said one block of said current group, and

means, responsive to the unloading of said message, for supplying said first block to said user as said second block if the bit in said local bit map corresponding with the block number identifying said first block is not set or supplying said message to said user if the latter bit in said local bit map is set.

11. The apparatus set forth in claim 10 wherein said means for unloading the blocks of said file representing respective earlier versions of said file further includes

means, responsive to said first block being supplied to said user as said second block, for setting the bit in said local bit map corresponding with said first block even though said first block of said group of blocks currently being unloaded is not supplied to said user as said first block.

12. The apparatus set forth in claim 8 wherein said memory comprises at least two memories independent of one another, and wherein said file represents data contained in one of said at least two memories, and wherein said apparatus further comprises

means, responsive to the storage of a previous version of said file on said one of said at least two memories, for then dividing data contained in the other one of said memories into respective blocks and generating respective check words for those blocks, and

means, responsive to generating check words for said other one of said memories, for replacing in said other one of said memories those blocks whose check words differ from the check words generated for corresponding blocks forming a previous contents of said other one of said memories.

13. A method for storing a file in a memory comprising the steps of

dividing said file into a plurality of blocks each containing a predetermined number of data bytes having respective values, assigning respective sequential numbers to said blocks and generating for each of said blocks of said file a check word indicative of the values of the data bytes forming the respective block of said file, and

storing in said memory those of said blocks of said file having check words different from check words generated for correspondingly numbered blocks of a prior version of said file, wherein groups of stored blocks form respective versions of said file, and wherein said method further comprises the steps of

maintaining a global bit map comprising a plurality of bit locations corresponding to respective ones of said block numbers,

responding to one of said blocks being unloaded from said memory by setting in said bit map the bit whose location corresponds with that one of said block numbers assigned to said one block, and

responding to an unloading of another one of said stored blocks of a respective one of said groups by preventing the unloading of said other one of said blocks if the corresponding bit in said global bit map for said other one of said blocks had been set as a result of an unloading of a correspondingly numbered block of another one of said groups characterizing a later version of said file.

14. The method set forth in claim 13 wherein said step of storing includes the step of storing all of said blocks in said memory if said check words generated for correspondingly numbered blocks of a prior version of said file do not exist.

15. The method set forth in claim 13 wherein the blocks of said file and blocks of said prior version of said file are assigned respective time stamps.

16. The method set forth in claim 13 further comprising the step of storing said check words in a table identified by a time stamp assigned to said file, said check words being stored in said table in the order that said check words are generated.

17. The method set forth in claim 13 wherein said step of storing includes the step of responding when the check words respectively generated for first and second blocks of said file equal one another by storing in said memory in place of said second block a message indicating that the contents of said second block equals the contents of said first block, in which said first and second blocks are not necessarily adjacent blocks in said file.

18. The method set forth in claim 17 wherein the blocks of said file and blocks of said prior version of said file are assigned respective time stamps.

19. The method set forth in claim 18 further comprising the steps of

responding to receipt of a request to restore said file by unloading from said memory the blocks of said file representing respective earlier versions of said file that may be stored in said memory and supplying them to a user such that said unloading of said earlier versions is based on the reverse order that said earlier versions were stored in said memory.

20. The method set forth in claim 19 wherein said step of unloading said earlier versions of said file further includes the step of responding to the unloading of said message indicating that the contents of said second block equals the contents of said first block by unloading said first block and supplying that block to said user as said second block.

21. The method set forth in claim 20 wherein said step of unloading earlier versions of said file further includes the steps of

maintaining a local bit map comprising a plurality of bits corresponding with respective ones of the block numbers of the blocks forming a group of blocks currently being unloaded, said current group including said message,

responding to one of said blocks of the current group being unloaded from said memory by setting in said local bit map the bit whose location corresponds with that one of said block numbers assigned to said one block of said current group, and

responding to the unloading of said message by supplying to said user as said second block either said first block or said message if the bit in said local bit map corresponding with the block number identifying said first block is not set or is set, respectively.

22. The method set forth in claim 19 wherein said step of unloading said earlier versions of said file further includes the step of

responding to said first block being supplied to said user as said second block by setting the bit in said local bit map that is associated with said first block even though said first block of said current group is not supplied to said user as said first block.

23. The method set forth in claim 19 wherein said memory comprises at least two memories independent of one another, and wherein said file represents a contents of one of said at least two memories, and wherein said method further comprises the steps of

responding to a storage of a previous version of said file on said one of said at least two memories by dividing data contained in the other one of said at least two memories into respective blocks and by generating respective check words for those blocks and

responding to the generation of said check words for said other one of said memories by replacing in said other one of said memories those blocks whose check words differ from the check words generated for their corresponding blocks forming a previous version of the contents of said other one of said memories.