分布式理论须知

2022-06-27 09:26:34 浏览数 (2)

文章目录

  • 0.前言
  • 1.CAP 定理
  • 2.BASE 理论
  • 3.一致性算法
    • 3.1 分类
    • 3.2 Paxos
      • 3.2.1 简介
      • 3.2.2 地位
      • 3.2.3 解决的问题
      • 3.2.4 相关概念
      • 3.2.5 基本原理
        • 3.2.5.1 单提议者 多接受者
        • 3.2.5.2 多提议者 单接受者
        • 3.2.5.3 多提议者 多接受者
        • 3.2.5.4 二阶段提交
      • 3.2.6 算法流程
      • 3.2.7 算法示例
      • 3.2.8 活锁问题
      • 3.2.9 小结
    • 3.3 Multi-Paxos
    • 3.4 Raft
      • 3.4.1 简介
      • 3.4.2 概述
      • 3.4.3 Leader 选举
      • 3.4.4 日志同步
      • 3.4.5 安全性
      • 3.4.6 日志压缩
      • 3.4.7 成员变更
      • 3.4.8 Raft 与 Multi-Paxos 的异同
      • 3.4.9 脑裂问题
      • 3.4.10 小结
    • 3.5 ZAB
      • 3.5.1 简介
      • 3.5.2 三个角色
      • 3.5.3 消息广播
      • 3.5.4 崩溃恢复
      • 3.5.5 数据同步
      • 3.5.6 脑裂问题
      • 3.5.7 小结
    • 3.6 Gossip
      • 3.6.1 简介
      • 3.6.2 六度分隔理论
      • 3.6.3 原理
      • 3.6.4 消息传播方式
      • 3.6.5 通信方式
      • 3.6.6 复杂度分析
      • 3.6.7 优点
      • 3.6.8 缺点
      • 3.6.9 工程上的使用
  • 参考文献

0.前言

作为一名后台开发人员，你可能不了解分布式相关理论，但是你做的很多事情都是符合分布式理论的。比如为了保证服务的高可用，我们可能经常采用降级兜底的策略。举个例子，比如我们做个性化推荐服务时，需要从用户中心获取用户的个性化数据，以便代入到模型里进行打分排序，但如果用户中心服务挂掉，我们获取不到数据了，那么就不推荐了？显然不行，我们可以在本地 cache 里放置一份热门商品以便兜底。

通过本篇文章的介绍，希望让你对分布式相关理论知识有个大致了解。理论指导实践，理论知识了然于胸，实践起来才会胸有成足。当你了解了相关的分布式理论知识，回过头再看自己在日常开发工作中所干的事情，你会不禁感叹，原来我的实现方案是符合分布式理论的。

1.CAP 定理

2000 年，加州大学伯克利分校的计算机科学家 Eric Brewer 在分布式计算原理研讨会（PODC）上提出了一个猜想，分布式系统有三个指标：

代码语言：javascript复制
一致性（Consistency）
可用性（Availability）
分区容错性（Partition tolerance）

它们的第一个字母分别是 C、A、P。

Eric Brewer 说，这三个指标最多只能同时实现两个，不可能三者兼顾，这便是著名的布鲁尔猜想。

在随后的 2002 年，麻省理工学院（MIT）的 Seth Gilbert 和 Nancy Lynch 发表了布鲁尔猜想的证明，使之成为一个定理，即 CAP 定理。

CAP 定理告诉我们，如果服务是分布式服务，那么不同节点间通信必然存在失败可能，即我们必须接受分区容错性（P），那么我们必须在一致性（C）和可用性（A）之间做出取舍，即要么 CP，要么 AP。

2.BASE 理论

在 CAP 定理的背景下，大部分分布式系统都偏向业务逻辑，面向用户，那么可用性相对一致性显得更加重要。如何构建一个高可用的分布式系统，BASE 理论给出了答案。

2008 年，eBay 公司选则把资料库事务的 ACID 原则放宽，于计算机协会（Association for Computing Machinery，ACM）上发表了一篇文章Base: An Acid Alternative，正式提出了一套 BASE 原则。

BASE 基于 CAP 定理逐步演化而来，其来源于对大型分布式系统实践的总结，是对 CAP 中一致性和可用性权衡的结果，其核心思想是即使无法做到强一致性，但每个业务根据自身的特点，采用适当的方式来使系统达到最终一致性。BASE 可以看作是 CAP 定理的延伸。

BASE 理论指：

  • Basically Available（基本可用）

基本可用就是假设系统出现故障，要保证系统基本可用，而不是完全不能使用。比如采用降级兜底的策略，假设我们在做个性化推荐服务时，需要从用户中心获取用户的个性化数据，以便代入到模型里进行打分排序。但如果用户中心服务挂掉，我们获取不到数据了，那么就不推荐了？显然不行，我们可以在本地 cache 里放置一份热门商品以便兜底。

  • Soft state（ 软状态）

软状态指的是允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

  • Eventual consistency（最终一致性）

上面讲到的软状态不可能一直是软状态，必须有时间期限。在期限过后，应当保证所有副本保持数据一致性，从而达到数据的最终一致性，因此所有客户端对系统的数据访问最终都能够获取到最新的值，而这个时间期限取决于网络延时，系统负载，数据复制方案等因素。

3.一致性算法

BASE 理论适用于业务系统，对于系统的一些核心组件，还是需要做到强一致。此时便需要依赖一致性算法，来保证分布式系统的元数据在多个节点上是一致的。

3.1 分类

从一致性强弱可以把一致性算法分为两类：

  • 强一致性

保证系统改变提交以后立即改变集群的状态。如 Paxos、Muti-Paxos、Raft、ZAB

  • 弱一致性

也叫最终一致性，系统不保证改变提交以后立即改变集群的状态，但是随着时间的推移最终状态是一致的。如 DNS 系统、Gossip 协议。

