分布式一致性算法：Paxos算法

type

status

date

slug

summary

1、分布式一致性

1.1 什么是分布式一致性算法

分布式系统通常由异步网络连接的多个节点构成，每个节点有独立的计算和存储。由于网络延迟、节点故障等原因，可能导致不同节点上的数据不一致。分布式一致性算法就是为了解决这个问题而诞生的。简单来说，一致性算法就是保证在多个节点中，同一时间点的数据视图是一致的。

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

1.2 分布式一致性算法的分类

根据数据一致性的强弱程度，分布式一致性算法可以分为强一致性和弱一致性。

1.2.1 强一致性

强一致性要求系统改变提交以后立即改变集群的状态。也就是说，当一个节点更新数据后，其他节点必须立即看到这个更新。Paxos、Raft 和 ZAB 等算法是实现强一致性的典型代表。

Paxos 算法：Paxos 算法是 Lamport 于1990年提出的一种基于消息传递的一致性算法。它通过多轮投票的方式，确保所有节点对某个决策达成一致。Paxos 算法分为两个阶段：准备阶段和提交阶段。在准备阶段，节点向其他节点发送准备消息，收集他们的意见；在提交阶段，节点根据收集到的意见做出决策，并通知其他节点。

Raft 算法：Raft 算法是 Diego Ongaro 和 John Ousterhout 于2014年提出的一种为管理复制日志的一致性算法。Raft将一致性算法分解为几个相对独立的子问题，并通过选举 Leader、日志复制和安全性等机制来保证数据的一致性。 Raft 算法相较于 Paxos 更为简洁易懂，因此在实际应用中得到了广泛采用。

ZAB 协议：ZAB协议（ZooKeeper Atomic Broadcast Protocol）是 Apache ZooKeeper 使用的一种原子广播协议。它基于 Paxos 算法进行改进，通过选举 Leader、数据恢复和广播等阶段来保证集群中各个副本数据之间的一致性。ZAB协议在 ZooKeeper 的实现中，通过优化和简化，提高了系统的性能和稳定性。

协议	简介	优点	缺点	应用
Paxos	是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。又分为Basic Paxos、Fast Paxos和Multi-Paxos，而前两者只能对一个值形成决议，因此它们几乎只是用来做理论研究，并不直接应用在实际工程中。Raft 和 Zab 协议都是基于 Multi-Paxos 的变种。	• 高效。 • Paxos算法有严格的数学证明，系统设计精妙。	• 难以理解。 • 难以实现，达到工业级性能需要进行不同程度的工程优化，而有时工程设计的偏差会造成整个系统的崩溃。 • Base-Paxos可能出现活锁问题。 • 对于客户端来说无法满足操作的全序关系。	Google的Chubby、MegaStore、Spanner
Raft	由于 Paxos 算法过于复杂、实现困难，极大地制约了其应用，而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法，在此背景下，Raft 算法应运而生。 Raft 是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。	• 比其他两者算法更容易理解，⽽且更容易工程化实现。论文中就给出了伪码。 • Raft与Paxos一样高效，效率上Raft等价于(multi-)Paxos。 • Raft的日志设计使得整个算法非常的简洁，分成了几个功能独立的子版块。	• 无法容忍拜占庭将军问题，当然其他两者也不能容忍，后面就不提了。 • 总的来说Raft只是Paxos实现的一种，但是Raft身上的限制比较多，而Paxos在算法层面上更通用，所以相比于Raft，在Paxos的基础上进行优化，上限应该会更高，比如上面提到了两点。 • 因为日志的设计只能串行写入，并发场景下效率有损失；且在多事务的情况下有可能损害性能和稳定性。	redis cluster、etcd、tidb
Zab	基于 Paxos 算法实现的，不过 Zab 对 Paxos 进行了很多改进与优化。所以 Zab 但并不像 Paxos 那样是一种通用的分布式一致性算法，而是为 Zookeeper 专门设计的崩溃可恢复的原子广播协议。	• 保证了客户端FIFO的语义。 • 比Paxos简单。	ㅤ	zookeeper

1.2.2 弱一致性

这种一致性级别约束了系统在写入成功后，不承诺立即可以读到写入的值，也不具体承诺多久之后数据能够达到一致，但会尽可能地保证到某个时间级别（比如秒级别）后，数据能够达到一致状态。弱一致性还可以再进行细分：

会话一致性：该一致性级别只保证对于写入的值，在同一个客户端会话中可以读到一致的值，但其他的会话不能保证。

用户一致性：该一致性级别只保证对于写入的值，在同一个用户中可以读到一致的值，但其他用户不能保证。

1.2.3 最终一致性

最终一致性是弱一致性的一个特例，系统会保证在一定时间内，能够达到一个数据一致的状态。这里之所以将最终一致性单独提出来，是因为它是弱一致性中非常重要的一种一致性模型，也是业界在大型分布式系统的数据一致性上比较推崇的模型。

1.3 分布式一致性算法的应用

