介绍

本文聚焦高并发场景下分布式一致性算法的分析和讨论

分布式场景下困扰我们的 3 个核心问题（CAP）：一致性、可用性、分区容错性。

1、一致性（Consistency）： 无论服务如何拆分，所有实例节点同一时间看到是相同的数据

2、可用性（Availability）： 不管是否成功，确保每一个请求都能接收到响应

3、分区容错性（Partition Tolerance）： 系统任意分区后，在网络故障时，仍能操作

点击查看大图

而我们最为关注的是如何在高并发下保障 Data Consistency（数据一致性），因为在很多核心金融业务场景（如 支付、下单、跨行转账）中，为了避免资金问题，是需要强一致性结果的。而分布式一致性算法就是保障 Data Consistency 的强大利刃，它的目标是确保分布式系统中多个节点在读取或修改同一份数据时，产生相同结果的关键机制。这些算法对于保证分布式系统的一致性和可靠性至关重要。常用的分布式算法：

1. Paxos 算法

2. Raft 算法

3. ZAB（ZooKeeper Atomic Broadcast）算法

2 主流分布式算法

2.1 Paxos 算法

Paxos 算法是一种用于分布式系统中保障一致性的算法，由 Leslie Lamport 于 1990 年提出，被广泛应用于分布式系统中的一致性问题，如分布式数据库、分布式存储系统等。该算法的主要目标是在一个由多个节点组成的分布式系统中，协调某个数据值并达成一致性，典型的少数服从多数的案例。

2.1.1 基本概念

1. 提案： 由提案号（id）和提案内容（value）组成，其中 id 主要用于实现 Paxos 算法，而 value 对应在实际的分布式系统中为所需要修改数据的命令 或者 log 信息。

2. 角色： Paxos 算法中抽象出来的概念，对应着实际分布式环境中的不同分工。主要角色包括提议者（Proposer）、批准者（Acceptor）和学习者（Learner）。

• 提议者负责提出值的提案

• 接受者负责接受提案并投票

• 学习者负责学习已经达成一致的值

点击查看大图

Proposer 提案者提案者负责提出提案 (Proposal)，Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。提案的 value，可以是任何行为或者操作，比如传统转账场景，将用户的账号余额从 0 改为 100，Paxos 协议统一抽象为 value。 Proposer 可以有多个，不同的 Proposer 可以提出不同的甚至互斥的 value，比如提案者 A 消费（将变量 Money-100），提案者 B 也消费（将变量 Money-200），但对同一轮 Paxose 而言，最多只有一个 value 可以被批准，否则就乱套了。

Acceptor 批准者 Acceptor 从含义上来说就是除了当前 Proposer 以外的其他机器，他们之间完全平等和独立，Proposer 需要争取超过半数（N/2+1）的 Acceptor 批准后，其提案才能通过，它倡导的“value”操作才能被所有机器（包括 Proposer、Acceptor、Learner）所接受。

Learner 学习者 Learner 不参与选举，而是学习被批准的 value，在 Paxos 中，Learner 主要参与相关的状态机同步流程。这里 Leaner 的流程就参考了 Quorum 议会机制，某个 value 需要获得超过半数的 Acceptor 批准，才能真正被 Learner 学习到。

2.1.2 算法流程

1. 准备阶段（Prepare 阶段）：提议者（Proposer）向所有 Acceptor 节点发起 Prepare 请求，携带全局唯一且递增的提案编号 N，要求它们告诉提议者已经接受的最高提议号。如果接受者接受了轮次小于当前轮次的提案，那么它会更新自己的状态，拒绝当前轮次的提案。

2. 承诺阶段（Promise 阶段） ：Acceptor 节点接收到 prepare 请求后，会检查该请求的提议号是否比它已经接受的提议号更高。如果是，那么节点会更新自己的状态，承诺不再接受轮次小于当前轮次的提案。

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

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

• 果 Acceptor 不是首次接收 Prepare 请求，则：若请求过来的提案编号 N 小于等于上次持久化的提案编号 ResN，则不响应或者响应 error。若请求过来的提案编号 N 大于上次持久化的提案编号 MaxN, 则更新 MaxN=N，同时给出正确的响应。

点击查看大图

3. 承诺响应阶段（Acknowledge 阶段） ：在这个阶段，接受者会检查自己是否接受了当前提案。如果是，那么接受者会返回一个承诺响应，告诉提议者当前提案已经被接受。4. 提议的接受与决策 ：当 Acceptor 节点接收到一个提议请求时，它会检查该提议的值是否比它已经接受的值更高。如果是，那么它会接受该提议，并向其他节点发送接受消息。当一个提议被大多数节点接受后，该提议就成为了决策，并被所有节点执行。

Proposer 获得 Accept 回复的信息之后，做如下判断：

• 回复数量 > Acceptor 数量的 1/2 时，代表提交 value 成功，发送广播给所有的 Proposer、Learner，通知它们已提交的 value。

• 回复数量 <= Acceptor 数量的 1/2 时，则重新开始，更新生成更大的提案号，跳转到准备阶段执行。