以上所列的一致性算法均有落地，比如：

  • Google 的分布式锁服务 Chubby 采用了 Muti-Paxos 算法
  • CoreOS 开源的分布式 KV 数据库 etcd，采用了 Raft 算法
  • Apache 开源的分布式应用协调服务 ZooKeeper，采用 ZAB 算法

3.2 Paxos

3.2.1 简介

Paxos 算法是 Leslie Lamport 提出的一种基于消息传递具有高度容错特性的共识（Consensus）算法。

Paxos 由 Lamport 于 1998 年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个名为 Paxos 的小岛作为比喻，描述了 Paxos 小岛中法律通过表决的流程，并以此命名这个算法。Paxos 算法基本思想并不复杂，但最初论文描述比较难懂，于是后来在 2001 年，Lamport 重新发表了朴实的算法描述版本《Paxos Made Simple》 进行重新解释。

Paxos 是首个得到证明并被广泛应用的共识算法，其原理类似于二阶段提交算法，进行了泛化和扩展，通过消息传递来逐步消除系统中的不确定状态。

3.2.2 地位

Paxos 自问世以来一致垄断着分布式一致性算法，Paxos 这个名词几乎等同于分布式一致性。Google 的很多大型分布式系统都采用了 Paxos 算法来解决分布式一致性问题，如 Chubby、Megastore 以及 Spanner 等。开源的 ZooKeeper，以及 MySQL 5.7 推出的用来取代传统的主从复制的 MySQL Group Replication 等纷纷采用 Paxos 算法解决分布式一致性问题。

后来很多著名的共识算法，如 Raft、ZAB 等，也都是以 Paxos 为基础。

Lamport 作为分布式系统领域的早期研究者，因为相关杰出贡献获得了 2013 年度图灵奖。

3.2.3 解决的问题

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复。在最普通的 Paxos 场景中，先不考虑可能出现“消息篡改”（即拜占庭将军问题）。Paxos 算法解决的问题是在一个可能发生上述异常（即排除消息篡改之外的其他任何异常）的分布式系统中，如何对某个值的看法达成一致。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“共识算法”以保证每个节点看到的指令一致。一个通用的共识算法可以应用在许多场景中，是分布式计算中的重要问题。因此从 20 世纪 80 年代起对于共识算法的研究就没有停止过。

Paxos 算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2F 1 的容错能力，即 2F 1 个节点的系统最多允许 F 个节点同时出现故障。

3.2.4 相关概念

Lamport 为了形象地描述算法，在 Paxos 中将系统节点划分为三种角色：

  • 提议者（Proposer），提出提议（Proposal），提议拥有一个自增的唯一提议号，可以表示为 <提议编号，提议内容>。
  • 接受者（Acceptor），负责对提议进行投票，接受（Accept）提议。若提议获得多数 Acceptors 的接受，则称该提议被批准（Chosen）。被批准的提议称为决议（Value）。接受者不同意比自己以前接收过的提议编号要小的提议，其他提议都同意。
  • 学习者（Learner），不参与投票，获取被批准的提议内容，并帮忙传播。

其中提议指分布式系统的修改请求，提议内容可以是一条日志，也可以是一条命令，不同的应用场景，提议内容也会不同。

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

算法需要满足安全性（Safety） 和存活性（Liveness）两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的：

  • Safety：保证决议（Value）结果是对的，无歧义的，不会出现错误情况。只有是被提议者提出的提议才可能被最终批准；
  • 在一次执行中，最终只批准（chosen）一个提议。被多数 Acceptors 接受的提议成为决议。
  • Liveness：保证决议过程能在有限时间内完成。
  • 决议总会产生，并且学习者能获得决议。

3.2.5 基本原理

Paxos 基本思路类似二阶段提交：多个提议者先要争取到提议的权利（得到大多数接受者的支持）；成功的提议者发送提议给所有人进行确认，得到大部分人确认的提议成为被批准的决议。

Paxos 并不保证系统总处在一致的状态。但由于每次达成共识至少有超过一半的节点参与，这样最终整个系统都会获知共识结果。一个潜在的问题是提议者在提议过程中出现故障，这可以通过超时机制来缓解。极为凑巧的情况下，每次新一轮提议的提议者都恰好故障，又或者两个提议者恰好依次提出更新的提议，则导致活锁，系统会永远无法达成共识（实际发生概率很小）。

Paxos 能保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案，会发现在满足各种约束情况下，算法过程总会十分类似 Paxos 的过程。这也是为何 Google Chubby 的作者 Mike Burrows 说：“这个世界上只有一种一共识算法，那就是 Paxos（There is only one consensus protocol, and that’s Paxos）”。

下面，由简单情况逐步推广到一般情况来探讨算法过程。

3.2.5.1 单提议者 多接受者

果系统中限定只允许某个特定节点是提议者，那么共识结果很容易能达成（只有一个方案，要么达成，要么失败）。提议者只要收到了来自多数接受者的投票，即可认为通过，因为系统中不存在其他的提议。

但此时一旦提议者故障，则整个系统无法工作。

3.2.5.2 多提议者 单接受者

限定某个特定节点作为接受者。这种情况下，共识也很容易达成，接受者收到多个提议，选第一个提议作为决议，发送给其它提议者即可。

缺陷也是容易发生单点故障，包括接受者故障或首个提议者节点故障。

以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。

当提议者和接受者都推广到多个的情形，会出现一些挑战。

3.2.5.3 多提议者 多接受者

既然限定单提议者或单接受者都会出现故障，那么就得允许出现多个提议者和多个接受者。问题一下子变得复杂了。

一种情况是同一时间片段（如一个提议周期）内只有一个提议者，这时可以退化到单提议者的情形。需要设计一种机制来保障提议者的正确产生，例如按照时间、序列、或者大家猜拳（出一个参数来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现多个提议者。那同一个节点可能收到多份提议，怎么对它们进行区分呢？如果一个节点只接受它收到的首个提议，将导致不同节点可能接受不同的提议。很自然地，提议需要带上不同的序号。节点根据序号来判断接受哪个提议。通常采用递增序号，选择接受序号最大的提议。这是因为旧提议可能基于过期数据，导致失败概率更大。