分布式一致性算法在许多领域都有广泛的应用，如数据库、缓存、消息队列等。例如，在分布式数据库中，为了保证各个节点上的数据一致，就需要使用一致性算法。在缓存系统中，当多个节点同时更新同一个缓存项时，也需要通过一致性算法来确保缓存的一致性。此外，在分布式系统中实现分布式锁、选举等功能时，也需要借助一致性算法来保证系统的正常运行。

2、Paxos算法

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

Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。Paxos 算法就是如何快速正确的在一个分布式系统中对某个数据的值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

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

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

2.1 角色

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

Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

Acceptor: 参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数

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

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

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

2.2 算法流程

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 请求后，有两种情况：

如果 Acceptor首次接收 Prepare请求，设置ResN=N，同时响应ok

如果 Acceptor 不是首次接收 Prepare请求，则：

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

第二阶段: Accept接受阶段

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

如果收到了超过半数响应 ok, 检查响应中是否有提案，如果有的话，取提案 V = 响应中最大 AcceptN 对应的 AcceptV，如果没有的话，V 则有当前 Proposer 自己设定。最后发出 accept 请求，这个请求中携带提案 V。

如果没有收到超过半数响应 ok, 则重新生成提案编号 N, 重新回到第一阶段，发起 Prepare 请求。

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

如果接受到的提案请求 N 大于等于此前保存的 RespN,接受提案，设置 AcceptN = N，AcceptV=V，并且回复ok。

如果接收到的提案请求 N 小于此前保存的 RespN，不接受，不回复或者回复error。

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

第三阶段: Learn学习阶段

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

2.3 Paxos应用案例

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

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

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

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

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

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

Client2 向集群发送了请求 Put("b", 2)，假设这个请求最终到了 server1 上。

Client3 向集群发送了请求 Put("c", 3)，假设这个求情发到了 server2 上。

server2 调用 doPaxos 函数进行协商，即询问集群中的所有 server 咱们的第 2 个操作能否为 Put("b", 2)

此时 server3 也调用 doPaxos 函数进行协商，即询问集群中的所有 server 咱们的第 2 个操作能否为 Put("c", 3)

这是 Paxos 只会选择其中 1 个提案，我们这里假设 server2 的议题最终被通过了，集群中所有 server 的状态表都新增 Put("c", 2)

server3 发现自己的提案没有选中，他会先接受被通过的方案，对自己的 database 进行 Put("b", 2) 操作，然后重新升级提案编号，再次调用 doPaxos 方法，直到自己的提案被通过。

2.4 Paxos算法优化

2.4.1 通过选取主Proposer保证算法的活性

假设存在这样一种极端情况，有两个 Proposer 依次提出了一系列编号递增的议案，但是最终都无法被选定，具体流程如下：

Proposer P1 提出了一个编号为M1的提案，并完成了上述阶段一的流程。

另外一个 Proposer P2 提出了一个编号为 M2(M2＞M1) 的提案，同样也完成了阶段一的流程，于是 Acceptor 已经承诺不再批准编号小于 M2 的提案了。

当 P1 进入阶段二的时候，其发出的 Accept 请求将被 Acceptor 忽略，于是 P1 再次进入阶段一并提出了一个编号为 M3(M3＞M2) 的提案

P2 在第二阶段的 Accept 请求被忽略，以此类推，提案的选定过程将陷入死循环。如下图所示：

为了保证 Paxos 算法流程的可持续性，以避免陷入上述提到的“死循环”，就必须选择一个主 Proposer，并规定只有主 Proposer 才能提出议案。这样一来，只要主 Proposer 和过半的 Acceptor 能够正常进行网络通信，那么但凡主 Proposer 提出一个编号更高的提案，该提案终将会被批准。当然，如果 Proposer 发现当前算法流程中已经有一个编号更大的提案被提出或正在接受批准，那么它会丢弃当前这个编号较小的提案，并最终能够选出一个编号足够大的提案。因此，如果系统中有足够多的组件（包括Proposer、Acceptor和其他网络通信组件）能够正常工作，那么通过选择一个主 Proposer，整套Paxos算法流程就能够保持活性。

3、总结

分布式系统通常包含多个节点，每个节点上保存一份数据副本。因为网络通讯故障、单点故障等各种原因，多个节点可能会出现数据不一致的问题。分布式一致性算法就是用来保证多个节点上的数据副本可以对外提供统一的视图。

分布式一致性算法按数据一致性的强弱程度，分为强一致性、弱一致性和最终一致性。

分布式一致性算法的实现有 Paxos 算法、Raft 算法和 Zab 算法。其中 Paxos 算法是业界公认的解决数据不一致性问题最有效的分布式一致性算法之一，后两者算法都是基于 Paxos 算法的变种。

Paxos 算法包含三种角色：

Proposer（提案提出者）：用于提出一个提案 P<N, V>，其中 N 是提案名，V 是提案值。
Acceptor（提案决议者）：用于决策通过哪一个提案。
Learner（提案学习者）：不参与提案的提出和决策过程，只是接受已经通过的提案。

Paxos 算法过程类似于 2PC，分为两个阶段

Prepare 阶段：

Proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求。
如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话） 作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。

Accept 阶段：

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

参考

《Paxos到Zookeeper：分布式一致性原理与实践》

‣