The dissemination of information to multiple users can be classified into two general categories. In one category, the information is managed at a central facility that is accessed by the users when they require the information. The information may be resident on multiple information servers that are geographically remote from one another, but are accessed through a central point by the users. In this type of system, the information is not replicated, except when a user manually saves a document in local storage, or the data is temporarily stored in cache memory as part of the information retrieval mechanism. In this type of system, only one master copy of the information exists, and therefore control over its content is easily maintained. An example of this type of information dissemination system is an Internet website.
An inherent requirement of this category of system is that the user must be connected to the central facility in order to access the information. As a result, a disconnected user, e.g. an employee traveling on an airplane, is limited in terms of the ability to obtain the information when needed. Even when a user is connected, excessive load on a server or network performance issues, such as low bandwidth or high latency, can result in inefficient access. Accordingly, the second general type of information dissemination system employs data replication. In this type of system, copies of the information are disseminated to, and stored at, multiple nodes. Once the copy has been stored at a node, the user is no longer required to be connected to the information source in order to access the information. Although advantageous from this standpoint, replication systems present a number of other issues that must be addressed. Foremost among these is the need to maintain consistency among the replicated copies of the information at the nodes. If changes are made to the information, these changes need to be disseminated to all of the nodes. Accordingly, replication systems employ different approaches for synchronizing the information among the multiple nodes.
One approach employs a single master version of the information, which is disseminated from a central source to replicas on remote devices that form the local nodes. The data flow is in one direction only, from the central master to the remote devices. In this type of system, all write operations occur at the master, and the users at the remote devices have read-only privileges. The set of information that is stored on each remote device is regarded as being no larger and no older than the central master.
When the number of content recipients is large, the central source can become overloaded. Furthermore, there is the possibility that a large number of nodes might be connected to the central source by a common network that can experience bandwidth bottlenecks. To address these types of performance issues, hyperdistribution systems might be desirable. In this type of arrangement, the information content is disseminated from the central source to a plurality of intermediate distribution points, and from there to the ultimate recipients at the remote locations.
Alternatively, a multiple master approach may be desirable, where users at the remote devices have the ability to modify the data. In this approach the potential exists for conflicting versions of the data at different nodes. Some multi-master systems address this issue by utilizing conflict avoidance, whereas others employ conflict resolution. To achieve conflict avoidance, a single user or application must be able to lock access to a data object before a write operation takes place, so that plural simultaneous edits cannot occur. To obtain a lock, however, connection to a resource which manages the locks is necessary. Hence, conflict avoidance is most practical in systems where the modifications are relatively infrequent.
In contrast, conflict resolution systems permit multiple simultaneous edits to occur, and conflicts are reconciled afterward. One type of dissemination system that is capable of resolving conflicts employs hub-and-spoke synchronization. This type of synchronization is commonly found, for example, in personal information management systems, in which mobile users are able to reconcile calendar and contact information with a single point of control. In this arrangement, each user device, e.g. personal digital assistant, carries a subset of the data in a central reference repository. When a device is connected to the central repository, its data set is synchronized with the reference data set. An example of this type of system is disclosed in U.S. Pat. No. 6,295,541. In these types of systems, the central repository functions as a clearinghouse for conflict resolution. Typically, immediate resolution is provided during synchronization, for example on the basis of time stamps. The business logic associated with this approach assumes that the individual who is performing the synchronization is the best person to resolve conflicts that arise during the synchronization. The conflict resolution process involves replacement of the older version of the information with the newer version, i.e., the prior version ceases to exist after conflict resolution.
An alternative to the hub-and-spoke arrangement is a peer-to-peer network, in which no single device functions as a central master. In this system, any device can synchronize with any other device at any time. This type of arrangement may be more suited to operations such as team collaboration. However, conflicting data entries can appear and be resolved many times, as disparate versions of the information propagate independently through the network and collide at various locations. Unlike hub-and-spoke mechanisms, there is no single valid version of the information, with respect to which the data set on a given device can be considered to be merely out of date.
Various combinations of these systems might also exist. For example, a project that employs hub-and-spoke synchronization for collaboration might also require hyperdistribution from a publisher. As a further extension of this arrangement, an object from a publisher might need to be identified with a corresponding object on the user's devices, and a workflow mechanism might allow each user to accept or postpone acceptance of any revisions to that object. As another example, a handheld device might be slaved via hub-and-spoke synchronization to a laptop, that also participates in peer-to-peer synchronization with other laptops.
Many data replication systems are based on a model that assumes that there is only one correct version of a data object at any given time. To assure a high degree of consistency among the copies of that data object, there is an implicit requirement that the nodes connect to one another on a frequent basis, so that the amount of revision to a data object between updates is relatively small. Thus, in a hub-and-spoke system, for example, since all information is expected to flow through the hub, frequent connections along the links that constitute the spokes are formed.
When there is no central hub for conflict resolution, an order-dependent approach can be employed to resolve the conflicts, but this can lead to unpredictable results. For instance, if node A is synchronized with node B, and then node B is synchronized with node C, one version of the data may be generated, whereas if node A is synchronized with node C and then node B is synchronized with node C, a different version may result.
It may be preferable to utilize an order-independent approach that allows business logic rules to be enforced in a way that provides more consistent results. If resolution is to be accomplished immediately, however, the business logic rules may have to be somewhat limited and/or restrictive.
It is an objective of the present invention to provide a framework for data replication that employs a different model to support relatively long periods of disconnection, and yet is compatible with each of the various dataflow techniques for replication described previously.