Two-Phase Commit In Addition To Beyond
In this post, nosotros model together with explore the two-phase commit protocol using TLA+.
The two-phase commit protocol is practical together with is used inwards many distributed systems today. Yet it is even therefore brief plenty that nosotros tin flame model it quickly, together with larn a lot from modeling it. In fact, nosotros run into that through this instance nosotros acquire to illustrate a telephone substitution impossibility effect inwards distributed systems directly.
The transaction director (TM) finalizes the transaction amongst a commit or abort decision. For the transaction to live on committed, each participating RM must live on prepared to commit it. Otherwise, the transaction must live on aborted.
A RM tin flame solely read the TM's dry reason together with read/update its ain state. It cannot read other RM's state. A TM tin flame read all RM nodes' dry reason together with read/update its ain state.
Lines 9-10 laid the initial rmState for each RM to "working" together with that of the TM to "init".
The canCommit predicate is defined to live on truthful iff all RMs are "prepared" (they are laid for a commit decision). If at that spot exists an RM amongst "abort" state, canAbort becomes truthified.
The TM modeling is straightforward. TM checks if it tin flame commit or tin flame abort, together with updates tmState accordingly.
TM tin flame too neglect making tmState "unavailable", but this gets exercised solely if the constant TMMAYFAIL is laid to truthful earlier the model checking starts. In TLA+, the labels determine the granularity of atomicity. By putting the labels F1 together with F2, nosotros announce that the corresponding statements are executed nonatomically (after simply about indeterminate fourth dimension passes) amongst observe to the previous statements.
The RM model is too simple. Since "working" together with "prepared" states are nonterminal states, the RM nondeterministically chooses amidst the enabled actions until a end dry reason is reached. A "working" RM may transition to an "aborted" or "prepared" state. A "prepared" RM waits to listen the commit together with abort conclusion from the TM together with acts accordingly. The figure below shows the dry reason transitions possible for 1 RM. But Federal Reserve notation that nosotros receive got multiple RMs, each of which is going through their dry reason transitions at their measuring without the cognition of the dry reason of simply about other RM.
We are interested inwards checking that our two-phase commit is consistent: at that spot are no 2 RMs such that 1 says "committed" together with simply about other "aborted".
The predicate Completed checks that the protocol does non hang on forever: eventually each RM reaches to a end "committed" or "aborted" state.
With that, nosotros are laid to model depository fiscal establishment check this protocol. Initially nosotros laid TMMAYFAIL=FALSE, RM=1..3 to run the protocol amongst iii RMs together with 1 TM that is reliable. The model checker takes fifteen seconds together with tells us that at that spot are no errors. Both Consistency together with Completed are satisfied past times whatever possible execution of the protocol amongst unlike interleaving of enabled RM actions together with TM actions.
Now, nosotros set TMMAYFAIL=TRUE together with restart the model checker. The model checker is quick to give us a counterexample describe where the RMs inwards this execution is stuck waiting to listen dorsum from the TM which has acquire unavailable.
We run into that on State=4 the RM2 transitions to aborted, on State=7 the RM3 transitions to aborted, on State=8 the TM transitions to "abort", together with crashes on State=9. On State=10, the organization is stuck because the RM1 is inwards the prepared dry reason waiting forever to larn a conclusion from the TM which has crashed.
When nosotros model depository fiscal establishment check amongst the BTM procedure added, nosotros acquire a novel fault message.
BTM cannot dominion for a commit, because our original, canCommit condition asserted that all RMstates should live on "prepared" together with didn't concern human relationship for the status when simply about RMs already learned the "commit" conclusion from the master copy TM earlier the BTM takes over. So nosotros revise our canCommit condition to concern human relationship for this.
Success! When nosotros depository fiscal establishment check the model, nosotros uncovering that both Consistency together with Completed are satisfied, equally the BTM tin flame receive got over together with finalizes the transaction when TM fails. Here is the 2PCwithBTM model inwards TLA+ (initially the BTM together with the minute occupation of canCommit commented out). Here is the pdf corresponding to the pdf.
We too quest to strengthen canAbort to receive got into concern human relationship the unavailable state. The TM tin flame dominion for "abort" if whatever of the RMs is inwards "aborted" or "unavailable" state. If nosotros omit this condition, an RM that has crashed (and never recovers) may brand the transaction lose progress. Of class precaution should live on taken to ensure that BTM cannot dominion for an abort if at that spot exists a RM that has learned of a "committed" conclusion from the master copy TM.
When nosotros depository fiscal establishment check this model, nosotros uncovering an inconsistency problem! How did this happen? Let's follow the execution describe for the counterexample.
On State=6, all the RMs are inwards prepared state, the TM had made a commit decision, together with RM1 has seen that conclusion together with moved to label RC, important that it is laid to modify its dry reason to "committed". (Keep RM1 inwards mind, this gun volition burn downwards at the in conclusion act.) Unfortunately, the TM crashes inwards State=7, together with RM2 becomes =unavailable= inwards State=8. In State 9, the BTM takes over reads the RMstates equally <prepared, unavailable, prepared> together with rules for an abort inwards State=10. Remember RM1, it finally acts on the commit conclusion it saw from the master copy TM, together with transitions to committed inwards State=11. In State=13, RM3 heeds the abort conclusion from the BTM together with transitions to aborted, together with nosotros receive got the Consistency violated amongst RM1 deciding for committed and RM3 for aborted.
In this case, the BTM made a conclusion that violated consistency. On the other hand, if nosotros had made BTM to hold off until at that spot are no "unavailable" RMs, it could live on waiting forever on a crashed node, together with this would therefore violate the progress condition.
The updated TLA+ model file is available here, together with the corresponding pdf here.
In our example, the BTM cannot correctly create upwards one's head whether RM2 is crashed or not, together with rules incorrectly for an abort. If at that spot was solely 1 conclusion maker, simply the TM, the inaccurate failure detector would non live on an issue. The RMs would follow whatever the TM decides together with both Consistency together with Progress would live on satisfied.
What surfaces together with illustrates the occupation is that nosotros receive got 2 conclusion makers TM together with BTM looking at the dry reason of the RMs at unlike times, together with making unlike decisions. This asymmetry of data is the root of all evil inwards distributed systems.
This occupation doesn't cash inwards one's chips away fifty-fifty amongst the three-phase commit extension. Here is the three-phase commit extension modeled inwards TLA+ (here is the pdf version), together with below is the fault describe that shows this fourth dimension Progress is violated. (The wikipedia page on three-phase commit says inwards a timeout later on receiving the precommit social club the RMs, i.e., RM2 together with RM3, should cash inwards one's chips ahead together with commit, but that would instead crusade a consistency occupation inwards this case.)
Not all promise is lost. We receive got Paxos. Paxos treads carefully inside bounds of the FLP result. The project design inwards Paxos is that it is always safe (even inwards presence of inaccurate failure detectors, asynchronous execution, faults), together with it eventually makes progress when consensus gets inwards the realm of possibility.
You tin flame emulate the TM amongst a Paxos cluster of 3 nodes together with that volition solve the inconsistent TM/BTM problem. Or as Gray together with Lamport demonstrate inwards the transaction commit paper, if the RMs purpose the Paxos box to shop their decisions concurrently amongst replying to the TM, this shaves off the extra 1 message delay from the obvious protocol.
The two-phase commit protocol is practical together with is used inwards many distributed systems today. Yet it is even therefore brief plenty that nosotros tin flame model it quickly, together with larn a lot from modeling it. In fact, nosotros run into that through this instance nosotros acquire to illustrate a telephone substitution impossibility effect inwards distributed systems directly.
The two-phase commit problem
A transaction is performed over resource managers (RMs). All RMs must concur on whether the transaction is committed or aborted.The transaction director (TM) finalizes the transaction amongst a commit or abort decision. For the transaction to live on committed, each participating RM must live on prepared to commit it. Otherwise, the transaction must live on aborted.
Some notes close modeling
We perform this modeling inwards the shared retentivity model, rather than inwards message passing, to hold things simple. This too ensures that the model checking is fast. But nosotros add together nonatomicity to the "read from vecino together with update your state" actions inwards social club to capture the interesting behaviors that would plough over off inwards a message passing implementation.A RM tin flame solely read the TM's dry reason together with read/update its ain state. It cannot read other RM's state. A TM tin flame read all RM nodes' dry reason together with read/update its ain state.
Definitions
Lines 9-10 laid the initial rmState for each RM to "working" together with that of the TM to "init".
The canCommit predicate is defined to live on truthful iff all RMs are "prepared" (they are laid for a commit decision). If at that spot exists an RM amongst "abort" state, canAbort becomes truthified.
TM model
The TM modeling is straightforward. TM checks if it tin flame commit or tin flame abort, together with updates tmState accordingly.
TM tin flame too neglect making tmState "unavailable", but this gets exercised solely if the constant TMMAYFAIL is laid to truthful earlier the model checking starts. In TLA+, the labels determine the granularity of atomicity. By putting the labels F1 together with F2, nosotros announce that the corresponding statements are executed nonatomically (after simply about indeterminate fourth dimension passes) amongst observe to the previous statements.
RM model
The RM model is too simple. Since "working" together with "prepared" states are nonterminal states, the RM nondeterministically chooses amidst the enabled actions until a end dry reason is reached. A "working" RM may transition to an "aborted" or "prepared" state. A "prepared" RM waits to listen the commit together with abort conclusion from the TM together with acts accordingly. The figure below shows the dry reason transitions possible for 1 RM. But Federal Reserve notation that nosotros receive got multiple RMs, each of which is going through their dry reason transitions at their measuring without the cognition of the dry reason of simply about other RM.
Model checking the two-phase commit
We are interested inwards checking that our two-phase commit is consistent: at that spot are no 2 RMs such that 1 says "committed" together with simply about other "aborted".
The predicate Completed checks that the protocol does non hang on forever: eventually each RM reaches to a end "committed" or "aborted" state.
With that, nosotros are laid to model depository fiscal establishment check this protocol. Initially nosotros laid TMMAYFAIL=FALSE, RM=1..3 to run the protocol amongst iii RMs together with 1 TM that is reliable. The model checker takes fifteen seconds together with tells us that at that spot are no errors. Both Consistency together with Completed are satisfied past times whatever possible execution of the protocol amongst unlike interleaving of enabled RM actions together with TM actions.
Now, nosotros set TMMAYFAIL=TRUE together with restart the model checker. The model checker is quick to give us a counterexample describe where the RMs inwards this execution is stuck waiting to listen dorsum from the TM which has acquire unavailable.
We run into that on State=4 the RM2 transitions to aborted, on State=7 the RM3 transitions to aborted, on State=8 the TM transitions to "abort", together with crashes on State=9. On State=10, the organization is stuck because the RM1 is inwards the prepared dry reason waiting forever to larn a conclusion from the TM which has crashed.
BTM modeling
In social club to avoid whatever downtime for many transactions the TM may live on commandeering, nosotros add together a Backup TM (BTM) to speedily receive got over when the TM becomes unavailable. The BTM uses the same logic equally the TM to brand decisions. And for simplicity nosotros assume the BTM does non fail.
When nosotros model depository fiscal establishment check amongst the BTM procedure added, nosotros acquire a novel fault message.
BTM cannot dominion for a commit, because our original, canCommit condition asserted that all RMstates should live on "prepared" together with didn't concern human relationship for the status when simply about RMs already learned the "commit" conclusion from the master copy TM earlier the BTM takes over. So nosotros revise our canCommit condition to concern human relationship for this.
Success! When nosotros depository fiscal establishment check the model, nosotros uncovering that both Consistency together with Completed are satisfied, equally the BTM tin flame receive got over together with finalizes the transaction when TM fails. Here is the 2PCwithBTM model inwards TLA+ (initially the BTM together with the minute occupation of canCommit commented out). Here is the pdf corresponding to the pdf.
What if RMs could too fail?
We assumed the RMs are reliable. Now nosotros relax that to run into how the protocol behaves inwards the presence of RM failure. We add together an "unavailable" dry reason to model for a crash. In social club to explore to a greater extent than conduct together with model intermittent loss of availability, nosotros allow a crashed RM to recover dorsum together with cash inwards one's chips along the protocol past times reading its dry reason from its log. Here is the RM dry reason transition diagram in 1 trial again amongst the newly added "unavailable" dry reason together with transitions marked amongst red. And below that is the revised model for the RMs.
We too quest to strengthen canAbort to receive got into concern human relationship the unavailable state. The TM tin flame dominion for "abort" if whatever of the RMs is inwards "aborted" or "unavailable" state. If nosotros omit this condition, an RM that has crashed (and never recovers) may brand the transaction lose progress. Of class precaution should live on taken to ensure that BTM cannot dominion for an abort if at that spot exists a RM that has learned of a "committed" conclusion from the master copy TM.
Model checking
When nosotros depository fiscal establishment check this model, nosotros uncovering an inconsistency problem! How did this happen? Let's follow the execution describe for the counterexample.
On State=6, all the RMs are inwards prepared state, the TM had made a commit decision, together with RM1 has seen that conclusion together with moved to label RC, important that it is laid to modify its dry reason to "committed". (Keep RM1 inwards mind, this gun volition burn downwards at the in conclusion act.) Unfortunately, the TM crashes inwards State=7, together with RM2 becomes =unavailable= inwards State=8. In State 9, the BTM takes over reads the RMstates equally <prepared, unavailable, prepared> together with rules for an abort inwards State=10. Remember RM1, it finally acts on the commit conclusion it saw from the master copy TM, together with transitions to committed inwards State=11. In State=13, RM3 heeds the abort conclusion from the BTM together with transitions to aborted, together with nosotros receive got the Consistency violated amongst RM1 deciding for committed and RM3 for aborted.
In this case, the BTM made a conclusion that violated consistency. On the other hand, if nosotros had made BTM to hold off until at that spot are no "unavailable" RMs, it could live on waiting forever on a crashed node, together with this would therefore violate the progress condition.
The updated TLA+ model file is available here, together with the corresponding pdf here.
FLP impossibility
So, what happened? We striking the Fischer, Lynch, Paterson (FLP) impossibility result: In an asynchronous system, it is impossible to solve consensus (satisfy both security together with progress conditions) inwards the presence of crash faults.In our example, the BTM cannot correctly create upwards one's head whether RM2 is crashed or not, together with rules incorrectly for an abort. If at that spot was solely 1 conclusion maker, simply the TM, the inaccurate failure detector would non live on an issue. The RMs would follow whatever the TM decides together with both Consistency together with Progress would live on satisfied.
What surfaces together with illustrates the occupation is that nosotros receive got 2 conclusion makers TM together with BTM looking at the dry reason of the RMs at unlike times, together with making unlike decisions. This asymmetry of data is the root of all evil inwards distributed systems.
This occupation doesn't cash inwards one's chips away fifty-fifty amongst the three-phase commit extension. Here is the three-phase commit extension modeled inwards TLA+ (here is the pdf version), together with below is the fault describe that shows this fourth dimension Progress is violated. (The wikipedia page on three-phase commit says inwards a timeout later on receiving the precommit social club the RMs, i.e., RM2 together with RM3, should cash inwards one's chips ahead together with commit, but that would instead crusade a consistency occupation inwards this case.)
Paxos, making the Blue Planet a meliorate place
Not all promise is lost. We receive got Paxos. Paxos treads carefully inside bounds of the FLP result. The project design inwards Paxos is that it is always safe (even inwards presence of inaccurate failure detectors, asynchronous execution, faults), together with it eventually makes progress when consensus gets inwards the realm of possibility.
You tin flame emulate the TM amongst a Paxos cluster of 3 nodes together with that volition solve the inconsistent TM/BTM problem. Or as Gray together with Lamport demonstrate inwards the transaction commit paper, if the RMs purpose the Paxos box to shop their decisions concurrently amongst replying to the TM, this shaves off the extra 1 message delay from the obvious protocol.
0 Response to "Two-Phase Commit In Addition To Beyond"
Post a Comment