/question/
作者：朱一聪
链接：/question//answer/
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
作为一个因为毕设和这个密切相关从而有了解的人表示，paxos本身并不复杂，在&&paxos made simple&& Lamport用两段话就描述清楚了它的流程。他老人家也说paxos其实是个简单的算法。但是是我在工程领域见过最为精妙的算法。我想论述Paxos为什么难以理解会比描述Paxos的流程长的多的多。我最初学习Paxos是从《从Paxos到Zookeeper:分布式一致性原理与实践》，看的时候看了两遍头略晕，似懂非懂。然后某天晚上我在床上睡不着，凭着印象自己尝试推了一遍basic-Paxos推通了，那时我感觉我想明白了。后来我决定把Zookeeper的类似文件系统的上层数据模型换成更为直接的Java对象，下层用Raft协议维护一致性日志，重写个类似的系统，作为我的毕设题目。于是我看了蛮多的相关论文，特别得提一下的是Diego
Ongaro那篇300页的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》，真是写不动了就翻翻的良作;也看了Zookeeper的源代码。最后自己YY的系统写的能跑的，性能还不错，靠不靠谱吗我觉得是不靠谱的，论文也码完。现在想想当时我觉得我懂了，简直是扯淡。期间无数次我都有一种我懂了的感觉，然后又被打脸。现在回过头来看那本《从Paxos到Zookeeper:分布式一致性原理与实践》，关于ZAB协议和Paxos介绍的章节，就真心不敢恭维了，作者只是翻译了下&&paxos
made simple&&和ZAB的两篇论文的关键章节，完全没有用自己的理解和语言来组织内容。不仅没有讲清ZAB两篇论文之间的关系，也搞混了paxos和ZAB之间的关系。在我所见过的资料里，现在看来没有任何地方关于Paxos的描述比&&paxos made simple&& Lamport的那两段话更为精确和简要。任何号称浅显易懂的解说Paxos算法的描述，最多只是让你更好的入门，要更深的理解Paxos以及所有等同于它的一致性协议，ZAB,Raft,ViewStamp，你需要的是直接阅读相关论文，比较，质疑，与人探讨，最后实现它。
好吧下面试图用尽量简短的话描述下paxos和它的原理（为何它是正确的），而为了描述为何它是正确的，我们尝试自己导出paxos=/=。当我想到Paxos其实可以假装这么推导出的时候，我以为推导过程是简短的，因为关键点就这么几个，但是当我写完之后我发现好长啊，然而我已经改不动了。
让我们考虑如下的场景：有一组进程p1,p2.....pn，一个变量v。所谓的一致性问题就是：如何让这组进程就变量v的值达成一致。为了解释何谓达成一致，考虑如下可能，p1令v=a,p2令v=b，那么显然进程p1和p2就v的值没有达成一致。如果p2令v=a，那么认为p1，p2就v的值达成一致。显然让各个进程对变量v的值达成一致需要两个过程：（1）给变量v选择一个值，假设是c（2）决定v的值为c，即让各个进程都认为v=c。
首先我们介绍一个性质，称之为法定集合性质。我们将一个超过半数的集合称之为法定集合，比如数字1,2,3,4,5，共5个元素，{1,2,3}有三个元素就是法定集合。法定集合性质：任意两个法定集合，必定存在一个公共的成员。
接着我们直接给出v的值被决定的定义：当法定集合的进程 令v为某个相同的值，比如都是c，那么称v的值被决定为c。一旦变量v的值被决定了，那么变量的值不可更改，按照之前达成一致的定义，最终所有的进程都会认为v=c，这个性质称之为安全性。
然后我们举例说明这个定义可能导致的问题，假设进程全集为p1,p2,p3。p1和p2都认为v=c，那么我们认为v的值被决定为c。如果此时p3令v=d，那么这组进程显然没有就v的值达成一致。因此p3只能令v=c。我们可以导出一个结论，一旦变量v的值被决定为c，尽管一个进程pi尚未给v赋值，但是pi已经没有了给变量v随意赋值的自由，pi只能选择值c赋予给变量v。
pi如何得知v已经被决定了或者如何选择值c赋予给变量v呢，一个最傻的办法是pi向其它所有进程询问你是不是已经给v赋值了，值是多少。收集到所有结果后，pi自然可以判定v的值是否被决定并且得知v的值被决定为c。问题在于，进程是可能崩溃的，例如进程pj崩溃了，那么pi还要不要等待pj的回复呢，不等待，当整个集合只有三个进程pi,pj,pk，且pk和pj记录了v=c时，pi由于无法判定pj是否记录了v=c，因此无法直接判定v的值是否被决定；等待，pj崩溃后如果没有恢复，pi就会一直等待。
我们假设v的值已经被决定为c，根据变量v的值被决定的定义，存在一个法定集合Q1,Q1中每个进程都记录了v=c。我们让进程pi向一个法定集合Q2中的每个进程询问v的值，这样我们就可以允许少数的进程崩溃。根据法定集合性质，Q1和Q2必然至少有一个公共的进程p。p记录了v=c，p告知pi v=c，存在这样的情形：Q2中有另一个进程pk告知pi v=d，关键的问题是为何pi要相信p，而不是相信pk，从而挑选p记录的值赋予给变量v。我们称这个问题称之如何选值。
上面我们已经明确了这样一步：一个进程pi需要先向一个法定集合中的每个进程询问它们v的值，这一步称为询问，再从中挑选某个进程v的值作为自己的v的值。考虑v的值还未被决定时的情形，比如初始时，这个时候进程pi需要有自由赋予变量v任何值的权利，因此我们规定，当pi完成询问后，如果法定集合中的每个进程告知pi它们都未给v赋予值，那么pi有自由赋值的权利。随之产生的问题是，如果有两个进程pi,pj同时询问，并同时获得了自由赋值的权利，如何保证安全性。考虑如下的情形，当获得自由赋值的权利后，pi令v=c，pj令v=d，pi试图向一个法定集合Q3写入v=c,pj试图另一个法定集合Q4写入v=d，使得v的值被决定，同时Q3和Q4必然至少有一个公共成员q2。为了安全性，我们必须保证pi和pj中只有一个的写入企图能够彻底实现。如果作为公共成员的进程q2能够只接受一个进程的写入，拒绝掉另一个进程，那么我们就可以保证这一点。这个问题称之为如何拒绝。
为了满足安全性，上面遗留了两个问题，如何选值和如何拒绝。为了让描述更清晰，我们赋予进程两种角色，提议者和接受者。提议者负责处理如何选值，接受者负责处理如何拒绝，显然一个进程可以同时有两种职能，顺便我们总结下两者分别负责的所有事情。
提议者：提议者首先向接受者进程进行询问，得到一个法定集合的进程的回复后，如果法定集合的进程均未给v赋予值，那么提议者拥有自由赋值的权利，不然提议者从回复中选择一个值赋予给v。
当询问结束后，提议者选择或者自由的给v赋予某个值，例如c后，提议者尝试将v=c写入到一个法定集合的进程，从而令v=c被决定。不防令接受者角色负责写入v的值。我们将这种提议者进程尝试令接受者写入自身v的值的行为叫做提议，这个过程中提议者发送给接受者的消息称之为提案，显然提案中包括了提议者自身的v的值。
接受者：接受者负责处理提议者的询问和提议。上面我们已经导出接受者必须有能力拒绝提议者的提议才能保证安全性。
我们先考虑如何拒绝。重新考虑这个场景：提议者pi,pj在询问之后，都获得了自由赋值的权利，对于变量v，pi尝试让法定集合Q3的接受者们接受提案pq1（令v的值为c)，pj尝试向法定集合Q4的接受者接受它的提案pq2（令v的值为d)。
Q3与Q4至少存在一个公共的接受者q2,上面我们已经得出关键之处在于进程q2必须能够拒绝掉其中一个提议者的提案。目前我们的流程并没有提供任何信息让q2能够做到这一点，提案中只包括了提议者建议的v的值。如果本身存在一个唯一的数字来标识这个提案，不妨称为proposer-id，那么q2可以根据提案proposer-id的大小从pq1和pq2当中选择一个接受，不妨选择proposer-id大的议案来接受。我们令接受者q2用变量a-proposer-id记录它接受过的提案的proposer-id，如果一个议案pq的proposer-id&a-proposer-id，那么接受者q2接受这个提案，并更新a-proposer-id=pq.proposer-id。不防假设pq1.proposer-id&pq2.proposer-id，有两种情形：(1)q2先收到提案pq1。（2）q2先收到提案pq2。情形一，显然q2将拒绝后到的提案pq2；但是情形二，q2接受pq2后也会接受后到的提案pq1，这违背了我们的目标。，根据我们目前为止的规则，看起来似乎没有办法解决这个问题，情形二中q2无法拒绝pq1，但是如果q2能够拒绝pq2呢？这也符合我们的目标。q2如何拒绝pq2呢？如果q2收到提案pq2时，此时接受者q2.a-proposer-id=pq1.proposer-id，那么就能做到这一点。然而q2并未收到议案pq1，如何能令q2.a-proposer-id=pq1.proposer-id？显然只有提案pq1的提议者p1能够预先知道pq1的proposer-id，而p1在提议之前，还有一个询问阶段，只要在询问阶段提议者p1告知接受者q2它在提议阶段将提出的议案的proposer-id，q2记录下这个proposer-id，那么就可以做到这一点。我们将询问阶段提议者发送给接受者的消息称之为预提案，预提案包含了即将发送的提案的proposer-id，它的作用就是告知接受者在下一阶段该提议者的提案的proposer-id。
整理一下上面说述，接受者在收到提议者的包含它的proposer-id的预提案后，会设置它的a-proposer-id=proposer-id。如果接受者每接受一个预提案，就更新它的a-proposer-id，那么对于上面的例子中的情形二，无法保证q2.a-proposer-id=pq1.proposer-id。例如接受者q2先收到提议者pi的预提案ppq1，之后收到另一个提议者pj的预提案ppq2，再收到pj的提案pq2，此时q2.a-proposer-id=ppq2.proposer-id=pq2.proposer-id。我们的目的是令提议者pi和pj同时提出预提案ppq1和ppq2时，无论ppq1和ppq2的到达顺序如何，最终q2.a-proposer-id=ppq1.proposer-id=pq1.proposer-id。我们已知ppq1.proposer-id&ppq2.proposer-id，因此自然的我们只要加一个约束，对于一个预提案ppq，当接受者q.a-proposer-id&ppq.proposer-id时，才更新q.a-proposer-id=ppq.proposer-id。这样如果q2后收到pj的预提案ppq2，此时q2.a-proposer-id=q1.proposer-id&q2.proposer-id，将拒绝预提案ppq2。考虑如下的情况，提议者发送预提案ppq给接受者q，q尚未接受任何预提案和提案，故q.a-proposer-id=ppq.proposer-id，系统中不存在其它提议者，因此pq受到法定集合的接受者回复发送提案pq给接受者q，由于此时pq.proposer-id=ppq.proposer-id=q.a-proposer-id，我们之前的约束要求pq.proposer-id&q.a-proposer-id，这会导致q拒绝提案pq，只存在一个提议者的系统，提议者的提案竟然无法被接受，这显然不合理，因此修改约束为pq.proposer-id&=q.a-proposer-id。上面我们已经彻底保证如果提议者pi和pj在询问之后都获得了自由赋值的权利，无论接受者q2以如何的顺序接受到它们的预提案和提案，q2只会接受它们中一个的提案。显然p1和p2可以是任意两个进程，c和d可以时任意两个值，因此目前为止协议已经保证如下的一点：任意时刻，就算存在多个提议者在询问之后提出了不同的值的提案，最终只有其中一个提议者的提案中的值将会被法定集合的接受者接受，即只有一个值能够被决定。
回顾下目前为止我们的协议对于如何决定变量v的值的流程：
询问：发送包含自身proposer-id的预提案给接受者，得到一个法定集合的接受者的回复后，如果法定集合的接受者均未给v赋予值，那么提议者拥有自由赋值的权利，不然提议者从中选择一个值赋予给v。假定自由赋予或者选择的值为c。
提议：发送包含c和proposer-id的提案给接受者。
处理询问：如果收到的预提案ppq.proposer-id&a-proposer-id，那么更新a-proposer-id=ppq.proposer-id，接受这个预提案，不然则拒绝这个预提案。
处理提议：如果收到的提案的pq.proposer-id&a-proposer-id，那么更新a-proposer-id=pq.proposer-id，接受这个提案，记录v的值为提案中的值，即v=pq.c。
提议者在询问阶段需要得到一个法定集合的接受者的回复后才进行选值，因此接受在处理询问时，如果接受预提案，就会回复一个消息给提议者，称这个消息为诺言，诺言中包含了接受者记录的v的值。
似乎我们只剩下了最后一个问题如何选值。上面最初我们已经论证了当变量v的值被决定为c时，提议者pi在询问阶段收到的法定集合Q2的接受者的回复中，必然存在一个接受者q2回复了它记录了v=c。选值的关键在于我们从什么地方来判断q2记录的v的值才是v被决定了的值。接受者必须向提议者额外的信息来使得接受者有能力做出这种判断。我们重新回到v的值被决定的定义，v的值被决定为c，代表存在一个法定集合Q的接受者，记录了q.v=c。由于我们上面已经丰富了我们的协议，并引入了许多关键的概念，所以此时接受者还记录了自身a-proposer-id。我们假设是议案pq最先另q.v=c，由提议者p在提议阶段提出。那么v被决定为值c后，Q中每一个接受者:q.v=c，并且可以论证q.a-proposer-id
&=p.proposer-id。论证如下：当q接受议案pq时，q.a-proposer-id=pq.proposer-id=p。而q.a-proposer-id更新的条件是pq.proposer-id&=q.a-proposer-id和ppq.proposer-id&q.a-proposer-id，故q.a-proposer-id单调递增，故结论成立。
假设pi收到的法定集合Q2的接受者的诺言中，qj回复的诺言中v=d。我们要相信q2记录的值才是v被决定的值而不是qj。不妨假设提出议案pqj令qj.v=d的提议者是pj,pqj向法定集合Q3发送提案或预提案的接受者。我们已经引入了预提案的阶段，一个提案pq被提出，代表存在一个集合Q，对于Q中的任意一个进程q.a-proposer-id&=pq.proposer-id。这一点论证非常容易，预提案阶段会使得如果q.a-proposer-id&ppq.proposer-id，那么q.a-propposer-id=ppq.proposer-id，同时只有收到的提案或预提案的proposer-id大于q.a-proposer-id，q.a-proposer-id才会更新，即q.a-proposer-id是单调递增的，故得证。根据这个结论，我们可以得知Q3,Q3中任意一个接受者q,q.a-proposer-id&=pqj.proposer-id,又知存在一个法定集合Q，Q中任意一个接受者q都接受了pq，而Q3和Q至少存在一个公共接受者qk，qk接受了提案pq，又收到了预提案ppqj。我们假设pqj.proposer-id=ppqj.proposer-id&pq.proposer-id。如果qk先收到预提案ppqj，那么代表qk收到pq时，qk.a-proposer-id&=ppqj.proposer-id&pq.proposer-id,qk就会拒绝pqj，与Q中每个q都接受了pq矛盾。如果qk先接受了提案pq，再接受预提案ppqj，那么qk会回复一个包含v=qp.v=c的诺言给qj，即提案pqj的提出在v的值被决定后。根据归纳原理，假设我们的选值策略有效，那么我们的策略会使得qj选择值c作为提案pq的值，即pq.v=pqj.v=c，与假设qpj.v=d!=c违背。此时可以认定假设pqf.proposer-id&qpj.proposer-id必然不成立，这样我们确信pqj.proposer-id&pqj.proposer-id。注意我们已经得知了一个非常关键的信息：pi收到的法定集合Q2的接受者的诺言中，q2回复的诺言的值对应的提案的proposer-id大于其它v的值不是c的诺言对应的提案的proposer-id。因此我们只需要从收到的诺言中挑选对应的提案的proposer-id最大的诺言，假设是pro-k，必然pro-k.v=c。诺言由接受者在处理询问阶段回复给提议者，因此接受者在处理提议阶段记录v为收到的提案中的值外，还要记录这个提案的proposer-id，事实上就是把整个提案记录下来。现在我们又保证了当v的值被决定为c后，之后任意的提议者提出的提案的值也是c。
目前整个协议已经完整了，我们用目前为止导出和定义的所有约束和概念重新描述这个协议，同时我们改称接受者处理询问的阶段为承诺，处理提议的阶段为接受。对于变量v整个一致性协议如下：
询问：发送包含自身proposer-id的预提案给接受者，得到一个法定集合的接受者的承诺后，从中挑选出承诺对应的提案的proposer-id最大的承诺，选择这个承诺的值作为v的值，如果这些诺言没有对应的提案（表明接受者尚未在接受阶段记录任何提案），就自由赋值给v。假定自由赋予或者选择的值为c。
提议：发送包含c和proposer-id的提案给接受者。
承诺：如果收到的预提案ppq.proposer-id&a-proposer-id，那么更新a-proposer-id=ppq.proposer-id，接受这个预提案，回复包含在接受阶段记录的提案的诺言给发出预提案的提议者。不然则拒绝这个预提案，直接。
接受：如果收到的提案的pq.proposer-id&a-proposer-id，那么更新a-proposer-id=pq.proposer-id，接受这个提案并且记录这个提案。假定用a-pq来记录提案，即令a-pq=pq。当接受者没有接受过任何提案时，a-pq=null。
上述的协议有了如下的两个保证：
（1）：任意时刻，就算存在多个提议者在询问之后提出了不同的值的提案，最终只有其中一个提议者的提案中的值将会被法定集合的接受者接受，即只有一个值能够被决定。
（2）当v的值被决定为后，假设被决定为c，之后任意的提议者提出的提案的值也是c
保证（2）可以得出多个提议者提出不同值的议案只有在v的值未被决定时，当v的值未被决定时，保证（1）又保证了v的值会被决定为一个唯一的值，假设是c。而v的值被决定为c后，(2)又保证了之后的提案的值都是c。因此最终所有的进程都会得知v的是c，这就达成了一致，保证了协议安全性。
上面这个协议就叫做Paxos=、=。描述和&&Pa本一致了。上面的导出协议过程的先验就是本来就理解Paxos=、=,假装从头推导出协议只是为了更好的理解Paxos。
（1）上面的论证是不严谨的，不严谨的地方在于并没有清晰的定义例如当v的值被确定后，这种先后关系。实际上判断v的值被确定后还是确定前的严格意义上的分界线并不是法定集合的接受者接受v的同一个值这个事件的先后点。同时提出议案的先后严格意义上的分界线也并不是提议者提出以后这个时刻点。这两件事的先后关系的严格定义要更加微妙一点=.=。如果要严格的证明可以参照原作者大神的论文&&Paxos made simple&&和&&Fast Paxos&&中对基本Paxos的回顾。
（2）上面的算法是存在无法终止的可能性的，想象下多个提议者同时提出议案，每个议案中的值被决定前后又一个提议者以更大的proposer-id提出议案。实际上FLP结论已经指出，哪怕容忍一个进程的崩溃，在一个异步的系统中任何一致性算法都存在无法终止的可能性，就不要怪Paxos在容忍了少数派进程崩溃的前提下，无法真正保证活性。
本文已收录于以下专栏：
相关文章推荐
Basic-Paxos算法(可以先看后面的实际例子再看前面的具体介绍部分）
Paxos算法的目的
Paxos算法的目的是为了解决分布式环境下一致性的问题。
    多个节点并发操纵数据，如何保证在读写...
最近研究paxos算法，看了许多相关的文章，概念还是很模糊，觉得还是没有掌握paxos算法的精髓，所以花了3天时间分析了libpaxos3的所有代码，此代码可以从https://bitbucket.o...
Paxos算法的难理解与算法的知名度一样令人敬仰，从我个人的经历而言，难理解的原因并不是该算法高深到大家智商不够，而在于Lamport在表达该算法时过于晦涩且缺乏一个完整的应用场景。如果大师能换种思路...
一、Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一...
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)真巧，我最近也在研究这个东西。&br&&br&先推荐你看 Instagram 的这篇 [0]，他们要求生成 ID 尽量短而且可按生成时间排序，里面提到了好几种不同的 ID 生成方法的优缺点，比如：&ul&&li&在应用里面直接生成 UUID，优点是独立生成、性能好，缺点是生成的 ID 比较长。&/li&&li&单独运行一套 ID 生成服务，比如 Twitter 的 Snowflake [1]，优点是可以生成比较短而且可以排序的 ID，并且分布式系统不容易挂，缺点是维护麻烦。&br&&/li&&li&依赖数据库自增，比如 Flickr [2]，优点是可以重用现有的计数，缺点是数据库写性能可能会是瓶颈，并且如果使用多个数据库，如何保证生成的 ID 可排序是个问题。&/li&&/ul&Instagram 然后根据自己的需要定制了基于 PostgreSQL 数据库的预分片 (pre-sharding) ID 生成机制。核心思想是预先分配足量的逻辑片 (logical shard)，然后将大量的逻辑片映射到少量的物理片 (physical shard)，最终依赖数据库的自增特性保证 ID 的唯一性。&br&&br&&br&注意以上提到的几套机制生成的都是 64 位的整数 ID，主要是给程序用来标记新建的数据对象用的。而原题目提到的用户 ID，我理解除了给程序用外，更重要的是要给人看。给人看的 ID 需要更加简短，因为对机器来说，64 位已经足够短了，而显然人是无法快速记忆 6571174 这样一长串数字的。所以生成给人看的 ID 需要根据应用场景尽可能短，比如绝大部分时候用户数量不会过亿，那么生成的 ID 的十进制表达最好不要超过 8 位数。&br&&br&题目中要求的另外一点『不能直接看出规则』也是需要特别考虑的。对于中国互联网这样没有任何道德底限的地方来说尤为重要。原因大家都懂，如果 ID 是连续的，扒取内容的工作就非常简单了，直接按顺序下载指定的 URL 范围即可，爬虫都不用写了。所以对于公开 ID，不连续、无规则是基本要求。&br&&br&以上两点和前述 Instagram 文章提到的几种 ID 生成需求有本质不同。结合知乎的用例，我把题目提到的这种 ID 需求特性概括为九个字：尽量短、无规则、无顺序。对于这样的应用场景，个人认为写一套单独的 ID 生成服务是比较好的办法。这个功能很简单，依赖过多的外部组件（如数据库）有点得不偿失。&br&&br&目前我正在写的 ID 生成服务的基本思路是这样的：&ul&&li&ID 生成服务管理多个不同名字的 ID 池 (pool)。&/li&&li&每种不同类型的 ID 属于不同的 ID 池，比如知乎会有用户 ID 池、问题 ID 池、回答 ID 池等等。&/li&&li&每个 ID 池由多个定长 ID 块 (block) 构成。&/li&&li&每个 ID 块包含一段连续的 ID，比如第一块是从 0~1023，第二块从 ，以此类推。&/li&&li&每个 ID 块并不完全分配，而是按照一个给定的填充率 (fill ratio) 随机选择来分配，比如假设填充率是 50%，那么每个 ID 块中只有大约一半的 ID 会被分配。也就是说每个 ID 块是有随机空洞的。&/li&&li&如果某个 ID 块中可用 ID 被分配完毕，服务会自动生成下一个新的 ID 块，并按照填充率去掉不可用 ID。生成新的 ID 块时需要记录下最后一个 ID 块的起始 ID。&/li&&li&已经分配过的 ID 会写入一个 append-only 日志。新的 ID 块生成时会创建一个新的 append-only 日志（因为旧的已经不需要了）。&/li&&li&服务重新启动的时候先拿到最后一个 ID 块的起始 ID，再读取 append-only 日志将已经分配过的 ID 剔除，再剔除掉部分未分配的 ID 以维持填充率。&/li&&li&客户端发送请求访问 ID 生成服务。服务端返回 ID 做为回复。&/li&&/ul&&br&优点是逻辑简单，生成的 ID 短小，单个进程维护起来方便。缺点是知道生成的 ID 的上限（可以用很大的块部分解决这个问题）。大概这样。欢迎讨论。&br&&br&[0]: &a href=&///?target=http%3A//instagram-/post//sharding-ids-at-instagram& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&instagram-&/span&&span class=&invisible&&/post//sharding-ids-at-instagram&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[1]: &a href=&///?target=https%3A///twitter/snowflake& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/twitter/snow&/span&&span class=&invisible&&flake&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&[2]: &a href=&///?target=http%3A///blog//ticket-servers-distributed-unique-primary-keys-on-the-cheap/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/blog/20&/span&&span class=&invisible&&10/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&
真巧，我最近也在研究这个东西。 先推荐你看 Instagram 的这篇 [0]，他们要求生成 ID 尽量短而且可按生成时间排序，里面提到了好几种不同的 ID 生成方法的优缺点，比如：在应用里面直接生成 UUID，优点是独立生成、性能好，缺点是生成的 ID 比较长。单独运…
&img src=&/50/v2-6ea155db7edbdbdf70fff_b.png& data-rawwidth=&408& data-rawheight=&244& class=&content_image& width=&408&&&p&相信不少做存储或者数据库的人已经被Paxos轰炸过过一轮，我也不能免俗，最近也尽可能的翻了一些Paxos的文章，看了这些文章后，我个人感觉最好的理解方式是将Paxos要解决的问题具体化，细节化，然后，我想任何一个有着丰富经验的同学都能不依赖Paxos的任何资料很好的回答这些问题，这些答案的形式化综合起来就应该是网络上的各种Paxos解释。我相信问题导向逐步推导的方式比冲上去学习Paxos文章里面的流程有趣一些，同时，没准还可以发现一个更适合自己业务的改进。&/p&&br&&p&&strong&问题一：Paxos[2]解决什么问题？&/strong&&/p&&p&&em&在保证一致性的前提下，提高系统的可用性。&/em&系统中破坏可用性的场景包括，机器down机（硬盘等各种硬件损坏类比），机器间网络丢包、高延时。解决这些问题的根本思路是多副本，这样一个机器down其他副本还可以使用。多副本早已被大家广泛使用，之前最主要的思路是主备机制，又叫做primary-second，或者master-slave，核心思路是主承担所有的操作，并&strong&定期异步&/strong&将主上面数据的变化同步到备。在主备系统运行过程中，如果备出问题，服务不受影响；如果主出问题，就切换到备，因为主总是比备多一点数据，所以这个过程中可能丢数据。丢多少数据呢？这取决于主隔多少时间能将最新的信息同步到备，如果主每隔1小时就能保证1小时前的数据完全到备，那么最多丢一个小时。那么，丢数据的量能缩短吗？5分钟？1秒钟？&/p&&br&&p&对于一个繁忙的数据库系统，1秒钟的数据丢失可能也是灾难，那么最小粒度是什么？就是per request，即主上面每一个变化备都能同步感受到，那么主down掉的时候，备能无损的接管服务，这就是MySQL 主备强同步的思路。但是，如果每个request都要备参与，就意味着这个系统如果备挂了就不可服务了，这也是线上恐怕很少有人选择MySQL主备强同步的理由，怎么办？多加几个备来降低备不可用对系统的影响。&/p&&br&&p&多加几个备之后，就带了两个问题，&/p&&p&1. 这些主备之间数据一致性怎么解决？Paxos是一种思路，即多数派同意的就是正确的&/p&&p&2. 那如果主挂了呢，这里有两种选择，一种是任何人在任何时候都可以是主，这时候就没有主备之分了，这是basic paxos[2]的思路；另一种思路是，主挂了就让某一个备成为主，系统可以继续服务，这是viewstamped replication[3]、Raft[4]、Zab[5]（广义上可以算Paxos）的思路，在multi-paxos[6]里面也提到了使用leader减少prepare message，leader切换条件更灵活，也可以归类为这个序列。&br&&/p&&p&&em&&strong&上面两个问题就是Paxos要解决的核心问题，即Safety（数据是一致的）和Liveness（系统总是能继续前进）。&/strong&&/em&&/p&&br&&p&&strong&问题二：状态机(Replication State Machine, RSM)和一致性有何关系&/strong&&/p&&p&状态机有一个很好的特性：任何初始状态一样的状态机，如果执行的命令序列一样，则最终达到的状态也一样。而存在多个参与者的系统的一致性可以理解为，系统多数成员就某一系列决议得到了相同的判断结果，使用状态机来描述就是，如果在某一个时刻系统不再接受外部输入，则系统中存在多个参与者具有完全相同的状态机。上面两点结合在一起，就得到系统参与者保持一致的关键是，起始状态完全一致，执行命令序列完全一致，那么系统的行为就是可以重复的。这跟单机数据库系统可以类比，数据库重做日志就等于命令序列，数据库数据存储就等于状态机，唯一不同的是单机数据库日志序列化lock一下就可以做，那么多个参与者之间如何让日志序列化呢？这就是Paxos等一致性协议致力解决的具体问题，即如果状态机状态的改变是由命令1...N组成的，那么Paxos需要保证对任何一个1&=k&=N，命令序列的内容被系统中绝大部分的参与者同意。这个k可以称之为log position，log index，不同文章叫法不同。这里我们对上面问题一的一致性问题进行了具体化，只要保证了大部分参与者执行的命令序列是一样的，系统就是一致的。再具体化一步，保证命令序列中每个序号对应的命令是一样的，就能保证命令序列是一样的。&strong&&em&Paxos的责任就是保证：在一个命令序列中，同一个序号下面对应的命令内容是一样的。&/em&&/strong&[7]的描述还是比较清晰的。&/p&&br&&p&&strong&问题三：Paxos如何保证多参与者同一个序号对应同样的命令内容&/strong&&/p&&p&这是各类Paxos算法的核心，不过我认为在准备动手写代码前这是最不重要的一部分，因为除了最开始的paxos文章说的比较模糊，后面出来的都把这一块描述的异常清晰，甚至各种优化都帮着想好了。这里面理解下面几点就行，&/p&&ol&&li&&p&目标：让第k个命令序号执行x命令（x比如是inc）&/p&&/li&&li&&p&动作：给所有人发请求，&no, k, x&，no每次都要涨，这个好理解，否则一个网络上漂了半天的包被服务器收到怎么办？&/p&&/li&&li&&p&结果：如果大部分参与者都同意，就确定了&k, add&的对应关系；否则，每个Paxos算法都有一系列的规则来让系统一定能达成一个共同的决议，具体参考每个算法；&br&&/p&&/li&&/ol&&br&&p&&strong&问题四：leader选还是不选&/strong&&/p&&p&网上见到有人争论basic paxos不用选leader，对运维更友好，对网络抖动容忍度高等等，这个更像是一个工程实现问题，而不是理论问题。在一个多参与者的系统里面，如果每个人都提议，那么显然冲突的概率是很大的，冲突了就要重新开始新一轮提议，这会导致很低效，就好像高速路上8车道变成了1车道，这时候谁先走就是一个问题，如果没有警察叔叔，必定乱成一锅粥，在一个高压力的系统中问题类似。选了一个leader之后，leader知道没人跟自己抢，就可以省不少事，事情省了，系统也简单了，这就是Raft的思路。同时，如果有了leader，批量确认命令序列也成了可能（否则同一个paxos group冲突肯定高的吓人，有了警察叔叔每个车道可以一次放行20辆，没有警察叔叔一次放20辆可能很快就会因为事故全部堵死），这就是multi-paxos，即一次确认多个命令。选leader不是没有弊端，如果leader挂了，这时候系统是不能服务的，必须等新的leader选出来，这个一般几百毫秒搞定。那么，leader挂的时候如何降低对服务的影响？就是将paxos group做的精细一点，一个leader挂了，只影响这个paxos group，其余正常服务。如果碰到leader节点网络抖动，也可以迅速切换，减小影响。&em&&strong&整体来看，选leader是较好的做法，人类社会不也需要leader嘛。&/strong&&/em&&/p&&br&&p&&strong&问题五：机器down掉后，新加入的机器是否能立刻服务&/strong&&/p&&p&这点取决于&em&&strong&状态机如何维护，是整个系统作为一个状态机还是每个参与者都是一个独立的状态机。&/strong&&/em&如果整个系统被当做一个独立的状态机，那么任何机器加入进来都可以立刻服务，因为系统的状态是完整的，这也是basic paxos能达到的效果。如果系统中每个参与者都被当做一个独立的状态机，那么任何新机器加入进来必须先从其他机器获得一个过去的状态（snapshot），类似数据库备份里面的数据文件，然后执行这个状态之后的命令，类似执行数据库重做日志，等到状态已经追赶上系统中的多数参与者，就可以提供服务，这是Raft的效果。从描述看，Raft似乎弱了点，但是本质上两个是类似的，因为basic paxos将整个系统视为状态机增加了复杂性，且在参与者连续down的场景中，一样不能很好的解决，也需要尽快让新机器追状态，以达到每个命令都有多replica。&/p&&br&&p&&strong&问题六：paxos group如何随着新节点加入而改变&/strong&&/p&&p&这个问题被称为view change，就是说参与者变多了，比如1 2 3变成1 2 3 4 5，或者参与者要换一批，比如 1 2 3换成4 5 6，这个问题Raft处理的最好，简洁明了，说简单点就是在&em&&strong&新旧config交叠的时候，leader必须得到新旧两个group的认可，&/strong&&/em&这就避免了多leader脑裂的问题。viewstamped replication第一版在变配的时候要停机，revised解决了这个问题；paxos make simple里面的N+alpha方案不太好懂，按照文中的描述，在极端情况下有正确性问题（练习题[10]里面最后的题目，当然，工程实现上可以绕，这本来就是一个低频动作）&/p&&br&&p&&strong&问题七：不同方案哪个资源会首先成为瓶颈&/strong&&/p&&p&在leader方案中，&em&&strong&最容易成为瓶颈的是网络&/strong&&/em&，因为从方案设计上使用的就不均衡，leader接受请求后转给其他参与者，出口带宽会承压，这时候可以选择chain forward，让其余参与者也承担网络流量。磁盘方面还好，毕竟都上paxos了，PCIe接口NVME SSD盘应该少不了，秒几十万写不是事，还有像Oceanbase[11]讲的，log落盘就返回的话磁盘更不是事。现在CPU也越来越强大，配合上各类专用处理器，牛的不行。&/p&&br&&p&&strong&问题八：读的时候怎么保证一致性&/strong&&/p&&p&这个问题在各个Paxos文章里面叙述的不太明显，其实是一个很难的工程问题。basic paxos里面没有专门提，我揣摩意思就是读跟写一样，走完整的多参与者决策流程，这个肯定能读到一致的数据，但是性能恐怕不会好。在leader选举的方案里面，也不是件简单的事情。直接读leader的话，因为leader可能是过期的，那么可能导致读到的数据是过期的，这时候又要给leader加上lease机制，而这个机制更进一步限制了leader挂时候的可用性恢复。这里或许提供两类接口是一个明智的选择，比如&/p&&p&1. 非一致读：可能读到过期数据，这时候读任何一个参与者都行，不过也不能太随便，client可以提要求，该参与者与leader的距离不能超过一个阈值或者已经apply到RSM的序列号至少得大于client曾经写过的命令序列号。&/p&&p&2. 一致读：只能读leader，或者为了负载均衡，leader选一个状态一致的参与者也行。&/p&&br&&p&以上是近来研究paxos的一点记录，算是一个总结，欢迎交流微信teaworldvc20。&/p&&ol&&li&&p&封面图片来自：&a href=&/?target=http%3A//www.cs.rutgers.edu/%7Epxk/rutgers/notes/clocks/images/clocks-lamport.png& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&cs.rutgers.edu/~pxk/rut&/span&&span class=&invisible&&gers/notes/clocks/images/clocks-lamport.png&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=http%3A///en-us/um/people/lamport/pubs/lamport-paxos.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/&/span&&span class=&invisible&&en-us/um/people/lamport/pubs/lamport-paxos.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=http%3A//101.96.10.62/www.pmg.csail.mit.edu/papers/vr-revisited.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&101.96.10.62/www.pmg.cs&/span&&span class=&invisible&&ail.mit.edu/papers/vr-revisited.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=https%3A///document//raft-pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&/document/&/span&&span class=&invisible&&/raft-pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=http%3A//www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&tcs.hut.fi/Studies/T-79&/span&&span class=&invisible&&.5001/reports/2012-deSouzaMedeiros.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=http%3A///en-us/um/people/lamport/pubs/paxos-simple.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/&/span&&span class=&invisible&&en-us/um/people/lamport/pubs/paxos-simple.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=https%3A//ramcloud.stanford.edu/%7Eongaro/userstudy/paxos.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&ramcloud.stanford.edu/~&/span&&span class=&invisible&&ongaro/userstudy/paxos.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=https%3A//ramcloud.stanford.edu/%7Eongaro/userstudy/raft.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&ramcloud.stanford.edu/~&/span&&span class=&invisible&&ongaro/userstudy/raft.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=https%3A//ramcloud.stanford.edu/%7Eongaro/userstudy/paxossummary.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&ramcloud.stanford.edu/~&/span&&span class=&invisible&&ongaro/userstudy/paxossummary.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/?target=https%3A//ramcloud.stanford.edu/%7Eongaro/userstudy/rubric.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&https://&/span&&span class=&visible&&ramcloud.stanford.edu/~&/span&&span class=&invisible&&ongaro/userstudy/rubric.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&/p&&/li&&li&&p&&a href=&/question//answer/& class=&internal&&&span class=&invisible&&https://www.&/span&&span class=&visible&&/question/1984&/span&&span class=&invisible&&1579/answer/&/span&&span class=&ellipsis&&&/span&&/a&&/p&&/li&&/ol&&br&&p&微信链接：&a href=&/?target=http%3A//mp./s%3F__biz%3DMzIyNzEwMjQ1Mw%3D%3D%26mid%3D%26idx%3D1%26sn%3D61f7f15f6f641e2be4dc82%26chksm%3Df381ac89c4f6259f0ebf46bbaf714f6942dadb4abca3db9f4c9ec038d%26scene%3D0%23wechat_redirect& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&mp./s?&/span&&span class=&invisible&&__biz=MzIyNzEwMjQ1Mw==&mid=&idx=1&sn=61f7f15f6f641e2be4dc82&chksm=f381ac89c4f6259f0ebf46bbaf714f6942dadb4abca3db9f4c9ec038d&scene=0#wechat_redirect&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&&br&&/p&&p&&a href=&/?target=http%3A///r/tTvo7BbEOt5GKVKPb24x& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&/r/tTvo7Bb&/span&&span class=&invisible&&EOt5GKVKPb24x&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a& (二维码自动识别)&/p&
相信不少做存储或者数据库的人已经被Paxos轰炸过过一轮，我也不能免俗，最近也尽可能的翻了一些Paxos的文章，看了这些文章后，我个人感觉最好的理解方式是将Paxos要解决的问题具体化，细节化，然后，我想任何一个有着丰富经验的同学都能不依赖Paxos的任何资…
&p&&strong&本文整理自美团点评技术沙龙第14期：美团背后的故事－你不知道的美团云。&/strong&&/p&&p&美团点评技术沙龙由美团点评技术团队主办，每月一期。每期沙龙邀请美团点评及其他互联网公司的技术专家分享来自一线的实践经验，覆盖各主要技术领域。&/p&&p&目前沙龙会分别在北京、上海和厦门等地举行，要参加下一次最新沙龙活动？赶快关注微信公众号“美团点评技术团队”。&/p&&p&&a href=&/?target=http%3A///event/0& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&本期沙龙&i class=&icon-external&&&/i&&/a&包括三场讲座：美团云Docker平台、美团云对象存储系统、美团四层负载均衡网关MGW。其他几场讲座的图文实录会陆续发表，请继续关注。&/p&&h1&前言&/h1&&p&在高速发展的移动互联网时代，负载均衡有着举足轻重的地位，它是应用流量的入口，对应用的可靠性和性能起着决定性的作用，因此负载均衡需要满足高性能、高可靠两个特点。MGW是美团点评自研的一款四层负载均衡，主要用于替代原有环境的四层负载均衡LVS，目前处理着美团点评数十 Gbps的流量、上千万的并发连接。本文主要介绍MGW是如何实现高性能、高可靠的。&/p&&h1&什么是负载均衡？&/h1&&p&互联网早期，业务流量比较小并且业务逻辑比较简单，单台服务器便可以满足基本的需求；但随着互联网的发展，业务流量越来越大并且业务逻辑也越来越复杂，单台机器的性能问题以及单点问题凸显了出来，因此需要多台机器来进行性能的水平扩展以及避免单点故障。但是要如何将不同的用户的流量分发到不同的服务器上面呢？&/p&&img src=&/50/v2-9bdeaaff23c253829cca9c_b.png& data-rawwidth=&713& data-rawheight=&419& class=&origin_image zh-lightbox-thumb& width=&713& data-original=&/50/v2-9bdeaaff23c253829cca9c_r.png&&&p&早期的方法是使用DNS做负载，通过给客户端解析不同的IP地址，让客户端的流量直接到达各个服务器。但是这种方法有一个很大的缺点就是延时性问题，在做出调度策略改变以后，由于DNS各级节点的缓存并不会及时的在客户端生效，而且DNS负载的调度策略比较简单，无法满足业务需求，因此就出现了负载均衡。&/p&&img src=&/50/v2-576db4a9c9aabd253e10e900_b.png& data-rawwidth=&721& data-rawheight=&290& class=&origin_image zh-lightbox-thumb& width=&721& data-original=&/50/v2-576db4a9c9aabd253e10e900_r.png&&&p&客户端的流量首先会到达负载均衡服务器，由负载均衡服务器通过一定的调度算法将流量分发到不同的应用服务器上面，同时负载均衡服务器也会对应用服务器做周期性的健康检查，当发现故障节点时便动态的将节点从应用服务器集群中剔除，以此来保证应用的高可用。&/p&&img src=&/50/v2-c5d66e35fb9_b.png& data-rawwidth=&751& data-rawheight=&392& class=&origin_image zh-lightbox-thumb& width=&751& data-original=&/50/v2-c5d66e35fb9_r.png&&&p&负载均衡又分为四层负载均衡和七层负载均衡。四层负载均衡工作在OSI模型的传输层，主要工作是转发，它在接收到客户端的流量以后通过修改数据包的地址信息将流量转发到应用服务器。&/p&&p&七层负载均衡工作在OSI模型的应用层，因为它需要解析应用层流量，所以七层负载均衡在接到客户端的流量以后，还需要一个完整的TCP/IP协议栈。七层负载均衡会与客户端建立一条完整的连接并将应用层的请求流量解析出来，再按照调度算法选择一个应用服务器，并与应用服务器建立另外一条连接将请求发送过去，因此七层负载均衡的主要工作就是代理。&/p&&p&既然四层负载均衡做的主要工作是转发，那就存在一个转发模式的问题，目前主要有四层转发模式：DR模式、NAT模式、TUNNEL模式、FULLNAT模式。&/p&&img src=&/50/v2-dc65bd07dbfb6f7c094c_b.png& data-rawwidth=&807& data-rawheight=&386& class=&origin_image zh-lightbox-thumb& width=&807& data-original=&/50/v2-dc65bd07dbfb6f7c094c_r.png&&&p&DR模式也叫作三角传输，通过修改数据包的目的MAC地址来让流量经过二层转发到达应用服务器，这样应用服务器就可以直接将应答发给应用服务器，性能比较好。由于这种模式需要依赖二层转发，因此它要求负载均衡服务器和应用服务器必须在一个二层可达的环境内，并且需要在应用服务器上配置VIP。&/p&&p&NAT模式通过修改数据包的目的IP地址，让流量到达应用服务器，这样做的好处是数据包的目的IP就是应用服务器的IP，因此不需要再在应用服务器上配置VIP了。缺点是由于这种模式修改了目的IP地址，这样如果应用服务器直接将应答包发给客户端的话，其源IP是应用服务器的IP，客户端就不会正常接收这个应答，因此我们需要让流量继续回到负载均衡，负载均衡将应答包的源IP改回VIP再发到客户端，这样才可以保证正常通信，所以NAT模式要求负载均衡需要以网关的形式存在于网络中。&/p&&p&TUNNEL模式的优缺点和DR是一样的，并且TUNNEL模式要求应用服务器必须支持TUNNEL功能。&/p&&p&FULLNAT模式是在NAT模式的基础上做一次源地址转换（即SNAT），做SNAT的好处是可以让应答流量经过正常的三层路由回到负载均衡上，这样负载均衡就不需要以网关的形式存在于网络中了，对网络环境要求比较低，缺点是由于做了SNAT，应用服务器会丢失客户端的真实IP地址。&/p&&img src=&/50/v2-b24c17d34c83b67a8b018ad39f7d4bd2_b.png& data-rawwidth=&677& data-rawheight=&461& class=&origin_image zh-lightbox-thumb& width=&677& data-original=&/50/v2-b24c17d34c83b67a8b018ad39f7d4bd2_r.png&&&p&下面详细介绍一下FULLNAT模式。首先负载均衡上需要存在一个localip池，在做SNAT时的源IP就是从localip池中选择的。当客户端流量到达负载均衡设备以后，负载均衡会根据调度策略在应用服务器池中选择一个应用服务器，然后将数据包的目的IP改为应用服务器的IP。同时从localip池中选择一个localip将数据包的源IP改为localip，这样应用服务器在应答时，目的IP是localip，而localip是真实存在于负载均衡上的IP地址，因此可以经过正常的三层路由到达负载均衡。由于FULLNAT比NAT模式多做了一次SNAT，并且SNAT中有选端口的操作，因此其性能要逊色于NAT模式，但是由于其较强的网络环境适应性，我们选择了FULLNAT作为MGW的转发模式。&/p&&h1&为什么选择自研四层负载均衡？&/h1&&p&选择自研四层负载均衡的原因主要有两个：第一个是考虑到硬件负载均衡成本比较高；第二个，随着美团点评业务流量越来越大，LVS出现了性能瓶颈以及运维成本的上升问题。&/p&&h2&硬件负载均衡成本问题&/h2&&ol&&li&硬件成本：中低端硬件负载均衡价格在数十万，高端的上百万，价格非常昂贵。当我们需要组成一个高可用集群时，需要数台机器，成本异常高。&/li&&li&人力成本：硬件负载均衡功能比较强大，配置比较灵活，这也导致在维护上，我们需要一些经过专业培训的人员，就增加了人力成本。&/li&&li&时间成本：当使用的过程中遇到bug或者新需求需要厂商提供新版本的时候，我们需要经过繁琐的流程向厂商上报，然后厂商再发布新版本供我们升级，时间周期非常长，在高速发展的互联网行业，这种周期是无法接受的。&/li&&/ol&&h2&LVS的性能问题&/h2&&p&最初美团点评使用的是LVS+Nginx组成的负载均衡结构，LVS做四层负载均衡，Nginx做七层负载均衡，但是随着美团点评流量的高速增长（几个月内无论新建连接数还是吞吐量都有三倍的增长），LVS故障频发，性能上出现瓶颈，因此我们自研了一款高性能、高可靠的四层负载均衡MGW来替换LVS。&/p&&h1&MGW如何实现高性能&/h1&&p&下面通过对比LVS的一些性能瓶颈来介绍MGW是如何实现高性能的。&/p&&h2&中断问题以及协议栈路径性能过长问题&/h2&&p&中断是影响LVS性能最重要的一个因素，假如我们一秒需要处理600万的数据包，每6个数据包产生一个硬件中断的话，那一秒就会产生100万个硬件中断，每一次产生硬件中断都会打断正在进行密集计算的负载均衡程序，中间产生大量的cache miss，对性能的影响异常大。&/p&&p&同时由于LVS是基于内核netfilter开发的一个应用程序，而netfilter是运行在内核协议栈的一个钩子框架。这就意味着当数据包到达LVS时，已经经过了一段很长的协议栈处理，但是这段处理对于LVS来说都不是必需的，这也造成了一部分不必要的性能损耗。&/p&&img src=&/50/v2-ff50812fa2eaee_b.png& data-rawwidth=&625& data-rawheight=&450& class=&origin_image zh-lightbox-thumb& width=&625& data-original=&/50/v2-ff50812fa2eaee_r.png&&&p&针对这两个问题，解决方法是使用轮询模式的驱动以及做kernel bypass，而DPDK提供的用户态PMD驱动恰好可以解决这两个问题。DPDK在设计时使用了大量硬件相关特性比如numa、 memory channel、 DDIO等，对性能优化非常大，同时提供了比较多网络方面的库，可以大大减小开发难度，提高开发效率。因此选择DPDK作为MGW的开发框架。&/p&&h2&锁&/h2&&p&由于内核是一个比较通用的应用程序，因此它并没有对一些特定场景做一些定制设计，这就导致一些公共的数据结构需要锁的保护。下面介绍一下出现锁的原因和MGW的解决方法。&/p&&img src=&/50/v2-c43ea71a17e1eb93995da9_b.png& data-rawwidth=&732& data-rawheight=&468& class=&origin_image zh-lightbox-thumb& width=&732& data-original=&/50/v2-c43ea71a17e1eb93995da9_r.png&&&p&首先介绍一下RSS（Receive Side Scaling），RSS是一个通过数据包的元组信息将数据包散列到不同网卡队列的功能，这时候不同的CPU再去对应的网卡队列读取数据进行处理，就可以充分利用CPU资源。之前介绍MGW使用FULLNAT的模式，FULLNAT会将数据包的元组信息全部改变，这样同一个连接，请求和应答方向的数据包有可能会被RSS散列到不同的网卡队列中，在不同的网卡队列也就意味着在被不同的CPU进行处理，这时候在访问session结构的时候就需要对这个结构进行加锁保护。&/p&&p&解决这个问题的方法有两种，一种就是在做SNAT选端口的时候，通过选择一个端口lport0让RSS(cip0, cport0, vip0, vport0) = RSS(dip0, dport0, lip0, lport0)相等；另外一种方法就是我们为每个CPU分配一个localip，在做SNAT选IP的时候，不同的CPU选择自己的localip，等应答回来以后，再通过lip和CPU的映射关系，将指定目的IP的数据包送到指定队列上。&/p&&p&由于第二种方法恰好可以被网卡的flow director特性支持，因此我们选择了第二种方法来去掉session结构的锁。&/p&&img src=&/50/v2-be2f4dbd7fced_b.png& data-rawwidth=&727& data-rawheight=&453& class=&origin_image zh-lightbox-thumb& width=&727& data-original=&/50/v2-be2f4dbd7fced_r.png&&&p&flow director可以根据一定策略将指定的数据包送到指定网卡队列，其在网卡中的优先级要比RSS高，因此我们在做初始化的时候就为每个CPU分配一个localip，比如为cpu0分配lip0，为cpu1分配lip1，为cpu2分配lip2，为cpu3分配lip3。 当一个请求包（cip0, cport0, vip0, vport0）到达负载均衡后，被RSS散列到了队列0上，这时这个包被cpu0处理。cpu0在对其做fullnat时，选择cpu0自己的localip lip0，然后将数据包（lip0, lport0, dip0, dport0）发到应用服务器，在应用服务器应答后，应答数据包（dip0, dport0, lip0,&br&lport0）被发到了负载均衡服务器。此时我们就可以在flow director下一条将目的IP为lip0的数据包送到队列0的规则，这样应答数据包就会被送到队列0让cpu0处理。这时候CPU在对同一个连接两个方向的数据包进行处理的时候就是完全串行的一个操作，也就不要再对session结构进行加锁保护了。&/p&&h2&上下文切换&/h2&&img src=&/50/v2-541e3a2caefe0b6abc73378_b.png& data-rawwidth=&953& data-rawheight=&449& class=&origin_image zh-lightbox-thumb& width=&953& data-original=&/50/v2-541e3a2caefe0b6abc73378_r.png&&&p&在设计时，希望控制平面与数据平面完全分离，数据平面专心做自己的处理，不被任事件打断。因此将CPU分成两组，一组用作数据平面一组用做控制平面。同时，对数据平面的CPU进行CPU隔离，这样控制平面的进程就不会调度到数据平面的这组CPU上面了；对数据平面的线程进行CPU绑定，这样就可以让每个数据线程独占一个CPU。 其他的控制平面的程序比如Linux kernel、 SSH等都跑在控制平面的这组CPU上。&/p&&h1&MGW如何做到高可靠&/h1&&p&下面从MGW集群、MGW单机以及应用服务器层这三个层介绍MGW如何在每一层实现高可靠。&/p&&h2&集群的高可靠&/h2&&img src=&/50/v2-041a0cdf30ea8af822cbad_b.png& data-rawwidth=&723& data-rawheight=&377& class=&origin_image zh-lightbox-thumb& width=&723& data-original=&/50/v2-041a0cdf30ea8af822cbad_r.png&&&p&MGW使用OSPF+ECMP的模式组成集群，通过ECMP将数据包散列到集群中各个节点上，再通过OSPF保证单台机器故障以后将这台机器的路由动态的剔除出去，这样ecmp就不会再给这台机器分发流量，也就做到了动态的failover。&/p&&img src=&/50/v2-8b30cacd94a4fe9e8ff6ba7de90d3985_b.png& data-rawwidth=&926& data-rawheight=&402& class=&origin_image zh-lightbox-thumb& width=&926& data-original=&/50/v2-8b30cacd94a4fe9e8ff6ba7de90d3985_r.png&&&p&传统的ecmp算法有一个很严重的问题，当集群中节点数量发生变化以后，会导致大部分流量的路径发生改变，发生改变的流量到达其他MGW节点上时是找不到自己的session结构的，这就会导致大量的连接出现异常，对业务影响很大，并且当我们在对集群做升级操作时会将每个节点都进行一次下线操作，这样就加重了这个问题的影响。&/p&&p&一种解决方式是使用支持一致性hash的交换机，这样在节点发生变化的时候，只有发生变化的节点上面的连接会有影响，其他连接都会保持正常，但是支持这种算法的交换机比较少，并且也没有完全实现高可用，因此我们做了集群间的session同步功能。&/p&&img src=&/50/v2-0f85bb5e5871d14fee34eb_b.png& data-rawwidth=&915& data-rawheight=&403& class=&origin_image zh-lightbox-thumb& width=&915& data-original=&/50/v2-0f85bb5e5871d14fee34eb_r.png&&&p&集群中每个节点都会全量的将自己的session同步出去，使集群中每个节点都维护一份全局的session表，因此无论节点变化以后流量的路径以任何形式改变，这些流量都可以找到自己的session结构，也就是说可以被正常的转发，这样就可以在集群中节点数量发生变化时保证所有连接正常。&/p&&p&在设计的过程中主要考虑了两个问题：第一个是故障切换，第二个是故障恢复以及扩容。&/p&&h3&故障切换&/h3&&img src=&/50/v2-26fd5ed20cda588b3dd3b4d_b.png& data-rawwidth=&951& data-rawheight=&325& class=&origin_image zh-lightbox-thumb& width=&951& data-original=&/50/v2-26fd5ed20cda588b3dd3b4d_r.png&&&p&在故障切换的问题上，我们希望在机器故障以后，交换机可以立刻将流量切到其他机器上，因为流量不切走，意味着到达这台机器流量会被全部丢掉，产生大量丢包。经过调研测试发现，当交换机侧全部使用物理接口并且服务器侧对接口进行断电时，交换机会瞬间将流量切换到其他机器上。通过一个100ms发两个包的测试（客户端和服务端各发一个），这种操作方法是0丢包的。&/p&&p&由于故障切换主要依赖于交换机的感知，当服务器上出现一些异常，交换机感知不到时，交换机就无法进行故障切换操作，因此需要一个健康自检程序，每半秒进行一次健康自检，当发现服务器存在异常时就对服务器执行网口断电操作，从而让流量立刻切走。&/p&&p&故障切换主要依赖于网口断电操作并且网卡驱动是跑在主程序里面的，当主程序挂掉以后，就无法再对网口执行断电操作了，因此为了解决这个问题，主进程会捕获异常信号，当发现异常时就对网卡进行断电操作，在断电操作结束以后再继续将信号发给系统进行处理。&/p&&p&经过以上设计，MGW可以做到升级操作0丢包，主程序故障0丢包，其他异常（网线等）会有一个最长500ms的丢包，因为这种异常需要靠自检程序去检测，而自检程序的周期是500ms。&/p&&h3&故障恢复与扩容&/h3&&img src=&/50/v2-7c70d5ffcc9b40_b.png& data-rawwidth=&927& data-rawheight=&352& class=&origin_image zh-lightbox-thumb& width=&927& data-original=&/50/v2-7c70d5ffcc9b40_r.png&&&p&无论是在进行故障恢复还是扩容操作，都会导致集群节点数量发生变化，这样也就会导致流量路径发生变化。当变化的流量到达集群中原有的节点时，因为原有节点都维护着一个全局的session表，因此这些流量是可以被正常转发的；但是如果流量到达了新机器上，这个机器是没有全局session表的，那么这部分流量就会全部被丢弃。为了解决这个问题，MGW在上线以后会经历一个预上线的中间状态，在这个状态上，MGW不会让交换机感知到自己上线了，这样交换机也就不会把流量切过来。首先MGW会对集群中其他节点发送一个批量同步的请求，其他节点收到请求以后会将自己的session全量的同步到新上线的节点上，新上线节点在收到全部session以后才会让交换机感知到自己上线，这时交换机再将流量切过来就可以正常被转发出去了。&/p&&p&在这个过程中主要存在两点问题。&br&第一个问题是，由于集群中并没有一个主控节点来维护一个全局的状态，如果request报丢失或者session同步的数据丢失的话，那新上线节点就没办法维护一个全局的session状态。但是考虑到所有节点都维护着一个全局的session表，因此所有节点拥有的session数量都是相同的，那么就可以在所有节点每次做完批量同步以后发送一个finish消息，finish消息中带着自己拥有的session数量。当新上线节点收到finish消息以后，便会以自己的session数量与finish中的数量做对比。当达到数量要求以后，新上线节点就控制自己进行上线操作。否则在等待一定的超时时间以后，重新进行一次批量同步操作，直到达到要求为止。&/p&&p&另外一个问题是在进行批量同步操作时，如果出现了新建连接，那么新建连接就不会通过批量同步同步到新上线的机器上。如果新建连接特别多，就会导致新上线机器一直达不到要求。因此，需要保证处于预上线状态的机器能接收到增量同步数据，因为新建连接可以通过增量同步同步出来。通过增量同步和批量同步就可以保证新上线机器可以最终获得一个全局的session表。&/p&&h2&单机高可靠&/h2&&img src=&/50/v2-b2c9d509e6cdb64b1af824acb9ec0dd9_b.png& data-rawwidth=&921& data-rawheight=&469& class=&origin_image zh-lightbox-thumb& width=&921& data-original=&/50/v2-b2c9d509e6cdb64b1af824acb9ec0dd9_r.png&&&p&在单机高可靠方面，MGW做了一个自动化测试平台，自动化平台通过连通性和配置的正确性来判断一个测试用例是否执行成功，失败的测试用例平台可以通过邮件通知测试人员。在每次新功能迭代结束以后，都会将新功能的测试用例加到自动化平台里面，这样在每次上线之前都进行一次自动化测试，可以大大避免改动引发的问题。&/p&&p&在之前，每次上线之前都需要进行一次手动的回归测试，回归测试非常耗时并且很容易遗漏用例，但是为了避免改动引发新问题又不得不做，有了自动化测试平台以后，大大提高了回归测试的效率和可靠性。&/p&&h2&RS可靠性&/h2&&h3&节点平滑下线&/h3&&img src=&/50/v2-51d7cc3572ad5cdddc72c9e_b.png& data-rawwidth=&900& data-rawheight=&353& class=&origin_image zh-lightbox-thumb& width=&900& data-original=&/50/v2-51d7cc3572ad5cdddc72c9e_r.png&&&p&在RS可靠性方面，MGW提供了节点平滑下线功能，主要是为了解决当用户需要对RS进行升级操作时，如果直接将需要升级的RS下线，那这个RS上存在的所有连接都会失败，影响到业务。此时如果调用MGW的平滑下线功能，MGW就可以保证此RS已有连接正常工作，但不会往上面调度新的连接。当所有已有连接结束以后，MGW会上报一个结束的状态，用户就可以根据这个结束的状态对RS进行升级操作，升级后再调用上线接口让这个RS器进行正常的服务。如果用户平台支持自动化应用部署，那就可以通过接入云平台使用平滑下线功能，实现完全自动化且对业务无影响的升级操作。&/p&&h3&一致性源IP Hash调度器&/h3&&p&源IP Hash调度器主要是保证相同的客户端的连接被调度到相同应用服务器上，也就是说建立一个客户端与应用服务器一对一的映射关系。普通的源IP Hash调度器在应用服务器发生变化以后会导致映射关系发生改变，会对业务造成影响。&/p&&p&因此我们开发了一致性源IP Hash调度器，保证在应用服务器集群发生变化时，只有发生变化的应用服务器与客户端的映射关系发生改变，其他都是不变的。&/p&&img src=&/50/v2-3ea90f6c890a01b410e17dc67a64c4c2_b.png& data-rawwidth=&957& data-rawheight=&440& class=&origin_image zh-lightbox-thumb& width=&957& data-original=&/50/v2-3ea90f6c890a01b410e17dc67a64c4c2_r.png&&&p&为了保证流量的均衡，首先在hash环上分配固定数量的虚拟节点，然后将虚拟机节点均衡的重分布到物理节点上，重分布算法需要保证两点：&/p&&ol&&li&在物理节点发生变化时，只有少数虚拟节点映射关系发生变化，也就是要保证一致性Hash的基本原则。&/li&&li&因为MGW是以集群的形式存在的，当多个应用服务器发生上线下线操作时，反馈到不同的MGW节点上就有可能会出现顺序不一致的问题，因此无论不同的MGW节点产生何种应用服务器上下线顺序，都需要保证最终的映射关系一致，因为如果不一致就导致相同客户端的连接会被不同的MGW节点调度到不同的应用服务器上，也就违背了源IP Hash调度器的原则。&/li&&/ol&&p&综合以上两点，Google Maglev负载均衡的一致性Hash算法是一个很好的例子，在paper中有详细的介绍，这里就不过多讨论了。&/p&&h1&总结&/h1&&p&经过美团点评以及美团云的流量验证，MGW无论在传统网络环境还是overlay的大二层环境下都有出色的性能和稳定性表现。在业务场景方面涵盖数据库业务，千万级别的长连接业务，嵌入式业务，存储业务以及酒店、外卖、团购等Web应用业务。在业务需求快速变化的环境下，MGW在不断完善自身功能，在各种业务场景下都有良好的表现。 在未来的一段时间内，MGW除了会完善四层的功能需求外，也会考虑向七层方向发展。&/p&&h1&参考资料&/h1&&ol&&li&&a href=&/?target=http%3A///content/www/us/en/communications/data-plane-development-kit.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&DPDK&i class=&icon-external&&&/i&&/a&.&/li&&li&&a href=&/?target=http%3A//zh.linuxvirtualserver.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&LVS&i class=&icon-external&&&/i&&/a&.&/li&&li&Eisenbud D E, Yi C, Contavalli C, et al. &a href=&/?target=http%3A///media//zh-CN//pubs/archive/44824.pdf& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Maglev: A Fast and Reliable Software Network Load Balancer&i class=&icon-external&&&/i&&/a&.&/li&&/ol&&br&&p&&strong&不想错过技术博客更新？想给文章评论、和作者互动？第一时间获取技术沙龙信息？&/strong&&/p&&p&&strong&请关注我们的官方微信公众号“美团点评技术团队”。&/strong&&/p&
本文整理自美团点评技术沙龙第14期：美团背后的故事－你不知道的美团云。美团点评技术沙龙由美团点评技术团队主办，每月一期。每期沙龙邀请美团点评及其他互联网公司的技术专家分享来自一线的实践经验，覆盖各主要技术领域。目前沙龙会分别在北京、上海和厦…
经典的意思是经过时间验证的。&br&排名第一的 &a data-hash=&dcb32aa26dd3a456bd79d2c2cdffa433& href=&///people/dcb32aa26dd3a456bd79d2c2cdffa433& class=&member_mention& data-editable=&true& data-title=&@严林& data-hovercard=&p$b$dcb32aa26dd3a456bd79d2c2cdffa433&&@严林&/a&的回答列举了他自己选择的最近15年经典，而且其中很多都是10年以后的文章。不可否认，这些是目前分布式比较热门的话题，但我觉得其中能称得上经典的只有一小部分（1，2，3，12，13）。其他文章不能说写的不好，但个人认为离经典还差一些。&br&&br&读经典是为了掌握这个领域最基本的思想，知其然，更要知其所以然。比如chubby，读实现之前，难道不更应该看看paxos算法本身是什么？&br&&br&其实美国比较好的大学的研究生分布式系统课应该都会有reading list，这些差不多就是经典了。&br&比如cmu的：&a href=&///?target=http%3A//www.cs.cmu.edu/%7Edga/15-712/F13/syllabus.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&15-712 Syllabus&i class=&icon-external&&&/i&&/a&。如果你要选30篇，70年代至今分布式最经典的文章，大概就是这些了。你会看到上面好多文章是很老的。为什么还要看？因为想法被继承了，这些文章可以帮你了解所以然。当然上面有些文章其他同学也提到了（比如leslie lamport的paxos等）。&br&&br&对db感兴趣的，可以看看这个：&a href=&///?target=http%3A//www.cs.cmu.edu/%7Epavlo/courses/fall2013/reading-list.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Reading List // 15-799 :: Advanced Topics in Database Systems (Fall 2013)&i class=&icon-external&&&/i&&/a& reynold xin 维护了这个&a href=&///?target=https%3A///rxin/db-readings& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&rxin/db-readings · GitHub&i class=&icon-external&&&/i&&/a&
经典的意思是经过时间验证的。 排名第一的 的回答列举了他自己选择的最近15年经典，而且其中很多都是10年以后的文章。不可否认，这些是目前分布式比较热门的话题，但我觉得其中能称得上经典的只有一小部分（1，2，3，12，13）。其他文章不能说写的不好…
&p&之前的回答本来就觉得一些细节处并不严谨，现在回看=/=。我觉得严谨是一个讨论技术的必要条件，觉得现在也有能力写的严谨，于是想把回答改的尽量严谨，最后发现不如重写，顺便补充了我想补充的内容，结果就是更长=.=。Paxos是个精巧，又强大的协议，仅从过程的复杂度来说，确实如作者本人一再说的那样是个“简单的协议”，但是可以从非常多的角度来理解它为何正确，而原本的流程也并不适合直接工程化，这也是大概为什么工程上它存在如此多的变体。希望这个回答的让人更快的感受paxos的魅力，建立一个初步印象的同时不给人以误导。最后依然推荐larmport自己写的和paxos相关的三篇论文：&& The Part-Time Parliament&&、&&Paxos made simple&&、&&Fast Paxos&&前面关于Paxos的论述。&br&&/p&&p&上周和一个有真正paxos工程经验的人讨论一下paxos，paxos现在大多是应用于replication的一致性，用来实现一个 多节点一致的日志，和他 的讨论让我觉得要想真正的精确掌握paxos和它对应的强一致性领域，也许只有真正的在工程中实现过才行。这个回答只能当做是想要了解原理的入门吧，甚至可能有些微妙的地方还会产生误导。它介绍了paxos面向的问题，以及为何它的流程要这么设计，但还是希望对有兴趣阅读这个问题的有所帮助。&br&&/p&&p&现在看开头这段话是在是觉得有点羞耻，遂改之。我了解paxos是从找工作开始，比较详细的了解则是在毕设，自己动手了写了个类似Zookeeper的系统，paxos本身并不复杂，在&&paxos made simple&& Lamport用两段话就描述清楚了它的流程，他老人家也说paxos其实是个简单的算法。但是是我在工程领域见过最为精妙的算法。我想论述Paxos为什么难以理解会比描述Paxos的流程长的多的多。我最初学习Paxos是从《从Paxos到Zookeeper:分布式一致性原理与实践》，现在看来并不是个很好选择，作者讲解的方式是直接翻译论文，论述ZAB和paxos关系的部分我也觉得不是很严谨。如果真心觉得Paxos的原文不知所云，也不知道能拿来干嘛，可以从阅读Raft的论文开始，如果真的有兴趣，强推Raft作者Diego Ongaro那篇300页的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》，不只是讲解了Raft协议，而且系统的论述Paxos类似的一致性协议，不仅从原理，也从工程角度出发，涉及方方面面，在写毕设中了就是写不动就翻翻的良作。我个人觉得阅读任何&b&号称浅显易懂的解说Paxos算法的描述（比如下文=/=），最多只是让你更好的入门，要更深的理解Paxos以及所有等同于它的一致性协议，ZAB,Raft,ViewStamp，直接阅读相关论文，理解证明，理解它们哪里不同，为何本质上相同，与人探讨，在工程上自己实现，或者阅读开源实现的源代码才是最好的方式。分布式一致性是个有趣的领域，而Paxos和类似的协议对这个问题的重要性不喻，在过去的十年，Paxos几乎等价于分布式一致性。&/b&&br&&/p&&p&&br&&/p&&p&之前的答案最大的不严谨之处在于两个事件“先后”这种时序关系的处理上。paxos是个分布式一致性协议，它的事件需要多个节点共同参与，一个事件完成是指多个节点上均完成了自身负责的单机子事件(就让我门把这样的事件称为&分布式事件&)，这样的分布式事件可以看作是多个单机子事件的复合，但&b&是即不能从两个分布式事件的先后推导出某个节点上它们的单机子事件的先后，也不能根据某个节点上两个单机子事件的先后断言它们对应的分布式事件的先后&/b&。举一个简单的例子，两个节点P1，P2;分布式事件a1设置每节点的本地变量v=1,分布式式事件a2设置每个节点本地变量v=2，如果我们称a1先于a2完成，那么对于节点P1而言，v=1发生在v=2之前还是之后都有可能;反之如果P1上v=1发生在v=2之前，a1和a2哪个县完成也都有可能。&br&&br&原来的回答有些地方论述 分布式事件a1在a2之后(先)时，默认了单节点上，a1会比a2先达成状态，或者反之。&br&&br&实际上为了论证paxos的正确性，并不需要借助于分布式事件的时序(起码无用太在意物理时序），对于paxos流程中的分布式事件，例如提案被通过，值被决定，让我们忘记它们之间物理时间上的先后关系吧。&/p&&p&&br&&/p&&p&下面就开始假装推导出paxos，作为一种理解协议的流程和协议如何保证正确性的方式。这样的推导的过程远比我想象的冗长；&b&相比之下，论文中Lamport自己推导出Paxos的过程简洁、巧妙、漂亮，但是更抽象。在末尾用自己的语言描述了这种方式，作为补充&/b&。补充的版本基本思路来自&&Paxos made simple&&，和原文略有不同；总共不到1500字，却既说明了Paxos是如何得到的，又严谨的论证了Paxos的正确性。&/p&&p&首先我们简单介绍paxos所保证的一致性的具体含义；达成一致的条件(何时达成一致）；基于的一个基本的数学原理；以及它需要满足的假设。&br&&br&什么是一致性?实际上这个词在不同地方语义并不那么一致，Paxos面向的是一个理论的一致问题，这个问题的通俗描述是：&br&&br&有一个变量v，分布在N个进程中，每个进程都尝试修改自身v的值，它们的企图可能各不相同，例如进程A尝试另v=a,进程B尝试另v=b，但最终所有的进程会对v就某个值达成一致,即上述例子中如果v=a是v达成一致时的值，那么B上，最终v也会为a。&b&需要注意的是某个时刻达成一致并不等价于该时刻所有进程的本地的v值都相同&/b&，有一个原因是进程可能挂掉，你不能要求挂掉的进程任何事；更像是最终所有存活的进程本地v的值都会相同。&br&&br&这个一致性需要满足三个要求：&br&&br&1.v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v=2，那么这样的一致也太容易了，也没有任何实际意义。&br&2.一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性。&br&3.一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性。&/p&&p&Paxos中变量v达成一致的条件：
&b&N个进程中大多数（超过一半） 进程都认为v是同一个值，&/b&例如c，那么我们称&b&v被决定为c&/b&。这样即使少数进程挂掉了，也不会使得一致无法达成。&/p&&p&Paxos保证的一致性如下：&b&不存在这样的情形，某个时刻v被决定为c，而另一个时刻v又决定为另一个值d。&/b&由这个定义我们也看到，当v的值被决定后，Paxos保证了它就像是个单机的不可变变量，不再更改。也因此，对于一个客户端可以多次改写值的可读写变量在不同的节点上的一致性问题，Paxos并不能直接解决，它需要和状态机复制结合。&/p&&p&Paxos基于的数学原理：
我们称大多数进程组成的集合为法定集合，&b&两个法定集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质&/b&。 例如A,B,C,D,F进程组成的全集，法定集合Q1包括进程A,B,C，Q2包括进程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程。如果要说Paxos最根本的原理是什么，那么就是这个简单性质。同时，可以注意到，这个性质和达成一致的定义相呼应。&/p&&p&Paxos中进程之间是平等的，即不存在一个特殊的进程，这是由于&b&如果协议依赖于某个特殊的进程，那么这个进程挂掉势必会影响协议;而对于分布式环境，无法保证单个进程必然必活，能够容忍一定数量的进程挂掉，是分布式协议的必然要求。&/b&这是推导过程所要遵循的一个原则，就称为平等性原则好了。&/p&&p&消息是进程间通信的唯一手段，对于分布式环境来说，这是显然的。&/p&&p&Paxos要求满足的前置假设只有一个：消息内容不会被篡改；更正式的说是无拜占庭将军问题。&/p&&p&假装的推导总是先从一些具体的场景开始，既然Paxos的假设仅仅只是消息不会被篡改,保证了这点任意场景下都能保证一致性，那么对于举例的场景它必然是能够保证一致性的；因此不妨先使得协议流程能在当前场景下能保证一致性，然后再举出另一个场景，当前的协议流程无法再该场景下满足一致性，接着再丰富协议流程，满足该场景，如此往复，最终得到完整的paxos协议，最后再不失一般性的论证协议对任意场景都能保证一致性。&/p&&p&进程的平等性假设会带来如下的问题，考虑如下的场景1：三个进程的场景P1,P2P3（n个进程的场景类似），P1尝试令v的值被决定为a,P2尝试令v被决定为b。假设它们都先改写了自身的v值，然后发送消息尝试改修P3的v值。显然如果P3收到两个消息后都满足了它们的企图，那么v就会两次被决定为不同的值，这破坏了之前的定义。因此P3必须得拒绝掉其中一个进程的请求，&b&如何拒绝也是我们最先考虑的问题。&/b&一个最简单的拒绝策略是先来后到，P3只会接受收到的第一个消息，拒绝之后的消息，即只会改写v一次。按照这个策略，如果P1发送的消息首先到达P3，那么P3接受该消息令v=a,拒绝掉后到的来自P2的消息。但是这个策略会引入一个另外的问题；在场景1的基础上考虑这样的场景1’，P3也尝试决定v的值，P3尝试令v被决定为c，那么P1，P2，P3都尝试修改v的值，首先P1令v=a,P2令v=b,P3令v=c(相当于自己给自己发消息），按照之前的策略，每个进程只会改写v的值一次，那么将永远不会出现两个进程的v值相等的情况，即v永远无法被决定。更正式的说，这样的协议不满足活性，活性要求协议总能达成一致。由此我们也得到第一个结论:&b&进程必须能够多次改写v的值&/b&。同时我们也要意识到：&b&当进程收到第一个消息时，进程是没有任何理由拒绝这个消息的请求的。&/b&&/p&&p&&br&&/p&&p&拒绝策略总是需要有一个依据，之前我们的依据是消息到达的先后，只接受第一个到达的消息，但这导致不满足活性。现在我们需要另一个拒绝策略，也就是需要另一个依据，这个依据至少能够区分两个消息。&b&为此我们引入一个ID来描述这个消息，这样就可以根据ID的大小来作为拒绝或接受的依据；&/b&选择ID更大的消息接受和选择ID更小的消息接受是两种完全对称的策略，不妨选择前者。这个策略不会导致明显的活性问题，ID更大的消息总是能被接受，一个节点可以多次更改v的值。例如在场景1'中，只要P1的消息ID比P3发送给自己的消息ID更大，P3就会接受P1的消息，令v=a，从而令v的值被决定为a。再来考虑最初的场景1，不妨假设P1的消息ID大于P2的消息ID，根据P3收到消息的先后可以分为两种情况：&br&&br&1. P3先收到P1的消息，记做场景1-2。由于P1的消息是P3收到的第一个消息，P3接受该请求，令v=a；同时为了能对之后收到的消息作出是否接受的判断，P3需要记录该消息的ID作为判断的依据。之后P3又收到P2的消息，该消息的ID小于P3记录的ID(即P1的消息ID)，因此P3拒绝该消息，这样我们的目的就达到。&br&&br&2. P3先收到P2的消息，记作场景1-3。同样P3接受该消息，令v=b,记录该消息的ID。之后P3收到P1的消息，由于P1的消息ID大于P3记录的ID，因此P3无法拒绝该消息，之前的问题依旧存在。&/p&&p&尽管对于场景1-3，目前的策略依旧无法保证一致性，但是起码我们缩小协议不适用的范围。先总结下我们目前的策略，并定义一些称谓以方便后面的论述。&b&我们称呼进程P发送的尝试修改另一个进程中变量v的值的消息称之为提案，记作Proposal；提案的ID记作proposal_id；提案中会附带一个值，如果一个进程接受一个提案，则修改自身的v值为该提案中的值。如果一个提案被大多数进程所接受，那么称提案被通过，此时显然v被决定为提案中的值。进程P记录的接受的提案ID记做a_proposal_id。&/b&&/p&&p&之前我们尚未清晰定义a_proposal_id，实际上我们也就并未清晰的定义我们的拒绝策略，当P收到一个提案Proposal-i时，可能已经收到过多个提案，Proposal-i.proposal_id该和其中哪个提案的proposal_id比较，我们并未定义。我们定义为其中的最大者，这样实际上进程P只需维护一个a_proposal_id即可，当收到一个Proposal时，更新a_proposal_id = Max(Proposal.proposal_id，a_proposal_id）。同时在之前的描述中我们应当注意到实际上一个进程存在&b&两个功能&/b&：&br&&br&1. 进程主动尝试令v的值被决定为某个值，向进程集合广播提案。&br&&br&2. 进程被动收到来自其它进程的提案，判断是否要接受它。&br&&br&因此可以把一个&b&进程分为两个角色，称负责功能1的角色是提议者，记作Proposer，负责功能2的角色是接受者，记作Acceptor。&/b&由于两者完全没有耦合，所以&b&并不一定需要在同个进程&/b&，但是为了方面描述，我们假定一个进程同时担任两种角色，而实际的工程实现也往往如此。&/p&&p&接着我们尝试解决场景1-3,这看起来很难。P3作为接受者，收到P2的提案之前未收到任何消息，只能接受该提案，而由于P1的提案proposal_id大于P2的提案，我们的拒绝策略也无法让P3拒绝P2。我们先不急着推导具体可行的策略，先考虑下解决1-3场景可能的角度，有如下三种角度可以入手：&br&&br&1. P3能够拒绝掉P2的提案。&br&&br&2. P3能够拒绝掉P1的提案。&br&&br&3. 限制P1提出的提案中的值，如果P1的提案中的值与P2的提案一致，那么接受P1也不会破坏一致性。&br&&br&接着我们分析三个角度的可行性：&br&&br&角度1需要P3有做出拒绝的依据，由于消息是进程间通信唯一手段，这要求P3在收到P2的提案之前必须先收到过其它消息。对于场景1-3，只有P1，P2是主动发送消息的进程，P2当然不可能额外还发送一个消息试图令P3拒绝自己随后的提案。那么唯一的可能是P1在正式发送提案前，还发送了一个消息给P3，这个消息先于P2的提案到达，给了P3拒绝P2提案的理由。如果沿用目前的拒绝策略，那么P1只需先发送随后提案的proposal_id给P3，P3更新a_proposal_id 为 该消息附带的proposal_id，这样a_proposal_id将大于P2的提案的proposal_id，而导致P2的提案被拒绝，似乎这是一个可行的角度。&br&&br&对于角度2，我们目前的策略无法做到这一点，因此除了proposal_id外，我们还得给提案附加上额外的信息作为另外的拒绝策略的依据。提案由进程提出，也许我们可以附加进程的信息，但是就算P3得知P1的提案由P1提出，P3又凭什么歧视P1，这违反进程的平等性假设。似乎这个角度不是一个好角度。&br&&br&最后我们分析一下角度3，角度3提供了与1,2截然不同的思路，它不再是考虑如何拒绝，而把注意力放在&b&如何对提案的值做出恰当的限制上&/b&。对于场景1-3而言，从这个角度，由于P3无法拒绝P1和P2的提案中的任何一个，因此&b&P1的提案的值就必须与P2的提案一致&/b&；这也意味着了P1在正式提出提案前，需要有途径能获悉P2的提案的值。如我们上面一直强调的，消息是唯一的通信手段，P1必须收到来自其它节点消息才有可能得知P2提出的提案的值。P1可以被动的等待收到消息，也可以主动的去询问其它节点等待回复。后者显然是更好的策略，没有收到