比较raft ，basic paxos以及multi-paxos

by 夏泽民 Jan 4, 2018

深入浅出的来讲清楚这些协议的两个问题：

这些协议是用来干什么的
这些协议有什么区别，为何有这些区别

首先来说说Paxos
作为basic paxos和multi-paxos，绕不过去的概念就是先得说说paxos，先来理理基本概念：

paxos并不指代一个协议，而是一类协议的统称，比较常见的paxos类协议有：basic paxos ，以及 multi-paxos
paxos的目的是为了多个参与者达成一致观点
paxos基于一个原则，参与者不能阳奉阴违，一致的观点不会在传递过程中反转
paxos协议有一堆角色和限制，因为经统计87%的读者都会在阅读paxos的限制时就点X，这篇文章会直接跳过paxos的其他内容，因为这些内容并不有助于理解multi paxos和basic paxos

basic paxos vs multi-paxos
先说结论，basic paxos 的协议更复杂，且相对效率较低。所以现在所有的和paxos有关的协议，一定是基于multi-paxos来实现的。

2.1 从basic paxos的两阶段协议开始：
basic paxos的角色中，谨记一个原则：每个acceptor维护了自己知道的最大的协议号 vx，且每个acceptor不会同意任意一项小于等于vx的协议的prepare请求。

basic paxos是由client发起的同步过程，在两阶段返回前，client不能得到成功的返回。

第一阶段a（发送prepare），proposer向acceptor提出一个协议，这里的协议可以理解为client发送过来期望多节点一起保存的一致性内容，举例：一句日志，某个配置等
第一阶段b（计算协议vn），根据半数以上acceptor的返回，选择 max{va,vb,vc} = vn，这里的vx理解为这个acceptor已知的最大协议号，acceptor一旦返回了vx后，则表明：
acceptor在接下来的prepare请求中，会返回的vx自增1
acceptor不会accept任何小于vx的协议请求，只会accept大于vx的协议请求
第二阶段a（发送决议好的vn），把vn发送给acceptor
第二阶段b，在半数acceptor返回了成功后，再返回client成功通过协议
引用wiki上的流程图：

Client Proposer Acceptor Learner
| | | | | | |
X——–>| | | | | | Request
| X———>|->|->| | | Prepare(1)
| |<———X–X–X | | Promise(1,{Va,Vb,Vc})
| X———>|->|->| | | Accept!(1,Vn)
| |<———X–X–X——>|->| Accepted(1,Vn)
|<———————————X–X Response
| | | | | | |
2.2 有助于理解basic paxos 协议的小细节
proposer是可以有多个，所以他叫做proposer，而不叫leader
proposer并不强制要发送propose到全部acceptor，也可以发送70%的acceptor，只要通过的有半数以上，就认为协议是成功的
容易看出，第二阶段的时候client仍需要等着，只有在第二阶段大半acceptor返回accepted后，client才能得到成功的信息
有一些错误场景中，proposer会互相锁住对方的递交，详细可以看wiki，这里不多阐述：Paxos (computer science)
2.3 Multi-paxos 如何让自己看起来像一阶段
multi-paxos 在basic paxos的二阶段上引入了一个机制，让自己看起来像一阶段一样，是如何做到的？让我们回顾basic paxos协议的关键内容：

多个proposer
max{va,vb,vc} = vn
这两个关键点导致的后果就是，在一阶段得到vn后，proposer并不可以肯定，accept(vn) 命令会在多数acceptor中成功执行，一个极端的例子如下：

Client Proposer Acceptor Learner
| | | | | | |
X—–>| | | | | | Request
| X————>|->|->| | | Prepare(1)
| |<————X–X–X | | Promise(1,{null,null,null})
| ! | | | | | !! LEADER FAILS
| | | | | | | !! NEW LEADER (knows last number was 1)
| X———>|->|->| | | Prepare(2)
| |<———X–X–X | | Promise(2,{null,null,null})
| | | | | | | | !! OLD LEADER recovers
| | | | | | | | !! OLD LEADER tries 2, denied
| X————>|->|->| | | Prepare(2)
| |<————X–X–X | | Nack(2)
| | | | | | | | !! OLD LEADER tries 3
| X————>|->|->| | | Prepare(3)
| |<————X–X–X | | Promise(3,{null,null,null})
| | | | | | | | !! NEW LEADER proposes, denied
| | X———>|->|->| | | Accept!(2,Va)
| | |<———X–X–X | | Nack(3)
| | | | | | | | !! NEW LEADER tries 4
| | X———>|->|->| | | Prepare(4)
| | |<———X–X–X | | Promise(4,{null,null,null})
| | | | | | | | !! OLD LEADER proposes, denied
| X————>|->|->| | | Accept!(3,Vb)
| |<————X–X–X | | Nack(4)
| | | | | | | | … and so on …
因为其他proposer的存在，大家交替propose的结果就是所有的prepare计算得到的vn，全部中途作废，accept的动作一个都没正常执行。
显然，这样的决议过程是正确且低效的。

如何让basic paxos得以进行一阶段的递交，最最重点的地方聚焦在了一个点：假如只允许有一个proposer

multi-paxos将集群状态分成了两种：

选主状态，由集群中的任意节点拉票发起选主，拉票中带上自己的vx，通过收集集群中半数以上的vx，来更新自己的vx值，得到目前集群通过的最大vx = vn
强leader状态，leader对vn的演变了如指掌，每次把vn的值直接在一阶段中发送给acceptor，和basic paxos的区别：basic paxos一阶段的时候，proposer对vn的值一无所知，要依赖一阶段的结果来算vn
一些有趣的细节：为何选主的时候，半数的vx就可以确定集群最大vn？

因为在vn生成过程中，必须达成通知到半数节点的目的，vn才能成功生成，所以一定有半数以上的节点知道vn
选主的时候的限制恰好对应vn生成时的限制，这是一个环环相扣的证明
multi-paxos强leader状态的流程图：

