分布式一致性协议paxos,分布式环境下一致性算法

　　概述Paxos算法是Lamport大师提出的基于消息传递的分布式一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。本文的目的是带领大家深入浅出地了解Paxos算法，了解它的执行过程，进而通过一个实例了解Paxos算法在分布式系统中的作用。有能力的同学可以直接看原文。

　　分布式分布式系统通常由多个节点通过异步网络连接而成，每个节点都有独立的计算和存储。一般来说，分布式一致性一般是指数据的一致性。例如，分布式存储系统通常以多副本冗余的形式实现数据的可靠存储。同一数据的多个副本必须一致，数据的多个副本存储在不同的节点。这里的分布式一致性问题是存储在不同节点的数据副本的值必须一致。

　　如果一致性得不到保证，那么这个系统中的数据就根本不可信，数据就没有意义，所以这个系统就根本没有价值。

　　在分布式系统中，每个节点需要相互通信以保持数据的一致性，通信有两种方式：共享内存和消息传递。在基于消息通信模型的分布式系统中，不可避免地会出现以下错误：机器停机，进程可能变慢、终止或重启，消息可能延迟、丢失或重复。那么在这种复杂的情况下如何保证一致性呢？

　　Paxos算法就是如何在一个分布式系统中快速正确地约定某个数据的值，并保证无论发生任何异常都不会破坏整个系统的一致性。

　　注意：这里某个数据的值不仅仅是狭义上的某个数字。它可以是日志或命令。根据不同的应用场景，某个数据的值有不同的含义。

　　Paxos算法描述了Paxos算法的目标：在分布式环境中确定一个值，并且这个值被所有节点识别。

　　Paxos将系统中的角色分为提议者、接受者和学习者：

　　提议者：提出建议。建议信息包括建议编号(建议ID)和建议值(值)。接受者：参与决策，回应提议者的提议。收到提议后，可以接受提议。如果提议被大多数接受者接受，就说该提议被批准了。

　　学习者：不参与决策，向提议者/接受者学习最新达成一致的提议(值)。在具体实现中，一个流程可以同时扮演多个角色。例如，一个过程可能既是提议者，又是接受者和学习者。

　　算法流程

　　Proper有两个重要的属性，提议号N、提议V和提议者(N，V)。

　　Acceptor有三个重要的属性：响应建议号ResN、接受建议号ACCEPTN、接受建议ACCEPTV和临时接受者(RESN、AcceptN、AcceptV)。

　　第一阶段：准备阶段。

　　提议者：提议者生成一个全局唯一且递增的提议号n，并向所有接受者发送一个准备请求。这里不需要携带提案内容，只需携带提案编号，即发送Proposer(N，null)。

　　接受者：接受者收到准备请求后，有两种情况：

　　如果接受者第一次收到准备请求，设置ResN=N，同时响应ok。如果接受者第一次没有接收到准备请求，则如果所请求的建议号n小于或等于最后的持续建议号ResN，则它将不会响应或响应错误。如果请求的建议号N大于最后一个持久建议号ResN，则更新ResN=N并给出响应。有两种回应结果。如果这个接受者以前没有接受建议，它只返回ok。否则，如果这个接受者以前收到过建议，它将返回ok和最后接受的建议号AcceptN，以及收到的建议AcceptV。第二阶段：接受验收阶段。

　　提议者：提议者收到响应后，有两种情况：

　　如果一半以上的回答是可以的，检查一下回答中是否有提议。如果有，取建议V=响应中最大接受度N对应的接受度V。如果没有，V由当前提议者设定。最后，发送一个accept请求，该请求携带了提议v，如果超过一半的响应都ok，那么将重新生成提议号N，再次返回第一阶段，并发起准备请求。接受者：接受者收到接受请求后，接受者分为两种情况：

　　如果发送的建议请求N大于之前保存的RespN，接受建议，设置AcceptN=N，AcceptV=V，回复ok。如果发送的建议请求n小于或等于之前保存的RespN，则不接受，不回复或回复错误。提议者：如果提议者收到一半以上的ok，则选择V，否则重新发起准备请求。

　　第三阶段：学习阶段。

　　学习者：在提议者得到大多数接受者的接受后，形成决议，并将形成的决议发送给所有学习者。

　　Paxos应用案例前面描述了paxos算法的细节，可能你还不明白Paxos算法在实际场景中有什么用。现在来说一个实际的用例。

　　我们以一个分布式KV数据库为例，分析Paxos的应用场景。

　　三台服务器组成一个分布式内存数据库，它们的状态必须同步，即每个服务器节点需要维护一个有序的操作日志，同时保持一致。

　　- -

　　1 Put(a ，1)

　　- -

　　2 Put(b ，2)

　　- -

　　3 Put(c ，3)

　　-当多个客户端并发发送请求时，服务器的多个节点需要协商，选择一个大家都认可的数据(指令)，存储在操作表中。这里协商和确定指令的过程就是Paxos。

　　例如，我们将paxos算法封装成以下方法：

　　Op doPaxos(int seq，Op v){.}用上面举例说明的例子详细划分这个过程：

　　Cient2向群集发送了一个请求Put(b ，2)，并假定此请求最终到达了server1。客户机3向群集发送了一个请求Put(c ，3)，假定此仲裁是发送给服务器2的。Server2调用doPaxos函数进行协商，即询问集群中的所有服务器我们的第二个操作是否可以放( c ，2)。此时服务器3也调用doPaxos函数进行协商，即询问集群中的所有服务器我们的第二个操作是否可以放( c ，3)。这是Paxos只会选择其中一个建议。这里我们假设server2的主题最终被传递，put (c ，2)被添加到集群中所有服务器的状态表中。当server3发现他的提议没有被选中时，他会放( b ，2)他的数据库，然后再次升级提议号，再次调用doPaxos方法，直到他的提议被通过。总结Paxos算法相当难懂。如果你对整个推导过程感兴趣，可以阅读Lamport的原文。

　　根据上面描述的Paxos算法流程，不知道大家有没有发现一个问题。如果两个Propser依次提出数量递增的提案，最终会陷入死循环，进入死锁状态，如下图所示：

　　我们可以通过选择主提议者来保证Paxos算法的活性，这就是ZAB协议的起源。

　　版权归作者所有：原创作品来自博主、程序员，转载请联系作者获得授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。