Foreword

PaxosThe algorithm is An algorithm used to solve how to agree on a certain value in a distributed system. Its degree of obscurity can completely match its importance. At present, there are a lot of introductions about paxosalgorithms, but few people can To P2c to put forward their own opinions, most of them are in harmony with the muddy people. But I believe that the truth will become clearer and clearer. Only by presenting one’s own views in a clear-cut way for everyone to discuss can we learn.

I personally think I understandPaxos There are two keys:

1. Why The proposals must be numbered sequentially (or what a higher number means).
2. WhyPromiseConsistency is guaranteed (the answer is implicit in the first1Click)

Consistency issues

Assume that there is a group of servers that save the user’s balance. Initially it is 100 block, now the user Two orders were submitted, one was for consumption10yuan, and the other was for consumption Top up50yuan. Due to network errors and delays, some servers only received the first order (the balance was updated to90元), some servers only received the second order (the balance is updated to150yuan), and some servers have received both orders (the balance is updated to140Yuan), these three cannot agree on the final balance. This is the issue of consistency.

The consensus algorithm does not guarantee that all proposed values ​​are correct (this may be the security administrator’s Responsibilities). We assume that all submitted values ​​are correct, and the algorithm needs to make a decision on which one to choose, and make the result of the decision be known to all participants.

In the formal introductionPaxosBefore facing the difficulties, for the convenience of presentation, let me mention it firstPaxosThe three roles in the algorithm will be used more frequently later:

• Proposer: the initiator of the proposal.
• Acceptor: The decision maker can approve the proposal.
• Learner: The learner who makes the final decision.

We virtualize a scene of consistency problems: there is a user Xiaolu, and now we have to His surname information was revised. At this time, a number of different proposals were proposed, how to reach an agreement on the final result.

Look at the simplest case below:

span>A1AcceptedPaThe motion “Zhao”,A2and< span style="font-family: Calibri;">A3AcceptedPb The motion “money”, then what should Xiaolu’s last name be?

The answer is simple: more than half The motion is the final selected value. Xiaolu should have his last name “money”! After the proposal is submitted, PaandPbJust look up the little green surname, and it’s easy to find more than half of the “money”, soPbThe motion will return “success”,PaThe motion will return “failure”.

P0. When more than half of the clustersAcceptoraccepted a proposal, Then we can say that this bill has been selected (Chosen).

P0is already a complete The consistency algorithm of P0 also solves the consistency problem. ButP0The practicality of is not good, and one proposal wants to be more than half of the people< /span>AcceptorAcceptance is extremely difficult!

Look at the following situation:A1,A2,A3Accepted “Zhao”, “Money” and “Sun “As a result, none of the bills formed a majority, and all the bills would return to “failure.” The greater the number of motions, the lower the probability of the motion being selected, which is obviously intolerable.

To solve this problem, you must Allow oneAcceptoraccept multiple proposals, and the later accepted proposals can overwrite the previously accepted proposals .

As shown in the picture below, A1has accepted “Zhao”,A2have accepted “money”, at this timePc “Sun” was proposed and was A1,A2,A3 span>Accept, and this will solve the problem of the inability to form a majority.

But now I will face the next New question in the picture:A1,A2,A3Already accepted” Zhao”, at this time we think that “Zhao” is selected, but at this time, it is PbandPcI don’t know the current affairs,< span style="font-family: Calibri;">Pb向A2< /span>proposed “money”,Pcproposed “sun” toA3. In this way, from a consistent state, back to an inconsistent state… This obviously destroys the consistency.

Paxosis produced under the above background,PaxosThe goal to be achieved is:

1. One bill must be selected in an election (it can’t happen that all bills are rejected)
2. Only one bill must be selected in an election (there cannot be a situation where two bills have different values ​​but are both selected)

Paxosderivation of algorithm

First of all,Paxosnecessary for the algorithm Meet the first condition:

P1: OneAcceptormust accept the first motion it receives.

To meet this condition is too simple, the method is omitted. . .

The following is my personal understanding of this condition, why this condition must be met:

Assuming there is only oneAcceptor, only OneProposer. IfAcceptorrejected for some reasonProposer‘s motion, which will inevitably lead toPaxosGoalT1Unable to reach. Therefore, it can be considered that the targetT1impliedP1.

Before starting the derivation ofP2, in order to distinguish between different proposals, you need to ProposerThe proposals of are numbered. When numbering, you must ensure that the number of each proposal has Uniqueness (do not discuss the implementation method), and the number is constantly increasing.

PaxosGoalT2ImpliedP2 :

P2 : If a value is vThe motion is selected, then the selected motion with a higher number must also have its valuev.

P2It’s easy to understand, Except for one of the adjectives, “larger numbered”, this adjective is very eye-catching. Why is there a restriction on motions with a larger number, and what about a smaller number?

The explanation given by the old man is very simple“By induction on proposal number” (If you don’t read the second half of the paper, no one knows What is he talking about…) Let me talk about my own understanding:

