Talk: How to explain 3PC to your girlfriend?

After a pleasant hotpot meal, I went home leisurely, and then started a new round of family science education.

Distributed Consistency

However, we still need to briefly explain the background. We have introduced the restaurant kitchen as an example:

With the development of the restaurant, it gradually evolved from having only one chef to having multiple chefs, and then to having multiple positions such as vegetable washers, food preparers, and chefs.

When there are multiple divisions of labor, it is necessary to coordinate the cooperation among these people.

For example, if a customer orders a dish of fried tomato and eggs, the kitchen staff will start to prepare it, the vegetable washer will start to wash the tomatoes, the side dish chef will start to prepare the eggs, and the chef will start to add oil to the pan to prepare the dish. This is a very normal situation.

However, if the message is not conveyed properly, or the vegetable washer is temporarily not in the kitchen, some people will have started preparing, but some will not.

This is like a distributed system. When we place an order on an e-commerce website, multiple distributed services are needed to serve simultaneously, such as the payment system for payment, the red envelope system for red envelope deductions, the inventory system for inventory deductions, and the logistics system for updating logistics information.

However, if one of the systems fails during execution, or does not receive the request due to network reasons, the entire system may be inconsistent, that is, the money is paid, the red envelope is deducted, but the inventory is not deducted.

This is the so-called data consistency problem of distributed systems.

In order to solve the distributed consistency problem, people have proposed many solutions, among which 2PC and 3PC are more important. We have introduced 2PC before, which is actually equivalent to introducing a coordinator in the back kitchen, who is responsible for coordinating all participants.

The algorithm idea of ​​the two-phase commit is to introduce a coordinator in the distributed system. Participants notify the coordinator of the success or failure of the operation, and the coordinator decides whether each participant should submit or terminate the operation based on the feedback information of all participants.

Then the whole operation is divided into two stages: the first stage: preparation stage (voting stage) and the second stage: submission stage (execution stage)

However, 2PC also has some disadvantages, such as synchronization blocking, single point failure, and inability to 100% guarantee data consistency. Therefore, people proposed the 3PC algorithm based on 2PC.

Three-phase commit

In the case of many problems with the two-phase commit (2PC), people proposed the three-phase commit (3PC), which is mainly used to solve some problems of 2PC (but it should be mentioned here that 3PC does not completely solve all the problems of 2PC).

There was a guy who wanted to play Honor of Kings with five other players, so he started contacting his friends.

When you use the 2PC algorithm to call friends to play together, the following things will happen:

Organizer: Xiao A, we are going to play King of Glory. If you can come and join us, please log in to the game now and then reply to me with a message on your game friends.

Xiao A logs into his game account and tells the organizer: Xiao A is in place.

Organizer: Xiao B, Xiao C, Xiao D, we are going to play King of Glory. If you can come and join us, please log in to the game now and then send me a message on your game friends page.

Little B, Little C, and Little D log into their game accounts respectively, and then tell the organizer: Little B, Little C, and Little D are in place.

The organizer found that everyone was in place, so he notified everyone one by one on the game.

Organizer: Xiao A, I invite you, please come in.

Xiao A accepts the invitation

Organizer: Xiao B, Xiao C, Xiao D, I invite you, please come in.

Little B, Little C, Little D accept the invitation

Next, let’s see what will happen if we use the 3PC method to organize a five-player King of Glory game:

Organizer: Xiao A, we want to meet at 8 o'clock in the evening. Are you free? If you are free, just say YES. If not, just say NO. Then I will ask other people. During this time, you can do your own things and don't have to wait for me.

Xiao A: Okay, I have time.

Organizer: Xiao B, Xiao C, Xiao D, we want to set a time at 8pm to play King of Glory with five guys... You don't have to keep waiting for me.

The organizer collects everyone's time information and notifies everyone again when everyone is available. (The coordinator receives all YES instructions)

Organizer: Xiao A, we have confirmed that King of Glory will be played with five players at 8pm. You need to make some time available and you can’t schedule anything else. Then I will notify other friends one by one. After that, I will come to confirm with you. Also, if I don’t call you specifically, you just need to log in at 8pm. By the way, are you sure you can come?

Xiao A set the alarm for 8 o'clock in the evening, and then told the organizer that he could go.

Organizer: Xiao B, we have decided to play King of Glory with five players at 8 o'clock in the evening... You just need to log in at 8 o'clock.

After the organizer notified everyone, all his friends told him, "I have cleared the 8 o'clock time slot." So, at 8 o'clock that day, he called them one by one and told them, "Hey, you can log in now..."

Little A, Little B, Little C, Little D: I'm already logged in, please pull me.

The organizer invites A, B, C, etc. to join the game.

The above process is a typical three-stage submission (3PC) process. Compared with 2PC, 3PC has one more step, which is to ask all participants in advance whether they can participate, and notify everyone to log in to the game again after everyone agrees.

The so-called 3PC is to divide the preparation phase of 2PC into two again, forming three stages.

In the first phase, all participants are only asked whether they can perform transaction operations, and transaction operations are not performed in this phase. When the coordinator receives YES responses from all participants, transaction operations are performed in the second phase, and then commit or rollback is performed in the third phase.

In this way, the three-phase commit has three stages: CanCommit (transaction inquiry), PreCommit (transaction execution), and DoCommit (transaction commit).

3PC Processing

