Non-blocking commit protocol systems and methods

• US 8,140,623 B2
• Filed: 06/08/2006
• Issued: 03/20/2012
• 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: Fachan, Neal T.
• Primary Examiner(s): Nguyen, Phuoc
• Assistant Examiner(s): NGUYEN, STEVEN C
• Application Number:
  US11/449,153
• Publication Number:
  US 20070168351A1
• Time in Patent Office: 2,112 Days
• Field of Search: 709205-207, 707/10
• 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 process atomic transactions within the distributed system, the distributed system comprising:

a plurality of participants in an atomic transaction, each of the plurality of participants residing on a node of a computer system;

a coordinator residing on a first node of the computer system; and

a distributor residing on a second node of the computer system;

wherein the coordinator is configured to;

receive votes directly from the plurality of participants;

determine whether a majority of votes have been received from the plurality of participants;

communicate a decision related to the atomic transaction to each of the plurality of participants, the decision based on whether a majority of votes have been received;

wherein the distributor is configured to;

receive votes directly from the plurality of participants;

determine whether a majority of votes have been received from the plurality of participants;

communicate a decision related to the atomic transaction to each of the plurality of participants, the decision based on whether a majority of votes have been received; and

wherein each of the plurality of participants is configured to;

receive a request related to the atomic transaction;

send a vote to a recipient, the recipient comprising one of the coordinator and the distributor;

receive either the decision related to the atomic transaction from the coordinator or the decision related to the atomic transaction from the distributor; and

commit or abort the request based on the received decision; and

wherein each of the votes comprises an indication that its sender will accept a decision of a recipient of whether to commit or abort the atomic transaction, the recipient comprising one of the coordinator and the distributor, wherein at least one of the plurality of participants sends to the distributor an indication that the at least one of the plurality of participants will accept a decision of the coordinator of whether to commit or abort the atomic transaction.

2. The distributed system of claim 1, wherein each of the plurality of participants, the coordinator, and the distributor are located on separate nodes to provide double-failure tolerance.

3. The distributed system of claim 1, wherein the coordinator or distributor is located on the same node as one of the plurality of participants to provide single-failure tolerance.

4. The distributed system of claim 1, wherein the recipient is the coordinator if the participant has lost communication with the distributor, the recipient is the distributor if the participant has lost communication with the coordinator, and if a vote is requested by the coordinator or the distributor, the recipient is the one of the coordinator and the distributor which requested the vote.

5. The distributed system of claim 1, wherein the coordinator is further configured to communicate a decision to commit the atomic transaction if the majority of votes is for the coordinator, and wherein the distributor is further configured to communicate a decision to abort the atomic transaction if the majority of votes is for the distributor.

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

receive a message related to the atomic transaction from each of the other plurality of participants; and

if communication is lost with both the coordinator and the distributor, commit or abort the atomic transaction based on the messages received from the other plurality of participants.

7. The distributed system of claim 6, wherein each of the plurality of participants is further configured to:

if communication is lost with both the coordinator and the distributor, abort the transaction if an abort message is received from one of the other plurality of participants; and

if communication is lost with both the coordinator and the distributor, commit the transaction if a commit message is received from each of the other plurality of participants.

13. The distributed system of claim 1, wherein the first node and the second node are the same.

14. The distributed system of claim 1, wherein the first node and the second node are different.

8. A method of resolving an atomic transaction comprising multiple transactions among a plurality of nodes within a distributed computing system, the method comprising:

receiving, by each of a plurality of participant nodes, a transaction request related to the atomic transaction, each of the plurality of participant nodes comprising a processor and memory;

determining, by each of a first subset of the plurality of participant nodes, that communication with a coordinator node is not available, the coordinator node comprising a processor and memory;

in response to the determination by each of the first subset of participant nodes that communication with the coordinator node is not available, sending, by each of the first subset of the plurality of participant nodes, a vote for a distributor node directly to the distributor node, the vote comprising an indication that the participant node will accept a decision of the distributor node of whether to commit or abort the atomic transaction, the distributor node comprising a processor and memory, wherein both the distributor node and the coordinator node are configured to receive votes from the plurality of participant nodes;

sending, by the distributor node, a pledge message to each of the plurality of participants nodes from which a vote has not yet been received;

receiving, by each of at least a second subset of the plurality of participant nodes, the pledge message, wherein the first subset and the second subset of the plurality of participant nodes collectively comprise a majority of the plurality of participant nodes, wherein each participant node receiving the pledge message is configured to send to the distributor node, in response to the pledge message, a vote indicating one of the distributor node or the coordinator node from which the participant node will accept a decision regarding the transaction, wherein at least one participant node sends to the distributor node an indication that the at least one participant node will accept a decision of the coordinator node of whether to commit or abort the atomic transaction;

sending, by each of the second subset of the plurality of participant nodes, a vote for the distributor node directly to the distributor node, wherein each vote for the distributor node indicates that the participant node will accept a decision of the distributor node of whether to commit or abort the atomic transaction;

determining, by the distributor node, that a majority of the plurality of participant nodes have voted for the distributor node, the majority comprising at least the first subset and the second subset of the plurality of participant nodes;

sending, by the distributor node, a decision related to the atomic transaction to the plurality of participant nodes; and

resolving the request in accordance with the decision.

9. The method of claim 8, wherein said decision is to abort said atomic transaction.

10. A method of resolving a transaction in a distributed computing system, the method comprising:

receiving, by each of a plurality of participant nodes, a request related to an atomic transaction, each of the plurality of participant nodes comprising a processor and memory;

sending, by each of the plurality of participant nodes, a prepared message directly to a coordinator node, the coordinator node comprising a processor and memory;

sending, by the coordinator node, a commit message to a distributor node, the distributor node comprising a processor and memory;

determining, by each of a first subset of the plurality of participant nodes, that communication with the distributor node is not available;

in response to the determination that communication with the distributor node is not available, sending, by each of the first subset of the plurality of participant nodes, a vote for the coordinator node directly to the coordinator node, the vote comprising an indication that the participant node will accept a decision of the coordinator node of whether to commit or abort the atomic transaction, wherein both the distributor node and the coordinator node are configured to receive votes from the plurality of participant nodes;

sending, by each of a second subset of the plurality of participant nodes, a vote for the distributor node directly to the distributor node, the vote comprising an indication that the participant node will accept a decision of the distributor node of whether to commit or abort the atomic transaction, wherein at least one of the second subset of the plurality of participant nodes sends to the coordinator node an indication that the at least one of the second subset of the plurality of participant nodes will accept a decision of the distributor node of whether to commit or abort the atomic transaction;

determining, by the coordinator node, that a majority of the plurality of participant nodes have voted for the coordinator node, the majority comprising at least the first subset of the plurality of participant nodes; and

sending, by the coordinator node, a decision related to the atomic transaction to the plurality of participant nodes; and

resolving the request in accordance with the decision.

11. The method of claim 10, further comprising:

determining, by the distributor node, that communication with a third subset of the plurality of participant nodes is not available;

determining, by the distributor node, that a majority of the plurality of participant nodes have voted for the coordinator node, the majority comprising at least the third subset of the plurality of participant nodes; and

sending, by the distributor node, a revoke message to at least the second subset of participant nodes from which the distributor node has received a vote.

12. The method of claim 10, wherein said decision is to commit said atomic transaction.