或许有人认为分布式技术，特别是分布式协议和算法，枯燥乏味、晦涩难懂，似乎离日常应用也很远。

当我对这些技术似懂非懂时，我才觉得算踏进了分布式世界的大门，分布式世界原来是那么的丰富而单调。丰富在于，各种分布式思想和技术...繁杂得乱花渐欲迷人眼；单调在于，当学会用分布式的角度去看周围的技术生态，种种万变不离其宗。

分布式协议和算法则是筑起分布式世界的基石。

概述

在分布式系统中，多台计算机节点通过网络进行通信和协作。而分布式协议可以帮助不同节点之间进行有效的协调和通信，保证系统的正确性和稳定性。

常见分布式协议和算法有 Paxos、Raft、Gossip、Quorum、ZAB、PoW。

在实际应用中，需要根据场景特点，在一致性、性能、可用性、容错性、实现复杂度之间权衡，选择合适的分布式协议和算法，来实现或解决分布式集群的故障探测、 避免脑裂、数据一致性、解决单点依赖连环套等功能/问题。

一致性

一致性有不同的理解维度。

简单可以划分为强制一致性和弱一致性。最终一致性是弱一致性的一种形式。

还可以分为

1. 事务一致性：关注多对象、多操作在单副本上的一致性。广义上的事务一致性被理解为 ACID 四个方面。

2. 数据一致性：关注单对象、单操作在多副本上的一致性。

• 【状态视角】状态一致性：数据客观状态的一致性，包括强一致和弱一致；只有全同步才能实现强一致性，但全同步会降低了系统的可用性。

• 【操作视角】操作一致性：允许数据客观存在短暂不一致，只要外部用户能够读到一致性数据。（下面的 Paxos、Raft 虽然实现了操作上线性一致性的算法，但从状态视角看也不是强一致的）

• 还能划分为线性一致性（全序关系）、顺序一致性、因果一致性（偏序关系）、最终一致性（只要保证写后读一致性、单调读一致性、前缀一致性）...

强一致性具有多种含义：

• 在埃里克.布鲁尔的猜想中，CAP 中的强一致性是指 ACID 的 C，系统状态一致性，可以通过分布式事务 2PC、TCC 实现。

• CAP 定理中，强一致性指原子一致性（线性一致性）；Paxos、Raft 能实现线性一致性。

一般而言，

• 在需要系统状态的一致性时，可考虑 2PC 协议、TCC。（在分布式事务中再介绍）

• 在需要数据访问的强一致性时，可考虑 Raft 算法。

• 在可用性优先的系统，可考虑 Gossip 协议实现最终一致性，Quorum NWR 提供强一致性。

容错性

Paxos，Raft 等算法无法对作恶行为进行容错，主要用于封闭、绝对可信的场景中，比如私链、内网。

拜占庭容错算法（如 Pow、PBFT），能容忍一定比例的作恶行为，可以应用于相对开放的场景中，比如公链、联盟链。

拜占庭容错是分布式领域一个复杂的容错模型，旨在解决分布式共识问题。

Paxos 算法

Paxos 是一种共识算法，包括 Basic Paxos 和 Multi-Paxos。

Basic Paxos 只能就单值达成共识，属于一个基础算法；大多数就某个值达成共识后，值就不再变了。如果要更新某个值，需要 Multi-Paxos 和状态机的支持。

Basic Paxos

【三种角色】

• 提议者 Proposer：接入和协调，收到客户端请求后，发起二阶段提交，进行共识协商

• 接受者 Acceptor：投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存

• 学习者 Learner：存储数据，不参与共识协商，只接受达成共识的值，存储保存。一般是数据备份节点

【共识协商】：通过二阶段提交的方式来达成共识

• 准备阶段 Prepare（会发现之前通过的提案的值，不会变）

• Proposer 分别向所有 Acceptor 发送包含提案编号 n1 的准备请求（这里不需要指定提议的值）

• Acceptor 响应提案：

• 尚无提案：并承诺以后不再响应编号小于等于 n1 的准备请求，不会通过编号小于 i 的提案

• 已响应提案 n2 且 n1 <= n2：丢弃准备请求，不做响应

• 已通过提案：在准备请求的响应中，包含已经通过的最大编号的提案信息（这里提案的值就是共识，不会再变）

