Paxos的简单理解

数据备份是为了数据的安全些，比如数据库系统，一主一备是基本的配置。当同一数据储存多份之后，每份数据之间理论上应该是要一样的（毕竟是同一数据），但如何在实际中保证他们是一样的，就是所谓的分布式系统的一致性难题。
Paxos算法解决的就是分布式系统的一致性问题。

问题：

假设有一堆进程，能对某个变量应该是什么值发表建议。paxos算法可以保证最终会选取一个值给这个变量。

1. 如果没有进程提出值，最终肯定也是没有结果的。
2. 如果有多个线程提出意见，最终只有一个值并选定，并且这个选定的值大家都会知道（然后就可以更新本地自己的变量了）

角色划分

从角色上划分，有proposer, acceptor,learner。
对于proposer，提出一个值v。直接提出就好了。
对于acceptor，对于接受到的proposer提出的proposal。可以选择接受，或者拒绝。既然有两种选择，就需要给出选择的依据。
learner只需要知道结果，因此对于值是如何达成一致的没有任何的帮助。因此下面主要通过proposer和acceptor的角度分析paxos算法。

过程推导

Conclusion 1: acceptor 必须接受第一个到达的proposal

1. 假设只有一个节点的情况。自己即是proposer, 又是 acceptor。当然自己没有理由拒绝自己的提案。
2. 假设两个节点的情况，A propose 一个值，而B 为了让系统达成最终的一致，只能接受自己收到的提议。
3. 扩展到多个节点， 考虑节点可能失效，消息可能丢失。对于一个acceptor，当他接受到一个提议时，他是无法预测未来是否还有提议，在这种情况下，他只能接受这个值。如果他不接受，系统最终就可能达不成一致。
   总结上面3点，对于acceptor，对于第一条达到的消息，只能选择接受。

Conclusion 2: acceptor 可以接受多个proposal

按照P1的原则，如果每个acceptor接受一次消息后，系统就达成了一致，那么P1足够保障系统的一致性。但由于proposer不止一个，acceptor也不止一个，当两个propose人的提案被不同的acceptor接收以后，导致没有一个提案获得大多数acceptor的接收，系统达不成一致。
在这个场景下，为了达成最终的一致，proposer会再次提出提案，而acceptor也会再次接收到提案。对于这些提案，acceptor一定是可能接收的（如果全是拒绝的策略，那么系统永远不能一致了）。
也就是说，对于acceptor而言，他是可能接受多个proposal 的。
为了能将各个proposal区分开来，将每个proposal分配一个编号id。proposal目标包含一个编号id和值value。当proposer发出提案时，需要使用唯一的id。

Conclusion 3: acceptor接受proposal_id 更大的提案

我们知道，第一个proposal用户已经接受了。现在问题是，对于后来的proposal，用户如何选择接受或者拒绝。
proposal中只包含两个东西。一个是id，一个是value。
对于value，只有两种情况

1. 当value一样的情况，选择接受当然不会有问题，但对于系统达成一致性没什么帮助。
2. 当value不一样的情况。如果全部拒绝，则系统最终达不成一致。如果全部接受，那么又回到混沌初开的原点，不需要任何算法了，对于acceptor，来一个提案，接受一个。能不能达成一致看运气了。
   所以从value的角度看，甚至没有办法给出一个拒绝或者接受的条件（哪怕是个不靠谱的条件也行）。

回到id，也只有两种情况

1. id比第一次接受的proposal的id要大。
2. id比第一次接受的proposal的id要小。
   两种情况没有本质区别，我们可以选择一种进行接受，另一种进行拒绝。为了符合人性，选择大的id接受。
   当然，这种选择也是靠天吃饭，但至少acceptor有个拒绝接受的依据了。

Conclusion 4：proposer提出的value需要和已经通过的提案（如果有的话）保持一致。

acceptor已经尽力了。剩下的只能看proposer的了。
proposer提出提案也是只包含id和value。
id可以考虑的东西不多，毕竟acceptor只接受更大的id，那不妨提出提案的时候选个尽量大的。

