This article belongs to reprint notes for knowledge review

preface

The Paxos algorithm is a message-based consistency algorithm proposed in 1990 by Leslie Lamport (“La” in LaTeX, who was at Microsoft Research). Paxos is currently recognized as one of the most effective algorithms for solving distributed consensus problems, and it is arguably the source of all distributed consensus algorithms in the past few decades. We see it all the time in blockchain.

When understanding PAXOS, it usually contains two important words: distributed fault tolerance and distributed consensus algorithm. What do you mean by those two words? What problem does Paxos solve?

  • Distributed fault tolerance: In a distributed environment, some nodes can be tolerated to break down and stable external services can be provided.
  • Distributed consensus algorithm: In a distributed environment, all nodes can reach a consensus on a value, that is, all nodes agree on a value.

Consensus is harder to penetrate, for example. Assume that client A and client B are simultaneously assigning to A variable X. Set X=1 on client A and X=2 on client B. The process of getting both A and B to agree that X is equal to 1 or X is equal to 2.

How to reach consensus? Paxos needs to be embodied

I met Paxos

Paxos abstracts three roles and two stages to help us understand

  • (a) the proposer (a proposer), the acceptor (a proposer), the learner (a proposer)
  • Phase: prepare phase, accept phase and learn phase

Proposal

In describing roles, we need to know what the proposal is first. In the PaxOS algorithm, a proposal is a value or an operation that needs to be agreed upon. Paxos encapsulates this into a proposal and generates a unique proposal number for it. Assume that [N, V] is used to represent a proposal, with N representing the proposal number and V representing the value of consensus.

(a) proposer

(A) The job of the proposer is to take the client request and encapsulate it into a proposal. And send the proposal to all acceptors. To control whether a proposal needs to be submitted based on the return of the acceptor, i.e., to save the proposal.

Acceptor

The job of an Acceptor is to participate in voting on a proposal and receive and process requests for both phases of PAXOS.

Learner

Learner does not participate in the proposal and vote, but passively receives the proposal results. Its existence can be used to extend read performance, or to read between regions.

Learners are not an important part of paxOS clusters because they do not directly participate or vote. As a result, you can fail or disconnect from the cluster without compromising the availability of paxOS services. The benefit for users is that learner is more able to connect through less reliable network links than acceptor. In fact, the learner can be used to communicate with a PAxOS server in another data center and write with minimal network traffic consumption because the number of messages required in the absence of a voting protocol is small.

Prepare stage

In the prepare phase, the proposer sends a PREPARE request to an acceptor, and the acceptor decides whether to respond to the request according to the convention. If an Acceptor approves the preparation request for a proposal [N,], it guarantees the following commitments to the proposer

  1. Acceptor pledges not to pass prepare requests for proposals whose number ** is less than or equal to **N
  2. An acceptor accepts an acceptor request for a proposal whose number is less than N
  3. If an acceptor accepts a proposal, it promises to return the maximum number of accepted proposals in its response to a PREPARE request. If no proposal is approved, NVL is returned in the response to the PREPARE request

(a) if a proposer sends a proposal number to a proposer, it will only send a proposal number [N,].

The accept stage

In the Accept phase, after the proposer has received most of the responses in the prepare phase, the proposer sends an accept request to an acceptor. For example, the proposal where the decision is made is [N, V], based on the promise the acceptor made to the proposer during the prepare phase.

  • If an Acceptor request does not pass a prepare request with a number greater than M, it will approve the proposal [N, V] and return the proposal with the largest number approved (that is, [N,]).
  • If an acceptor accepts a prepare request with a number greater than M, the acceptor rejects the proposal [N, V] and returns the proposal with the largest number (greater than N) that has been accepted.

A proposer counts the responses to the accept request it receives:

If the number in the response is the same as the number it issued, the acceptor is considered to have approved the proposal.

If a majority of acceptors approve the proposal, a consensus is reached on the proposal or the proposal is approved.

If a majority of acceptors do not approve the proposal, it goes back to the PREPARE phase for negotiation.

(a) Prepare (b) prepare (C) prepare (D) prepare (d) prepare (d) prepare (d) prepare (d) If the request is accept, then the proposer sends the proposal number and the proposal value, which is [N, V]. If the response to the PREPARE request contains proposals that have already been approved by some acceptors, then V is the proposal with the largest number in the response to the prepare request. If the response to the prepare request does not contain a proposal that has already been approved by some acceptors, then V is the proposal with the largest number in the response to the prepare request.

