例解Poxos算法
source link: https://fishermartyn.github.io/blog/Paxos/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
例解Poxos算法
By fisherMartyn 2016-12-13
PaxOS算法是分布式系统中最经典的算法之一，也是不得不谈及的问题，这个博客的目的并不是去讲解它的原理，甚至去证明；而是希望通过例子的方式来体现一些细节，提升对它的理解、甚至提升对于分布式本身的理解。
CAP原理 ： 一致性、可用性和分区容错性不可兼得。
FLP Impossibility ： 在异步通信的环境下，没有一个算法可以保证数据一致性。
Paxos算法（有人也叫Paxos协议），也无法完全解决异步通信环境下数据一致性的问题，而只是在可用性上做了权衡。
Paxos算法的地位极高：
all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.
所有目前存在的异步一致性协议，在核心上都是Paxos。
Paxos解决的问题 ： 分布式系统之间，如果就一个不可变的变量达成一致。
并且对于可用性，Paxos做了两点保证：
1.Liveness
只要存在多数派存活，而且多数派之间的网络是联通的，那么：
- 肯定就变量值达成一致
- 达成一致的值肯定可以被其他进程学习到
2. Safety
不会出错，只有一个值被确定，不会出现第二个值将其覆盖。
假设有三个进程 A, B, C，希望就变量V的值达成一致。
最直接的想法：
P1 ：集合中任一进程向其他进程提议V的值，提议被进程接收后，拒绝其他的值。
该解决方案的问题是：1、不允许任何进程故障；2、多个进程并发赋值的问题无法支持。因此我们可以针对此问题进行优化：
P2 ：集合中任一进程可以进行提议V的值，当提议被法定集合采纳，即可认为提议已经确定；当提议被接收后，进程会拒绝再次对V的提议。
该解决方案的问题是，无法支持多并发进程对V赋值的场景。我们尝试将拒绝对V的再次提议的限制条件开放。
P3 ：任一进程可以进行提议V的值，当提议被法定集合采纳，即可认为提议已经确定；当提议被进程接收后，进程仍然可以接收对V的提议。
该方案的问题主要是重复赋值的问题。例如A的进程希望赋值为i，B进程也采纳了该值；但同时C被赋值为j。按照多数派的规定，i的值已经获得了多数派的认可，这以意味着j的赋值应该受到限制。
提议前，进程询问下其他进程的建议值，如果建议为空，则提议自己定义的值；如果建议不为空，则提议出现次数最多的那个值
该方案出现了并发和时序的问题，假设很不幸的出现了A去B和C询问建议值，分别返回了i和j，这时候A就无法选择。可以引入时序变量epoch（你可以理解为一个全局id），例如A返回的是(epoch1 , i)，而B返回的是(epoch2, j)，这样就可以根据epoch的不同来进行一个选择即可。
这样所有的条件都已经具备了，至少包含几个信息：
- 依赖法定集合而不是全集
- 可以接受多次提议
- 至少两个阶段，询问和提议
再考虑下并发的情况：
假设两个进程同时向集合发起询问，返回的结果都是null，这个时候两个进程都提交了提案，而且值不同。这个时候如何处理呢？
两个法定集合必然存在一个公共子进程。这是法定集合存在的意义。只需要确定公共子集的行为，即可以达到一致。可以通过一条简单的规则：只接受epoch最大的提案，拒绝其它提案。
综上，我们隐约可以推导出一个Paxos的执行过程。
Paxos的执行过程
我们首先根据是否会提出提案，将进程分为Proposer和Acceptor。前者提出提案，后者接受提案并进行处理。
-
Proposer发送Propose
Proposer生成全局ID，并且向所有的机器发送Propose（不需要携带提案内容）。
-
Acceptor应答Propose
收到Propose后做出
两个承诺和一个应答两个承诺 : 不再应答Propose ID小于等于该请求的Propose；不再应答Propose小于该请求的Accept请求
一个应答：返回已经Accept过的提案中Propose ID最大的提案的的Value和Propose ID；如果没有则返回null。
-
Proposer发送Accept
提案生成规则：Proposer收到多数派的Propose请求后，从应答中选择存在提案，并且Propose ID最大的Value，作为本次Accept的提案。如果所有应答的Value均为空，则携带当前的Propose ID和新的值，向集群发送Accept请求。
-
应答Accept
Acceptor收到Accept请求后，在不违背
两个承诺的前提下，持久化当前的Propose ID和Value，形成决议。
一些不同的情况
说明：
S1 - S5 ：所有的进程集合。
X，Y：由进程提出的不同的议案的值。
黑框白底：成功的Propose和Accept。
黑框绿底：虽然Accept但没有在系统中达成一致的Accept。
上图中的S1提出了X并被多数派同意，S5在提出propose时获取到了X的值。
上图中的S1提出了X，但只被S3同意；S5在提出propose时恰好询问到了S3，并将X值更新给了S4和S5。
P1并没有被多数派Accept，同时也没有被P2学习到。P2可以Accept自己的Value Y；后续P1的Accept会失败、同时进行下一轮提案，最终也学习到了Value Y。
P1并没有被Accept的时候，P2提出，然后P3提出，然后P4提出……S3永远无法应答Accept请求。
这种情况称之为活锁。
Paxos的边界
两将军问题、FLP不可能性，这都说明分布式系统在故障发生时的通过算法实现一致性无法100%保证。
我们再来看Paxos的Liveness保证，注意，这里只是保证了“肯定就变量值达成一致”，而没解释具体的结束时间。这里引申出来活锁问题：
询问阶段：确定谁的编号更高，更高编号的才能proposal。 提交阶段：编号更高者提交的proposal如果没有其它节点提出的更高的Proposal，则可以通过；如果有，则从头重来。
试想如果不停有更高Proposal的产生，则算法永远无法结束。虽然Paxos在工程中应用广泛，但活锁是Paxos无法解决的硬伤。
有兴趣的话会继续研究下Multi-Paxos和Raft。
Recommend
-
161
漫画：什么是MD5算法？ Original...
-
201
程序员必备算法——排列组合 [TOC] 还记得排列组合吗？ 在高中的时候最常接触的莫过于排列组合了，毕竟高考必考的嘛。我们先来回忆下这两个的公式是啥： 排列组合公式 如果看到这个还有一丢丢的印象，说明大家的基础都还不错。那么问题来了，大家都是学计算机
-
129
This site can’t be reached down.51cto.com’s server IP address could not be found.
-
367
如何利用相对廉价的机器搭建分布式超大规模机器学习集群是一件非常复杂的事情，对工程和算法都有极高的要求，从Spark到李沐的通用参数服务器，业界对此都进行过哪些尝试？本文尝试梳理一下这方面的历史和当前最佳实践。
-
160
人民日报在三评王者荣耀后，最近今日头条也遭到了点名。批评的重点是以今日头条为代表的的算法推荐资讯平台，还提出了价值观缺失、制造信息茧房、竞争手段无底线的“三宗罪”。总的来说，人民日报提出的这些问题还是非常客观的。此前也有不少新...
-
100
2017-10-13 08:46算法驱动的资讯类平台为什么让人讨厌？在王者荣耀之后后，今日头条也遭到了人民日报的点名。批评的重点是以今日头条为代表的算法推荐资讯类平台，存在价值观缺失、制造信息茧房、竞争手段无底线的“三宗罪”...
-
119
0x00 前言标准的 Bloom Filter 是一种比较简单的数据结构，只支持插入和查找两种操作。在所要表达的集合是静态集合的时候，标准 Bloom Filter 可以很好地工作，但是如果要表达的集合经常变动，标准 Bloom Filter 的弊端就显现出来了，因为它不支持删除操作...
-
96
不要再问：“XX 岁，学习 XX，还来得及吗？”亡羊补牢，为时未晚。如果有心，什么都会来得及，只是需要付出更多的努力，只是看自己是否愿意！本文想和大家分享的是一位名为吴祖增的 84 岁技术人的故事，他
-
118
51CTO网+平台推出《态牛-TechNeo》电子杂志，通过精选和技术原创内容，精致的排版，给技术人员的阅读带来绝佳的体验。“读我懂你，做千万开发者的选择”是《态牛-TechNeo》的口号，本杂志面向广大开发者、技术总监以及架构师，杂志具涵盖独家的经验分享、案例剖析、...
-
3
依赖Kafka的Go单元测试例解
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK