Collision avoidance in database replication systems

• US 7,103,586 B2
• Filed: 03/29/2002
• Issued: 09/05/2006
• Est. Priority Date: 03/16/2001
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Gravic Incorporated
• Inventors: Holenstein, Bruce D., Holenstein, Paul J., Strickler, Gary E.
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/112,129
• Publication Number:
  US 20020133507A1
• Time in Patent Office: 1,621 Days
• Field of Search: 707 1- 10, 707200-206, 707100-1041, 714/7, 714/74.8, 714/20, 710/242, 218/101, 709/205, 134/100.1, 711/129, 370/410
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2064 while ensuring consistency
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 11/2076 Synchronous techniques
• CPC Class Codes: G06F 11/2079 Bidirectional techniques
• 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 2201/855 Details of asynchronous mirroring using a journal to transfer not-yet-mirrored changes
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Database replication systems replicate blocks of transaction steps or operations with synchronous replication, and perform dual writes with queuing and blocking of transactions. Tokens are used to prepare a target database for replication from a source database and to confirm the preparation. Database replication systems switch between a synchronous replication mode and an asynchronous replication mode, and then back to a synchronous replication mode, based on detection of selected events.

Claims

1. A method of replicating data associated with a plurality of transactions in a replication system including a plurality of nodes connected via communication media in a topology, each node including a database, the method comprising:

(a) replicating the data from an originating node to one or more other nodes, each transaction being one or more transaction steps or transaction operations; and

(b) pausing each transaction that is requested to be executed in the database at an originating node prior to a first I/O operation for the transaction upon detection that synchronization between the database at the originating node and the database at one or more of the other nodes cannot be ensured.

2. The method of claim 1 wherein the system operates in a synchronous data replication mode when synchronization between the database at the originating node and the database at one or more of the other nodes can be ensured, the method further comprising:

(c) switching the system operation to an asynchronous data replication mode upon detection that synchronization between the database at the originating node and the database at one or more of the other nodes cannot be ensured.

3. The method of claim 2 wherein during the synchronous data replication mode,

(i) pausing each transaction being executed in the database at the originating node prior to a commit operation for the transaction,

(ii) assigning a ready to commit token to the transaction,

(iii) sending the ready to commit token to the one or more other nodes,

(iv) determining at the one or more other nodes whether the respective databases are 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 originating node, and

(v) executing a commit operation at the database of the originating node only upon receipt from at least one of other nodes of the ready to commit tokens originally sent from the originating node.

4. The method of claim 3 wherein token latency is the time it takes for a newly generated ready to commit token to travel from the end of a transaction queue at the originating node to the beginning of a replay queue at one of the other nodes, the method further comprising:

(d) restoring the synchronous replication mode when it is detected that synchronous replication can be ensured again and token latency becomes less than a predetermined time value.

5. The method of claim 3 wherein the commit operation in step (v) is performed only upon receipt from each of the one or more the other nodes of the ready to commit tokens originally sent from the originating node.

6. The method of claim 2 further comprising:

(d) restoring the synchronous replication mode upon detection that synchronization between the database at the originating node and the database at one or more of the other nodes can be ensured again.

7. The method of claim 1 wherein each node includes a replication engine and a queue of transactions that were posted to the database at the respective node, the replication engine at each node synchronizing the database at the originating node to one or more of the databases at the other nodes by sending the transactions in the queue to the one or more of the other databases, step (b) further comprising detecting that synchronization between the database at the originating node and the database at one or more of the other nodes cannot be ensured when the queue at the originating node is not draining or is draining at a rate less than a predetermined rate.

8. The method of claim 7 wherein the queue of transactions are developed from audit trail entries at the respective node.

9. The method of claim 1 wherein the first I/O operation is a begin operation.

10. The method of claim 1 wherein each node includes a replication engine that synchronizes the database at the originating node to the one or more other databases by sending the transactions posted to the originating database to the one or more other databases, step (b) further comprising detecting that synchronization between the database at the originating node and the database at one or more of the other nodes cannot be ensured when the replication engine at the originating node is not properly functioning.

11. The method of claim 1 further comprising:

(c) upon detection that synchronization between the database at the originating node and the database at one or more of the other nodes cannot be ensured, routing all subsequent transactions at the originating node to one of the other nodes.

12. A method of synchronizing plural databases in a database replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, and (ii) a transaction transmitter which sends selected transactions posted to the database to one or more other nodes, each transaction being one or more transaction steps or transaction operations, the method comprising:

(a) a transaction transmitter at a first node collecting a block of transaction steps or transaction operations posted to a source database at the first node;

(b) the transaction transmitter at the first node sending the block of transaction steps or transaction operations to a second node having a target database for posting thereto;

(c) repeating steps (a) and (b) for additional blocks of transaction steps or transaction operations in the source database; and