Learn stage

In the Learn stage, after a proposal reaches a consensus through PAXOS, acceptor informs Learner of the proposal results.

Initial description of the algorithm

The algorithm described is divided into two parts: proposal selection and proposal acquisition.

  • Proposal selection, paXOS goes from the creation of a proposal to how consensus is reached. It is the prepare phase and accept phase
  • Proposal acquisition, learner how to obtain and save the proposal, that is, the learn stage

Proposals for the selected

Let’s start with an easy-to-understand paxOS process,

Notification of variables

  • MinProposal: indicates the maximum number of a proposal approved by an acceptor in a prepare request
  • AcceptedProposal: Indicates the maximum number of a proposal approved by an acceptor in an accept request
  • AcceptedValue: Indicates the value of the maximum proposal number approved by an acceptor in an Accept request

Process explanation:

  1. First, generate a number n for the proposal. Here, ensure that the number is globally unique and incrementing. The specific implementation of the global number is not discussed here.
  2. (A) numbered ER broadcasts a prepare(n) request to all acceptors
  3. If n>minProposal, an acceptor executes minProposal=n and returns an acceptedProposal and an acceptedValue to its proposer.
  4. (a) If a proposer receives a majority of the replies and finds any acceptedValues returned, it considers the value of the proposal to be the one with the largest acceptedproposals among the replies.
  5. At this point you can enter the second phase, broadcasting accept (n,value) to all nodes.
  6. If n>=minProposal, acceptedProposal=minProposal=n, acceptedValue=value, local persistence, return; Otherwise, return minProposal.
  7. (a) If a proposer receives a majority request and finds a return value of result (minProposal) > n, it indicates that there is an updated proposal and jumps to 1. Otherwise value agrees.

In practice, of course, this is not as ideal as stated above. In fact, each proposer has the potential to produce more than one proposal, but as long as each proposal follows the algorithm, it will be executed correctly.

Proposals for

After reaching consensus on a proposal, how to let learner get the proposal is also a problem worth exploring. Generally, there are three conditions:

  • The easiest way to do this is to send a proposal to all learner once an Acceptor has approved it. Although this method can make the learner get the selected proposal as soon as possible, it requires each acceptor to communicate with all the learner one by one, and the number of communication is the product of the two, so the efficiency is low.
  • Select a master learner, if there is a proposal approved by the acceptor to notify the master learner, when the master learner is notified, by it to notify the other learner. Although this scheme has one more step, the communication times are greatly reduced, and the communication times are the number of learner. The scheme also leads to another problem: the main learner may malfunction at any time.
  • On the basis of scheme 2, a single master learner is expanded into a master learner set. The higher the number of learner in the collection, the better the reliability.

Simulation of algorithm

To get more familiar with PAxOS, let’s illustrate the proposal selection process in PAxOS. Assuming there is a paxOS cluster with three nodes, it is important to note that each node can act as a proposer and an acceptor at the same time. As follows

ProposerA gets a request and sets X to 3, proposerB gets a request and sets X to 5. ProposerA and proposerB generate proposals for this, with proposerA’s proposal number 1 and proposerB’s proposal number 2. In the prepare phase, they interact with the following results:

  1. ProposerA and proposerB enter the prepare phase and send the proposal number to each acceptor.
  2. After receiving the prepare request from proposerA, acceptorA and acceptorB have neither passed any prepare request nor approved any accept request. ProposerA returns no proposal.
  3. Because acceptorC received a prepare request from proposerA after receiving a prepare request from proposerB, and proposerB’s proposal number was larger than proposerA’s, it did not return a prepare response to proposerA.
  4. After receiving a prepare request from proposerB, an acceptorA and an acceptorB compare their proposal numbers because they received a prepare request from proposerA before. Since proposerB’s proposal number is larger than proposerA’s, If no accept request is passed, it returns no proposal to proposerB and guarantees proposerB the three promises mentioned above.

