如何通过目录basic Pax操作系统三个角色达成共识basic Pax操作系统总结多Pax操作系统阅读器优化basic Pax操作系统运行reference
Paxos算法包括以下两个部分：
1、Basic Paxos :说明多节点之间如何就某个值达成共识
2、Multi-Paxos :描述多个Basic Paxos实例的执行，并对一系列值达成共识
Basic Paxos的三种角色该算法存在三种角色：提议者，接受者，学习者，3http://ww.Sina.com /，关系
提议者:提议用于投票的值。 多数情况下，集群内接收到客户端请求的节点时，多为提案者。 这样就没有了对业务代码的入侵性，无需在业务代码中实现算法逻辑。
接受者:对提议的每个值进行投票，存储接受的值。 一般来说，群集中的所有节点都是接收者，他们参与共识协商，接收并存储数据
注意：节点可以起到多个作用，如下所示：
学习者:被告知投票结果，接收并保存达成协议的值，不参与投票过程。 一般来说，学习者是数据备份节点，如“Master - Slave”模型的Slave，被动接收数据并进行灾难恢复。
三个角色代表三种功能。
1、提案人代表接入和协调功能，在收到客户端请求后，开始二阶段提交，进行共识协商。 2、接受方代表协商和存储数据对建议的值进行投票，接受并保存商定的值。 3、学员为3358ww.Sinn
这里以2个客户端为提案者和3个节点为接受方，
希望客户机1节点的Key针对x数据将Value设置为3，而客户机2节点的Key针对x数据将Value设置为5。
提案者将发送给接收者的信息称为提案，结构为[n，v]，n为提案编号(相当于事务ID，后发的提案编号越大)，v为提案值)写入db的值
存储数据
在准备阶段，2个提案者分别向3个接收者发送包含提案号码的准备阶段，在准备请求中只包含提案号码。 假设接收者节点接收到准备请求的时序图如下。
接下来，接收方节点对之前接收到的准备请求的响应。 由于到目前为止还没有通过任何提案，a、b、c回复说“还没有提案”。
但是，a、b告诉提案者不回应提案号=1的准备要求，c告诉提案者不回应提案号=5的准备要求。
也就是说，每个节点接受大于当前建议号的请求。
然后，每个收件人第二次收到准备请求的响应。
A、B收到的请求，序号5=1，并且此时两个节点没有通过任何提案，所以回复“还没有提案”，不再响应提案序号=5的准备请求。
因为C收到的请求编号为15，所以丢弃该准备请求，以便不响应。
准备请求
2个提议者节点在收到接受阶段的准备应答后，分别发送大多数节点。
在客户机1中，根据应答中的提案编号最大的提案的值，设定受理请求中的值。 [客户机1只有来自a、b的准备应答]。 由于响应都是“尚未提出”的，所以客户机1将自身的接受请求:3作为提议值发送接收请求[n，v ] 3360 [ 1，3 ]
在客户机2中，根据响应中提案编号最大的提案的值，设定正在接受请求的值。 [客户机2是来自a、b、c的准备响应]，响应都是“尚未提议的”，因此客户机1将其自身的提案值:7接受为提议值
三个接收方节点从两个提议方接收提案值并进行处理。
对于a、b、c节点来说，对于请求[ 1，3 ]，由于建议号5 (最小建议号)，这些是不被接受的。
它们对于请求[ 5，7 ]是可以接受的。 因为提案编号=5，所以通过提案后，将接受请求:7作为x的Value。
Basic Paxos的总结根据建议号码的大小，收件人保证三个约定。 具体来说：
提案值的建议号，准备请求受益人响应的准备请求的建议号时，受益人接受小于等于的准备请求； 如果不响应
>的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。 Multi-PaxosBasic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用了。
它具有两个缺点：
1、如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商
2、2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。
可以通过通过引入领导者和优化 Basic Paxos 执行来解决这两个问题。
领导者领导者节点作为唯一提议者，就不会存在多个提议者同时提交提案的情况，也就不存在提案冲突了。
模型结构如下：
如何选举领导者需要我们在Multi-Paxos自己实现。
在Chubby中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。
所有的读请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后，作为提议者，执行 Basic Paxos 实例，将数据发送给所有的节点，并且在大多数的服务器接受了这个写请求之后，再响应给客户端成功：
当主节点接收到读请求后，处理就比较简单了，主节点只需要查询本地数据，然后返回给客户端就可以了：
缺点就是所有写请求都在主节点处理，限制了集群处理写请求的并发能力，约等于单机。
下面两个图是 Basic Paxos 以及有领导者的优化执行。
图1 Basic Paxos 图2 优化之后 可以看到，当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段。这是因为领导者节点上的命令时最新的，不需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。 如何理解领导者处于稳定状态？领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。本质上而言，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，是通过减少非必须的协商步骤来提升性能的。这种方法非常常用，也很有效。比如，Google 设计的 QUIC 协议，是通过减少 TCP、TLS 的协商步骤，优化 HTTPS 性能。
reference《分布式协议与算法实战.韩健》