System and method for reducing storage requirement in backup subsystems utilizing segmented compression and differencing

• US 5,574,906 A
• Filed: 10/24/1994
• Issued: 11/12/1996
• Est. Priority Date: 10/24/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morris, Robert J. T.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Wang, Peter Y.
• Application Number:
  US08/328,204
• Time in Patent Office: 750 Days
• Field of Search: 395/600, 395/200
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

In a client/server environment, a method and means for reducing the storage requirement in the backup subsystem and further reducing the load on the transmission bandwidth where base files are maintained on the server in a segmented compressed format. When a file is modified on the client, the file is transmitted to the server and compared with the segmented compressed base version of the file utilizing a differencing function but without decompressing the entire base file. A delta file which is the difference between the compressed base file and the modified version of the file is created and stored on a storage medium which is part of the backup subsystem. Alternatively, a copy of frequently accessed base files are maintained on the client in a compressed format. Whenever the client detects that a frequently accessed file has been modified, the modified version of the file is differenced against the base version of that file without decompressing the entire base file and a delta file is generated. The delta file is then transmitted to the server to be stored at the server for storage medium to be utilized either immediately or at a later time to update the base version of the modified file on the server.

Claims

1. A method for storing information in a clinet-server environment having a client and a backup subsystem, the backup subsystem comprising a backup server, a server backup program, a storage medium, and a copy of a versioned sequence of a file stored in the storage medium, said versioned sequence comprising a base version of a file in multiple compressed segments and a predetermined number of delta files, the client having a client backup program and a storage medium, the client and the backup server are connected to each other by a communication link, comprising the steps of:

establishing a backup session between the client and the backup server;

detecting, using the client backup program, a changed version of said file at the client;

transmitting a changed version of said file in an uncompressed format, using the communication link, from the client to the backup subsystem; and

differencing using the backup subsystem, the changed version of said file and the multiple compressed segments of the base version of said file, said differencing further including the steps of;

compressing the changed version of said file at the backup server one line at a time;

comparing each compressed line of the changed version of said file with the corresponding line of the base version of said file one line at a time;

determining whether a difference between the compressed line of the changed version of said file and the compressed line of the base version of said file has been detected;

decompressing the segment of the base version of said file, known as the current segment, if a difference has been detected;

comparing the uncompressed current segment of the base version of said file and the corresponding segment of the changed version of said file where the difference has been detected;

creating a delta file which includes the differences detected;

determining whether the differencing procedure is back in synch at the end of the current segment of the base version of said file; and

storing the changed version of said file in the compressed segmented format.

2. A method for storing information in a client-server environment having a client and a backup subsystem, the backup subsystem comprising a backup server, a server backup program, a storage medium, and a copy of a versioned sequence of a file stored in the storage medium, said versioned sequence comprising a base version of a file in multiple compressed segments and a predetermined number of delta files, the client and the server are in communication with each other by a communication link, comprising the steps of:

establishing a backup session between the client and the backup subsystem;

detecting a changed version of said file at the client;

differencing, using the client, the changed version of said file and the multiple compressed segments of the base version of said file at the client to create a delta file, said differencing further including the steps of;

compressing the changed version of said file at the client one line at a time;

comparing each compressed line of the changed version of said file with the corresponding line of the base version of said file one line at a time;

determining whether a difference between the compressed line of the changed version of said file and the compressed line of the base version of said file has been detected;

decompressing the segment of the base version of said file, known as the current segment, if a difference has been detected;

comparing the uncompressed current segment of the base version of said file and the corresponding segment of the changed version of said file where the difference has been detected;

creating a delta file which includes the differences detected;

determining whether the differencing procedure is back in synch at the end of the current segment of the base version of said file; and

storing the changed version of said file in the compressed segmented format;

transmitting said delta file, using the communication link, to the backup subsystem; and

storing said delta file in the backup subsystem.

3. In a client-server environment having a client and a backup subsystem, the backup subsystem comprising a backup server and a backup storage medium, and where the client comprises a client storage medium, the client and the backup server connected to each other by a communication link, a method for reducing the storage requirements and transmission loads in said client-server environment, comprising the steps of:

storing a versioned sequence of a file, using the backup storage medium, in the backup subsystem, said versioned sequence comprising a base version of a file in multiple compressed segments and a predetermined number of delta files;

detecting a changed version of said file at the client;

differencing, using the client, the changed version of the said file and the multiple compressed segments of the base version of said file to create a delta file at the client, said differencing further including the steps of;

compressing the changed version of said file at the client one line at a time;

comparing, at the client, each compressed line of the changed version of said file with the corresponding line of the base version of said file one line at a time;

determining whether a difference between the compressed line of the changed version of said file and the compressed line of the base version of said file has been detected;

decompressing the segment of the base version of said file, known as the current segment, if a difference has been detected;

comparing the uncompressed current segment of the base version of said file and the corresponding segment of the changed version of said file where the difference has been detected;

determining whether the differencing procedure is back in synch at the end of the current segment of the base version of said file; and

storing the changed version of said file in multiple compressed segments;

transmitting, using the communication link, said delta file to the server; and

storing said delta file in the backup subsystem.

4. In a client-server environment having a client and a backup subsystem, the backup subsystem comprising a backup server and a storage medium, and where the client comprises a client storage medium, the client and the server connected to each other by a communication link, said client-server environment comprising:

mean for storing a versioned sequence of a file in the backup subsystem, said versioned sequence comprising a base version of a file in multiple compressed segments and a predetermined number of delta files;

means for storing a copy of the base version of said file in the client;

means for detecting a changed version of said file at the client;

means for differencing the changed version of said file and the multiple compressed segments of the base version of said file to create a delta file at the client, said means for differencing further including;

means for compressing the changed version of said file at the client one line at a time;

means for comparing, at the client, each compressed line of the changed version of said file with the corresponding line of the base version of said file one line at a time;

means for determining whether a difference between the compressed line of the changed version of said file and the compressed line of the base version of said file has been detected;

means for decompressing the segment of the base version of said file, known as the current segment, if a difference has been detected;

means for comparing the uncompressed current segment of the base version of said file and the corresponding segment of the changed version of said file where the difference has been detected;

means for determining whether the differencing procedure is back in synch at the end of the current segment of the base version of said file; and

means for storing the changed version of said file in multiple compressed segments;

means for transmitting the delta file to the backup subsystem; and

means for storing said delta file in the backup subsystem so the base version of said file can be updated at a predetermined time.