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

This article mainly explains "what are the knowledge points related to Paxos protocol". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what are the knowledge points related to Paxos protocol".

You may have heard of the Paxos protocol on various occasions. After all, this groundbreaking protocol is the ancestor of many distributed protocols. For example, the more famous Raft protocol is based on the Paxos protocol. In reality, there are also many products that use Paxos protocol, such as Google's Chubby,Spanner,IBM 's SVC and so on. However, in the process of learning, the author found that there are many people who introduce the Paxos protocol, but few can really explain it clearly. Therefore, the author specially spent some time to study the Paxos protocol, and now the learning results are analyzed as follows.

Role

There are five roles in the Paxos protocol: client, acceptor, proposer, learner, and leader. However, in the actual implementation, a service may play one or more roles at the same time, which is considered to reduce message latency and the number of messages, and improve the efficiency of the entire Paxos protocol.

Client

Client refers to the initiator of the request. Client sends the request to the distributed system and waits for a reply.

Acceptor (Voters)

The Acceptor can be thought of as a memory for message requests. Generally speaking, Acceptors consists of a certain number of services. When a message is sent to Acceptor, the message will be stored only if most of the Acceptor confirms that it is received, otherwise the message will be discarded.

Proposer

Proposer can be seen as an agent for Client. Proposer sends a message request for Client to Acceptors and waits for confirmation from Acceptors. When a message conflict occurs, Proposer will try to resolve the conflict.

Learner

Learners can be regarded as the executor of all acknowledged messages. Once the message request of Client is confirmed by Acceptors, Learners will do the corresponding processing (for example, execute the message content and send a reply to Client). There can be multiple Learner.

Leader

Paxos needs a Leader to ensure that the distributed system can proceed step by step. The Leader here is actually a Proposer, and the Paxos protocol ensures that only one Proposer will be treated as a Leader.

Proposal Number & Agreed Value

Proposal Number is also called proposal number, and we use n to indicate that for each Proposer, each proposal number is unique.

Agreed Value is also called the exact value, and we use v to express it, and v is the value confirmed by Acceptors.

The combination of the two values is (npendium v).

Basic Paxos

There are many variants of the Paxos protocol. Here we will first introduce Basis Paxos, and we will continue to introduce other Paxos protocols in a later article. Of course, since it is the basic Paxos protocol, it is easy to understand other Paxos protocols.

In the Basic Paxos protocol, there are many execution processes, each of which produces a separate execution result. There are many rounds in each execution process, and each round has two stages.

Stage 1

Stage 1A:Prepare

In the Prepare phase, a Proposer creates a Prepare message, and each Prepare message has a unique proposal number n. N is not the content of the proposal, but just a unique number that marks the message of the Prepare.

N must be larger than all the numbers previously used by the Proposer, and generally speaking we can implement this number by incrementing numbers.

Proposer then sends the number to Acceptors, which is considered successful only if most Acceptors receives a message from Proposer.

Stage 1B:Promise

All Acceptors are waiting for a Prepare message from Proposers. When an Acceptor receives a Prepare message from Proposer, there are two situations:

The n in this message is the largest of all Prepare messages received by Acceptor, so the Acceptor must return a Promise message to Proposer, telling it that I will ignore all subsequent messages less than n. If the Acceptor has acknowledged a message at some point in the past, it must return the proposal number m and accepted value w of that message. If the Acceptor has not acknowledged any messages in the past, it returns NULL.

If the n in the Prepare message is less than the message received by the Acceptor, the message will be ignored by the Acceptor (for optimization, you can also return a reject message to Proposer, telling it not to send me any more messages less than n).

Stage 2

Stage 2A:Accept

If a Proposer receives enough Promises from Acceptors (> Accept 2), this means that the Proposer can start the phase of the next Accept request, where the Proposer needs to set a value and then send the Accept request to the Acceptors.

As we talked about in phase 1B, if Acceptor has previously confirmed the message, the message number and the value of the message (mforce w) will be returned to Proposer. After receiving messages returned by multiple Acceptors, Proposer will select the value z corresponding to the message with the highest number and send it to Acceptor as the value of the Accept request (NMague z). If none of the Acceptors acknowledges the message, then the Proposer can choose the value z to confirm.

Phase 2b: Accepted

When Acceptor receives an acknowledgement message request from Proposer (NMagnez), if the Acceptor does not have promise only to receive messages > n during phase 1b, then the (NMagnez) message must be acknowledged by Acceptor.

When the (NMagnez) message is confirmed by Acceptor, Acceptor sends an Accepted (NMagnez) message to Proposer and all Learner. Of course, in most cases, the roles of Proposer and Learner can be merged.

If the Acceptor receives only messages > n during phase 1b, the acknowledgement request message will be rejected or ignored.

Following the above logic, there is a situation where Acceptor acknowledges multiple messages in one round. Under what circumstances will this happen? Let's give an example:

Acceptor received Accept (NMagnez) and returned Accepted (NMagnez), and then the Acceptor received a request from Prepare (nasty 1). According to the principle of stage 1B, Acceptor will Promise (nasty 1Magnez), then Acceptor will receive Accept (nasty 1Magnez), and finally return Accepted (nasty 1Magnez). You can see that although Acceptor acknowledges multiple requests, it ultimately ensures that the confirmed values are consistent.

Thank you for your reading, the above is the content of "what are the knowledge points related to the Paxos protocol". After the study of this article, I believe you have a deeper understanding of the knowledge points related to the Paxos agreement, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.