Collision avoidance in bidirectional database replication
First Claim
1. A method of avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are ready to be committed, but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the method comprising:
- (a) the transaction transmitter of an originating node sending selected transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
b) pausing each transaction being executed in a database of an originating node prior to a commit operation for the transaction;
(c) entering into the table at the originating node, indicia of the initiated transactions that are ready to be committed but that are not yet committed, and assigning a ready to commit token to the transaction;
(d) the transaction transmitter at the originating node sending the ready to commit tokens in the table of the originating node to the one or more other nodes;
(e) determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared for a commit operation for the transactions corresponding to each received ready to commit tokens, and, if so, the transaction transmitter in each of the other nodes sends back the ready to commit tokens to the respective originating node; and
(f) executing the commit operation of the transaction in the database of the originating node only upon receipt from each of the other nodes in the system of the ready to commit token originally sent from the originating node for the transaction, wherein the commit operation for each transaction in the system is paused so as to allow all of the nodes in the system to prepare for the commit and thereby avoid collisions at all of the nodes in the system.
7 Assignments
0 Petitions
Accused Products
Abstract
A bidirectional database replication system includes a plurality of nodes. Each transaction at an originating node is paused prior to a commit operation. Ready to commit tokens are sent to the other nodes in the system to determine if the other nodes are prepared for the commit operation for the paused transaction. If all of the ready to commit tokens properly return to the originating node from the other nodes, thereby indicating that the other nodes are prepared for the commit operation, then the transaction is commited. For lengthy transactions, ready to sync tokens are assigned at one or more predesignated intermediate points in the transaction, and propagate throughout the system in a similar manner. The transaction continues to execute as long as all ready to sync tokens properly return to the originating node. The pause-before-commit and sync point schemes are used to avoid collisions at any of the nodes.
114 Citations
42 Claims
-
1. A method of avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are ready to be committed, but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the method comprising:
-
(a) the transaction transmitter of an originating node sending selected transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
b) pausing each transaction being executed in a database of an originating node prior to a commit operation for the transaction;
(c) entering into the table at the originating node, indicia of the initiated transactions that are ready to be committed but that are not yet committed, and assigning a ready to commit token to the transaction;
(d) the transaction transmitter at the originating node sending the ready to commit tokens in the table of the originating node to the one or more other nodes;
(e) determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared for a commit operation for the transactions corresponding to each received ready to commit tokens, and, if so, the transaction transmitter in each of the other nodes sends back the ready to commit tokens to the respective originating node; and
(f) executing the commit operation of the transaction in the database of the originating node only upon receipt from each of the other nodes in the system of the ready to commit token originally sent from the originating node for the transaction, wherein the commit operation for each transaction in the system is paused so as to allow all of the nodes in the system to prepare for the commit and thereby avoid collisions at all of the nodes in the system. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
(g) locking the row in the database associated with the transaction at each node in the system, wherein the return of the ready to commit token at the originating node from the other nodes in the system indicates that the corresponding rows in all of the replicated databases are locked and that the transaction may be committed without a possibility of a collision.
-
-
5. The method of claim 1 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, and in step (c), the ready to commit token is entered into the audit trail at the originating node, and in step (d), the transaction transmitter at the originating node sends the ready to commit tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
6. The method of claim 1 wherein step (c) further comprises associating a flag for each transaction in the table that is ready to be committed, wherein the flag has a first state when the ready to commit token for the transaction has not yet been returned from all of the other nodes, and the flag has a second state when the ready to commit token for the transaction has been returned from all of the other nodes, the system allowing the transaction to be committed when the flag becomes changed from the first state to the second state.
-
7. The method of claim 1 further comprising:
(g) deleting any table entries when the ready to commit token for the transaction has been returned from all of the other nodes and the commit operation for the associated transaction has been executed.
-
8. The method of claim 1 wherein step (e) further comprises comparing the sequence number of any received ready to commit tokens to an expected sequence number to determine if the node has previously received the transaction steps or operations corresponding to the transaction of the ready to commit token, and thus is prepared for a commit operation.
-
9. An article of manufacture for avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are ready to be committed, but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the article of manufacture comprising a computer-readable medium holding computer-executable instructions for performing a method comprising:
-
(a) the transaction transmitter of an originating node sending selected transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
(b) pausing each transaction being executed in a database of an originating node prior to a commit operation for the transaction;
(c) entering into the table at the originating node, indicia of the initiated transactions that are ready to be committed but that are not yet committed, and assigning a ready to commit token to the transaction;
(d) the transaction transmitter at the originating node sending the ready to commit tokens in the table of the originating node to the one or more other nodes;
(e) determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared for a commit operation for the transactions corresponding to each received ready to commit tokens, and, if so, the transaction transmitter in each of the other nodes sends back the ready to commit tokens to the respective originating node; and
(f) executing the commit operation of the transaction in the database of the originating node only upon receipt from each of the other nodes in the system of the ready to commit token originally sent from the originating node for the transaction, wherein the commit operation for each transaction in the system is paused so as to allow all of the nodes in the system to prepare for the commit and thereby avoid collisions at all of the nodes in the system. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
(g) locking the row in the database associated with the transaction at each node in the system, wherein the return of the ready to commit token at the originating node from the other nodes in the system indicates that the corresponding rows in all of the replicated databases are locked and that the transaction may be committed without a possibility of a collision.
-
-
13. The article of manufacture of claim 9 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, and in step (c), the ready to commit token is entered into the audit trail at the originating node, and in step (d), the transaction transmitter at the originating node sends the ready to commit tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
14. The article of manufacture of claim 9 wherein step (c) further comprises associating a flag for each transaction in the table that is ready to be committed, wherein the flag has a first state when the ready to commit token for the transaction has not yet been returned from all of the other nodes, and the flag has a second state when the ready to commit token for the transaction has been returned from all of the other nodes, the system allowing the transaction to be committed when the flag becomes changed from the first state to the second state.
-
15. The article of manufacture of claim 9 wherein the computer-executable instructions perform a method further comprising:
(g) deleting any table entries when the ready to commit token for the transaction has been returned from all of the other nodes and the commit operation for the associated transaction has been executed.
-
16. The article of manufacture of claim 9 wherein step (e) further comprises comparing the sequence number of any received ready to commit tokens to an expected sequence number to determine if the node has previously received the transaction steps or operations corresponding to the transaction of the ready to commit token, and thus is prepared for a commit operation.
-
17. An apparatus for avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are ready to be committed, but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the apparatus comprising:
-
(a) a transaction transmitter of an originating node which sends selected transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
(b) means for pausing each transaction being executed in a database of an originating node prior to a commit operation for the transaction;
(c) means for entering into the table at the originating node, indicia of the initiated transactions that are ready to be committed but that are not yet committed, and assigning a ready to commit token to the transaction, the transaction transmitter at the originating node sending the ready to commit tokens in the table of the originating node to the one or more other nodes;
(d) means for determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared for a commit operation for the transactions corresponding to each received ready to commit tokens, and, if so, the transaction transmitter in each of the other nodes sends back the ready to commit tokens to the respective originating node; and
(e) means for executing the commit operation of the transaction in the database of the originating node only upon receipt from each of the other nodes in the system of the ready to commit token originally sent from the originating node for the transaction, wherein the commit operation for each transaction in the system is paused so as to allow all of the nodes in the system to prepare for the commit and thereby avoid collisions at all of the nodes in the system. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
(f) means for locking the row in the database associated with the transaction at each node in the system, wherein the return of the ready to commit token at the originating node from the other nodes in the system indicates that the corresponding rows in all of the replicated databases are locked and that the transaction may be committed without a possibility of a collision.
-
-
21. The apparatus of claim 17 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, the ready to commit token is entered into the audit trail at the originating node, and the transaction transmitter at the originating node sends the ready to commit tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
22. The apparatus of claim 17 further comprising:
(f) a flag associated with each transaction in the table that is ready to be committed, wherein the flag has a first state when the ready to commit token for the transaction has not yet been returned from all of the other nodes, and the flag has a second state when the ready to commit token for the transaction has been returned from all of the other nodes, the system allowing the transaction to be committed when the flag becomes changed from the first state to the second state.
-
23. The apparatus of claim 17 further comprising:
(f) means for deleting any table entries when the ready to commit token for the transaction has been returned from all of the other nodes and the commit operation for the associated transaction has been executed.
-
24. The apparatus of claim 17 wherein the means for determining further comprises means for comparing the sequence number of any received ready to commit tokens to an expected sequence number to determine if the node has previously received the transaction steps or operations corresponding to the transaction of the ready to commit token, and thus is prepared for a commit operation.
-
25. A method of avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the method comprising:
-
(a) the transaction transmitter of an originating node sending selections transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
(b) entering into the table at the originating node, indicia of the initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and assigning a ready to sync token to the transaction at each of the predesignated intermediate points;
(c) the transaction transmitter at the originating node sending the ready to sync tokens in the table of the originating node to the one or more other nodes;
(d) determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared to properly process the transaction up to the intermediate point associated with the respective ready to sync token, and, if so, the transaction transmitter in each of the other nodes sends back the ready to sync tokens to the respective originating node; and
(e) stopping the execution of a transaction in the system if the originating node fails to receive back a ready to sync token from at least one of the other nodes in the system for any of the predesignated intermediate points, wherein the transaction continues to execute as long as all ready to sync tokens properly return to the originating node, thereby indicating that no collisions should occur at any of the nodes in the system up to the most recent intermediate point in the transaction. - View Dependent Claims (26, 27, 28)
(f) if the execution of a transaction is stopped, restarting the transaction at the beginning of the predesignated intermediate point associated with the ready to sync token that failed to properly return from a node.
-
-
27. The method of claim 26 wherein the predesignated intermediate points occur at every N transaction steps or operations.
-
28. The method of claim 26 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, and in step (c), the ready to sync token is entered into the audit trail at the originating node, and in step (d), the transaction transmitter at the originating node sends the ready to sync tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
29. An article of manufacture for avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the article of manufacture comprising a computer-readable medium holding computer-executable instructions for performing a method comprising:
-
(a) the transaction transmitter of an originating node sending selections transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
(b) entering into the table at the originating node, indicia of the initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and assigning a ready to sync token to the transaction at each of the predesignated intermediate points;
(c) the transaction transmitter at the originating node sending the ready to sync tokens in the table of the originating node to the one or more other nodes;
(d) determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared to properly process the transaction up to the intermediate point associated with the respective ready to sync token, and, if so, the transaction transmitter in each of the other nodes sends back the ready to sync tokens to the respective originating node; and
(e) stopping the execution of a transaction in the system if the originating node fails to receive back a ready to sync token from at least one of the other nodes in the system for any of the predesignated intermediate points, wherein the transaction continues to execute as long as all ready to sync tokens properly return to the originating node, thereby indicating that no collisions should occur at any of the nodes in the system up to the most recent intermediate point in the transaction. - View Dependent Claims (30, 31, 32)
(e) if the execution of a transaction is stopped, restarting the transaction at the beginning of the predesignated intermediate point associated with the ready to sync token that failed to properly return from a node.
-
-
31. The article of manufacture of claim 29 wherein the predesignated intermediate points occur at every N transaction steps or operations.
-
32. The article of manufacture of claim 29 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, and in step (c), the ready to sync token is entered into the audit trail at the originating node, and in step (d), the transaction transmitter at the originating node sends the ready to sync tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
33. An apparatus for avoiding collisions in a bidirectional database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a table that stores indicia of initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and (iii) a transaction transmitter, each transaction being one or more transaction steps or transaction operations, the apparatus comprising:
-
(a) a transaction transmitter of an originating node which sends selected transactions posted to the database of the originating node to one or more other nodes for replication at the one or more other nodes;
(b) means for entering into the table at the originating node, indicia of the initiated transactions that are at one or more predesignated intermediate points in the transaction but are not yet committed, and assigning a ready to sync token to the transaction at each of the predesignated intermediate points, the transaction transmitter at the originating node sending the ready to sync tokens in the table of the originating node to the one or more other nodes;
(c) means for determining at each of the one or more other nodes whether the database at the one or more other nodes is prepared to properly process the transaction up to the intermediate point associated with the respective ready to sync token, and, if so, the transaction transmitter in each of the other nodes sends back the ready to sync tokens to the respective originating node; and
(d) means for stopping the execution of a transaction in the system if the originating node fails to receive back a ready to sync token from at least one of the other nodes in the system for any of the predesignated intermediate points, wherein the transaction continues to execute as long as all ready to sync tokens properly return to the originating node, thereby indicating that no collisions should occur at any of the nodes in the system up to the most recent intermediate point in the transaction. - View Dependent Claims (34, 35, 36)
(e) means for restarting the transaction at the beginning of the predesignated intermediate point associated with the ready to sync token that failed to properly return from a node if the execution of a transaction is stopped.
-
-
35. The apparatus of claim 33 wherein the predesignated intermediate points occur at every N transaction steps or operations.
-
36. The apparatus of claim 33 wherein each node further comprises (iv) an audit trail connected to the database and to the table, the audit trail containing all transactions posted to the database and all table entries, wherein the transaction transmitter sends selected audit trail entries to the one or more nodes, and the ready to sync token is entered into the audit trail at the originating node, and the transaction transmitter at the originating node sends the ready to sync tokens in the audit trail that were obtained from the table of the originating node to the one or more other nodes.
-
37. A method of replicating data in a database replication system including a source database and a target database, each transaction being one or more transaction steps or transaction operations, the method comprising:
-
(a) sending to the target database any transaction steps or operations that are received and posted at the source database, the transaction steps or operations that are received and posted at the source database thereby being replicated to the target database;
(b) pausing each transaction being executed in the source database prior to a commit operation for the transaction, (c) assigning a ready to commit token to the transaction;
(d) sending the ready to commit token to the target database only after all transaction steps or operations prior to the commit operation for the transaction have been posted to the source database;
(e) determining whether the target database is prepared for a commit operation for the transaction corresponding to the ready to commit token, and, if so, sending back the ready to commit token to the source database; and
(f) executing a commit operation at the source database for a transaction only upon receipt from the target database of the ready to commit token originally sent from the source database for the respective transaction, wherein the commit operation for each transaction in the system is paused so as to allow the source and the target database to prepare for the commit. - View Dependent Claims (38, 39)
wherein step (a) further comprises, sending to the target database any transaction steps or operations other than commit operations that are received and posted at the source databases; - the method further comprising;
(g) sending to the target database any commit operations posted to the source database for replication and posting therein.
-
-
40. An apparatus for replicating data in a database replication system including a source database and a target database, each transaction being one or more transaction steps or transaction operations, the apparatus comprising:
-
(a) means for sending to the target database any transaction steps or operations that are received and posted at the source database, the transaction steps or operations that are received and posted at the source database thereby being replicated to the target database;
(b) means for pausing each transaction being executed in the source database prior to a commit operation for the transaction;
(c) means for assigning a ready to commit token to the transaction;
(d) means for sending the ready to commit token to the target database;
(e) means for determining whether the target database is prepared for a commit operation for the transaction corresponding to the ready to commit token, and, if so, sending back the ready to commit token to the source database; and
(f) means for executing a commit operation at the source database for a transaction only upon receipt from the target database of the ready to commit token originally sent from the source database for the respective transaction, wherein the commit operation for each transaction in the system is paused so as to allow the source and the target database to prepare for the commit. - View Dependent Claims (41, 42)
wherein the means for sending to the target database, sends any transaction steps or operations other than commit operations that are received and posted at the source database prior to any pausing operation; and
also sendsto the target database any commit operations posted to the source database for replication and posting therein.
-
Specification