分布式理论之一：Paxos算法的通俗理解 - esingchan - 推酷
分布式理论之一：Paxos算法的通俗理解 - esingchan
维基的简介：Paxos算法是莱斯利&兰伯特（Leslie Lamport，就是 LaTeX 中的&La&，此人现在在微软研究院）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。
Paxos算法目前在Google的Chubby、MegaStore、Spanner等系统中得到了应用，Hadoop中的ZooKeeper也使用了Paxos算法，在上面的各个系统中，使用的算法与Lamport提出的原始Paxos并不完全一样，这个以后再慢慢分析。本博文的目的是，如何让一个小白在半个小时之内理解Paxos算法的思想。小白可能对数学不感兴趣，对分布式的复杂理论不熟悉，只是一个入门级程序员。之所以想写这篇博文，是因为自己看了网上很多介绍Paxos算法的文章，以及博客，
包括Lamport的论文，
感觉还是难以理解，大多过于复杂，本人一直认为，复杂高深的理论背后一定基于一些通用的规律，而这些通用的规律在生活中其实我们早就遇到过，甚至用过。所以，我们先忽略Paxos算法本身，从生活中的小事开始谈起。
假如有一群驴友要决定中秋节去旅游，这群驴友分布在全国各地，假定一共25个人，分别在不同的省，要决定到底去拉萨、昆明、三亚等等哪个地点（会合时间中秋节已经定了，此时需要决定旅游地）。最直接的方式当然就是建一个QQ群，大家都在里面投票，按照少数服从多数的原则。这种方式类似于“共享内存”实现的一致性，实现起来简单，但Paxos算法不是这种场景，因为Paxos算法认为这种方式有一个很大的问题，就是QQ服务器挂掉怎么办？Paxos的原则是容错性一定要很强。所以，Paxos的场景类似于这25个人相互之间只能发短信，需要解决的核心问题是，哪怕任意的一部分人（Paxos的目的其实是少于半数的人）“失联”了，其它人也能够在会合地点上达成一致。好了，怎么设计呢？
这25个人找了另外的5个人（当然这5个人可以从25个人中选，这里为了描述方便，就单拿出另外5个人），比如北京、上海、广州、深圳、成都的5个人，25个人都给他们发短信，告诉自己倾向的旅游地。这5个人相互之间可以并不通信，只接受25个人发过来的短信。这25个人我们称为驴友，那5个人称为队长。
先来看驴友的逻辑。驴友可以给任意5个队长都发短信，发短信的过程分为两个步骤：
第一步（申请阶段）：询问5个队长，试图与队长沟通旅游地。因为每个队长一直会收到不同驴友的短信，不能跟多个驴友一起沟通，在任何时刻只能跟一个驴友沟通，按照什么原则才能做到公平公正公开呢？这些短信都带有发送时间，队长采用的原则是同意与短信发送时间最新的驴友沟通，如果出现了更新的短信，则与
更新的驴友沟通。总之，作为一个有话语权的人，只有时刻保持倾听最新的呼声，才能做出最明智的选择。在驴友发出短信后，等着队长回复。某些队长可能会回复说，你这条短信太老了，我不与你沟通；有些队长则可能返回说，你的短信是我收到的最新的，我同意跟你沟通。对于后面这些队长，还得返回自己决定的旅游地。关于队长是怎么决定旅游地的，后面再说。
对于驴友来说，第一步必须至少有半数以上队长都同意沟通了，才能进入下一步。否则，你连沟通的资格都没有，一直在那儿狂发吧。你发的短信更新，你获得沟通权的可能性才更大。。。。。。
因为至少有半数以上队长（也就是3个队长以上）同意，你才能与队长们进行实质性的沟通，也就是进入第二步；而队长在任何时候只能跟1个驴友沟通，所以，在任何时候，不可能出现两个驴友都达到了这个状态。。。当然，你可以通过狂发短信把沟通权抢了。。。。
对于获得沟通权的那个驴友（称为A），那些队长会给他发送他们自己决定的旅游地（也可能都还没有决定）。可以看出，各个队长是自己决定旅游地的，队长之间无需沟通。
第二步（沟通阶段）：这个幸运的驴友收到了队长们给他发的旅游地，可能有几种情况：
第一种情况：跟A沟通的队长们（不一定是全部5个队长，但是半数以上）全部都还没有决定到底去那儿旅游，此时驴友A心花怒放，给这些队长发第二条短信，告诉他们自己希望的旅游地（比如马尔代夫）；
可能会收到两种结果：一是半数以上队长都同意了，于是表明A建议的马尔代夫被半数以上
都同意了，整个决定过程完毕了，其它驴友迟早会知道这个消息的，A先去收拾东西准备去马尔代夫；除此之外，表明失败。可能队长出故障了，比如某个队长在跟女朋友打电话等等，也可能被其它驴友抢占沟通权了（因为队长喜新厌旧嘛，只有要更新的驴友给自己发短信，自己就与新人沟通，A的建议队长不同意）等等。不管怎么说，苦逼的A还得重新从第一步开始，重新给队长们发短信申请。
第二种情况：至少有一个队长已经决定旅游地了，A可能会收到来自不同队长决定的多个旅游地，这些旅游地是不同队长跟不同驴友在不同时间上做出的决定，那么，A会先看一下，是不是有的旅游地已经被半数以上队长同意了（比如3个队长都同意去三亚，1个同意去昆明，另外一个没搭理A），如果出现了这种情况，那就别扯了，说明整个决定过程已经达成一致了，收拾收拾准备去三亚吧，结束了；如果都没有达到半数以上（比如1个同意去昆明，1个同意去三亚，2个同意去拉萨，1个没搭理我），A作为一个高素质驴友，也不按照自己的意愿乱来了（Paxos的关键所在，后者认同前者，否则整个决定过程永无止境），虽然自己原来可能想去马尔代夫等等。就给队长们发第二条短信的时候，告诉他们自己希望的旅游地，就是自己收到的那堆旅游地中最新决定的那个。（比如，去昆明那个是北京那个队长前1分钟决定的，去三亚的决定是上海那个队长1个小时之前做出来的，于是顶昆明）。驴友A的想法是，既然有队长已经做决定了，那我就干脆顶最新那个决定。
从上面的逻辑可以看出，一旦某个时刻有半数以上队长同意了某个地点比如昆明，紧跟着后面的驴友B继续发短信时，如果获得沟通权，因为半数以上队长都同意与B沟通了，说明B收到了来自半数以上队长发过来的消息，B必然会收到至少一个队长给他发的
这个结果（否则说明半数以上队长都没有同意昆明这个结果，这显然与前面的假设矛盾），B于是会顶这个最新地点，不会更改，因为后面的驴友都会顶昆明，因此同意昆明的队长越来越多，最终必然达成一致。
看完了驴友的逻辑，那么队长的逻辑是什么呢？
队长的逻辑比较简单。
在申请阶段，队长只会选择与最新发申请短信的驴友沟通，队长知道自己接收到最新短信的时间，对于更老的短信，队长不会搭理；队长同意沟通了的话，会把自己决定的旅游地（或者还没决定这一信息）发给驴友。
在沟通阶段，驴友C会把自己希望的旅游地发过来（同时会附加上自己申请短信的时间，比如3分钟前），所以队长要检查一下，如果这个时间（3分钟前）确实是当前自己最新接收到申请短信的时间（说明这段时间没有驴友要跟自己沟通），那么，队长就同意驴友C的这个旅游地了（比如昆明，哪怕自己1个小时前已经做过去三亚的决定，谁让C更新呢，于是更新为昆明）；如果不是最新的，说明这3分钟内又有其它驴友D跟自己申请了，因为自己是个喜新厌旧的家伙，同意与D沟通了，所以驴友C的决定自己不会同意，等着D一会儿要发过来的决定吧。
Paxos的基本思想大致就是上面的过程。可以看出，其实驴友的策略才是Paxos的关键。让我们来跟理论对应一下。
Paxos主要用于保证分布式存储中副本（或者状态）的一致性。副本要保持一致，那么，所有副本的更新序列就要保持一致。因为数据的增删改查操作一般都存在多个客户端并发操作，到底哪个客户端先做，哪个客户端后做，这就是更新顺序。如果不是分布式，那么可以利用加锁的方法，谁先申请到锁，谁就先操作。但是在分布式条件下，存在多个副本，如果依赖申请锁+副本同步更新完毕再释放锁，那么需要有分配锁的这么一个节点（如果是多个锁分配节点，那么又出现分布式锁管理的需求，把锁给哪一个客户端又成为一个难点），这个节点又成为单点，岂不是可靠性不行了，失去了分布式多副本的意义，同时性能也很差，另外，还会出现死锁等情况。
所以，说来说去，只有解决分布式条件下的一致性问题，似乎才能解决本质问题。
如上面的例子，Paxos解决这一问题利用的是选举，少数服从多数的思想，只要2N+1个节点中，有N个以上同意了某个决定，则认为系统达到了一致，并且按照Paxos原则，最终理论上也达到了一致，不会再改变。这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去，容错性相当好。因此，以前看有的博客说在部署ZooKeeper这种服务的时候，需要奇数台机器，这种说法当然有一定来源背景，比如如果是5台，那么任意客户端与任意其中3台达成一致就相当于投票结束，不过6台有何不可？只是此时需要与4台以上达成一致。
Paxos中的Acceptor就相当于上面的队长，Proposer就相当于上面的驴友，epoch编号就相当于例子中申请短信的发送时间。关于Paxos的正式描述已经很多了，这里就不复述了，关于Paxos正确性的证明，因为比较复杂，以后有时间再分析。另外，Paxos最消耗时间的地方就在于需要半数以上同意沟通了才能进入第二步，试想一下，一开始，所有驴友就给队长狂发短信，每个队长收到的最新短信的是不同驴友，这样，就难以达到半数以上都同意与某个驴友沟通的状态，为了减小这个时间，Paxos还有Fast Paxos的改进等等，有空再分析。
倒是有一些问题可以思考一下：在Paxos之前，或者说除了Chubby，ZooKeeper这些系统，其它分布式系统同样面临这样的一致性问题，比如
、分布式数据库、
Amazon的Dynamo
等等，解决思路又不同，有空再进行对比分析。
最后谈谈一致性这个名词。
关于Paxos说的一致性，个人理解是指冗余副本（或状态等，但都是因为存在冗余）的一致性。这与
关系型数据库中ACID的一致性说的不是一个东西。
在关系数据库里，可以连副本都没有，何谈副本的一致性？按照经典定义，
ACID中的C指的是在一个事务中，事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。那么，什么又是一致性状态呢，这跟业务约束有关系，比如经典的转账事务，事务处理完毕后，不能出现一个账户钱被扣了，另一个
钱没有增加的情况，如果两者加起来的钱还是等于转账前的钱，那么就是一致性状态。
从很多博文来看，对这两种一致性往往混淆起来。另外，CAP原则里面所说的一致性，个人认为是指副本一致性，与Paxos里面的一致性接近。都是处理“因为冗余数据的存在而需要保证多个副本保持一致”的问题，NoSQL放弃的强一致性也是指副本一致性，最终一致性也是指副本达到完全相同存在一定延时。
当然，如果数据库本身是分布式的，且存在冗余副本，则除了解决事务在业务逻辑上的一致性问题外，同时需要解决副本一致性问题，此时可以利用Paxos协议。
但解决了副本一致性问题，还不能完全解决业务逻辑一致性；
如果是分布式数据库，但并不存在副本的情况，
事务的一致性需要根据业务约束进行设计。
另外，谈到Paxos时，还会涉及到拜占庭将军问题，它指的是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。Paxos本身就是利用消息传递方式解决一致性问题的，所以它的假定是信道必须可靠，这里的可靠，主要指消息不会被篡改。消息丢失是允许的。
关于一致性、事务的ACID，CAP，NoSQL等等问题，以后再详细分析。本文的描述也许可能存在一些举例不太恰当的地方，如果错误，欢迎批评指正。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致26419人阅读
ZooKeeper（10）
分布式应用（3）
1&Paxos算法
1.1&基本定义
算法中的参与者主要分为三个角色，同时每个参与者又可兼领多个角色
proposer&;
算法保重一致性的基本语义
⑴()提出后才能被批准(&()&);
⑵算法的执行实例中，只批准();
有上面的三个语义可演化为四个约束
⑴:必须接受第一次收到的提案;
:的提案被批准，那么之后任何再次接受的提案必须具有;
⑶:的提案被批准，那么以后任何&提出的提案必须具有;
:的提案具有，那么存在一个多数派，要么他们中所有人都没有接受编号小于的任何提案，要么他们已经接受的所有编号小于的提案中编号最大的那个提案具有;
1.2&基本算法(basic&paxos)
算法)主要分为两个阶段
(1).&希望提出方案，首先发出请求至大多数请求内容为序列号;
(2).&接收到请求时，检查自身上次回复过的请求
a).&，则忽略此请求，直接结束本次批准过程;
b).&请求，，并且回复，；如果之前没有进行过批准，则简单回复;
(1a).&回复，回复可分为以下几种:
a).&，则发出请求，请求内容为议案，;
b).&，，，则找到所有回复中超过半数的，，则请求，请求内容为议案，;
c).&尝试增加序列号为，转继续执行;
&&&&&&&&&(1b).&回复，回复可分为以下几种:
a).&被接受;
b).&未被接受，增加序列号为，转继续执行;
(2).&的承诺的前提下，收到请求后即接受并回复
1.3&算法优化(fast&paxos)
Paxos算法在出现竞争的情况下，其收敛速度很慢，甚至可能出现活锁的情况，例如当有三个及三个以上的在发送请求后，很难有一个收到半数以上的回复而不断地执行第一阶段的协议。因此，为了避免竞争，加快收敛的速度，在算法中引入了一个这个角色，在正常情况下同时应该最多只能有一个参与者扮演角色，而其它的参与者则扮演的角色，同时所有的人又都扮演的角色。
在这种优化算法中，只有可以提出议案，从而避免了竞争使得算法能够快速地收敛而趋于一致，此时的算法在本质上就退变为两阶段提交协议。但在异常情况下，系统可能会出现多的情况，但这并不会破坏算法对一致性的保证，此时多个都可以提出自己的提案，优化的算法就退化成了原始的算法。
一个的工作流程主要有分为三个阶段：
(1).学习阶段&向其它的参与者学习自己不知道的数据决议
(2).同步阶段&让绝大多数参与者保持数据决议的一致性
(3).服务阶段&为客户端服务，提议案
1.3.1&学习阶段
当一个参与者成为了之后，它应该需要知道绝大多数的实例，因此就会马上启动一个主动学习的过程。假设当前的新早就知道了、和的实例，那么它会执行和大于的实例的第一阶段。如果只检测到和的实例有确定的值，那它最后就会知道以及的实例。
1.3.2&同步阶段
此时的已经知道了、的实例，那么它就会重新执行的实例，以保证绝大多数参与者在的实例上是保持一致的。至于的实例，它并不马上执行的实例，而是等到在服务阶段填充了、的实例之后再执行。这里之所以要填充间隔，是为了避免以后的总是要学习这些间隔中的实例，而这些实例又没有对应的确定值。
1.3.4&服务阶段
Leader将用户的请求转化为对应的实例，当然，它可以并发的执行多个实例，当这个出现异常之后，就很有可能造成实例出现间断。
1.3.5&问题
(1).Leader的选举原则
(2).Acceptor如何感知当前的失败，客户如何知道当前的
(3).当出现多之后，如何掉多余的
(4).如何动态的扩展
2.&Zookeeper
2.1&整体架构
在集群中，主要分为三者角色，而每一个节点同时只能扮演一种角色，这三种角色分别是：
(1).&Leader&接受所有的提案请求并统一协调发起提案的投票，负责与所有的进行内部的数据交换同步
(2).&Follower&直接为客户端服务并参与提案的投票，同时与进行数据交换同步
(3).&Observer&直接为客户端服务但并不参与提案的投票，同时也与进行数据交换同步
2.2&QuorumPeer的基本设计
Zookeeper对于每个节点的设计相当的灵活，主要包括四个组件：客户端请求接收器、数据引擎、选举器、核心功能组件。其中：
(1).&ServerCnxnFactory负责维护与客户端的连接接收客户端的请求并发送相应的响应
(2).&ZKDatabase负责存储加载查找数据基于目录树结构的操作日志客户端
(3).&Election负责选举集群的一个节点
(4).&Leader/Follower/Observer一个节点应该完成的核心职责
2.3&QuorumPeer工作流程
2.3.1&Leader职责
Follower确认等待所有的连接注册，若在规定的时间内收到合法的注册数量，则确认成功；否则，确认失败。
2.3.2&Follower职责
2.4&选举算法
4.&选举算法
发起选举的线程担任，他主要的功能对投票结果进行统计，并选出推荐的。选举线程首先向所有发起一次询问()(是否一致)，并存储到当前询问对象列表中，最后获取对方提议&的
，并将这些&信息存储到当次选举的投票记录表中，当向所有
S最大的设置为当前要推荐的(，根据投票结果而定，但是每一个在第一次投票时都会投自己)获得的票数，设置当前推荐的为获胜的Server。根据获胜的相关信息设置自己的状态。每一个都重复以上流程直到选举出。
初始化选票第一张选票每个节点一开始都投给自己
收集选票使用协议尽量收集所有节点当前的选票单线程同步方式，超时设置
统计选票每个节点的票数
&&&&&&&&&2).为自己产生一张新选票、均最大
选举成功某一个节点的票数超过半数
更新选票在本轮选举失败的情况下，当前节点会从收集的选票中选取合适的选票、均最大作为自己下一轮选举的投票
异常问题的处理
1).&选举过程中，的加入
当一个启动时它都会发起一次选举，此时由选举线程发起相关流程，那么每个&都会获得当前最大的哪个是谁，如果当次最大的没有获得个票数，那么下一次投票时，他将向最大的投票，重复以上流程，最后一定能选举出一个。
2).&选举过程中，的退出
只要保证个存活就没有任何问题，如果少于个存活就没办法选出。
3).&选举过程中，死亡
当选举出以后，此时每个应该是什么状态都已经确定，此时由于已经死亡我们就不管它，其它的按正常的流程继续下去，当完成这个流程以后，所有的都会向发送消息，如果无法通，就改变自己的状为，发起新的一轮选举。
4).&选举完成以后，死亡
处理过程同上。
5).&双主问题
Leader的选举是保证只产生一个公认的的，而且重新选举与旧恢复并退出基本上是同时发生的，当无法同是就认为已经出问题开始重新选举，收到的没有达到半数以上则要退出重新选举。
2.4.2&FastLeaderElection选举算法
FastLeaderElection是标准的的实现，它首先向所有提议自己要成为，当其它收到提议以后，解决&和&的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息。
FastLeaderElection算法通过异步的通信方式来收集其它节点的选票，同时在分析选票时又根据投票者的当前状态来作不同的处理，以加快的选举进程。
每个都一个接收线程池和一个发送线程池在没有发起选举时，这两个线程池处于阻塞状态，直到有消息到来时才解除阻塞并处理消息，同时每个都有一个选举线程可以发起选举的线程担任。
1).&主动发起选举端选举线程的处理
首先自己的&加，然后生成消息，并将消息放入发送队列中，&系统中配置有几个就生成几条消息，保证每个都能收到此消息，如果当前的状态是就一直循环检查接收队列是否有消息，如果有消息，根据消息中对方的状态进行相应的处理。
2).主动发送消息端发送线程池的处理
将要发送的消息由消息转换成消息，然后发送对方，并等待对方的回复。
3).&被动接收消息端接收线程池的处理
将收到的消息转换成消息放入接收队列中，如果对方的小于则向其发送一个消息让其更新；如果对方处于状态，自己则处于或状态，则也发送一个消息当前已产生，让其尽快收敛。
2.4.3&AuthFastLeaderElection选举算法
AuthFastLeaderElection算法同算法基本一致，只是在消息中加入了认证信息，该算法在最新的中也建议弃用。
getChildren
createSession
closeSession
2.6&Zookeeper中的请求处理流程
2.6.1&Follower节点处理用户的读写请求
2.6.2&Leader节点处理写请求
&&& 值得注意的是， Follower/Leader上的读操作时并行的，读写操作是串行的，当CommitRequestProcessor处理一个写请求时，会阻塞之后所有的读写请求。
通信不可靠消息延迟、消息重复传递、消息丢失
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：378806次
积分：4893
积分：4893
排名：第3850名
原创：109篇
转载：44篇
评论：171条
(1)(2)(2)(6)(1)(1)(2)(1)(4)(8)(13)(10)(8)(26)(17)(16)(10)(4)(6)(7)(2)(5)(1)3738人阅读
学习了1个多月，现在回头看，觉得要理解paxos算法，需要阅读下面三篇论文：
The part-time parliament [] []
Paxos Made Simple [] []
Paxos Made Code []
前两篇更多的是理论，第三篇介绍了paxos的实现。
阅读第三篇还是很有必要的，在看第三篇之前，我一直不理解一个paxos的instance到底指的是什么。
ballot、提案、提议：一轮投票
决议、decree：状态proposed候选的值，同时发起的请求的值，可能取的值；状态passed确定的唯一值，一致的值，写到律簿的值
投票、vote：同意该提案的值
承诺、promise：出现在承诺不再接受某些提案
律簿、法典、ledger：记录通过的决议，包括一个编号，以及对应的内容。
实例编号、instance No、decree number：对应律簿中的编号
提案编号、ballot No：每个提案的编号不能重复
法定人数集、quorum：牧师这群人中的一部分，一般是多数派就行。
Leader、president：从proposer中选出来的，只让它发起提案
Basic Paxos算法能从众多的请求中唯一地确定一个值，Multi Paxos则是多次运行Paxos实例，从而得到一个唯一的序列。
Paxos算法角色
Proposer&发出提议 (提案：一个提案proposal，提案中含有决议(value))
Acceptor&参与投票
Learner&学习通过的决议
Acceptor被动参与投票。Paxos算法规定了Proposer和Acceptor的原则。
一个一致性算法需要保证：一次选举中只批准一个决议(value)，只有被提出(proposed)的决议才能被批准，只有已经被批准的决议才能被学习(即可以执行或保存这个决定的内容)。
1.决议（value）只有在被 proposers 提出后才能批准（未经批准的决议称为“提案（proposal）”）；
2.在一次 Paxos 算法的执行实例中，只批准一个 Value；
3.learners 只能获得被批准（chosen）的Value。
safety condition：If in round M a proposal V is chosen, then every higher-numbered proposal must have value V.
数学结论(β:表决集合)
B1(β)：表决编号唯一
B2(β)：β中任意两个表决的法定人数集(quorum)至少有一个牧师是相同的。
B3(β)：对β中任一表决B，如果B的法定人数集中有牧师在之前的表决投过赞成票。那么，表决B的法令的内容应与那些投票的表决中最近的那轮的法令一致。
B3(β)解释：（论文中Fig.1.）红色为投票(phase 2b)
decree这一列是根据参与的Acceptor的投票历史记录确定的。所以2,5随便选，14只能选α
Q1:为什么提案编号不是连续的?
A1:因为可能有多个Proposer提出议案，它们提出的议案的编号是没有交集的。每个牧师都有一个无限的表决编号集合单独供自己使用。
提案参与的牧师不一样，这是因为法定人数集是提前选出来的。 另外一种实现是向所有人发送，然后收到多数派的回复提案算成功。
满足B1(β), B2(β), B3(β)
保证一致性：同一个法令编号，一旦达成结果。今后都将会是同一个结果，因为B3，无法篡改。只达成一条一致的法令
不保证进展性
初级协议 Preliminary protocol&
使B1成立：机器i发起的表决编号 可以使用：N+i,2N+i
使B2成立： 选择法定人数集
使B3成立：p在发起表决前，需要找出Maxvote(b,Q,β)dec，也就是对于Q中的每一个q找出Maxvote(b,p,β)(编号最大的投票)。
一个牧师p在发起表决之前，需要找出MaxVote(b, Q,β)dec,为了找出MaxVote(b,
Q,β)dec，p需要对Q中的每一个q找出MaxVote(b,
q, β)dec。
------这就是为什么在request的回复中需要夹带编号小于b的表决中编号最大的表决的投票。
LibPaxos中把必须选择MaxVote(b, q, β)dec对应的值，称为instance stolen，或者是说值是Reserved.
初级协议- 步骤
(1)牧师p选择一个新的表决编号b，并向某些牧师Q发送NextBallot(b)。
(2)q回复Lastvote(b,v)，v=Maxvote(b,q,β)
因为β会改变，要保证p选择Maxvote(b,Q,β)之后Maxvote(b,Q,β)不变，q承诺不再向vbal ~ b之间的表决投票。
如果Maxvote(b,Q,β)变了，这个Lastvote也就失效了，从而在(4)中就不再对这个balllot b投票。
(3)p收到Q中所有人/多数派牧师的Lastvote(b,v)后，选择满足B3(β)的法令d，并向Q中每一个牧师发送BeginBallot(b,d)
(4)Q投票发送voted(b,q)。如果在其它表决中发送了Lastvote(b’,v’)，而投这一票会违背这个消息隐含的承诺，则不投。
(5)P收到Q中所有人/多数派牧师q的vote(b,q)，则在律簿中写下法令d，并向每一个牧师发送success(d)
(6)Q收到success(d)之后，将法令d记录在律簿上
(1)、(2)是为了找出Maxvote(b,Q,β)
(3)、(4)选值、投票
(5)、(6)通过则学习
Q中所有人/多数派牧师&是两种不同的实现方式，原文中的方法是先选择出一个quorum（一群牧师），只发送消息给这个quorum，必须收到quorum中所有人回复。另一种方法是向所有人发送，必须收到多数派的回复。
需要记住：
1) 每个发起的提议的编号
2)每个对提议的投票
3)每个LastVote
也可以看出牧师是身兼proposer和acceptor的角色的，既参与投票，也能发起提案。
基本协议 Basic Protocol
只需记住：
1) LastTried[p]&最后一次发起的提议的编号&
2) preVote[p] & &投票最大编号，第4步投票的编号。
3) nextBal[p] & &回复prepare的最大编号 ，也是承诺的编号，第2步的编号。
lastTried[p]：p发起的最后一个表决编号，没有则为负无穷。
prevVote[p]：p投票的所有表决中，编号最大的表决对应的p的投票。
nextBal[p]：p发出的所有LastVote(b,v)消息，表决编号b的最大值。
(1) &p选择比LastTried[p]大的编号b，设置LastTried[p]为b，然后发送NextBallot(b)
(2) &q收到大于nextBal[q]的NextBallot(b)消息后，牧师将nextBal[q]设置为b，然后发送一个Lastvote(b,v)消息给p，其中v等于prevote[q]
更强的承诺：不再对任何编号小于b的表决投票
(3) &P发送BeginBallot(b,d)消息给Q中的每一个牧师&
(4) &投票，设置prevote[q]为这一票，然后发送voted(b,q)
(5) &P收到Q中每一个q的vote(b,q)之后，记录d到律簿上，发送success(d)给每个牧师
(6) &收到success(d)，写法令
Basic Paxos
Phase 1a:Proposer向Acceptor的多数派发送Prepare(Ballot id)
Phase 1b:Acceptor返回Promise(Ballot id, Accepted Id, Accepted Value)或者NACK
Phase 2a:Proposer收到多数派的Promise之后，根据B3选择值V, 发送Accept(Ballot id, V)
Phase 2b:Acceptor发送Accepted(Ballot id)或UnAccepted，vote&
收到多数派的Voted，就可以将决议写到律簿中了。
Multi-paxos
收到Client的多个请求
每次运行一次Paxos，唯一选出一个一致的值(&一个实例instance)
Proposer发现当前律簿上已经有了i-1个
Proposer开始第i个Paxos实例
发送prepare(instance id, ballot id)
回复promise(instance id, ballot id, acc id, acc val)
发送accepted(instance id, ballot id, V)
回复accept/unaccept
收到多数派的accept，实例i的值确定为V。
同时进行多个实例，可能出现空洞gap。这时proposer必须填充一个NOP操作，没有意义的值。因为打乱了顺序，填充其它有意义的值，可能是没有意义的。
Paxos Made Simple
P1: An acceptor must accept the first proposal that it receives.
A proposal is chosen when it has been accepted
by a majority of acceptors. accepted不是accept，是指promise，也就是phase 1b
A value is chosen when a single proposal with that value has been chosen.
提案被接收：Acceptor只是保证不承诺比该propose的ID小的，如果后来出现ID更大的，则会在后面的阶段中拒绝该propose。
决议被批准：提案被Acceptors集合中的任意一个Majority的所有成员接受。
Unique value( by induction on the proposal number )
P2: If a proposal with value v is chosen,then every higher-numbered proposal
that is chosen&has value v.
-strengthen-&
P2a: If a proposal with value v is chosen,then every higher-numbered proposal
accepted by any acceptor has value v.
-strengthen-&
P2b: If a proposal with value v is chosen,then every higher-numbered proposal
issued by any proposer has value v.
Suppose p wants to issue a proposal numbered n.
If p can be certain that no proposal numbered n’&n has been chosen then p can propose any value!
If not, p should propose the value of the highest numbered proposal among all accepted proposal among all accepted proposals numbered less than n.
P2c: For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either:
No acceptor in S has accepted any proposal numbered less than n, or
V is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.
acceptor需要记住什么?
An acceptor needs only remember the highest numbered proposal it has
accepted and the number of the highest-numbered prepare request to which it has responded.
Paxos保证了每个Learner的律簿的一致性，各个learner遵照次序学习。&
学习的顺序是一致的。按实例编号依次学习，不能跳过，所有Learner看到的实例的值是一致的。
学习的进度是异步的。可能实例还没写到Learner的律簿上，所以学习的进度不一样。
An instance&is the algorithm for choosing one value.
A round&refers to a proposer’s single attempt of a Phase 1+Phase 2. A node can have multiple rounds in a instance of Paxos. A round id is globally unique per instance across all nodes. This is sometimes called&proposal
Round ids(aka proposal numbers) should be increasing and must be unique per instance across all nodes.
One scheme: roundId = i*M + index[node]where I is the ith round this node is starting(that is I is unique per node per paxos instance, and is monotonically increasing).
Instance reserved:Promise中有value
Instance close:被多数派accepted
Acceptor有状态&idd, B, V, VB&，它知道自己已经对instance做出/没做出决定.
Q:if there is only one “distinguished”proposer who is able to issue proposal, then what is the difference of paxos algorithm from 2-phase commit algorithm?
A:The Distinguished Proposer is an optimization and is not a requirement for the algorithm. The Distinguished Proposer reduces the contention of two proposer sleap-frogging prepare/accept messages, which is important if you
want the instance to finish. In this model, a node forwards the request to the Distinguished Proposer instead of proposing for itself.If it thinks the Distinguished Proposer is dead then it just proposes for itself.(it does not
have to be/it can never be 100% confident the Distinguished Proposer is dead.)
3)&Paxos is expensive enough that many systems using it use hints as well, or use it only for leader election, or something.However, it does provide guaranteed consistency in the presence of failures.
4)&保证只有一个Leader提出proposal，可以优化，减少消息的条数
The parliamentary protocol[aka Mult-paxos] used a separate instance of the&complete Synod protocol [aka Paxos] for each decree number.However, a single president [aka proposer/leader] was selected
for all these instances, and he performed the first two steps of the protocol just once.
《Paxos Made Live》
A Mult-Paxos algorithm may be designed to pick a coordinator for long periods of time, trying not to let the coordinator change.
With this optimization, the Paxos algorithm only requires a single write to disk per Paxos instance on each replica, executed in parallel with each other.
多个Proposer发起提案可能造成race condition，甚至活锁，从而无法满足Liveness。所以一般都会从中选择出一个Leader，由Leader提出Proposal。
You have a way of determining which node is the Leader per Paxos instance(required by Multi-Paxos). The Leader is able to change from one Paxos instance to the next.
Q: As for protocol violation, I think it's already a violation of the Basic protocol to send Accept!(N+1,V2) since this wouldn't have happened with Basic Paxos (you'd have sent Prepare!(N+1) first,would have received V1 from acceptors in return and would
have been forced tosend Accept! with V1 afterwards).
A: From the point of view of an Acceptor, it can receive an Accept without having ever seen the corresponding Prepare. Yes it is inviolation of Basic Paxos, but not in violation of Multi-Paxos.
Prepare messages have form&(instance,
proposal_num)
Propose messages have form&(instance, proposal_num, proposal_val)
In Phase 1a, there is no need to send the value to agree on.
大家可能会比较疑惑，难道自始至终只能选出一个value？其实这里的选出，是指一次选举，而不是整个选举周期，可以多次运行paxos，每次都只选出一个value.
8)&需要向所有acceptor发送prepare消息吗?
A coordinator can send a phase 1a or 2amessage only to a majority of acceptors that it believes are nonfaulty. It canlater send the message to other acceptors if one of the original acceptors doesnot respond. &Fast paxos&
9)&关于提请求：&Paxos Made Code&
To submit values, clients connects to the current leader. In case the coordinator crashes, they connect to the next elected leader.
Alternatively, clients can send their values by multicasting them on the
“leader network”.A coordinator crash is completely transparent to them in this case.
The leader is busy broadcasting client values as fast as possible. When received, those values are temporarily stored in a&pending list.
10)&Multi-Paxos
一个paxos instance怎样才能算是closed?
If a majority of acceptors accepted the value, it is safe to assume that the
instance is closed with v permanently associated to it. Nothing can happen in the system that will changes this fact, therefore learners can deliver the value to their clients.
Learners’ state consists of a&window&of instances.
Lower bound of this window is the lowest instance&not yet closed;
Higher bound must be chosen&
11)&学习：
在一个总统可以提议任何新的法令之前，他必须向一个多数（过半的）集合中的每个议员学习他已经投票过的法令。任何已经通过的法令一定被至少一个多数集合中的议员投过票。
Learner学习可以通过Acceptor发送Accept广播，收到一个majority的Accepted通知之后开始学习。Acceptor也可以将Accept消息只发送给Leader，然后Leader收到多数派Accept消息后，再发送Commit给Learner通知该实例的值已确定，可以写到律簿中，也就是学习。
– Each acceptor, whenever it accepts a proposal, informs all&the learners.
– Acceptors informs a distinguished learner (usually the&proposer) and let the distinguished learner broadcast the&result.
12)&宕机：
Acceptor的多数派宕机后，如果proposer也宕机，则新的proposer请求因为无法得到多数派的回应而需要递增投票的编号，直到Acceptor有多数派恢复在线。同时，新的proposer无法改变该instance的值，因为Acceptor中有记录。
多数机器宕机也不会造成不一致，只是会推迟结果的达成。Live if a quorum of processes are OK (up and connected with each other)
13)&消息格式及状态：《Paxos Made Code》
Acceptorstate:
the acceptor keeps a state record,consisting of & iid, B, V, V B &, where B is an integer, the highestballot number that was accepted or promised for this instance, V is a clientvalue and V B is the ballot number corresponding to the accepted value. Thethree
fields are initially empty.
Promise:It sets B = b and answers with a promise message, consisting of& i, b, V, V B &, where V and V B are null if no value was accepted yet.
Accepted: It sets B = b, V = v,V B = b and answers with a learn message,consisting of & i, b, v &.
14)&如果形成多数派怎么办. 《Paxos Made Code》
如果没有通过promise，则增加ballot number，重发prepare。
如果没有通过accept，则增加ballot number，重发prepare。从头开始
直到instance 被close。
15)&Persistency
在发送消息之前，需要写到磁盘上，否则可能会导致对promise食言。即使写到磁盘后，没有发出去或者消息丢失，也只是影响进展。
16)&如果都没有人学习到? 但是确实有多数派accepted了，则下一轮至少有一个会在多数派中，缺少这些肯定构不成多数派。应该是还是会取这个值，否则能推出矛盾，意味着有follower的accepted Id更大，那原本就不是取这个值了。
=======================
17)&libpaxos中在phase 2a之前为什么可能有取值?
在p1b或这p2a发生超时的情况下，需要从头开始。但是如果p2a超时，实际上这个实例可能已经有取值了，也就是和某个request绑定。为了不丢失这个请求，一种方法是将该请求放回到缓冲队列。但是这种做法可能出现该请求在当前的实例为reserved value，也就是多数派的acceptor已经通过该值。而下一个或者后续的实例又从缓冲队列中取到该值，从而出现请求在多个实例中重复出现的情况。
所以，不应该重新放回到缓冲队列，而应该继续和实例绑定。只有发现reserved value是另外一个值的情况下才将该请求放回缓冲队列。
参考资料：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：116359次
积分：1609
积分：1609
排名：第17603名
原创：50篇
(1)(1)(2)(1)(4)(4)(4)(5)(5)(3)(2)(1)(1)(1)(7)(1)(2)(3)(3)(1)