Preforming concurrent transactions in a replicated database environment

• US 5,781,910 A
• Filed: 09/13/1996
• Issued: 07/14/1998
• Est. Priority Date: 09/13/1996
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Stratus Computer, Inc. (Stratus Technologies Bermuda Holdings Ltd.)
• Inventors: Gostanian, Richard K., Ahern, John E.
• Primary Examiner(s): LINTZ, PAUL R
• Application Number:
  US08/710,135
• Time in Patent Office: 669 Days
• Field of Search: 707/10, 707/104, 707/200, 707/8, 707/201
• US Class Current: 707/610
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• 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/80 Database-specific techniques
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

An actively replicated, fault-tolerant database system based on a state machine approach that supports the concurrent execution of multiple transactions requested by a plurality of application clients communicating with the system. The system includes a plurality of database servers for storing system data and an application server layered over each database server for controlling the access to and the manipulation of data stored at the underlying database server. The application servers replicate system data to at least one other database server and coordinate the execution of transactions at each database server to ensure consistent data replicas across the system. More specifically, the application servers administer one of two preselected, novel coordination protocols governing the execution of each database-dependent transaction. The protocols assure transaction atomicity and consistent data replication across the entire system as well as continued processing despite database server and communications failures.

Claims

1. A method for assuring consistent data replication across a database system during concurrent execution of transactions, the database system having a plurality of application clients for issuing transactions operably connected to a plurality of database servers via a communications network, the method comprising the steps of:

providing a plurality of application servers, each associated with one of the database servers, such that each application server may access and manipulate data stored at its associated database server and communicate with the other application servers and the application clients over the communications network;

designating a selected application server and its associated database server as a coordinator for a selected transaction and designating all other application servers and their associated database servers that contain a replica of data involved in the selected transaction as cohorts;

initiating execution of the selected transaction at the coordinator and cohorts;

forwarding, via an atomic multicast message from the coordinator to each cohort, either a commit decision, if the coordinator is able to execute the transaction, or an abort decision, if the coordinator is unable to execute the transaction;

designating those cohorts receiving the commit or abort decision as surviving cohorts;

receiving an acknowledgment at the coordinator that the commit decision was delivered to all surviving cohorts; and

in response to the step of receiving, either committing the selected transaction at the coordinator and surviving cohorts, if the coordinator issues a commit decision or aborting the selected transaction at the coordinator and surviving cohorts, if the coordinator issues an abort decision.

2. The method of claim 1 further comprising the step of forwarding the selected transaction from the coordinator to the cohorts.

3. The method of claim 2 wherein the step of forwarding the selected transaction is via an atomic multicast message.

4. The method of claim 2 wherein the coordinator includes a manager process and at least one worker process whereby the manager process coordinates the exchange of messages between the coordinator and the cohorts and said at least one worker process executes the selected transaction at the database server associated with the coordinator.

5. The method of claim 4 wherein each cohort includes a manager process and at least one worker process whereby the manager process of each cohort communicates with the manager process of the coordinator and said at least one worker process of each cohort executes the selected transaction at the database server associated with that cohort.

6. The method of claim 5 wherein the step of forwarding the selected transaction from the coordinator to each cohort is performed by the manager process of the coordinator utilizing the communications network.

7. The method of claim 6 wherein the step of initiating execution of the selected transaction comprises the steps of:

designating a single worker process of the coordinator and each cohort to execute the selected transaction;

forwarding the selected transaction (i) from the manager process to the designated worker process at the coordinator and (ii) from the manager process to the designated worker process at each cohort; and

instructing the associated database servers to execute the selected transaction by the designated worker processes.

8. The method of claim 7 further comprising the step of activating a transaction time-out at the coordinator prior to initiating execution of the selected transaction at the coordinator and wherein the coordinator forwards the commit decision to the cohorts, if the coordinator completes execution of the selected transaction prior to expiration of the transaction time-out.

9. The method of claim 8 wherein the coordinator forwards the abort decision to the cohorts, if the transaction time-out expires before the coordinator completes execution of the selected transaction.

10. The method of claim 9 wherein the step of committing the selected transaction at the coordinator is performed by the designated worker process.

11. The method of claim 10 further comprising the step of intentionally failing each cohort that is unable to commit the selected transaction, removing the cohort from the database system.

12. The method of claim 11 wherein the step of committing the selected transaction at each surviving cohort is performed by the designated worker process.