如何为提议分配序号呢？一种可能方案是每个节点的提议数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。

同时允许多个提议，意味着很可能单个提议人无法集齐足够多的投票；另一方面，提议者即便收到了多数接受者的投票，也不敢说就一定通过。因为在此过程中投票者无法获知其它投票人的结果，也无法确认提议人是否收到了自己的投票。因此，需要实现两个阶段的提交过程。

3.2.5.4 二阶段提交

提议者发出提议申请之后，会收到来自接受者的反馈。一种结果是提议被大多数接受者接受了，一种结果是没被接受。没被接受的话，可以过会再重试。即便收到来自大多数接受者的答复，也不能认为就最终确认了。因为这些接受者自己并不知道自己刚答复的提议可以构成大多数的一致意见。

很自然的，需要引入新的一个阶段，即提议者在第一阶段拿到所有的反馈后，需要再次判断这个提议是否得到大多数的支持，如果支持则需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备（Prepare）和提交（Commit）。准备阶段通过锁来解决对哪个提议内容进行确认的问题，提交阶段解决大多数确认最终值的问题。

准备阶段：

  • 提议者向多个接受者发送计划提交的提议编号 n，试探是否可以锁定多数接受者的支持；
  • 接受者 i 收到提议编号 n，检查回复过的提议的最大编号 M_i。如果 n > M_i，则向提议者返回准备接受（accept）提交的最大编号的提议 P_i（如果还未接受过任何提议，则为空），并不再接受小于 n 的提议，同时更新 M_i = n。这一步是让接受者筛选出它收到的最大编号的提议，接下来只接受其后续提交。

提交阶段：

  • 某个提议者如果收到大多数接受者的回复（表示大部分人收到了 n），则准备发出带有 n 的提交消息。如果收到的回复中带有提议 P_i（说明自己看到的信息过期），则将编号 P_i 的值作为提议值；否则指定一个新提议值。如果没收到大多数回复，则再次发出请求；
  • 接受者 i 收到序号为 n 的提交消息，如果发现 n >= P_i 的序号，则接受提议，并更新 P_i 序号为 n。

一旦多数接受者接受了共同的提议值，则形成决议。之后可以开始新一轮的提交确认。

需要注意，Paxos 并不一定能保证每一轮都能提交提议。

3.2.6 算法流程

Paxos 算法通过一个决议分为两个阶段（Learn 阶段之前决议已经形成）：

第一阶段：Prepare 阶段。Proposer 向 Acceptors 发出 Prepare 请求，Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。

第二阶段：Accept 阶段。Proposer 收到多数 Acceptors 承诺的 Promise 后，向 Acceptors 发出 Propose 请求，Acceptors 针对收到的Propose 请求进行 Accept 处理。

第三阶段：Learn 阶段。Proposer 在收到多数 Acceptors 的 Accept 之后，标志着本次 Accept 成功，决议形成，将形成的决议发送给所有 Learners。

Paxos 算法流程中的每条消息描述如下：

  • Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。
  • Promise: Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”

两个承诺：

  1. 不再接受 Proposal ID 小于等于（注意：这里是<= ）当前请求的 Prepare 请求。
  2. 不再接受 Proposal ID 小于（注意：这里是< ）当前请求的 Propose 请求。

一个应答：

  1. 不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Proposal ID 和 Value，没有则返回空值。
  • Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。
  • Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。
  • Learn: Proposer 收到多数 Acceptors 的 Accept 后，决议形成，将形成的决议发送给所有 Learners。

Paxos 算法伪代码描述如下：

  1. 获取一个 Proposal ID n，为了保证 Proposal ID 唯一，可采用“时间戳 Server ID”生成；
  2. Proposer 向所有 Acceptors 广播 Prepare(n) 请求；
  3. Acceptor 比较 n 和 minProposal，如果 n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
  4. Proposer 接收到过半数回复后，如果发现有 acceptedValue 返回，将所有回复中 acceptedProposal 最大的 acceptedValue 作为本次提案的 value，否则可以任意决定本次提案的 value；
  5. 到这里可以进入第二阶段，广播 Accept (n,value) 到所有节点；
  6. Acceptor 比较 n 和 minProposal，如果 n>=minProposal，则 acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回 minProposal。
  7. 提议者接收到过半数请求后，如果发现有返回值 result >n，表示有更新的提议，跳转到1；否则 value 达成一致。

3.2.7 算法示例

根据上面的 Paxos 的流程描述，下面举几个例子。

  • 实例 1

图中 P 代表 Prepare 阶段，A 代表 Accept 阶段。3.1 代表 Proposal ID 为 3.1，其中 3 为时间戳，1 为 Server ID。X 和 Y 代表提议 Value。

实例 1 中 P 3.1 达成多数派，其 Value(X) 被 Accept，然后 P 4.5 学习到 Value(X)，并 Accept。

  • 实例 2

图中 P 3.1 没有被多数派 Accept（只有 S3 Accept），但是被 P 4.5 学习到，P 4.5 将自己的 Value 由 Y 替换为 X，Accept（X）。

  • 实例 3

图中 P 3.1 没有被多数派 Accept（只有 S1 Accept），同时也没有被 P 4.5 学习到。由于 P 4.5 Propose 的所有应答，均未返回 Value，则 P 4.5 可以 Accept 自己的 Value (Y)。后续 P 3.1 的 Accept (X) 会失败，已经 Accept 的 S1，会被覆盖。

3.2.8 活锁问题

Paxos 算法可能形成活锁而永远不会结束，如下图实例所示：

回顾两个承诺之一，Acceptor 不再应答 Proposal ID 小于等于当前请求的 Prepare 请求。意味着需要应答 Proposal ID 大于当前请求的 Prepare 请求。

