Replica administration without data loss in a store and forward replication enterprise

Abstract

A system and method for replica administration without data loss is disclosed. In a replication environment where data is replicated around a network and where any system can make changes to the data, data loss may occur if one copy of the data is deleted before changes made to that copy are replicated to other systems in the network. The present invention describes a robust administration environment which prevents inadvertent data loss by verifying that changes made to a local copy of the data reside on at least one other system in the network. The system and method of the present invention also provide a mechanism to allow an administrator to bypass such safeguards in appropriate circumstances in order to handle special cases such as total removal of the data from the network. The replica administration environment is implemented by defining various states that represent the level of participation in the replication of the data. For example, an active state can indicate full participation while a deleted state can indicate no participation. In addition to an active state and a deleted state, one or more intermediate states may be defined. The checks and safeguards can be performed in these intermediate states. In appropriate circumstances, an administrator may force the transition from certain of the intermediate states to either the active state in order to return a system to full participation or to the deleted state in order to bypass the safeguards of the present invention.

Claims

What is claimed and desired to be secured by United States Letters Patent is:

1. In a computer network where copies of data objects are replicated among a plurality of replica nodes that are logically connected to provide a data flow path from each replica node to any other replica node in the network, and each replica node being capable of making changes to the replicated data objects and each being capable of storing the changes made either locally or by any other node, and each being capable of providing access to such stored changes by any other replica node in the network, a method of removing a local copy of a data object from a local replica node in the computer network while protecting against inadvertent loss of any changes made to the local data object prior to its removal at the local replica node, the method comprising the steps of:

saving, at a local replica node, changes made to a local copy of a data object by the local replica node and changes made by and received from other replica nodes on a computer network so that the local copy of the data object reflects all such changes made to the data object;

transmitting to at least one other replica node in the network any changes which have been made to the local copy of the data object by the local replica node and which have not previously been transmitted to at least one other replica node in the network in order to preserve said changes and ensure continued availability of said changes by virtue of their storage in said at least one other replica node of the network;

verifying that the saved changes reside on at least one other replica node in the network prior to removal of the local copy of the data object from the local replica node by (1) sending a message to said at least one other replica node, and by (2) positively confirming that the saved changes reside on the at least one other replica node if the combination of all changes on all replica nodes other than the local replica node include at least the saved changes;

removing the local copy of the data object from the local replica node if said saved changes reside on at least one other replica node without removing any changes from said at least once other replica node; and

accessing said saved changes from at least one replica node in the network.

2. A method of removing a copy of a data object from a replica node as recited in claim 1 further comprising the step of terminating user access to the local copy of the data object prior to the step of transmitting any changes which have been made to the local copy of the data object that have not previously been transmitted.

3. A method of removing a copy of a data object from a replica node as recited in claim 1 further comprising the step of removing the local replica node from a replica list comprising all replica nodes that have a copy of the data object.

4. A method of removing a copy of a data object from a replica node as recited in claim 1 wherein the message sent to said at least one other replica node comprises a request to respond if the saved changes reside on said at least one other replica node.

5. A method of removing a copy of a data object from a replica node as recited in claim 1 wherein the step of verifying that the saved changes reside on at least one other replica node in the network is skipped if an administrator directs that the step be skipped.

6. A method of removing a copy of a data object from a replica node as recited in claim 1 further comprising the step of preventing all access to the local copy of the data object prior to the step of removing the local copy of the data object.

7. In a computer network where copies of data objects are replicated among a plurality of replica nodes that are logically connected to provide a data flow path from each replica node to any other replica node in the network, and each replica node being capable of making changes to the replicated data objects and each being capable of storing the changes made either locally or by any other node, and each being capable of providing access to such stored changes by any other replica node in the network, a method of removing a local copy of a data object from a local replica node in the computer network while protecting against inadvertent loss of any changes made to the local data object prior to its removal at the local replica node, the method comprising the steps of:

transmitting to at least one other replica node in a network any changes which have been made to a local copy of a data object by a local replica node and which have not previously been transmitted to at least one other replica node in the network;