First, replace the words ” with a larger number” with “other”, we call it P2S< span style="font-family: Song Ti;">. SoP2SCan it be satisfiedPaxosThe goal? The answer is yes. Then compareP2andP2SWhose restraint is stronger? It depends on how the “smaller number” is handled. From the deduction at the back of the paper, a proposal with a smaller number is definitely not allowed to be selected! ! ! So satisfyingP2The proposal isP2SA subset of.

obviously,P2SandP2 Both PaxosGoal. In other words, there are many ways to meet the goals ofPaxos, but we only choose One way is toOK. However, choose the easiest way (you will know after reading it).

In short, now we can draw a conclusion:

< span style="font-size: 14px;">IfP1and span>P2 can be satisfied, thenPaxosThe two goals can be achieved.

If you are interested in the above There is no objection to the conclusion, then it means that you have fully understoodP1andP2< /span>.

Next, we need to figure out how to do it SatisfyP2: The proposal must be selected before it is selectedAcceptor span>Accept, so meetP2, we only need to meet the following conditions:

P2a: If a value is v Is selected, thenAcceptorAccept the larger numbered motion, it The value of must also bev.

P2aYesP2sufficient conditions, butP2aThere is a big trouble: when a bill is selected, part of itAcceptorCannot be notified immediately. For example in the picture belowA1andA2has accepted “Zhao”, at this time “Zhao” was selected, at this time< span style="font-family: Calibri;">Pb向A3< /span> proposed a motion “money”, this isA3The first bill accepted, in order to satisfyP1,A3This bill must be accepted, and it will P2acannot be satisfied.

In order to solve the above problems, let’s think about it: If we don’t letPbThe proposal of “money”, but the proposal of “Zhao” will be fine. Following this line of thought, we got P2b: span>

P2b: If a value isvThe motion is selected, thenProposerthe proposal of a larger number, and its value must also bev.

P2bis a comparison< /span>P2a stronger constraints, that is to sayP2bYesP2a sufficient conditions, as long as it can meetP2b, thenP2a is automatically satisfied. ButP2bIt is difficult to be satisfied. Consider the following picture. span>A1Accepted the motion “Zhao”,A2The bill “Zhao” is about to be accepted, at this timePb proposed a motion “money”, in this case we will meet againP2aExactly the same trouble.

Obviously, in order to satisfyP2b, we must letProposerHaving the ability to “predict the future” sounds like telling a ghost story. We will find a way to solve this later.

Introducing how to” forecast Before “the future”, we must first determine the value of Proposer when proposing a proposal Selection, because the method of obtaining the value determines the method of “forecasting”.

A natural value method: find one AcceptorThe majority of the collection, the values ​​of the accepted proposals in the collection are allv, at this timeProposerPropose a new motion, and the value of the motion must also bev;If there is no such majority group, thenProposeranything carry.

This value method is fully compatible with /span>P2b, this is clear at a glance, but the problem lies in the “prediction”. We must be able to predict the proposal that will form a majority. If anyone can do it Then it’s really telling a ghost story.

ProposalThe correct posture for proposing a proposal: span>

P2c: in all Acceptor, arbitrarily select more than half of theAcceptorcollection, we call this collectionS span>. ProposalNew proposal (abbreviated as Pnew) must meet one of the following two conditions: p>

1)IfSallAcceptornever accept If you have passed the motion, then the number of Pnew can be unique and incremented. PnewThe value can be any value.

2) IfS contains one or moreAcceptor span>If you have ever accepted a bill, you must first find the bill with the largest number, assuming its number isN, the value isV. ThenPnewThe number must be greater thanN,PnewThe value must be equal toV .

P2cRules for proposing proposals It’s a bit complicated. Is it really satisfyingP2b? At least it doesn’t look so clear. P2ccan satisfyP2b, but the effect is not good, no one can understand, so the following proof process must be too frustrating even if you can’t understand it (pictures and texts will be explained later).

Proof question(Attention! High energy ahead):

Known motionis the first selected motion in the set. The one that accepts this motionAcceptor set is , in the case of satisfying P2c rule 2 Next, a new proposal was proposed. ,n>m, proof that

The first step is to prove the initial establishment: when the number of the billn = m+1, prove that

Becauseis the first motion selected, so before m+1 is proposed, m must be the highest numbered motion in the cluster< /strong>.

according to< /span>P2c rule 2, motion Can be proposed because there is a majority set, in this set, the value of the motion with the highest number is . Becauseand All are majority groups, so they must have intersections. In the intersectionAcceptor must all accept . m is the largest number in the entire cluster, which of course is The largest number in according to the rules ofP2c 2. must be equal

< p class="p">The second step, whenn> m+1, assume The values ​​of the proposals numbered from m+1 to n-1 are all , to prove that :

After the proposals numbered m+1 to n-1 are proposed, we There is no way to determine which motion will be selected, but one thing is certain: all accepted TheAcceptor constitutes a new collection of , this collection contains the collection allAcceptor in It is obviously a majority group, and the number of bills accepted by this group is between m and n-1, and The value is . Not included in the collection The motion accepted by the Acceptor must be less than m.

