Distributed system basic (V) protocol (I)

1 Atomic submission (Atomic commit)

There are many processes in our distributed system ,p1,p2,p3...pn, We hope that every process can know what it should do , meanwhile , We also hope that each process can keep synchronized , Perform the same transaction , This is called Submit (commit). If a transaction is committed , Then all processes will know , And perform operations . for example ： Maintain the consistency of each copy of the database . In the process , We have one of the biggest problems , be called error (fault), We may make many mistakes . There are two kinds of mistakes ：

1. Crash failures： The system stops working
2. Byzantine failures: A Byzantine process can do anything , Even malicious system failure , such failure Better than the first crash failures Even worse

An atomic commit means that all processes commit or not commit at the same time . In an asynchronous system , Even if there is one, there is one crash failure, Consistency is also unattainable ( according to FLP principle ). And for a system in a broad sense , We also cannot judge whether a process is implemented very slowly or crash failure 了 .

2 nature

AC 1 All processes reach a decision （reach decision）, Then it must be the same decision

AC 2 The process cannot return to the previous decision

AC 3 Only when all processes vote "yes" yes , To submit (commit)

AC 4 If it doesn't exist failure, And all processes are invested in “yes”, Then this decision must be commit

3 Two-phase commit(2PC)

two-phase commit The protocol is the simplest atomic submission Protocol , It is safe but not active ( namely , Not always at work ). In this Agreement , We have two roles ：coordinator and participants.coordinator To all participants Send voting request information , be-all participants Send their votes to coordinator. If it is "no" that participant direct abort, If it is “yes”, Then participant wait for coordinator The response of the . When coordinator After receiving all the votes , If it's all “yes”, To all participants send out “COMMIT” news , If there is “no”, Then it throws “yes” Of participants send out “ABORT” news .

Now we know two-phase commit How it works , But in real life, faults often occur , Let's assume some faults . for example ： Some participan Didn't receive coordinator To ask for a vote (vote request), Then it waits for the time to end , Then it will ABORT, According to the agreement , The whole system will ABORT.

If coordinator Failed to send decision news , Then we will be stuck in the last stage ,participant I don't know whether I should COMMIT still ABORT.

So we have two solutions to this problem ：

1. Cooperative Termination Protocol
2. Recovery Protocol

First option Cooperative Termination Protocol, When one participant When you don't know what to do ( I don't know I should COMMIT still ABORT), It tells others it knows participants Broadcast inquiry , If you know something, you will tell it coordinator The choice of

The core idea of the second plan is ： Suppose a process crash 了 , We can solve this problem by restarting crash. In order to know the previous state after the process restarts , We need logs to record , This log is called ：DTLOG. in general , The function of this log is to save decisions ： If participant vote “yes”, Then before sending a message , You must write to the log . If you vote “no”, Then write the log before and after sending the message . If coordinator Send the COMMIT Words , It must be recorded before sending , If it is ABORT Words , Before and after sending .

thus , We can get another AC：

AC 5 Perform any considering failure The algorithm of , At any time of execution , When failure Repaired , And it hasn't been new for a while failure, Then all the processes are finally decided .

4 Logging

It will be described in detail here DTLog Function and function of . We use according to the following rules DTLog, We will abbreviate Coordinator by C,Participant by P.

1. When C When sending a voting request , stay DTLog Write on Start2PC. Including each participant Of id, And it can be written before or after sending log. It's interesting if you write before sending , Then if you write it right away crash 了 , No time to send vote request, So when you recover , You check log, You can see participant Of id list , So your state can be restored . And if you choose to write after sending , When the result is sent crash 了 , Didn't have time to write , Then after recovery, you can't log Find anything , You will send ABORT, It's also safe .
2. If P vote “yes” Must be written before sending DTLog, because , If you write after sending , Then if you send it immediately crash 了 , Write what doesn't come log, So after you recover , You say you can't be in your log Find out what you invested before , Then you will execute ABORT, however , The fact is that you may have voted “yes”, And everyone voted “yes”, At this time, other processes may be executing COMMIT. If P vote “NO” In this case, you can record before and after sending
3. If C decision COMMIT, It must be sent before log Write in COMMIT, If it is ABORT Before and after sending
4. On receiving decision after ,P To write it log