• 接受阶段 Accept

• Proposer 收到大多数节点的准备响应后，分别发送接受请求

•  根据响应中提案编号最大的提案值，设置接受请求中的值；如果响应中为空，则设置自己的提议值

• Acceptor 接受请求

• 提案编号 < 承诺能通过的提案编号：拒绝

• 提案编号 >= 承诺能通过的提案编号：接受

• 当 Acceptor 通过了一个提案，就通知给所有的 Learner；Learner 发现大多数的 Acceptor 都通过了某个提案，那么它也通过该提案，接受该提案的值。

即使小于一半的节点出现故障时，Basic Paxos 的共识协商仍然在正常工作。

Multi-Paxos

Basic Paxos 只能实现单个值的共识，而且不能修改达成共识后的值；虽然可以通过多次执行 Basic Paxos 实例，来实现一系列值的共识，但是会存在以下几个问题：

• 如果多个 Proposer 同时提交提案，可能出现因为提案编号冲突，在准备阶段没有 Proposer 接收到大多数准备响应，协商失败，需要重新协商，甚至会循环。

• 2 轮 RPC 通讯往返消息多、耗性能、延迟大。

以上问题，可以通过以下方法来解决：

• 引入领导者（Leader）：作为唯一 Proposer

• 优化 Basic Paxos 执行：当 Leader 处于稳定状态时，省掉准备阶段，直接进入接受阶段

Multi-Paxos 算法是一个统称，是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法，比如 Chubby 的 Multi-Paxos 实现（代表 Multi-Paxos 思想在生产环境中的真正落地，将一种思想变成了代码实现）、Raft 算法等。

Raft 算法

Raft 算法也属于 Multi-Paxos 算法，不同之处主要有：

• 在 Raft 中，日志必须是连续的。日志较完整的节点更有可能当选领导者。

• 一个任期只有一位领导：通过任期编号、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则来保证，也极大减少选举失败的情况。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。通过客户端协议的配合，也能实现强一致性（即线性一致性）。

现代分布式系统中，Raft 算法比较常见，比如 etcd，Nacos, Eureka, TIDB 等。而 Paxos 因为算法复杂目前还没有成熟的开源实现。

不过 Raft 在复制效率上比 Paxos 稍差，比如顺序投票的限制，可能出现不必要的阻塞，带来额外的损耗。

成员身份

成员身份，或者说服务器节点状态：

• 领导者 Leader：一切以我为准（Raft 算法是强领导者模型）

• 处理写请求、管理日志复制和不断发送心跳信息

• 跟随者 Follower：接收和处理来自领导者的消息，当领导者心跳信息超时时，推荐自己当候选人

• 刚启动时所有节点都为 Follower 状态

• 候选人 Candidate：向其他节点发送请求投票消息，如果赢得大多数选票，晋升为领导者

主要流程

领导者选举

领导者选举关乎着节点故障容错能力和集群可用性，非常核心的设计。

• 初始阶段，集群中所有节点都是跟随者，可能有之前的任期编号和超时时间

• 发起领导者选举：节点 A 等待领导者节点心跳信息超时后，增加任期编号，推举自己为候选人，向其他节点发送请求投票消息

• 每个节点等待领导者节点心跳信息的超时时间间隔是随机的（避免某些条件下选举失败）

• 节点间通讯：请求投票消息和日志复制消息（由领导者发起，向其他节点复制日志和提供心跳消息）

• 先到先得投票：其他节点收到投票消息，如果在该编号下没有进行过投票，则把选票投给节点 A，并增加自己的任期编号

• 如果候选者或上一任领导者任期编号更小，会立即恢复成跟随者状态

• 节点 A 在选举超时时间内赢得了大多数的选票，就成为本任期内新的领导者；随后周期性地发送心跳消息给其他节点。

总结下选举规则：

• 在一次选举中赢得大多数选票的候选人，晋升为领导者

• 每个服务器节点最多只会对一个任期编号投出一张票，先来先投

• 在一个任期内，领导者一直都是领导者，直到它自身出现问题（如宕机）或网络延迟导致心跳消息无法及时发送给其他节点，其他节点则会发起新一轮选举

• 日志完整性高的跟随者，可以拒绝投票给日志完整性低的候选者

如果多个候选人同时发起选举，可能会导致选举持续失败。可以通过随机超时时间缓解这个问题：