• 收到响应 error 时，同样更新生成更大的提案号，转到准备阶段执行。

点击查看大图

5. 学习阶段（Learn 阶段） ：学习者会向所有接受者发送一个学习请求，接受者会返回已经接受的最大提案，使学习者能够学习到已经达成一致的值。

2.1.3 应用

Paxos 算法具有高度容错特性，可以在某个节点宕机、网络异常、消息延迟等问题的情况下，快速且正确地在集群内部对某个数据达成一致。所以在很多业务场景中得到应用。比如：

• Zookeeper 使用一个类 Multi-Paxos 的共识算法作为底层存储协同的机制。

• Google 公司在其分布式锁中应用了 Multi-Paxos 算法。

2.2 Raft 算法

2.2.1 基本概念

Raft 算法是一致性算的一种，用来解决分布式一致性问题。它提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。其主要目标是解决分布式系统中的领导者选举、日志复制和安全性等关键问题。

2.2.2 领导者选举与超时机制

在 Raft 算法中，服务器可以处于三种状态：领导者（leader）、跟随者（follower）和候选者（candidate）。正常情况下，集群中只包含一个 leader ，其余服务器都是 follower 。跟随者通过投票选出领导者，只有得到“大多数”跟随者投票的服务器能成为领导者；领导者负责将命令同步给跟随者，只有被“大多数”跟随者确认的命令才能提交。

1. 跟随者(Follower)Fllower 是所有节点的初始状态，内部都会有一个随机超时时间。这个超时时间，规定了在倒计时结束后仍然收不到 Leader 的心跳，Follower 就会转变为 Candidate。

2. 候选者(candidate)Follower 在转变为 Candidate 后，超时时间重置，倒计时结束时就会向其他节点提名自己的实，拉取选票。如果能获得半数以上（1/2 以上,包含自己投给自己的）的选票，则当选为 Leader，这个过程就叫做 Leader 选举。所以节点最好是单数，避免极端情况下出现一个集群选举出两个 Leader 的脑裂问题。

3 .领导者(leader)Raft 集群通过 Leader 与客户端进行交互，Leader 不断处理写请求与发送心跳给 Follower，Follower 在收到 Leader 的心跳后，其超时时间会重置，即重新开始倒计时。正常工作期间只有 Leader 和 Follower，且 Leader 至多只能有一个。

角色状态转换过程

点击查看大图

2.3 ZAB（ZooKeeper Atomic Broadcast）算法

2.3.1 基本概念

ZAB（Zookeeper Atomic Broadcast）是 Zookeeper 原子消息广播协议，是 Zookeeper 保证数据一致性的核心算法。该算法借鉴了 Paxos 算法，但又不像 Paxos 那样是一种通用的分布式一致性算法，而是特别为 Zookeeper 设计的支持崩溃恢复的原子广播协议。在 Zookeeper 中，主要依赖 ZAB 协议来实现数据一致性。基于该协议，Zookeeper 实现了一种主备模型（即 Leader 和 Follower 模型）的系统架构，保证集群中各个副本之间数据的一致性。通过一台主进程（Leader）负责处理外部的写事务请求，然后将数据同步到其他 Follower 节点，如果超过半数成功 ACK，则主进程执行 Commit 操作。

2.3.2 广播流程

点击查看大图

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似一个 二阶段(2PC) 提交过程。对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数成功响应，则执行 Commit 操作（先提交自己，再发送 Commit 给所有 Follwer）

3 总结

分布式一致性算法是确保分布式系统中多个节点在读取或修改同一份数据时，产生相同结果的关键机制。这些算法对于保证分布式系统的一致性和可靠性至关重要。目前常见以下是一些常用的分布式一致性算法：

1. Paxos 算法：由 Lamport 宗师提出，是一种基于消息传递的分布式一致性算法。它旨在解决在一个可能发生故障的分布式系统中，如何快速正确地在集群内对某个值达成一致，并保证整个系统的一致性。

2. Raft 算法：一种相对易于理解的分布式一致性算法，它将一致性问题的复杂性分解为若干个相对独立的子问题。Raft 通过选举和日志复制的方式确保数据的一致性。

3. ZAB（ZooKeeper Atomic Broadcast）算法：是 ZooKeeper 中使用的原子广播协议，用于实现分布式系统中的状态同步。ZAB 协议包括恢复模式和广播模式，确保 ZooKeeper 集群中的各个节点能够保持数据的一致性。

此外，还有其他分布式一致性算法，如 Gossip 协议等，这些算法在不同的分布式系统场景中有各自的应用和优势。

在选择分布式一致性算法时，需要考虑系统的规模、节点的数量、通信开销、数据一致性要求以及容错性等因素。不同的算法可能适用于不同的场景，因此需要根据具体情况进行选择和调整。

文章转载自：Hello-Brand 

原文链接：https://www.cnblogs.com/wzh2010/p/18031245

体验地址：http://www.jnpfsoft.com/?from=infoq