verifying that all changes which form the basis for the local copy of the data object reside on at least one other replica node on the network so that said changes will be preserved and will remain available to said network by (1) transmitting a message comprising a request for a replica node that receives the message to respond if the replica node that receives the message has at least the changes held by the local replica node, and by (2) positively confirming that the changes forming the basis for the local copy of the data object reside on at least one other replica node if the combination of all changes on all replica nodes, other than the local replica node, include at least the changes which form the basis for the local copy of the data object; and

if said changes reside on said at least one other replica node, then removing the local copy of the data object from the local replica node without removing any changes from said at least one other replica node.

8. A method of removing a copy of a data object from a replica node as recited in claim 7 further comprising the step of terminating access to the local copy of the data object prior to the step of transmitting any changes made to the local copy of the data object and which have not previously been transmitted.

9. A method of removing a copy of a data object from a replica node as recited in claim 8 wherein the local copy of the data object can be removed through intervention by an administrator even if all changes which form the basis for the local copy of the data object do not reside on at least one other replica node.

10. A method of removing a copy of a data object from a replica node as recited in claim 9 further comprising the step of removing the local replica node from a replica list comprising all replica nodes that have a copy of the data object.

11. A method of removing a copy of a data object from a replica node as recited in claim 9 further comprising the step of informing other replica nodes that the local copy of the data object has been deleted.

12. In a computer network where copies of data objects are replicated among a plurality of replica nodes that are logically connected to provide a data flow path from each replica node to any other replica node in the network, and each replica node being capable of making changes to the replicated data objects and each being capable of storing the changes made either locally or by any other node, and each being capable of providing access to such stored changes by any other replica node in the network, a method of moving a copy of a data object from a local replica node in the computer network while protecting against inadvertent loss of any changes made to the local data object prior to its removal at the local replica node, the method comprising the steps of:

initiating a process to add a first copy of a data object to a first replica node where a copy of said data object does not currently reside;

initiating a process to remove a second copy of said data object from a second replica node, said process to remove the second copy of the data object comprising:

transmitting to at least one other replica node in a network any changes which have been made to a local copy of a data object by a local replica node and which have not previously been transmitted to at least one other replica node in the network;

verifying that all changes which form the basis for the local copy of the data object reside on at least one other replica node on the network so that said changes will be preserved and will remain available to said network by (1) sending a message to said at least one other replica node, and by (2) positively confirming that the saved changes reside on the at least one other replica node if the combination of all changes on all replica nodes other than the local replica node include at least the saved changes; and

if said changes reside on said at least one other replica node, then removing the local copy of the data object from the local replica node without removing any changes from said at least one other replica node.

13. An article of manufacture for use in a computer system defining a location in a computer network where a copy of a designated data object is replicated, said computer system logically connected to at least one other computer system through networking means, each computer system comprising a CPU, said article of manufacture comprising:

program storage means for storing and providing to the CPU program code means, said program code means comprising:

means for defining an active state of a local computer system where changes made to a local copy of a data object by the local computer system are transmitted to at least one other computer system and where changes made to a copy of said data object stored by said at least one other computer system are transmitted to said local system;

means for defining a deleted state of said local computer system where said local copy of the data object has been removed from said local computer system so that said local copy no longer exists on said local computer system;

and

means for defining at least one intermediate state between said active and deleted states of said local computer system where (a) said local computer system transmits to said at least one other computer system any changes made to the local copy of the data object by said local system which have not yet been transmitted to said at least one other computer system, and where (b) said local system verifies that all information contained in the local copy of the data object resides on at least one other computer system so that when the local copy of the data object is removed, changes made to the local copy of the data object will be preserved on said at least one other computer system by (1) sending a message to said at least one other replica node, and by (2) positively confirming that the saved changes reside on the at least one other replica node if the combination of all changes on all replica nodes other than the local replica node include at least the saved changes.

14. An article of manufacture as recited in claim 13 wherein the program code means further comprises means for initiating transition from one state to another.