• 跟随者等待领导者心跳信息超时的时间间隔是随机的

• 候选人在一个随机时间间隔内，没有赢得过半票数，选举无效

日志复制

在 Raft 算法中，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和应用日志项到状态机的过程。副本数据是以日志的形式存在的，包含用户指定的数据，比如指令，附加信息（索引值，任期编号等）。

日志复制流程：

• 接收到客户端请求后，领导者根据请求指令，创建一个日志项，并添加到本地日志中

• 领导者通过日志复制消息，将新的日志项复制到其他节点上

• 当日志项成功复制到大多数的节点上后，领导者才会将这条日志项应用到它的状态机中

• 领导者给客户端返回执行结果

• 这时不会马上通知跟随者：将二阶段提交优化为一阶段提交，降低了一半的消息延迟

• 当跟随者接收到心跳信息，或者新的日志复制消息后，会将领导者以及应用自己还没应用的日志项应用到本地的状态机中

当进程崩溃、服务器宕机时，会导致日志不一致，解决方案：

• 逐一对比：领导者通过日志复制的一致性检查，找到跟随者节点与自己相同日志项的最大索引值

• 领导者发送需要复制的日志项给跟随者（PrevLogEntry, PrevLogTerm）

• 若跟随者在本地状态机中没有找到与（PrevLogEntry, PrevLogTerm）一样的日志项，表示日志不一致，跟随者返回失败信息给领导者

• 领导者把更早前的日志项发给跟随者，直至找到与跟随者相同日志项的最大索引值

• 强制更新：领导者通过日志复制消息，强制跟随者更新覆盖的不一致日志项，实现日志的一致

通过以上选举规则和日志复制，Raft 算法保证了每个节点都执行相同序列操作，保证选举出来新的领导者一定包含先前已提交的日志。

成员变更

Raft 领导者选举，建立在大多数的基础上，当集群成员发生了变化，就可能同时存在新旧配置的 2 个大多数，出现 2 个领导者，破坏了 Raft 集群的领导者唯一性，影响集群的运行。

通过单节点变更解决：一次变更一个节点。正常情况下，不管旧的集群配置是怎么组成的，旧配置的大多数和新配置的大多数都会有一个节点是重叠的。

Step1：领导者（节点 A）向新节点（节点 D）同步数据

Step2：领导者（节点 A）将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项应用（Apply）到本地状态机，完成单节点变更。

Gossip 协议

Paxos 和 Raft 算法需要满足“大多数节点正常运行”原则，如果希望系统在少数服务节点正常运行的情况下，仍能对外提供稳定服务，这时就需要实现最终一致性。

Gossop 协议通过发送失败重传、反熵（随机选择节点互相交互数据消除差异）、谣言传播（周期性向其他节点发送新数据）等机制实现最终一致性。

Quorum NWR 算法

Quorum 协议是一种在分布式计算中用于达成共识的协议。它被设计用来解决拜占庭容错问题，确保系统能够在存在节点故障或恶意行为的情况下依然保持一致性。

• N，表示副本数（集群中同一份数据有多少个副本，不同数据可以有不同的副本数），又叫做复制因子。

• W，写一致性级别，表示成功完成 W 个副本更新，才完成写操作。

• R，读一致性级别，表示读取一个数据对象时需要读 R 个副本，返回 R 个副本中最新的那份数据。

在 AP 型分布式系统中，通常都会实现 Quorum NWR。

通过 Quorum NWR 设计，可以权衡前面提到的几个特征（一致性、性能、容错...）：

• W+R > N 时，能保证强一致性（注意客户端侧一致性模型，不是指线性一致性）

• W+R <= N 时，只能保证最终一致性

• W = N 时，对读友好

• R = N 时，对写友好

• W =（N+1）/2, R =（N+1）/2 时，容错能力较好

不同的写一致性级别：

• any：任何一个节点写成功，或写其他节点失败后本地节点上缓存写失败数据，返回成功

• one：至少一个节点写成功，返回成功

• quorum：大多数节点写入成功，返回成功

• all：所有节点写入成功，返回成功

ZAB 协议

ZAB 协议（ZooKeeper Atomic Broadcast）是为 ZK 设计的基于主备模式的原子消息广播协议，它可以保证集群数据的一致性和命令的全局有序性。（可靠传递、全局有序、因果有序）