13. The method of claim 12 further comprising the steps of:

performing a check by the manager process of the coordinator to confirm the step of committing the selected transaction; and

transmitting a reply message from the coordinator to the application client that issued the selected transaction, indicating that the selected transaction has been committed.

14. The method of claim 13 further comprising the step of continuing the concurrent execution of transactions despite failure of one or more cohorts.

15. The method of claim 1 wherein each transaction issued by the application clients contains information indicating that the transaction is commutative.

16. The method of claim 1 further comprising the step of designating a selected cohort as a new coordinator upon failure of the coordinator.

33. The method of claim 1 or 17 wherein each database server is an Open Database Connectivity database application server.

17. A method for assuring consistent data replication across a database system during concurrent execution of transactions, the database system having a plurality of application clients for issuing transactions operably connected to a plurality of database servers via a communications network, the method comprising the steps of:

providing a plurality of application servers, each associated with one of the database servers, such that each application server may access and manipulate data stored at its associated database server and communicate with the other application servers and the application clients over the communications network;

designating a selected application server and its associated database server as a coordinator for a selected transaction and designating all other application servers and their associated database servers that contain a replica of data involved in the selected transaction as cohorts;

activating a rendezvous time-out at the coordinator;

initiating execution of the selected transaction at the coordinator and cohorts;

forwarding, via an atomic multicast message from the coordinator to all cohorts, a status request message;

designating those cohorts receiving the status request message as surviving cohorts;

in response to the step of forwarding a status message, transmitting by each surviving cohort either a ready to commit response, if the surviving cohort completes execution of the selected transaction, or an abort response, if the surviving cohort is unable to complete execution of the transaction;

issuing from the coordinator to each cohort either a commit decision, if the coordinator receives a ready to commit response from each surviving cohort prior to the rendezvous time-out expiring and the coordinator completes execution of the transaction, or an abort decision, if (1) the coordinator receives at least one abort response from a surviving cohort, (2) the rendezvous time-out expires before a response is received from each surviving cohort or (3) the coordinator is unable to complete execution of the selected transaction;

either committing the selected transaction at the coordinator and each surviving cohort, if the coordinator issues a commit decision, or aborting the selected transaction at the coordinator and each surviving cohort, if the coordinator issues an abort decision.

18. The method of claim 17 further comprising the step of forwarding the transaction from the coordinator to the cohorts.

19. The method of claim 18 wherein the step of forwarding the transaction from the coordinator to the cohorts is via an atomic multicast message.

20. The method of claim 18 wherein the coordinator includes a manager process and at least one worker process whereby the manager process coordinates the exchange of messages between the coordinator and the cohorts and said at least one worker process executes the selected transaction at the database server associated with the coordinator.

21. The method of claim 20 wherein each cohort includes a manager process and at least one worker process whereby the manager process of each cohort communicates with the manager process of the coordinator and said at least one worker process of each cohort executes the selected transaction at the database server associated with that cohort.

22. The method of claim 21 wherein the step of forwarding the selected transaction from the coordinator to each cohort is performed by the manager process of the coordinator utilizing the communications network.

23. The method of claim 22 wherein the step of initiating execution of the selected transaction at the coordinator and the cohorts comprises the steps of:

designating a single worker process at the coordinator and each cohort to execute the transaction;

forwarding the selected transaction from (i) the manager process to the designated worker process at the coordinator and (ii) the manager process to the designated worker process at each cohort; and

instructing the database servers associated with the coordinator and each cohort to execute the transaction by the designated worker processes.

24. The method of claim 23 further comprising the step of activating a transaction time-out at the coordinator prior to initiating execution of the selected transaction at the coordinator and wherein the coordinator issues the commit decision, if the coordinator completes execution of the selected transaction prior to the transaction time-out expiring.

25. The method of claim 24 wherein the coordinator forwards, via an atomic multicast message to each cohort, the abort decision if the transaction time-out expires before the coordinator completes execution of the selected transaction.

26. The method of claim 25 further comprising the step of intentionally failing each cohort that is unable commit the selected transaction, removing the cohort from the database system.

27. The method of claim 25 wherein the step of committing the selected transaction at the coordinator is performed by the designated worker process.

28. The method of claim 27 wherein the step of committing the selected transaction at each cohort is performed by the designated worker process.

29. The method of claim 28 further comprising the steps of:

performing a check by the manager process of the coordinator to confirm the step of committing the selected transaction; and

transmitting a reply message from the coordinator to the application client that issued the selected transaction, indicating that the transaction has been committed.

30. The method of claim 29 further comprising the step of continuing the concurrent execution of transactions despite failure of one or more cohorts.

31. The method of claim 17 wherein each transaction issued by the application clients contains information indicating that the transaction is non-commutative.

32. The method of claim 17 further comprising the step of designating a selected cohort as a new coordinator upon failure of the coordinator.

34. A database system capable of supporting concurrent execution of transactions, the database system comprising:

a communications network;

a plurality of application clients operably coupled to the communications network, the application clients capable of issuing the transactions;

a coordinator operably coupled to the communications network, the coordinator including an application server and an associated database server containing a replica of data involved in a selected transaction;

a plurality of cohorts, each operably coupled to the communications network and including an application server and an associated database server containing a replica of data involved in the selected transaction;

means for initiating execution of the selected transaction at the coordinator and cohorts;

means for forwarding, via an atomic multicast message from the coordinator to the cohorts, either a commit decision, if the coordinator completes execution of the selected transaction, or an abort decision, if the coordinator is unable to complete execution of the selected transaction;

means for recognizing those cohorts able to receive the commit or abort decision as surviving cohorts;

means for providing an acknowledgment at the coordinator that the commit decision was delivered to all surviving cohorts; and

means for either committing the selected transaction at the coordinator and surviving cohorts, if the coordinator issues a commit decision, or aborting the selected transaction at the coordinator and surviving cohorts, if the coordinator issues an abort decision.

35. The database system of claim 34 further comprising means for designating a selected cohort as a new coordinator upon failure of the coordinator.

36. The database system of claim 35 wherein the application server of the coordinator comprises:

a manager process for communicating with the application clients and the cohorts across the communications network; and

at least one worker process for executing transactions at the database server associated with the coordinator.

37. The database system of claim 36 wherein the application server of each cohort comprises:

a manager process for communicating with the coordinator across the communications network; and

at least one worker process for executing transactions at the database server associated with the corresponding cohort.

38. The database system of claim 37 further comprising means for intentionally failing a cohort that is unable to commit the selected transaction, thereby removing the cohort from the database system.

39. The database system of claim 38 wherein the coordinator further comprises a transaction time-out that may be activated by the coordinator and further wherein the coordinator forwards the commit decision, if the coordinator completes execution of the selected transaction prior to the transaction time-out expiring.

40. The database system of claim 39 wherein the coordinator forwards the abort decision, if the coordinator is unable to complete execution of the selection transaction prior to the transaction time-out expiring.

41. A database system capable of supporting concurrent execution of transactions, the database system comprising:

a communications network;

a plurality of application clients operably coupled to the communications network, the application clients capable of issuing the transactions;

a coordinator operably coupled to the communications network, the coordinator including an application server and an associated database server containing a replica of data involved in a selected transaction;

a plurality of cohorts, each operably coupled to the communications network and including an application server and an associated database server containing a replica of data involved in the selected transaction;

means for initiating execution of the selected transaction at the coordinator and cohorts;

means for activating a rendezvous time-out at the coordinator prior to execution of the selected transaction at the coordinator;

means for forwarding, via an atomic multicast message from the coordinator to the cohorts, a status request message;

means for recognizing those cohorts receiving the status request message as surviving cohorts;

means for transmitting, in response to the status message, from each surviving cohort either a ready to commit response, if the surviving cohort completes execution of the selected transaction, or an abort response, if the surviving cohort is unable to complete execution of the selected transaction;

means for issuing from the coordinator to the cohorts either a commit decision, if the coordinator receives a ready to commit response from each surviving cohort prior to expiration of the rendezvous time-out and the coordinator completes execution of the selected transaction, or an abort decision, if (1) the coordinator receives at least one abort response from a surviving cohort, (2) the rendezvous time-out expires before a response is received from each surviving cohort or (3) the coordinator is unable to complete execution of the selected transaction; and

means for either committing the selected transaction at the coordinator and surviving cohorts, if the coordinator issues a commit decision, or aborting the selected transaction at the coordinator and surviving cohorts, if the coordinator issues an abort decision.

42. The database system of claim 41 further comprising means for designating a selected cohort as a new coordinator upon failure of the coordinator.