This article comes from the public number: Hook hook Java universe (wechat: Javagogo), mo to promote, all dry goods!

The original link: mp.weixin.qq.com/s/b8BfWCdb9…

By Bing Yue

————————————————————————————-

According to Mike Burrows, author of Google Chubby, an open source distributed lock component

There’s only one consistency algorithm in the world, and that’s Paxos. The rest of the algorithm is a relic.

The Paxos algorithm is important but also complex.

Quorum mechanism

Before talking about the Paxos algorithm, consider the Quorum election algorithm in distributed systems.

Quorum mechanism can be found in various consistency algorithms, and the main mathematical idea is derived from the drawer principle: if W of N replicas are successfully updated at one time, then I need to read data from more than N-W replicas so that I can read at least one updated data.

The counterpart of Quorum mechanism is Write All Read One (WARO), a simple copy control protocol. When a Client requests to Write data to a copy (update data), the Write operation succeeds only when All copies are updated successfully. Otherwise, the Write operation fails.

  • WARO prioritizes the read service to ensure that all copies are consistent and only the data on any copy needs to be read.

  • The availability of the write service is low. Suppose there are N copies and n-1 copies are down, the remaining copy can still provide read service. But as long as one copy goes down, the write service will not succeed.

WARO maximizes the availability of read services at the expense of update services, and Quorum is a tradeoff between update and read services.

1. The Quorum definition

Quorum is defined as follows —

Assume that there are N replicas. The WI is considered to be successfully updated only after the WI is successfully updated in W replicas. The data corresponding to the successfully submitted update operation is called Successfully submitted data.

For the read operation, at least R copies must be read to read the updated data. W+R>N indicates that W and R overlap. Generally, W+R=N+1.

  • N = Number of data copies stored

  • W = Copies required for the update to succeed

  • R = Number of copies to be accessed from a data object read at a time

Quorum is defined as requiring at least N+1-W copies of data to be read at a time.

For example, if we maintain 10 replicas and successfully update 3 at a time, we need to read at least 8 replicas to ensure that we can read the latest data.

2. Quorum application

The Quorum mechanism cannot guarantee strong consistency, that is, any user or node can read the last successfully committed copy at any time.

You need a metadata service that retrieves the latest successfully committed version number to determine the latest successfully committed version number, and then to identify the latest written data from the read data.

Quorum is a common mechanism in distributed systems. It is a voting algorithm used to ensure data redundancy and ultimate consistency. It can be seen in algorithms such as Paxos, Raft and ZooKeeper’s Zab.

Paxos

1. Node role of Paxos

In the Paxos protocol, there are three types of node roles, numbered Proposer, Acceptor, and Learner, plus a Client that generates issues.

The above three roles are only logical. In practice, a node can play all three roles.

  • Proposer who

At the beginning of the process, a Proposer presents a proposal, known as a value. In a project, value can be any operation, such as “changing the value of a variable to a new value.”

Proposer can have more than one Proposer, each with a different or even contradictory value, such as one Proposer with a proposal to “set variable X to 1,” and another Proposer with a proposal to “set variable X to 2.” However, for the same round of Paxos process, only one value is approved at most.

  • Acceptor approver

In a cluster with N acceptors, a numbered value (Proposer) must be approved by a majority of acceptors (N/2+1).

  • Learner learners

Learner does not participate in the election, but learns the approved value. In Paxos, Learner mainly participates in the related state machine synchronization process.

A value needs to be approved by W=N/2+1 acceptors. Learner needs to read at least N/2+1 Accpetor. A maximum of N Acceptor results can be read before a value that passes can be learned.

  • Client generates issues

As the issue generator, the Client does not actually participate in the election process, such as the source of the amendment request.

2. Interactions between Proposer and acceptors

In Paxos, Proposer and Acceptor are the core roles of the algorithm. Paxos describes how to get acceptors to agree to proposals numbered with a number of acceptors in a system with a number of proposals, and Learner only “learns” the proposals that are ultimately approved.

The proposals exchanged with acceptors consist of four types of message communications, corresponding to two phases and four processes of the Paxos algorithm.

3. Paxos election process

The election process can be divided into two parts, the preparation phase and the election phase, as shown in the sequence diagram below:

3.1 Phase 1 Preparation Phase

Proposer generates a globally unique and increasing ProposalID, and sends a Prepare request to all machines in the Paxos cluster with no value but N (ProposalID).

An Acceptor, after receiving a Prepare request, determines whether the ProposalID received is greater than the number N of the proposals previously responded to.

If so, then —

  • Persist N locally, denoted as Max_N

  • Reply to the request with the maximum value of N of the accepted proposals, or null if there are no accepted proposals yet

  • Make a commitment not to accept any proposal less than Max_N

If no, then —

  • Not reply or replyError.

3.2 Phase 2 Election Phase

For the sake of description, we split the Phase 2 election Phase into P2a, P2b, and P2c.

  • P2a: Proposer sends Accept

A Proposer, after a period of time, collects Prepare responses with the following scenarios:

(1) If the number of acceptors received is greater than half, and all acceptors received are null, then the Porposer sends an Accept request with its specified value.

(2) If the number of Acceptor responses is greater than half, and any of the responses are not empty, the Porposer sends a accept request with the largest value of its ProposalID.

(3) If the number of Acceptor responses is less than half of the number of acceptors, an update is attempted to generate a larger ProposalID and proceed to the prepare phase.

  • P2b: Acceptor accepts acceptances

Upon receiving the Accpet request, Accpetor determines that:

(1) If the received N >= Max_N (generally equal to Max_N), the reply submission is successful, and N and value are persisted;

(2) If the received N is less than Max_N, no reply is received or the reply submission fails.

  • P2c: Proposer counts votes

A Proposer, after a period of time, collects a number of cases where an Accept response was submitted successfully, such as:

(1) If the number of Acceptor responses is greater than half, a value is submitted successfully, and a broadcast is sent to each of the proposers notifting them of the committed value.

(2) If the number of Acceptor responses is less than half of the number of acceptors, an update is attempted to generate a larger ProposalID and proceed to the prepare phase.

(3) If it receives a response with a failed submission, it tries to update and generates a larger ProposalID, which also moves to the prepare phase.

Common problems with Paxos

  1. How to run properly if less than half of acceptors fail?

In a Paxos process, if less than half of acceptors fail, there are two cases.

  • In the first case, if less than half of the acceptors fail without a final value, then all of the proposers resubmit proposals and one proposal is submitted successfully.

  • If no more than half of acceptors fail and a final value is determined, then any Proposer submitted must submit with a final value, that is, if the value is actually in force and can be obtained without modification.

  1. Acceptors need to accept a larger N, that is, a ProposalID. What does that mean?

This mechanism prevents blocking problems when one of the proposers crashes, allowing the other proposers to preempt temporary access with a larger ProposalID.

  1. How do you generate a unique number, called a ProposalID?

In the Paxos Made Simple paper, it is stated that a unique number allows all proposers to choose from a set of data that do not intersect, requiring no duplication between proposers.

If there are five proposers, each numbered with a j(0 to 4), then the number of proposals numbered with each Proposer is 5* I +j, and I is used to indicate the number of proposals submitted.

In summary, Paxos is a classic distributed protocol, and once you understand it, it will be much easier to learn about other distributed protocols.

————————————————————————————–

Welcome big guys to pay attention to the public account of the Java universe (wechat: Javagogo), refuse hydrology, harvest dry goods!