Non-blocking commit protocol systems and methods

• US 8,055,711 B2
• Filed: 10/28/2005
• Issued: 11/08/2011
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Passey, Aaron J., Godman, Peter J., Fachan, Neal T.
• Primary Examiner(s): WINDER, PATRICE L
• Application Number:
  US11/262,306
• Publication Number:
  US 20060095438A1
• Time in Patent Office: 2,202 Days
• Field of Search: 709/205, 709/230, 709/237
• US Class Current: 709/205
• CPC Class Codes: G06F 16/1865 Transactional file systems

Abstract

Systems and methods are provided for atomic single-failure non-blocking and double-failure non-blocking commitment protocols. The protocols may be used for a variety of transactions that involve two or more parties including an initiator of the transaction, a coordinator of the transaction, and one or more participants in the transaction. The participants notify the coordinator when they are prepared to commit the transaction. The coordinator then determines when to commit or abort the transaction. If the coordinator disconnects from one or more of the participants, the participants can resolve the transaction independently. Some embodiments also include a distributor that interacts with the coordinator and the participants to resolve the transaction. If one or more parties become disconnected from the coordinator or the distributor, the participants vote to determine whether to receive instructions from the coordinator or the distributor.

Claims

1. A distributed system configured to resolve an atomic transaction comprising multiple transactions among a set of parties within the distributed system, the distributed system comprising:

a plurality of participants, each of the plurality of participants residing on a node of a computer system and in communication with each of the other of the plurality of participants; and

a coordinator residing on a node of the computer system and in communication with each of the plurality of participants, wherein at least one of the plurality of participants resides on the same node of the computer system as the coordinator;

wherein the coordinator is configured to;

receive one or more prepared messages from one or more of the plurality of participants, each prepared message indicating whether the sending participant can commit a transaction of the atomic transaction;

decide to either commit or abort the atomic transaction based on the received prepared messages; and

send the decision to either commit or abort the atomic transaction to two or more of the plurality of participants;

wherein each of the plurality of participants is configured to;

receive a prepare message, the prepare message indicating that the participant should commit a transaction of the atomic transaction;

determine whether the participant can commit the transaction;

send a prepared message to the coordinator, the prepared message indicating whether the participant can commit the transaction;

receive decision messages from two or more of the plurality of participants which are different than the coordinator, each decision message indicating that the sending participant has either committed or aborted a transaction of the atomic transaction;

if communication with the coordinator is available, receive the decision to either commit or abort the atomic transaction from the coordinator;

if the decision is received from the coordinator, decide to either commit or abort the transaction based on the received decision;

if communication with the coordinator is not available and the decision was not received from the coordinator, decide to either commit or abort the transaction based on the received decision messages from the two or more of the plurality of participants which are different than the coordinator; and

send the participant'"'"'s decision to either commit or abort the transaction to each of the other of the plurality of participants with which communication is available.

2. The distributed system of claim 1, wherein the coordinator is further configured to decide to:

commit the atomic transaction if prepared messages have been received from each of the plurality of participants and each received prepared message indicates that the sending participant can commit a transaction of the atomic transaction; and

abort the atomic transaction if at least one prepared message has been received from one of the plurality of participants and the received prepared message indicates that the sending participant cannot commit a transaction of the atomic transaction.

3. The distributed system of claim 1, wherein each of the plurality of participants is further configured to decide to:

commit the transaction if a decision to commit the atomic transaction is received from the coordinator; and

abort the transaction if a decision to abort the atomic transaction is received from the coordinator.

4. The distributed system of claim 2, wherein the coordinator is further configured to abort the transaction if communication between the coordinator and one of the plurality of participants is unavailable.

5. The distributed system of claim 1, wherein each of the plurality of participants is further configured to commit the transaction if all of the received one or more decision messages indicate that the sending participant has committed a transaction of the atomic transaction.

6. The distributed system of claim 1, wherein each of the plurality of participants is further configured to abort the transaction if one of the received one or more decision messages indicate that the sending participant has aborted a transaction of the atomic transaction.

7. The distributed system of claim 1, further comprising a shared participant residing on the same node of the computer system as the coordinator and in communication with each of the plurality of participants, the shared participant configured to:

receive a prepare message from an initiator, the prepare message indicating that the shared participant should commit a transaction of the atomic transaction;

determine whether the shared participant can commit the transaction;

send a prepared message to the coordinator, the prepared message indicating whether the shared participant can commit the transaction;

receive one or more decision messages from one or more of the plurality of participants, each decision message indicating that the sending participant has either committed or aborted a transaction of the atomic transaction; and

decide to either commit or abort the transaction based on the received one or more decision messages.

8. The method of claim 1, wherein each of the plurality of participants is further configured to:

determine that communication with one of the plurality of participants was previously unavailable and has become available; and

send the participant'"'"'s decision to either commit or abort the transaction to the previously unavailable one of the plurality of participants.

9. The method of claim 8, wherein said determination that communication with one of the plurality of participants was previously unavailable and has become available is based on a message received from said previously unavailable one of the plurality of participants.

10. The method of claim 1, wherein each of the plurality of participants is further configured to:

receive a request message from one or more of the plurality of participants, the request message requesting the participant'"'"'s decision to either commit or abort the transaction; and

send the participant'"'"'s decision to either commit or abort the transaction to one or more of the other of the plurality of participant from which a request message was received.

11. A method of resolving an atomic transaction comprising multiple transactions among a plurality of participants, each participant residing on a node of a distributed computer system, the method comprising:

sending, by the one or more computer processors of each of the plurality of participants, a prepared message to a coordinator, the coordinator residing on the same node as at least one of the plurality of participants, the prepared message indicating that the sending participant is prepared to commit a transaction of the atomic transaction;

receiving, by each of a first subset of two or more of the plurality of participants which are different than the coordinator, a decision from the coordinator to either commit or abort the atomic transaction;

determining, by each of a second subset of one or more of the plurality of participants, that communication with the coordinator is not available and that no decision from the coordinator was received;

deciding, by the one or more computer processors of each of the first subset of the plurality of participants, to either commit or abort the transaction;

sending, by the one or more computer processors of two or more of the first subset of the plurality of participants, the decision by the sending participant to either commit or abort the transaction to each of the second subset of the plurality of participants with which communication is available;

receiving, by each of the second subset of the plurality of participants, a decision to either commit or abort the transaction from two or more of the first subset of the plurality of participants; and

deciding, by the one or more computer processors of each of the second subset of the plurality of participants, to either commit or abort the transaction based on the received decisions from the two or more of the first subset of the plurality of participants.

12. The method of claim 11, further comprising receiving, by each of the plurality of participants, a prepare message from an initiator, the prepare message indicating that the receiving participant should prepare for the transaction.

13. The method of claim 11, wherein receiving a decision from the coordinator comprises receiving a commit message from the coordinator node to commit the transaction.

14. The method of claim 11, wherein receiving a decision from the coordinator comprises receiving an abort message from the coordinator node to abort the transaction.