Paxos

简介

Paxos的两阶段

Paxos是一种共识算法，共识算法往往用作分布式系统下实现一致性的一种手段。

Paxos是Leslie Lamport在1990提出的，Lamport在文中虚构了一个希腊城邦 Paxos 来阐述该理论，因为论文未和审稿人就修改意见达成一致，该文章未能在当年进行发表。

在 1998 年和 2001 年，Lamport分别写了两篇论文，《The Part-Time Parliament》和《Paxos Made Simple》来解释Paxos协议。

Paxos将共识算法分为了两个阶段，分别是投票阶段和审议阶段，通过两个阶段在集群中半数以上的结点完成一致性的共识。

共识算法是保证分布式集群中多个结点达到最终一致性的算法。

共识算法不能解决拜占庭问题（数据的丢失以及错误问题）

保证多个结点数据一致性可以通过下列方式：


一致性策略	实现方案	优点	缺点
复制策略	主从同步复制	保证了强一致性	可用性较低，一个结点宕机会影响整个集群的写入。效率较低，主从结点复制整个过程中需要并发机制。缺少同步机制并发依然会出现结点之间数据不一致。
	主从异步复制	可用性较高	不能保证一致性，极端场景下无法达成共识
	主从半同步复制	权衡了可用性和一致性	通过同步多副本保证数据的一致性。没有权威副本有完整的最新的数据，在主结点宕机的时候无法形成新的主节点。
多数派写	多数派写	权衡了可用性和一致性	主从半同步复制需要实现多数写才有可能实现共识。多数写需要处理数据版本的问题，通常用时间戳采用后写者胜的方式覆盖之前写入的值。系统宕机情况，最大时间戳的优胜值无法形成多数，需要处理回滚或者其他手段保障一致性。
共识算法	两阶段	可用性和一致性较好的权衡	第一阶段通过投票获取写数据的权利。第二阶段通过多数写完成共识。

Paxos将结点分为提议者（ Proposer ），接收者（ Acceptor ），学习者（Learner）。在提交数据的时候除了提交的值之外，还会提交递增的版本号。


结点类型	概念
Proposer	发起写操作提议的结点，类似Client。
Acceptor	数据的存储结点，处理Proposer发起的消息。
Learner	也是数据的存储结点，但是不处理Proposer的消息，只是简单复制Acceptor写入的消息。

Paxos的写入冲突

Paxos将写入流程分为两个阶段，第一个阶段是投票阶段，第二个阶段是执行阶段。

Paxos的第一阶段是Proposer发起提议，提议的过程中Proposer会结合Acceptor的返回判断是否进行第二阶段的提交操作。

Proposer发起某个版本的提议。

Acceptor接收Proposer的提议，Acceptor会记录之前Proposer提交的数据版本，并且将之前保存的数据版本以及已经接收的值返回给Proposer。

Proposer接收到Acceptor的返回之后，有两种情况会直接放弃提议：

如果Acceptor没有比当前Proposer提交的更大的版本号，而且收到了半数以上的回应，则进入第二阶段。

Paxos的第一阶段类似于获得数据的操作权，需要提前获取锁，在操作过程利用版本号类乐观锁的机制来实现该阶段的并发安全性。

Paxos的第二阶段Proposer发起写操作，操作过程中会带有数据的值Value和版本号。

Acceptor收到Proposer的写请求之后，会判断当前的数据版本是否和之前接收的版本一致，如果一致则返回接受，否则则不接受。

Paxos的值收敛

Proposer如果接受到半数以上的接受响应，则写入成功。

第二阶段可能会出现没有写入半数以上结点的情况，此时会出现写多数架构中类似的情况，最新的数据未完成写入，Paxos通过后续值恢复的方式来完成数据的写入，值恢复的方式需要第一阶段配合使用。

第一阶段中Accptor如果接受到Proposer的提议中有之前的版本的值，Acceptor会选择其中最大版本号的数据作为自己第二阶段提交的值，通过这种方式，Paxos可以使得提交的值完成收敛，而不会一直提交新值而导致无法形成多数写。