1, the introduction of

• Paxos consensus algorithm is a kind of non-Byzantine fault tolerant algorithm, which is used to solve the consensus problem of distributed fault behavior but no malicious behavior
• Is a strong consistency model that requires more than half of the reads or writes to be successful.
• The most commonly used consensus algorithms such as Fast Paxos algorithm, Cheap Paxos algorithm, Raft algorithm, ZAB protocol and so on are improved from Paxos algorithm
• There are two types of Paxos algorithms
  • Basic Paxos algorithm: describes how multiple nodes betweenA valueReach a consensus on the Value of the proposal
  • Multi-paxos idea: describes the execution of multiple instances of Basic PaxosA set of valuesReach a consensus

2. State machine replication

What exactly is guaranteed consistency? 1. Generally speaking, distributed consistency solutions are solved by state machine replication. For example, each operation is a log, and each node has its own operation log.

2. When the logs are consistent, the same log sequence is input to the same state machine and output to the same result.

About state machines

• The goal of a state machine is to get the same output from the same sequence of inputs. For example, each server runs the same same state machine S, and then each state machine starts at the initial state S0, and then these state machines computeSame input sequencefor{x0, x1, x2, x3, ... xn}, then these state machines must go through the same state transition process as:S0->S1->S2->S3... SnIn the endSame state Sn, and outputSame result sequenceTo:{out1(S1), out2(S2), out3(S3), .... outn(Sn)}.

For example, if you have the following input sequence (from top to bottom), as long as each server has the same state machine and the state machine is in the same state before processing the input sequence, they will eventually reach the same state after going through the state machine, such as throughInstructions to replaySo if you go through the input sequence and a is equal to 4, and B is equal to 3, you get to the same state.

3. Base Paxos algorithm

3.1 Decision model

• The Client (Client) :
  • Responsible for initiating read and write requests
• Proposal (the Proposer) :
  • Responsible for initiating an internal response to a client requestThe proposalUsed for voting.
  • It represents the access and coordination function. After receiving the client request, it initiates the two-stage submission and carries out consensus negotiation.
• The receiver (Acceptor) :
  • Responsible for voting on each proposal, and local storage of their voted proposals
  • Representatives vote to negotiate and store data, vote on the proposed value, and accept the consensus value, store and save;
• Learners (Learner) :
  • Store the vote result of the proposal (i.e. the consensus result) after the vote is passed
  • Indicates stores data, does not participate in consensus negotiation, only accepts the agreed values and saves them.

General consensus negotiation process:

• At one stage, the client wants to initiate a proposal toProposed the Proposer(for example, a write request set a=3, etc.), and then the proposer makes a proposal request such as [1, NULL] to pass to the first oneThe recipient of the AcceptorAnd then copy the proposal request to others based on the state machine replication modelThe recipient AccpetorA stage readiness request is successful when more than half of Acceptor acceptors respond to allow a proposal to be sent. Then the proposer starts the second stage. The proposer sends the proposal id and its content (such as [1,3]) to Accpetor, the receiver. Then, the proposer also sends more than half of the responses to indicate that the proposal is approved.

3.2 How to reach a consensus on Base Paxos

• Is through theProposal (the Proposer)initiateTwo-stage submissionTo complete a consensus negotiation,

One stage is called the preparation stage:

• 1)Prepare request stage:
  • Basically, the proposer issues a proposal preparation request with proposal number N greater than the proposer’s previous proposal number (ensure that the proposal ID is globally unique and incremented).
• 2) The Promise preparation and response stage
  • It is primarily up to the receiver to decide whether to respond to the proposer’s proposal or not. If the current proposal is smaller than any proposal number previously accepted by the receiver, it is rejected. Otherwise, it is accepted and responded

The second stage is called the acceptance stage

• 1)Accept request stage:
  • After the proposer has received more than half of the responses from the recipient, it enters the second phase and starts sending the proposal acceptance request. The proposal contains the number and details of the proposal
• 2)Accepted response stage
  • It is primarily up to the receiver to decide whether or not to accept the proposer’s proposal. If the current proposal is smaller than any proposal number previously accepted by the receiver, it is rejected, otherwise it is accepted.

[Negotiation Rules]

• The receiver will not accept proposals that are less than the ID of the proposal it currently guarantees
• The proposal ID needs to be globally unique in order to incrementKeep your proposal organized

3.2.1 Case 1: Consensus on a single proposal

A phase

• inPrepare Prepares the request phase, proposer P sends A proposal with proposal ID 1 to three recipients A, B, and C(null because there is no need to carry proposal content at this time).
• As shown in Figure 1, the three recipients received the first-stage proposal request of proposer P at 2, 3 and 4 points respectively.
• Figure 2. Because recipients A, B, C are not locally availableGuarantee or no bill has been passed(if both are null), so the responder says they can accept proposals with this ID, stores them locally, and promises not to accept proposals with a smaller id.And sends a Promise in response to the request(If no proposal was previously guaranteed or approved locally, the response is empty, that is, there is no proposal, otherwise the response is approvedBill/id, value]). When proposer PMore than half were receivedAfter the Promise prepares for the success of the response stage, as shown in Figure 2, there are 3 more than half, and the Promise can enter the next stage[Acceptance stage].

Two stage