15. An article of manufacture as recited in claim 14 wherein the means for initiating transition from one state to another comprises means for initiating transition from the active state to said at least one intermediate state under direction from a network administrator.

16. An article of manufacture as recited in claim 13 wherein the program code means comprises means for initiating transition from the active state to said at least one intermediate state and means for initiating transition from said at least one intermediate state either to said active state or to said deleted state.

17. An article of manufacture as recited in claim 13 wherein said means for defining at least one intermediate state comprises means for defining a first intermediate state where said local computer system transmits to said at least one other computer system any changes made to the local copy of the data object by said local system which have not yet been transmitted to said at least one other computer system and where said local system verifies that all information contained in the local copy of the data object resides on at least one other computer system and means for defining a second intermediate state where the local copy of the data object is removed from said local computer system.

18. An article of manufacture as recited in claim 17 wherein said program code means comprises:

means to initiate transition from said active state to said first intermediate state;

means to initiate transition from said first intermediate state to said second intermediate state;

means to initiate transition from said first intermediate state to said active state;

means to initiate transition from said second intermediate state to said deleted state; and

means to initiate transition from said deleted state to said active state.

19. An article of manufacture as recited in claim 18 wherein said means to initiate transition from said active state to said first intermediate state initiates the transition in response to a command from a network administrator.

20. An article of manufacture as recited in claim 18 wherein said means to initiate transition from said first intermediate state to said active state initiates the transition in response to a command from a network administrator.

21. An article of manufacture as recited in claim 18 wherein said means to initiate transition from said first intermediate state to said second intermediate state initiates the transition in response to either a command from a network administrator or a positive determination that all information contained in the local copy of the data object resides on at least one other computer system in the network.

22. An article of manufacture as recited in claim 18 wherein said means to initiate transition from said second intermediate state to said deleted state initiates the transition after the local copy of the data object has been removed from said local system.

23. An article of manufacture as recited in claim 18 wherein said means to initiate transition from said deleted state to said active state initiates the transition in response to a command from a network administrator.

24. An article of manufacture for use in a computer system defining a location in a computer network where a copy of a designated data object is replicated, said computer system logically connected to at least one other computer system through networking means, each computer system comprising a CPU, said article of manufacture comprising:

program storage means for storing and providing to the CPU program code means, said program code means comprising;

means for initiating replication of changes which have been made but which have not yet been previously replicated to at least one other computer system in a computer network;

means for verifying that the changes which have been made to said local copy of the data object reside of at least one other computer system in the computer network before said local copy of the data object is removed from said local computer system so that when the local copy of the data object is removed, changes made to the local copy of the data object will be preserved on said at least one other computer system by (1) sending a message to said at least one other replica node, and by (2) positively confirming that the saved changes reside on the at least one other replica node if the combination of all changes on all replica nodes other than the local replica node include at least the saved changes; and

means for tracking a replica state of the local computer system with respect to said local copy of the data object, said replica state reflecting whether the local computer system is actively participating in the replication of said data object or whether the local computer system is in the process of removing the local copy of the data object from said local computer system.

25. An article of manufacture as recited in claim 24 wherein the program code means further comprise means for changing the replica state of the local computer system.

26. An article of manufacture as recited in claim 24 wherein the program code means further comprise means for bypassing the means for verifying that the changes which have been made to said local copy of the data object reside on at least one other computer system in the computer network so that said local copy of the data object can be deleted without verifying that the changes reside on at least one other computer system.

27. An article of manufacture as recited in claim 24 wherein the program code means comprises means for notifying a network administrator if attempts to verify that the changes made to the local copy of the data object reside on at least one other computer system are unsuccessful.

Description

BACKGROUND OF THE INVENTION

1. The Field of the Invention

The present invention relates to systems and methods for replication of data, that is, transferring changes (e.g, creation of new data, modification of existing data or deletion of existing data) made locally at one server to a specified list of other remote or locally connected servers. More specifically, the present invention relates to systems and methods for adding a copy of a data set to a server, moving a copy of a data set from one server to another and/or deleting a copy of a data set from a server without inadvertent data loss.

