Why Not Paxos
Paxos算法是莱斯利·兰伯特（LeslieLamport，就是&LaTeX&中的”La”，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后1998年重新发表到ACM Transactions on Computer Systems上（）。即便如此paxos算法还是没有得到重视，2001年Lamport 觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍（）。可见Lamport对Paxos算法情有独钟。近几年Paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。2006年Google的三篇论文初现“云”的端倪，其中的Chubby
Lock服务使用Paxos作为Chubby Cell中的一致性算法，Paxos的人气从此一路狂飙。Lamport 本人在 描写了他用9年时间发表这个算法的前前后后。
“There is only one consensus protocol, and that’sPaxos-all other approaches are just broken versions of Paxos.” –Chubby authors
“The dirtylittle secret of the NSDI community is that at most five people really, trulyunderstand every part of P-).”&–NSDI reviewer
Notes：回想当年，我不知翻阅了多少资料，才勉强弄明白“Basic Paxos”，由于缺乏实践体会，至今对于“Multi-Paxos”仍如云里雾里，不得要领。反观本文的主角Raft，《》，从它设计之初，作者就将Understandable作为最高准则，这在诸多决策选择时均有体现。
分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免地会发生以下错误：进程可能会慢、垮、重启，消息可能会延迟、丢失、重复（不考虑“”）。
一个典型的场景是：在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么它们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个「一致性算法」以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。从20世纪80年代起对于一致性算法的研究就没有停止过。
图 1Replicated State Machine Architecture
Raft算法将这类问题抽象为“ReplicatedState Machine”，详见上图，每台Server保存用户命令的日志，供本地状态机顺序执行。显而易见，为了保证“Replicated State Machine”的一致性，我们只需要保证“ReplicatedLog”的一致性。
通常来说，在分布式环境下，可以通过两种手段达成一致：
1.&&&&&& Symmetric, leader-less
所有Server都是对等的，Client可以和任意Server进行交互
2.&&&&&& Asymmetric, leader-based
任意时刻，有且仅有1台Server拥有决策权，Client仅和该Leader交互
“Designing for understandability”的Raft算法采用后者，基于以下考虑：
1.&&&&&&&问题分解：Normaloperation & Leader changes
2.&&&&&&&简化操作：Noconflicts in normal operation
3.&&&&&&&更加高效：Moreefficient than leader-less approaches
Server States
Raft算法将Server划分为3种角色：
1.&&&&&& Leader
负责Client交互和log复制，同一时刻系统中最多存在1个
2.&&&&&& Follower
被动响应请求RPC，从不主动发起请求RPC
3.&&&&&& Candidate
由Follower向Leader转换的中间状态
图 2Server States
众所周知，在分布式环境中，“时间同步”本身是一个很大的难题，但是为了识别“过期信息”，时间信息又是必不可少的。Raft为了解决这个问题，将时间切分为一个个的Term，可以认为是一种“逻辑时间”。如下图所示：
1.&&&&&&&每个Term至多存在1个Leader
2.&&&&&&&某些Term由于选举失败，不存在Leader
3.&&&&&&&每个Server本地维护currentTerm
Heartbeats and Timeouts
1.&&&&&&&所有的Server均以Follower角色启动，并启动选举定时器
2.&&&&&&&Follower期望从Leader或者Candidate接收RPC
3.&&&&&&&Leader必须广播Heartbeat重置Follower的选举定时器
4.&&&&&&&如果Follower选举定时器超时，则假定Leader已经crash，发起选举
Leader election
自增currentTerm，由Follower转换为Candidate，设置votedFor为自身，并行发起RequestVote RPC，不断重试，直至满足以下任一条件：
1.&&&&&&&获得超过半数Server的投票，转换为Leader，广播Heartbeat
2.&&&&&&&接收到合法Leader的AppendEntries RPC，转换为Follower
3.&&&&&&&选举超时，没有Server选举成功，自增currentTerm，重新选举
细节补充：
1.&&&&&&&Candidate在等待投票结果的过程中，可能会接收到来自其它Leader的AppendEntries RPC。如果该Leader的Term不小于本地的currentTerm，则认可该Leader身份的合法性，主动降级为Follower；反之，则维持Candidate身份，继续等待投票结果
2.&&&&&&&Candidate既没有选举成功，也没有收到其它Leader的RPC，这种情况一般出现在多个节点同时发起选举（如图Split Vote），最终每个Candidate都将超时。为了减少冲突，这里采取“随机退让”策略，每个Candidate重启选举定时器（随机值），大大降低了冲突概率
Log replication
图 4Log Structure
正常操作流程：
1.&&&&&&&Client发送command给Leader
2.&&&&&&&Leader追加command至本地log
3.&&&&&&&Leader广播AppendEntriesRPC至Follower
4.&&&&&&&一旦日志项committed成功：
1)&&&&&Leader应用对应的command至本地StateMachine，并返回结果至Client
2)&&&&&Leader通过后续AppendEntriesRPC将committed日志项通知到Follower
3)&&&&&Follower收到committed日志项后，将其应用至本地StateMachine
为了保证整个过程的正确性，Raft算法保证以下属性时刻为真：
1.&&&&&& Election Safety
在任意指定Term内，最多选举出一个Leader
2.&&&&&& Leader Append-Only
Leader从不“重写”或者“删除”本地Log，仅仅“追加”本地Log
3.&&&&&& Log Matching
如果两个节点上的日志项拥有相同的Index和Term，那么这两个节点[0, Index]范围内的Log完全一致
4.&&&&&& Leader Completeness
如果某个日志项在某个Term被commit，那么后续任意Term的Leader均拥有该日志项
5.&&&&&& State Machine Safety
一旦某个server将某个日志项应用于本地状态机，以后所有server对于该偏移都将应用相同日志项
直观解释：
为了便于大家理解Raft算法的正确性，这里对于上述性质进行一些非严格证明。
“ElectionSafety”：反证法，假设某个Term同时选举产生两个LeaderA和LeaderB，根据选举过程定义，A和B必须同时获得超过半数节点的投票，至少存在节点N同时给予A和B投票，矛盾
LeaderAppend-Only： Raft算法中Leader权威至高无上，当Follower和Leader产生分歧的时候，永远是Leader去覆盖修正Follower
LogMatching：分两步走，首先证明具有相同Index和Term的日志项相同，然后证明所有之前的日志项均相同。第一步比较显然，由Election Safety直接可得。第二步的证明借助归纳法，初始状态，所有节点均空，显然满足，后续每次AppendEntries RPC调用，Leader将包含上一个日志项的Index和Term，如果Follower校验发现不一致，则拒绝该AppendEntries请求，进入修复过程，因此每次AppendEntries调用成功，Leader可以确信Follower已经追上当前更新
LeaderCompleteness：为了满足该性质，Raft还引入了一些额外限制，比如，Candidate的RequestVote RPC请求携带本地日志信息，若Follower发现自己“更完整”，则拒绝该Candidate。所谓“更完整”，是指本地Term更大或者Term一致但是Index更大。有了这个限制，我们就可以利用反证法证明该性质了。假设在TermX成功commit某日志项，考虑最小的TermY不包含该日志项且满足Y&X，那么必然存在某个节点N既从LeaderX处接受了该日志项，同时投票同意了LeaderY的选举，后续矛盾就不言而喻了
StateMachine Safety：由于LeaderCompleteness性质存在，该性质不言而喻
Cluster membership changes
在实际系统中，由于硬件故障、负载变化等因素，机器动态增减是不可避免的。最简单的做法是，运维人员将系统临时下线，修改配置，重新上线。但是这种做法存在两个缺点：
1.&&&&&&&系统临时不可用
2.&&&&&&&人为操作易出错
图 5Online Switch Directly
失败的尝试：通过运维工具广播系统配置变更，显然，在分布式环境下，所有节点不可能在同一时刻切换至最新配置。由上图不难看出，系统存在冲突的时间窗口，同时存在新旧两份Majority。
两阶段方案：为了避免冲突，Raft引入Joint中间配置，采取了两阶段方案。当Leader接收到配置切换命令（Cold-&Cnew）后，将Cold,new作为日志项进行正常的复制，任何Server一旦将新的配置项添加至本地日志，后续所有的决策必须基于最新的配置项（不管该配置项有没有commit），当Leader确认Cold,new成功commit后，使用相同的策略提交Cnew。系统中配置切换过程如下图所示，不难看出该方法杜绝了Cold和Cnew同时生效的冲突，保证了配置切换过程的一致性。
图 6Joint Consensus
Log compaction
随着系统的持续运行，操作日志不断膨胀，导致日志重放时间增长，最终将导致系统可用性的下降。快照（Snapshot）应该是用于“日志压缩”最常见的手段，Raft也不例外。具体做法如下图所示：
图 7S基于“快照”的日志压缩
与Raft其它操作Leader-Based不同，snapshot是由各个节点独立生成的。除了日志压缩这一个作用之外，snapshot还可以用于同步状态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成该过程，不再赘述。
Client interaction
典型的用户交互流程：
1.&&&&&&&Client发送command给Leader
&&&&&&&&&&& 若Leader未知，挑选任意节点，若该节点非Leader，则重定向至Leader
2.&&&&&&&Leader追加日志项，等待commit，更新本地状态机，最终响应Client
3.&&&&&&&若Client超时，则不断重试，直至收到响应为止
细心的读者可能已经发现这里存在漏洞：Leader在响应Client之前crash，如果Client简单重试，可能会导致command被执行多次。
Raft给出的方案：Client赋予每个command唯一标识，Leader在接收command之前首先检查本地log，若标识已存在，则直接响应。如此，只要Client没有crash，可以做到“Exactly Once”的语义保证。
个人建议：尽量保证操作的“幂等性”，简化系统设计！
Raft算法虽然诞生不久，但是在业界已经引起广泛关注，强烈推荐大家浏览其官网，上面有丰富的学习资料，目前Raft算法的开源实现已经涵盖几乎所有主流语言（C/C++/Java/Python/Javascript …），其流行程度可见一斑。由此可见，一项技术能否在工业界大行其道，有时“可理解性”、“可实现性”才是至关重要的。
timyang在《》一文中，列举了一些Paxos常用的应用场合：
1.&&&&&&&Database replication, logreplication …
2.&&&&&&&Naming service
3.&&&&&&&配置管理
4.&&&&&&&用户角色
5.&&&&&&&号码分配
Note：对于分布式锁、数据复制等场景，非常容易理解，但是对于“Naming Service”一类应用场景，具体如何实操，仍然表示困惑。翻阅一些资料发现，借助Zookeeper的watch机制，当配置发生变更时可以实时通知注册客户端，但是如何保证该通知的可靠送达呢，系统中是否可能同时存在新旧两份配置？烦请有相关经验的高人私下交流~
本文已收录于以下专栏：
相关文章推荐
数据库高可用性难题
数据库的数据一致和持续可用对电子商务和互联网金融的意义不言而喻，而这些业务在使用数据库时，无论 MySQL 还是 Oracle，都会面临一个艰难的取舍，就是如何处理主备库之间的数...
superset 介绍:Superset是一个旨在视觉，直观和互动的数据探索平台。
说明：以下内容总结自网络
要想数据高可用，就得写多份数据
写多分数据就会导致数据一致性问题
数据一致性问题会引起性能问题
2.一致性模型
犹记得去年靠着微信后台的强势宣传，coroutine在我司的C/C++后台界着实火了一把，当时我也顺势对中心的后台网络框架做了coroutine化改造，详见《当C/C++后台开发遇上Coroutine...
What is the difference between Buffers and Cached columns in /proc/meminfo output?
分布式一致性协议Raft原理与实例1.Raft协议1.1 Raft简介Raft是由Stanford提出的一种更易理解的一致性算法，意在取代目前广为使用的Paxos算法。目前，在各种主流语言中都有了一些...
本篇博客为著名的 RAFT 一致性算法论文的中文翻译，论文名为《In search of
an Understandable Consensus Algorithm (Extended Versi...
LT的编程与poll/select接近，符合一直以来的习惯，不易出错
ET的编程可以做到更加简洁，某些场景下更加高效，但另一方面容易遗漏事件，容易产生bug
一日，诸葛亮找到刘备，突然献上一曲《独角戏》，而后放声大哭。刘备正沉醉于新曲，暗叹孔明大才，竟作得如此不凡仙乐，看到孔明忽而大悲，慌问：“水，何事悲恸？”
诸葛亮止住抽泣：“亮自主...
他的最新文章
讲师：王哲涵
讲师：韦玮
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)如何浅显易懂地解说 Paxos 的算法？ - 知乎1956被浏览150799分享邀请回答29584 条评论分享收藏感谢收起13930 条评论分享收藏感谢收起查看更多回答
作者：朱一聪
链接：/question//answer/
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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算法，关于这个原理更具体的阐述可以看看我在下的回答。所以确实在一定程度上可以视raft,ZAB,VR都是paxos算法的一种改进，一种简化，一种优化，一种具象化。Lamport老人家还是叼叼叼。。。。。。。不过值得一提的是，ZAB和raft作者确实是受了paxos很多启发，VR是几乎同时独立于paxos提出的。
Raft容易实现在于它的描述是非常规范的，包括了所有的实现细节。如上面的人说的有如伪代码。而paxos的描述侧重于理论，工程实现按照谷歌chubby论文中的说话，大家从paxos出现，写着写着，处理了n多实际中的细节之后，已经变成另外一个算法了，这时候正确性已经无法得到理论的保证。所以它的实现非常难，因为一致性协议实非常精妙的。小细节上没考虑好，整个协议的一致性就崩溃了，而发现并更正细节上的错误在没有详尽的现成的参考的情况下是困难的，这需要对协议很深的理解。而且在Raft协议的博士论文CONSENSUS:
BRIDGING THEORY AND PRACTICE，两位作者手把手事无巨细的教你如何用raft协议构建一个复制状态机。我表示智商正常的大学生，都能看懂。我相信在未来一致性现在被提起来，肯定不是现在这样，大部分人觉得好难啊，实现更难。。。。应该会成为一种常用技术。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4060次
排名：千里之外
原创：10篇
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'2665人阅读
分布式系统（60）
数据库高可用性难题
数据库的数据一致和持续可用对电子商务和互联网金融的意义不言而喻，而这些业务在使用数据库时，无论 MySQL 还是 Oracle，都会面临一个艰难的取舍，就是如何处理主备库之间的数据同步。对于传统的主备模式或者一主多备模式，我们都需要考虑的问题，就是与备机保持强同步还是异步复制。
对于强同步模式，要求主机必须把 Redolog 同步到备机之后，才能应答客户端，一旦主备之间出现网络抖动，或者备机宕机，则主机无法继续提供服务，这种模式实现了数据的强一致，但是牺牲了服务的可用性，且由于跨机房同步延迟过大使得跨机房的主备模式也变得不实用。
而对于异步复制模式，主机写本地成功后，就可以立即应答客户端，无需等待备机应答，这样一旦主机宕机无法启动，少量不同步的日志将丢失，这种模式实现了服务持续可用，但是牺牲了数据一致性。这两种方式对应的就是 Oracle 的 Max Protection 和 Max Performance 模式，而 Oracle 另一个最常用的 Max Availability
模式，则是一个折中，在备机无应答时退化为 Max Performance 模式，我认为本质上还是异步复制。
主备模式还有一个无法绕过的问题，就是选主，最简单山寨的办法，搞一个单点，定时 Select 一下主机和各个备机，貌似 MHA 就是这个原理，具体实现细节我就不太清楚了。一个改进的方案是使用类似 ZooKeeper 的多点服务替代单点，各个数据库机器上使用一个 Agent 与单点保持 Lease，主机 Lease 过期后，立即置为只读。改进的方案基本可以保证不会出现双主，而缺点是 ZooKeeper 的可维护性问题，以及多级 Lease 的恢复时长问题（这个本次就不展开讲了，感兴趣的同学请参考这篇文章 /
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 配置缓慢校准，最后平稳渡过。
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 都同步到一致。
能完成在全球同步的业务吗？理论上支持多少机器同步?
Paxos 成员组横跨全球的案例我还没有见过 Paper，我个人认为它并不适合全球不同，原因是延迟太大，但是 Google 的 Spanner 和 Amazon 的 Aurora 都实现了横跨北美多 IDC 的同步；理论上多少都行，你能接受延迟就可以。
3、问个问题，能否简单说说
Raft 算法和 Paxos 算法的异同？应用场的异同？
Raft 可以认为是一种简化的 Multi-Paxos 实现，他的最大简化之处在于备机接受 Leader 日志的前提是收到 LogID 连续的日志，在这个假设前提下，没有我文中提到的“幽灵复现”和“重确认”问题。简化带来的代价是对网络抖动的容忍度稍低一些，考虑这样的场景 ABC 三台机器，C 临时下线一会错过一些日志，然后 C上 线了，但是在 C 补全日志之前，AB
如果再宕机一台的话，服务就停了。
实现是独立的库或服务还是和具体的业务逻辑绑定，上线前如何验证 Paxos 算法实现的正确性？
OB 实现的 Paxos 是和事务 Redolog 库比较紧耦合的，没有独立的库；测试方案一个是
Monkey tests，随机模拟各种异常环境，包括断网、网络延迟、机器宕机、包重复到达等情况保持压力和异常；另外一个是做了一个简易的虚拟机，来解释测试 Case，通过人工构造多种极端的场景，来是系统立即进入一个“梦境”。
和 proposalid都应该是不能重复的，这个是如何保证的？原子钟的精确性仅仅是为了选主吗？
首先，Leader 任期内，Logid 只由 Leader 产生，没有重复性的问题；
第二，Leader 产生后，会执行 GetMaxLogID，从集群多数派拿到最大的 Logid，加以后作为本届任期内的 Logid 起点，这也可以保证有效日志 logid 不重复。Proposalid，高位使用 64 位时间戳，低位使用 IP 地址，可以保证唯一性和递增性。
Paxos 协议做 Master 和 Slave 一致性保证时，Paxos 日志回放应该怎样去做？
Master 形成多数派确认后，异步的写出“确认日志”，Slave 回放到确认日志之后，才能去回放收到的正常日志。因此一般情况下，备机总是要落后主机一点点的。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3355350次
积分：22241
积分：22241
排名：第340名
原创：40篇
转载：808篇
评论：234条
(1)(1)(5)(2)(2)(3)(3)(2)(2)(2)(1)(7)(3)(1)(1)(1)(2)(6)(24)(6)(6)(3)(24)(2)(2)(10)(13)(7)(20)(8)(21)(14)(34)(34)(34)(34)(54)(55)(55)(57)(57)(37)(37)(37)(17)(20)(48)(11)(2)(5)(10)(6)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'