US6539381B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for synchronizing database information
Assignee: RPX Corp
•
Filing: 1999-04-21
•
Granted: 2003-03-25
•
Expires: 2019-04-21
Abstract
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.
Inventors
- 👤 Ranjan Prasad
- 👤 Layne C. Izatt
- 👤 Dale R. Olds
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 02:56
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/27; G06F16/273; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
452 words
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.
Claim 2
Independent Claim
452 words
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.
Claim 3
Dependent Claim
105 words
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.
Claim 4
Dependent Claim
26 words
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.
Claim 5
Dependent Claim
19 words
The method according to claim 1 , wherein the act of comparing is performed in accordance with a policy.
Claim 6
Dependent Claim
51 words
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.
Claim 7
Dependent Claim
31 words
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.
Claim 8
Dependent Claim
18 words
The method according to claim 1 , wherein each of the state vectors comprises a plurality of timestamps.
Claim 9
Dependent Claim
31 words
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.
Claim 10
Dependent Claim
45 words
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.
Claim 11
Dependent Claim
47 words
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.
Claim 12
Dependent Claim
16 words
The method according to claim 1 , wherein the replicas each belong to a replica set.
Claim 13
Dependent Claim
55 words
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.
Claim 14
Dependent Claim
54 words
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.
Claim 15
Dependent Claim
14 words
The method according to claim 1 , wherein the change comprise a partition change.
Claim 16
Independent Claim
445 words
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.
Claim 17
Independent Claim
445 words
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.
Claim 18
Independent Claim
420 words
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.
Claim 19
Independent Claim
420 words
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.
Claim 20
Dependent Claim
429 words
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.
Claim 21
Dependent Claim
429 words
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.
Claim 22
Dependent Claim
420 words
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.
Claim 23
Dependent Claim
420 words
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.
References Cited (Backward Citations)
EP0702497A2
Cited
US5832487A
Cited
US5596574A
Cited
US5765171A
Cited
US6098078A
Cited
US6233623B1
Cited
US5787247A
Cited
US6021118A
Cited
US6065017A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-24 | 2006-09-23 | 2007-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-24 | 2010-09-23 | 2011-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-24 | 2014-09-23 | 2015-03-25 | $7700.00 | Window Closed / Lapsed |