2. The Prior State of the Art

Today, business and technology trends are changing the way we use computers and information. The personal computer or PC has become the standard business information tool as prices have decreased and computing power has increased. In record numbers, businesses are re-engineering their organizational structure and processes to become faster is and more competitive, in addition to being better able to use the wealth of information resources available today. Never before has there been so much information so readily available nor such high expectations for how much the individual will be able to accomplish by utilizing this information. The result is that people today need access to information everywhere, anytime. In June 1994, Microsoft announced a new product designed to meet these needs called Microsoft.RTM. Exchange.

The main concept behind Microsoft.RTM. Exchange is to provide a product that integrates E-mail, scheduling, electronic forms, document sharing, and other applications such as customer tracking to make it altogether easier to turn information into a business advantage. The result is that users can access, organize, and exchange a world of information, wherever they happen to be in the world--whether from the office, the home, or while traveling on the road. In essence, a main barrier to PC-based communication, namely, accessibility and sharing by multiple parties of up-to-the-minute information, has now been significantly reduced.

With the increased accessibility and sharing of information between multiple users, it is now more common than ever for such multiple users to simultaneously or in tandem work on shared data set objects, as for example word processing documents, spreadsheets, electronic forms, E-mail messages, graphics images or a host of other such data objects. With such shared use of data objects among multiple users of a computer network, there arises the need for each user to keep all other users of the same data object or the same set of data objects apprised of changes that are made locally by that user. This need gives rise to a process called replication of data, that is, transferring changes (e.g., creation of new data, modification of existing data or deletion of existing data) made locally at one server to a specified list of other remote or locally connected servers.

When data is replicated among several servers in a computer network, it is often undesirable to have each and every server contain a copy of each and every data set. If each server contained each and every data set, the message traffic needed to support replication of the data would eventually overwhelm the ability of the computer network to transfer such data. Thus, a network administrator typically selects certain servers on the network to have copies of certain data sets.

In deciding which servers should have copies of which data sets, an administrator typically considers such factors as load balancing, network topology, disk space, network bandwidth, replication latency, and frequency of access. An administrator will typically try to locate copies of the data sets in such a manner that the load on the network is balanced, and which will take advantage of plentiful network resources and minimize dependence on scarce network resources. Furthermore, factors such as replication latency, which represents the time needed for a change made to one copy of a data set to ripple through the network, should also be considered.

In deciding where to locate copies of data sets in a computer network, from time-to-time it typically becomes necessary to change the locations where copies of the data set reside. This can include, for example, adding a copy of a data set on a system which does not currently possess a copy of the data set, moving a copy of the data set from one system to another system, and/or removing a copy of the data set from a system. Whenever one of these actions are undertaken, care must be taken to avoid any inadvertent data loss.

Because of replication latency, when a change is made to a copy of a data set on one server, it will take a finite period of time before those changes propagate, via the replication process, to other servers also having a copy of the data set. Thus, once a change is made, if the copy of the data set is deleted before those changes can be successfully replicated across the computer network, those changes would be lost. Thus, it is important, especially when removing a copy of a data set, to avoid losing any changes which have been made to the local copy of the data set before the changes can be replicated to other servers in the network.

One method of preventing inadvertent data loss would be to delay removing a data set until sufficient time has past for all changes to be replicated across the computer network. For replication enterprises which have a fixed replication latency, such an approach may be feasible. However, most, if not all, replication methods in current use today have no fixed replication latency time. Replication latency is typically a complex function of many variables such as the number of servers with a copy of the data set, the present communication load on the network, the number of changes being made to each local copy of the data set, the network topology, the processing load on each individual server, and the number of data sets being replicated throughout the network. With replication latency depending on so many variables, it is virtually impossible to guarantee that replication latency will remain constant over time.

