Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-07-01
2002-06-25
Oberley, Alvin E. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S170000
Reexamination Certificate
active
06412017
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to facilities for replicating data in a distributed system, and more particularly to an improved facility for urgently replicating data in a distributed network environment.
BACKGROUND OF THE INVENTION
In a distributed network environment, multiple copies of replicated data, such as multiple copies of files, objects, directory structures, programs or databases, are typically distributed throughout the network. For example, in a wide area network (WAN) comprised of multiple local area networks (LANs), a separate copy of replicated data may reside in at least one file server or workstation located on each of the LANs.
A benefit to having replicated data in the above-described distributed network includes facilitating access to the replicated data by each of the nodes on the network. Nodes may simply obtain the desired data locally on their LAN rather than seeking the data from another node on the WAN in a perhaps more costly and time-consuming manner. In addition, replicated data helps to distribute the load on any given node that would otherwise have to maintain the data and respond to all requests for such data from all other nodes on the network. A further benefit includes enhancing system reliability, e.g., no one node (which may fail) exclusively possesses access to required data. Databases, network directory services and groupware are typical products that take advantage of replication.
Since the replicated data may change and multiple copies of the replicated data are distributed throughout the network, replication facilities must typically employ some scheme for reconciling any differences and ensuring a certain amount of consistency between the replica set. A replica set is considered to have strong consistency if the changes to the data are reconciled simultaneously throughout the set at some ordained time. Weak consistency is a concept which allows the replicas to be moderately, yet tolerably, inconsistent at various times.
As can be appreciated, maintaining strong consistency generally requires the use of more resources, e.g., at least in terms of reduced available bandwidth. Moreover, strong consistency becomes more and more impractical, and at some point almost impossible, to guarantee as the numbers of replicas increase in a distributed system. This is mostly due to performance limitations, network partitioning, and the like. Consequently, most replicated systems implement some level of weak consistency.
An improved replication facility which provides a standardized interface for replication that can be used regardless of the underlying file system is described in commonly assigned U.S. patent application Ser. No. 08/181,704, now U.S. Pat. No. 5,588.147, the entire description found therein being incorporated herein by reference. For ease of understanding, the general replication topology described therein can be thought of as a graph of unidirectional edges where changes are transmitted from a source to a destination. Replication occurs pairwise and in one direction. In other words, the destination is responsible for originating a request for replication from the source. This technique is known as pulling, since the destination attempts to pull the data from the source.
In this facility, a cursor is maintained at the destination for each connection (edge) it has to a source from which it pulls data. The cursors track the last change information received by the destination from the respective sources. Using a cursor, when a destination requests updates from a given source, the source provides the destination with 1) a list of objects (or other data structures) that have changed and 2) the type of change which has occurred for each object since the last replication to that destination. To avoid unnecessary transmission, the source also filters from this list any change items which it knows were originated or propagated by the requesting destination. The source then updates the cursor maintained at the destination based upon the replication information provided during that replication cycle.
After the list of changes is received at the destination, each object identified in the list attempts to reconcile itself with its counterpart object at the source using a class-specific reconciler. Class specific reconcilers allow each class of object to define for itself what it means to be consistent with other replica objects in its class. If a class specific reconciler is not available for a given data structure, e.g., a text file, then a default reconciler is used, which utilizes, for example, a “last writer wins” algorithm.
Because the above replication facility is “pull” driven by the destination, replication data is only sent to the destination at discrete intervals of time, usually set according to policies defined by the network system administrator and/or the system administrators of the source and destination. Moreover, to conserve network resources (such as available bandwidth), the discrete intervals of time are often set so as to provide only weak consistency.
As a result of the delay between time intervals, a relatively substantial amount of time may occur between replications. Although some delay is ordinarily acceptable with many types of replicated data, significant potential problems may arise with other types of data structures. In particular, changes to certain classes of objects such as password or access rights changes to user objects cannot be unduly delayed if system security is to be maintained.
As discussed above, the solution of decreasing the time interval between replications is not always practicable or even possible. Other solutions have been considered such as 1) tracking the differences between changed data structures to reduce the amount of data that needs to be transmitted during replication, i.e., data logging, or 2) expediting the replication of certain objects. However, such prior art solutions have required that the replicas possess both substantial knowledge of the complete replication topology and/or intimate knowledge of the operating environment of the other replicas. In other words, the replicas need to possess knowledge and/or assurance that all replicas are of similar implementation, e.g., that the replicas have been implemented on uniform homogeneous object sets thereby obviating the above difficulties. As such, these solutions are not amenable to a distributed system wherein the replicas may have different file systems and/or many object types. Similarly, objects created by third parties cannot be easily replicated unless those objects are created with specific knowledge of the topology and file systems in which they may be replicated.
OBJECTS AND SUMMARY OF THE INVENTION
Accordingly, a primary objective of the present invention is to provide a system and method of efficiently replicating data objects in a distributed system of replicas.
In accomplishing that objective, it is an aim of the invention to provide a replication facility that maintains incremental differencing information and replicates the differencing information upon a request for replication.
It is also an objective of the invention to provide a replication facility that enables the expedited replication of certain data objects deemed urgent.
It is a related objective to provide a replication facility wherein an object may initiate its propagation to other replicas in the system.
Another objective of the invention is to provide a system and method for replicating objects in an object-oriented environment.
Still another objective of the invention is to provide a system and method for replicating objects wherein any object can be replicated throughout one or more replicas in the system without the need for the object to have knowledge of the replication topology or the operating environment.
It is a related objective to provide a replication facility that is extensible and replicates objects independent of the type of file systems used to store those objects.
Briefly, the present invention provides a s
Contorer Aaron M.
Miller Arnold S.
Misra Pradyumna K.
Raman Balan S.
Seaman Michael R. C.
Lao Sue
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
Oberley Alvin E.
LandOfFree
Urgent replication facility does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Urgent replication facility, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Urgent replication facility will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2967248