ZAB 有两种基本的工作模式：崩溃恢复和消息广播。

集群和成员

【成员角色】

• Leader 领导者：同一时间集群只有一个

• Follower 跟随者：可以处理读请求，需要要把写请求转发给领导者处理

• Observer 观察者：可以看做没有投票权的跟随者

【成员状态】

• 选举状态 LOOKING：当成员认为集群没有 Leader，进入 LOOKING 状态，查找或者选举 Leader

• 跟随者状态 FOLLOWING：对应 Follower

• 领导者状态 LEADING：对应 Leader

• 观察者状态 OBSERVING：对应 Observer

【ZAB 状态/节点运行状态】：驱动节点状态变更，反应了节点从选举到对外提供服务过程的几个步骤

• 选举状态 ELECTION：各节点在进行 Leader 选举，最终选出一个 Leader

• 成员发现状态 DISCOVERY：各节点在协商沟通 Leader 的合法性，连接 Leader，检测 Leader 是否有变更

• 数据同步状态 SYNCHRONIZATION：各节点以 Leader 的数据为准，修复自己数据副本的一致性

• 广播状态 BROADCAST：各节点能正常接收客户端请求（只有集群大多数节点处于广播状态时，集群才能对外提供服务）

主要流程

领导者选举

【关键概念】

• zxID 是一个 long 型（64bit）整数，全局有序。包括任期编号 epoch（32bit）和计数器两部分。

• 投票信息内容：节点提议的领导者的集群 ID、任期编号、事务标识符最大值 proposedLastZxID，投票的节点。

【触发选举时机】

• 服务启动时整个集群没有 Leader 节点。

• 服务运行中，因为宕机、断电、延迟等导致 Leader 不能对外提供服务。

• 其他节点通过心跳检测到 Leader 失联后也会进入选举状态。

【领导者 PK 规则】：任期编号 Epoch > 事务标识符值 zxID > 集群 serverID

目标：选举出数据最完整的节点

【选举流程】

• 触发选举时机时，跟随者变更状态 FOLLOWING->LOOKING；增加选举轮次编号，推荐自己，发起领导者选举，把投票信息广播给所有节点；

• 周期性地从队列中读取接收其他投票信息

• 某节点接收到新的投票信息，根据领导者 PK 规则，调整选票信息后，需要把选票信息重新广播给所有节点

• 选举轮次大的节点不会接收来自值小的节点的投票信息

• 获取一半以上投票的节点把 LOOKING 修改为 LEADING ，其他节点修改为 FOLLOWING（之前发起选举的节点也退出选举）

选举出新领导后，还需要通过成员发现来确立领导关系；通过数据同步来恢复故障（解决各副本数据冲突），然后领导者才能行使领导职能，处理写请求。

成员发现

成员发现，确立领导者关系。

新的领导者选举出后，所有节点把自己的 ZAB 状态设置为 DISCOVERY，代表选举 ELECTION 阶段结束，领导者会对任期编号+1，创建新的任期编号，事务标识符也会重置。

• FOLLOWING 节点会主动发送 FOLLOWINFO 给领导者。（Raft 算法是领导者先发给跟随者）

• 领导者将 LEADINFO 消息（含新的任期编号和最大值的事务标识符）响应给跟随者

• FOLLOWING 节点接收到领导者的响应，判断任期编号是否最新/合法

• 是：返回 ACKEPOCH 消息给领导者；并设置 ZAB 状态为数据同步

• 否：发起新的选举

• 领导者阻塞等待，当接收到大多数节点的 ACKEPOCH 消息后，设置 ZAB 状态为数据同步

• 各节点就领导者的领导关系达成了共识

数据同步

数据同步，进行故障恢复。

为了高效复制提案，领导者将一定数量的已提交提案放在内存队列里：

maxCommittedLog 和 minCommittedLog 表示内存队列中已提交提案事务标识符的最大值和最小值；peerLastZxID 表示跟随者提案事务标识符的最大值。

• 领导者根据跟随者事务标识符最大值，采取不同方式处理不一致数据：

• TRUNC：回滚，maxCommittedLog < peerLastZxID

• DIFF：差异化同步，minCommittedLog <= peerLastZxID < maxCommittedLog