What is needed, therefore, are systems and methods for replica administration that preclude data loss. It would also be desirable that such systems and methods would be scalable to any number of servers in a network. The systems and methods should also work reliably to prevent data loss independent of a variety of factors such as the number of servers that have copies of the data set, the total number of data sets replicated across the network, the communication bandwidth available, and the frequency with which data sets are changed. Finally, it is preferred that the systems and methods prevent data loss without generating unneeded or unnecessary communication traffic on the network in order to efficiently utilize available communication bandwidth.

SUMMARY AND OBJECTS OF THE INVENTION

1. Glossary of Terms

In order to assist in more easily understanding the terminology used in the following detailed description and summary of the invention, the following definitions for key terms are provided:

Asynchronous store and forward replication: A process of replicating data throughout a network or enterprise by broadcasting locally made changes (e.g., creation of new data, modification of existing data, or deletion of existing data) to a specified list of servers (called replica nodes) which contain copies of the data. Communications in store and forward replication are one-way and there is no acknowledgment of receipt of messages containing the changes.

Backfill: A discovery based data recovery process by which changes held by other servers (called replica nodes) but not held locally are recovered so that the copy of the data (called a replica) held locally is the same as replicas held by other replica nodes.

Change number: A unique identifying code used to identify a particular change made to a particular copy of a data object or data set properties by a particular replica node.

Change range: A range of changes, identified by a minimum and maximum change number. The change range is inclusive of the minimum and maximum change number.

Change set: The set of change ranges that defines the changes available for a given replica of a data set on a given replica node. The change set contains changes made on the local replica node and changes to the data set received from other replica nodes through the replication process.

Data set: A set of one or more objects which can be replicated. In one sense a data set can be though of as a container with various data set properties which holds or stores data objects. A populated data set includes both the data objects and data set properties, while an unpopulated data set does not have any associated data objects and refers to the data set properties.

Data set list: A list of the data set properties for the data sets being replicated across the enterprise. In one sense a data set list can be thought of as a container which holds or stores data sets (as defined by their data set properties) in much the same way that a data set is a container that stores data objects. Thus, a data set is a container that holds data objects while a data set list is a container that holds data sets (the set of data sets).

Data set properties: A set of information used to describe or track key information about a data set including a name and/or ID value and the replica list for the data set. The data set properties can also contain other information such as a change number, and a time stamp indicating the time last modified.

Enterprise: The set of servers (or replica nodes) comprising the replication environment.

Replica: A local copy of a particular data set (one or more data objects) replicated on one or more replica nodes throughout the network.

Replica list: A list of all replica nodes on the network containing a replica of a data set. Each entry in the replica list also contains the replica state for each replica node and a time stamp indicating when the entry was last modified.

Replica node: A server or other location on the network where a copy of a data set (called a replica) resides.

Replica state: A state identifier used to indicate the current state of a replica node with respect to a particular data set. Such states can include "active" where the replica node is actively participating in the replication of the data set, "deleted" which indicates the replica node has deleted its copy of the data set, and one or more intermediate states indicating that the replica node is in the process of deleting its copy of the data set.

Site: A plurality of replica nodes in which each node is relatively similar in terms of cost to access data, as compared to the cost between sites. Cost is representative of factors such as the monetary cost to obtain data, the speed of obtaining data, and the reliability of obtaining data.

2. Brief Summary

The foregoing problems in the prior state of the art have been successfully overcome by the present invention, which is directed to a system and method for replica administration without data loss. The current system and method can be used with virtually any replication process. The preferred replication process, however, is an asynchronous store and forward replication process.

In a store and forward replication process, each server keeps track of locally made changes to a particular copy of a data set (sometimes referred to as a "replica") which contains one or more data objects. Each server periodically broadcasts the new locally made changes (since the last replication broadcast) to all other servers with a copy of the data set. The group of other servers also having a copy of the data set is kept on a "replica list." The changes are preferably broadcast in the form of updated copies of the changed data objects. This allows each server to update its local copy of the data set as changes are received by replacing the older data objects with the newer data objects. In essence, a store and forward replication process utilizes existing networking hardware as a transport system to deliver one way, unacknowledged messages between servers, much like E-mail messages are delivered between users of computer systems.

