分布式协议与算法

我重生了，重生在刚刚接触分布式的那一天晚上，这一世，我要成为分布式高手，而拦在我面前的第一关，就是分布式协议与算法…

施法前摇：[X::分布式协同]来自分布式技术通识篇的旧事重提

如果看完了那两篇有关分布式通识的博客，一定还记得我最后都没填的那个坑：分布式式协同。倒不是自己懒病犯了，分布式协议和算法是一个比较复杂和重要的模块，后面篇幅太短写不下，所以挖了个大坑。这篇文章就是专门为此开的番外篇，从这里开始学习为了实现分布式协同，全世界的天才们都开发出了哪些脑洞和技术。

分布式协议与算法的起源：CAP理论

显而易见的是，分布式协议与算法就是为了解决分布式协同问题而诞生的。原本的分布式协同问题只是指：如何让一个分布式系统中的各个节点保持共识，保障数据和状态的一致性，这便是分布式算法和协议要解决的一个核心问题：一致性。但是只解决这个又不够，一部分分布式系统是没有那么强的一致性需求的，反而高可用才是最重要的需求，在可用性和一致性的斗争中，分布式系统也迎来了我们熟悉的一个理论：CAP理论。

CAP 理论（CAP Theorem），又称布鲁尔定理（Brewer’s Theorem），是由计算机科学家 Eric Brewer 在 2000 年提出的一个关于分布式系统的理论。CAP 理论指出，在一个分布式系统中，不可能同时满足以下三个特性：

• 一致性（Consistency）
• 可用性（Availability）
• 分区容错性（Partition Tolerance）

分区容错性是所有分布式系统必然需要满足的特性，不然和单机有什么区别，总不能一个机器坏了整个系统就崩了。在满足P的前提下，C和A就鱼和熊掌不可兼得了。

C/A的边界其实出现在分布式通信导致的网络分区的问题上：

• 当网络分区发生时，如果要满足一致性，就必须保证所有节点都要同步通信来同步状态数据，那就无法在发生节点网路故障的时候实时提供服务，即丧失可用性。
• 如果要满足可用性，节点往往会不管系统中一部分节点的故障和状态不同仍然要坚持对外提供服务，此时整个系统就失去了一致性。

CAP 理论很经典也很有普适性，但是有一个很不友好的问题，那就是太过于严苛，CAP 的一致性指的是整个系统的强一致性，可用性指的是系统可以提供所有服务的全可用。这些显然是一个系统的边界条件，很难落地实践。

分布式协议和算法的指标：2+1+0

叠个甲，这个 2+1+0 是笔者自己定义的指标，并不代表主流观点，如有反对，以大家自己的心里的标准为准。

根据 CAP 理论，我们很容易就能想到，度量一个分布式协议算法的最基本指标有两个：可用性，一致性。除开这些基本指标，剩下的还有一些指标我们也可以很容易想到，比如性能，安全性，这就构成了评判分布式协议算法的 2+1+0 标准：可用性&一致性 + 性能 + 拜占庭容错

至于为什么是 2+1+0 标准呢，我们好好说一说 0 代表的指标：安全性::拜占庭容错

拜占庭容错

一般来说，我们自己的分布式系统都是部署在自己的私有云上的，公网上面会有一个网关来保障整个系统外围的安全性，内部节点之间都是默认信任亲如手足的，这是现在大多数分布式系统的姿态。

然而，莱斯利·兰波特在 1982 年提出了一个问题，如果是一个去中心化的分布式对等网络，这些网络的节点还并非是我们能全局可控的，比如区块链网络，节点里面出现叛徒或智障传递错误消息怎么办，还如何保证一致性。这个问题就叫拜占庭将军问题The Byzantine Generals Problem。

蠢和坏在某些时候带来的结果是一样的

拜占庭容错核心问题：在没有上帝全局视角的情况下，节点还会传错误消息的情况下，我们如何完成一次保障一致性并且不受错误消息干扰的通信。

在这里定义一下错误消息：并不是服务器在本该回应 YES 的时候回应了 NO 这种错误，而是服务器给不同节点通信的同一个消息内容不一样。此时不同节点对同一个消息的共识就混乱了，这便是拜占庭问题里的错误消息的定义。

针对拜占庭问题的解决方案有很多种，比如论文里面提到的 3M+1 策略递归，可以至少容忍 M 个问题节点，比如通过消息签名，快速定位错误消息。正式使用的有区块链常用算法有 PoW，PoS。

以后有时间细聊。解决拜占庭问题往往会带来另一个问题：可用性和性能很差，必须采用强可靠强一致的分布式协议。