对于value。
我们首先要注意整个一致性算法的目标是在value上达成一致。也就是说，如果某个acceptor提出的value已经被大多数的acceptor接受了，你现在要提出一个提案（你还不知道已经在value上达成了一致，刚刚说被大多数acceptor接受这个事情是属于上帝视角，在一段时间内，整个系统都不知道这件事而这件事确实已经发生），你选择了一个大的id，刚刚那批达成一致了的acceptor又没有办法拒绝你，所以这个时候，为了达成一致性，你提出的value必须和已经被大多数acceptor认可的value一样。
从上帝视角看，当你要提出一个proposal的时候，系统的状态分为两种

1. 某个提案被大多数acceptor已经接受，其值为value。此时proposal提出的提案也必须为value。
2. 还没有达成一致。此时proposal提出的提案的值可以任意。

Conclusion 5: proposer根据接受到acceptor反馈的proposal决定如何选取value。

如果acceptor没有返回任何proposal，则proposer可以任意选取value。否则选择其中最大的proposal的值。

对于一个proposer而言，

1. 他已经知道了整个系统达成了一致。他肯定不会提出提案。
2. 如果他不知道整个系统是否一致，这个时候他该怎么提出值？

此时别无他法，只能由该proposer去询问每个acceptor，而每个acceptor的回答会有两种情况

1. 我没有接受过任何proposal。
2. 我接受过proposal。

对于情况2，需要进行分析

1. 该acceptor可能接受过多个proposal。

2. 该acceptor返回的proposal可能是已经通过的提案，也可能还没有通过，只是这个acceptor接受而已。
   在询问一圈之后，proposer会收到多个acceptor的回答。回答中包含了各个acceptor曾经接受了的proposal。这些proposal中可能一个都没有通过--此时该proposer可以随意提出value，也可能有一个（最多一个了）是已经通过的--此时该选取哪个proposal的值又是一个问题。
   为了便于区分，先将这一次proposal的询问行为定义为prepare_request。
   同时，我们需要解决的问题演变为了：如何在各个acceptor回到的proposal中选取一个，作为此次提案的value依据。

3. 如果这堆提案中没有一个是通过的，则proposer可以任意提出value。

4. 其中有提案时通过的，记其中一个为m=(m, v)，其对应的大多数集合为C。
   划重点：当提案(m,v)通过是，集合C中的所有acceptor接受过的最大的proposal都是(m,v)。所以当m+1号提案提出时，为了获取到v这个值，他一定要获取到C中至少一个acceptor的回复，因此m+1好提案正式提出前，至少要获取都大多数集合的acceptor的回复才行。
   对于m+1而言，获取大多数集合的回复，并且使用通过的最大的proposal的v就能满足Conclusition4。由于m+1的提案值也是v，因此对于集合C，依然保持了接受的最大proposal的v就是通过的提案value。
   因此对于m+2号提案，可以使用与m+1号提案相同的方式。
   通过简单的归纳证明，沿用此方法，能使得在m之后的所有提案都具有相同的提案值。

也就是说:如果n要提出(n, v)，那么存在一个大多数集合C。满足

1. C中的acceptor没有接受过任何提议。-- 对应于还没有提案通过的情况
   或者 2. C中的acceptor接受小于n的最大提议的值为v。 -- 对应于有提案通过的情况

在上述条件的情况下，如果v被通过，则后续提出的所有值都将是v。可以严格证明反证如下：
对于m+1，如果提出的值不等v。那么存在一个大多数集合C没有接受过任何值，或者C中接受的小于m+1提案的提议值不等于v。而(m,v)已经被接受，因此不存在那样的集合C。

因此，对于proposer的要求出来了：
当获取到acceptor返回的proposal后，选取最大的proposal作为值，如果不存在，则可以任意选取。

至此，paxos的整个过程已经确定了。
预请求阶段:

1. proposer选定编号n，将编号发送给acceptors
2. acceptor收到预请求后，a) 保证后面不在接受比n小的提案。 b) 返回已经接受过的，编号比n小的，最大的提案。

请求阶段：

1. 如果proposer收到了大多数acceptor的反馈。则进入请求阶段。其value为 a) 如果acceptor没有返回任何已经接受过的proposal。 b) acceptor返回的proposal中编号最大的对应的value。
2. acceptor接受到请求后，如果大于等于其接收过的最大的预请求编号，就接受这个请求。

一些易混点

1. acceptor返回给proposal的是小于预编号的最大接受提案。