In addition to replicating data set objects, store and forward replication also replicates "data set properties." Data set properties describe and define a data set. Data set properties can include such information as a data set name and/or other identifying information, access privilege information such as a list of users which can access or change the contents and/or properties of the data set, a replica list which contains those replica nodes with a copy of the contents of the data set, and other information. Data set properties can be replicated independently from the data objects of the data set. By replicating data set properties to all or some of the replica nodes in the enterprise, those replica nodes will know what data sets are available throughout the enterprise and where copies of the data sets can be found.

In accordance with the present invention, each server has several states which indicate its participation in the replication process for a particular data set. These states are referred to as "replica states." For example, an "active" state can indicate that a server is actively participating in the replication of a data set. A "deleted" state can be used to indicate that a server has deleted its copy of the data set. In addition, each server can have one or more intermediate states to indicate that it is in the process of removing its local copy of the data set.

Each data set has a replica list property, containing the list of replica nodes, their replica state and a time last modified stamp indicating the time that the replica state was last modified. In this way, when the replication process replicates data set properties throughout the network, then servers will know the replica state of the other servers in the network for each data set.

In order to prevent data loss, a server that is going to remove its copy of a data set performs several steps. The first step is to initiate the removal process. This may be accomplished by setting the current replica state for the data set to one of the intermediate states described above. If data set properties, including the replica state, are replicated across the enterprise, this action will let other servers in the network know that its copy of the data set is in the process of being removed.

The next step is to terminate user access to the local copy of the data set. If the local copy of the data set is going to be removed, it is unwise to allow users to continue to access the data set. One reason to terminate user access to the data set is to prevent any new changes from being made to the data set during the removal process. If user access was not terminated, these changes may be lost if they occur immediately before removal of the data set. In addition, if continued access to the data set is allowed, when the data set is removed, users will simply see the data set disappear. This may leave them wondering what happened to the data set.

After terminating user access to the data set and initiating the removal process, the next step is to force replication of any changes which have been made to the local copy of the data set and which have not yet been sent to other servers in the network. After the changes are replicated, the server then verifies that the changes reside on at least one other server in the network. By forcing replication of any changes and then verifying that the changes actually reside on another server in the network, inadvertent data loss is prevented.

After the server verifies that all changes held locally are also held by at least one other server in the network, the local server can then delete its local copy of the data set without fear of data loss. After the local copy of the data set has been removed, the server can set its replica state for that data set to a deleted replica state for that data set. This informs other servers in the network that the local copy of the data set is no longer available on this server.

The present invention also includes mechanisms to handle special cases. For example, situations may arise where a server is unable to verify that its local changes are held by another server in the network. Such a situation may arise when an administrator is removing the only copy of a data set from the network or for any number of other reasons. Thus, the present invention includes a mechanism to allow an administrator to bypass the protections provided by the method described above. In one embodiment when such a situation arises, the data set may be left on the server and the replica state of the server may be left in one of the previously described intermediate states. If the data set is left on the server, no user will be able to access the data set but the data set remains on disk and so no data loss is incurred. Such an approach, however, leaves some disk space unreclaimed. Alternatively, embodiments within the present invention allow an administrator to bypass the verification step and force removal of a data set or return the server to the active replica state.

Embodiments within the scope of this invention also provide for an add function which adds a copy of a data set to a server. The add function first adds an empty data set and then fills the data set with data objects.

Finally, embodiments within the scope of the present invention also provide for a move operation which will move a data set from one server to another. In one embodiment, this move operation is accomplished by first adding a copy of the data set to the server that is to receive the data set and then initiating a remove process on the server that will no longer have the data set. The remove process may operate as described above.

