一致性的问题定义

多个副本如何如何保存一致的数据换句话说就是多个进程就一个值达成一致，达成一致之后，这个值是可以被访问到的。

常用的副本数据同步方案，主从复制（redis,mysql复制方案），主要缺点是依赖master，slave复制速度不同，master宕机的时候，各个副本的数据是不一致的。

paxos解决问题的方案

paxos使用大多数都同意的方式就一个值达成一致，算法描述中称为（提案），在该一致性算法中有三种角色，proposer、acceptor、learner,proposer 提出提案（paxos算法中有多个，实际工程实现只有一个），acceptor决定是否批准提案（多个），leaner获得已经确定了的提案（就是被大多数accepor批准的提案）

只要有半数机器可用就能提供一致性的服务，理论上是若要容忍n台机器宕机，则至少需要2*n+1台机器的集群。

paxos协议的论证

一致性算法的安全性要求：

1、只有被提出的提案才能被选定

2、只有一个提案可以被选定

3、如果某个进程能够获取提案，那么这个提案肯定是被选定的那个。

最重要的是只有一个提案被选中，最简单的方案就是只有一个aceptor,acceptor只批准收到的第一个提案。但是显然这样是不行的，从这个角度可以把1主多从的架构看作paxos的子集，即accepor数量=1的情况。要保证可用性，必须要保证多个acceptro工作的情况。

推导过程

最简单的情况，只有一个提案如何满足？

p1一个acceptor必须批准它收到的第一个提案。

仅仅满足p1是不能适用于多个提案的提案的情况的。

提案可以由多个proposer提出也可以由一个，如果一个提案被多个proposer同时提出，或者由一个proposer连续提出，每个acceptor批准了收到的第一个值，但是恰好每个acceptor收到的值都不同。这样就不能选定一个值了，不满足安全性的第二点要去。

一个提案被半数以上acceptor批准才被选定。这意味着每个aceptor必须批准多个值，而不是仅仅批准收到的第一个值，要不然还是无法解决上面描述的无法形成多数派的情况。

为区分提案，每一个提案用一个全局唯一递增的id来标志，这样每次提案可以表示为[id,value]

现在的问题是，每个aceptor可以批准多个值，而算法的要求是只有一个值被选定。有两种方案可以解决这个问题：

1、一旦一个值被选定了，就拒绝后续编号更高的提案

2、一旦一个值被选定了，后续提出的提案的值=被选定的值

第一种方案accepor需要跟其他acceptor通信确定已被批准的值proposer将提案发往m个acceptor，总共有n个acceptor，提出一次提案产生的通信量m*(n-1)

第二种方案的通信量为（n/2，n］

显然选取第二种方案是合理的，而paxos也是采取的第二种方案 ，所以对p1做如下强化

p2：如果编号为M0、Value为V0的提案（即[M0,V0]）被选定了，那么所有比编号M0高的，且被选定的提案，其value值必须也是V0。

因为一个提案被选中必须被多数acceptor批准，可以通过如下条件满足p2

p2a:如果[m0,v0]被选定了，那么所有比m0编号更高的提案，被acceptor批准的提案必须也是v0

假设如下情况:

假如某个acceptor假设为acceptor1没有收到任何消息(消息丢失)，在acceptor1不参与的情况下，其他acceptor批准了［m0,v0],而此时某个proposer向acceptor1发送了[m1,v1],根据p1，acceptor1必须批准[m1,v1]但是这跟p2a矛盾

那么如何保证p2a呢？

p2b:如果一个提案[m0,v0]被选定了，那么之后proposer产生的任何编号更高的提案，其value值必须为v0

p2b包含了p2a,进而包含了p2,接下来只需要论证p2b成立，也就是说，假设[M0,V0]已经被选定了，证明任何编号Mn>M0的提案其Value值也为V0

数学归纳法证明

假设:编号在M0-Mn-1之间的提案Value值为V0

证明Mn也为V0

先描述下如何保证p2b，即提出的提案一定是被批准的提案，在这里默认了一条，要想获取批准的请求proposer必须向多数集合发起请求，询问已经被批准的提案．

M0被选中意味着存在一个多数集合C,批准了该提案，M0-Mn-1的Ｖａｌｕｅ值为V0以为着存在n-1个多数集C，每个多数集的每个acceptor都批准了编号为M0-Mn-1的Ｖａｌｕｅ值为V0

因为任何一个多数集Ｓ都至少包含一个Ｃ中的元素,所以只要保证如下提出提案[Mn,Vn]的条件就能保证Vn=V0

p2C:对于任意［Mn,Vn]，被提出至少存在一个多数集Ｓ，S满足以下两点任意一个

１集合S不存在已经批准过编号＜Ｍｎ的提案（第一次提出提案的情况）

２S中Acceptor批准的编号小于Mn的提案中，编号最大的提案(Mn-1)的值也为Ｖｎ．

这其实描述了提案被提出的条件，要么集合中没有被批准的提案，要么只能选取被批准的最大编号提案的值

保证p2c就能保证p2b

详细论证：

归纳法第一步，n=1即提案编号为M0+1的时候

因为M０已被选中，则肯定存在多数集Ｃ，C批准了V0,M0+1被提出肯定存在一个多数集Ｓ，而Ｓ与Ｃ必有一个公共元素，该元素包含最大编号的提案［M0,V0]，所以M0+1的值为Ｖ０

第二步

假设在M0-Mn-1内所有的提案的值都为V0,证明Mｎ也为Ｖ０．Mn被提出肯定存在一个多数集Ｓ

Ｓ中编号最大的提案也只能是M0-Mn-1之间的，而它们的提案的值都为V0，所以Ｍｎ的值也为V0