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

This article mainly introduces "what are the Paxos variants and optimization methods". In daily operation, I believe many people have doubts about what problems there are in the Paxos variants and optimization methods. I have consulted all kinds of information and sorted out simple and easy operation methods. I hope to help you answer the doubts about "what are the Paxos variants and optimization methods"! Next, please follow the small series to learn together!

Multi Paxos

First, let's review Multi Paxos. Multi Paxos determines a series of values on the basis of Basic Paxos, and its resolution process is as follows:

phase1a: leader submits proposal to acceptor

phase1b: acceptor Returns the last accepted offer (i.e. the largest offer ID and corresponding value ever accepted), null if no offer has been accepted

phase2a: leader collects acceptor responses in two cases

phase2a.1: If the answer is empty, choose a proposal value freely.

phase2a.2: If the response is not empty, select the value of the proposal with the largest ID in the response.

phase2b: acceptor synchronizes resolution to learner

In Multi Paxos, the leader is used to avoid livelock, but the existence of the leader will bring other problems, one is how to elect and maintain a unique leader(although no leader or multiple leaders do not affect consistency, but affect the progress of the resolution process), the other is that the node acting as the leader will bear more pressure, and how to balance the load of the nodes. Mencius[1] proposes that nodes rotate as leaders to achieve load balancing; leases can help achieve a unique leader, but in case of leader failure, services can be unavailable for a short period of time.

Fast Paxos

In Multi Paxos, proposer -> leader -> acceptor -> learner, there are 3 communications from proposal to resolution completion. Can communication steps be reduced?

For Multi Paxos phase2a, if you can freely propose value, you can let the proposer directly initiate the proposal, the leader exits the communication process, and becomes proposer -> acceptor -> learner, which is the origin of Fast Paxos[2].

In Multi Paxos, proposals are put forward by the leader, so there is no multiple values in one resolution. In Fast Paxos, proposals are directly proposed by the proposer. There may be multiple proposer proposals and multiple values in one resolution, that is, proposal conflict occurs. The leader plays the role of initializing the resolution process and resolving conflicts. When conflicts occur, the leader re-participates in the resolution process and falls back to three communication steps.

An implicit feature of Paxos itself can also achieve the goal of reducing communication steps. If the acceptor last selected proposal came from proposer A, then the current resolution proposer A can directly propose to reduce one communication step. If you want to achieve such an effect, you need to record the history of the last resolution (chosen) in the proposer and acceptor, so as to know which proposer's proposal was last determined and whether the current resolution can save a communication step before proposing.

EPaxos

In addition to improving Paxos resolution efficiency from the perspective of reducing communication steps, there are other aspects that can reduce Paxos resolution latency, such as Generalized Paxos[3] proposing non-conflicting proposals (e.g. write requests for different keys) can be resolved simultaneously to reduce Paxos latency.

Furthermore, EPaxos[4](Egalitarian Paxos) proposes a Paxos optimization method that not only supports non-collision proposals while reducing latency, but also balances the load of each node and minimizes communication steps.

To achieve these goals, EPaxos has several key points. One is that there is no global leader in EPaxos, but the proposer of each proposal is the leader(command leader) of the current proposal; the other is that proposals that do not interfere with each other can be submitted at the same time; and the third is to skip prepare and directly enter the accept phase. The process of EPaxos resolution is as follows:

The left shows the resolution of two update requests that do not affect each other, and the right shows the resolution of two update requests that affect each other. Multi Paxos, Mencius, EPaxos latency and throughput comparison:

To determine whether resolutions influence each other, EPaxos must record the dependencies between resolutions.

At this point, the study of "Paxos variants and optimization methods" is over, hoping to solve everyone's doubts. Theory and practice can better match to help everyone learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

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.