Accordingly, it is a primary object of this invention to provide systems and methods for replica administration which prevent inadvertent data loss. Other objects of the present invention include: providing systems and methods for replica administration which allow an administrator to bypass safeguards and force removal of a data set without guaranteeing that inadvertent data loss will be prevented; providing systems and methods for replica administration which minimize the amount of communication traffic which is generated during removal of a data set; and providing systems and methods for replica administration that do not significantly degrade in performance when an increasingly large number of systems are added to the network.

Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other objects and features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.

BRIEF DESCRIPTION OF THE DRAWINGS

In order that the manner in which the above recited and other advantages and objects of the invention are obtained, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings in which:

FIG. 1 is a diagram representing a network which is logically completely connected;

FIG. 2 is a block diagram representing the relationship of one embodiment of the system and method of replica administration of the present invention to an associated replication process;

FIG. 3 is a state diagram illustrating the replica states of one preferred embodiment;

FIG. 4 is a flow diagram illustrating the processing which takes place in the delete pending state of one preferred embodiment;

FIG. 5 is a flow diagram illustrating the processing which takes place in the delete now state of one preferred embodiment;

FIG. 6 is a flow diagram illustrating the processing which takes place in the deleted state of one preferred embodiment; and

FIG. 7 is a flow diagram illustrating the processing that occurs when the active state of one preferred embodiment is entered.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The following invention is described by using flow diagrams to describe either the structure or the processing of certain preferred embodiments to implement the systems and methods of the present invention. Using the diagrams in this manner to present the invention should not be construed as limiting of its scope. The present invention contemplates both methods and systems for replica administration without data loss. The presently preferred embodiment of the system for replica administration without data loss comprises a general purpose computer. The systems and methods of the present invention, however, can also be used with any special purpose computer or other hardware system and all should be included within its scope.

Embodiments within the scope of the present invention also include articles of manufacture comprising program storage means having encoded therein program code means. Such program storage means can be any available media which can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such program storage means can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired program code means and which can be accessed by a general purpose or special purpose computer. Combinations of the above should also be included within the scope of program storage means.

Program code means comprises, for example, executable instructions and data which cause a general purpose computer or special purpose computer to perform a certain function or a group of functions.

1. Summary of Store and Forward Replication

The system and method for replica administration without data loss as disclosed herein can be utilized with any type of replication process. However, the systems and methods of the present invention do require some sort of replication process. The presently preferred type of replication process is a store and forward replication process.

Although store and forward replication does not form a specific part of the present invention, an understanding of the basics of store and forward replication is helpful in understanding the details of the present invention. For a detailed discussion of store and forward replication, see copending U.S. patent application Ser. No. 08/673,741, entitled "System and Method for Asynchronous Store and Forward Data Replication" (hereinafter referred to as the "Store and Forward Application"), which is incorporated herein by reference. Asynchronous store and forward replication, or simply store and forward replication, is designed to utilize existing network hardware, networking control software, and networking configurations as a transport system to deliver at least one-way, unacknowledged communications between systems in a replication enterprise. In the context of this application, networking hardware and any associated networking control software which performs this transport function will be referred to as the Message Transport Agent (MTA). One-way, unacknowledged communication means that the store and forward replication process delivers a message to be transferred to the MTA and does not receive feedback as to the success of the transfer. Primarily for efficiency reasons, the systems and methods that are the subject of this invention and the invention described in the copending Store and Forward Application have been designed with the presumption that no acknowledgement or feedback is required. The concepts disclosed in this application and in the copending Store and Forward Application, however, could be modified to use any status or information available from the MTA. Similarly, as previously described, the concepts of this invention do not depend on the type of replication process employed and virtually any type of replication process can be used. However, the store and forward replication process provides the presently preferred context of this invention.