一致性的天花板：分布式事务

事务的本质是 ACID，是对一致性的更高扩展和更严格的要求，事务不但要求严格的强一致性，还提出了原子性和隔离性的要求（当然持久化这个是基础项，本质上可以看作一种有状态系统的状态更新），这其中就涉及到很多有关版本控制和事务并发的复杂问题，这里就不多讨论该怎么做了，我们先从一个最简单的无并发事务的角度来了解，实现事务的协议有哪些。

2PC:两阶段提交

两阶段提交方案需要一个协调者的角色，客户端上传事务给协调者，在准备阶段协调者在将事务信息给其他节点同步，首先询问所有节点是否可以进行事务，得到全部肯定答复之后，在执行阶段，发起所有节点执行事务的请求，再次等到所有节点的完成答复之后，事务结束。

原始的两阶段提交有两个特征：所有参与事务的节点，如果在准备阶段，**确认了事务可以执行，就只能执行，不许取消，哪怕节点故障或被替换也不允许事务取消（失败另说）。**其次，所有节点会在准备阶段完成后对资源上锁，保证事务能正常运行，这段期间内不允许任何对资源的操作，严重影响并发性。

同时，在两阶段提交的过程中，协调者存在巨大的单点通信压力和严重的单点故障风险，因为如果准备阶段结束后协商者挂掉了，那很显然会有一群参与者锁着资源等调度，导致系统严重宕机。

两阶段提交是一个很简单也很直观的实现分布式事务的模型，但是太过简单，就很难有高性能的表现。现在主流的分布式数据库的事务协议是 XA 协议，比如 MySQL XA，这个协议基于两阶段协议开发的 DTP 模型，算两阶段提交的升级优化版本。

两阶段提交还有个升级版本叫 3PC 一看也就知道是干嘛的，所以不展开。

TCC:Try-Confirm-Cancel

TCC 协议和两阶段有一点性质上的不同：两阶段提交或者 XA 协议是一个数据层上的事务设计方案，对于客户端来说是无感的，对业务也是没有侵入性的，每个客户端都不需要关心事务的具体内容和执行方案，只需要发起和等待结果，但是 TCC 协议却要求客户端自己去考虑事务的执行和补偿方案，并且自己去安排协调各个节点事务的一致性。

TCC 的事务方案称为补偿性事务方案，补偿性事务是指在事务失败后执行补偿行为来保证所有节点恢复到开始状态，保障事务的最终一致性，和回滚操作的强一致性+原子性保障不同，补偿事务允许在事务执行期间系统处于一段时间的不一致状态，这个时间可能长达好几秒。

TCC 协议由客户端在业务层实现，对于服务节点来说反而是偏向无感的：

客户端首先需要尝试（try）向系统注册事务，即向所有节点广播，参与者节点收到广播后会**预留事务资源（由客户端配置，有可能不够用）**并响应“事务注册成功”，如果不是所有节点都响应成功，则事务失败。

然后客户端会本地提前设计好两种任务：Confirm 任务和 Cancel 任务，一个用于执行事务，一个用于撤销事务。这两种任务需要客户端针对不同的服务节点独自设计（所以才说业务侵入性大，因为在我们写业务代码的时候还得去特地写这些），在得到 try 成功的响应后发送 Confirm 任务，交给所有参与者节点执行，并等待所有参与者节点响应，全部响应成功则事务完成。

如果并非全部响应成功，则任事务失败，需要回滚，但这个时候就不是服务节点自己回滚了，有的节点是缓存，有的节点是数据库，有的节点是无状态的节点，不用回滚，这些都需要服务器自己去设计 Cancel 的方案，并且交给所有参与者节点执行，参与者节点执行完成了，返回任务失败。

一般来说，事务失败是因为资源不够或者任务有问题才导致，服务节点自身的异常是系统故障，要考虑的是容灾和故障问题。
如果参与者节点连 Cancel 任务都执行失败了，那就是服务器异常，该做故障隔离和恢复了。

BASE 理论：正好够用胜过完美系统

先叠个甲，Base理论很多人看来是一种对 AP 方案的扩展衍生，但笔者不这么认为，不过你反对就是你对。

在 CAP 理论中，作者的观点是：因为网络分区的问题，强一致性，高可用，和区域容灾在一个分布式系统中无法全部满足。

这个理论里面 Consistency 的定义是强一致性：在每一个瞬间系统的每一个机器都拥有相同的状态视图。按照这个 CP 的视角来看，TCC 这种分布式事务协议都算不上严格意义的 CP，因为 TCC 是可以容忍在正常情况下一段时间里面整个系统状态的不一致，并采用补偿事务的方式完成最终一致性的，甚至很多采用弱一致性的分布式数据库，都算不上CP。

