US 5,559,991 AGranted

Incremental computer file backup using check words

AssigneeLucent Technologies Inc.

InventorArnon Kanfi

Life of this patent

Estimating the term…

Loading patent…

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.

Claims23

Dependent claims

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.

3 more elements

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.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/495,242Filed 27 Jun 1995 · continuation
Priority: 4 Nov 1991
Granted: 24 Sep 1996
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 11/1451
Management of the data involved in backup or backup restore: by selection of backup contents
G06F 11/08
Responding to the occurrence of a fault, e.g. fault tolerance: error detection or correction by redundancy in data representation, e.g. by using…
G06F 2201/835
Indexing scheme relating to error detection, to error correction, and to monitoring: timestamp
Y10S 707/99953
Coherency, e.g. same view to multiple users: recoverability