Turning now to FIG. 1, an example of a network over which data is to be replicated is shown generally as 10. In this application, such a network will be referred to as a "replication enterprise" or simply an "enterprise." In a store and forward replication process, a given populated data set (data set properties with associated data objects), a copy of which is referred to as a "replica," and/or a given unpopulated data set (data set properties without associated data objects), is replicated at one or more locations in the enterprise. In FIG. 1, the locations where a replica or a copy of an unpopulated data set can reside are referred to as "replica nodes" and are shown as 12 and labeled A-F. The term "replica node" is preferred over the term "server" since "server" often implies a system which serves one or more desktop, laptop, or other computers. Replica nodes include not only servers in the traditional sense of the term, but also desktop, laptop, or any other system where a copy of a populated or unpopulated data set may reside. In the context of this invention, "replica" will be used to refer to a specific copy of a set of one or more data objects which are to be replicated as a unit across one or more replica nodes. The term is intended to be read broadly and encompasses any type or format of data to be replicated. The term "data set" is used to describe one or more data objects which are replicated as a unit and should be read broadly to refer to a unit of replication. The term "data object" should also be read broadly and includes data such as a data file, a spread sheet, a word processing document, or any other type of data. "Unpopulated data set" or "data set properties" refers to data sets without their associated data objects. The term "replica object" will be used to refer broadly to either a populated or unpopulated data set or to an individual data object or a data set property object. A replica object is thus a unit of replication.

In the enterprise, replica nodes may be grouped into "sites." A site is a plurality of replica nodes with relatively similar costs to access data. Replica nodes within a site are generally, but not necessarily, located in a relatively localized geographic area and have high speed connectivity between nodes, such as, for example, Local Area Network (LAN) connections. The cost to access data between sites is generally much greater than the cost to access data within a site. Site groupings are typically assigned by a system administrator. FIG. 1 shows two sites, designated 14a consisting of replica nodes A, B, and C, and 14b consisting of replica nodes D, E, and F.

Replica nodes are connected by physical network connections. In FIG. 1, the physical network connections 16 are illustrated by the solid arrows. As shown in FIG. 1, replica nodes 12 may not be fully connected by physical network connections 16. (Note that the site containing the A B C group is connected to the site containing the D E F group by only a single link.) For store and forward replication, however, all that is required is the physical connections be sufficient to provide a data flow path between each of the replica nodes. Furthermore, physical connections 16 may be of any type. For example, the physical connections between replica nodes A, B, and C may be a LAN or other high speed link while the connections between replica nodes D and B may be a slower dial up, Internet, Wide Area Network (WAN), or other long haul connection. All these physical network connections are some examples of networking means for connecting replica nodes in an enterprise.

By ensuring a data flow path between each of the replica nodes, the entire enterprise is logically fully connected even though physical connections are of arbitrary topology. In FIG. 1, the logical network connections forming the fully connected logical topology are illustrated by dashed arrows 18.

In a store and forward replication system, each replica node keeps track of all changes made locally to a replica object (either data objects or data set properties). Each replica node then periodically broadcasts new changes that have occurred since the last replication broadcast through the MTA to all other replica nodes having a copy of the replica object. Store and forward replication can be used to distribute both populated and unpopulated data sets. This is done by replicating the contents of data sets (data objects) and the properties that define data sets (data set properties). Data replication in a store and forward replication enterprise can be thought of as the distribution of copies of the contents of a container. In the case of a data set, the contents are the individual data objects that make up the data set and the replication system distributes changes made to the data objects. In the case of the data set list, the contents are the individual data set properties that define each data set.

The relationship of the data set list, the data sets, and data objects, can be illustrated as follows. Each replica node keeps a list of the data sets (whether populated or unpopulated) that it knows about. Usually every replica node in the replication enterprise knows about all data sets in the enterprise. The data set list can be illustrated as:

    ______________________________________
    Data Set List
    ______________________________________
    Data Set No. 1
    Data Set No. 2
    .cndot.
    .cndot.
    .cndot.
    Data Set No. n
    ______________________________________

    ______________________________________
    A              Active  T.sub.1
    D              Deleted T.sub.2
    G              Active  T.sub.3
    ______________________________________

    ______________________________________
    A              Active  T.sub.1
    D              Active  T.sub.4
    ______________________________________

    ______________________________________
    A              Active  T.sub.1
    D              Active  T.sub.4
    G              Active  T.sub.3
    ______________________________________