Non-blocking commit protocol systems and methods

• US 20070168351A1
• Filed: 06/08/2006
• Published: 07/19/2007
• 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
• Granted Patent: US 8,140,623 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 process atomic transactions within the distributed system, the distributed system comprising:

a plurality of participants configured to permit communication among the plurality of participants and to process an atomic transaction;

a coordinator configured to communicate with the plurality of participants;

a distributor configured to communicate with the plurality of participants; and

the plurality of participants further configured to determine whether to commit the atomic transaction based on at least one of messages received from the distributor, messages received from the coordinator, and votes from the plurality of participants.

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 votes from the plurality of participants include whether to accept instructions from the coordinator and/or whether to accept instructions from the distributor.

5. The distributed system of claim 4, each of the plurality of participants further configured to vote to accept instructions from the coordinator if the participant has lost its connection with the distributor and to vote to accept instructions from the distributor if the participant has lost its connection with the coordinator.

6. The distributed system of claim 4, the plurality of participants further configured to accept instructions from the coordinator if a majority of the votes from the plurality of participants is for the coordinator and accept instructions from the distributor if a majority of votes from the plurality of participants is for the distributor.

7. The distributed system of claim 1, wherein the votes from the plurality of participants include whether to commit the atomic transaction if the plurality of participants loses their connections with the coordinator and the distributor.

8. The distributed system of claim 7, the plurality of participants further configured to commit the atomic transaction if the plurality of participants unanimously votes to commit the atomic transaction and abort the atomic transaction if the plurality of participants does not unanimously vote to commit the atomic transaction.

9. A method of resolving a transaction by a participant of a plurality of participants, the method comprising:

communicating with the plurality of other participants, a coordinator, and a distributor to determine whether to commit a transaction;

determining whether communication with the coordinator is available;

determining whether communication with the distributor is available; and

if communication with the coordinator and the distributor are not available, sending a voting message to each of the plurality of other participants indicating whether to commit the transaction and receiving voting messages from the plurality of other participants indicating whether to commit the transaction.

10. The method of claim 9, further comprising committing the transaction if the plurality of participants unanimously votes to commit the transaction.

11. The method of claim 9, further comprising aborting the transaction if the plurality of participants does not unanimously vote to commit the transaction.

12. The method of claim 9, wherein if communication with one of the coordinator and the distributor is not available,

sending a voting message to each of the plurality of other participants indicating whether to accept instructions from the coordinator or the distributor as to whether to commit the transaction;

and

receiving voting messages from the plurality of other participants indicating whether to accept instructions from the coordinator or the distributor as to whether to commit the transaction.

13. The method of claim 12, further comprising:

accepting an instruction from the coordinator if a majority of the plurality of participants votes for the coordinator.

14. The method of claim 12, further comprising:

accepting an instruction from the distributor if a majority of the plurality of participants votes for the distributor.

15. The method of claim 12, wherein sending the voting message indicating whether to accept instructions from the coordinator or the distributor includes sending the voting message to accept instructions from the coordinator if communication with the distributor is not available.

16. The method of claim 12, wherein sending the voting message indicating whether to accept instructions from the coordinator or the distributor includes sending the voting message to accept instructions from the distributor if communication with the coordinator is not available.

17. The method of claim 12, wherein sending the voting message indicating whether to accept instructions from the coordinator or the distributor relates to whether a request for a vote was received first from the coordinator or the distributor.

18. The method of claim 9, wherein each of the plurality of other participants, the coordinator, and the distributor are located on separate nodes.

19. A storage medium having a computer program stored thereon for causing a suitably programmed system to process the computer program by performing the method of claim 9 when such computer program is executed on the system.

20. A system for resolving a transaction by a participant of a plurality of participants, the system comprising:

means for communicating with the plurality of other participants, a coordinator, and a distributor to determine whether to commit a transaction;

means for determining whether communication with the coordinator is available;

means for determining whether communication with the distributor is available; and

means for sending a voting message to each of the plurality of other participants indicating whether to commit the transaction and receiving voting messages from the plurality of other participants indicating whether to commit the transaction if communication with the coordinator and the distributor are not available.

21. A method of resolving atomic transactions within a distributed system, the method comprising:

sending messages from a plurality of participants to a coordinator indicating that the plurality of participants are prepared for an atomic transaction;

sending a message from the coordinator to a distributor indicating that the plurality of participants are ready to commit the atomic transaction;

sending messages from the distributor to the plurality of participants instructing the plurality of participants to commit the atomic transaction;

sending messages among the plurality of participants indicating that the plurality of participants committed the atomic transaction; and

sending messages from the plurality of participants to the coordinator indicating that the plurality of participants committed the atomic transaction.

22. A storage medium having a computer program stored thereon for causing a suitably programmed system to process the computer program by performing the method of claim 21 when such computer program is executed on the system.

23. A coordinator configured to participate in resolving a transaction within a distributed system, the coordinator comprising:

a first module configured to receive from a plurality of participants messages indicating that each of the plurality of participants are prepared to commit a transaction;

a second module configured to send a message to a distributor indicating that the distributor should send a commit message to the plurality of participants instructing the plurality of participants to commit the transaction; and

a third module configured to receive messages from each of the plurality of participants indicating that the plurality of participants have committed the transaction.