同时，Availability 高可用性要求也十分严格，每一个请求都能返回非错误的响应，很多大企业都只有 6N 的可用性，实际上目前来看的所有的AP方案，也都只是尽力在很大程度上保证了高可用而已。

所以 C 纬度有了向下妥协的弱一致性，最终一致，A 纬度也自然有向下妥协的 6N，4N，2N 不同程度的高可用。

BASE 理论是 CAP 落地实际生产带来的经验总结，CAP 只是分布式系统性能的边界，实际生产里面我们需要什么指标的系统，才是 BASE 理论给出的答案。

BASE 理论的指标：

• Basically Available 基本可用
• Soft state 软状态/中间状态
• Eventual consistency 最终一致性

GFS 就是 BASE 理论的一个践行者，这个系统既不强一致性（影子读节点异步复制，数据流式传输向 chunk，并且会带来坏区），也不高可用（其实已经够可用，但一群廉价机器并且每个节点都只有2个副本怎么可能保证100%没有意外），但当时对于一个实际的分布式系统来说设计简直优秀。

前摇结束：正式开始学习分布式算法

Paxos 算法

Paxos 算法是很多分布式算法的基础，也是个比较简单的算法，我们先从这个简单的算法开始了解。设计一个简单场景，对于一个分布式 KV 存储系统，在接受写入一个新的键值对的时候，如何让所有的节点保持一致性达成共识？

Paxos 算法涉及三个主要角色：

1. 提议者（Proposer）：提出提案并寻求接受者的批准。
2. 接受者（Acceptor）：接受或拒绝提案，参与投票过程。
3. 学习者（Learner）：了解最终达成的决策。

Paxos 算法的核心步骤可以分为两个阶段：

1. Prepare 阶段：提议者提出准备请求，接受者回应。
2. Accept 阶段：提议者提出提案，接受者投票。

Paxos 算法的详细流程

1. 阶段 1：Prepare 阶段
   • 提议者生成一个唯一的提案编号 n，并向所有接受者发送 Prepare(n) 请求。
   • 接受者收到 Prepare(n) 请求后，进行以下操作：
     • 如果 n 大于接受者之前响应的所有提案编号，则接受该请求，并承诺不再接受编号小于 n 的提案。接受者记录下承诺的提案编号 n 和已接受的最大提案 proposal.
     • 接受者向提议者发送 Promise(n, proposal) 响应，其中 proposal 是接受者已接受的最大提案。
2. 阶段 2：Accept 阶段
   • 提议者收到多数接受者的 Promise 响应后，选择一个提案值 v（如果有已接受的提案，则选择编号最大的提案值，否则选择新的提案值），并向所有接受者发送 Accept(n, v) 请求。
   • 接受者收到 Accept(n, v) 请求后，进行以下操作：
     • 如果 n 大于或等于接受者之前承诺的提案编号，则接受该提案并记录提案值 v。接受者向提议者发送 Accepted(n, v) 响应。
     • 如果 n 小于接受者之前承诺的提案编号，则拒绝该提案。
3. 阶段 3：达成一致
   • 提议者收到多数接受者的 Accepted 响应后，认为提案 v 已被接受，并将该提案值通知所有学习者。
   • 学习者收到提议者的通知后，记录并了解最终达成的一致决策。

大多数节点同意算是一个容错机制，可以保证在一半节点宕机的时候对串行提议依旧能正常完成协商。

Paxos 协议是一个支持并发的强一致性方案，支持多个请求和提案并发执行，仍然能保证强一致性。

Paxos 协议保证共识的强一致性，但不保证共识的执行顺序，也不关心最后的共识是什么。

这一系列过程就是 Paxos 协议的流程，这个流程十分简单，细节上也不太完善，Paxos 算一个非常基础简单的思想，作为一个开创者深刻影响了后续的很多分布式算法。

如果我们提案者节点减少为1，就可以跳过准备阶段，此时提案没有并发性，但是性能却不会下降，因为省去了第一阶段协商共识的时间，这种方案称为 Multi-Poxos 方案，选举一个稳定的领导者去安排提案的准备的共识。

如果我们将接受者的总数量减少为1，也就是一个接受者和多个学习者，就变成了我们熟悉的一主多从的一致性场景，可以直接省去提案的接受阶段的共识协商时间直接进入接受提案后主从同步。

Raft 算法

Raft GitHub 可视化和文档

Raft 协议下所有节点有三个身份：

