System and method for synchronizing database information

• US 6,539,381 B1
• Filed: 04/21/1999
• Issued: 03/25/2003
• Est. Priority Date: 04/21/1999
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Olds, Dale R., Izatt, Layne C., Prasad, Ranjan
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/296,687
• Time in Patent Office: 1,434 Days
• Field of Search: 707/8-10, 707/1, 707/200-205, 709/316
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method for synchronizing database information over a communications network distributed among a plurality of servers. The system allows each server to track the state of a replica on each of the servers, and changes to the servers are communicated between the servers along with their states. The states may be stored as an array of timestamps, the timestamps each indicating a time at which the replica on each server was updated. In a network wherein two servers (a first and third server) cannot communicate directly, a first network server transmits a change to an intermediate (a second) server including its state information. The second server transmits the change to the third server, and the third server updates its replica. The third server transmits its state information to the second server, and the timestamp information is conveyed to the first server. The state information of the third server may be transmitted to the second server during later updates of the third server'"'"'s replica. The first server, by receiving the third server'"'"'s state information, can determine that the change in replica information was performed on the third server. The synchronization system and method may be used to transmit changes, such as those involved in a partitioning operation.

Claims

1. A method for synchronizing replicas of at least a portion of a database, wherein each of the replicas is associated with a respective node and is further associated with a respective known state vector comprising information regarding a state of synchronization of that replica and a state of synchronization of the other replicas as perceived by that replica, and wherein each of the replicas is also associated with perceived state vectors, each of the perceived state vectors corresponding to a respective other one of the replicas and comprising information regarding a state of synchronization of the replica to which it is associated as perceived by the respective other one of the replicas, wherein a node associated with a replica receives a perceived state vector from a node associated with the other one of the replicas to which the perceived state vector corresponds, the method comprising:

comparing a known state vector associated with a first one of the replicas with perceived state vectors associated with the first one of the replicas to determine if the first one of the replicas includes a change that should be made to one of the other replicas;

if the change should be made to the one of the other replicas, sending the change and the known state vector associated with the first one of the replicas to a node associated with the one of the other replicas to which the change should be made;

making the change to the one of the other replicas to which the change should be made;

updating information regarding a state of synchronization in a known state vector associated with the one of the other replicas to which the change was made; and

storing the known state vector associated with the first one of the replicas in a perceived state vector corresponding to the first one of the replicas and associated with the one of the other replicas to which the change was made,

wherein a perceived state vector associated with the one of the other replicas to which the change was made and corresponding to a respective one of the other replicas comprises information regarding a state of synchronization of the one of the other replicas to which the change was made, as perceived by the respective one of the other replicas, and wherein the known state vector associated with the one of the other replicas to which the change was made can be compared with the perceived state vector associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.

2. The method according to claim 1, further comprising:

in response to the act of making the change included in the first one of the replicas to the one of the other replicas to which the change should be made, comparing the known state vector associated with the one of the other replicas to which the change was made with the perceived state vectors associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.

3. The method according to claim 1, wherein the act of comparing is in response to a change made to the first one of the replicas.

4. The method according to claim 1, wherein the act of comparing is performed in accordance with a policy.

5. The method according to claim 1, wherein the act of comparing is performed at a node associated with the first one of the replicas, and the acts of updating and storing are performed at the node associated with the one of the other replicas to which the change was made.

6. The method according to claim 1, wherein each of the state vectors comprises a plurality of unique identifiers, each of which being associated with a particular one of the replicas.

7. The method according to claim 1, wherein each of the state vectors comprises a plurality of timestamps.

8. The method according to claim 7, further comprising, in response to a change to one of the replicas, updating one of the timestamps in one of the known state vectors.

9. The method according to claim 7, wherein the act of comparing comprises comparing a timestamp in the known state vector associated with the first one of the replicas with a timestamp in the perceived state vectors associated with the first one of the replicas.

10. The method according to claim 1, wherein the act of updating information further comprises merging the known state vector associated with the first one of the replicas with the known state vector associated with the one of the other replicas to which the change was made.

11. The method according to claim 1, wherein the replicas each belong to a replica set.

12. The method according to claim 11, wherein each known state vector comprises information regarding a state of synchronization of its associated one of the replicas in the replica set and information regarding a state of synchronization of each of the other ones of the replicas in the replica set that are currently receiving updates.

13. The method according to claim 11, wherein each known state vector comprises information regarding a state of synchronization of its associated one of the replicas in the replica set and information regarding a state of synchronization of each of the other ones of the replicas in the replica set that are read/write replicas.

14. The method according to claim 1, wherein the change comprise a partition change.

15. A system for synchronizing replicas of at least a portion of a database, comprising:

a known state vector associated with each one of the replicas, each of the known state vectors comprising information regarding a state of synchronization of the associated one of the replicas and states of synchronization of other ones of the replicas as perceived by the associated one of the replicas;

perceived state vectors associated with each one of the replicas, wherein each of the perceived state vectors is associated with one of the replicas and corresponds to a respective other one of the replicas and comprises information regarding a state of synchronization of the one of the replicas to which it is associated as perceived by the respective other one of the replicas;

executable instructions operable to compare the known state vector associated with a first one of the replicas with perceived state vectors associated with the first one of the replicas to determine if the first one of the replicas includes a change that should be made to one of the other replicas;

