Paxos是分布式系统中的经典的一致性协议，之前在学习zookeeper时第一次接触到，不过当初并没明白这个有点绕的算法到底解决了什么问题，直到最近研究分布式数据库又碰到，重新对这块进行了进一步学习，在这里进行总结下。paxos协议在原来的论文中是比较抽象的，所以很多人看完都觉得有点晦涩，因为它并没有说明在工程实践中这个协议怎么用、怎么落地，接来下我们就看看这个推演过程，然后主要看下分布式存储场景下的使用。
目的：在多进程下确定一个不可变量
推演
假设我们要设计一个系统， 服务器端Acceptor【接受客户端请求，设置一个变量为一个值，一旦修改完成便不可更改】；客户端Proposer：【请求服务端设置变量为一个值，不同的客户端发起的值不相同】。
场景1：服务器端Acceptor数量为1，客户端Proposer数量为1
这种场景下，不存在并发问题，直接客户端请求修改即可。但现实场景中，客户端往往是多个，因此产生了场景2。
场景2：服务器端Acceptor数量为1个，客户端Proposer数量为多个
这种场景下，存在并发问题，通常会通过锁机制进行串行化实现，这也是大部分数据库等实现的方式，但注意的是我们要求是设置一个值后便不可更改，所以只允许第一个值生效。因此我们可以将这个操作拆分成两个阶段：
第一阶段：通过Acceptor提供的prepare()请求互斥锁和当前变量值，如果不能获取，则返回失败（锁为别的Proposer占用），
第二阶段：根据第一阶段返回当前变量值f选择执行，如果f为null（未设置），则通过Acceptor的accept(value)设置变量值为value；如果f不为null，则代表其他proposer已经设置过值，则通过Acceptor的release()方法释放访问权；如果返回失败，则代表锁正被Proposer占用，则放弃这次设置或稍后再尝试。
这种方式通过获取互斥访问权让Proposer操作串行进行，可简单实现变量不可变性，对于各个Proposer达到了一致性。但这种机制有个严重的问题，Proposer在释放互斥访问权之前发生故障，会导致系统陷入死锁，为了解决这个问题，我们接下来看场景3
场景3：服务器端Acceptor数量为1个，客户端Proposer数量为多个，引入访问权抢占机制
为了解决场景2中死锁问题，我们引入访问权抢占机制，Acceptor可以让某个proposer获取到的访问权失效，不再接收它的访问，然后将访问权发放给给其它的proposer，让其进行变量值设置。简单的一个方案是：
第一阶段：Proposer在调用申请访问权时指定编号epoch(越大的epoch越新，可以采用时间戳等实现)【方法变为prepare(current_proposer_epoch)】，获取到访问权之后，才能向Acceptor提交取值。Acceptor采用“喜新厌旧”原则，一旦收到更大的新epoch的申请,马上让旧epoch的访问权失效，不再接收他们提交的取值，然后给新epoch发放访问权，只接收新epoch提交的取值。另外Acceptor端记录当前获得访问权的epoch值、接受的epoch值以及最新的变量值【prepared_epoch，accpeted_epoch，latest _value 】，如果latested _value为null，则比较当前Proposer的epoch是否大于prepared_epoch，如果是则给该Proposer发送访问权，否则返回失败；如果latest _value不为null，说明变量已设置，则返回给Proposer该变量值。
第二阶段：如果Proposer在第一阶段成功获得访问权，则发起请求设置变量值；如果第一阶段成功返回最新变量值不为空，则第一阶段直接认可该值f，即调用accept(epoch，f)，设置当前变量值不为f得Accetor值为f，使所有Acceptor值一致；如果第一阶段失败，则增加epoch值，再进行下一轮paxos尝试。Acceptor端会盘点epoch是否为prepared_epoch，如果不是则直接拒绝，如果是，则设置变量值。
引入访问权抢占机制后，新epoch可以抢占旧epoch,让旧epoch的访问权失效，旧epoch的proposer将无法运行，新epoch的proposer将开始运行，不同epoch的proposer之间采用”后者认同前者”的原则：
a.在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的value.不会冲突
b.一旦旧epoch形成确定性取值，新的epoch肯定可以获取到此取值，并且会认同此取值，不会破坏.
这个方案看起来已经没了死锁问题，但服务器端Acceptor数量仅有1个，存在单点故障问题，因此我们需要将Acceptor集群化，也就是场景4
场景4：服务器端Acceptor数量为多个，客户端Proposer数量为多个，引入访问权抢占机制
第一阶段：Acceptor变为多个后，按照场景3中机制，Proposer在第一阶段获取访问权时，会向所有Acceptor发送，那么如何决定是哪个Proposer获取到访问权呢？这里我们引入“过半机制”，假设Acceptor数量为2n+1，如果某个Proposer得到有n+1个Acceptor的成功回应，则表明该Proposer获得访问权，因为两个过半集合必定至少有一个是相同的，所以这个机制保证了只会有一个Proposer第一个阶段成功，获得访问权。
第二阶段：第一阶段获得过半响应的Proposer向这些Acceptor发起accept(epoch，value)，设置变量值为value。其它Proposer以及Acceptor处理机制同场景3第二阶段。
这样，通过场景4方案，成功解决了多个进程下设置一个不可变量值的问题，而且没有死锁和单点问题，只要过半节点存活即可运行。
以上就是paxos中核心的算法，在原论文的最后简单的提到了如何基于该协议实现状态机模型，同时引入了learner角色【负责获取最新确定的不可变量值】，在多进程中，每个进程都同时扮演proposer、acceptor和learner的角色。
好吧，你肯定会想，设置一个不可变量有个鬼用，现实系统的状态都是随着输入不断的变化着，但别急，仔细想下，每个系统实际上就是一个状态机，通过不同的操作从而导致状态进行改变，我们将每个操作看做一个不可变量值，那么现实系统可以看做是多次有序paxos的过程，之后来我们看下主要的使用场景，不过在这之前我们看下经典paxos或者叫basic-paxos的问题
问题：
活锁：Paxos因为会有多个Proposer发起Proposal, 新的epoch能抢占旧的，这样就会有活锁(Liveness)问题
性能：经典paxos中每个Proposer都可发起Proposal,因此对于系统的每个输入，每次都会进行第一阶段投票阶段，这样在集群较大、网络不好的情况下效率是比较低，而且处于安全性，还需要通过WAL机制在磁盘上进行持久化，这些过程实践细节，lamport也并未进行详细描述，这也是paxos协议实现的困难之处。
基于上面两个问题，通常的解决方案是选Leader, 由Leader来发起Proposal，Leader会维护一个Lease, Lease过期的话，需要选举新的Leader。Leader是保证和加速Paxos进度的重要手段，通常在具体的工程实践中，都会选Leader。而工程实践具体实现该协议时，都会增加一些限制，例如大多都会强化Leader角色，在日志复制方面增加了各自的限制，例如Multi-paxos、ZAB、Raft等算法，都可以看作是经典paxos或者basic-paxos的一种简化、具体化，但这些算法在做了这些改变后其实并不能完全通过原paxos中那样进行形式化论证了。
使用场景：分布式存储
为了提高数据可靠性需要多副本，副本之间需要保证一致性，我们将每个副本看作一个状态机，如果每个副本按照同样顺序执行【op1、op2、op3...opn】，那么便可保证副本的一致性。将每个操作op*看作是确定的一个不可变量，则可以通过多次paxos过程从而达到数据存储的一致性。例如zookeeper、etcd、consul、微信最近开源的PhxSQL根本都是采用各种具象化的paxos协议。
当然其实除了分布式存储，所有通过状态机复制模型来保证一致性的场景都可以使用paxos来实现，例如：命名服务、配置管理、集群选主等。
参考资料：
