Computer apparatus and method for merging system deltas

• US 5,729,743 A
• Filed: 11/30/1995
• Issued: 03/17/1998
• Est. Priority Date: 11/17/1995
• Status: Expired due to Term

• Current Assignee: Double-Take Software Canada Incorporated (Open Text Corporation)
• Original Assignee: Deltatech Research, Inc.
• Inventors: Squibb, Mark
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Min, Donald
• Application Number:
  US08/565,486
• Time in Patent Office: 838 Days
• Field of Search: 395/619, 395/620, 395/712, 395/618, 395/617
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• 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/99954 Version management

Abstract

A computer apparatus and method for merging system deltas, and more particularly, to a computer apparatus and method for 1) merging a number of system deltas with a copy of a system'"'"'s files (primary input stream) to create a revised copy of a system'"'"'s files (primary output stream), 2) merging a plurality of system deltas with one another to create a compiled system delta, 3) creating inverse system deltas, and 4) merging inverse system deltas as in 1) and 2), supra. The methods may be used to save, construct and/or retrieve current and historical system states. The apparatus and method may be used in conjunction with a computer backup process, version manager, or the like.

Claims

1. In a programmable computer, a method of merging a number of system deltas with a primary input stream to build a primary output stream, said primary input stream being associated with a primary input stream directory, the method comprising the steps of:

a) setting up a system filter;

b) processing each element of a physical element set through the system filter, in an order dictated by the primary input stream directory; and

c) either before or after step b), processing each element of a new-in-scope element set through the system filter, pursuant to a new-in-scope directory order.

2. In a programmable computer, a method of merging a number of system deltas with a primary input stream to build a primary output stream, said primary input stream being associated with a primary input stream directory, the method comprising the steps of:

a) setting up a system filter, the system filter comprising;

i) a primary input;

ii) a primary output; and

iii) a number of base filter elements corresponding to the number of system deltas, wherein,

A) each of the number of base filter elements has a system delta input; and

B) if more than one base filter element exists, each of the number of base filter elements links to one another to form a sequence of base filter elements between the primary input and the primary output;

b) processing each element of a physical element set through the system filter, in an order dictated by the primary input stream directory; and

c) either before or after step b), processing each element of a new-in-scope element set through the system filter;

wherein the step of setting up the system filter comprises the steps of;

d) determining the system filter'"'"'s scope and sense;

e) if the system filter'"'"'s sense is forward, connecting each forward system delta within the system filter'"'"'s scope to one of the system delta inputs of the number of base filter elements;

f) if the system filter'"'"'s sense is negative, connecting each negative system delta within the system filter'"'"'s scope to one of the delta inputs of the number of base filter elements;

g) configuring the primary input to receive a primary input stream; and

h) configuring the primary output to generate a primary output stream.

3. A method as in claim 2, wherein each base filter element of the number of base filter elements comprises a system delta output.

4. A method as in claim 3, wherein the method further comprises the steps of:

a) if the system filter'"'"'s sense is forward, configuring each system delta output of the number of base filter elements to generate a negative system delta corresponding to the system delta received at the base filter element'"'"'s system delta input; and

b) if the system filter'"'"'s sense is negative, configuring each system delta output of the number of base filter elements to generate a forward system delta corresponding to the system delta received at the base filter element'"'"'s system delta input.

5. A method as in claim 4, wherein the steps of processing each element of an element set through the system filter comprise the steps of:

a) engaging one or more of the number of base filter elements which are within a lifetime of the element to be processed, beginning with a base filter element which is closest in proximity to the system filter'"'"'s primary input, and ending with a base filter element which is closest in proximity to the system filter'"'"'s primary output, to form a routing path between a working input stream (WIS) and a working output stream (WOS);

wherein each of the elements to be processed through the system filter may have a unique routing path;

b) redirecting the WIS and/or WOS in response to a transaction type serviced by each of the number of base filter elements which is engaged in the above step.

6. A method as in claim 5, further comprising the steps of:

a) each time an element is to be processed through the system filter, initializing the WIS and WOS to respectively coincide with the system filter'"'"'s primary input stream and primary output stream;

b) each time an element of the physical element set is to be processed through the system filter, redirecting the WOS to coincide with either the system filter'"'"'s primary output stream or the system delta output of one of the system filter'"'"'s number of base filter elements; and

c) each time an element of the new-in-scope element set is to be processed through the system filter,

i) redirecting the WIS to coincide with the system delta input of one of the system filter'"'"'s number of base filter elements; and

