Shulou(Shulou.com)06/01 Report--

This article mainly explains "what problems have been solved by consistency algorithm Paxos". The explanation content in this article is simple and clear, which is easy to learn and understand. Please follow the idea of Xiaobian and go deep into it slowly to study and learn "what problems have been solved by consistency algorithm Paxos" together.

1: Consistency algorithm Paxos

Paxos algorithm is a message-passing and highly fault-tolerant consistency algorithm, which is recognized as one of the most effective algorithms for distributed consistency problems.

1.1 What problem did Paxos solve?

In common distributed systems, there are always communication anomalies, node failures, network partitions and so on. Paxos algorithm needs to solve the problem of how to quickly and correctly agree on the value of a certain data within the cluster in a distributed system where the above exceptions may occur, and ensure that no matter any of the above exceptions occur, the consistency of the whole system will not be broken.

Note: The value of a certain data here is not just a certain number in a narrow sense, it can be a log or a command. According to different application scenarios, the value of a certain data has different meanings.

1.2 Related concepts of Paxos

Proposal: Proposal information includes Proposal ID and Value

In the Paxos algorithm, there are three roles:

Proposer: Proposer advocates customer requests, tries to persuade Acceptor to agree on them, and acts as mediator in case of conflict to move the agreement forward

Acceptor: decision-maker, can approve proposals, Acceptor can accept proposals; if a proposal is selected, then the value in the proposal is determined

Learners: Learners who ultimately make decisions, learners who act as replicators of the protocol

1.4 Proposer Rules for Generating Proposals

Before a Proposer generates a proposal, it should first "learn" the value that has been selected or may be selected, and then use that value as the value of its proposal. If no value is selected, the Proposer can determine the value of value by himself. That's how we can reach agreement. This stage of learning is achieved through a Prepare Request.

The following figure shows the case where most Acceptor sets (more than half) do not receive proposals:

Proposer proposal generation algorithm:

The Proposer selects a new proposal number N and sends a request to a set of Acceptors (more than half) asking each Acceptor in the set to respond as follows:

(a)Promise the Proposer not to accept any proposal with a number less than N.

(b)If the Acceptor has accepted proposals, then it responds to the Proposer with the highest number of proposals less than N that have been accepted.

We refer to this request as a Prepare request numbered N.

If the Proposer receives more than half of the Acceptor responses, it can generate a proposal [N,V] with number N and Value V. where V is the Value of the proposal with the highest number of responses. If there is no proposal in all the responses, then V can be selected by the Proposer.

After generating a proposal, the Proposer sends it to more than half of the Acceptor set, expecting them to accept it.

We call this request an Accept request. (Note: The Acceptor set accepting the Accept request at this time is not necessarily the Acceptor set responding to the Prepare request before)

1.5 Acceptor Receive Proposal Rules

An Acceptor may receive two types of requests from the Proposer, namely Prepare requests and Accept requests. The conditions for responding to these two types of requests are as follows:

Prepare request: Acceptor can respond to a Prepare request at any time

Accept Request: Accept requests can be responded to arbitrarily without violating Accept's existing commitments.

Therefore, the Acceptor is constrained to accept proposals as follows:

p1a: An Acceptor can accept a Proposal numbered N as long as it has not responded to any Prepare requests numbered greater than N.

Acceptor algorithm optimization

From the above, if the Acceptor receives a Prepare request with number N, it has already responded to a Prepare request with number greater than N. According to P1a, the Acceptor is unlikely to accept proposal number N. Therefore, the Acceptor can ignore the Prepare request numbered N.

With this optimization, each Acceptor only needs to remember the maximum number of proposals it has approved and the maximum number of proposals it has responded to with a Prepare request.

1.6 Paxos algorithm description

Stage 1:

(a)The Proposer selects a Proposal Number N and sends Prepare Requests Number N to more than half of the Acceptors.

(b)If an Acceptor receives a Prepare request with number N, and N is greater than the number of all Prepare requests that the Acceptor has responded to, then it sends back to the Proposer as a response the proposal with the highest number (if any) that it has accepted, and the Acceptor promises not to accept any more proposals with numbers less than N.

Stage 2:

(a)If the Proposer receives more than half of the Acceptors responding to its Prepare request number N, it sends an Accept request for [N,V] proposals to more than half of the Acceptors. Note: V is the value of the proposal with the highest number in the received response. If the response does not contain any proposal, V is determined by the Proposer himself.

(b)If an Acceptor receives an Accept request for a Proposal with Number N, it accepts the Proposal as long as the Acceptor has not responded to Prepare requests with numbers greater than N.

1.7 Learner learning selected value

Three ways:

1.8 How to Ensure the Activity of Paxos Algorithm

Suppose there is such an extreme situation, there are two Proposers in turn put forward a series of increasing number of proposals, resulting in the final loop, no value is selected, the specific process is as follows:

Resolution: By selecting the main Proposer and specifying that only the main Proposer can propose a proposal. This way, as long as the master Proposer and more than half of the Acceptors can communicate normally, then any proposal proposed by the master Proposer with a higher number will eventually be approved, so that by selecting a master Proposer, the whole Paxos algorithm can remain active.

Thank you for your reading. The above is the content of "What problems have been solved by the consistency algorithm Paxos". After studying this article, I believe that everyone has a deeper understanding of what problems have been solved by the consistency algorithm Paxos. The specific use situation still needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.