Compared with the two-phase commit, the three-phase commit mainly inserts a preparation phase into the first and second phases of 2PC, ensuring that the states of all participating nodes are consistent before the final commit phase.

Next, let’s take a look at the specific implementation process.

CanCommit

The CanCommit phase of 3PC is actually very similar to the preparation phase of 2PC. The coordinator sends a commit request to the participant, and the participant returns a Yes response if it can be committed, otherwise it returns a No response.

1. Transaction inquiry: The coordinator sends a CanCommit request to the participant, asking whether the transaction commit operation can be performed. Then it starts waiting for the participant's response.

2. Response feedback: After receiving the CanCommit request, under normal circumstances, if the participant believes that the transaction can be successfully executed, it will return a YES response and enter the preparation state. Otherwise, it will return NO.

PreCommit Phase

The coordinator decides whether to perform the PreCommit operation of the transaction based on the responses of the participants in the CanCommit phase.

If the coordinator receives YES responses from all participants, the transaction pre-execution is performed:

1. Send a pre-commit request: The coordinator sends a PreCommit request to the participant and enters the Prepared phase.

2. Transaction pre-commit: After receiving the PreCommit request, the participant will perform the transaction operation and record the undo and redo information in the transaction log.

3. Response feedback: If the participant successfully executes the transaction operation, an ACK response is returned and the participant starts waiting for the final instruction.

If any participant sends a NO response to the coordinator, or if the coordinator does not receive a response from the participant after a timeout, the transaction is interrupted.

1. Send an interrupt request: The coordinator sends an abort request to all participants.

2. Interrupt transaction: After the participant receives the abort request from the coordinator (or after timeout, still no request from the coordinator is received), the transaction is interrupted.

doCommit phase

This phase is where the actual transaction is committed, and can be divided into the following two situations.

If the coordinator receives ACK responses from all participants after the transaction is executed, the following happens:

1. Send a commit request: When the coordinator receives the ACK response from the participant, it will enter the commit state from the pre-commit state and send a doCommit request to all participants.

2. Transaction commit: After receiving the doCommit request, the participant executes the formal transaction commit and releases all transaction resources after completing the transaction commit.

3. Response feedback: After the transaction is committed, an Ack response is sent to the coordinator.

4. Complete the transaction: After the coordinator receives the ack responses from all participants, the transaction is completed.

If the coordinator does not receive the ACK response sent by the participant (it may be that the recipient did not send an ACK response, or the response may time out), then the transaction will be interrupted.

1. Send an interrupt request: The coordinator sends an abort request to all participants

2. Transaction rollback: After receiving the abort request, the participant uses the undo information recorded in phase 2 to perform the transaction rollback operation and releases all transaction resources after completing the rollback.

3. Feedback result: After the participant completes the transaction rollback, it sends an ACK message to the coordinator

4. Interrupt transaction: After the coordinator receives the ACK message fed back by the participant, it interrupts the transaction.

There is another situation. If the participant cannot receive the doCommit or abort request from the coordinator in time, it will continue to commit the transaction after waiting for a timeout.

The above is the operation process of the three main stages of 3PC.

How is 3PC better than 2PC?

1. Reduce synchronization blocking.

In 3PC, participants are not allowed to execute transactions directly in the first phase, but only in the second phase. This greatly reduces the probability and duration of blocking. In addition, in 3PC, if a participant does not receive a message from the coordinator, he will automatically execute the commit of the transaction after waiting for a period of time, instead of being blocked all the time.

2. Improved data consistency

There is a situation in 2PC that will cause data inconsistency. For example, in the second phase of 2PC, after the coordinator sends a commit request to the participants, a network anomaly occurs and only some participants receive the commit request. After receiving the commit request, these participants will execute the commit operation. However, other machines that have not received the commit request cannot execute the transaction commit. As a result, the entire distributed system has data inconsistency.

This situation is well solved in the 3PC scenario, because in 3PC, if the participant does not receive the message from the coordinator, it will not be blocked all the time, and after a period of time, it will automatically execute the transaction. This solves the problem that after the coordinator sends a commit.

In addition, 2PC has another problem that cannot be solved. That is, if the coordinator crashes after sending the commit message, and the only participant who received this message also crashes at the same time, then even if the coordinator generates a new coordinator through the election protocol, the status of this transaction is uncertain, and no one knows whether the transaction has been committed.

This situation can be solved in 3PC, because in 3PC, after the new coordinator is selected, he can consult the status of all participants. If any one is in the commit state or prepare-commit state, he can notify all participants to execute the commit, otherwise he will notify everyone to rollback. Because once a machine executes the commit in the third stage of 3PC, it must be that everyone in the first stage agreed to commit, so you can rest assured to execute the commit.

Problems that 3PC cannot solve

In the doCommit phase, if the participant cannot receive the doCommit or abort request from the coordinator in time, it will continue to commit the transaction after waiting for a timeout.

Therefore, due to network reasons, the abort response sent by the coordinator is not received by the participant in time, so the participant executes the commit operation after the waiting timeout, which results in data inconsistency with other participants who received the abort command and executed the rollback.

Therefore, we can conclude that neither the two-phase commit nor the three-phase commit can completely solve the distributed consistency problem.

Mike Burrows, the author of Google Chubby, said:

there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos.

This means that there is only one consistency algorithm in the world, and that is Paxos. All other consistency algorithms are incomplete versions of the Paxos algorithm.