什么是Paxos算法（一致性算法）？

Paxos算法所解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模式的一致性算法。

但在正式深入了解Paxos之前需要先引入三个概念：分布式系统，状态复制 和 消息传递模式。

什么是分布式系统？

说分布式系统必须要说集中式系统，集中式系统中整个项目就是一个独立的应用，整个应用也就是整个项目，所有的东西都在一个应用里面。

集中式系统图示 分布式系统图示

分布式系统就是将系统的应用层，数据层或其它部分构架成分布（物理和逻辑上的都可以）状（通常是网状）。

比如在线游戏通常就是分布系统，里面所谓的“大区”就是分布系统里子例程。

什么是状态复制？

对于一组节点，如果所有节点均以相同的顺序执行一个（可能是无限的）命令序列c1,c2,c3,......，则这组节点实现了状态复制。

    · 状态复制是分布式系统的基本性质。

    · 单一节点天然实现状态复制。

什么是消息传递模式？

简单来说，就是在消息传递模式下构建一个分布式系统时，系统中每个节点都能进行本地运算，并可以向所有的其他节点发送消息。

基于Paxos算法搭建分布式系统

为了更好的深入了解Paxos算法，我们从最小的分布式系统（仅有两个节点）开始。该系统有一个客户端节点，它希望操作（储存或者更新）在远程服务器节点上的数据。

简单发送算法

客户端向服务器发送一条命令。

此时服务器应该会接收到这条命令？不一定，消息传递模式下会存在“消息丢失”，在存在“消息丢失”的时候，任何一条消息都不能保证可以安全的发送给消息接收者。

如果消息丢失，则算法无法正常工作，所以我们需要一点小小的改进。

带确认的发送算法

1.客户端每次向服务器发送一条命令

2.服务器每收到一条命令，都会发送一条确认信息

3.如果客户端没有在一个合理的时间内收到确认信息，它将重新发送命令

每次发送一条命令指的是客户端在发送命令之后，收到确认信息之前，客户端不会发送任何新的命令。

“带确认的发送算法”可以很容易的拓展到单客户端，多服务器的的应用场景，比如：客户端发送命令给所有的服务器，只要收到所有的服务器发回的确认消息，就可以认为此命令被执行成功。

但是如何处理多个客户端的情况呢？

并且在实际的应用场景里面，消息传输花费的时间是不同的（可变消息延迟模式）。多个客户端这种情况的发生尤为明显。

序列化器实现状态复制算法

1.所有的客户端都向序列化器发送命令，每次发送一条

2.序列化器自动将命令排序并依次转发给所有的服务器

3.一旦序列化器收到所有的确认信息，它将通知所有的客户端命令被成功执行

我们通过序列化器解决了“带确认的发送算法”无法实现状态复制的问题，但是如果序列化器宕机了呢？所以，序列化器是一个很“明显”的潜在故障点！

我们需要一个更分布式的方法：与其实现一个序列化器，不如想办法确保最多只有一个客户端在发布命令（挖矿的影子）。

给客户端上锁算法

阶段1

1.客户端向所有的服务器请求锁

阶段2

2.if（该客户端成功获得了所有服务器的锁）{

    该客户端向每个服务器发送命令，释放全部的锁

}else{

    该客户端释法已获得的锁

    该客户端等待一段时间，再重新进入阶段1

}

可是“给客户端上锁算法”真的有更好的解决节点的宕机吗？不，实际上，“给客户端上锁算法”比“序列化器实现状态复制算法”更差，“序列化器实现状态复制算法”只要求一个节点必须正常工作，但是“给客户端上锁算法”却要求所有的服务器节点能够正常的响应请求。

其实我们只得到部分服务器的响应，获得过半数以上节点的锁就足够了。所以“锁”的方式太沉重，所以我们需要一个轻量化的“锁”：票。

票是一个弱化形式的锁，具备下面的性质：

    1.可重新发布：一个服务器节点可以随时发布新的票，哪怕前面发布的票还没有被释放。

    2.票可以过期：当客户端使用一张票T来发送命令时，只有当服务器验证票T为最新发布的票的时候，服务器才会接收这条命令。

有了票之后，节点宕机的问题被解决了：一个客户端在得到一张票之后宕机了，其他客户端不会收到影响，因为服务器会发布新的票。

且票可以用计数器来实现：没发布一张新票，计数器加一，这样每当客户端用票来请求的时候，服务器就可以判定票是否已经过期了。

票算法

阶段1

1.客户端向所有的服务器请求一张票

阶段2

2.if(收到过半数目服务器的回复){

    客户端将获得的票和命令一期发送给每个服务器

    服务器检查票的状态，如果票仍然有效，则储存命令并给客户端发送一个反馈

}else{

    客户端继续等待，并重新进入阶段1

}

阶段3

if(客户端从过半数目服务器处得到了反馈){

    客户端告诉所有服务器执行之前储存的命令

}else{

    客户端继续等待，并重新进入阶段1

}

这个算法没问题了吗？有，因为“可变消息延迟模式”，又来了。

如果服务器不但发布票，而且还发布他当前锁储存的命令，那么U2就知道U1已经储存了命令C1，U2可不要求服务器存储命令C2，而是继续存储C1，这样两个客户端都尝试存储和执行相同的命令，那先后顺序就不重要了。

但是如果，服务器存储的命令不一定相同，所以我们应该支持最新存储的命令。只要还不存在一个过半服务器都支持的命令，客户端们就可以随意支持任何的命令，然而一旦有一个过半数服务器一致支持的命令，那所有客户端都必须支持这个命令。

所以，为了判定哪一个命令是最新的存储的，服务器们必须记录存储命令时客户端所用到票的编号，并且在阶段1把命令和相应的编号都告诉客户端。

但如果每个服务器都是用自己的票号，最新的票号就不一定是一致的。

我们需要一个全局一致的票号，因此不能让每个服务器自己维护一个自己本地的计数器来产生票号，我们可以让客户端自己来决定下一个票号T，然后去向所有的服务器请求票号为T的票，服务器收到请求之后，先将T和自己本地计数器去进行比较，只有T大于计数器的值的时候，服务器才会发布票号为T的票，并且将计数器的值更新为T。

Paxos算法

客户端                                                                                 服务端

c ==> 等待执行的命令                                                         Tmax = 0  ==>  当前已发布的最大票号

t ==> 当前尝试的票号                                                          C ==> 当前存储的命令    

                                                                                            Tc[] ==> 用来存储命令C的票

阶段1

1. t=t+1

2.向所有服务器发送消息，请求编号为t的票

                                                                                            3.if(t > Tmax){

                                                                                                Tmax = t，并回复ok(Tc[]，C)

                                                                                            }

阶段2

4.if(过半服务器回复ok() ){

    选择Tc[]中值最大的(Tc，C)

    if(Tc > 0){

        c = C

    }

    向回复了ok的服务器发送(t,c)

}

                                                                                            5.if(t = Tmax){

                                                                                                C = c，Tc = t，回复success

                                                                                            }

阶段3

6.if(过半服务器回复success){

    向每个服务器发送消息：execute(c)

}

至此，一个完整的Paxos算法就成型了