# CAP & BASE 理论详解

# CAP 理论

# 简介

CAP 理论指的是 **在一个分布式系统中，在设计读写操作时，只能同时满足以下三点中的两个：一致性（C）、可用性（A）、分区容错性（P）**。

• 一致性（ C onsistency）：分布式系统中多个主机之间是否能够保持数据一致的特性。即，当系统数据发生更新操作后，各个主机中的数据仍然处于一致的状态。所有节点访问同一份最新的数据副本。

• 可用性（ A vailability）：系统提供的服务必须一直处于可用的状态。即，对于用户的每一个请求，系统（非故障节点）总是可以在有限的时间内对用户做出合理响应（不是错误 / 超时的响应）。

• 分区容错性（ P artition tolerance）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供（满足一致性和可用性的）服务。

  partition-tolerance

  网络分区：分布式系统中，多个节点之间的网络本来是连通的，但是因为某些故障（比如部分节点网络出了问题）某些节点之间不连通了，整个网络就分成了几块区域，这就叫网络分区。

# 不是所谓的 “3 选 2”

大部分人解释这一定律时，常常简单的表述为：“一致性、可用性、分区容忍性三者你只能同时达到其中两个，不可能同时达到”。实际上这是一个非常具有误导性质的说法，而且在 CAP 理论诞生 12 年之后，CAP 之父也在 2012 年重写了之前的论文。

当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提，决定了 P 之后才有 C 和 A 的选择。也就是说分区容错性（Partition tolerance）我们是必须要实现的。

简而言之就是：CAP 理论中分区容错性 P 是一定要满足的，在此基础上，只能满足可用性 A 或者强一致性 C。

因此，分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。比如 ZooKeeper、HBase 就是 CP 架构，Cassandra、Eureka 就是 AP 架构，Nacos 不仅支持 CP 架构也支持 AP 架构。

为啥不可能选择 CA 架构呢？举个例子：若系统出现 “分区”，系统中的某个节点在进行写操作。为了保证 C，必须要禁止其他节点的读写操作，这就和 A 发生冲突了。如果为了保证 A，其他节点的读写操作正常的话，那就和 C 发生冲突了。

选择 CP 还是 AP 的关键在于当前的业务场景，没有定论，比如对于需要确保强一致性的场景如银行一般会选择保证 CP 。

另外，需要补充说明的一点是：如果网络分区正常的话（系统在绝大部分时候所处的状态），也就说不需要保证 P 的时候，C 和 A 能够同时保证。

# CAP 实际应用案例：注册中心

我这里以注册中心来探讨一下 CAP 的实际应用。考虑到很多小伙伴不知道注册中心是干嘛的，这里简单以 Dubbo 为例说一说。

下图是 Dubbo 的架构图。注册中心 Registry 在其中扮演了什么角色呢？提供了什么服务呢？

注册中心负责服务地址的注册与查找，相当于服务的目录，服务提供者和消费者只在启动时与注册中心交互，注册中心不转发请求，压力较小。

常见的可以作为注册中心的组件有：ZooKeeper、Eureka、Nacos...。

1. **ZooKeeper 保证的是 CP。** 任何时刻对 ZooKeeper 的读请求都能得到一致性的结果，但是，ZooKeeper 不保证每次请求的可用性，比如在 Leader 选举过程中，或者半数以上的机器不可用的时候，或者当 Leader 节点中的数据发生了变化但 Follower 还没有同步完成之前，整个 ZooKeeper 集群是不对外提供服务的。
2. Eureka 保证的则是 AP。 Eureka 在设计的时候就是优先保证 A （可用性）。在 Eureka 中不存在什么 Leader 节点，每个节点都是一样的、平等的。因此 Eureka 不会像 ZooKeeper 那样出现选举过程中或者半数以上的机器不可用的时候服务就是不可用的情况。 Eureka 保证即使大部分节点挂掉也不会影响正常提供服务，只要有一个节点是可用的就行了，只不过这个节点上的数据可能并不是最新的。
3. Nacos 不仅支持 CP 也支持 AP。

🐛 修正（参见：issue#1906）：

ZooKeeper 通过可线性化（Linearizable）写入、全局 FIFO 顺序访问等机制来保障数据一致性。多节点部署的情况下， ZooKeeper 集群处于 Quorum 模式。Quorum 模式下的 ZooKeeper 集群，是一组 ZooKeeper 服务器节点组成的集合，其中大多数节点必须同意任何变更才能被视为有效。

