A brief discussion on the 3PC protocol for distributed system consistency

This article is reproduced from the WeChat public account "Backend Technology Compass". Please contact the Backend Technology Compass public account for reprinting this article.

1. Write in front

Distributed System Consistency Topic This issue should write about the 3PC protocol. I was too busy last week to update it, so I took the old article and made some adjustments to repost it. I hope readers will forgive me. There are about 3 more issues to come: Paxos protocol, Raft protocol, etc., so let's warm up first. Warm reminder: This article is not boring. I changed the drawing tool. For an IT dog like me who majored in architecture, drawing is simply the happiest thing, so feel free to read it!

[[328175]]

Picture (Internet) | Orion Nebula

2. The emergence of 3PC

Previous articles mentioned the problems of the 2PC protocol, such as the single point of coordinator, participant blocking timeout, network partition, fault tolerance, etc. These problems can be optimized and adjusted to some extent, and are not fatal problems. We have disassembled the abnormal situation of the 2PC protocol, but that is an m*n combination problem. We tried to analyze the main contradictions, and found that when the coordinator and the only participant receiving the instruction both have unrecoverable downtime, even if a new coordinator is elected later, data inconsistency may still occur. The emergence of 3PC may be caused by multiple factors. However, it is basically certain that 3PC will correct and optimize the problems existing in 2PC, but this does not mean that 3PC will not introduce new problems. This article will explain these two major contents from the 3PC protocol process:

3. Basic process of 3PC protocol

3PC protocol Three-Phase-Commit is also called three-phase commit protocol. Compared with 2PC protocol, it adds one more phase, so we generally regard 3PC protocol as an improved version of 2PC protocol. 3PC protocol divides the preparation phase of 2PC protocol into two, thus forming three phases:

The coordinator and participant waiting timeout situations are discussed separately. Let’s look at the basic process of normal situations first, otherwise it will be easy to be confused.

3.1 CanCommit Phase

In the 2PC preparation phase, after the coordinator sends instructions to the participants, if the participants meet the execution conditions, they will acquire locks and execute actions, but they have not actually submitted. It can be considered that the participants are just one step away from success and have to wait for the coordinator's signal. If it is a commit signal, it is fine. If it is a rollback signal, then it is a waste for some participants who have executed actions locally. So from this perspective, 2PC is a bit radical, but there is a reason for doing so. In a complex network environment, one more round of interaction means performance loss. 3PC is more reasonable. The coordinator first sends a query signal to the participants, asking if they have time, and then starts to collect feedback, which is lighter in comparison. At this stage, the participants do not actually acquire locks to occupy resources, but only check the status of their own transaction execution to see if they meet the conditions for executing the transaction, and then respond to the query.

Based on the participants' responses to the query, two situations may occur during the CanCommit phase:

A. All participants are ready

Figure: All participants in the inquiry phase are qualified to execute transactions

B. There are scenarios where participants are not OK

Figure: Unqualified participants in the inquiry phase

3.2 PreCommit Phase

The specific actions of the second stage depend on the results of the first stage, so it can be divided into two cases:

• CanCommit stage unanimously passed

In the first phase, all participants are ready, so the coordinator will send local execution instructions to the participants. This part is very similar to the first phase of 2PC. After receiving the instructions, the participants will execute local transactions, record logs, and feedback the processing results to the coordinator for decision-making. During the process, participants may succeed or fail. There are two situations:

Figure: All participants in the PreCommit phase reported success

Figure: Failure instances among participants in the PreCommit phase

Disagreement in CanCommit phase

In the first phase, if any participant is not ready, the coordinator will send a signal to all participants, informing them that the transaction is canceled and that they can continue with their work. The loss to the participants is not that great because they have not done anything in essence.

3.3 DoCommit Phase

This is the third phase of 3PC and is similar to the second phase of 2PC. The specific actions performed by DoCommit also depend on the result of the second phase PreCommit, so it is still divided into two cases:

• PreCommit stage unanimously passed

After PreCommit, all participants have completed their local transaction execution but have not committed it, and have all responded to the coordinator with an ACK. At this point, the coordinator thinks everything is ready, and in the DoCommit phase, the coordinator sends a commit command to the participants. After receiving it, the participants start executing the local commit and feedback the results, and finally complete the transaction. Cool!

• Disagreement in the PreCommit phase

After receiving feedback from participants in the second phase PreCommit, the coordinator finds that some participants are unable to execute the transaction. At this time, it decides to tell other participants to roll back locally, release resources, and cancel the transaction.

IV. Timeout strategy in 3PC

We mentioned earlier that 3PC is to solve the problem of participant blocking timeout in 2PC. In 2PC, participants are more infatuated. If the coordinator does not give a signal, it will be blocked for a long time and resources will not be released. In this way, others cannot handle other things. This is really not good. It seems that 2PC is still too dependent on the coordinator. 3PC believes that network timeout is a common situation. If participants perform some actions in a state with a high probability, it is also allowed, and they will not be subject to external military orders. 3PC's timeout processing may occur in the PreCommit and DoCommit stages. Let's take a look at the figure:

Participant timed out waiting for PreCommit

There may be a large network delay between the coordinator and the participants, or the coordinator may fail, or there may be a network partition. The participants will not wait foolishly. After the set time, the participants will continue to do their previous tasks, because it seems that they have been left out, so they can only do what they should do. This is also the correct decision.

Participant timed out waiting for DoCommit

After CanCommit and PreCommit, participants think that everyone is aligned and everything is great. If participants do not receive the DoCommit instruction from the coordinator within the set time, they will execute the commit locally to complete the transaction, because participants speculate that the big brother probably wants us to commit, and waiting is not a solution. The rollback may be different from everyone else's. Under the decision, participants choose to commit the transaction.

The coordinator has timed out waiting for feedback

The waiting timeout processing of the 3PC coordinator is basically the same as that of 2PC. No matter at which stage the timeout occurs, it is considered that the conditions are not met and an abort or rollback operation is performed. This is very easy to understand.

It can be seen that the participants in the 3PC protocol are no longer overly dependent on the command signals of the coordinator, but have their own relative independence and can make their own decisions based on the current state. It avoids the waste of resources caused by the blocking waiting in 2PC, which is indeed a good optimization, but we cannot guarantee that this optimization is completely correct! In other words, 3PC solves the bug of 2PC, but it does not mean that 3PC does not introduce new bugs.

5. Some analysis of 3PC protocol

We mentioned earlier that an important role of the 3PC protocol is to improve and optimize the 2PC protocol. From the above process analysis, we can see that some optimizations have indeed been made, but new problems are still inevitable.

5.1 3PC data inconsistency problem

The 2PC protocol has data inconsistency issues in certain scenarios, so does 3PC have this problem? The answer is yes, and the root cause is the newly added participant timeout mechanism. For example, due to its own network problems, participant A did not receive the coordinator's signal within the set time. At this time, participant A executed the Commit operation based on the previous state and submitted the transaction. This situation does happen, and different results will appear depending on whether the real coordinator signal is commit or rollback.

If the coordinator sends a Commit instruction, it will be consistent with the decision made by participant A alone, and there will be no problem. If the coordinator sends a rollback instruction during the DoCommit phase, the timed participant A will commit the local transaction, resulting in inconsistent data with other participants who received the instruction to execute the rollback.

5.2 Alignment of decision states

We know that in the initial stage of the 2PC protocol, only the decision maker knows the decision result. Only after it sends the decision solution, the participants know it. In this way, the decision result may be lost. If the coordinator hangs up, the new coordinator can consult all participants to determine the decision status, and determine it according to the situation of all participants, but what if the truth is in the hands of a few people?

Extreme Cases:

Suppose there are 10 participants, 9 of which are normal and 1 is in an unknown state (let's call it A). All 10 participants send feedback to the coordinator. If A sends back a Not Ready signal, the other 9 will send Ready signals. The coordinator summarizes the results and decides that the execution conditions are not met, and starts to send rollbacks to all participants. It happens that the first machine to receive the signal is A, and the coordinator crashes. A also crashes after receiving the signal. The new coordinator asks the other 9 and they are all OK. The new coordinator believes that the conditions are met and sends a Commit signal, which causes inconsistency.

Brain-opening:

This process is very similar to the emperor's appointment of a crown prince in Qing palace dramas. The emperor hangs the result on a plaque in the court. Assuming that the edict disappears and the emperor dies, the result will be unknown. The think tank needs to examine the situations of all candidates without any selfish motives to make a determination, which may lead to inconsistencies.

Transparency in decision making:

In 3PC, there is still a situation where only one machine receives the instruction and then hangs up, but if it occurs in the pre-stage, it will have no impact on the overall result because it will be cancelled and the participants will not execute it locally.

Now the idea of ​​3PC is to make the decision results when making major actions transparent and unified, so the impact will be very small, so the status of the PreCommit stage is clear.

We need to make the decision results transparent so that all participants know the decision results. The PreCommit phase of 3PC aligns the results. As long as one machine is still alive, the status of the entire transaction is certain. After all, the probability of all participants hanging up is very low.

6. Summary

The 3PC protocol is an optimization and improvement of the 2PC protocol. By dividing the preparation phase of 2PC into two: CanCommit and PreCommit, the flow of the next phase of the whole process depends on the result of the previous phase. The flow diagram is as follows:

After the CanCommit and PreCommit stages, the decision results are aligned and retained between the participants, which is a better practice to avoid the erroneous loss of decision results in extreme cases of the 2PC protocol.

In the 2PC protocol, only the coordinator has a timeout mechanism, while the 3PC protocol also introduces a timeout mechanism for participants, with different timeout processing at different stages. However, due to network fluctuations and network partitions, the timeout processing of participants brings new uncertainties, and even data inconsistency may occur.

The 3PC protocol adds a round of inquiry phase, so the entire interaction process is longer than 2PC, and the performance is slightly lower than 2PC, but the 3PC protocol does not handle network partitions and other situations very well.

In general, 3PC has made many improvements compared to 2PC and has achieved certain results, but there are still problems with data inconsistency, and more efforts are needed.