Paxos算法是由xhdsp Lamport在1989年提出的分布式共识算法。 Paxos算法很难理解。 本文试图用图形的方法说明Paxos算法。
本文在很大程度上参考了勇敢的狼极客时间课《分布式协议与算法》。 有兴趣了解踏实鸽子其他课程的同学可以购买学习。
Lamport提出的Paxos算法有两个部分。
基本Pax操作系统算法：多节点如何达成某个值的共识多操作系统思想：运行多个基本Pax操作系统并达成一系列值的共识的基本Pax操作系统问题是，一个集群中有三个节点a、b、c 只读key-value意味着在创建key时，该值是固定的，以后不能更改。
客户端1和客户端2试图同时创建x密钥。 客户机1为“leehao.me”创建值x，客户机2为“www.leehao.me”创建值x。 在这种情况下，群集如何达成共识，以实现每个节点上的x值匹配？
关于Paxos的概念Paxos算法中，有提议者(Proposer )、接受者)、学习者) 3个作用，它们的关系如下。
提议用于提案者(Proposer )投票的值，可以将上图中的客户机1和客户机2视为提案者。 实际上，提案者多为集群内的节点，但这里为了便于演示，将客户机1和2视为提案者，不影响Paxos算法的实质接收者(Acceptor )对每个提案的值进行投票。 例如，上图的集群内的节点a、b、c的学习者) Learner )，被通知投票的结果并被接受
Paxos算法使用提案表示包含建议编号和建议值的建议。 接下来，使用[n，v]表示提案。 其中，n是提案编号，v是提案的值。
在Basic Paxos中，集群内的各节点为了达成共识，需要准备(Prepare )阶段和接受(Accept )阶段这两个阶段的协商。
准备阶段中，设客户机1的提案编号为1，客户机2的提案编号为5，假设节点a、b先接受来自客户机1的准备请求，节点c先接受来自客户机2的准备请求。
客户端作为提案者，向所有接收者发送包含提案号码的准备请求。 请注意，在准备阶段，不需要为请求指定建议的值，而只需包括建议编号。
接下来，节点a、b接收客户机1的准备请求(提案编号1 )，节点c接收客户机2的准备请求(提案编号5 )。
集群中的每个节点接收到第一个准备请求的过程：
节点a、b :由于到目前为止还没有通过任何提案，所以节点a、b回复“还没有提案”的准备应答，承诺以后不应答提案号码在1以下的准备请求，保证不通过号码小于1的提案节点c :到目前为止没有通过任何提案节点c回复“还没有提议”准备应答，并约定以后不应答提议号5以下的准备请求，在提议号5以下的提议中，接下来，节点a、b接收提议号5的准备请求，节点c接收提议号1的准备请求。
节点a、b :由于提案编号5大于以前响应过的准备请求的提案编号1，且节点a、b都没有提出任何提案，所以回复“还没有提出”，约定今后不响应提案编号5以下的准备请求， 未满5号的提案节点c :节点c因为提案编号1没有收到节点c之前应答的准备请求的提案编号5，所以放弃该准备请求，在接受阶段basic没有应答的客户机1、2在从大部分节点收到准备应答后，接受请求的
客户机1 :客户机1收到很多接收者(节点a、b )的准备应答时，根据应答中的提案号码最大的提案的值，设定接受请求的值。 节点a、b都返回“还没有提案”即提案值为空，所以客户机1将自己的提案值“leehao.me”作为提案的值，发送受理要求[1，' leehao.me']客户机2 :客户机基于应答中的提案编号最大的提案的值，设定受理请求的值的节点a、b、c都返回“还没有提案”，也就是说由于提案值为空，客户机2将自身的提案值' www.leehao.me '作为提案的值
节点a、b、c收到受理要求[1，' leehao.me']，由于提案编号1小于3个节点可以承诺并通过的最小提案编号5，所以提案[1，' leehao.me']被拒绝的节点a、b、c
节点承诺可以通过的最小提案编号 5 ，所以通过提案 [5, "www.leehao.me"]，即三个节点达成共识，接受 X 的值为 "www.leehao.me"如果集群中还有学习者，当接受者通过一个提案，就通知学习者，当学习者发现大多数接受者都通过了某个提案，那么学习者也通过该提案，接受提案的值。
接受者存在已通过提案的情况上面例子中，准备阶段和接受阶段均不存在接受者已经通过提案的情况。这里继续使用上面的例子，不过假设节点 A, B 已通过提案 [5, "www.leehao.me"]，节点 C 未通过任何提案。
增加一个新的提议者客户端 3，客户端 3 的提案为 [9，"leehao"] 。
接下来，客户端 3 执行准备阶段和接受阶段。
客户端 3 向节点 A, B, C 发送提案编号为 9 的准备请求：
节点 A, B 接收到客户端 3 的准备请求，由于节点 A, B 已通过提案 [5, "www.leehao.me"]，故在准备响应中，包含此提案信息。
节点 C 接收到客户端 3 的准备请求，由于节点 C 未通过任何提案，故节点 C 将返回“尚无提案”的准备响应。
客户端 3 接收到节点 A, B, C 的准备响应后，向节点 A, B, C 发送接受请求。这里需要特点指出，客户端 3 会根据响应中的提案编号最大的提案的值，设置接受请求的值。由于在准备响应中，已包含提案 [5, "www.leehao.me"]，故客户端 3 将接受请求的提案编号设置为 9，提案值设置为 "www.leehao.me" 即接受请求的提案为 [9, "www.leehao.me"]：
节点 A, B, C 接收到客户端 3 的接受请求，由于提案编号 9 不小于三个节点承诺可以通过的最小提案编号，故均通过提案 [9, www.leehao.me]。
概括来说，Basic Paxos 具有以下特点：
Basic Paxos 通过二阶段方式来达成共识，即准备阶段和接受阶段Basic Paxos 除了达成共识功能，还实现了容错，在少于一半节点出现故障时，集群也能工作提案编号大小代表优先级。对于提案编号，接受者提供三个承诺： 如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者承诺不响应这个准备请求如果接受请求中的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者承诺不通过这个提案如果按受者已通过提案，那些接受者承诺会在准备请求的响应中，包含已经通过的最大编号的提案信息 Multi PaxosBasic Paxos 算法只能对单个值达成共识，对于多个值的情形，Basic Paxos 算法就不管用了。因此，Basic Paxos 算法几乎只是用来理论研究，并不直接应用在实际工作中。
Lamport 提出的 Multi Paxos 是一种思想，并不是算法。
Multi Paxos 算法则是一个统称，是指基于 Multi Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（例如 Raft 算法等）。
如果直接通过多次执行 Basic Paxos 实例方式，来实现一系列值的共识，存在以下问题：
如果集群中多个提议者同时在准备阶段提交提案，可能会出现没有提议者接收到大多数准备响应，导致需要重新提交准备请求。例如，在一个 5 个节点的集群中，有 3 个节点同时作为提议者同时提交提案，那就会出现没有一个提议者获取大多数的准备响应，而需要重新提交为了达成一个值的共识，需要进行 2 轮 RPC 通讯，分别是准备阶段和接受阶段，性能低下为了解决以上问题，Multi Paxos 引入了领导者（Leader）和优化了 Basic Paxos 的执行过程。
领导者上面的问题一存在多个提议者同时提交准备请求的情况，如果引入了领导者，由领导者作为唯一的提议者，就可以解决问题一中的冲突的问题。
Lamport 没有说明如何选举领导者，需要在实现 Multi Paxos 算法的时候自行实现。这里我们略去如何选举领导者的算法，假设已经选举出领导者。
优化 Basic Paxos 执行过程准备阶段的意义，是发现接受者节点上已通过的提案的值。引入领导者后，只有领导者才可发送提议，因此，领导者的提案就已经是最新的了，不再需要通过准备阶段来发现之前被大多数节点通过的提案，领导者可以独立指定提议的值。
这样一来，准备阶段存在就没有意义了，领导者可以直接跳过准备阶段，直接进行接受阶段，减少了 RPC 通讯次数。
Chubby 的 Multi Paxos 实现Google 分布式锁 Chubby 实现了 Multi Paxos 算法。Chubby 的 Multi Paxos 算法主要包括：
Chubby 引入主节点作为领导者，即主节点作为唯一提议者，不存在多个提议者同时提交提案的情况，也不存在提案冲突的情况。Chubby 通过执行 Basic Paxos 算法进行投票选举产生主节点在 Chubby 中，由于引入了主节点，因此，也去除了 Basic Paxos 的准备阶段在 Chubby 中，为实现强一致性，所有的读请求和写请求都由主节点来处理 Chubby 所有的写请求由主节点来处理当主节点接收到客户端的写请求，作为提议者，将数据发送给所有节点，在大多数服务器接受了这个写请求后，给客户端响应写成功。
Chubby 所有的读请求由主节点来处理当主节点接收到读请求，主节点只需要查询本地数据，然后返回给客户端。
另外，需要指出的是，Basic Paxos 是经过证明的算法。Multi Paxos 是一种思想但缺乏实现算法所需的编程细节，因此，Multi Paxos 的算法实现，是建立在一个未经证明的基础之上。实现 Multi Paxos 算法，最大的挑战是如何证明它是正确的。
参考资料 https://time.geekbang.org/column/article/201700https://blog.the-pans.com/paxos-explained/https://zhuanlan.zhihu.com/p/31780743https://www.cnblogs.com/linbingdong/p/6253479.htmlhttps://www.ux.uis.no/~meling/papers/2013-paxostutorial-opodis.pdfhttps://medium.com/@nevverlander/paxos-made-simple-for-real-aa221be7d91bhttp://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdfhttps://lamport.azurewebsites.net/pubs/lamport-paxos.pdfhttps://lamport.azurewebsites.net/pubs/paxos-simple.pdf