(d) inhibiting a commit operation at either the source database or the target database until it can be ensured that the source database and the target database can both be successfully updated with the transaction steps or transaction operations, the transactions, thus being replicated using a synchronous replication mode.

13. The method of claim 12 wherein step (d) further comprises:

(i) pausing each transaction being executed in the database at the originating node prior to a commit operation for the transaction,

(ii) assigning a ready to commit token to the transaction,

(iii) sending the ready to commit token to the one or more other nodes,

(iv) determining at the one or more other nodes whether the respective databases are 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 originating node, and

(v) executing a commit operation at the database of the originating node only upon receipt from at least one of the other nodes of the ready to commit tokens originally sent from the originating node.

14. The method of claim 13 wherein the commit operation in step (v) is performed only upon receipt from each of the one or more the other nodes of the ready to commit tokens originally sent from the originating node.

15. The method of claim 13 wherein if it is determined at another node that the respective database is prepared for a commit operation for the transaction corresponding to the ready to commit token, then

(vi) committing the transaction at the other node before the transaction is committed at the originating node.

16. The method of claim 12 wherein the transactions are replicated in synchronous replication mode in normal operation, the method further comprising:

(e) replicating the transactions using an asynchronous replication mode when synchronous replication is not properly functioning.

17. The method of claim 16 further comprising:

(f) restoring the synchronous replication mode when it is detected that synchronous replication can properly function again.

18. The method of claim 12 wherein the block of transaction steps or transaction operations is collected from a queue of transaction steps or transaction operations posted to a source database at the first node.

40. The method of claim 12 wherein each block of transaction steps or transaction operations includes at least two transaction steps or transaction operations associated with a single transaction.

19. A method of performing dual writes in a database replication system that includes (i) a local application which receives transactions, each transaction being one or more transaction steps or transaction operations, (ii) a local database associated with the local application process, and (iii) a remote database, the method comprising:

(a) at the local application, queuing a plurality of transaction steps or transaction operations;

(b) sending a block of queued transaction steps or transaction operations to the remote database for posting thereto;

(c) repeating steps (a) and (b) for additional blocks of transaction steps or transaction operations collected at the local application; and

(d) inhibiting a commit operation at either the local database or the remote database until it can be ensured that the local database and the remote database can both be successfully updated with the transaction steps or transaction operations, the transactions thus being replicated using a synchronous replication mode.

20. The method of claim 19 wherein the transaction steps or transaction operations in the queue are transaction steps or transaction operations that have not yet been posted to the local database.

21. The method of claim 19 wherein during the synchronous replication mode,

(i) pausing each transaction being executed at the local application prior to a commit operation for the transaction,

(ii) the local application assigning a ready to commit token to the transaction,

(iii) the local application sending the ready to commit token to the remote database,

(iv) determining whether the remote 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 local application, and

(v) executing a commit operation at the local database only upon receipt from the remote database of the ready to commit token originally sent from the local application.

41. The method of claim 19 wherein each block of transaction steps or transaction operations includes at least two transaction steps or transaction operations associated with a single transaction.

22. A method of avoiding collisions in a database replication system including a plurality of nodes connected via communication media in a topology, each node including a database, at least some of the nodes being able to independently receive and post transactions, the method comprising:

(a) pausing each transaction being executed in the database at an originating node prior to a commit operation for the transaction;

(b) assigning a ready to commit token to the transaction;

(c) sending the ready to commit token to the one or more other nodes;

(d) determining at the one or more other nodes whether the respective databases are 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 originating node; and

(e) executing a commit operation at the database of the originating node only upon receipt from at least one of the other nodes of the ready to commit tokens originally sent from the originating node.

23. The method of claim 22 wherein the commit operation in step (e) is performed only upon receipt from each of the one or more the other nodes of the ready to commit tokens originally sent from the originating node.

24. A method of avoiding collisions in a database replication system including a plurality of nodes connected via communication media in a topology, each node including a database, at least some of the nodes being able to independently receive and post transactions, the method comprising:

(a) pausing each transaction being executed in the database at an originating node prior to a commit operation for the transaction;

(b) assigning a ready to commit token to the transaction;

(c) sending the ready to commit token to the one or more other nodes; and

(d) determining at the one or more other nodes whether the respective databases are prepared for a commit operation for the transaction corresponding to the ready to commit token, and, if so, executing the commit operation at the one or more other nodes before a commit operation is performed at the originating node.

25. The method of claim 24 further comprising:

(e) executing a commit operation at the database of the originating node upon receipt from at least one of the other nodes of the ready to commit tokens originally sent from the originating node.

26. A method of replicating data associated with a plurality of transactions in a replication system including a plurality of nodes connected via communication media in a topology, each node including (i) a database, (ii) a replication engine which performs data replication functions, and (iii) an application which executes transactions and posts the transactions to the database, the application being independent of the replication engine, each transaction being one or more transaction steps or transaction operations, the method comprising:

