paxos一致性协议

 

所有机器完全同步不是目的，对外服务一致才是目的。

 

Paxos 算法分为两个阶段。具体如下：
阶段一（准 leader 确定 ） ：
(a) Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求。
(b) 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。

阶段二（leader 确认） ：
(a) 如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的Accept 请求给半数以上的 Acceptor。注意： V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么V 就由 Proposer 自己决定。
(b) 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。
 

 

如何产生唯一的编号？

在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择，例如系统有5个Proposer，则可为每一个Proposer分配一个标识j(0~4)，则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)。

 

为什么只保证超过半数的机器保持同步？那剩下的机器是不是会出现不一致的问题？

如前面所述，paxos协议是为了解决分布式系统的“读写一致性”而设计的，集群对外服务时，表现的是系统整体的行为。既然通过交集已经保证了对外服务的一致，那么目的已达到，其余没同步的机器，可通过Leader重试同步、通过Recover阶段同步、通过全同步过程同步，甚至是不同步，都是一致性算法可接受的运行状态。

 

 

扩展：（待补充各种一致性...）

在事务的上下文中，一致性（Consistency）的概念是：对数据的一组特定陈述必须始终成立。即不变量（invariants）。具体到分布式事务的上下文中这个不变量是：所有参与事务的节点状态保持一致：要么全部成功提交，要么全部失败回滚，不会出现一些节点成功一些节点失败的情况。

在分布式系统的上下文中，线性一致性（Linearizability）的概念是：多副本的系统能够对外表现地像只有单个副本一样（系统保证从任何副本读取到的值都是最新的），且所有操作都以原子的方式生效（一旦某个新值被任一客户端读取到，后续任意读取不会再返回旧值）。

 

截取自知乎冯若航的回答  https://www.zhihu.com/question/275845393/answer/386816571