executable instructions operable to send the change and the known state vector for the first one of the replicas to a node associated with the one of the other replicas if the change should be made to the one of the other replicas;

executable instructions operable to make the change to the one of the other replicas to which the change should be made;

executable instructions operable to update information regarding a state of synchronization in a known state vector associated with the one of the other replicas to which the change was made; and

executable instructions operable to store the known state vector for the first one of the replicas in a perceived state vector corresponding to the first one of the replicas and associated with the one of the other replicas to which the change was made,

wherein a perceived state vector associated with the one of the other replicas to which the change was made and corresponding to a respective one of the other replicas comprises information regarding a state of synchronization of the one of the other replicas to which the change was made, as perceived by the respective one of the other replicas, and wherein the known state vector associated with the one of the other replicas to which the change was made can be compared with the perceived state vector associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.

16. An apparatus capable of synchronizing replicas of at least a portion of a database, comprising:

a processor;

a memory system configured to store the replicas, wherein each of the replicas is associated with a known state vector comprising information regarding a state of synchronization of that replica and a state of synchronization of the other replicas as perceived by that replica, and wherein each of the replicas is also associated with perceived state vectors, each of the perceived state vectors corresponding to a respective other one of the replicas and comprising information regarding a state of synchronization of the replica to which it is associated as perceived by the respective other one of the replicas; and

a synchronization system configured to;

compare a known state vector associated with a first one of the replicas with perceived state vectors associated with the first one of the replicas to determine if the first one of the replicas includes a change that should be made to one of the other replicas;

send the change and the known state vector associated with the first one of the replicas to a node associated with the one of the other replicas if the change should be made to the one of the other replicas;

make the change to the one of the other replicas to which the change should be made;

update information regarding a state of synchronization in a known state vector associated with the one of the other replicas to which the change was made; and

store the known state vector associated with the first one of the replicas in a perceived state vector corresponding to the first one of the replicas and associated with the one of the replicas to which the change was made,

wherein a perceived state vector associated with the one of the other replicas to which the change was made and corresponding to a respective one of the other replicas comprises information regarding a state of synchronization of the one of the other replicas to which the change was made, as perceived by the respective one of the other replicas, and wherein the known state vector associated with the one of the other replicas to which the change was made can be compared with the perceived state vector associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.

17. A state matrix for use in synchronizing replicas of at least a portion of a database, comprising:

a known state vector associated with a first one of the replicas and comprising information regarding a state of synchronization of the first one of the replicas and states of synchronization of the other ones of the replicas as perceived by the first one of the replicas; and

perceived state vectors associated with the first one of the replicas, each of which perceived state vectors corresponding to a respective other one of the replicas and comprising information regarding a state of synchronization of the first one of the replicas as perceived by the respective other one of the replicas, wherein

the known state vector can be compared with the perceived state vectors to determine if the first one of the replicas includes a change that should be made to one of the other replicas;

if the change should be made to the one of the other replicas, the change and the known state vector can be sent to a node associated with the one of the other replicas;

the change to the one of the other replicas can be made;

information regarding a state of synchronization of the one of the other replicas to which the change was made can be updated in a known state vector of a state matrix associated with the one of the other replicas to which the change was made; and

the known state vector associated with the first one of the replicas can be stored in a perceived state vector corresponding to the first one of the replicas in the state matrix associated with the one of the other replicas to which the change was made,

wherein a perceived state vector of the state matrix associated with the one of the other replicas to which the change was made and corresponding to a respective one of the other replicas comprises information regarding a state of synchronization of the one of the other replicas to which the change was made, as perceived by the respective one of the other replicas, and wherein the known state vector of the state matrix associated with the one of the other replicas to which the change was made can be compared with the perceived state vector of the state matrix associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.

18. Computer readable medium comprising instructions for performing a method for synchronizing replicas of at least a portion of a database, wherein each of the replicas is associated with a known state vector comprising information regarding a state of synchronization of that replica and a state of synchronization of the other replicas as perceived by that replica, and wherein each of the replicas is also associated with perceived state vectors, each of the perceived state vectors corresponding to a respective other one of the replicas and comprising information regarding a state of synchronization of the replica to which it is associated as perceived by the respective other one of the replicas, the method comprising:

comparing a known state vector associated with a first one of the replicas with perceived state vectors associated with the first one of the replicas to determine if the first one of the replicas includes a change that should be made to one of the other replicas;

if the change should be made to the one of the other replicas, sending the change and the known state vector associated with the first one of the replicas to a node associated with the one of the other replicas to which the change should be made;

making the change to the one of the other replicas to which the change should be made;

updating information regarding a state of synchronization in a known state vector associated with the one of the other replicas to which the change was made; and

storing the known state vector associated with the first one of the replicas in a perceived state vector corresponding to the first one of the replicas and associated with the one of the other replicas to which the change was made,

wherein a perceived state vector associated with the one of the other replicas to which the change was made and corresponding to a respective one of the other replicas comprises information regarding a state of synchronization of the one of the other replicas to which the change was made, as perceived by the respective one of the other replicas, and wherein the known state vector associated with the one of the other replicas to which the change was made can be compared with the perceived state vector associated with the one of the other replicas to which the change was made to determine if the one of the other replicas to which the change was made includes a change that should be made to one of the replicas.