• Leader：负责处理客户端请求并将日志条目复制给其他节点。
• Follower：被动接收 Leader 的日志复制和心跳消息。
• Candidate：在 Leader 选举过程中发起选举。

Raft 协议是一个用一系列规则构成的分布式协议，建议直接看论文page4的内容，清晰明了。

初始的 Raft 协议其实有很多问题：比如在选举期间往往不可控地出现选举失败的情况，会导致整个系统有两个倒计时周期的无法提供服务，可用性下降；在 Raft 系统中进行成员变更的时候也会出现一些边界情况下的问题，比如新旧配置法定人数不一致，同时发生分区错误导致的双 Leader 问题。

Raft 在实现方案足够简单明了的前提下把性能和一致性做到了十分可观的效果，这也是直到现在也有很多分布式系统采用 Raft 的原因之一。

题外话：如何解决节点变更带来的多 Leader 问题（脑裂问题）？

一个最简单且稳定的方案是单节点变更，一次只新增或删除一个节点，这样很就能保证新配置和旧配置交替的时候，“大多数”的数量之和始终比总节点数量多1个，就不会因为分区错误带来双节点问题。

脑裂过程：
A、B、C：2/3
+--------------------------+
|           / [B-Follower] |
| [A-Leader]               |
|           \ [C-Follower] |
+--------------------------+
网络分区
A、B、C：2/3
+--------------------------+  +---------------+
| [A-Leader]--[B-Follower] |  | [C-Candidate] |
+--------------------------+  +---------------+
新增两个节点在 C 的分区，通知 C 更改配置
A、B：2/3
C、D、E：3/5
+--------------------------+ 
| [A-Leader]--[B-Follower] |
+--------------------------+
+--------------------------+
|           / [D-Follower] |
| [C-Leader]               |
|           \ [E-Follower] |
+--------------------------+
Raft 集群丧失区域容错性，出现脑裂

ZAB 协议：ZooKeeper

ZAB协议解决的问题是：如何规定顺序执行一系列指令？（其实Raft也能做到，但是 ZK 出现在2007年，比Raft早了6年）

Multi-Paxos 协议无法做到保证指令的执行顺序，不是因为提案者的并发，Multi-Paxos 只有一个领导者，不存在提案并发问题。

基于 Basic-Paxos 的 Multi-Paxos 在执行指令的时候，是没有连续日志这个要求的，所以中间存在什么操作日志缺失也无法知道，同时领导者的选举因为没有日志完整性要求，也会出现记录是全是残缺日志拼凑出来的问题，带来指令缺失和重排的问题。

ZAB 协议具体内容：主备模式（一主多从），基于TCP的原子有序广播。

• 单领导者模式，只能有一个主节点作为写节点
• 32 位提案序号提供强指令有序性；[16bit/任期编号, 16bit/提案序号]
• TCP 协议通信，保证消息传递的有序性
• 严格依次执行提案，保证执行提案的有序性

ZAB 协议的领导选举：通过领导者 PK 完成，和 Raft 的设计很像，但是有一个人为要素控制：集群 ID 会作为最终保底优先条件，这个 ID 是要我们自己去设计的，一般更大的ID优先给性能比较好的节点。

ZAB 协议在领导挂掉的故障恢复阶段会执行成员发现和数据同步，成员会主动联系领导者建立心跳关系，还会根据提案序号日志进行数据同步，具体内容不讲。

Gossip & Anti-Entropy

Gossip 协议：谣言传播算法，一个广泛使用的最终一致性协议，具有去中心化、容错性强和扩展性好的特点。

• 分布式数据库：Cassandra和DynamoDB等分布式数据库使用Gossip协议来传播节点的状态信息和集群拓扑变化。
• 分布式缓存：Memcached和Redis的集群模式中使用Gossip协议来同步节点状态和缓存数据。
• 分布式监控：Consul和Serf等分布式系统使用Gossip协议来传播节点的健康状态和服务注册信息。

实现细节：

每个节点定期随机选择其他节点，并向其传播自己知道的信息。被选中的节点接收到信息后，再随机选择其他节点继续传播。通过不断的传播，信息最终会在整个系统中扩散开来。同时，每一个节点在收到新的写消息时会变的活跃，扩散频率变高，以便尽快扩散新的数据。

反熵协议（Anti-Entropy Protocol）：一种用于分布式系统中的数据同步机制，通过定期比较和交换数据副本来消除差异，确保数据一致性。

反熵协议实现过程有一些细节要注意：

• 定期交换全量数据副本比对带来的网络开销太吓人，采用纠错编码的方式进行分区比对更合适。
• 反熵更新的链路应当主动设计闭环链路，减少随机链路带来的不收敛问题。
• 反熵算法对于更新太频繁的系统没有用。