由于 Quorum 模式下的读请求不会触发各个 ZooKeeper 节点之间的数据同步，因此在某些情况下还是可能会存在读取到旧数据的情况，导致不同的客户端视图上看到的结果不同，这可能是由于网络延迟、丢包、重传等原因造成的。ZooKeeper 为了解决这个问题，提供了 Watcher 机制和版本号机制来帮助客户端检测数据的变化和版本号的变更，以保证数据的一致性。

# 小结

在进行分布式系统设计和开发时，我们不应该仅仅局限在 CAP 问题上，还要关注系统的扩展性、可用性等等。

在系统发生 “分区” 的情况下，CAP 理论只能满足 CP 或者 AP。要注意的是，这里的前提是系统发生了 “分区”。

如果系统没有发生 “分区” 的话，节点间的网络连接通信正常的话，也就不存在 P 了。这个时候，我们就可以同时保证 C 和 A 了。

总结：如果系统发生 “分区”，我们要考虑选择 CP 还是 AP。如果系统没有发生 “分区” 的话，我们要思考如何保证 CA 。

# BASE 理论

# 简介

BASE 是对 CAP 中一致性 C 和可用性 A 权衡的结果，其来源于对大规模互联网系统分布式实践的总结，是基于 CAP 定理逐步演化而来的，它大大降低了我们对系统的要求，由以下三个短语的简写组成：

• B asically A vailable（基本可用）：分布式系统在出现不可预知故障的时候，允许损失部分可用性。但这绝不等价于系统不可用。
• S oft state（软状态）：允许系统数据存在的中间状态，并认为该中间状态的存在不会影响系统的整体可用性。即，允许系统主机间进行数据同步的过程存在一定延时。软状态，其实就是一种灰度状态，过渡状态。
• E ventually consistent（最终一致性）：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要保证系统数据的实时一致性。

# 核心思想

BASE 理论的核心思想：即使无法做到强一致性 C ，但每个系统都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性 E 。

也就是 **牺牲数据的强一致性 C 来满足系统的基本可用性 BA** ，系统中一部分数据不可用或者不一致时，仍需要保持系统整体 “基本可用”。

**BASE 理论本质上是对 CAP 的延伸和补充，更具体地说，是对 CAP 中 AP 方案的一个补充。**AP 方案只是在系统发生分区的时候放弃一致性，而不是永远放弃一致性。在分区故障恢复后，系统应该达到最终一致性。这一点其实就是 BASE 理论延伸的地方。

# 三要素

# 基本可用（BA）

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。但是，这绝不等价于系统不可用。

• 响应时间上的损失：正常情况下，处理用户请求需要 0.5s 返回结果，但是由于系统出现故障，处理用户请求的时间变为 3 s。
• 系统功能上的损失：正常情况下，用户可以使用系统的全部功能，但是由于系统访问量突然剧增，系统的部分非核心功能无法使用。

# 软状态（S）

软状态指允许系统中的数据存在中间状态（CAP 理论中的数据不一致），并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

# 最终一致性（E）

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

分布式一致性的 3 种级别：

1. 强一致性：系统写入了什么，读出来的就是什么。
2. 弱一致性：不一定可以读取到最新写入的值，也不保证多少时间之后读取到的数据是最新的，只是会尽量保证某个时刻达到数据一致的状态。
3. 最终一致性：弱一致性的升级版，系统会保证在一定时间内达到数据一致的状态。

业界比较推崇是最终一致性级别，但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。

那实现最终一致性的具体方式是什么呢？《分布式协议与算法实战》 中是这样介绍：

• 读时修复：在读取数据时，检测数据的不一致，进行修复。比如 Cassandra 的 Read Repair 实现，具体来说，在向 Cassandra 系统查询数据的时候，如果检测到不同节点的副本数据不一致，系统就自动修复数据。
• 写时修复: 在写入数据，检测数据的不一致时，进行修复。比如 Cassandra 的 Hinted Handoff 实现。具体来说，Cassandra 集群的节点之间远程写数据的时候，如果写失败 就将数据缓存下来，然后定时重传，修复数据的不一致性。
• 异步修复：这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复。

比较推荐 写时修复，这种方式对性能消耗比较低。

# 小结

ACID 是数据库事务完整性的理论，CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。

# Paxos 算法详解

# 背景

Paxos 算法是 Leslie Lamport（莱斯利・兰伯特）在 1990 年提出了一种 **分布式系统共识算法**。这也是第一个被证明完备的共识算法（前提是不存在拜占庭将军问题，也就是没有恶意节点）。