两个 Proposers 交替 Prepare 成功，而 Accept 失败，形成活锁（Livelock）。

3.2.9 小结

Paxos 算法虽然给出了共识设计，但并没有讨论太多实现细节，也并不重视工程上的优化。此外原始的 Paxos 算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。

因此后来在学术界和工程界出现了一些改进工作，包括 Fast Paxos、Multi-Paxos，Zookeeper Atomic Broadcast（ZAB）和 Raft 等。这些算法重点在于改进执行效率和可实现性。

3.3 Multi-Paxos

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos 正是为解决此问题而提出。Multi-Paxos 基于 Basic Paxos 做了两点改进：

  1. 针对每一个要确定的值，运行一次 Paxos 算法实例（Instance），形成决议。每一个Paxos实例使用唯一的 Instance ID 标识。
  2. 在所有 Proposers 中选举一个 Leader，由 Leader 唯一地提交 Proposal 给 Acceptors 进行表决。这样没有 Proposer 竞争，解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下，Prepare 阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos 首先需要选举 Leader，Leader 的确定也是一次决议的形成，所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal，在 Leader 宕机之后服务临时不可用，需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下，Prepare 阶段可以跳过。

Multi-Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例，从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段，后续只需要执行 Accept 阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个 Instance ID 标识，Instance ID 由 Leader 本地递增生成即可。

Multi-Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性，这样的场景即退化为 Basic Paxos。

3.4 Raft

3.4.1 简介

Raft 是一种用于替代 Paxos 的共识算法，由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出。

Raft 算法的主要设计思想与 ZAB 类似，通过先选出领导节点来简化流程和提高效率。实现上解耦了领导者选举、日志复制和安全方面的需求，并通过约束减少了不确定性的状态空间。

Raft 算法的开源实现众多，在 Go、C 、Java 以及 Scala 中都有完整的代码实现。Raft 这一名字来源于 “Reliable, Replicated, Redundant, And Fault-Tolerant”（“可靠、可复制、可冗余、可容错”）的首字母缩写。

3.4.2 概述

不同于 Paxos 算法直接从分布式一致性问题出发推导出来，Raft 算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。Raft 实现了和 Paxos 相同的功能，它将一致性分解为多个子问题：

  • Leader 选举（Leader election）
  • 日志同步（Log replication）
  • 安全性（Safety）
  • 日志压缩（Log compaction）
  • 成员变更（Membership change）等

同时，Raft 算法使用了更强的假设来减少需要考虑的状态，使之变的易于理解和实现。

Raft 将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）。

  • Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉 Follower 提交日志。
  • Follower：接受并持久化 Leader 同步的日志，在 Leader 告之日志可以提交之后，提交日志。
  • Candidate：Leader 选举过程中的临时角色。

Raft 要求系统在任意时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Followers。

Raft 算法角色状态转换如下：

Follower 只响应其他服务器的请求。如果 Follower 超时没有收到 Leader 的消息，它会成为一个 Candidate 并且开始一次 Leader 选举。收到大多数服务器投票的 Candidate 会成为新的 Leader。Leader 在宕机之前会一直保持 Leader 的状态。

Raft 算法将时间分为一个个的任期（term），每一个 term 的开始都是 Leader 选举。在成功选举 Leader 之后，Leader 会在整个 term 内管理整个集群。如果 Leader 选举失败，该 term 就会因为没有 Leader 而结束。

3.4.3 Leader 选举

每个 Follower 都持有一个定时器，Leader 存在时会向所有 Followers 周期性发送 heartbeat，来证明自己还活着。Follower 收到心跳后会回复 Leader 并清空定时器。

如果 Follower 在定时器时间到了而没有收到 Leader 的 heartbeat，那么认为 Leader 已死，那么该节点就会转变成 Candidate，进入下一轮Leader 选举。

Follower 将其当前 term 加一然后转换为 Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。结果有以下三种情况：

  • 赢得了多数的选票，成功选举为Leader；
  • 收到了Leader 的消息，表示有其它服务器已经抢先当选了Leader；
  • 没有服务器赢得多数的选票，Leader 选举失败，等待选举时间超时后发起下一次选举。

选举出 Leader 后，Leader 通过定期向所有 Followers 发送心跳信息维持其统治。若 Follower 一段时间未收到 Leader 的心跳则认为 Leader可能已经挂了，再次发起 Leader 选举过程。

若出现两个 Candidate 同时选举并获得了相同的票数，那么这两个 Candidate 将随机推迟一段时间后再向其他节点发出投票请求，这保证了再次发送投票请求以后不冲突。

Raft 保证选举出的 Leader 一定具有最新的已提交的日志，这一点将在下面的安全性中说明。

3.4.4 日志同步

Leader 选出后，就开始接收客户端的请求。Leader 把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader 将这条日志应用到它的状态机并向客户端返回执行结果。

某些 Followers 可能没有成功的复制日志，Leader 会无限的重试 AppendEntries RPC 直到所有的 Followers 最终存储了所有的日志条目。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

Raft 日志同步保证如下两点：

  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于 Leade r在一个 term 内在给定的一个 log index 最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader 会把新日志条目紧接着之前的条目的 log index 和 term 都包含在里面。如果 Follower 没有在它的日志中找到 log index 和 term 都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader 和 Followers 的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader 崩溃可能会导致日志不一致：旧的 Leader 可能没有完全复制完日志中的所有条目。

上图阐述了一些 Followers 可能和新的 Leader 日志不同的情况。一个 Follower 可能会丢失掉 Leader 上的一些条目，也有可能包含一些 Leader 没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader 通过强制 Followers 复制它的日志来处理日志的不一致，Followers 上的不一致的日志会被 Leader 的日志覆盖。

Leader 为了使 Followers 的日志同自己的一致，Leader 需要找到 Followers 同它的日志一致的地方，然后覆盖 Followers 在该位置之后的条目。