Quorum NWR 算法

Quorum NWR协议：通过对读写操作设置不同的副本数量和一致性要求，在性能和一致性之间进行平衡的数据一致性协议。

一些协议的实现细节：

• NWR分别代表写操作的副本数量（N）、读操作的副本数量（R）和总的副本数量（W）。
• 每个数据项都会被复制到多个副本上，总的副本数量用N表示。副本数不代表节点数，一个节点可能有多个副本。
• 写操作需要写入到至少W个副本上才能认为写操作成功。
• 读操作需要从至少R个副本中读取数据，并对读取到的数据进行合并或冲突解决。
• Quorum条件：W + R > N，确保读写操作之间有至少一个副本交集，从而保证数据一致性。

实际应用中，可以根据具体需求选择合适的N、W和R值，以平衡系统的一致性、性能和容错性，这个协议没有什么好讲的，挺简单的一个协议。

BPFT，PoW，PoS 解决拜占庭问题

BPFT 采用签名来解决拜占庭问题，也是一个客户端和“主节点”通信，然后通过3阶段提交来完成，每个阶段都需要超过指定数量的节点达成共识才能进行，这个数量门槛和整个系统能容忍的叛徒数量相关，就不多说了。

BPFT 因为有主节点，如果主节点出现问题就需要客户端参与系统主节点轮换的过程，所以是对业务有侵入的做法。同时BPFT设计大量的签名广播，网络压力特别大，只适合中小型分布式系统。

PoW 工作量证明：如何攻击一条区块链？

首先简单了解一下区块链，一个分布式的去中心化的账本。每个区块按照时间顺序链接到上一个区块之后，形成的交易时间链就是区块链。

区块结构：

• 区块头(80Byte)
  • 前一个区块的哈希值
  • 新区块中所有交易的Merkle根哈希值
  • 时间戳
  • 难度目标
  • 随机数（Nonce）
• 区块体：
  • 交易数据信息

区块链本质是一个记账系统，在前期系统做完交易的合法性认证之后，所有认定合法的交易都会进入系统的内存池，等待被记录。

区块链记录过程：

1. 矿工节点从内存池中选择几笔交易记录，作为新区块的区块体。（一般选交易手续费高的）
2. 矿工节点选择最长的区块链作为主链，进行挖矿。
3. 挖到新区块，加入区块链，进行广播，所有节点认证后也记录到自己的区块链信息里面。
4. 手续费账户也会在区块链信息里面，获取这些交易的手续费。

什么是挖矿，其实就是 PoW 的工作量。

新区块入链的条件是，区块头的双重 SHA256 哈希值达到难度目标。这个条件很容易验证，但是不容易找到，矿工需要不断调整区块头中的随机数来尝试达到这个目标，这个过程随机性高且耗费巨大算力，所以称为挖矿。

对于一般的攻击者来说，想改变区块链中某一笔交易的信息，不仅会影响这个区块的根Hash值需要重新挖矿，也会通过区块链传播到后续的区块上去（因为都记录了前一个区块的信息），也就是需要拿到后面所有区块的工作量才能实现攻击，几乎不可能。

并且挖矿是很不稳定的，哪怕算力强大但是运气一般也不容易攻击成功，一般认为只要超过 50% 的算力就能实现区块链攻击，但是去中心化的分布式系统几乎是无门槛的散户系统，理论上很难一个人单挑千军万马。

不过讽刺的是，主打去中心化的区块链现在由于矿池的出现已经开始中心化了，没有去中心化保证的区块链根本没有任何安全保障，当矿池的算力超过70%的时候，交易信息早就是矿池的一言堂了

PoS 权益证明：解决 PoW 带来算力开销太大的问题，简而言之就是一个信用协议，只要足够守信用，就可以免去一部分工作量去更新区块链，当然也有惩罚机制，如果不守信用会被贬为平民，其实也是个资源越来越中心化的手段。

总结一下所有提到的分布式算法

一些小补充

关于可用性：对于一个去中心化的系统，只要能联系上其中一个节点就可用，所以去中心化的系统一定是高可用的。其他系统的可用性基本看节点集群的副本设计，一般都有不错的可用性

关于一致性：一致性分为强一致性和弱一致性，在现在的分布式系统中，弱一致性一般为最终一致性。

关于性能：一般的分布式协议性能指标其实只看网络通信的压力，如果协议需要很大的网络通信压力（比如 2PC 的单点压力，PBFT 反复广播的网络压力）自然会导致性能降低。只有 PoW 协议由于其为了安全而带来的离谱的计算压力导致性能也很低。