为了介绍 Paxos 算法，兰伯特专门写了一篇幽默风趣的论文。在这篇论文中，他虚拟了一个叫做 Paxos 的希腊城邦来更形象化地介绍 Paxos 算法。

不过，审稿人并不认可这篇论文的幽默。于是，他们就给兰伯特说：“如果你想要成功发表这篇论文的话，必须删除所有 Paxos 相关的故事背景”。兰伯特一听就不开心了：“我凭什么修改啊，你们这些审稿人就是缺乏幽默细胞，发不了就不发了呗！”。

于是乎，提出 Paxos 算法的那篇论文在当时并没有被成功发表。

直到 1998 年，系统研究中心 (Systems Research Center，SRC）的两个技术研究员需要找一些合适的分布式算法来服务他们正在构建的分布式系统，Paxos 算法刚好可以解决他们的部分需求。因此，兰伯特就把论文发给了他们。在看了论文之后，这俩大佬觉得论文还是挺不错的。于是，兰伯特在 1998 年重新发表论文 《The Part-Time Parliament》。

论文发表之后，各路学者直呼看不懂，言语中还略显调侃之意。这谁忍得了，在 2001 年的时候，兰伯特专门又写了一篇 《Paxos Made Simple》 的论文来简化对 Paxos 的介绍，主要讲述两阶段共识协议部分，顺便还不忘嘲讽一下这群学者。

《Paxos Made Simple》这篇论文就 14 页，相比于 《The Part-Time Parliament》的 33 页精简了不少。最关键的是这篇论文的摘要就一句话：

The Paxos algorithm, when presented in plain English, is very simple.

翻译过来的意思大概就是：当我用无修饰的英文来描述时，Paxos 算法真心简单！

有没有感觉到来自兰伯特大佬满满地嘲讽的味道？

# 介绍

Paxos 算法是第一个被证明完备的分布式系统共识算法。共识算法的作用是 **让分布式系统中的多个节点之间对某个提案（Proposal）达成一致的看法**。提案的含义在分布式系统中十分宽泛，像哪一个节点是 Leader 节点、多个事件发生的顺序等等都可以是一个提案。

兰伯特当时提出的 Paxos 算法主要包含 2 个部分:

• Basic Paxos 算法：描述的是多节点之间如何就某个值 (提案 Value) 达成共识。
• Multi-Paxos 思想：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。Multi-Paxos 说白了就是执行多次 Basic Paxos ，核心还是 Basic Paxos 。

由于 Paxos 算法在国际上被公认的非常难以理解和实现，因此不断有人尝试简化这一算法。到了 2013 年才诞生了一个比 Paxos 算法更易理解和实现的共识算法 —Raft 算法 。更具体点来说，Raft 是 Multi-Paxos 的一个简化变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现。

针对没有恶意节点的情况，除了 Raft 算法之外，当前最常用的一些共识算法比如 ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进的。

针对存在恶意节点的情况，一般使用的是 工作量证明（POW，Proof-of-Work）、 权益证明（PoS，Proof-of-Stake ） 等共识算法。这类共识算法最典型的应用就是区块链，就比如说前段时间以太坊官方宣布其共识机制正在从工作量证明 (PoW) 转变为权益证明 (PoS)。

区块链系统使用的共识算法需要解决的核心问题是 **拜占庭将军问题** ，这和我们日常接触到的 ZooKeeper、Etcd、Consul 等分布式中间件不太一样。

下面我们来对 Paxos 算法的定义做一个总结：

• Paxos 算法是兰伯特在 1990 年提出了一种分布式系统共识算法。
• 兰伯特当时提出的 Paxos 算法主要包含 2 个部分: Basic Paxos 算法和 Multi-Paxos 思想。
• Raft 算法、ZAB 协议、 Fast Paxos 算法都是基于 Paxos 算法改进而来。

# Basic Paxos 算法

Basic Paxos 中存在 3 个重要的角色：

1. 提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接受客户端的请求，并发起提案。提案信息通常包括提案编号 (Proposal ID) 、提议的值 (Value)。
2. 接受者（Acceptor）：也可以叫做投票员（voter），负责对提议者的提案进行投票，同时需要记住自己的投票历史；
3. 学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

为了减少实现该算法所需的节点数，一个节点可以身兼多个角色。并且，一个提案被选定需要被半数以上的 Acceptor 接受。这样的话，Basic Paxos 算法还具备容错性，在少于一半的节点出现故障时，集群仍能正常工作。

# Multi Paxos 思想

Basic Paxos 算法的仅能就单个值达成共识，为了能够对一系列的值达成共识，我们需要用到 Multi Paxos 思想。

⚠️注意：Multi-Paxos 只是一种思想，这种思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识。也就是说，Basic Paxos 是 Multi-Paxos 思想的核心，Multi-Paxos 就是多执行几次 Basic Paxos。

由于兰伯特提到的 Multi-Paxos 思想缺少代码实现的必要细节 (比如怎么选举领导者)，所以在理解和实现上比较困难。

不过，也不需要担心，我们并不需要自己实现基于 Multi-Paxos 思想的共识算法，业界已经有了比较出名的实现。像 Raft 算法就是 Multi-Paxos 的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现，实际项目中可以优先考虑 Raft 算法。

# Raft 算法详解

# 背景

当今的数据中心和应用程序在高度动态的环境中运行，为了应对高度动态的环境，它们通过额外的服务器进行横向扩展，并且根据需求进行扩展和收缩。同时，服务器和网络故障也很常见。

因此，系统必须在正常操作期间处理服务器的上下线。它们必须对变故做出反应并在几秒钟内自动适应；对客户来说的话，明显的中断通常是不可接受的。

幸运的是，分布式共识可以帮助应对这些挑战。

# 拜占庭将军问题

在介绍共识算法之前，先介绍一个简化版拜占庭将军的例子来帮助理解共识算法。

假设多位拜占庭将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成是否要进攻的一致性决定？

解决方案大致可以理解成：先在所有的将军中选出一个大将军，用来做出所有的决定。

举例如下：假如现在一共有 3 个将军 A，B 和 C，每个将军都有一个随机时间的倒计时器。

1. 假设 A 将军的倒计时先结束，这个将军就把自己当成大将军候选人，然后派信使传递选举投票的信息给将军 B 和 C；
2. 如果将军 B 和 C 还没有把自己当作候选人（自己的倒计时还没有结束），并且没有把选举票投给其他人，它们就会把票投给将军 A；
3. 信使回到将军 A 时，它知道自己收到了足够的票数，成为了大将军，此后是否需要进攻就由大将军 A 决定；
4. 然后 A 将军再去派信使通知另外两个将军，自己已经成为了大将军。如果一段时间还没收到将军 B 和 C 的回复（信使可能会被暗杀），那就再重派一个信使，直到收到回复。

# 共识算法

共识是可容错系统中的一个基本问题：即使面对故障，服务器也可以在共享状态上达成一致。

共识算法允许一组节点像一个整体一样一起工作，即使其中的一些节点出现故障也能够继续工作下去，其正确性主要是源于复制状态机的性质：一组 Server 的状态机计算相同状态的副本，即使有一部分的 Server 宕机了，它们仍然能够继续运行。

一般通过使用复制日志来实现复制状态机。每个 Server 存储着一份包括命令序列的日志文件，状态机会按顺序执行这些命令。因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态，得到相同的输出。

因此，共识算法的工作就是保持复制日志的一致性。服务器上的共识模块从客户端接收命令并将它们添加到日志中。它与其他服务器上的共识模块通信，以确保即使某些服务器发生故障。每个日志最终包含相同顺序的请求。一旦命令被正确地复制，它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令，并将输出返回给客户端。因此，这些服务器形成了一个单一的、高度可靠的状态机。

适用于实际系统的共识算法通常具有以下特性：

• 安全。确保在非拜占庭条件（也就是上文中提到的简易版拜占庭）下的安全性，包括网络延迟、分区、包丢失、复制和重新排序。
• 高可用。只要大多数服务器都是可操作的，并且可以相互通信，也可以与客户端进行通信，那么这些服务器就可以看作完全功能可用的。因此，一个典型的由五台服务器组成的集群可以容忍任何两台服务器端故障。假设服务器因停止而发生故障；它们稍后可能会从稳定存储上的状态中恢复并重新加入集群。
• 一致性不依赖时序。错误的时钟和极端的消息延迟，在最坏的情况下也只会造成可用性问题，而不会产生一致性问题。
• 在集群中大多数服务器响应，命令就可以完成，不会被少数运行缓慢的服务器来影响整体系统性能。

# Raft 算法基础

Raft 算法是一种 **通过对日志复制管理来达到集群节点一致性** 的算法。这个日志复制管理发生在集群节点中的 Leader 与 Followers 之间。Raft 通过选举出的 Leader 节点负责管理日志复制过程，以实现各个节点间数据的一致性。

# 节点类型

一个 Raft 集群包括若干服务器，在任意的时间，每个服务器一定会处于以下三个状态中的一个：

• Leader ：负责发起心跳；响应客户端的读写请求；创建、同步（复制）日志；
• Candidate ：Leader 选举的候选人，由 Follower 转化而来；发起投票参与竞选；
• Follower ：可以处理客户端的读请求；接受 Leader 的心跳；同步来自于 Leader 的日志；当接收到其它 Candidate 的投票请求后，可以进行投票；当 Leader 挂了后，会转变为 Candidate 发起 Leader 选举；

在正常的情况下，只有一个服务器是 Leader，剩下的服务器是 Follower。Follower 是被动的，它们不会发送任何请求，只是响应来自 Leader 和 Candidate 的请求。

# 任期（term）

如下图所示，raft 算法将时间划分为任意长度的任期（term），任期用连续的数字表示，看作当前 term 号。

• 每一个任期的开始都是一次选举，在选举开始时，一个或多个 Candidate 会尝试成为 Leader。
• 如果一个 Candidate 赢得了选举，它就会在该任期内担任 Leader。
• 如果没有选出 Leader，将会开启另一个任期，并立刻开始下一次选举。【t3】
• raft 算法保证在给定的一个任期最少要有一个 Leader。

任期规则：

• 每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号；
• 如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值；
• 如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower；
• 如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求；

# 日志

• entry ：每一个事件成为 entry，只有 Leader 可以创建 entry。entry 的内容为 <term,index,cmd> 其中 cmd 是可以应用到状态机的操作。

• log ：由 entry 构成的数组，每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。

# 🌟Leader 选举

Raft 算法使用心跳机制来触发集群中 Leader 的选举。

如果一台服务器能够收到来自 Leader 或者 Candidate 的有效信息，那么它会一直保持为 Follower 状态，并且刷新自己的 electionElapsed（选举已用时间），重新计时。

Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位。如果一个 Follower 在一个心跳超时周期内没有收到 Leader 的心跳信息，则认为 Leader 挂了，这叫做选举超时。

为了开始新的选举，Follower 会自增自己的 term 号，并且转换状态为 Candidate。然后他会向所有节点发起 RequestVoteRPC 请求， Candidate 的状态会持续到以下情况发生：

• 该节点赢得选举。条件是该 Candidate 在一个任期内，收到了来自集群内的多数选票 （N/2+1） ，它就可以成为 Leader。然后会将消息广播给所有其它节点，通知大家我是新的 Leader 了。

• 其他节点赢得选举。在该 Candidate 等待选票的时候，它可能收到其他节点声明自己是 Leader 的心跳，此时有两种情况：

  • 对方的 term 号 ≥ 自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower 。
  • 对方的 term 号 ＜ 自己的 term 号，那么会拒绝该请求，并让对方节点更新 term 。

• 一轮选举结束无人胜出，重新选举。由于可能同一时刻出现多个 Candidate，导致没有 Candidate 获得大多数选票（即：没有收到过半选票，也没有收到新 Leader 通知）。如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。

  raft 使用了 **随机的选举超时时间**（ randomized election timeouts ）来避免上述情况。其会为这些 Follower 随机分配一个选举发起时间 election timeout，只有到达了 election timeout 时间的 Follower 才能转变为 candidate，否则等待。那么 election timeout 较小的 Follower 则会转变为 candidate 然后先发起选举，一般情况下其会优先获取到过半选票成为新的 leader。

# 日志复制（数据同步）

一旦选出了 Leader，它就开始接受客户端的请求。每一个客户端的请求都包含一条需要被复制状态机（ Replicated State Machine ）执行的命令。

1. Leader 收到客户端请求后，会生成一个 entry，包含 <index,term,cmd> 。将这个 entry 添加到自己的日志末尾后，向所有的节点广播该 entry，要求其他服务器复制这条 entry。

2. 如果 Follower 接受该 entry，则会将 entry 添加到自己的日志后面，同时返回给 Leader 同意。

3. 如果 Leader 收到了多数的成功响应，Leader 会将这个 entry 应用到自己的状态机中，之后可以认为这个 entry 是 committed 的，并且向客户端返回执行结果。

raft 保证以下两个性质：

• 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd
• 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同

通过 “仅有 Leader 可以生成 entry” 来保证第一个性质，第二个性质需要 **一致性检查** 来进行保证。

一般情况下，Leader 和 Follower 的日志保持一致，然后，Leader 的崩溃会导致日志不一样，这样一致性检查会产生失败。Leader 通过强制 Follower 复制自己的日志来处理日志的不一致。这就意味着，在 Follower 上的冲突日志会被 Leader 的日志覆盖。为了使得 Follower 的日志和 Leader 的日志一致，Leader 需要找到 Follower 与它日志一致的地方，然后删除 Follower 在该位置之后的日志，接着把 Leader 自己在这之后的日志发送给 Follower。

Leader 给每一个 Follower 维护了一个 nextIndex ，它表示 Leader 将要发送给该 Follower 的下一条日志条目的索引。当一个 Leader 开始掌权时，它会将 nextIndex 初始化为它的最新的日志条目索引数 + 1。如果一个 Follower 的日志和 Leader 的不一致， AppendEntries 一致性检查会在下一次 AppendEntries RPC 时返回失败。在失败之后，Leader 会将 nextIndex 递减然后重试 AppendEntries RPC 。最终 nextIndex 会达到一个 Leader 和 Follower 日志一致的地方。这时， AppendEntries 会返回成功，Follower 中冲突的日志条目都被移除了，并且添加所缺少的上了 Leader 的日志条目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日志就一致了，这样的状态会保持到该任期结束。

# Leader 宕机处理

# 请求到达前 Leader 挂了

Leader 在 client 发送写操作请求到达之前就挂了，因为请求还没有到达集群，所以这个请求对于集群来说就没有存在过，对集群数据的一致性没有任何影响。Leader 挂了之后，会选举产生新的 Leader。

由于 Stale Leader （旧领导）并未向 client 发送成功处理响应，所以 client 会重新发送该写操作请求。

# 未开始同步数据前 Leader 挂了

client 发送写操作请求给 Leader，请求到达 Leader 后，Leader 还没有开始向 Followers 发出数据就挂了。这时集群会选举产生新的 Leader。Stale Leader 重启后会作为 Follower 重新加入集群，并同步新 Leader 中的数据以保证数据一致性。之前接收到 client 的数据被丢弃。

由于 Stale Leader 并未向 client 发送成功处理响应，所以 client 会重新发送该写操作请求。

# 同步完部分后 Leader 挂了

client 发送写操作请求给 Leader，Leader 接收完数据后向所有 Follower 发送数据。在部分 Follower 接收到数据后 Leader 挂了。由于 Leader 挂了，就会发起新的 Leader 选举。

• 若 Leader 产生于已完成数据接收的 Follower，其会继续将前面接收到的写操作请求转换为日志，并写入到本地状态机，并向所有 Flollower 发出询问。在获取过半同意响应后会向所有 Followers 发送 commit 指令，同时向 client 进行响应。
• 若 Leader 产生于尚未完成数据接收的 Follower，那么原来已完成接收的 Follower 则会放弃曾接收到的数据。由于 client 没有接收到响应，所以 client 会重新发送该写操作请求。

# commit 通知发出后 Leader 挂了

client 发送写操作请求给 Leader， Leader 也成功向所有 Followers 发出的 commit 指令，并向 client 发出响应后，Leader 挂了。

由于 Stale Leader 已经向 client 发送成功接收响应，且 commit 通知已经发出，说明这个写操作请求已经被 server 成功处理。

# 安全性

# 选举限制

Leader 需要保证自己存储全部已经提交的日志条目。这样才可以使日志条目只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的日志条目。

每个 Candidate 发送 RequestVoteRPC 时，都会带上最后一个 entry 的信息。所有节点收到投票信息时，会对该 entry 进行比较，如果发现自己的日志更新，则拒绝投票给该 Candidate。

判断日志新旧的方式：

• 如果两个日志的 term 不同，term 大的更新
• 如果 term 相同，更长的 index 更新

# 节点崩溃

如果 Leader 崩溃，集群中的节点在 electionTimeout 时间内没有收到 Leader 的心跳信息就会触发新一轮的 Leader 选举，在 Leader 选举期间，整个集群对外是不可用的。

如果 Follower 和 Candidate 崩溃，处理方式会简单很多。之后发送给它的 RequestVoteRPC 和 AppendEntriesRPC 会失败。由于 raft 的所有请求都是幂等的，所以失败的话会无限的重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。

# 时间与可用性

raft 的要求之一就是安全性不依赖于时间：系统不能仅仅因为一些事件发生的比预想的快一些或者慢一些就产生错误。为了保证上述要求，最好能满足以下的时间条件：

broadcastTime << electionTimeout << MTBF

• broadcastTime ：向其他节点并发发送消息的平均响应时间；
• electionTimeout ：选举超时时间；
• MTBF(mean time between failures) ：单台机器的平均健康时间；

broadcastTime 应该比 electionTimeout 小一个数量级，为的是使 Leader 能够持续发送心跳信息（heartbeat）来阻止 Follower 开始选举；

electionTimeout 也要比 MTBF 小几个数量级，为的是使得系统稳定运行。当 Leader 崩溃时，大约会在整个 electionTimeout 的时间内不可用；我们希望这种情况仅占全部时间的很小一部分。

由于 broadcastTime 和 MTBF 是由系统决定的属性，因此需要决定 electionTimeout 的时间。

一般来说，broadcastTime 一般为 0.5～20ms ，electionTimeout 可以设置为 10～500ms ，MTBF 一般为一两个月。

# 动画演示

http://thesecretlivesofdata.com/raft/

# raft 概述

# Leader 选举

在 Raft 中，有两个控制选举的超时设置：

• election timeout （选举超时）：表示 Follower 等待转变为 Candidate 的倒计时间，随机设置在 150ms ~ 300ms 之间。某个 Follower 率先选举超时后，它成为 Candidate，开始新的选举任期（term 加 1），并为自己投一票，同时向其他节点发送请求投票的消息。如果接收节点在本任期内尚未投票，那么它将投票给 Candidate。
• heartbeat timeout （心跳超时）：

分裂投票的例子：

# 日志复制

# Gossip 协议详解

gossip：闲话、流言蜚语

# 背景

在分布式系统中，不同的节点进行数据 / 信息共享是一个基本的需求。

一种比较简单粗暴的方法就是集中式发散消息，简单来说就是一个主节点同时共享最新信息给其他所有节点，比较适合中心化系统。这种方法的缺陷也很明显，节点多的时候不光同步消息的效率低，还太依赖与中心节点，存在单点风险问题。

于是，分散式发散消息的 Gossip 协议 就诞生了。

# 介绍

Gossip 协议 也叫 Epidemic 协议（流行病协议）或者 Epidemic propagation 算法（疫情传播算法），别名很多。不过这些名字的特点都具有 **随机传播特性**（联想一下病毒传播、癌细胞扩散等生活中常见的情景），这也正是 Gossip 协议最主要的特点。

Gossip 协议最早是在 ACM 上的一篇 1987 年发表的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出的。根据论文标题，我们大概就能知道 Gossip 协议当时提出的主要应用是在分布式数据库系统中各个副本节点同步数据。

正如 Gossip 协议其名一样，这是一种随机且带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。

在 Gossip 协议下，没有所谓的中心节点，每个节点周期性地随机找一个节点互相同步彼此的信息，理论上来说，各个节点的状态最终会保持一致。

下面我们来对 Gossip 协议的定义做一个总结：Gossip 协议是一种允许在分布式系统中共享状态的去中心化通信协议，通过这种通信协议，我们可以将信息传播给网络或集群中的所有成员。

# 应用

NoSQL 数据库 Redis 和 Apache Cassandra、服务网格解决方案 Consul 等知名项目都用到了 Gossip 协议，学习 Gossip 协议有助于我们搞清很多技术的底层原理。

我们这里以 Redis Cluster 为例说明 Gossip 协议的实际应用。

我们经常使用的分布式缓存 Redis 的官方集群解决方案（3.0 版本引入） Redis Cluster 就是基于 Gossip 协议来实现集群中各个节点数据的最终一致性。

Redis Cluster 是一个典型的分布式系统，分布式系统中的各个节点需要互相通信。既然要相互通信就要遵循一致的通信协议，Redis Cluster 中的各个节点基于 Gossip 协议 来进行通信共享信息，每个 Redis 节点都维护了一份集群的状态信息。

Redis Cluster 的节点之间会相互发送多种 Gossip 消息：

• MEET：在 Redis Cluster 中的某个 Redis 节点上执行 CLUSTER MEET ip port 命令，可以向指定的 Redis 节点发送一条 MEET 信息，用于将其添加进 Redis Cluster 成为新的 Redis 节点。
• PING/PONG：Redis Cluster 中的节点都会定时地向其他节点发送 PING 消息，来交换各个节点状态信息，检查各个节点状态，包括在线状态、疑似下线状态 PFAIL 和已下线状态 FAIL。
• FAIL：Redis Cluster 中的节点 A 发现 B 节点 PFAIL，并且在下线报告的有效期限内集群中半数以上的节点将 B 节点标记为 PFAIL，节点 A 就会向集群广播一条 FAIL 消息，通知其他节点将故障节点 B 标记为 FAIL 。
• ……

下图就是主从架构的 Redis Cluster 的示意图，图中的虚线代表的就是各个节点之间使用 Gossip 进行通信 ，实线表示主从复制。

有了 Redis Cluster 之后，不需要专门部署 Sentinel 集群服务了。Redis Cluster 相当于是内置了 Sentinel 机制，内部的各个节点通过 Gossip 协议互相探测健康状态，在故障时可以自动切换。

# 消息传播模式

Gossip 设计了两种可能的消息传播模式：反熵（Anti-Entropy） 和 传谣（Rumor-Mongering）。

# 反熵（Anti-Entropy）

根据维基百科：

熵的概念最早起源于物理学，用于度量一个热力学系统的混乱程度。熵最好理解为不确定性的量度，而不是确定性的量度，因为越随机的信源的熵越大。

在这里，你可以把反熵中的熵理解为节点之间数据的混乱程度 / 差异性，反熵就是指消除不同节点中数据的差异，提升节点间数据的相似度，从而降低熵值。

具体是如何反熵的呢？集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据，来消除两者之间的差异，实现数据的最终一致性。

在实现反熵的时候，主要有推、拉和推拉三种方式：

• 推：就是将自己的所有副本数据，推给对方，修复对方副本中的熵。
• 拉：就是拉取对方的所有副本数据，修复自己副本中的熵。
• 推拉：就是同时修复自己副本和对方副本中的熵。

伪代码如下：

在我们实际应用场景中，一般不会采用随机的节点进行反熵，而是需要可以的设计一个闭环。这样的话，我们能够在一个确定的时间范围内实现各个节点数据的最终一致性，而不是基于随机的概率。像 InfluxDB 就是这样来实现反熵的。

1. 节点 A 推送数据给节点 B，节点 B 获取到节点 A 中的最新数据。
2. 节点 B 推送数据给 C，节点 C 获取到节点 A，B 中的最新数据。
3. 节点 C 推送数据给 A，节点 A 获取到节点 B，C 中的最新数据。
4. 节点 A 再推送数据给 B 形成闭环，这样节点 B 就获取到节点 C 中的最新数据。

虽然反熵很简单实用，但是节点过多或者节点动态变化的话，反熵就不太适用了。这个时候，我们想要实现最终一致性就要靠 传谣 (Rumor mongering) 。

# 传谣（Rumor-Mongering）

谣言传播指的是分布式系统中的一个节点一旦有了新数据之后，就会变为活跃节点，活跃节点会周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。

如下图所示（下图来自于 INTRODUCTION TO GOSSIP 这篇文章）：

伪代码如下：

谣言传播比较适合节点数量比较多的情况，不过，这种模式下要尽量避免传播的信息包不能太大，避免网络消耗太大。

# 小结

• 反熵（Anti-Entropy）会传播节点的所有数据，而谣言传播（Rumor-Mongering）只会传播节点新增的数据。

• 一般会给反熵设计一个闭环。

• 谣言传播（Rumor-Mongering）比较适合节点数量比较多或者节点动态变化的场景。

# 优缺点

优势：

1、相比于其他分布式协议 / 算法来说，Gossip 协议理解起来非常简单。

2、能够容忍网络上节点的随意地增加或者减少，宕机或者重启，因为 Gossip 协议下这些节点都是平等的，去中心化的。新增加或者重启的节点在理想情况下最终是一定会和其他节点的状态达到一致。

3、速度相对较快。节点数量比较多的情况下，扩散速度比一个主节点向其他节点传播信息要更快（多播）。

缺陷 :

1、消息需要通过多个传播的轮次才能传播到整个网络中，因此，必然会出现各节点状态不一致的情况。毕竟，Gossip 协议强调的是最终一致，至于达到各个节点的状态一致需要多长时间，谁也无从得知。

2、由于拜占庭将军问题，不允许存在恶意节点。

3、可能会出现消息冗余的问题。由于消息传播的随机性，同一个节点可能会重复收到相同的消息。

# 总结

• Gossip 协议是一种允许在分布式系统中共享状态的通信协议，通过这种通信协议，我们可以将信息传播给网络或集群中的所有成员。

• Gossip 协议被 Redis、Apache Cassandra、Consul 等项目应用。

• 谣言传播（Rumor-Mongering）比较适合节点数量比较多或者节点动态变化的场景