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

Paxos is a distributed consistency algorithm based on message passing, which was proposed by Leslie Lamport (Leslie Lambert) in 1990. It is recognized as one of the most effective algorithms to solve the distributed consistency problem.

Problems to be solved and application scenarios

The problem to be solved by Paxos algorithm can be understood as how to agree on a certain value (resolution) in a distributed system with asynchronous communication.

Asynchronous communication here means that messages are lost, timed out and out of order in the process of network transmission.

The typical application scenarios are:

In a distributed system, if the initial state of each node is the same, and each node executes the same command sequence, then a consistent state can be obtained at last. In order to ensure that each node executes the same sequence of commands, it is necessary to implement a consistency algorithm (such as Paxos algorithm) on each instruction to ensure that each node's instructions are consistent.

Concept definition

Proposal: a proposal initiated to agree on a value, including the proposal number and the value of the proposal.

The roles involved are as follows:

Proposer: proposal initiator, in order to agree on a certain value, Proposer can initiate any number of proposals at any speed and can stop or restart.

Acceptor: the person who approves the proposal, who is responsible for processing the received proposal, responding, making a commitment, or approving the proposal.

Learner: proposal learners can obtain approved proposals from Acceptor.

Agreement

Paxos needs to follow the following conventions:

1. An Acceptor must approve the first proposal it receives.

2. If the proposal numbered n is approved, then all proposals numbered greater than n must have the same value as the proposal numbered n.

Algorithm description

Stage 1: preparation phase

1. Proposer chooses a proposal number n to broadcast the Prepare (n) request to Acceptor.

2. Acceptor receives a Prepare (n) request, and if the number n is greater than the number of all Prepare requests that have previously been responded to, then the previously approved proposal with the highest number is fed back to Proposer and promises not to receive proposals with a number less than n. Or ignore it.

Phase II: approval phase

1. After Proposer receives more than half of the Acceptor responses, if the response does not contain any proposal, then send the proposal number n and its own value to Acceptor as the proposal Accept request. Otherwise, the number n, and the value of the proposal with the highest number in the response received, is sent as a proposal to the Accept request to Acceptor.

2. Acceptor receives the Accept request with the number n, and can approve the proposal as long as the Acceptor has not responded to the Prepare request with the number greater than n.

Endless cycle problem

If Proposer1 makes a proposal numbered N1 and completes phase one. At the same time, Proposer2 put forward a proposal numbered N2, N2 > N1, which also completed phase one. So Acceptor promises not to approve proposals with numbers less than N2, and when Proposer1 enters phase 02:00, it will be ignored. Similarly, at this point, Proposer1 can put forward a proposal numbered n3, with N2 > N2, which in turn causes the proposal numbered N2 of Proposer2 to be ignored at 02:00. And so on, it will enter an endless cycle.

Solution:

You can choose a Proposer as the primary Proposer and agree that only the master Proposer can make a proposal. Therefore, as long as the master Proposer can keep communicating with more than half of the Acceptor, any proposal with a higher number put forward by the master Proposer will be approved.

Learner

Once the Acceptor approves a proposal, send it to all Learner. To avoid heavy traffic, the Acceptor can also send approved proposals to the main Learner, which will be distributed to other Learner by the master Learner. Considering the single point problem of the master Learner, you can also consider that the proposal that Acceptor will approve will be sent to the master Learner group, which will be distributed to other Learner by the master Learner group.

Reference documentation

Paxos Made Simple (Chinese translation)

Introduction to the implementation principle of production-level paxos Class Library PhxPaxos developed by Wechat

[original] understanding Paxos algorithm step by step

Postscript

The Paxos algorithm is relatively difficult to understand and implement, so later there appeared the Raft algorithm which is easier to understand and implement.

It will be summarized separately later.

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.