Leader 会从后往前试，每次 AppendEntries 失败后尝试前一个日志条目，直到成功找到每个 Follower 的日志一致位点，然后向后逐条覆盖Followers 在该位置之后的条目。

3.4.5 安全性

Raft 增加了如下两条限制以保证安全性：

  • 拥有最新的已提交的 log entry 的 Follower 才有资格成为 Leader。

这个保证是在 RequestVote RPC 中做的，Candidate 在发送 RequestVote RPC 时，要带上自己的最后一条日志的 term 和 log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条 log entry 的 term 更大，则 term 大的更新，如果 term 一样大，则 log index 更大的更新。

  • Leader 只能推进 commit index 来提交当前 term 的已经复制到大多数服务器上的日志，旧 term 日志的提交要等到提交当前 term 的日志来间接提交（log index 小于 commit index 的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

在阶段 a，term 为 2，S1 是Leader，且 S1 写入日志（term, index）为 (2, 2)，并且日志被同步写入了 S2；

在阶段 b，S1 离线，触发一次新的选主，此时 S5 被选为新的 Leader，此时系统 term 为 3，且写入了日志（term, index）为 (3, 2)；

S5 尚未将日志推送到 Followers 就离线了，进而触发了一次新的选主，而之前离线的 S1 经过重新上线后被选中变成 Leader，此时系统 term 为 4，此时 S1 会将自己的日志同步到 Followers，按照上图就是将日志 (2, 2) 同步到了 S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志 (2, 2) 可以被提交了。

在阶段 d，S1 又下线了，触发一次选主，而 S5 有可能被选为新的 Leader。这是因为 S5 可以满足作为主的一切条件：

  • term = 5 > 4
  • 最新的日志为 (3, 2)，比大多数节点（如 S2/S3/S4 的日志都新）

然后 S5 会将自己的日志更新到 Followers，于是 S2、S3 中已经被提交的日志 (2, 2) 被截断了。

增加上述限制后，即使日志 (2, 2) 已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前 term(2) 的日志，直到 S1 在当前 term(4) 产生的日志被大多数 (4, 4) Followers 确认，S1 方可提交日志 (4, 4) 这条日志。当然，根据 Raft 定义，(4, 4) 之前的所有日志也会被提交。此时即使 S1 再下线，重新选主时 S5 不可能成为 Leader，因为它没有包含大多数节点已经拥有的日志 (4, 4)。

3.4.6 日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot 中包含以下内容：

  • 日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在 snapshot 之后的第一条 log entry 的 AppendEntries RPC 的完整性检查的时候会被用上。
  • 系统当前状态。

当 Leader 要发给某个日志落后太多的 Follower 的 log entry 被丢弃，Leader 会将 snapshot 发给 Follower。或者当新加进一台机器时，也会发送 snapshot 给它。发送 snapshot 使用 InstalledSnapshot RPC。

做 snapshot 既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次 snapshot。

做一次 snapshot 可能耗时过长，会影响正常日志同步。可以通过使用 copy-on-write 技术避免 snapshot 过程影响正常日志同步。

3.4.7 成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向 Leader 发送成员变更请求，Leader 复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在 Cold 和 Cnew 中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

为了解决这一问题，Raft 提出了两阶段的成员变更方法。集群先从旧成员配置 Cold 切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置 Cold 和新成员配置 Cnew 的组合 Cold U Cnew，一旦共同一致 Cold U Cnew 被提交，系统再切换到新成员配置 Cnew。

Raft 两阶段成员变更过程如下：

  1. Leader 收到成员变更请求从 Cold 切成 Cold,new；
  2. Leader 在本地生成一个新的 log entry，其内容是 Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该 log entry 复制至 Cold∪Cnew 中的所有副本。在此之后新的日志同步需要保证得到 Cold 和 Cnew 两个多数派的确认；
  3. Follower 收到 Cold∪Cnew 的 log entry 后更新本地日志，并且此时就以该配置作为自己的成员配置；
  4. 如果 Cold 和 Cnew 中的两个多数派确认了 Cold U Cnew 这条日志，Leader 就提交这条 log entry 并切换到 Cnew；
  5. 接下来 Leader 生成一条新的 log entry，其内容是新成员配置 Cnew，同样将该 log entry 写入本地日志，同时复制到 Follower 上；
  6. Follower 收到新成员配置 Cnew 后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在 Cnew 这个成员配置中会自动退出；
  7. Leader 收到 Cnew 的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

异常分析：

  • 如果 Leader 的 Cold U Cnew 尚未推送到 Follower，Leader 就挂了，此后选出的新 Leader 并不包含这条日志，此时新Leader依然使用Cold作为自己的成员配置。
  • 如果 Leader 的 Cold U Cnew 推送到大部分的 Follower 后就挂了，此后选出的新 Leader 可能是 Cold 也可能是 Cnew 中的某个 Follower。
  • 如果 Leader 在推送 Cnew 配置的过程中挂了，那么同样，新选出来的 Leader 可能是 Cold 也可能是 Cnew 中的某一个，此后客户端继续执行一次改变配置的命令即可。
  • 如果大多数的 Follower 确认了 Cnew 这个消息后，那么接下来即使 Leader 挂了，新选出来的 Leader 肯定位于 Cnew 中。

两阶段成员变更比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程。

两阶段成员变更，之所以分为两个阶段，是因为对 Cold 与 Cnew 的关系没有做任何假设，为了避免 Cold 和 Cnew 各自形成不相交的多数派选出两个 Leader，才引入了两阶段方案。

如果增强成员变更的限制，假设 Cold 与 Cnew 任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。

那么如何限制 Cold 与 Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。

可从数学上严格证明，只要每次只允许增加或删除一个成员，Cold 与 Cnew 不可能形成两个不相交的多数派。

一阶段成员变更：

  • 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。
  • 成员变更由 Leader 发起，Cnew 得到多数派确认后，返回客户端成员变更成功。
  • 一次成员变更成功前不允许开始下一次成员变更，因此新任 Leader 在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
  • Leader 只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步。