• TRUNC+DIFF：先回滚再同步，存在无效的提案

•  节点在退出跟随者状态时，会将所有本地未提交的提案都提交，但可能并未被复制到大多数节点上，故这些提案可能会被删除

• SNAP：全量同步，peerLastZxID < minCommittedLog；或 minCommittedLog/maxCommittedLog 为空，同步快照数据，直接覆盖跟随者本地数据

• 领导者给跟随者返回差异数据和 NEWLEADER 消息

• 跟随者修复不一致数据，返回 NEWLEADER 消息的确认响应给领导者

• 领导者接收到大多数节点对于 NEWLEADER 消息的确认响应后，领导者设置自己 ZAB 状态为广播，并发送 UPTODATE 消息给所有跟随者，通知他们数据同步已完成

• 当跟随者接收到 UPTODATE 消息时，也把 ZAB 状态设为广播

• 这时，集群才可以正常处理写请求（Raft 选举出新的领导者后，是可以立即处理写请求的）

• 当有新的节点加入正常工作的集群，那新节点会自动进入数据恢复模式，找到 Leader 服务器，并与其进行数据同步，然后再参与到消息广播流程中去。

提供服务

【写请求】必须在领导者上处理（若跟随者接收到了写请求，也需要转发给领导者）：只能通过分集群方式来突破写性能的限制。

# LOOKING 状态的节点不能处理读写请求，也不能转发写请求给领导者

• 领导者接收到写请求，通过事务生成器创建提案并持久化存储

• 领导者将提案广播给集群所有节点

• 跟随者接收到提案，持久化存储，并返回 ACK 给领导者

• 当领导者接收到大多数节点的 ACK 后，提交提案，并广播 COMMIT 消息给跟随者

• 跟随者接收到 COMMIT 消息后，提交提案（如果是自己接收到写请求，返回成功响应给客户端）

【读操作】

可以在任意节点上执行，查询本地数据（提交的数据存储在 dataTree 中，类似 Raft 的状态机）。

所以客户端可能会读到旧数据，客户端可以通过执行 sync 命令，读取最新数据。

可以水平扩展读性能。 

ZK 和 ZAB

ZK 集群选主服务器流程（使用 ZAB 协议，选举期间，集群不可用）：

• 读取/servers/leader 的值，并监听 path 的变化

• 有值，表示主服务器已经产生

• 无值继续下面流程

• 将自己的主机名写入/servers/leader（ZAB 算法保证只有一个服务器能写成功）

• 写入成功，成为主服务器（如果当前程序崩溃，ZK 会删除临时路径，其他监听这个路径的服务器会收到通知，所有服务器重新选举主服务器）

• 写入失败，从头再来

Zookeeper 是以类似目录结构的数据结构存储数据的，要求命名的有序性。ZAB 协议保证了有序性。

如何保证操作有序性：通过“一切以领导者为准”的强领导者模型和严格按照顺序处理、提交提案，来实现操作的有序性。

• 主节点基于 TCP 协议，按照顺序把提案广播到其他节点，保证了先发送的消息先被收到（UDP 不能保证）

• 节点之前会维护一个 FIFO 队列，保证全局有序性

• 通过全局递增的 zxID 保证因果有序性：主节点接收到写请求，会基于指令创建 Proposal，使用 zxID 唯一 ID 标识；并根据事务标识符大小，按照顺序提交提案

Raft 和 ZAB

相同点：

• 主备模式：领导者、跟随者模型

• 日志复制：日志必须连续、按顺序提交；以领导者日志为准实现日志一致

• 成员变更：Raft 和 ZAB 都支持

• 写操作：必须在领导节点上处理

差异点：

• 领导者选举：ZAB（相互推荐的领导者选举）；Raft（先到先得选票，通讯消息数更少，选举更快）

• 读操作和一致性：ZAB（最终一致性）；Raft（强一致性，也可提供最终一致性）

• ZAB：follower 主动发送 followInfo 给 leader；Raft：leader 给 follower 发送心跳信息

• ZAB 和 ZK 强耦合；Raft 可以独立使用，Raft 设计更为简洁（Raft 没有引入类似 ZAB 的成员发现和数据同步阶段）

参考资料：韩健《分布式协议与算法实战》

下期预告：【分布式技术】分布式锁和 ID