Collision avoidance in bidirectional database replication

• US 6,662,196 B2
• Filed: 03/16/2001
• Issued: 12/09/2003
• Est. Priority Date: 03/16/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: ITI Limited (Government of India)
• Inventors: Holenstein, Bruce D., Holenstein, Paul J., Strickler, Gary E.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): GODDARD, BRIAN D
• Application Number:
  US09/810,674
• Publication Number:
  US 20030187884A1
• Time in Patent Office: 998 Days
• Field of Search: 707/201, 707/202, 707/204, 707/8, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

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.

2. The method of claim 1 wherein step (d) further comprises the transaction transmitter at the originating node sending transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein.

3. The method of claim 2 wherein each node further comprises (iv) a local application program that controls the progression of the transaction with respect to only its own node, and the transaction transmitters at each node send transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein independent of the local application program.

4. The method of claim 2 further comprising:

(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.

10. The article of manufacture of claim 9 wherein step (d) further comprises the transaction transmitter at the originating node sending transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein.

11. The article of manufacture of claim 10 wherein each node further comprises (iv) a local application program that controls the progression of the transaction with respect to only its own node, and the transaction transmitters at each node send transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein independent of the local application program.

12. The article of manufacture of claim 10 wherein the computer-executable instructions perform a method further comprising:

(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.

18. The apparatus of claim 17 wherein the transaction transmitter at the originating node also sends transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein.

19. The apparatus of claim 18 wherein each node further comprises (iv) a local application program that controls the progression of the transaction with respect to only its own node, and the transaction transmitters at each node send transactions posted to the originating database to the databases at the one or more other nodes for replication and posting therein independent of the local application program.

20. The apparatus of claim 18 further comprising:

(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.

26. The method of claim 25 further comprising:

(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.

30. The article of manufacture of claim 29 wherein the computer-executable instructions perform a method further comprising:

(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.

34. The apparatus of claim 33 further comprising:

(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.

38. The method of claim 37 wherein both the source and the target database can both independently receive and post transactions and replicate the transactions to the other database.

39. The method of claim 37 wherein the transaction associated with a ready to commit token is posted to the source database upon receipt of the respective ready to commit token at the source database,

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.

41. The apparatus of claim 40 wherein both the source and the target database can both independently receive and post transactions and replicate the transactions to the other database.

42. The apparatus of claim 40 wherein the transaction associated with a ready to commit token is posted to the source database upon receipt of the respective ready to commit token at the source database:

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 sends

to the target database any commit operations posted to the source database for replication and posting therein.