3.4.8 Raft 与 Multi-Paxos 的异同

Raft 与 Multi-Paxos 都是基于领导者的一致性算法，乍一看有很多地方相同，下面总结一下 Raft 与 Multi-Paxos 的异同。

Raft 与 Multi-Paxos 中相似的概念：

Raft 与 Multi-Paxos 的不同：

3.4.9 脑裂问题

若集群中出现网络异常，导致集群被分割，在不同的网络分区里会因为无法接收到原来的 Leader 发出的心跳而超时选主，这样将出现多个 Leader，即脑裂（Split Brain）。

下图中网络分区 1 的节点 A 是新产生的 Leader，因为有大多数节点可以投票，将其选为 Leader。

在网络分区 1 和网络分区 2 中，出现了两个 Leader A 和 D。假设此时要更新分区 2 的值，因为分区 2 无法得到集群中的大多数节点的 ACK，会复制失败。而网络分区 1 会成功，因为分区 1 中的节点更多，Leader A 能得到大多数回应。

Raft 是能够应对脑裂问题的，以上面的脑裂为例：

  • 如果更新请求到达少数节点的网络分区 2 是不会更新成功，因为得不到大多数节点的支持
  • 如果更新请求到达大多数网络分区 1 会更新成功，因为得到大多数节点的支持
  • 如果此时网络恢复了，旧 Leader 发现自己 term 落后而自动成为 Follower。新 Leader 将新日志同步给所有节点，集群重新达到一致性状态

所以要么是避免脑裂选主，要么是脑裂后老 Leader 自动降级为 Follower。Raft 是通过后者来解决脑裂的问题。当然最好的办法还是在节点之间加一个专线，降低出现分区的概率。

3.4.10 小结

Raft 算法具备强一致、高可靠、高可用、高性能等优点，具体体现在：

  • 强一致性：虽然所有节点的数据并非实时一致，但Raft算法保证Leader节点的数据最全，同时所有请求都由Leader处理，所以在客户端角度看是强一致性的。
  • 高可靠性：Raft 算法保证了 Committed 的日志不会被修改，State Matchine 只应用 Committed 的日志，所以当客户端收到请求成功即代表数据不再改变。Committed 日志在大多数节点上冗余存储，少于一半的磁盘故障数据不会丢失。
  • 高可用性：从 Raft 算法原理可以看出，选举和日志同步都只需要大多数的节点正常互联即可，所以少量节点故障或网络异常不会影响系统的可用性。即使 Leader 故障，在选举超时到期后，集群自发选举新 Leader，无需人工干预，不可用时间极小。但 Leader 故障时存在重复数据问题，需要业务去重或幂等性保证。
  • 高性能：与必须将数据写到所有节点才能返回客户端成功的算法相比，Raft 算法只需要大多数节点成功即可，少量节点处理缓慢不会延缓整体系统运行。

3.5 ZAB

3.5.1 简介

ZAB 全称是 Zookeeper Atomic Broadcast，即 Zookeeper 原子广播。

ZAB 是为分布式协调服务 Zookeeper 专门设计的一种支持崩溃恢复的原子广播协议，是 Zookeeper 保证数据一致性的核心算法。

3.5.2 三个角色

ZAB 中三个主要的角色，领导者（Leader）、跟随者（Follower）和观察者（Observer） 。

Leader ：集群中唯一的写请求处理者 ，能够发起投票（投票也是为了进行写请求）。 Follower：能够接收客户端的请求，如果是读请求则可以自己处理，如果是写请求则要转发给 Leader 。在选举过程中会参与投票，有选举权和被选举权 。 Observer ：就是没有选举权和被选举权的 Follower 。

基于该协议，Zookeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性。具体如下图所示：

上图显示了 Zookeeper 如何处理集群中的数据。所有客户端写入数据都是写入到 主进程（称为 Leader）中，然后，由 Leader 复制到备份进程（称为 Follower）中。从而保证数据一致性。从设计上看，和 Raft 类似。

那么复制过程又是如何的呢？复制过程类似 2PC（二阶段提交，Two Phase Commit），ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交，大大减小了同步阻塞，也提高了可用性。

3.5.3 消息广播

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

基本上，整个广播流程分为 3 步骤：

  • 将数据都复制到 Follwer 中。
  • 等待 Follwer 回应 Ack，最低超过半数即成功。
  • 当超过半数成功回应，则执行 commit ，同时提交自己。

通过以上 3 个步骤，就能够保持集群之间数据的一致性。实际上，在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，避免同步，实现异步解耦。

还有一些细节：

  • Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务ID（ZXID），ZAB 兮协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。
  • 在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。
  • Zookeeper 集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。
  • 实际上，这是一种简化版本的 2PC，不能解决单点问题。下面会讲述 ZAB 如何解决单点问题（即 Leader 崩溃问题）。

3.5.4 崩溃恢复

实际上，当 Leader 崩溃，即进入我们开头所说的崩溃恢复模式（崩溃即：Leader 失去与过半 Follwer 的联系）。下面来详细讲述。

  • 假设1：Leader 在复制数据给所有 Follwer 之后崩溃，怎么办？
  • 假设2：Leader 在收到 Ack 并提交了自己，同时发送了部分 commit 出去之后崩溃怎么办？

针对这些问题，ZAB 定义了 2 个原则：

  • ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
  • ZAB 协议确保丢弃那些只在 Leader 提出复制，但没有提交的事务。

所以，ZAB 设计了下面这样一个选举算法：能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。

针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 拥有集群中编号 ZXID 最大的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。 而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

这样，我们刚刚假设的两个问题便能够解决。

  • 假设 1 最终会丢弃调用没有提交的数据
  • 假设 2 最终会同步所有服务器的数据。

这个时候，就引出了一个问题，如何同步？

3.5.5 数据同步