Client Leader Acceptor Learner
| | | | | | | — Following Requests —
X——–>| | | | | | Request
| X———>|->|->| | | Accept!(N,I+1,W)(prepare）
| |<———X–X–X——>|->| Accepted(N,I+1,W)(prepared)
|<———————————X–X Response
| | | | | | |
2.4 multi-paxos 一些有趣的小细节：
流程图中没有了basic paxos的两阶段，变成了一个一阶段的递交协议：
一阶段a：发起者（leader）直接告诉Acceptor，准备递交协议号为I+1的协议
一阶段b：收到了大部分acceptor的回复后（图中是全部），acceptor就直接回复client协议成功写入
wiki中写的Accept方法，我更愿意把它当做prepare，因为如果没有半数返回，该协议在超时后会返回失败，这种情况下，I+1这个协议号并没有通过，在下个请求是仍是使用I+1这个协议号
看过上一篇：raft 经典场景分析 - 知乎专栏的同学已经发现了，multi-paxos在选定了leder后的行为和raft一模一样，那么multi-paxos和raft有什么区别呢，且看下一节分解。

raft vs multi-paxos
看到这里的，说明对分布式一致性的学习绝对是真爱。

在我的上一篇文章：raft 经典场景分析 - 知乎专栏中，已经详细讨论了raft的选主和日志复制，而在上一节中，我们惊喜的发现multi-paxos和raft，在选定了leader状态下的行为模式一模一样，在这一节中，主要将比较它们在选主和日志复制上的行为。

注意：raft的日志复制，等同我们在上文讨论的协议，为叙述方便，现在这一节，我们把multi-paxos的一阶段协议递交成为日志复制。

结论也同样隐藏在我上一篇文章中：

raft仅允许日志最多的节点当选为leader，而multi-paxos则相反，任意节点都可以当选leader
raft不允许日志的空洞，这也是为了比较方便和拉平两个节点的日志方便，而multi-paxos则允许日志出现空洞
这两个不同的设定反应到日志中的区别可以看如下图：

如图，multi-paxos日志中间允许出现空洞，而multi-paxos的leader节点也会异步的查询其他节点来填补自身日志空洞

如图：raft的典型日志，可以看出这个raft集群中，8节点的日志仍未完成且返回，只有1，3，5这三个节点有机会被重新选为leader
深化一下刚才的理解，那就是：multi-paxos的leader只是知道最大的log index是多少，但是空洞部分，可以异步填充，而raft的leader，不但知道最大的log index是多少，也必须拥有从0到log index直接的之间日志，在被选择为leader后，raft的leader可以单向的向其他节点同步落后的日志。

多谢 @LoopJump 指出，raft这个协议方便的地方在于：”raft不允许日志的空洞，这也是为了比较方便和拉平两个节点的日志方便 “ Raft连续确认更大的一个优势是新主上任过程简单了。Multi Paxos在上任过程很复杂，不只是补全过程。我在raft经典场景这篇文章中也指出了这一点：

在一些一致性算法中，例如：Viewstamped Replication，
即使一开始没有包含全部已提交的条目也可以被选为领导人。
这些算法都有一些另外的机制来保证找到丢失的条目并将它们传输给新的领导人，
这个过程要么在选举过程中完成，要么在选举之后立即开始。
不幸的是，这种方式大大增加了复杂性。

Raft 使用了一种更简单的方式来保证：也就是日志落后的候选人，
无法被选中为Leader，这其实大大减小了选举和日志复制的相关性，
简化了raft的算法理解难度。

作者：张帅
链接：https://www.zhihu.com/question/57321934/answer/152640954
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

multi-paxos在basic-paxos的模型基础之上，增加了“连续递增”value的元素；换言之，basic-paxos至始至终都是说单个value达成一致的过程，而multi-paxos说的是多个value达成一致，并且这些value还有个特点：value有id标记，而且id连续递增。用数据库redo 日志的模型来描述这个模型就是：数据库不停写入多个事务，每个事务insert一条记录，每个insert都会在数据库引擎内部产生一条redo日志，这个redo日志就是一个value，redo日志会被顺序标记递增的log_id。介绍完背景，现在可以来看看正确性和可优化的地方：先说协议正确性容易被忽视的地方：0. 有些值必须持久化存储这个似乎是废话，需要持久化哪些值呢？prepare 记录，accept记录。。。1.全局唯一的proposal_idBasic-paxos要求proposal_id全局唯一（否则会有不一致风险），如何保证唯一呢， ip+本地时间戳是个可选方案；2.prepare请求应该包含哪些信息？multi-paxos的prepare请求，可以理解为basic-paxos对于一批value发送prepare请求，那这个“一批”具体如何设定呢，答案是[start_id, 无穷大)这个连续区间。Start_id指的是什么呢？就是当前proposer 中value序列连续形成多数派的最大值，举个栗子，比如本地形成多数派的是{123,5}，未形成多数派的是{4， 7}，那么此时start_id就是3。是否这一区间的每一个value都需要指定一个proposal_id呢？当然不是，共享一个相同的proposal_id，这里是multi-paxos的关键。3. acceptor 如何响应收到的一个prepare请求？如何响应prepare请求，basic-paxos已经有详细说明，不再赘述。现在只说multi-paoxs的情况下，acceptor响应的注意点。acceptor收到prepare请求后，首先当然要比较proposal_id，通过检查后，下面就是关键操作了。这个关键操作其实在basic-paxos中有清楚的说明，就是返回给存在的已经accepted的最大的proposal_id的value，如果不存在，则返回NULL。当有basic到multi后，返回结果则变为一个集合了。如果集合元素太多怎么办？此处有个优化手段是，acceptor返回一个max_log_id，此id的含义是本地存在的accept记录的最大值。proposer拿到这个值后，就知道哪些value需要找acceptor去要，哪些可以自己随便生成了。下面说实现上的优化问题：滑动窗口Multi-paxos大部分应用场景就是数据流，既然是数据流传输，其实相关优化都可以在tcp滑动窗口上找到相应点，滑动窗口中存储的就是value：1.批量并发网络发送：proposal可以同时发送多个value的accept请求；2.批量发送accept ack3.proposal超时重推（push），acceptor超时拉取（pull）已经从滑动窗口出去的value，是明确已经形成多数派不会被改写的value；滑动窗口中的，可能是空洞或者还有可能被改写的value，滑动窗口外是还未收到或者还未产生的value；commit消息另外一个重要的优化是commit 消息，当某个value确认形成多数派后，proposer可以发送commit消息给acceptor，便于acceptor将其清除出buff，并且加速此acceptor转换到proposal并且能够正常提供写入的恢复时间。为什么能加速呢？这要联系前面讲的proposal 发送prepare请求的过程，proposal在发送prepare前，要获取start_id，如果没有commit消息，start_id的确定就非常困难了。Group commit这个不是multi-paxos特有的优化，但凡是传输速度有差异的介质转换都有这个优化存在的空间，比如内存到磁盘（无论是机械还是SSD）。基本原因是，磁盘的I/O ps是有上限的，机械盘200左右，SSD 几千左右，比起内存和网络太低了。怎么办呢？把几百几千几万个value放在一个I/O buff里面刷到磁盘去，I/Ops成倍提升。成员组变更成员组指的是本来acceptor是{A BC}，我想安全的变成{D EF},怎么实现呢？raft给出了完美的实现方式，但multi-paxos在实现上不能照搬，有两点需要注意：1.成员变更的信息也是value序列中的一个，只不过内容比较特殊，描述的是成员组变更信息，简称做change_value。Change_value需要是一个barrier，就是说，change_value被accept之前，需要之前的value都accept，这个水很深，可以再开一个问题讨论；2.raft中成员变更是两阶段的，其实没必要的，想实现一阶段安全的成员变更，只需要限制变更成员的数量就可以，即{ABC}可以变为{ABD}，但不能变为{ADE}。连续变多次，就可以从{ABC}到{DEF}了。

谨记paxos协议，对空洞日志的重确认，要用新的proposal id与raft不同，multi-paxos对选主没有特别要求，谁当都可以，甚至可以外部指定，过一轮完整paxos就行使用multi-paxos的上层应用要支持乱序提交和乱序回放，否则难以发挥性能优势redolog本地是乱序存储的，因此你可能需要配合一个的日志内容索引文件，以提供方便的旁路日志导出由于乱序确认的机制，网络层面在主备之间建立多条TCP链接更能发挥优势主切换为备，仔细考虑回放起点和未决事务如何处理；同样备切换为主时，也要仔细考虑重确认起点和未决事务尽管leader有效期内只需要accept过程即可，仍然要记得备机要严格按照P2b的约束进行检查，避免不小心接受了上一任leader的消息；同样的，主机也要有机制避免接受过期的备机应答消息

作者：朱一聪
链接：https://www.zhihu.com/question/36648084/answer/82332860
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Raft协议比paxos的优点是容易理解，容易实现。它强化了leader的地位，把整个协议可以清楚的分割成两个部分，并利用日志的连续性做了一些简化：
（1）Leader在时。由Leader向Follower同步日志
（2）Leader挂掉了，选一个新Leader，Leader选举算法。但是本质上来说，它容易的地方在于流程清晰，描述更清晰，关键之处都给出了伪代码级别的描述，可以直接用于实现，而paxos最初的描述是针对非常理论的一致性问题，真正能应用于工程实现的mulit-paxos，Lamport老爷爷就提了个大概，之后也有人尝试对multi-paxos做出更为完整详细的描述，但是每个人描述的都不大一样。 Zookeeper的ZAB，Viewstamped Replication（VR），raft，multi-paxos，这些都可以被称之为Leader-based一致性协议。不同的是，multi-paxos leader是作为对经典paxos的优化而提出，通过选择一个proposer作为leader降低多个proposer引起冲突的频率，合并阶段一从而将一次决议的平均消息代价缩小到最优的两次，实际上就算有多个leader存在，算法还是安全的，只是退化为经典的paxos算法。而经典的paxos，从一个提案被提出到被接受分为两个阶段，第一个阶段去询问值，第二阶段根据询问的结果提出值。这两个阶段是无法分割的，两个阶段的每个细节都是精心设计的，相互关联，共同保障了协议的一致性。而VR,ZAB,Raft这些强调合法leader的唯一性协议，它们直接从leader的角度描述协议的流程，也从leader的角度出发论证正确性。但是实际上它们使用了和Paxos完全一样的原理来保证协议的安全性，当同时存在多个节点同时尝试成为leader或者不知一个节点认为自己时leader时，本质上它们和经典Paxos中多个proposer并存的情形没什么不同。 Paxos和raft都是一旦一个entries（raft协议叫日志，paxos叫提案，叫法而已）得到多数派的赞成，这个entries就会定下来，不丢失，值不更改，最终所有节点都会赞成它。Paxos中称为提案被决定，Raft,ZAB,VR称为日志被提交，这只是说法问题。一个日志一旦被提交(或者决定），就不会丢失，也不可能更改，这一点这4个协议都是一致的。Multi-paxos和Raft都用一个数字来标识leader的合法性，multi-paxos中叫proposer-id，Raft叫term，意义是一样的，multi-paxos proposer-id最大的Leader提出的决议才是有效的，raft协议中term最大的leader才是合法的。实际上raft协议在leader选举阶段，由于老leader可能也还存活，也会存在不只一个leader的情形，只是不存在term一样的两个leader，因为选举算法要求leader得到同一个term的多数派的同意，同时赞同的成员会承诺不接受term更小的任何消息。这样可以根据term大小来区分谁是合法的leader。Multi-paxos的区分leader的合法性策略其实是一样的，谁的proproser-id大谁合法，而proposer-id是唯一的。因此它们其实在同一个时刻，都只会存在一个合法的leader。同时raft协议的Leader选举算法，新选举出的Leader已经拥有全部的可以被提交的日志，而multi-paxos择不需要保证这一点，这也意味multi-paxos需要额外的流程从其它节点获取已经被提交的日志。因此raft协议日志可以简单的只从leader流向follower在raft协议中，而multi-paxos则需要额外的流程补全已提交的日志。需要注意的是日志可以被提交和日志已经被提交是两个概念，它们的区别就像是我前方有块石头和我得知我前方有块石头。但是实际上，Raft和multi-Paxos一旦日志可以被提交，就能会保证不丢失，multi-paxos天然保证了这一点，这也是为什么新leader对于尚未被确认已经提交的日志需要重新执行经典paxos的阶段一，来补全可能缺失的已经被提交的日志，Raft协议通过强制新Leader首先提交一个本term的no-op 日志，配合前面提到的Leader选举算法所保证的性质，确保了这一点。一条日志一旦被多数派的节点写入本地日志文件中，就可以被提交，但是leader只有得知这一点后，才会真正commit这条日志，此时日志才是已经被提交的。 Raft协议强调日志的连续性，multi-paxos则允许日志有空洞。日志的连续性蕴含了这样一条性质：如果两个不同节点上相同序号的日志，只要term相同，那么这两条日志必然相同，且这和这之前的日志必然也相同的，这使得leader想follower同步日志时，比对日志非常的快速和方便；同时Raft协议中日志的commit（提交）也是连续的，一条日志被提交，代表这条日志之前所有的日志都已被提交，一条日志可以被提交，代表之前所有的日志都可以被提交。日志的连续性使得Raft协议中，知道一个节点的日志情况非常简单，只需要获取它最后一条日志的序号和term。可以举个列子，A,B,C三台机器，C是Leader，term是3，A告诉C它们最后一个日志的序列号都是4，term都是3，那么C就知道A肯定有序列号为1,2,3,4的日志，而且和C中的序列号为1,2,3,4的日志一样，这是raft协议日志的连续性所强调的，好了那么Leader知道日志1，2，3，4已经被多数派（A,C)拥有了，可以提交了。同时，这也保证raft协议在leader选举的时候，一个多数派里必然存在一个节点拥有全部的已提交的日志，这是由于最后一条被commit的日志，至少被多数派记录，而由于日志的连续性，拥有最后一条commit的日志也就意味着拥有全部的commit日志，即至少有一个多数派拥有所有已commit的日志。并且只需要从一个多数集中选择最后出最后一条日志term最大且序号最大的节点作为leader，新leader必定是拥有全部已commit的日志(关于这一点的论证，可以通过反证法思考一下，多数集中节点A拥有最后一条已commit的日志，但是B没有，而B当选leader。根据选主的法则只能有两种可能(1)当选而A最后一条日志的term小于B；(2)A最后一条日志的term等于B，但是A的日志少于B。1,2可能嘛？）而对于multi-paxos来说，日志是有空洞的，每个日志需要单独被确认是否可以commit，也可以单独commit。因此当新leader产生后，它只好重新对每个未提交的日志进行确认，已确定它们是否可以被commit，甚至于新leader可能缺失可以被提交的日志，需要通过Paxos阶段一向其它节点学习到缺失的可以被提交的日志，当然这都可以通过向一个多数派询问完成（这个流程存在着很大的优化空间，例如可以将这个流程合并到leader选举阶段，可以将所有日志的确认和学习合并到一轮消息中，减少消息数目等）。但是无论是Raft还是multi-paxos，新leader对于那些未提交的日志，都需要重新提交，不能随意覆写，因为两者都无法判定这些未提交的日志是否已经被之前的leader提交了。所以本质上，两者是一样的。一个日志被多数派拥有，那么它就可以被提交，但是Leader需要通过某种方式得知这一点，同时为了已经被提交的日志不被新leader覆写，新leader需要拥有所有已经被提交的日志（或者说可以被提交，因为有时候并没有办法得知一条可以被提交的日志是否已经被提交，例如当只有老leader提交了该日志，并返回客户端成功，然而老leader挂了），之后才能正常工作，并且需要重新提交所有未commit的日志。两者的区别在于Leader确认提交和获取所有可以被提交日志的方式上，而方式上的区别又是由于是日志是否连续造成的，Raft协议利用日志连续性，简化了这个过程。在Raft和multi-paxos协议确保安全性的原理上，更进一步的说，所有的凡是满足集群中存活的节点数还能构成一个多数派，一致性就能满足的算法，raft协议，paxos，zab，viewstamp都是利用了同一个性质：两个多数派集合之间存在一个公共成员。对于一致性协议来说，一旦一个变量的值被确定，那么这个变量的值应该是唯一的，不再更改的。Raft,paoxos等协议，对于一个变量v来说，一个由节点n1提出的值a只有被一个多数集q1认可并记录后，才会正式令v=a，如果另一个节点n2想要修改变量v的值为b，也需要一个多数集q2的认可，而q1和q2必然至少有一个共同的成员p,节点p已经记录了v=a。因此只需要通过增加一些约束，让p能够告诉节点n2这个事实：v=a，使得n2放弃自己的提议，或者让节点p拒绝节点n2想要赋予v的值为b这个行为，都可以确保变量v的一致性不被破坏。这个思想对于这个四个协议来说都是一样的，4个协议都使用一个唯一的整数作为标识符来标明leader的合法性，paxos叫做proposer-id，ZAB叫epoch，VR叫view，raft叫term。把leader看做是想要赋予变量v某个值的节点n1,n2，上面提到的情形中，如果n2是目前的合法leader，那么n2需要知道v=a这个事实，对于raft来说就是选择n2是已经记录了v=a的节点，对于multi-paxos来说，就是重新确认下v的值。如果n1是目前的合法leader，n2是老的leader，p就会根据leader的标识符拒绝掉n2的提案，n2的提案会由于得不到一个多数派的接受而失效。最直接的从理论上阐明这个原理的是经典的paxos算法，关于这个原理更具体的阐述可以看看我在如何浅显易懂地解说 Paxos 的算法？下的回答。所以确实在一定程度上可以视raft,ZAB,VR都是paxos算法的一种改进，一种简化，一种优化，一种具象化。Lamport老人家还是叼叼叼。。。。。。。不过值得一提的是，ZAB和raft作者确实是受了paxos很多启发，VR是几乎同时独立于paxos提出的。 Raft容易实现在于它的描述是非常规范的，包括了所有的实现细节。如上面的人说的有如伪代码。而paxos的描述侧重于理论，工程实现按照谷歌chubby论文中的说话，大家从paxos出现，写着写着，处理了n多实际中的细节之后，已经变成另外一个算法了，这时候正确性已经无法得到理论的保证。所以它的实现非常难，因为一致性协议实非常精妙的。小细节上没考虑好，整个协议的一致性就崩溃了，而发现并更正细节上的错误在没有详尽的现成的参考的情况下是困难的，这需要对协议很深的理解。而且在Raft协议的博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE，两位作者手把手事无巨细的教你如何用raft协议构建一个复制状态机。我表示智商正常的大学生，都能看懂。我相信在未来一致性现在被提起来，肯定不是现在这样，大部分人觉得好难啊，实现更难。。。。应该会成为一种常用技术。

作者：郁白
链接：https://www.zhihu.com/question/36648084/answer/81413837
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

raft利用日志连续性对Paxos做了大量很好的简化，但是其中有一点有很强的误导性，就是新任leader对于旧日志的处理，他的原文描述是“Raft uses a simpler approach where
it guarantees that all the committed entries from previous terms are present on each new leader from the moment of
its election, without the need to transfer those entries to
the leader.”raft利用日志连续确认的特性，只要选举termID最大的做leader，就可以保证leader当选以后，不需要对本地旧日志重新投票，而是请follower过来直接抓就行了。即使对哪些尚未形成多数派的entry，也是一样的处理方式，并未进行重新投票，在他的协议里这个做法是没有问题的。但是multi-paxos原本的意思是，即使形成了多数派，仍然需要使用新的proposalID走一遍prepare-accept过程，工程上做了优化之后，对于明确标记了已形成多数派的entry可以不重新投票，但是未确认是否形成多数派的entry，则要求新任leader使用新的proposalID重新投票。因为multi-paxos并不假设日志间有连续确认的关系，每条日志之间相互独立，没有关系，1号日志尚未确认时，2号日志就可以确认形成多数派备份。

作者：朱一聪
链接：https://www.zhihu.com/question/19787937/answer/82340987
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Paxos是个精巧，又强大的协议，仅从过程的复杂度来说，确实如作者本人一再说的那样是个“简单的协议”，但是可以从非常多的角度来理解它为何正确，而原本的流程也并不适合直接工程化，这也是大概为什么工程上它存在如此多的变体。希望这个回答的让人更快的感受paxos的魅力，建立一个初步印象的同时不给人以误导。最后依然推荐larmport自己写的和paxos相关的三篇论文：« The Part-Time Parliament»、«Paxos made simple»、«Fast Paxos»前面关于Paxos的论述。2016/12/28上周和一个有真正paxos工程经验的人讨论一下paxos，paxos现在大多是应用于replication的一致性，用来实现一个多节点一致的日志，和他的讨论让我觉得要想真正的精确掌握paxos和它对应的强一致性领域，也许只有真正的在工程中实现过才行。这个回答只能当做是想要了解原理的入门吧，甚至可能有些微妙的地方还会产生误导。它介绍了paxos面向的问题，以及为何它的流程要这么设计，但还是希望对有兴趣阅读这个问题的有所帮助。2016 10/30现在看开头这段话是在是觉得有点羞耻，遂改之。我了解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类似的一致性协议，不仅从原理，也从工程角度出发，涉及方方面面，在写毕设中了就是写不动就翻翻的良作。我个人觉得阅读任何号称浅显易懂的解说Paxos算法的描述（比如下文=/=），最多只是让你更好的入门，要更深的理解Paxos以及所有等同于它的一致性协议，ZAB,Raft,ViewStamp，直接阅读相关论文，理解证明，理解它们哪里不同，为何本质上相同，与人探讨，在工程上自己实现，或者阅读开源实现的源代码才是最好的方式。分布式一致性是个有趣的领域，而Paxos和类似的协议对这个问题的重要性不喻，在过去的十年，Paxos几乎等价于分布式一致性。2016 6/20之前的答案最大的不严谨之处在于两个事件“先后”这种时序关系的处理上。paxos是个分布式一致性协议，它的事件需要多个节点共同参与，一个事件完成是指多个节点上均完成了自身负责的单机子事件(就让我门把这样的事件称为”分布式事件”)，这样的分布式事件可以看作是多个单机子事件的复合，但是即不能从两个分布式事件的先后推导出某个节点上它们的单机子事件的先后，也不能根据某个节点上两个单机子事件的先后断言它们对应的分布式事件的先后。举一个简单的例子，两个节点P1，P2;分布式事件a1设置每节点的本地变量v=1,分布式式事件a2设置每个节点本地变量v=2，如果我们称a1先于a2完成，那么对于节点P1而言，v=1发生在v=2之前还是之后都有可能;反之如果P1上v=1发生在v=2之前，a1和a2哪个县完成也都有可能。原来的回答有些地方论述分布式事件a1在a2之后(先)时，默认了单节点上，a1会比a2先达成状态，或者反之。实际上为了论证paxos的正确性，并不需要借助于分布式事件的时序(起码无用太在意物理时序），对于paxos流程中的分布式事件，例如提案被通过，值被决定，让我们忘记它们之间物理时间上的先后关系吧。下面就开始假装推导出paxos，作为一种理解协议的流程和协议如何保证正确性的方式。这样的推导的过程远比我想象的冗长；相比之下，论文中Lamport自己推导出Paxos的过程简洁、巧妙、漂亮，但是更抽象。在末尾用自己的语言描述了这种方式，作为补充。补充的版本基本思路来自«Paxos made simple»，和原文略有不同；总共不到1500字，却既说明了Paxos是如何得到的，又严谨的论证了Paxos的正确性。首先我们简单介绍paxos所保证的一致性的具体含义；达成一致的条件(何时达成一致）；基于的一个基本的数学原理；以及它需要满足的假设。什么是一致性?实际上这个词在不同地方语义并不那么一致，Paxos面向的是一个理论的一致问题，这个问题的通俗描述是：有一个变量v，分布在N个进程中，每个进程都尝试修改自身v的值，它们的企图可能各不相同，例如进程A尝试另v=a,进程B尝试另v=b，但最终所有的进程会对v就某个值达成一致,即上述例子中如果v=a是v达成一致时的值，那么B上，最终v也会为a。需要注意的是某个时刻达成一致并不等价于该时刻所有进程的本地的v值都相同，有一个原因是进程可能挂掉，你不能要求挂掉的进程任何事；更像是最终所有存活的进程本地v的值都会相同。这个一致性需要满足三个要求：1.v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v=2，那么这样的一致也太容易了，也没有任何实际意义。2.一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性。3.一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性。Paxos中变量v达成一致的条件： N个进程中大多数（超过一半）进程都认为v是同一个值，例如c，那么我们称v被决定为c。这样即使少数进程挂掉了，也不会使得一致无法达成。Paxos保证的一致性如下：不存在这样的情形，某个时刻v被决定为c，而另一个时刻v又决定为另一个值d。由这个定义我们也看到，当v的值被决定后，Paxos保证了它就像是个单机的不可变变量，不再更改。也因此，对于一个客户端可以多次改写值的可读写变量在不同的节点上的一致性问题，Paxos并不能直接解决，它需要和状态机复制结合。Paxos基于的数学原理：我们称大多数进程组成的集合为法定集合，两个法定集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。例如A,B,C,D,F进程组成的全集，法定集合Q1包括进程A,B,C，Q2包括进程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程。如果要说Paxos最根本的原理是什么，那么就是这个简单性质。同时，可以注意到，这个性质和达成一致的定义相呼应。Paxos中进程之间是平等的，即不存在一个特殊的进程，这是由于如果协议依赖于某个特殊的进程，那么这个进程挂掉势必会影响协议;而对于分布式环境，无法保证单个进程必然必活，能够容忍一定数量的进程挂掉，是分布式协议的必然要求。这是推导过程所要遵循的一个原则，就称为平等性原则好了。消息是进程间通信的唯一手段，对于分布式环境来说，这是显然的。Paxos要求满足的前置假设只有一个：消息内容不会被篡改；更正式的说是无拜占庭将军问题。假装的推导总是先从一些具体的场景开始，既然Paxos的假设仅仅只是消息不会被篡改,保证了这点任意场景下都能保证一致性，那么对于举例的场景它必然是能够保证一致性的；因此不妨先使得协议流程能在当前场景下能保证一致性，然后再举出另一个场景，当前的协议流程无法再该场景下满足一致性，接着再丰富协议流程，满足该场景，如此往复，最终得到完整的paxos协议，最后再不失一般性的论证协议对任意场景都能保证一致性。进程的平等性假设会带来如下的问题，考虑如下的场景1：三个进程的场景P1,P2P3（n个进程的场景类似），P1尝试令v的值被决定为a,P2尝试令v被决定为b。假设它们都先改写了自身的v值，然后发送消息尝试改修P3的v值。显然如果P3收到两个消息后都满足了它们的企图，那么v就会两次被决定为不同的值，这破坏了之前的定义。因此P3必须得拒绝掉其中一个进程的请求，如何拒绝也是我们最先考虑的问题。一个最简单的拒绝策略是先来后到，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永远无法被决定。更正式的说，这样的协议不满足活性，活性要求协议总能达成一致。由此我们也得到第一个结论:进程必须能够多次改写v的值。同时我们也要意识到：当进程收到第一个消息时，进程是没有任何理由拒绝这个消息的请求的。拒绝策略总是需要有一个依据，之前我们的依据是消息到达的先后，只接受第一个到达的消息，但这导致不满足活性。现在我们需要另一个拒绝策略，也就是需要另一个依据，这个依据至少能够区分两个消息。为此我们引入一个ID来描述这个消息，这样就可以根据ID的大小来作为拒绝或接受的依据；选择ID更大的消息接受和选择ID更小的消息接受是两种完全对称的策略，不妨选择前者。这个策略不会导致明显的活性问题，ID更大的消息总是能被接受，一个节点可以多次更改v的值。例如在场景1’中，只要P1的消息ID比P3发送给自己的消息ID更大，P3就会接受P1的消息，令v=a，从而令v的值被决定为a。再来考虑最初的场景1，不妨假设P1的消息ID大于P2的消息ID，根据P3收到消息的先后可以分为两种情况：1. P3先收到P1的消息，记做场景1-2。由于P1的消息是P3收到的第一个消息，P3接受该请求，令v=a；同时为了能对之后收到的消息作出是否接受的判断，P3需要记录该消息的ID作为判断的依据。之后P3又收到P2的消息，该消息的ID小于P3记录的ID(即P1的消息ID)，因此P3拒绝该消息，这样我们的目的就达到。2. P3先收到P2的消息，记作场景1-3。同样P3接受该消息，令v=b,记录该消息的ID。之后P3收到P1的消息，由于P1的消息ID大于P3记录的ID，因此P3无法拒绝该消息，之前的问题依旧存在。尽管对于场景1-3，目前的策略依旧无法保证一致性，但是起码我们缩小协议不适用的范围。先总结下我们目前的策略，并定义一些称谓以方便后面的论述。我们称呼进程P发送的尝试修改另一个进程中变量v的值的消息称之为提案，记作Proposal；提案的ID记作proposal_id；提案中会附带一个值，如果一个进程接受一个提案，则修改自身的v值为该提案中的值。如果一个提案被大多数进程所接受，那么称提案被通过，此时显然v被决定为提案中的值。进程P记录的接受的提案ID记做a_proposal_id。之前我们尚未清晰定义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）。同时在之前的描述中我们应当注意到实际上一个进程存在两个功能：1. 进程主动尝试令v的值被决定为某个值，向进程集合广播提案。2. 进程被动收到来自其它进程的提案，判断是否要接受它。因此可以把一个进程分为两个角色，称负责功能1的角色是提议者，记作Proposer，负责功能2的角色是接受者，记作Acceptor。由于两者完全没有耦合，所以并不一定需要在同个进程，但是为了方面描述，我们假定一个进程同时担任两种角色，而实际的工程实现也往往如此。接着我们尝试解决场景1-3,这看起来很难。P3作为接受者，收到P2的提案之前未收到任何消息，只能接受该提案，而由于P1的提案proposal_id大于P2的提案，我们的拒绝策略也无法让P3拒绝P2。我们先不急着推导具体可行的策略，先考虑下解决1-3场景可能的角度，有如下三种角度可以入手：1. P3能够拒绝掉P2的提案。2. P3能够拒绝掉P1的提案。3. 限制P1提出的提案中的值，如果P1的提案中的值与P2的提案一致，那么接受P1也不会破坏一致性。接着我们分析三个角度的可行性：角度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的提案被拒绝，似乎这是一个可行的角度。对于角度2，我们目前的策略无法做到这一点，因此除了proposal_id外，我们还得给提案附加上额外的信息作为另外的拒绝策略的依据。提案由进程提出，也许我们可以附加进程的信息，但是就算P3得知P1的提案由P1提出，P3又凭什么歧视P1，这违反进程的平等性假设。似乎这个角度不是一个好角度。最后我们分析一下角度3，角度3提供了与1,2截然不同的思路，它不再是考虑如何拒绝，而把注意力放在如何对提案的值做出恰当的限制上。对于场景1-3而言，从这个角度，由于P3无法拒绝P1和P2的提案中的任何一个，因此P1的提案的值就必须与P2的提案一致；这也意味着了P1在正式提出提案前，需要有途径能获悉P2的提案的值。如我们上面一直强调的，消息是唯一的通信手段，P1必须收到来自其它节点消息才有可能得知P2提出的提案的值。P1可以被动的等待收到消息，也可以主动的去询问其它节点等待回复。后者显然是更好的策略，没有收到想要的消息就一直等待未免也太消极了，这种等待也可能一直持续下去从而导致活性问题。经过上面的分析，我们暂时排除了从角度2入手（实际上后面也不会再考虑，因为从1,3入手已经足以解决问题）。下面将沿着角度1,3进行更深入的分析，我们先尝试从角度1出发，毕竟考虑如何拒绝已经有了经验。先来总结下我们在分析角度1时引入的额外的流程:进程P在发送提案前，先广播一轮消息，消息附带着接下来要发送的提案的proposal_id。由于该消息和接下来发送的提案相关，且在提案被提出之前发送，不妨称这个消息为预提案，记作PreProposal，预提案中附带着接下来的提案的proposal_id。当作为接受者的进程Pj收到预提案后，更新Pj. a_proposal_id。还记得我们之前的拒绝策略中a_proposal_id的更新策略嘛：a_proposal_id = max(proposal_id,a_proposal_id)，a_proposal_id是递增的。因此如果预提案的proposal_id小于Pj.a_proposal_id，Pj完全可以忽略这个预提案，因为这代表了该预提案对应的提案的proposal_id小于Pj.a_proposal_id，必然会被拒绝。我们沿用之前拒绝策略中a_proposal_id的更新策略。这样当收到预提案或者提案后，a_proposal_id的值均更新为 max(a_proposal_id,proposal_id)。接着我们来看看引入了预提案后，能否真正解决场景1-3。根据P1和P2的预提案到达P3的先后也存在两种场景：1.场景1-3-1：P1的预提案先到达，P3更新a_proposal_id 为该提案的proposal_id，这导致随后到达的P2的提案的proposal_id小于a_proposal_id，被拒绝。满足一致性2.场景1-3-2：P2的提案先到达，P3接受P2的提案，此时和原始的场景1-3存在同样的问题。归根结底，预提案阶段能否使得P3拒绝该拒绝的，也依赖消息到达的顺序，和提案阶段的拒绝策略存在相同的问题，但至少又缩小了不能保证安全性的场景范围。幸好我们还有角度3可以着手考虑，所以仍有希望完全解决场景1-3。在深入角度3之前，先总结下协议目前为止的流程，现在协议的流程已经分为了两个阶段：预提案阶段和提案阶段，两种消息：预提案和提案，两种角色：接受者和提议者，流程如下：阶段一提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id) 阶段二提议者Proposer：向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)为了更形象，之前的讨论是基于三个进程的场景,实际上对于N进程的场景也是一样的。N个进程时，与之前场景1对应的场景是：N个进程，存在两个进程Pi,Pj，Pi尝试另v被决定为a,Pj尝试另v被决定为b，Pi提出的预提案记作PreProposal-i，提案记作Proposal-i；Pj的预提案PreProsal-j，提案Proposal-j。之拒绝策略的讨论都是基于一个关键的进程P3，只要P3最终能拒绝Proposal-i和Proposal-j中的一个，两个提案就不会都被通过，那么一致性就不会被破坏。Pi的提案被通过代表了存在一个法定集合Q-i，Q-i中的进程都接受了Proposal-i，Pj同理，存在一个Q-j，Q-j中的进程都接受了Proposal-j。由于法定集合的性质，两个多数集Q-i和Q-j中必然存在一个公共进程Pk。Pk即相当于场景1中的P3，只要Pk能够拒绝Proposal-i和Proposal-j中的一个，协议依旧是安全的。为了不失一般性，下面我们都以N个进程的场景作为讨论的基础，称为场景2，由于场景1和场景2可以一一对应，所以接下来顺着限制提案的值的角度，我们直接针对场景2-3-2，之前的场景和场景1一样，我们的拒绝策略已经足以应付。v的值被决定代表有一个提案，它被法定数目的集合接受，我们称这为提案被通过。首先我们看下场景2-3-2，Pi对应场景1-3-2中的P1，Pj对应P2，Pk对应P3。Pj的提案Proposal-j最终会被法定集合Q-j接受，即v的值被决定为b，且Proposal-i.proposal-id > Proposal-j.proposal_id。我们需要限制Pi的提案的值，不能让Pi自由的给Proposal-i中的v赋值。在2-3-2中，由于拒绝策略失效，所以只能令Proposal-i.v = Proposal-j.v=b。要做到这一点，正如前面的分析所言，Pi需要先主动询问进程集合，来得知Proposal-j.v =b这一事实。显然Pi是没有先验信息来得知Proposal-j由哪个进程提出，也不知道Q-i和Q-j的公共节点Pk是谁，因此Pi只能广播它的查询。由于我们需要允许少数进程失败，Pi可能只能得到大多数进程的回复，而这之中可能不包括Pj。我们称这些回复Pi的查询的进程的集合为Q-i-2,为了描述更简单，无妨假设Q-i-2=Q-i。尽管Pi的查询可能得不到Pj的回复，好在作为将会被通过的提案，Proposal-j将会被Q-j内所有进程接受，因此如果进程作为接受者在接受提案时，顺便记录该提案，那么Q-j内所有进程都将得知Proposal-j.v=b。由于Pk属于Q-i和Q-j的交集，所以Pk即收到了Pi的查询，又接受了提案Proposal-j。之前我们已经引入了预提案阶段，显然我们可以为预提案附带上查询的意图，即Pk作为接受者收到Pi的预提案后，会回复它记录的接受过的提案。有一个问题是Pk此时是否已经记录了Proposal-j呢?很巧的是在场景2-3-2中，Pj的提案Proposal-j是先于Pi的预提案PreProposal-i先到达，所以Pk已经记录了Proposal-j.v = b，Pj收到的来自Pk的回复中包含了提案Proposal-j，而2-3-2之外的场景，拒绝策略已经足以应付。这里依旧还有两个问题，先讨论第一个：实际上除了Pi和Pj外可能还会有多个进程发起预提案和提案，所以收到 PreProposal-i时Pk可能已经接受过多个提案，并非只有Proposal-j，那么Pk应该回复PreProposal-i其中哪个提案，或者都回复？Pk并不知道Proposal-j会被通过，它只知道自己接受了该提案。都回复是个效率很低但是稳妥，可以保证Pk不会遗漏Proposal-j，Pk已经回复了它所能知道的全部，我们也无法要求更多。需要注意到的是进程是平等的，所以Q-i中所有进程都和Pk一样回复了它接受过的所有提案。当Pi收到所有来自Q-i的回复时，随之而来的是第二个问题：Pi收到了多个Proposal作为一个Acceptor组成的法定集合Q-i对PreProposal-i的回复，记这些Proposal组成的集合记坐K-i，那么它应当选择K-i中哪个一个提案的值作为它接下来的提案Proposal-i的v值？记最终选择的这个提案为Proposal-m。在场景2-3-2中，我们第一直觉是希望选择的Proposal-m 即是 Proposal-j，但是实际上，我们只要保证Proposal-m .v = Proposal-j.v即可。从另一个角度，K-i中很可能存在这样的提案Proposal-f,Proposal-f.v!=Proposal-j.v，我们要做的是避免选择到这类提案。我们可以根据一些依据瞎选碰碰运气，但是这并明智。我们不妨假设存在一个策略cf，cf满足需求，使得选择出提案Proposal-m满足Proposal-m.v= Proposal-j.v。然后让我们来分析一下此时Proposal-f有什么特征。Proposal-f能够被提出，代表存在一个多数集合Q-f，Q-f中每个进程都接受了PreProposal-f，同时假设是进程P-f提出了PreProposal-f和Proposal-f。Q-f和Q-j必然存在一个公共节点，记做Ps，Ps即接受了PreProposal-f又接受了Proposal-j。Ps收到PreProposal-f和Proposal-j的顺序只有两种可能：1.Ps先收到PreProposal-f2.Ps先收到Proposal-jPreProposal-f.proposa-id和Proposal-j. proposal_id的大小也只有两种可能，不妨先假设PreProposal-f.proposal_id > Proposal-j.proposal_id。对于情形1，Ps先收到PreProposal-f，接受它，更新Ps.a_proposal_id = PreProposal-f.proposal_id > Proposal-j.proposal_id，同时之前的a_proposal_id的更新策略又使得Ps.a_proposal_id是递增的，于是导致收到Proposal-j时,Proposal-j.proposal_id小于Ps.a_proposal_id,被拒绝，而这于Ps的定义矛盾。对于情形2，Ps将把提案Proposal-j回复给PreProposal-f。由于我们假设了策略cl的存在，于是P-f在收到所有Q-f对PreProposal-f的回复后，将令Proposal-f.v=Proposal-j.v，cl就是干这个的。因此由于Proposal-f.v!=Proposal-j.v矛盾。于是当假设PreProposal-f.proposal_id > Proposal-j.proposal_id 时，情形1,2我们都得出了矛盾，同时两者的proposal_id又不相等(最初的假设），所以必然PreProposal-f.proposal_id < Proposal-j.proposal_id，即Propsoal-f.proposal_id < Proposal-j.proposal_id。于是我们得到的结论是：如果策略cl存在，提案Proposal-j最终会被通过，任意一个proposal_id更大的预提案PreProposal-i，对于它得到的Q-i的回复K-i中的Proposal-f，只要Proposal-f.v!= Proposal-j.v，那么必然 Proposal-f.proposal_id < Proposal-j.proposal_id。既然K-i中所有v值不等于Proposal-j.v的提案，proposal_id都比Proposal-j更小，那代表所有proposal_id比Proposal-j更大的提案，v值都等于Proposal-j.v，因此选择K-i中proprosal_id最大的提案，就能保证Proposal-i.v = Proposal-j.v。于是我们得到了策略cl的具体形式。我们得到了具体可行的策略cl是建立在策略cl存在这一前提之上，因此反过来，对于这个具体的选值策略cl，结合之前我们得到了协议流程，它是否能保证如下的性质CP1，依旧需要进一步的论证：如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么Proposal-i.v = Proposal-j.v。我们先总结下目前得到的协议流程：阶段一预提案阶段提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id大于a_proposal_id，那么回复该预提案的提议者改接受者接受过的所有提案。阶段二提案阶段提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组合成的集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)这些流程是为了解决举例的场景而不断丰富的，接着就让我们论证下协议流程是否总是可以确保CP1。首先假设Proposal-i.v != Proposal-j.v，如果得出矛盾即可证明CP1。在尝试推出矛盾前，我们先做一些定义，以便后续的推导。记大多数接受者组成的法定集合为Q，K是提议者在提案阶段收到的所有Q回复的提案组成的集合，如果K不为空，记K中proposal_id最大的提案是MaxProposal(K)，本次提案的值即是MaxProposal(K).v；如果K是空集，那么MaxProposal(K).v = null。特别的，对于提案Proposal-i,回复它预提案接受者的集合为Q-i,回复的提案组成的集合为K-i，Proposal-i.v = MaxProposal(K-i)，Proposal-i.v=null代表可以随意赋值。为了描述方便，我们令Proposal-i的proposal_id为i，即Proposal-i代表了proposal_id=i的提案，Proposal-j意味着Proposal-j.proposal_id =j。论证过程如下：(1) Proposal-i.v!=Proposal-j.v，即MaxProposal(K-i) .v！= Proposal-j.v，即MaxProposal(K-i)!=Proposal-j(2) Proposal-j最终会被通过，代表最终会存在一个多数集合Q-j，Q-j中每个接受者都接受了Proposal-j。(3) 两个多数集必然存在公共成员，故Q-j和Q-i必然存在一个公共的进程Pk，Pk即收到了PreProposal-i又收到了Proposal-j，且都接受了它们；Pk收到消息的先后关系只存在如下两种可能：1.Pk先收到了PreProposal-i2.Pk先收到了Proposal-j(4) 情形1中Pk先收到了PreProposal-i，那么Pk收到Proposal-j时，Pk.a_proposal >= PreProposal-i.proposal_id ＞Proposal-j.proposal_id，Pk会拒绝Proposal-j，与(3)矛盾，因此情况1不可能，Pk必然是先收到Proposal-j。(5) 情形2中Pk收到PreProposal-i时，已经接受了Proposal-j，因此Pk回复PreProposal-i的提案中包含了Proposal-j，因此K-i中必然包含了Proposal-j。(6) 由(1)已知MaxProposal(K-i) != Proposal-j，即存在另一个提案Proposal-m = MaxProposal(K-i),而Proposal-j属于K-i,因此Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.v != Proposal-j.v。(7)由预提案阶段，接受者回复预提案的条件可知：Proposal-i.proposal_id大于集合K-i中任意一个提案的Proposal-id，故Proposal-i.proposal_id>Proposal-m.proposal_id。(8) 目前我们已经论证如下一点：在Proposal-j最终会被通过的前提下，如果存在一个提案Proposal-i.v!=Proposal-j.v，且Proposal-i.proposal_id >Proposal-j.proposal_id,我们一个数学符号来带表示这个情况，记CF(j,i)；那么必然存在一个提案Proposal-m, Proposal-m！=Proposal-j.v,且Proposal-m.proposal_id > Proposal-j.proposal_id，同样的我们可以记做CF(j,m)。并且Proposal-m.proposal_id < Proposal-i.proposal_id，m < i。即如果CF(i,j)成立，那么必然CF(m,j)成立，且i>m，即 CF(i,j) —> CF(m,j)。这个过程可以继续往下递归，但由于区间[j,i]范围是有限的，因此一定会递归到一个CF(j,e)，此时不可能存在一个提案，它的proposal_id在区间(j,e)内，无法往下递归，这与(8)矛盾。这也就意味着CF(e,j)不成立，而如果CF(i,j)成立，那么CF(e,j)成立,因此CF(i,j)不成立，故假设不成立，即Proposal-i.v 必然等于Proposal-j.v，即证CP1。通过归约的方式得出矛盾的方式依旧有些抽象，我们可以通过更好的定义假设来更容易得到的矛盾：我们加强对Proposal-i的约束;先假设存在一个提案的非空集合KD，KD中的任意一个提案Proposal-k,Proposal-k.v!=Proposal-j.v，且Proposal-k.proposal_id > Proposal-j.v;再假设Proposal-i是KD中proposal_id最小的提案；由于KD是非空集合，故Proposal-i必然存在。我们依旧可以从Proposal-i出发，(1)~(7)与上面相同，同理得到：存在一个提案Proposal-m, Proposal-m！=Proposal-v,且Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.proposal_id < Proposal-i.proposal_id。显然Proposal-m满足集合KD对提案的要求，故Proposal-m属于KD，又Proposal-m.proposal_id<Proposal-i.proposal_id，这和Proposal-i是KD中proposal_id最小的提案的定义矛盾。因此不存在这样的非空集合KD，即不存在一个提案Proposal-k,Proposal-k.v!=Proposal-j.v且Proposal-k.proposal_id>Proposal-j.proposal_id，即如果一个提案Proposal-j最终会被通过，对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么必定Proposal-i.v = Proposal-j.v，即CP1。CP1约束了proposal_id大于Proposal-j的提案的值，保证了如果一个提案Proposal-j最终会被通过，不会存在另一个proposal-id更大且值不同的提案被通过，因为这些提案的值都和Proposal-j相同。那么对于proposal_id更小的提案呢？我们假设存在一个提案Proposal-o,Proposal-o.proposal_id < Proposal-j.proposal_id，且Proposal-o.v!=Proposal-j.v,Proposal-o最终会被通过，将CP1应用于Proposal-o,则可知Proposal-j不存在，这矛盾，故Proposal-o不存在。故由CP1我们可知：如果一个提案Proposal-j最终会被通过，那么不存在另一个提案，它最终会被通过，且它的值与Proposal-j不同。由此协议必然是安全的。虽然我们得到了一个安全的一致性协议，基本上它就是Paxos，但是真正的Paxos要比我们假装推导出的协议更简单一点。回过头来看下我们的阶段1中接受者Acceptor的行为，它要回复所有的它接受过的提案，从实践的角度，不论是在本地保存所有它接受过的提案还是通过网络将它们传输给提议者，开销都太大且不可控。再看下阶段二中，提议者的选值策略，它只是选择了收到的多数集接受者回复的提案中proposal_id最大的那一个，因此接受者实际上只需要回复它接受过的proposal_id最大的提案即可，因为其它提案根本不可能会被选值策略选中。因此最终的协议如下，它就是Paxos:阶段一预提案阶段：提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id>a_proposal_id，Acceptor回复记录的接受过的proposal_id最大的提案。阶段二提案阶段：提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组成的法定数目的提案集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。然后把该提案广播给接受者们，提案和预提案共享同一个proposal_id。接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新记录的提案。补充部分：上面的过程从具体的场景开始推导Paxos，虽然直观但是繁琐，如果从抽象的概念和分析入手，那么过程将会相当简洁和漂亮，这也是Lamport的原始论文中的方式。这种方式理解起来更困难的地方在于：1.没有任何具体的认知下，直接抽象的讨论容易让人摸不着头脑。2.大神总是在一些地方觉得显然而不加以展开论述，而普通读者如我的内心OS:显然你mei!但是原文引出Paxos算法的过程实在是简洁、漂亮；而经过上面的轮述，相信有了直观的印象后，再来看抽象的方式也不那么困难，所以补充下。回顾下定理CP1：如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么必定Proposal-i.v = Proposal-j.v。上面我们已经论证了只要协议能够保证CP1就能够保证一致性。但是CP1依旧过于宽泛，从CP1引出具体的协议流程依然是一头雾水，那么我们是否可以得到一个更加具体的定理CP2，保证CP2即可保证CP1，同时从CP2出发更容易引出协议的具体流程。为了描述方便，我们令Proposal-i的proposal_id为i，即Proposal-i代表了proposal_id=i的提案。要导出CP2不妨先考虑下如何证明CP1，利用归纳法，只要如能证明如下性质成立，即可证明CP1：如果proposal_id在区间[j,i）内任意的提案，提案的值均为Proposal-j.v，那么必定Proposal-i.v=v;这个定理记做CP1_2。现在我们用高中时简单而效果神奇的归纳法，利用CP1_2证明下CP1:假设propsal_id小于i的提案中最大的提案是Proposal-(i-1)。1.如果对于[j,i-1)内的任意提案，值均为Proposal-j.v，那么由CP1_2可知Proposal-i.v = Proposal-j.v。2.由1可知如果对于[j,i-1)内的任意提案，值均为Proposal-j.v，[j,i)内的任意提案，值均为Proposal-j.v3.假设Proposal-(j+1)是proposal-id大于j的最小提案，由CP1_2可知Proposal-(j+1).v = Proposal-j.v4.由3,2归纳可知[j, )内任意提案Proposal-i，Proposal-i.v = Proposal-j.v，即CP1来看下CP1_2，相比CP1，它结论不变，但是多了一个前置条件：proposal_id在区间[j,i）内任意的提案值均为Proposal-j.v；这是一个重大的进步。CP1_2相比CP1看起来容易保证很多，但是它们却是等价的。考虑CP1_2的三个前置条件：1.i > j2.提案Proposal-j最终会被通过。因此由提案被通过的定义可知必然存在一个法定集合Q-j，Q-j中任意一个接受者最终都接受了Proposal-j3.proposal_id在区间[j,i)内的提案的值均为Proposal-j.v对于任意的一个法定集合Q，考虑Q最终（包括过去和未来的所有时空）会接受的所有proposal_id小于i的提案组成的集合K。根据法定集合性质，Q和Q-j必然存在一个公共的节点，即Q中必然存在一个节点，该节点最终会接受Proposal-j，因此集合K包含Proposal-j。由K包含Proposal-j可知K中最大的提案proposal_id >= j；由CP1_2的前置条件3和K的定义可知如果K中存在proposal-id大于j的提案，那么该提案的值等于Proposal-j.v，因此K中proposal_id最大的提案的值等于Proposal-j.v。综上所述由CP1_2的前置条件可知：对于任意的一个法定集合Q，Q最终会接受的proposal_id小于i的提案组成的集合K，K中proposal_id最大的提案的值必定为Proposal-j.v。如果我们能证明该条件下，Proposal-i.v = Proposal-j.v，即可证明CP1_2。将CP1_2的前置条件替换为该条件，我们可以得到一个如下的性质CP2，保证CP2即可保证CP1_2：对于任意的一个法定集合Q，Q最终会接受的所有proposal_id小于i的提案组成的集合K，如果K中proposal_id最大的提案的值为Proposal-j.v;那么Proposal-i.v = Proposal-j.v。而引出满足CP2的流程就比较容易了，由于集合K中proposal_id最大的提案的值等于Proposal-j.v，看起来只要令Proposal-i的值为K中proposal-id最大提案的值就可以保证CP2。由于Q是任意一个法定集合，因此获取K似乎在实现上也不难，提出Proposal-i的提议者只要向Q中所有接受者询问即可。然后： CP2 —> CP1_2—> CP1 —>一致性但是实际上获取K没有那么简单，K包含的是Q所有最终接受的proposal-id小于i的的提案，不仅包含已经接受过的提案，还包括未来会接受的提案。获取已经接受过的提案是容易的，Q中的接受者只需记录它所有接受过的提案，当收到提出Proposal-i的提议者询问时，回复当中proposal_id小于i的提案即可;但是如何知晓未来？我们可以换个思路，既然无法知晓未来，那么我们约束未来，收到询问后，令Q中的接受者都承诺不再接受任何proposal_id小于i的提案，即接受者未来将不接受任何proposal_id小于i的提案;既然未来已不存在，那么Proposal-i的提议者根据Q的回复获能得到完整的K。于是协议的流程如下：对于提议者，在正式提案前，先向任意的法定集合Q发送一个消息，这个消息即是预提案，消息中要附带提案的proposal-id，作为接受者承诺和回复的依据。接受者收到预提案后，承诺：不再接受比预提案中附带的proposal-id更小的提案；并回复:已经接受的proposal-id比于提案的proposal-id更小的提案，如之前所论述的，回复的所有满足条件的提案可以优化为只回复一个比预提案proposal_id更小的提案中proposal_id最大的那个提案。提议者收到所有Q中接受者回复的提案后，挑选其中proposal_id最大的提案的值作为本次提案的值。这样我们就得到了Paxos中最为关键的几步，阅读了之前冗长的假装推导，相信读者很容易就能补全它得到完整的Paxos。相比于之前近万字的假装推导，这个推导过程才1500字左右，但是即说清了Paxos是如何得出的，又论证Paxos为何正确，简洁却更有力。所以最后还是建议真有兴趣的话去看下原文，在我看来它无疑是计算机领域那数不尽的论文中最值得阅读的那一类。末尾我所描述的版本思路来自«Paxos made simple»，基本一致但也并不完全相同；而« The Part-Time Parliament»则别有一番风味。最后需要注意的是Paxos并不完全满足开头解决一致性问题需要满足的三个条件中的3。理论上，Paxos存在永远无法达成一致的可能，哪怕是在所有进程都存活的情况下。想象一下这样的场景，一个提案Proposal-j被提出时，恰好一个proposal-id更大的预提案Proposal-i被提出，导致Proposal-j无法被通过，而Proposal-i同样的又因为一个proposal_id更大的其它预提案被提出，导致无法被通过。这种情况理论上存在无限递归的可能，这个问题也称为活锁;FLP早就证明了就算是容忍一个进程的失败，异步环境下任何一致性算法都存在永不终止的可能。但是实际的工程中，很多手段可以来减小两个提案的冲突概率，使得v被决定的均摊开销是一个提案，多个提案还无法决定v值的情形是极小概率事件，且概率随着提案个数增加越来越小。另外的一点，通常认为Paxos可以容忍少数进程挂掉，但这只是为了保证它的活性，对于安全性，实际上Paxos永远满足1,2，哪怕进程都挂掉了，此时只是显然一致无法达成而已。

数据库高可用性难题
数据库的数据一致和持续可用对电子商务和互联网金融的意义不言而喻，而这些业务在使用数据库时，无论 MySQL 还是 Oracle，都会面临一个艰难的取舍，就是如何处理主备库之间的数据同步。对于传统的主备模式或者一主多备模式，我们都需要考虑的问题，就是与备机保持强同步还是异步复制。

对于强同步模式，要求主机必须把 Redolog 同步到备机之后，才能应答客户端，一旦主备之间出现网络抖动，或者备机宕机，则主机无法继续提供服务，这种模式实现了数据的强一致，但是牺牲了服务的可用性，且由于跨机房同步延迟过大使得跨机房的主备模式也变得不实用。

而对于异步复制模式，主机写本地成功后，就可以立即应答客户端，无需等待备机应答，这样一旦主机宕机无法启动，少量不同步的日志将丢失，这种模式实现了服务持续可用，但是牺牲了数据一致性。这两种方式对应的就是 Oracle 的 Max Protection 和 Max Performance 模式，而 Oracle 另一个最常用的 Max Availability 模式，则是一个折中，在备机无应答时退化为 Max Performance 模式，我认为本质上还是异步复制。

主备模式还有一个无法绕过的问题，就是选主，最简单山寨的办法，搞一个单点，定时 Select 一下主机和各个备机，貌似 MHA 就是这个原理，具体实现细节我就不太清楚了。一个改进的方案是使用类似 ZooKeeper 的多点服务替代单点，各个数据库机器上使用一个 Agent 与单点保持 Lease，主机 Lease 过期后，立即置为只读。改进的方案基本可以保证不会出现双主，而缺点是 ZooKeeper 的可维护性问题，以及多级 Lease 的恢复时长问题（这个本次就不展开讲了，感兴趣的同学请参考这篇文章 Http://oceanbase.org.cn/

Paxos 协议简单回顾
主备方式处理数据库高可用问题有上述诸多缺陷，要改进这种数据同步方式，我们先来梳理下数据库高可用的几个基本需求：

数据不丢失

服务持续可用

自动的主备切换

使用Paxos协议的日志同步可以实现这三个需求，而 Paxos 协议需要依赖一个基本假设，主备之间有多数派机器（N / 2 + 1）存活并且他们之间的网络通信正常，如果不满足这个条件，则无法启动服务，数据也无法写入和读取。

我们先来简单回顾一下 Paxos 协议的内容，首先，Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数派离线的情况下，剩余的多数派节点仍然能够达成一致。然后，再来看一下协议内容，它是一个两阶段的通信协议，推导过程我就不写了（中文资料请参考这篇 Http://t.cn/R40lGrp ），直接看最终协议内容：

1、第一阶段 Prepare

P1a：Proposer 发送 Prepare

Proposer 生成全局唯一且递增的提案 ID（Proposalid，以高位时间戳 + 低位机器 IP 可以保证唯一性和递增性），向 Paxos 集群的所有机器发送 PrepareRequest，这里无需携带提案内容，只携带 Proposalid 即可。

P1b：Acceptor 应答 Prepare
Acceptor 收到 PrepareRequest 后，做出“两个承诺，一个应答”。

两个承诺：

第一，不再应答 Proposalid 小于等于（注意：这里是 <= ）当前请求的 PrepareRequest；

第二，不再应答 Proposalid 小于（注意：这里是 < ）当前请求的 AcceptRequest

一个应答：

返回自己已经 Accept 过的提案中 ProposalID 最大的那个提案的内容，如果没有则返回空值;

注意：这“两个承诺”中，蕴含两个要点：

就是应答当前请求前，也要按照“两个承诺”检查是否会违背之前处理 PrepareRequest 时做出的承诺；

应答前要在本地持久化当前 Propsalid。

2、第二阶段 Accept

P2a：Proposer 发送 Accept
“提案生成规则”：Proposer 收集到多数派应答的 PrepareResponse 后，从中选择proposalid最大的提案内容，作为要发起 Accept 的提案，如果这个提案为空值，则可以自己随意决定提案内容。然后携带上当前 Proposalid，向 Paxos 集群的所有机器发送 AccpetRequest。

P2b：Acceptor 应答 Accept

Accpetor 收到 AccpetRequest 后，检查不违背自己之前作出的“两个承诺”情况下，持久化当前 Proposalid 和提案内容。最后 Proposer 收集到多数派应答的 AcceptResponse 后，形成决议。

这里的“两个承诺”很重要，后面也会提及，请大家细细品味。

Basic Paxos 同步日志的理论模型
上面是 Lamport 提出的算法理论，那么 Paxos 协议如何具体应用在 Redolog 同步上呢，我们先来看最简单的理论模型，就是在 N 个 Server的机群上，持久化数据库或者文件系统的操作日志，并且为每条日志分配连续递增的 LogID，允许多个客户端并发的向机群内的任意机器发送日志同步请求。在这个场景下，不同 Logid 标识的日志都是一个个相互独立的 Paxos Instance，每条日志独立执行完整的 Paxos 两阶段协议。

因此在执行 Paxos 之前，需要先确定当前日志的 Logid，理论上对每条日志都可以从 1 开始尝试，直到成功持久化当前日志，但是为了降低失败概率，可以先向集群内的 Acceptor 查询他们 PrepareResponse 过的最大 Logid，从多数派的应答结果中选择最大的 Logi-d，加 1 后，作为本条日志的 Logid。然后以当前 Logid 标识 Paxos Instance，开始执行Paxos两阶段协议。可能出现的情况是，并发情况下，当前 Logid 被其他日志使用，那么在 P2a 阶段确定的提案内容可能就不是自己本次要同步的日志内容，这种情况下，就要重新决定logid，然后重新开始执行 Paxos 协议。

考虑几种异常情况，Proposer 在 P1b 或 P2b 阶段没有收到多数派应答，可能是受到了其他 Logid 相同而 Proposalid 更大的 Proposer 干扰，或者是网络、机器等问题，这种情况下则要使用相同的 Logid，和新生成的 Proposalid 来重新执行 Paxos 协议。恢复时，按照 Logid 递增的顺序，针对每条日志执行完整 Paxos 协议成功后，形成决议的日志才可以进行回放。那么问题来了：比如 A/B/C 三个 Server，一条日志在 A/B 上持久化成功，已经形成多数派，然后B宕机；另一种情况，A/B/C 三个 Server，一条日志只在A 上持久化成功，超时未形成多数派，然后B宕机。上述两种情况，最终的状态都是 A 上有这条日志，C 上没有，那么应该怎么处理呢？

这里提一个名词：“最大 Commit 原则”，这个阳振坤博士给我讲授 Paxos 时提出的名词，我觉得它是 Paxos 协议的最重要隐含规则之一，一条超时未形成多数派应答的提案，我们即不能认为它已形成决议，也不能认为它未形成决议，跟“薛定谔的猫”差不多，这条日志是“又死又活”的，只有当你观察它（执行 Paxos 协议）的时候，你才能得到确定的结果。因此对于上面的问题，答案就是无论如何都对这条日志重新执行 Paxos。这也是为什么在恢复的时候，我们要对每条日志都执行 Paxos 的原因。

Multi Paxos 的实际应用
上述 Basic-Paxos 只是理论模型，在实际工程场景下，比如数据库同步 Redolog，还是需要集群内有一个 leader，作为数据库主机，和多个备机联合组成一个 Paoxs 集群，对 Redolog 进行持久化。此外持久化和回放时每条日志都执行完整 Paxos 协议（3 次网络交互，2 次本地持久化），代价过大，需要优化处理。因此使用 Multi-Paxos 协议，要实现如下几个重要功能：

自动选主

简化同步逻辑

简化回放逻辑

我在刚刚学习 Paxos 的时候，曾经认为选主就是跑一轮 Paxos 来形成“谁是 leader”的决议，其实并没有这么简单，因为 Paxos 协议的基本保证就是一旦形成决议，就不能更改，那么再次选新主就没办法处理了。因此对“选主”，需要变通一下思路，还是执行 Paxos 协议，但是我们并不关心决议内容，而是关心“谁成功得到了多数派的 AcceptResponse”，这个 Server 就是选主产生的 Leader。而多轮选主，就是针对同一个 Paxos Instance 反复执行，最后赢得多数派 Accept 的 Server 就是“当选 Leader”。

不幸的是执行 Paxos 胜出的“当选 Leader”还不能算是真正的 Leader，只能算是“当选 Leader”，就像美国总统一样，“当选总统”是赢得选举的总统，但是任期还未开始他还不是真正的总统。在 Multi-Paxos 中因为可能存在多个 Server 先后赢得了选主，因此新的“当选leader”还要立即写出一条日志，以确认自己的 Leader 身份。这里就顺势引出日志同步逻辑的简化，我们将 Leader 选主看作 Paxos 的 Prepare 阶段，这个 Prepare 操作在逻辑上一次性的将后续所有即将产生的日志都执行 Prepare，因此在 Leader任期内的日志同步，都使用同一个 Proposalid，只执行 Accept 阶段即可。那么问题来了，各个备机在执行 Accept 的时候，需要注意什么？

答案是上面提到过的“两个承诺”，因为我们已经把选主的那轮 Paxos 看做 Prepare 操作了，所以对于后续要 Accept 的日志，要遵守“两个承诺”。所以，对于先后胜出选主的多个“当选 Leader”，他们同步日志时携带的 Proposalid 的大小是不同的，只有最大的 Pro-posalid 能够同步日志成功，成为正式的 Leader。

再进一步简化，选主 Leader 后，“当选 Leader”既然必先写一条日志来确认自己的 Leader身份，而协议允许多个“当选 Leader”产生，那么选主过程的本质其实就是为了拿到各个备机的“两个承诺”而已，选主过程本身产生的决议内容并没有实际意义，所以可以进一步简化为只执行 Prepare 阶段，而无需执行 Accept。

再进一步优化，与 Raft 协议不同，Multi-Paxos 并不要求新任 Leader 本地拥有全部日志，因此新任 Leader 本地可能与其他 Server 相差了一些日志，它需要知道自己要补全哪些日志，因此它要向多数派查询各个机器上的 MaxLogD，以确定补全日志的结束 LogID。这个操作成为 GetMaxLogID，我们可以将这个操作与选主的 Prepare 操作搭车一起发出。这个优化并非 Multi-Paxos 的一部分，只是一个工程上比较有效的实现。

回放逻辑的简化就比较好理解了，Leader 对每条形成多数派的日志，异步的写出一条“确认日志”即可，回放时如果一条日志拥有对应的“确认日志”，则不需要重新执行 Paoxs，直接回放即可。对于没有“确认日志”的，则需要重新执行 Paxos。工程上为了避免“确认日志”与对应的 Redolog 距离过大而带来回放的复杂度，往往使用滑动窗口机制来控制他们的距离。同时“确认日志”也用来提示备机可以回放收到的日志了。与 Raft 协议不同，由于 Multi-Paxos 允许日志不连续的确认（请思考：不连续确认的优势是什么？），以及允许任何成员都可以当选 Leader，因此新任 leader 需要补全自己本地缺失的日志，以及对未“确认”的日志重新执行 Paxos。我把这个过程叫做日志的“重确认”，本质上就是按照“最大commit原则”，使用当前最新的 Proposalid，逐条的对这些日志重新执行 Paxos，成功后再补上对应的“确认日志”。

相对于 Raft 连续确认的特性，使用 Multi-Paxos 同步日志，由于多条日志间允许乱序确认，理论上会出现一种被称我们团队同学戏称为“幽灵复现”的诡异现象，如下图所示（图片引用自我的博客）

第一轮中A被选为 Leader，写下了 1-10 号日志，其中 1-5 号日志形成了多数派，并且已给客户端应答，而对于 6-10 号日志，客户端超时未能得到应答。

第二轮，A 宕机，B 被选为 Leader，由于 B 和 C 的最大的 LogID 都是 5，因此 B 不会去重确认 6 - 10 号日志，而是从 6 开始写新的日志，此时如果客户端来查询的话，是查询不到上一轮 6 - 10 号日志内容的，此后第二轮又写入了 6 - 20 号日志，但是只有 6 号和 20 号日志在多数派。

第三轮，A 又被选为 Leader，从多数派中可以得到最大 LogID 为 20，因此要将 7 - 20 号日志执行重确认，其中就包括了 A 上的 7-10 号日志，之后客户端再来查询的话，会发现上次查询不到的 7 - 10 号日志又像幽灵一样重新出现了。

处理“幽灵复现”问题，需要依赖新任 Leader 在完成日志重确认，开始写入新的 Redolog 之前，写出一条被称为 StartWorking 的日志，这条日志的内容中记录了当前 Leader 的 EpochID（可以使用 Proposalid 的值），并且 Leader 每写一条日志都在日志内容中携带现任 Leader 的 EpochID。回放时，经过了一条 StartWorking 日志之后，再遇到 EpochID 比它小的日志，就直接忽略掉，比如按照上面例子画出的这张图，7 - 19 号日志要在回放时被忽略掉。

依赖时钟误差的变种 Paxos 选主协议简单分析
阿里的阳振坤老师根据 Paxos 协议设计了一个简化版本的选主协议，相对 MultiPaxos 和 Raft 协议的优势在于，它不需要持久化任何数据，引入选主窗口的概念，使得大部分场景下集群内的所有机器能够几乎同时发起选主请求，便于投票时比对预定的优先级。下面的图引用自 OB 团队在公开场合分享 PPT 中的图片。

如图所示，选主协议规定选主窗口开启是当前时间对一个T取余为0的时间，即只能在第 0，T，2T，3T…N*T 的时间点上开启选主窗口，协议将一次选主划分为三个阶段

T1 预投票开始即由各个选举组成员向集群里的其他机器发送拉票请求；

一段时间后进入 T2 预投票开始，选举组各个成员根据接受到的拉票请，从中选出优先级最高的，给它投票应答；

一段时间后进入 T3 计票阶段，收到多数派投票的成员成为 leader，并向投票组其他成员发送自己上任的消息。

假设时钟误差最大为 Tdiff，网络网路传输单程最长耗时为 Tst

收到预投票消息的时间区间 [T1 - Tdiff × 2，T1 + Tdiff × 2 + Tst = T2]

收到投票消息的时间区间 [T2 - Tdiff×2，T2 + Tdiff × 2 + Tst = T3]

收到广播消息的时间区间 [T3 - Tdiff×2，T3 + Tdiff × 2 + Tst = T4]

选主耗时 Telect = T4-T1 = Tdiff × 6 + Tst × 3

因此最差情况下，选主开始后，经过 Tdiff × 6 + Tst × 3 的 d 时间，就可以选出 Leader 各个成员投出选票后，就从自己的 T1 时刻开始计时，认为 leader 持续 lease 时间内有效，在 Lease 有效期内，Leader 每隔 Telect 的时间就向其他成员发出续约请求，将 Lease 时间顺延一个 Telect，如果 Lease 过期后 Leader 没有续约，则各个成员等待下一个选主窗口到来后发起选主。因此最差情况下的无主时间是：Lease 时间 + Telect + 选主窗口间隔时间 T。

这个选主算法相对 Paxos 和 Raft 更加简单，但是对时钟误差有比较强的依赖，时钟误差过大的情况下，会造成投票分裂无法选出主，甚至可能出现双主（不过话说任何保持 Leader 身份的 Lease 机制都得依赖时钟…），因此可能仅仅适合 BAT 这种配备了原子钟和 GPS 校准时钟，能够控制时钟误差在 100ms 以内的土豪机房。2015 年闰秒时，这个选主算法已经上线至支付宝，当时测试了几个月吧，1 秒的跳变已经太大，当时测试了几个月，修改 ntp 配置缓慢校准，最后平稳渡过。

Q & A
1、ZooKeeper 所使用的 zad 协议与 Paxos 协议有什么区别？

Zab 用的是Epoch 和 Count 的组合来唯一表示一个值, 而Raft 用的是 Term和 Index.

Zab 的 Follower 在投票给一个 Leader 之前必须和 Leader 的日志达成一致,而 Raft的 Follower 则简单地说是谁的 Term 高就投票给谁。

Raft 协议的心跳是从 Leader 到 Follower, 而 zab 协议则相反。

Raft 协议数据只有单向地从 Leader 到 Follower (成为 Leader 的条件之一就是拥有最新的 Log), 而 Zab 协议在 Discovery 阶段, 一个 Prospective Leader 需要将自己的Log 更新为 Quorum 里面最新的 Log,然后才好在 Synchronization 阶段将 Quorum 里的其他机器的 Log 都同步到一致。

2、Paxos 能完成在全球同步的业务吗？理论上支持多少机器同步?
Paxos 成员组横跨全球的案例我还没有见过 Paper，我个人认为它并不适合全球不同，原因是延迟太大，但是 Google 的 Spanner 和 Amazon 的 Aurora 都实现了横跨北美多 IDC 的同步；理论上多少都行，你能接受延迟就可以。

3、问个问题，能否简单说说 Raft 算法和 Paxos 算法的异同？应用场的异同？

Raft 可以认为是一种简化的 Multi-Paxos 实现，他的最大简化之处在于备机接受 Leader 日志的前提是收到 LogID 连续的日志，在这个假设前提下，没有我文中提到的“幽灵复现”和“重确认”问题。简化带来的代价是对网络抖动的容忍度稍低一些，考虑这样的场景 ABC 三台机器，C 临时下线一会错过一些日志，然后 C上线了，但是在 C 补全日志之前，AB 如果再宕机一台的话，服务就停了。

4、Paxos 实现是独立的库或服务还是和具体的业务逻辑绑定，上线前如何验证 Paxos 算法实现的正确性？

OB 实现的 Paxos 是和事务 Redolog 库比较紧耦合的，没有独立的库；测试方案一个是 Monkey tests，随机模拟各种异常环境，包括断网、网络延迟、机器宕机、包重复到达等情况保持压力和异常；另外一个是做了一个简易的虚拟机，来解释测试 Case，通过人工构造多种极端的场景，来是系统立即进入一个“梦境”。

5、Logid 和 proposalid都应该是不能重复的，这个是如何保证的？原子钟的精确性仅仅是为了选主吗？

首先，Leader 任期内，Logid 只由 Leader 产生，没有重复性的问题；

第二，Leader 产生后，会执行 GetMaxLogID，从集群多数派拿到最大的 Logid，加以后作为本届任期内的 Logid 起点，这也可以保证有效日志 logid 不重复。Proposalid，高位使用 64 位时间戳，低位使用 IP 地址，可以保证唯一性和递增性。

6、在用 Paxos 协议做 Master 和 Slave 一致性保证时，Paxos 日志回放应该怎样去做？

Master 形成多数派确认后，异步的写出“确认日志”，Slave 回放到确认日志之后，才能去回放收到的正常日志。因此一般情况下，备机总是要落后主机一点点的。

paxos是在多个成员之间对某个值(提议)达成一致的一致性协议。这个值可以是任何东西。比如多个成员之间进行选主，那么这个值就是主的身份。在把multi-paxos协议应用在日志同步中时，这个值就是一条日志。网上讲paxos的文章已经很多了，这里简要说明一下。

paxos分为prepare和accept两个阶段。协议中有两个主要的角色，proposer和acceptor。

value被majority accept之前，每个acceptor可以accept多个不同的值。但是，一旦一个value被majority accept(即value达成一致)，那么这个value就不会变了。因为prepare阶段会将该value给找出来，随后accept阶段会使用这个value，后续的所有的提案都会选择这个value。

需要注意的是，每个阶段都是收到majority的响应后即开始处理。并且由于机器会宕机，acceptor需要对acceptedProposalID, acceptedValue和minProposal进行持久化。

从流程中可以看出prepare有两个作用:

大的proposal id会block未完成的小的proposal id达成一致的过程，所以为了减少无效的prepare请求，每次都选择比自己以往见过的proposal id更大的id。
一旦某个value达成一致，那么后续的prepare都会找到这个value作为accept阶段的值
可以看出，一次paxos达成一致至少需要两次网络交互。

multi-paxos
paxos是对一个值达成一致，multi-paxos是运行多个paxos instance来对多个值达成一致，每个paxos instance对一个值达成一致。在一个支持多写并且强一致性的系统中，每个节点都可以接收客户端的写请求，生成redo日志然后开始一个paxos instance的prepare和accept过程。这里的问题是每条redo日志到底对应哪个paxos instance。

在日志同步应用中，用log id来区分不同的paxos instance。每条日志都由一个id唯一标示，这个log id标识一个paxos instance，这个paxos instance达成一致，即对应的日志内容达成一致，即majority的成员accept了这个日志内容。在一个由N个机器(每个机器既承担proposer也承担acceptor角色)组成的集群(通常叫做paxos group)中，每个proposer都可以产生redo日志并且进行paxos instance，那么每条redo日志到底使用哪个log id? 显然，每个proposer都会选择自己知道的还没有达成一致的最小的log id来作为这次日志的log id，然后运行paxos协议，显然，多个proposer可能会选择同一个log id(最典型的场景就是空集群启动的情况下),最终，只有一个proposer能够成功，那么其他的proposer就需要选择更大的未达成一致的log id来运行paxos。显然，这种冲突是非常严重的，会有很多的proposer成功不了进而选择更大的log id来运行paxos。

在真实的系统中，比如chubby, spanner，都会在paxos group中选择一个成员作为leader，只有leader能够propose日志，这样，prepare阶段就不会存在冲突，相当于对整个log文件做了一次prepare，后面这些日志都可以选用同一个proposal id。这样的话，每条日志只需要一次网络交互就能达成一致。回顾一下文章开头提到paxos中需要每个成员需要记录3个值，minProposal，acceptedProposal,acceptedValue，其中后面两个值可以直接记录在log中，而第一个值minProposal可以单独存在一个文件中。由于这里后面的日志都可以选用同一个proposal id，显然，在大部分时间内，minProposal都不需要改变。这正是multi-paxos的精髓

选主
对于paxos来说，主的身份无所谓，主不需要像raft那样拥有最全的已经commit的日志。所以选主算法无所谓，比如大家都给机器ip最大的机器投票，或者给日志最多的投票，或者干脆直接运行一次paxos，值的内容就是主的身份。显然，由于对新主的身份无限制，那么，新主很有可能没有某些已经达成一致的日志，这个时候，就需要将这些已达成一致的日志拉过来，另外，新主也有可能没有某些还未达成一致的日志。如下图所示：

图中，恢复之前，log id等于3的日志C已经在多数派上达成了一致，但是在新主上没有。比如log id等于4的日志D在多数派上没有达成一致，在新主上也没有。

恢复
新主向所有成员发送查询最大log id的请求，收到majority的响应后，选择最大的log id作为日志恢复的结束点。图中，如果收到的majority不包括2号成员，那么log id=6为恢复结束点。如果收到的majority包括2号成员，那么log id=7为恢复结束点。这里取majority的意义在于恢复结束点包含任何的majority达成一致的日志。拿到log id后，从头开始扫描日志，对于每条日志都运行paxos协议确认一次：如果日志之前已经达成一致了，比如日志A，B，C，E，F，那么再次运行paxos的prepare阶段会把日志内容找出来作为accept阶段的值，不影响结果。如果日志之前并没有达成一致，比如日志D，那么当返回的majority中包含3号成员时，D会被选出来当作accept阶段的值，当返回的majority中不包含3号成员时，那么D实际上不会被选出，这时主可以选择一个dummy日志作为accept阶段的值。

恢复优化
可以看出，如果日志非常多，每次重启后都要对每条日志做一次paxos，那么恢复时间可想而知。在上面的例子中，A,B,E已经达成一致，做了无用功。paxos协议中，只有主即proposer知道哪些日志达成了一致，acceptor不知道，那么很容易想到的一个优化就是proposer将已经达成一致的日志id告诉其他acceptor,acceptor写一条确认日志到日志文件中。后续重启的时候，扫描本地日志只要发现对应的确认日志就知道这条日志已经达成多数派，不需要重新使用paxos进行确认了。这种做法有一个问题，考虑如下场景:

旧主成功的给自己和2号成员发送了确认日志，但是没有给3号成员发送成功旧挂了，然后2号成员被选为新主，那么新主不会对log id=3的日志重新运行paxos，因为本机已经存在确认日志。这样的话，3号成员就回放log id=3的日志到上层了。解决这个问题的做法就是followers需要主动的向主询问日志到底有没有达成一致，如果有，则自己补充确认日志。

回放
宕机重启后，对未达成一致的日志重新运行paxos时，如log id=4的日志，如果返回的majority中不包含3号成员，那么日志D不会被找出来，这样就需要将3号成员的log id=4日志置未一条无操作的日志记作NOP日志，D最终也就不会形成多数派。由于multi-paxos允许日志乱序接收，并且日志的长度几乎都不一样，所以在磁盘上log id是乱序的，所以从物理上说，每个成员的日志不是一模一样的。那么要把log id=4的日志覆盖写成NOP日志也就比较麻烦，需要为每条日志维护索引。实现上可以不覆盖写，直接append一条log id=4的NOP日志到日志文件，这样没有问题，因为回放的时候只会回放能找到确认日志的日志到上层应用中。

成员变更
multi-paxos处理成员变更比较简单，规定第i条日志参与paxos同步的时候，其成员组是第i-k条日志包含的成员组(每条日志里面都包含成员组)。

multi-paxos协议之外
multi-paxos只是保证大家对日志达成一致。但是具体multi-paxos运用到真实的系统中时，从应用层面上看，可能会出现一些诡异的问题。考虑如下场景：

如图，1号主写了A,B,C,D,其中B,C,D没有形成多数派，然后A宕机了，2号被选为了主，客户端过来读不到B,C,D，然后B没写任何东西，就挂了，这个时候，A起来后重新被选为主，对B,C,D重新运行paxos，把B,C,D达成了一致，这个时候客户端再次过来读，又能读到B,C,D了。对于multi-paxos本身来说，并没有什么不对的地方，但是上层应用的语义出现了问题：曾经读不到的东西，什么都没做，又能读到了。

解决这个问题的方法是通过主提供服务之前必须成功写入一条start working日志来解决。如下图：

如图，每个成员成为主提供服务之前都要首先写一条start working日志，只有达成多数派才能提供服务。1号在重新成为主之后，通过对log id=2的日志运行paxos，将2号start日志恢复了出来，然后对C和D运行paxos恢复出来后，后续回放的时候，如果发现后面日志中带有的timestamp(其实时leader上任时间)比start working带有的timestamp更小，那么就不回放到上层。随后客户端来读仍然读不到B,C,D，前后保持一致。

1.CAP原理
要想数据高可用，就得写多份数据

写多分数据就会导致数据一致性问题

数据一致性问题会引起性能问题

2.一致性模型
弱一致性

最终一致性（一段时间达到一致性）

强一致

1、2 异步冗余；3是同步冗余

扩展服务的方案
数据分区： uid % 16

数据镜像：让多有的服务器都有相同的数据，提供相当的服务（冗余存储，一般3份为好）

4.两种方案的事务问题
A向B汇钱，两个用户不在一个服务器上

镜像：在不同的服务器上对同一数据的写操作如何保证一致性。

解决一致性事务问题的技术

Master -Slave
读写请求由Master负责

写请求写到Master后，由Master同步到Slave上

由Master push or Slave pull

通常是由Slave 周期性来pull，所以是最终一致性

问题：若在 pull 周期内（不是期间？），master挂掉，那么会导致这个时间片内的数据丢失

若不想让数据丢掉，Slave 只能成为 ReadOnly方式等Master恢复

若容忍数据丢失，可以让 Slave代替Master工作

如何保证强一致性？

Master 写操作，写完成功后，再写 Slave，两者成功后返回成功。若 Slave失败，两种方法

标记 Slave 不可用报错，并继续服务（等恢复后，再同步Master的数据，多个Slave少了一个而已）

回滚自己并返回失败

Master-Master
数据同步一般是通过 Master 间的异步完成，所以是最终一致

好处：一台Master挂掉，另外一台照样可以提供读写服务。当数据没有被赋值到别的Master上时，数据会丢失。

对同一数据的处理问题：Dynamo的Vector Clock的设计（记录数据的版本号和修改者），当数据发生冲突时，要开发者自己来处理

3.两阶段提交 Two Phase Commit _ 2PC
第一阶段：针对准备工作

协调者问所有节点是否可以执行提交

参与者开始事务，执行准备工作：锁定资源（获取锁操作）

参与者响应协调者，如果事务的准备工作成功，则回应”可以提交”，否则，拒绝提交

第二阶段：

若都响应可以提交，则协调者项多有参与者发送正式提交的命令（更新值），参与者完成正式提交，释放资源，回应完成。协调者收到所有节点的完成响应后结束这个全局事务.。若参与者回应拒绝提交，则协调者向所有的参与者发送回滚操作，并释放资源，当收到全部节点的回滚回应后，取消全局事务

存在的问题：若一个没提交，就会进行回滚

第一阶段：若消息的传递未接收到，则需要协调者作超时处理，要么当做失败，要么重载

第二阶段：若参与者的回应超时，要么重试，要么把那个参与者即为问题节点，提出整个集群

在第二阶段中，参与者未收到协调者的指示（也许协调者挂掉），则所有参与者会进入“不知所措” 的状态（但是已经锁定了资源），所以引入了三段提交

三段提交：把二段提交的第一阶段 break 成了两段
询问

锁定资源（获取锁）

提交

核心理念：在询问的时候并不锁定资源，除非所有人都同意了，才开始锁定

好处：当发生了失败或超时时，三段提交可以继续把状态变为Commit 状态，而二段提交则不知所措？

Raxos 算法（少数服从多数）
解决的问题：在一个可能发生异常的分布式系统中如何就某个值达成一致，让整个集群的节点对某个值的变更达成一致

任何一个节点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数的节点同意（所以节点数总是单数）—— 版本标记。虽然一致性，但是只能对一个操作进行操作啊？？

当一个Server接收到比当前版本号小的提案时，则拒绝。当收到比当前大的版本号的提案时，则锁定资源，进行修改，返回OK. 也就是说收到超过一半的最大版本的提案才算成功。

核心思想：

在抢占式访问权的基础上引入多个acceptor，也就是说当一个版本号更大的提案可以剥夺版本号已经获取的锁。

后者认同前者的原则：

在肯定旧epoch 无法生成确定性取值时，新的 epoch 会提交自己的valu

一旦旧epoch形成确定性取值，新的 epoch肯定可以获取到此取值，并且会认同此取值，不会被破坏。

步骤

P1 请求Acceptor的 #1,Acceptor 这时并没有其他线程获取到锁，所以把锁交给 P1，并返回这时 #1 的值为null

然后 P1 向第一个 Acceptor 提交 #1 的值，Acceptor 接受并返回 OK

这个时候，P2向Acceptor请求#1上的锁，因为版本号更大，所以直接抢占了 P1 的锁。这时 Acceptor 返回了 OK并且返回了 #1 的值

这时 P1 P向后面两个 Acceptor 提交 #1 的值，但是由于中间的那个Acceptor 版本号已经更改为 2 了，所以拒绝P1。第三个 Acceptor 接受了，并且返回了 OK

由于后者认同前者的原则，这时 P1 已经形成确定性取值了 V1 了，这时新的 P2 会认同此取值，而不是提交自己的取值。所以，P2会选择最新的那个取值也就是V1 进行提交。这时Acceptor 返回 OK

6.ZAB 协议 ( Zookeeper Atomic Broadcast) 原子广播协议：保证了发给各副本的消息顺序相同
定义：原子广播协议 ZAB 是一致性协议，Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的。Zookeeper 使用单一主进程 Leader用于处理客户端所有事务请求，采用 ZAB 协议将服务器状态以事务形式广播到所有 Follower 上，由于事务间可能存在着依赖关系，ZAB协议保证 Leader 广播的变更序列被顺序的处理，一个状态被处理那么它所依赖的状态也已经提前被处理

核心思想：保证任意时刻只有一个节点是Leader，所有更新事务由Leader发起去更新所有副本 Follower，更新时用的是两段提交协议，只要多数节点 prepare 成功，就通知他们commit。各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务

协议状态

Looking:系统刚启动时或者 Leader 崩溃后正处于选举状态

Following：Follower 节点所处的状态，Follower与 Leader处于数据同步状态

Leading：Leader 所处状态，当前集群中有一个 Leader 为主进程

ZooKeeper启动时所有节点初始状态为Looking，这时集群会尝试选举出一个Leader节点，选举出的Leader节点切换为Leading状态；当节点发现集群中已经选举出Leader则该节点会切换到Following状态，然后和Leader节点保持同步；当Follower节点与Leader失去联系时Follower节点则会切换到Looking状态，开始新一轮选举；在ZooKeeper的整个生命周期中每个节点都会在Looking、Following、Leading状态间不断转换。

选举出Leader节点后 ZAB 进入原子广播阶段，这时Leader为和自己同步每个节点 Follower 创建一个操作序列，一个时期一个 Follower 只能和一个Leader保持同步

阶段

Election：在 Looking状态中选举出 Leader节点，Leader的LastZXID总是最新的（只有lastZXID的节点才有资格成为Leade,这种情况下选举出来的Leader总有最新的事务日志）。在选举的过程中会对每个Follower节点的ZXID进行对比只有highestZXID的Follower才可能当选Leader

每个Follower都向其他节点发送选自身为Leader的Vote投票请求，等待回复；

Follower接受到的Vote如果比自身的大（ZXID更新）时则投票，并更新自身的Vote，否则拒绝投票；

每个Follower中维护着一个投票记录表，当某个节点收到过半的投票时，结束投票并把该Follower选为Leader，投票结束；

Discovery:Follower 节点向准 Leader推送 FollwerInfo,该信息包含了上一周期的epoch，接受准 Leader 的 NEWLEADER 指令

Sync：将 Follower 与 Leader的数据进行同步，由Leader发起同步指令，最终保持数据的一致性

Broadcast：Leader广播 Proposal 与 Commit，Follower 接受 Proposal 与 commit。因为一个时刻只有一个Leader节点，若是更新请求，只能由Leader节点执行（若连到的是 Follower 节点，则需转发到Leader节点执行；读请求可以从Follower 上读取，若是要最新的数据，则还是需要在 Leader上读取）

消息广播使用了TCP协议进行通讯所有保证了接受和发送事务的顺序性。广播消息时Leader节点为每个事务Proposal分配一个全局递增的ZXID（事务ID），每个事务Proposal都按照ZXID顺序来处理（Paxos 保证不了）

Leader节点为每一个Follower节点分配一个队列按事务ZXID顺序放入到队列中，且根据队列的规则FIFO来进行事务的发送。

Recovery ：根据Leader的事务日志对Follower 节点数据进行同步更新

同步策略：

SNAP ：如果Follower数据太老，Leader将发送快照SNAP指令给Follower同步数据；

DIFF ：Leader发送从Follolwer.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据；

TRUNC ：当Follower.lastZXID比Leader.lastZXID大时，Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据；（当老Leader在Commit前挂掉，但是已提交到本地）

Follower将所有事务都同步完成后Leader会把该节点添加到可用Follower列表中；

Follower接收Leader的NEWLEADER指令，如果该指令中epoch比当前Follower的epoch小那么Follower转到Election阶段

Raft 算法
Raft 算法也是一种少数服从多数的算法，在任何时候一个服务器可以扮演以下角色之一：

Leader：负责 Client 交互和 log 复制，同一时刻系统中最多存在一个

Follower：被动响应请求 RPC，从不主动发起请求 RPC

Candidate : 由Follower 向Leader转换的中间状态

在选举Leader的过程中，是有时间限制的，raft 将时间分为一个个 Term，可以认为是“逻辑时间”：

每个 Term中至多存在1个 Leader

某些 Term由于不止一个得到的票数一样，就会选举失败，不存在Leader。则会出现 Split Vote ，再由候选者发出邀票

每个 Server 本地维护 currentTerm

选举过程：

自增 CurrentTerm，由Follower 转换为 Candidate，设置 votedFor 为自身，并行发起 RequestVote RPC,不断重试，直至满足下列条件之一为止：

获得超过半数的Server的投票，转换为 Leader，广播 HeatBeat

接收到合法 Leader 的 AppendEnties RPC，转换为Follower

选举超时，没有 Server选举成功，自增 currentTerm ,重新选举

当Candidate 在等待投票结果的过程中，可能会接收到来自其他Leader的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term，则认可该Leader身份的合法性，主动降级为Follower，反之，则维持 candida 身份继续等待投票结果

Candidate 既没有选举成功，也没有收到其他 Leader 的 RPC (多个节点同时发起选举，最终每个 Candidate都将超时)，为了减少冲突，采取随机退让策略，每个 Candidate 重启选举定时器

日志更新问题：

如果在日志复制过程中，发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwers了，那么Leader只能正常更新它能访问的那些Follower服务器，而大多数的服务器Follower因为没有了Leader，他们重新选举一个候选者作为Leader，然后这个Leader作为代表于外界打交道，如果外界要求其添加新的日志，这个新的Leader就按上述步骤通知大多数Followers，如果这时网络故障修复了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新。

流程：

Client 发送command 命令给 Leader

Leader追加日志项，等待 commit 更新本地状态机，最终响应 Client

若 Client超时，则不断重试，直到收到响应为止（重发 command，可能被执行多次，在被执行但是由于网络通信问题未收到响应）

解决办法：Client 赋予每个 Command唯一标识，Leader在接收 command 之前首先检查本地log

paxos 算法与 raft 算法的差异
raft强调是唯一leader的协议，此leader至高无上

raft：新选举出来的leader拥有全部提交的日志，而 paxos 需要额外的流程从其他节点获取已经被提交的日志，它允许日志有空洞

相同点：得到大多数的赞成，这个 entries 就会定下来，最终所有节点都会赞成

NWR模型
N： N个备份

W：要写入至少 w 份才认为成功

R : 至少读取 R 个备份

W+ R > N ——> R > N - W(未更新成功的) ，代表每次读取，都至少读取到一个最新的版本（更新成功的），从而不会读到一份旧数据

问题：并非强一致性，会出现一些节点上的数据并不是最新版本，但却进行了最新的操作

版本冲突问题：矢量钟 Vector Clock ：谁更新的我，我的版本号是什么（对于同一个操作者的同一操作，版本号递增）

参考资料：

http://www.tuicool.com/articles/IfQR3u3

http://blog.csdn.net/chen77716/article/details/7309915

http://www.infoq.com/cn/articles/distributed-system-transaction-processing/

http://www.jdon.com/artichect/raft.html

http://blog.csdn.net/cszhouwei/article/details/38374603

Category spark