根据P2c的规则2，议案能够被提出，那么一定存在一个多数派集合，因为和都是多数派集合，所以他们必定存在交集。交集中的议案的最大编号一定大于等于m，小于等于n-1。因此集合中编号最大的议案一定位于交集内。根据P2c的规则，必定等于。

 

这个证明过程，如果你能看懂，请受我三跪。 . .

接下来，上图，举例说明。

假设有一个议案（3，Va）提交后，这个议案成为了被Acceptor集群选定的第一个议案 ，那此时集群的状态可能会如下图所示：

一共5个Acceptor，有3个Acceptor接受了议案（3，Va< /span>），刚刚过半。此时有一个编号为4的议案要提出，根据P2c的规则2，首先选一个过半的集合，就选上图中蓝色线圈出来的A3，A4，A5好了（任意选），这个集合中编号最大的议案是（3，Va），因此新提出的议案必定为（4，Va）。符合P2b。

议案（4，Va）提出后，集群的状态可能是下面这样：

此时再提出编号为5或6，7，8，9，10的议案，这个议案的值必定也是Va（不信的话请举出反例），符合P2b。依此类推。 . .

由此可证，P2c是能够满足P2b的！ ! !

想想看P2，P2a，P2b中为什么一定要有“更大编号的”这几个扎眼的字眼，此时你应该能有一点感觉了，可能你会把它理解成“后提出的”，如果你是这样理解的话，请往下看。

有些童鞋肯定早就已经想到了：当议案（3，Va）提交后，这个议案成为了被Acceptor集群选定的第一个议案，此时集群的状态有没有可能是下面这样？

注意，这时议案（4，Vb）才是集群当中的编号最大的议案，要是这样就糟糕了！当我们提出编号为5的议案时，它的取值就有可能是Vb，导致无法满足P2b。

为了保证不出现这种情况，就要用到前面提到的“预测未来”的能力。跟P2c的议案规则相配套的，需要预测的未来是：

当一个议案在提出时（即使已经在发送的半路上了），它必须能够知道当前已经提出的议案的最大编号。

这样的话，议案（3，Va）提交时，就会知道有一个（4，Vb）的议案已经提交了，然后将自己的编号改成5或更大编号提交，一切就完美了。

但是你知道的，我们并不可能真的预测未来，换个思路，议案肯定是要提交给Acceptor的，只要由Acceptor来保证议案编号的顺序就OK了。于是有：

议案（n，v）在提出前，必须将自己的编号通知给半数以上的Acceptor。 收到通知的Acceptor将n跟自己之前收到的通知进行比较，如果n更大，就将n确认为最大编号。 当半数以上Acceptor确认n是最大编号时，议案（n，v）才能正式提交。

两个编号不同的议案，不可能同时被确认为最大编号，证明略。

但是实际环境上，上面的条件还不足以保证议案被接受的顺序，比如议案（n，Va）被确认为最大编号后，开始向Acceptor发送，此时（n+1，Vb）提出，由于网络速度的原因，（n+1，Vb）可能比（n，Va）更早被Acceptor接收到。

因此Acceptor收到一个新的编号n，在确认n比自己之前收到的编号大时，必须做出承诺（Promise）：不再接受比n小的议案。

这个承诺会导致部分漏网之鱼（在发送途中被抢走最大编号的议案），无法形成多数派。

例如下图所示：有一个在途的议案（1，Va），当A2和A3对议案（2，Vb）做出承诺的同时，（1，Va）就失去了形成多数派的权利。

 

至此，我们就形成了一个完整的算法（具体实现请自行搜索PhxPaxos）。

 

后记

 

算法原文中，将Promise看做是P2c的具体实现，而我们将Promise看成是弥补P2c的补充条件。这两者没有质的差别，只是角度不同，我个人认为后一种更容易被理解，所以采用了后一种。不过采用后一种会遇到下面的麻烦：

按下面的顺序提交议案：

① 议案（1，Va）向A1发送Prepare，获得A1的承诺。

② 议案（2，Vb）向A1发送Prepare，获得A1的承诺。

③ 发送议案（1，Va）

此时A1会拒绝议案（1，Va）

采用后一种解释的话，会发现A1拒绝议案（1，Va）是违反了P1的，而采用前一种解释则不违反P1。 （这不过是个文字游戏，我已经懒的去思考了，就这样吧）

 

如果我们将半数以上的Acceptor对同一个议案（n，v）做出承诺的状态称作是“锁定”状态。那么这个“锁定”状态具有以下性质：

排它性：所有比n小的议案都不允许提交，已经在途的议案，则不允许其形成多数派。

唯一性：任意时刻，全局只有一个议案能获得“锁定”状态。

原子性：议案n从锁定状态变为非锁定状态的过程是原子的，议案n+1从非锁定状态变更为锁定状态的过程也是原子的。

我相信（有点虚…），正是上面的这三条性质保证了一致性。

最后，感谢老头子给出的如此精彩的算法。