在概论分布式系统中，数据通常存储多个副本，如何保持副本之间的一致性是一个比较经典的问题。 Paxos是比较经典的一致性算法，本文对Paxos进行简要介绍。
由于Paxos算法以难以理解而闻名，后来还提出了更容易理解的算法Raft。 在https://blog.csdn.net/QQ _ 34924156/article/details/111589352一文中简要介绍。
Paxos算法问题定义一致性：
现在有一个process小组，每个process可以提出一个建议(value )。 该组中的process需要执行相同的建议，因此需要从决策建议中选择一个执行。 最终，这个小组的process将执行这个被选中的建议。
转换为分布式存储时，可以理解为有一组包含相同数据的复制副本，每个复制副本都可以建议更改数据，但由于复制副本集必须保持相同的复制副本数据，因此最终只会选择一个更改建议。
一致性协议的目标：
选择一个方案(如果有)，所有process都会通知您选定的方案。 异步通信存在允许信息丢失和重复，但内容不会损坏(拜占庭以外的型号)，允许机器故障等问题。一致性的安全性：
如果没有选择只有在提交提案后才能选择的一个提案，process将不会收到已选择该提案的消息。 也就是说，只接收正确选择的消息(http://www.Sina.com/consistency算法没有特别准确的时间要求。
注：提案人(proposer )、批准人(acceptor )、收件人(listener ) )。 一个process可以承担多个作用。
选择方案主要角色：如果有很多acceptor批准某个方案，则会选择方案。
一个加速器只能批准一个提案。 之所以只能选择一个加速器，是因为一个加速器存在单点故障，如果出现该加速器故障，系统将无法继续运行。基本原则：
两个阶段的过程：
1. Proposer (选择一个议案编号n，也向加速器的多数派发送编号n的prepare请求。
加速器：如果收到的prepare请求的编号n大于已经响应的prepare请求，则承诺响应批准的编号最高的案件(如果有)，而不响应编号较高的烤鸡案件。
2.Proposer )当收到许多加速器对prepare请求(编号n )的回复时，它会向这些加速器发送议案(n，v )的accept请求，称加速器们还没有批准过议案
加速器：如果收到议案{n，v}的accept请求，只要已经对ngdch号的议案做出响应，就批准该议案。 只要遵循上述算法，Proposer可以提出多个议案。 可以随时放弃议案。 【这不损害正确性。 即使议案被放弃后，根据议案的要求和信息终于达到目标】如果其他职业人士已经开始提出更高编号的议案，最好可以放弃现在的议案。 因此，如果加速器忽略了一个prepare或accept请求(因为收到了更高编号的prepare请求)，它就必须通知proposer放弃议案。 这是性能优化，不影响准确性。
算法过程：
概念：议案={编号，提案}，其中编号是唯一的
详细规则：（可以忽视，主要是算法过程的由来）
1. Acceptor必须批准它接收到的第一个提案。（可以批准多个议案，但是要保证议案拥有相同提案）。
rong>2.a 如果一个议案{n, v}被选择，那么任何acceptor批准的议案（编号更高）包含的决议都是v。
我们依然保证1来确认选择了某些议案。因为通信是异步的，在特殊情况下，某些acceptor c没有接收到过任何议案，它们可能会批准一个议案。设想一个新的proposer“醒来”并提出了一个更高编号的议案（包含不同的决议）。根据P1的要求，c应该批准这个议案，但是这违反了P2A。为了同时保证P1和P2A，我们需要2.b：
2.b 如果一个议案{n, v}被选择，那么此后，任何proposer提出的议案（编号更高）包含的决议都是v。
因为一个议案必须在被proposer提出后才能被acceptor批准，因此2.b包含了2.a，进而包含了2。
如何才能满足2.b呢，让我们来考虑如何证明它是成立的。我们假设某个议案{m, v}被选择，然后证明任何编号n>m的议案的提案都是v。对n归纳可以简化证明，根据条件：每个提出的议案（编号从m到n-1）的提案都是v，我们可以证明编号为n的议案的提案是v。对于选择的议案（编号为m），必定存在一个集合C（acceptor的多数派），C中的每个acceptor都批准了该议案。结合归纳假设，m被选择这一前提意味着：
C中的每个acceptor都批准了一个编号在m到n-1范围内的议案，并且议案的提案为v。
因为任何由多数派组成的集合S都至少包含C中的一个成员，我们可以得出结论：如果下面的不变性成立，那么编号为n的提案的决议就是v：
2.c 对于任意的v和n，如果议案{n, v}被提出，那么存在一个由acceptor的多数派组成的集合S，要么：S中没有acceptor批准过编号欣喜的烤鸡的议案，要么：在S的任何acceptor批准的所有议案（编号欣喜的烤鸡）中，v是编号最大的议案的提案。
通过保持2.c，我们就能满足2.b。
为了保持不变性2.c，准备提出议案（编号为n）的proposer必须知道所有编号欣喜的烤鸡的议案中编号最大的那个，如果存在的话，它已经或将要被acceptor的某个多数派批准。获取已经批准的议案是简单的，但是预知将来可能批准的议案是困难的。Proposer并不做预测，而是假定不会有这样的情况。也就是说，proposer要求acceptor不能批准任何编号欣喜的烤鸡的议案。这引出了下面提出议案的算法（两阶段提交）。
两阶段提交：
Prepare阶段：proposer选择一个新编号n，向某个acceptor集合中的所有成员发送请求，n是prepare请求的编号，也是下面acceptor请求的议案编号。Acceptor需要保证永不批准编号欣喜的烤鸡的议案，同时响应它已经批准的所有编号欣喜的烤鸡的议案中，编号最大的议案（如果存在的话）如果proposer收到了多数acceptor的回应，那么它就可以提出议案{n, v}，如果acceptor们回应说还没有批准过议案，那么v就是该proposer提出的议案，否则v是所有回应中编号最高的议案的决议。2.c介绍了两阶段提交proposer的行为，对于acceptor，主要行为如下：
1.a acceptor可以批准一个编号为n的议案，当且仅当它没有回应过一个编号ngdch的prepare请求。
1.a蕴含了1。
假设一个acceptor接收到一个编号为n的prepare请求，但是它已经回应了一个编号ngdch的prepare请求。于是acceptor就没有必要回应这个prepare请求了，因为它不会批准这个编号为n的议案。它还可以忽略已经批准过的议案的prepare请求。
acceptor只需要保存它已经批准的最高编号的议案（包括编号和决议），以及它已经回应的所有prepare请求的最高编号。因为任何情况下，都需要保证P2C，acceptor必须记住这些信息，包括失效并重启之后。注意，proposer可以随意的抛弃一个议案——只要它永远不会使用相同的编号来提出另一个议案。
Learner获知结果：
Learner必须找到一个被多数acceptor批准的议案，才能知道一个决议被选择了。一个显而易见的算法就是，让每个acceptor在批准议案时通知所有的learner。于是learner可以尽快知道选择的决议，但是要求每个acceptor通知每个learner——需要的消息个数等于learner数和acceptor数的乘积。
基于非拜占庭假设，一个learner可以从另一个learner得知被选择的决议。我们可以让acceptor将批准情况回应给一个主Learner，它再把被选择的决议通知给其它的learner。这增加了一次额外的消息传递，也不可靠，因为主learner可能会失效，但是要求的消息个数仅是learner数和acceptor数的总和。
更一般的，可以有多个主Learner，每个都能通知其它所有的acceptor。主learner越多越可靠，但是通信代价会增加。
由于消息丢失，可能没有learner知道选择了一个决议。Learner可以向acceptor询问批准的议案，但是由于acceptor的失效，可能难以得知多数派是否批准了一个议案。这样，learner只能在新的议案被选择时才能知道acceptor选择的决议。如果learner需要知道是否已经选择了一个决议，它可以让proposer根据上面的算法提出一个议案【提出请求就有回应，并且新的提案的决议就是当前选择的决议】。
死锁与解决：
死锁：两个proposer轮流提出一系列编号递增的议案，但是都没有被选择。Propoer p选择议案的编号为n1，并结束阶段1。接着，另外一个proposer q选择了议案编号n2>n1，并结束阶段1。于是p在阶段2的accept请求将被忽略，因为acceptor已经承诺不再批准编号欣喜的烤鸡2的议案。于是p再回到阶段1并选择了编号n3 > n2，这又导致q第二阶段的accept请求被忽略。
解决：选择一个主proposer，只有主proposer才能提出议案。如果主proposer和多数acceptor成功通信，并提出一个编号更高的议案，议案将被批准。如果它得知已经有编号更高的议案，它将放弃当前的议案，并最终能选择一个足够大的编号。
实现 选出Leader：担任主proposer和主learnerAcceptor在发送响应前必须持久化存储该响应。proposer都持久化保存它已经提出的编号最高的议案。proposer从互不相交的集合中选择议案编号，保证两个不同的proposer永远不会提出相同编号的议案。如proposer i的议案编号选择序列为：5*j + iPaxos进阶 PaxosLease前文提到需要选出leader担任主proposer和主learner，PaxosLease便是用于选举leader的算法。
众多的Node中选择一个作为Master（即leader），如果该Master 一直 alive则无需选举，如果master crash，则其他的node进行选举下一个master。为了保证任何时刻最多只能有一个master，算法将选举master变成了分布式锁的问题。
完全靠锁来解决选举问题会存在死锁（如果一个Node拿到了锁，之后crash，那锁会导致无法释放）。因此设计Master只能在Lease有效期内访问锁定的资源，在Lease timeout后，其他Node可以继续竞争锁，这就从根本上避免了死锁。Master在拿到锁后，如果一直alive，可以向其他node”续租“锁，从而避免频繁的选举活动。
Multi-Paxospaxos是对一个值达成一致，multi-paxos是运行多个paxos instance来对多个值达成一致，每个paxos instance对一个值达成一致。在一个支持多写并且强一致性的系统中，每个节点都可以接收客户端的写请求，生成redo日志然后开始一个paxos instance的prepare和accept过程。这里的问题是每条redo日志到底对应哪个paxos instance。
Multi Paxos基于Basic Paxos，将原来2-Phase过程简化为了1-Phase，从而加快了提交速度。Multi Paxos要求在各个Proposer中有唯一的Leader，并由这个Leader唯一地提交value给各Acceptor进行表决，在系统中仅有一个Leader进行value提交的情况下，Prepare的过程就可以被跳过，而Leader的选举则可以由Paxos Lease来完成。