Thus, proposerA gets 2 prepare responses and proposerB gets 3 prepare responses. They both receive prepare responses from most of the nodes, so they start the Accept phase.

  1. Since there is no proposal value in the prepare response received by proposerA, it arbitrarily sets the proposal value, that is, [1, 3]. And sends accept requests to each acceptor.
  2. AcceptorA, acceptorB and acceptorC will not accept proposerA’s accept request, since they all promised proposerB the above three promises during the prepare phase. And return the largest proposal number passed in the prepare stage to proposerA, that is, [2,].
  3. When proposerA receives [2,] and finds that the proposal number 2 in the response is larger than its proposal number 1, it considers that the proposal is not accepted. ProposerA needs to go back to the prepare stage for negotiation.
  4. ProposerB sets the proposal value as he chooses because the prepare response he receives does not have any proposal value, that is [2, 5] And sends accept requests to each acceptor.
  5. AcceptorA, acceptorB, acceptorC, during which neither prepare nor Accept requests are passed, that is, the proposal is approved and returned to proposerB [2,].
  6. – After receiving the accept response, proposerB compares the proposal numbers and finds that most of the proposal numbers are his own, so he considers the proposal to be a consensus and the negotiation process is complete

The above process mainly describes the two commitments that accept makes to a proposer if the acceptor passes the request for preparation of proposal [N,]

  • An acceptor undertakes not to pass prepare requests for proposals whose number is less than or equal to N
  • An acceptor accepts an acceptor request for a proposal whose number is less than N

So here’s another promise:

  • If an acceptor accepts a proposal, it promises to return the maximum number of accepted proposals in its response to a PREPARE request. If no proposal is approved, NVL is returned in the response to the PREPARE request

To better describe this commitment, we can imagine a scenario like this. After proposeB completes the prepare request, it initiates the accept request, and the proposal is [3, 6]. In this process, proposeA initiates a PREPARE request with the proposal number [4,] and an acceptor receives a PREPARE request from proposeA first. That is to say, an acceptor rejects the accept request from proposeB

  1. ProposerB initiates an accept request with the proposal [3, 6].
  2. – acceptorA receives an accept request from proposerB and approves it
  3. ProposerA initiates a prepare request and the proposal is [4,].
  4. AcceptorB and acceptorC received a prepare request from proposerA. ProposerB’s accept request is rejected.
  5. AcceptorA receives a prepare request from proposerA. Since it received the accept request from proposerB, it returns an approved proposal to proposeA [3, 6].
  6. (a) If proposerA receives a majority of prepare responses, it initiates an accept request. (A) If proposerA receives a proposal [3, 6] from an acceptorA, then its proposal value can only be 6, [4, 6].
  7. Accept Completes the negotiation.

Multi – paxos algorithm

The original PAxOS algorithm (Basic PaxOS) can only accomplish a consensus value. The Lamport master mentioned that you can implement a common set of values by executing basic-Paxos multiple times. However, multiple consultations increase communication and affect the activity of negotiations.

The master proposed the solution of multi-Paxos, but the master did not explain the multi-Paxos clearly, but only introduced the general idea without the necessary details of the algorithm process. So this leaves a lot of room for imagination, and as a result, the multi-PaxOS implementation will be different.

In general, multi-PaxOS makes two improvements based on basic-PaxOS:

  1. Among the Proposers, a Leader is elected. The Leader uniquely submits a Proposal to the Acceptors for a vote. This solves the live lock problem without a Proposer competition. If there is only one Leader in the system to commit the Value, the Prepare phase can be skipped. In this way, the two phases are changed into one phase to improve efficiency.
  2. For each value to be determined, the Paxos algorithm Instance is run once to form a resolution. Each Paxos Instance is identified by a unique Instance ID.

Firstly, the multi-paxos needs to elect a leader. The master mentioned that the leader can be elected through basic-paxos.

  • After the leader is elected, only the leader can make proposals.
  • After the leader is down, services are temporarily unavailable until the leader is elected again.
  • If there is only one leader to submit a proposal, the prepare phase can be skipped.

Multi-paxos changes the scope of the prepare phase to all instances to be submitted by the leader, so that the leader only needs to execute the prepare phase once and only the Accept phase later. In this way, the two phases are changed into one phase and efficiency is improved. To distinguish between multiple instances that are submitted consecutively, each instance is identified by an instance ID that is locally incrementally generated by the leader.

Multi-paxos allows multiple nodes that consider themselves as leaders to submit proposals concurrently without affecting their security. In such a scenario, basic-Paxos is degraded.

This article is adapted for personal records

Concurrent notes: Distributed Conformance Protocol – Paxos

The description

WF Warp Future: Paxos Algorithm as the core algorithm of blockchain

Diagram distributed consistency protocol Paxos

Half an hour to learn what a distributed consistency algorithm is — Paxos

And then Paxos