ii) redirecting the WOS to coincide with either the system filter'"'"'s primary output stream or the system delta output of one of the system filter'"'"'s number of base filter elements.

7. A method as in claim 6, wherein the step of redirecting the WIS and/or WOS in response to a transaction type serviced by an engaged base filter element comprises the steps of:

a) if the transaction type is NEW, redirecting the WIS to coincide with the system delta input of the base filter element servicing the NEW transaction type, and recording a DELETE transaction type in the inverse system delta associated with the base filter element'"'"'s system delta output;

b) if the transaction type is UPDATE, extending a delta bridge to a bridge filter element, and recording an UPDATE transaction type in the inverse system delta associated with the base filter element'"'"'s system delta output;

c) if the transaction type is DELETE, redirecting the WOS to coincide with the system delta output of the base filter element servicing the DELETE transaction type, and recording a NEW transaction type in the inverse system delta associated with the base filter element'"'"'s system delta output; and

d) if the transaction type is REPLACE,

i) redirecting the WOS to coincide with the system delta output of the base filter element servicing the REPLACE transaction type;

ii) processing the element through the system filter; and

iii) redirecting the WIS to coincide with the system delta input of the base filter element servicing the REPLACE transaction type, and recording a REPLACE transaction type in the inverse system delta associated with the base filter element'"'"'s system delta output.

8. A method as in claim 7, wherein the steps of processing each element of an element set through the system filter further comprise the steps of:

a) if a delta bridge exists,

i) merging the WIS with a sequential plurality of delta streams received through the system delta inputs of the base filter elements comprising the delta bridge; and

ii) writing a result of the merge to the WOS;

b) if a delta bridge does not exist, copying the WIS to the WOS; and

c) updating the directory of the WOS.

9. A method as in claim 8, wherein the steps of processing each element of an element set through the system filter further comprise the step of processing any clones of an element, immediately after processing the cloned element.

10. A method as in claim 9, wherein the step of processing any clones of an element, immediately after processing the cloned element, comprises the steps of:

a) replaying the data of the cloned element once for each of its clones;

b) processing a next clone each time the data of the cloned element is replayed.

11. A method as in claim 10, wherein the step of replaying the data of the cloned element comprises the step of replaying a portion of the primary input stream or system delta comprising the data of the cloned element.

12. A method as in claim 10, wherein the step of replaying the data of the cloned element comprises the steps of:

a) recording the data of each cloned element during its processing through the system filter; and

c) replaying the recorded data each time the data of the cloned element is required to be replayed by claim 10.

13. A method as in claim 12, wherein the step of redirecting the WIS and/or WOS in response to the transaction type of an engaged base filter element further comprises the step of:

if the transaction type is CLONE, recording a DELETE transaction type in the inverse system delta associated with the base filter element servicing the CLONE transaction type.

14. A method as in claim 13, wherein processing a clone element comprises the steps of:

a) redirecting the WIS in response to each base filter element existing prior to a lifetime of the clone element which corresponds to an element from which data of the clone element depends;

b) disabling inverse system delta generation for each of the base filter elements referred to in the above step; and

c) performing the steps of claim 13.

15. A method as in claim 14, further comprising the steps of:

a) periodically repeating the method; and

b) from time to time, archiving a primary input stream, along with any forward or negative system deltas within a specified system filter scope of the primary input stream.

16. A method as in claim 3, wherein each system delta output of the number of base filter elements is attached to a null device.

17. In a programmable computer, a method of merging a number of system deltas with a primary input stream to build a primary output stream, said primary input stream being associated with a primary input stream directory, the method comprising the steps of:

a) setting up a system filter;

b) processing each element of a physical element set through the system filter, in an order dictated by the primary input stream directory; and

c) either before or after step b), processing each element of a new-in-scope element set through the system filter;

wherein the steps of processing each element of an element set through the system filter comprise the step of processing any clones of an element, immediately after processing the cloned element; and

wherein the step of processing any clones of an element, immediately after processing the cloned element, comprises the steps of;

d) replaying the data of the cloned element once for each of its clones; and

e) processing a next clone each time the data of the cloned element is replayed.

18. A method as in claim 17, wherein the step of replaying the data of the cloned element comprises the step of replaying a portion of the primary input stream or system delta comprising the data of the cloned element.

19. A method as in claim 17, wherein the step of replaying the data of the cloned element comprises the steps of:

a) recording the data of each cloned element during its processing through the system filter; and

c) replaying the recorded data each time the data of the cloned element is required to be replayed by claim 17.