当崩溃恢复之后，需要在正式工作之前（接收客户端请求），Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了，即是否完成了数据同步。目的是为了保持数据一致。 当所有的 Follwer 服务器都成功同步之后，Leader 会将这些服务器加入到可用服务器列表中。 实际上，Leader 服务器处理或丢弃事务都是依赖着 ZXID 的，那么这个 ZXID 如何生成呢？

在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 1 操作。 而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 Epoch 值，然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。 基于这样的策略：当 Follower 连接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

3.5.6 脑裂问题

当集群因网络问题出现分区时， ZAB 过半机制一定程度上也减少了脑裂情况的出现，起码不会出现三个 leader 同时。但是如果原 Leader 被划分到少部分节点的分区中，那么大部分节点的分区因为缺少 Leader 而会选举出新的 Leader，整个集群出现了两个 Leader，这就是所谓的脑裂（Split-Brain）。

ZAB 和 Raft 一样，可以应对脑裂的问题：

  • 如果更新请求到达少数节点的分区是不会更新成功，因为得不到大多数节点的支持
  • 如果更新请求到达大多数节点的分区会更新成功，因为得到大多数节点的支持
  • 如果此时网络恢复了，旧 Leader 发现自己 epoch 标号(标识当前属于那个 Leader 的统治时期)，这个 epoch 落后而自动成为 Follower。新 Leader 将新日志同步给所有节点，集群重新达到一致性状态

实际上，应该尽可能地防止脑裂，一般有下面几种方法：

  • 法定人数（Quorums） 比如 3 个节点的集群，Quorums = 2，也就是说集群可以容忍 1 个节点失效，这时候还能选举出 1 个 Leader，集群还可用。比如 4 个节点的集群，它的 Quorums = 3，相当于集群的容忍度还是 1，如果 2 个节点失效，那么整个集群是无效的，不会产生新的 Leader。这是 Zookeeper 防止脑裂默认采用的方法。
  • 冗余通信（Redundant communications） 集群中采用多种通信方式，防止一种通信方式失效导致集群中的节点无法通信。
  • 共享资源（Fencing） 比如能看到共享资源就表示在集群中，能够获得共享资源的锁的就是Leader，看不到共享资源的，就不在集群中。
  • 仲裁机制 脑裂导致的后果是从节点不知道该连接哪一台Leader，此时有一个仲裁方就可以解决此问题。比如提供一个参考的IP地址，心跳机制断开时，节点各自ping一下参考IP，如果ping不通，那么表示该节点网络已经出现问题，则该节点需要自行退出争抢资源，释放占有的共享资源，将服务的提供功能让给功能更全面的节点。
  • 磁盘锁 使用磁盘锁的形式，保证集群中只能有一个Leader获取磁盘锁，对外提供服务，避免数据错乱发生。但是，也会存在一个问题，若该Leader节点宕机，则不能主动释放锁，那么其他的Follower就永远获取不了共享资源。于是有人设计了智能锁。正在服务的一方只有在发现心跳线全部断开（察觉不到对端）时才启用磁盘锁，平时不上锁。

3.5.7 小结

ZAB 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有一个 Leader，用来保证一致性（Paxos 并没有使用 Leader 机制保证一致性）。再有采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。

ZAB 让整个 Zookeeper 集群在两个模式之间转换，消息广播和崩溃恢复，消息广播可以说是一个简化版本的 2PC，通过崩溃恢复解决了 2PC 的单点问题，通过队列解决了 2PC 的同步阻塞问题。

而支持崩溃恢复后数据准确性的就是数据同步了，数据同步基于事务的 ZXID 的唯一性来保证。通过 1 操作可以辨别事务的先后顺序。

ZAB 和 Raft 还是有些区别的：

  • 对于 Leader 的任期，Raft 叫做 term，而 ZAB 叫做 epoch
  • 在状态复制的过程中，Raft 的心跳从 Leader 向 Follower 发送，而 ZAB 则相反

3.6 Gossip

3.6.1 简介

Gossip 协议又称流行病协议（Epidemic Protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用，比如我们可以使用 Gossip 协议来确保网络中所有节点的数据一样。

Gossip 协议在1987年由施乐公司帕洛阿尔托研究中心研究员 Alan Demers 发表在 ACM 上的论文《Epidemic Algorithms for Replicated Database Maintenance》中被提出。

从 Gosssip 单词就可以看到，其中文意思是八卦、流言等意思，我们可以想象下绯闻的传播（或者流行病的传播），Gossip 协议的工作原理就类似于这个。Gosssip 协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip 其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。

使用 Gossip 协议的有：Redis Cluster、Consul、Apache Cassandra 等。

3.6.2 六度分隔理论

说到 Gossip 协议，不得不提一下六度分隔理论（Six Degrees of Separation），因为 Gossip 协议借鉴了六度分隔理论的思想。

1967 年，哈佛大学的心理学教授 Stanley Milgram 想要描绘一个连结人与社区的人际连系网。做过一次连锁信实验，结果发现了“六度分隔”现象。简单地说：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。

数学解释该理论：依据邓巴数，即每个人认识 150 人，其六度就是 150^6 ​＝11,390,625,000,000（约11.4万亿）。消除一些节点重复，那也几乎覆盖了整个地球人口若干多多倍，这也是 Gossip 协议的雏形。

基于六度分隔理论，任何信息的传播其实非常迅速，而且网络交互次数不会很多。比如 Facebook 在 2016 年 2 月 4 号做了一个实验：研究了当时已注册的 15.9 亿使用者资料，发现这个神奇数字的“网络直径”是 4.57，翻成白话文意味着每个人与其他人间隔为 4.57 人。

3.6.3 原理

Gossip 协议基本思想就是：一个节点想要分享一些信息给网络中的其他的一些节点。于是，它周期性的随机选择一些节点，并把信息传递给这些节点。这些收到信息的节点接下来会做同样的事情，即把这些信息传递给其他一些随机选择的节点。一般而言，信息会周期性的传递给 N 个目标节点，而不只是一个。这个 N 被称为 fanout（这个单词的本意是扇出）。

