Non-blocking commit protocol systems and methods

• US 20060095438A1
• Filed: 10/28/2005
• Published: 05/04/2006
• 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.
• Granted Patent: US 8,055,711 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 a transaction among a set of parties within the distributed system, the distributed system comprising:

a plurality of participants configured to permit communication among the plurality of participants and to resolve a transaction;

a coordinator configured to communicate with the plurality of participants to resolve the transaction;

wherein the plurality of participants are configured to determine whether to commit the transaction based on messages from the coordinator, and if not, to determine among the plurality of participants whether to commit the transaction.

2. The distributed system of claim 1, wherein the determination of whether to commit the transaction is based upon whether at least one of the plurality of participants has lost communication with the coordinator.

3. The distributed system of claim 1, wherein the determination of whether to commit the transaction is based upon whether at least one of the plurality of participants has received a commit message from the coordinator.

4. The distributed system of claim 1, wherein the determination of whether to commit the transaction is based upon whether at least one of the plurality of participants has received an abort message from the coordinator.

5. The distributed system of claim 1, wherein the plurality of participants are configured to determine among the plurality of participants whether to commit the transaction based upon whether at least one of the plurality of participants has committed the transaction.

6. The distributed system of claim 1, wherein the plurality of participants are configured to determine among the plurality of participants whether to commit the transaction based upon whether at least one of the plurality of participants has aborted the transaction.

7. The distributed system of claim 1, further comprising a shared participant configured to resolve the transaction, the shared participant located on a node with the coordinator.

8. The distributed system of claim 7, wherein the shared participant is configured to resolve the transaction based on messages from at least one of the plurality of participants.

9. A method of resolving a transaction among a set of nodes comprising:

determining whether communication with a coordinator node is available;

if communication with the coordinator node is available, receiving messages from the coordinator node indicating whether to commit or abort a transaction; and

if communication with the coordinator node is not available, receiving messages from other nodes involved in the transaction indicating whether to commit or abort the transaction.

10. The method of claim 9, further comprising receiving prepare messages from an initiator node to prepare for the transaction.

11. The method of claim 9, wherein receiving messages from the coordinator includes receiving a commit message from the coordinator node to commit the transaction.

12. The method of claim 9, wherein receiving messages from the coordinator includes receiving an abort message from the coordinator node to abort the transaction.

13. A distributed system configured to resolve a transaction among a set of parties within a distributed system, the distributed system comprising:

a set of participant nodes configured to permit communication among the plurality of nodes and to resolve a transaction among a set of parties from the plurality of nodes;

an initiator located on a first node configured to communicate with the plurality of participant nodes;

a coordinator located on the first node;

wherein the initiator is further configured to;

receive a start command to start the transaction,

add participant nodes to the set of participant nodes after the start of the transaction to form an updated set of participant nodes, and

send a message to the coordinator, the message configured to indicate that the initiator is prepared to commit the transaction and to indicate that the participant nodes in the updated set of participant nodes are to be included in the transaction.

14. The distributed system of claim 13, wherein the updated set of participant nodes is larger than the set of participant nodes.

15. The distributed system of claim 13, wherein the updated set of participant nodes is configured to determine whether to commit the transaction based on messages from the coordinator, and if not, to determine among the updated set of participant nodes whether to commit the transaction.

16. The distributed system of claim 15, wherein the determination of whether to commit the transaction is based upon whether at least one of the set of participant nodes has lost communication with the coordinator.

17. The distributed system of claim 13, further comprising a shared participant located on the first node, the shared participant configured to determine whether to commit the transaction based on messages from at least one of updated set of participant nodes.

18. The distributed system of claim 13, further configured to commit the transaction and to track other participant nodes that have committed the transaction until all participants nodes in the updated set of participant nodes have committed the transaction.

19. A method of resolving a transaction among a set of parties within a distributed system, the method comprising:

receiving a command to start an transaction;

receiving a first set of participant nodes to be included in the transaction;

receiving additional participant nodes to be included in the transaction;

adding the additional participant nodes to the first set of participant nodes;

receiving a command to commit the transaction; and

sending a message to a coordinator node to prepare for the transaction, the message including the updated first set of participant nodes.

20. The method of claim 19, further comprising receiving a committed message from at least one of the updated first set of participant nodes indicating that the at least node of the updated first set of participant nodes has committed the transaction and sending committed messages to the updated first set of participant nodes indicating which of the updated first set of participant nodes have committed the transaction.