WeChat public account: Concurrent notes to pay attention to more consensus algorithm-related content. If you have any questions or suggestions, please leave a message on the official account;

To answer this question, first understand the following questions

What is the difference between consensus and consistency?

How to understand the majority?

Why only need a majority to support it, even if there is consensus?

How does Paxos handle read requests?

Correct ambiguities in the topic.

Paxos is a Consensus Algorithm. Many articles in China translate Consensus as “consistency”, there is no problem in Chinese understanding, and in spoken language, we often use “consensus” and “consistency” alternately. For example, “tourism to Yunnan has reached a consensus” and “tourism to Yunnan has reached an agreement”, these two sentences express the same meaning. But in a distributed environment of computers, the two words differ slightly.

Consistency means that the data between replicas remains 100% the same state, such as C in CAP, which means 100% consistency, and the trade-off between CAs means that the data of each member is consistent. The trade-off between C and A is a philosophical problem that regulates (0 to 100%) intensity. For details, please refer to:

The deepest thinking of CAP on the whole network

Consensus means that from the perspective of external observers (clients), the data inside the system is consistent, and no matter which copy is accessed, the same data can be obtained, while the real situation inside the system may not be 100% consistent. Therefore, it is more appropriate for the Paxos algorithm to be translated as “consensus algorithm”.

A consensus algorithm, in addition to ensuring the correctness of the algorithm, fault tolerance is also essential, Paxos is no exception. In order to achieve high fault tolerance, Paxos allows a small number of members to fail, and only needs the support of the majority of members when deciding whether a proposal is agreed upon.

The Paxos algorithm is divided into two phases, the Prepare phase and the Accept phase. The Prepare phase is used to gain ownership of the initiating negotiations in this round and to obtain proposals that may have been agreed upon in the previous round of consultations. So we can also think of the Prepare stage as the read stage, and the Accept stage as the write stage.

In order to ensure that a proposal that has reached consensus does not change, when a proposal with potential consensus is obtained at the reading stage, the writing stage can only use that proposal to initiate consultations. In the two independent stages, in order to exchange information, there must be a medium of communication, and the medium of communication originates from the “majority”. Because the “majority idea” can ensure that any two majority sets intersect, then this intersecting copy is the medium of communication, we only need to control the intersecting copies so the rules that support the proposal (of course, all copies may be intersecting copies), so that the reading stage can get to the previous round of writing stage may reach a consensus proposal, continue this possible consensus proposal, in this round can only put forward the proposal, then we can ensure that the consensus proposal will not change.

Paxos only needs majority support, so the data between each member is inconsistent, but there must be a majority that has consistent data.

So Paxos handles read requests and usually needs to run another round of Paxos to get a consensus on a proposal through the Prepare stage.

Of course, each read request runs a round of Paxos, which is very slow, so there is also an optimization scheme in the industry, such as adding a round of confirm requests to record the confirm log for the consensus proposal.

How does Leaner get a consensus proposal? There are usually two scenarios, the most commonly used is the second type, the first is not efficient, and the Learner requires some computing power.

After Acceptor receives an Accept request, after accepting the request, forwards the Accept request to all Learners, and Learner needs to determine whether a proposal has a majority support for the proposal.

After Proposer receives a majority Acceptor support Acceptor request, it knows that the proposal has reached consensus and sends the proposal to Learner.