(a) an application at a first node pausing each transaction being executed in a source database at the first node prior to a commit operation for the transaction;

(b) a replication engine at the first node assigning a ready to commit token to the transaction in coordination with the application;

(c) the replication engine at the first node sending the ready to commit token to the second node;

(d) a replication engine at a second node determining whether a target database at the second node 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 first node; and

(e) the application at the first node executing a commit operation at the source database in coordination with the replication engine only upon receipt from the second node of the ready to commit token originally sent from the first node.

27. A method of synchronizing plural databases in a database replication system including a plurality of nodes connected via communication media in a topology, each node including a database, each database including a plurality of records, each record having an associated key, each transaction being one or more transaction steps or transaction operations, the method comprising:

(a) initially sending only keys of database records in a source database at a first node that are desired to be replicated to a target database at a second node as a result of a transaction;

(b) using the keys at the target database to prepare the target database for a subsequent commit operation;

(c) pausing each transaction being executed in the source database at the first node prior to a commit operation for the transaction;

(d) assigning a ready to commit token to the transaction;

(e) sending the ready to commit token to the second node;

(f) determining whether a target database at the second node 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 first node; and

(g) executing a commit operation at the source database only upon receipt from the second node of the ready to commit token originally sent from the first node.

28. The method of claim 27 further comprising:

(h) after the commit operation is performed at the source database, sending the transaction steps or transaction records for the database records to be replicated to the target database.

29. The method of claim 27 wherein the target database is prepared for a subsequent commit operation by locking the corresponding database records at the target database.

30. A method of determining when to switch from a synchronous replication mode to an asynchronous replication mode in a database replication system including a plurality of nodes connected via communication media in a topology, each node including a database, at least some of the nodes being able to independently receive and post transactions, the method comprising:

(a) pausing each transaction being executed in the database at an originating node prior to a commit operation for the transaction;

(b) assigning a ready to commit token to the transaction;

(c) sending the ready to commit token to the one or more other nodes;

(d) determining at the one or more other nodes whether the respective databases are 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 originating node; and

(e) switching from a synchronous replication mode to an asynchronous replication mode if the originating node does not receive back the ready to commit token that it has originally sent to any of the other nodes, the switching occurring only for the nodes that the originating node does not receive back a token.

31. The method of claim 30 further comprising:

(f) executing a commit operation at the database of the originating node upon receipt from at least one of the other nodes of the ready to commit tokens originally sent from the originating node.

32. A method of determining when to restore a synchronous replication mode in a replication system which replicates data associated with a plurality of transactions, the system including a plurality of nodes connected via communication media in a topology, each node including a database, wherein the system normally operates in a synchronous replication mode, but switches to an asynchronous replication mode when synchronization between a database at an originating node and a database at one or more of the other nodes cannot be ensured, the method comprising:

(a) detecting replication latency; and

(b) restoring the synchronous replication mode when synchronization between a database at an originating node and a database at one or more of the other nodes can be ensured again and replication latency becomes less than a predetermined time value.

33. The method of claim 32 wherein the replication system is a bidirectional relication system.

34. A method of routing transaction inputs in a bidirectional replication system which replicates data associated with a plurality of transactions, the system including a plurality of nodes connected via communication media in a topology, each node including a database, wherein the system normally operates in a synchronous replication mode, but switches to an asynchronous replication mode when synchronization between a database at an originating node and a database at one or more of the other nodes cannot be ensured, the method comprising:

(a) selecting a winning node upon switching to an asynchronous replication mode; and

(b) routing all transaction inputs at the other nodes to the winning node during the time period of asynchronous replication.

35. A method of addressing collisions upon restoring a synchronous replication mode in a replication system which replicates data associated with a plurality of transactions, the system including a first node and a second node, each node including a database, wherein the system normally operates in a synchronous replication mode, but switches to an asynchronous replication mode when synchronization between a database at the first node and a database at the second node cannot be ensured, the method comprising:

(a) detecting that the synchronous replication mode may be restored;

(b) sending all queued transactions at each node that do not cause any collision to the other node in their order of occurrence;

(c) resolving any collisions in the remaining queued transactions and sending the resolved transactions to the respective nodes; and

(d) upon completion of steps (b) and (c), switching back to the synchronous replication mode.

36. The method of claim 35 wherein the replication system is a bidirectional replication system.

37. The method of claim 35 wherein between steps (a) and (b), pausing each transaction that is requested to be executed in the database at an originating node prior to a first I/O operation, step (d) further comprising inhibiting the pausing upon switching back to the synchronous replication mode.

38. The method of claim 35 wherein in step (c) the collisions are resolved using relative transaction steps or operations.

39. The method of claim 35 wherein each of the nodes may accept transaction inputs and upon switching to an asynchronous mode, all of the transaction inputs are routed to one of the nodes, and step (d) further comprises redistributing the transaction inputs between the nodes upon switching back to the synchronous replication mode.