5
$\begingroup$

Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?

Good reference: Analysis and Verification of Two-Phase Commit & Three-Phase Commit Protocols, by Muhammad Atif,

Elaboration of the question:

Let’s say, a coordinator sends 1st message (PREPARE-COMMIT). At this point assuming all cohorts are reachable, there are two possible outcomes- either all cohorts reply YES or at least one cohort replies NO. In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT). Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?

$\endgroup$
  • 1
    $\begingroup$ Your question would get more attention if you expanded more. I think it would help if you described 2-phase commit in your own words, and what you think happens when the coordinator fails. $\endgroup$ – Gilles Jun 3 '17 at 21:03
  • $\begingroup$ @ Gilles : 2PC is quite standard concept, and there is a [wiki page][1] as well. Not sure if I should rewrite the main points of the whole concepts. [1]: en.wikipedia.org/wiki/Two-phase_commit_protocol $\endgroup$ – KGhatak Jun 4 '17 at 16:15
  • 2
    $\begingroup$ The point is to describe it in your own words. This way people would know precisely what you understand and what you don't. $\endgroup$ – Gilles Jun 4 '17 at 18:39
7
+50
$\begingroup$

Is it because the cohorts don't employ timeout concept in 2PC?

Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1):

The Two-Phase Commit Protocol goes to a blocking state by the failure of the coordinator when the participants are in uncertain state. The participants keep locks on resources until they receive the next message from the coordinator after its recovery

In practice that 'uncertain state' means voting 'yes'. After a cohort votes 'yes', there is no going back, it waits for the global decision. (Other cases are fine: by voting 'no', the given cohort immediately knows that the global decision is also a 'no', and if the coordinator dies even before initiating the voting round, cohorts may decide voting 'no' based on a timeout)

$\endgroup$
  • $\begingroup$ @ tevemadar : Don't find any mentioning of timeout in Sec II.B.1 (page 2) . "cohorts may decide voting 'no' based on a timeout" - But you just said cohorts don't have timeout!! Am I missing something! $\endgroup$ – KGhatak Jun 4 '17 at 16:12
  • $\begingroup$ @KGhatak That is a possible implementation detail, not part of 2PC itself (and it is not in the paper either). Keeping a transaction open consumes resources (locks, anything), which actual implementations do not necessarily like. So, if the coordinator does not act in some timeframe, cohorts may decide to reclaim these resources, and vote a 'no' when the coordinator asks them in the future. This behaviour does not violate 2PC, cohorts are free to vote 'no'. But, they can cast their vote only once. If voting has happened already, and the vote is a 'yes', they can not do anything, just wait. $\endgroup$ – tevemadar Jun 4 '17 at 17:05
  • $\begingroup$ @ tevemadar : "vote a 'no' when the coordinator asks them in the future" - This seems incorrect. Just because a coordinator failed to send a 'commit/abort' doesn't mean that the cohorts would get 'pissed off' and say 'no' next time. Coming to the timeout aspect , referring to "cohorts may decide to reclaim these resources" - doesn't this mean cohorts are NOT blocked when a coordinator fails!!! $\endgroup$ – KGhatak Jun 5 '17 at 21:34
  • $\begingroup$ @KGhatak I am not talking about getting pissed off and retaliate something. I am talking about that the coordinator will try to finish this very transaction some time in the future, and the cohorts can freely vote a 'no' then - they can decide it earlier than they get asked. Remember that in these comments we are talking about the case when the coordinator died or just waited too long before it started the voting round. $\endgroup$ – tevemadar Jun 6 '17 at 0:04
  • 1
    $\begingroup$ @KGhatak Yes, that is why they can not just simply timeout: it would lead to inconsistency. That would be the worst possible outcome, completely disregarding what people expect from a transaction. The possible need for manual resolution by an actual human being is a far better compromise than silently driving databases into an inconsistent state. $\endgroup$ – tevemadar Jun 7 '17 at 13:10
2
$\begingroup$

In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT). Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?

"Option 1" does not exist. When a cohort votes 'yes', it waits for the global decision indefinitely. That is 2PC. If you alter it because it does not look sane/plausible enough, that is not 2PC any more.

EDIT:

Some relaxation for the above: the Atif paper (and mostly Wikipedia too) describe the 'classroom' variant of 2PC. But in the original papers there were suggestions for distributed recovery too. You can find some description in the referred articles (both by Wikipedia and the Atif paper - http://dl.acm.org/citation.cfm?id=850772 is one I managed to access). The 3PC article on Wikipedia mentions it too, in its Motivation section.

I find it hard to access most of these papers (like the 'Gray 78' lecture notes from TU Munich), but as far as I understand:

  • The recovery mechanism tries to get the global decision from practically anybody
  • If the global decision is found anywhere, that is the global decision, and can be carried out. When the coordinator revives, it will do the same. In my interpretation, a cohort could also say 'abort', if its own vote was a 'no'. But again, I have not read the very original paper(s)
  • If the global decision has not been found, and everyone (minus the coordinator) is alive, nothing happened so far (coordinator died before sending out 'commit'-s), the transaction can be aborted
  • If the global decision has not been found, and there is at least one dead cohort (on top of the coordinator being dead too), that is a problem: in 2PC there is no way to tell if the unreachable cohort got a 'commit' message and carried it out before both of them died, or not. So even if there is a timeout or failure detection applied in the 'voted yes and waiting for global decision' step, there can be an indefinite waiting in the recovery procedure

(Here I was writing only about the case where the coordinator dies and cohort(s) try to deal with it)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.