• Since most of the recipients’ promises were received before the response was ready to enterAccept Indicates the request acceptance phase.start the acceptance request, and this time with the proposal content, butContent of the proposalThe value of the proposal with the largest proposal number will be used as the content of the proposal in the response content of the first-stage Promise preparation. As shown in Figure 2, since recipients A, B, and C have not approved any proposal locally before, the response of “[no proposal]” is returned, which is actually empty in the prepared response. Therefore, I took my proposal value of 3 as the content of this proposal.
• In the acceptance and response stage of Accepted, as the proposal number 1 of the proposal is not less than the proposal ID that has been locally guaranteed or approved by receivers A, B and C, the proposal [1,3] is passed and the write value of 7 is Accepted, and the three nodes reach A consensus on this

3.2.2 Case 2: Concurrent proposal reached consensus

In the preparation request stage of the first stage, proposer P initiates the proposal [1: NULL] first. After receiving the proposal at time points 1 and 2, recipients A and B will guarantee the proposal and not respond to proposals smaller than the proposal ID [1] because there is no approved proposal locally. Subsequently, the time line proposer Q at 3 o ‘clock also initiates A proposal [6, NULL], and receivers A, B, and C receive the request at 3 o ‘clock, 4 o ‘clock, and 5 o ‘clock respectively. Since the current proposal 6 is larger than the proposal 1 locally guaranteed by receivers A and B, receivers A and B will change the guaranteed proposal to 6. Recipient C has no local approved proposal and no guarantee of any proposal, so he will accept the proposal and update the guarantee proposal to 6. Subsequently, at point 6, receiver C receives a proposal request from proposer P [1, NULL] and rejects Proposal 1 because receiver C has guaranteed that proposal 6 will not respond to proposals smaller than proposal 6.

In the first-stage Promise preparation and response stage, since recipients A, B and C have not approved any proposal locally, the content of the response to proposer P and Q is no proposal yet (but if the proposal has been approved, the approved proposal [ID,value] will be used as the response content).

In the two-stage Accept request stage, proposer P received two responses from receiver A and receiver B. Therefore, more than half of the recipients responded, so we can start the phase 2 submission request phase and use the value of the proposal with the largest proposal number in the response as the value of the proposal in the phase 2 acceptance request. Since the response of receivers A and B is empty (i.e., there is no proposal), the value of their proposal 3 is taken as the value of the proposal and the acceptance request of proposal [1, 3] is sent to receivers A, B, and C. After receiving three response requests, the proposer Q will also enter the second stage, and the value of the proposal with the largest number in the response will also be used as the value of the proposal in the second stage. Since the response of receivers A, B, and C is empty, the proposal value 7 is used as the proposal value and the accept request with proposal [6, 7] is sent to receivers A, B, and C.

In the second-stage Accepted response stage, receivers A, B and C first receive the proposal [1,3] of the proposer P’s acceptance request, but since the id of the proposal 1 is smaller than the proposal 6 they guarantee, the proposal [1,3] will be rejected by receivers A, B and C. Then receivers A, B, and C receive the acceptance request [6,7], proposal number 6 is not less than the guaranteed proposal 6, so the proposal [6,7] is adopted, that is, the value 7 is accepted, and the three receivers reach A consensus on the value 7.

3.2.3 Case 3: Live lock problem under concurrent proposal

• In fact, each nodeIt can be either the proposer or the receiverBecause each node can be responsible for read and write requests. The node that receives the write request initiates the proposal as a proposer, and the other nodes vote as receivers. Therefore, it is possible for multiple proposers to initiate proposals at the same time, resulting in a live lock problem
• The live lock problem is when all proposals are rejected and continueWe know that the recipient will reject the current proposal if it is smaller than the current guaranteed proposal. The reason for the life lock is that under the concurrent proposal, the current proposal only completes the first phase request, and before it is ready to enter the second phase request, the proposal is overwritten by the higher level proposal issued by other proposers. Later, the request for the second phase was rejected. If this loop continues, it will create a live lock.
• Let’s say recipient A experiencesPhase ONE of Proposal [1] Phase two of Proposal [1] => Phase two of Proposal [3] => Phase two of Proposal [4] Phase two of Proposal [3].....If recipient A goes through these state transitions, then proposals 1, 2, and 3 will all be rejected by recipient A. And the same way that crosses over and over again recipient A can never accept the proposal.

4 Multi Paxos ideas

• Basic Paxos can only agree on a single value at a time and is prone to live locks under concurrent proposals
• Instead of the proposer sending a proposal request to each recipient individually, we send one recipient and it replicates and synchronizes to the other recipients. So BasePaxos only has replication, and both phases need to be replicated, resulting in too many RPC calls.
• Multi Paxos idea is divided into two Basic Paxos,The first Basic Paxos was called elections.The second Basic Paxos is called replicationTo elect a leader, consensus is reached through a Basic Paxos. The leader is introduced as the only proposer to solve the problem of proposal conflict. Then all the acceptors are subject to the leader’s proposal. Instead of going through the preparation phase, the commit phase goes directly to the two-phase phase, bypassing the process of state replication.

Elections:

• Recipients send out proposals internally and vote to choose the leader. The process of election and negotiation is also a Base Paxos model (roughly the same as above), and a new leader is elected after two-stage submission

copy

• After the leader is elected, the proposer sends all the proposals to the leader, and the leader alone decides whether to approve the proposals. After the proposal is passed, the leader copies and synchronizes the proposal to other recipients to accept it directly