Incremental computer file backup using a two-step comparison of first two characters in the block and a signature with pre-stored character and signature sets

• US 5,794,254 A
• Filed: 12/03/1996
• Issued: 08/11/1998
• Est. Priority Date: 12/03/1996
• Status: Expired due to Term

• Current Assignee: CDD Technologies LLC (IPNav)
• Original Assignee: Fairbanks Systems Group
• Inventors: McClain, Fred W.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US08/757,134
• Time in Patent Office: 616 Days
• Field of Search: 395/182.04, 395/600, 707/204, 711/162, 711/111
• US Class Current: 707/654
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06Q 40/08 Insurance
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A system backs up computer files to a remote site via modem. Files of a user computer that are found in a common library at the remote site initially are not copied to the remote site, whereas files not in the library are copied to the remote site. Then, periodically the user computer determines which blocks have been changed, and the user computer transmits only changed blocks to the remote site. The blocks are gathered in "chunk" files, and when a chunk file reaches a predetermined size, it is transmitted to the remote site for updating the back up version of the respective file. The process then resumes identifying changed blocks. In addition to flagging the changed block for transfer, the process resynchronizes the local data file with the backed up version using a two-step comparison, first comparing the first two characters in the block with a pre-stored character set, and then, if the first comparison results in a match, comparing a digital signature of the changed block with a pre-stored signature. If either comparison results in a mismatch, the test is repeated using, as the first byte of the test block, the next byte in the sequence.

Claims

1. A computer program product comprising:

a computer program storage device readable by a digital processing system; and

logic means on the program storage device and including instructions executable by the digital processing system for performing method steps for backing up at least some blocks in at least one local computer file from at least one user computer in a computer network, the method steps comprising;

(a) transmitting the local file to a data center remote from the user computer to render a remote version, the data center being accessible via the computer network;

(b) for each of the blocks in the local file, copying two respective characters thereof defining respective first comparison values and generating respective digital signature codes defining second comparison values;

(c) for each block, periodically determining a test digital signature code and comparing it to the respective second comparison value; and

(d) designating a block of the local file as a transmission block to be transmitted to the data center to thereby update the remote version when the test digital signature code of the block does not equal the second comparison value of the block.

2. The computer program product of claim 1, wherein the method steps further comprise:

(e) when the test digital signature code of a block does not equal the respective second comparison value, determining whether the first two characters of a block, starting with a test byte_i of the block, equal one of the first comparison values, wherein i=a natural number;

(f) when the first two characters equal one of the first comparison values, determining a block digital signature code using the test byte_i as the first byte of a test block;

(g) determining whether the block digital signature code equals one of the second comparison values;

(h) when the block digital signal code equals one of the second comparison values, returning "resynchronized";

otherwise

(i) when either the first two characters do not equal one of the first comparison values, or when the block digital signature code does not equal one of the second comparison values, setting i=i+1 and repeating steps (e)-(i).

3. The computer program product of claim 2, wherein the method steps further comprise:

gathering transmission blocks in a transfer chunk; and

when the size of the transfer chunk equals a predetermined size, transmitting the transfer chunk to the data center.

4. The computer program product of claim 3, wherein transfer chunks are transmitted to the data center only during a predetermined period.

5. The computer program product of claim 4, wherein the method steps further comprise:

for each local file block, determining whether a duplicate of the local file block is stored in a common file block library at the data center; and

undertaking step (a) only when a duplicate of the local file block is not stored in a common file block library.

6. The computer program product of claim 5, wherein the method steps further comprise:

periodically copying remote versions at the data center onto a portable data storage medium; and

restoring local files by copying remote versions from the portable data storage medium when the remote versions stored on the portable data storage medium are at least as current as the remote versions stored at the data center, and otherwise restoring local files by copying remote versions from the data center.

7. The computer program product of claim 2, in combination with the digital processing apparatus.

8. The combination of claim 7, in further combination with the computer network.

9. A system for backing up files in user computers, comprising:

a data center;

a plurality of user computers remote from the data center and in communication with the data center;

initialization logic means associated with each user computer for causing at least some file blocks to be transmitted to the data center;

subfile incremental back up logic means associated with each user computer for determining changed blocks that have been changed since a predetermined back up time and generating changed block signals in response thereto;

chunk transmission logic means responsive to the subfile incremental logic means for sending only changed blocks to the data center in chunks having a predetermined size;

synchronizing logic means responsive to the changed block signals for synchronizing the subfile incremental logic means;

logic means for generating a listing of the blocks of the files stored at the data center and, associated with each block the first two characters of the block, and a digital signature of the block, wherein the subfile incremental logic means uses the listing to undertake the determining function and the synchronizing logic means uses the listing to undertake the synchronizing function;

logic means for periodically copying remote versions at the data center onto a portable data storage medium; and

logic means for restoring local files by copying remote versions from the portable data storage medium when the remote versions stored on the portable data storage medium are at least as current as the remote versions stored at the data center, and otherwise restoring local files by copying remote versions from the data center.

10. A computer-implemented for backing up at least one local computer file from at least one user computer in a computer network, comprising:

(a) transmitting the local file to a data center remote from the user computer to render a remote version, the data center being accessible via the computer network;

(b) for each of the blocks in the local file, copying two respective characters thereof defining respective first comparison values and generating respective digital signature codes defining second comparison values;

(c) for each block, periodically determining a test digital signature code and comparing it to the respective second comparison value; and

(d) designating a block of the local file as a transmission block to be transmitted to the data center to thereby update the remote version when the test digital signature code of the block does not equal the second comparison value of the block.

11. The computer-implemented method of claim 10, further comprising:

(e) when the test digital signature code of a block does not equal the respective second comparison value, determining whether the first two characters of the block equal one of the first comparison values;

(f) when the first two characters equal one of the first comparison values, determining a block digital signature code using a test byte_i as the first byte of a test block;

(g) determining whether the block digital signature code equals one of the second comparison values;

(h) when the block digital signal code equals one of the second comparison values, returning "resynchronized";

otherwise

(i) when either the first two characters of the test byte_i do not equal one of the first comparison values, or when the block digital signature code does not equal one of the second comparison values, setting i=i+1 and repeating steps (e)-(i).

12. The computer-implemented method of claim 11, further comprising:

gathering transmission blocks in a transfer chunk; and

when the size of the transfer chunk equals a predetermined size, transmitting the transfer chunk to the data center.

13. The computer-implemented method of claim 12, wherein transfer chunks are transmitted to the data center only during a predetermined period.

14. The computer-implemented method of claim 13, further comprising:

for at least some of the local file block, determining whether a duplicate of the local file block is stored in a common file block library at the data center; and

undertaking step (a) only when a duplicate of the local file block is not stored in a common file block library.

15. The computer-implemented method of claim 14, further comprising:

periodically copying remote versions at the data center onto a portable data storage medium; and

restoring local file blocks by copying remote versions from the portable data storage medium when the remote versions stored on the portable data storage medium are at least as current as the remote versions stored at the data center, and otherwise restoring local file blocks by copying remote versions from the data center.