深入浅出理解分布式一致性Paxos算法

概述

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。本文的目的就是带领大家深入浅出理解Paxos算法，理解它的执行流程，然后通过一个例子来了解Paxos算法在分布式系统中起到的作用。如果有能力的同学可以直接拜读原文。

分布式一致性

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

如果不保证一致性，那么就说明这个系统中的数据根本不可信，数据也就没有意义，那么这个系统也就没有任何价值可言。

在分布式系统中，各个节点之间需要进行通信来保持数据的一致性，而通信的实现方式有共享内存和消息传递两种模型。基于消息传递通信模型的分布式系统，不可避免的会发生下面的错误：机器宕机，进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。那么在这种复杂的情况下该如何保证一致性呢？

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

注： 这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令，根据应用场景不同，某个数据的值有不同的含义。

Paxos算法描述

Paxos算法的目标：在分布式环境下确定一个值，这个值被所有节点承认。

角色

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
• Acceptor: 参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数

Acceptors的接受，则称该Proposal被批准。

• Learner: 不参与决策，从Proposers/Acceptors学习最新达成一致的提案(Value)。

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。

算法流程

Propser有两个重要属性，提案编号N, 提案V, 简记 Proposer(N, V)。

Acceptor有三个重要属性，响应提案编号ResN, 接受的提案编号AcceptN, 接收的提案AcceptV， 间记Acceptor(ResN, AcceptN, AcceptV)。

第一阶段: Prepare准备阶段

Proposer： Proposer生成全局唯一且递增的提案编号N,，向所有Acceptor发送Prepare请求，这里无需携带提案内容，只携带提案编号即可, 即发送 Proposer(N, null)。

Acceptor： Acceptor收到Prepare请求后，有两种情况：

1. 如果Acceptor首次接收Prepare请求, 设置ResN=N， 同时响应ok
2. 如果Acceptor不是首次接收Prepare请求，则：

• 若请求过来的提案编号N小于等于上次持久化的提案编号ResN，则不响应或者响应error。
• 若请求过来的提案编号N大于上次持久化的提案编号ResN, 则更新ResN=N，同时给出响应。响应的结果有两种，如果这个Acceptor此前没有接受过提案， 只返回ok。否则如果这个Acceptor此前接收过提案，则返回ok和上次接受的提案编号AcceptN, 接收的提案AcceptV。

第二阶段: Accept接受阶段

Proposer： Proposer收到响应后，有两种情况：

1. 如果收到了超过半数响应ok, 检查响应中是否有提案，如果有的话，取提案V=响应中最大AcceptN对应的AcceptV，如果没有的话，V则有当前Proposer自己设定。最后发出accept请求，这个请求中携带提案V。
2. 如果没有收到超过半数响应ok, 则重新生成提案编号N, 重新回到第一阶段，发起Prepare请求。

Acceptor： Acceptor收到accept请求后，分为两种情况：

1. 如果发送的提案请求N大于此前保存的RespN,接受提案，设置AcceptN = N, AcceptV=V, 并且回复ok。
2. 如果发送的提案请求N小于等于此前保存的RespN，不接受，不回复或者回复error。

Proposer： Proposer收到ok超过半数，则V被选定，否则重新发起Prepare请求。

第三阶段: Learn学习阶段

Learner: Proposer收到多数Acceptor的Accept后，决议形成，将形成的决议发送给所有Learner。

Paxos应用案例

前面讲述了paxos算法细节，可能你还是不明白paxos算法在实际场景中有什么用处，我们现在讲个实际的使用案例。

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

3个server组成一个分布式内存数据库，他们的状态必须保持同步，也就是每个server 节点都需要维护有顺序的操作日志，同时保持一致。

+---+-------------+
|1  |Put("a", 1)  |
+---+-------------+
|2  |Put("b", 2)  |
+---+-------------+
|3  |Put("c", 3)  |
+---+-------------+
 

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

比如我们将paxos算法封装到下面的方法中：

Op doPaxos(int seq, Op v){...}
 

以上面图示的例子详细分下这个过程：

1. Cient2向集群发送了请求Put("b", 2),假设这个请求最终到了server1上。
2. Client3向集群发送了请求Put("c", 3), 假设这个求情发到了server2上。
3. server2调用doPaxos函数进行协商，即询问集群中的所有server咱们的第2个操作能否为Put("c", 2)
4. 此时server3也调用doPaxos函数进行协商，即询问集群中的所有server咱们的第2个操作能否为Put("c", 3)
5. 这是Paxos只会选择其中1个提案，我们这里假设server2的议题最终被通过了，集群中所有server的状态表都新增Put("c", 2)
6. server3发现自己的提案没有选中，他会对自己的database进行Put("b", 2)操作，然后重新升级提案编号，再次调用doPaxos方法，直到自己的提案被通过。

总结

Paxos算法还是挺难以理解的，如果对整个推导过程感兴趣的话，可以阅读Lamport的原文。

根据前面讲述的Paxos算法流程，不知道大家有没有发现一个问题，如果两个Propser依次提出编号递增的提案，最终回陷入死循环，进入死锁状态，如下图：

我们可以通过选取主Proposer，就可以保证Paxos算法的活性， 这样是ZAB协议的由来。