现在，我们通过一个具体的实例来深入体会一下 Gossip 传播的完整过程。

为了表述清楚，我们先做一些前提设定：

  1. Gossip 是周期性的散播消息，把周期限定为 1 秒
  2. 被感染节点随机选择 k 个邻接节点（fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。
  3. 每次散播消息都选择尚未发送过的节点进行散播
  4. 收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。

这里一共有 16 个节点，节点 1 为初始被感染节点，通过 Gossip 过程，最终所有节点都被感染：

Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip 协议是一个多主协议，所有写操作可以由不同节点发起，并且同步给其他副本。Gossip 内组成的网络节点都是对等节点，是非结构化网络。

3.6.4 消息传播方式

Gossip 的消息传播方式有两种：反熵传播和谣言传播。

  • 反熵传播（Anti-Entropy）：以固定的概率传播所有的数据

Anti-Entropy 使用 “simple epidemics” 的方式，这种模型也称为 SI model。所以其包含两种状态 Suspective（病原）和 Infective（感染）。处于 Infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点；处于 Suspective 状态的节点代表其并没有收到来自其他节点的更新。

Anti-Entropy 工作方式是每个节点周期性地随机选择其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异。Anti-Entropy 这种方法非常可靠，但是每次节点两两交换自己的所有数据会带来非常大的通信负担，因此不会频繁使用。

  • 谣言传播（Rumor-Mongering）：仅传播新到达的数据

Rumor-Mongering 使用 “complex epidemics” 方法，相比 Anti-Entropy 多了一种状态 Removed（愈除），这种模型也称为 SIR model。处于 Removed 状态的节点说明其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

因为 Rumor 消息会在某个时间标记为 removed，然后不会发送给其他节点，所以 Rumor-Mongering 类型的 Gossip 协议有极小概率使得更新不会达到所有节点。

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

3.6.5 通信方式

Gossip 协议最终目的是将数据分发到网络中的每一个节点。不管是 Anti-Entropy 还是 Rumor-Mongering 都涉及到节点间的数据交互方式，Gossip 网络中两个节点之间存在三种通信方式：Push、Pull 以及 Push&Pull。

  • Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
  • Pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
  • Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push/Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push/Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push/Pull 的收敛速度也是最快的。

3.6.6 复杂度分析

对于一个节点数为 N 的网络来说，假设每个 Gossip 周期，新感染的节点都能再感染至少一个新节点，那么 Gossip 协议退化成一个二叉树查找，经过 LogN 个周期之后，感染全网，时间开销是 O(LogN)。由于每个周期，每个节点都会至少发出一次消息，因此，消息复杂度（消息数量 = N*N）是 O(N^2) 。注意，这是 Gossip 理论上最优的收敛速度，但是在实际情况中，最优的收敛速度是很难达到的。

假设某个节点在第 i 个周期被感染的概率为 pi，第 i 1 个周期被感染的概率为 pi 1 ，

  • Pull 的方式
p_{i 1}=p_i^2
  • Push 方式

显然 Pull 的收敛速度大于 Push ，而每个节点在每个周期被感染的概率都是固定的 p (0<p<1)，因此 Gossip 算法是基于 p 的平方收敛，也称为概率收敛，这在众多的一致性算法中是非常独特的。

3.6.7 优点

Gossip 是一种去中心化的分布式协议，数据通过节点像病毒一样逐个传播。因为是指数级传播，整体传播速度非常快，很像现在大流行的新冠病毒。

  • 扩展性（Scalable） 网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。
  • 容错（Fault-tolerance） 网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。
  • 去中心化 Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。
  • 一致性收敛 Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
  • 简单 Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

3.6.8 缺点

Gossip 拥有很多优点，但是分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要有：

  • 消息的延迟 由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是需要通过多轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。
  • 消息冗余 Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。
  • 拜占庭问题 如果有一个恶意传播消息的节点，Gossip 协议的分布式系统就会出问题。

上述优缺点的本质是因为Gossip是一个带冗余的容错算法，是一个最终一致性算法，虽然无法保证在某个时刻所有节点状态一致，但可以保证在“最终所有节点一致”，“最终”的时间是一个理论无法明确的时间点。所以适合于AP场景的数据一致性处理。

3.6.9 工程上的使用

Gossip 协议可以支持以下需求：

  • Database replication
  • 消息传播
  • Cluster membership
  • Failure 检测
  • Overlay Networks
  • Aggregations（比如计算平均值、最大值以及总和）

Gossip 协议在很多组件中被用到：

  • Riak 使用 Gossip 协议来共享和传递集群的环状态（ring state）和存储桶属性（bucket properties）。
  • 数据库 Apache Cassandra：节点间的信息交换使用了 Gossip 协议，因此所有节点都可以快速了解集群中的所有其他节点。
  • Dynamo：采用基于 Gossip 协议的分布式故障检测和成员协议，这样集群中添加或移除节点，其他节点可以快速检测到。
  • Consul：使用了称为 SERF 的 Gossip 协议，主要有两个目的：一发现新的节点或者发现故障节点；二为一些重要的事件（比如 Leader 选举）传播提供可靠、快速的传播。
  • Amazon s3 使用 Gossip 协议将服务的状态传递给系统。

参考文献

CAP theorem.wikipedia Base: An Acid Alternative 分布式系统的 CAP 定理与 BASE 理论 《The Part-Time Parliament》 《Paxos Made Simple》 Paxos 算法与 Raft 算法 | 区块链技术指南 Paxos算法详解 | 知乎 Raft算法详解 | 知乎 分布式一致性算法-Paxos、Raft、ZAB、Gossip 分布式算法 - ZAB算法 | Java 全栈知识体系 P2P 网络核心技术：Gossip 协议 一致性算法-Gossip协议详解 | 腾讯云 分布式原理：一文了解 Gossip 协议 | 51CTO博客

编程算法 分布式 raft ide

0 人点赞