CAP 理论

一致性（Consistency）

客户端的每次读操作，不管访问哪个节点，要么读到的都是同一份最新的数据，要么读取失败。

你可以把一致性看作是分布式系统对访问本系统的客户端的一种承诺:不管你访问哪个节点，要么我给你返回的都是绝对一致的数据，要么你都读取失败。你可以看到，一致性强调的不是数据完整，而是各节点间的数据一致。

可用性（Availability）

任何来自客户端的请求，不管访问哪个节点，都能得到响应数据，但不保证是同一份最新数据。

你也可以把可用性看作是分布式系统对访问本系统的客户端的另外一种承诺:我尽力给你返回数据，不会不响应你，但是我不保证每个节点给你的数据都是最新的。
这个指标强调的是服务可用，但不保证数据的一致。

分区容错性（Partition Tolerance）

当节点间出现任意数量的消息丢失或高延迟的时候，系统仍然可以继续提供服务。

也就是说，分布式系统在告诉访问本系统的客户端: 不管我的内部出现什么样的数据同步问题，我会一直运行，提供服务。这个指标，强调的是集群对分区故障的容错能力。

因为分布式系统与单机系统不同，它涉及到多节点间的通讯和交互，节点间的分区故障是必然发生的，所以我要提醒你，在分布式系统中分区容错性是必须要考虑的。

CAP不可能三角

对于一个分布式系统而言，一致性(Consistency)、可用性 (Availability)、分区容错性(Partition Tolerance)3 个指标不可兼得，只能在 3 个指标中选择 2 个。

如何使用CAP理论

只要有网络交互就一定会有延迟和数据丢失，而这种状况我们必须接受，还必须保证系统不能挂掉。所以就像我上面提到的，节点间的分区故障是必然发生的。也就是说，分区容错性(P)是前提，是必须要保证的。

CP

当选择了一致性(C)的时候，如果因为消息丢失、延迟过高发生了网络分区，部分节点无法保证特定信息是最新的，那么这个时候，当集群节点接收到来自客户端的写请求时，因为无法保证所有节点都是最新信息，所以系统将返回写失败错误，也就是说集群拒绝新数据写入。

AP

当选择了可用性(A)的时候，系统将始终处理客户端的查询，返回特定信息，如果发生了网络分区，一些节点将无法返回最新的特定信息，它们将返回自己当前的相对新的信息。

这里我想强调一点，大部分人对 CAP 理论有个误解，~~认为无论在什么情况下，分布式系统都只能在 C 和 A 中选择 1 个。~~ 其实，在不存在网络分区的情况下，也就是分布式系统正常运行时(这也是系统在绝大部分时候所处的状态)，就是说在不需要 P 时，C 和 A 能够同时保证。只有当发生分区故障的时候，也就是说需要 P 时，才会在 C 和 A 之间做出选择。而且如果各节点数据不一致，影响到了系统运行或业务运行(也就是说会有负面的影响)，推荐选择 C，否则选 A。

应用

CA 模型，在分布式系统中不存在。因为舍弃 P，意味着舍弃分布式系统，就比如单机版关系型数据库 MySQL，如果 MySQL 要考虑主备或集群部署时，它必须考虑 P。
CP 模型，采用 CP 模型的分布式系统，一旦因为消息丢失、延迟过高发生了网络分区，就影响用户的体验和业务的可用性。因为为了防止数据不一致，集群将拒绝新数据的写入，典型的应用是 ZooKeeper，Etcd 和 HBase。
AP 模型，采用 AP 模型的分布式系统，实现了服务的高可用。用户访问系统的时候，都能得到响应数据，不会出现响应错误，但当出现分区故障时，相同的读操作，访问不同的节点，得到响应数据可能不一样。典型应用就比如 Cassandra 和 DynamoDB。

ACID理论

二阶段提交协议

二阶段提交协议，顾名思义，就是通过二阶段的协商来完成一个提交操作

第一阶段 - 请求阶段(表决/投票阶段)

事务协调者通知每个参与者准备提交或取消事务，然后进入表决过程，参与者将告知协调者自己的决策: 同意(事务参与者本地作业执行成功)或取消（本地作业执行故障）

第一个阶段，每个参与者投票表决事务是放弃还是提交。一旦参与者投票要求提交事务，那么就不允许放弃事务。也就是说，在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己那一部分，即使参与者出现故障或者中途被替换掉。 这个特性，是我们需要在代码实现时保障的。

第二阶段 - 提交阶段(执行阶段)

在该阶段，事务协调者将基于第一个阶段的投票结果进行决策: 提交或取消

当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务

问题

不管是原始的二阶段提交协议，还是 XA 协议，都存在一些问题:

在提交请求阶段，需要预留资源，在资源预留期间，其他人不能操作(比如，XA 在第一阶段会将相关资源锁定);
数据库是独立的系统。

因为上面这两点，我们无法根据业务特点弹性地调整锁的粒度，而这些都会影响数据库的并发性能。

TCC（Try-Confirm-Cancel）

TCC 是 Try(预留)、Confirm(确认)、Cancel(撤销) 3 个操作的简称，它包含了预留、确认或撤销这 2 个阶段。

协调者向参与者发送Try请求，参与者如果可以提交就返回yes响应，否则返回no响应。
如果参与者都返回yes，就执行Confirm 操作，如果出现问题或不全是yes就执行Cancel操作。

其实在我看来，TCC 本质上是补偿事务，**它的核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作(也就是撤销操作)**。它是一个业务层面的协议，你也可以将 TCC 理解为编程模型，TCC 的 3 个操作是需要在业务代码中编码实现的，为了实现一致性，确认操作和补偿操作必须是等幂的，因为这 2 个操作可能会失败重试。
另外，TCC 不依赖于数据库的事务，而是在业务中实现了分布式事务，这样能减轻数据库的压力，但对业务代码的入侵性也更强，实现的复杂度也更高。所以，我推荐在需要分布式事务能力时，优先考虑现成的事务型数据库(比如 MySQL XA)，当现有的事务型数据库不能满足业务的需求时，再考虑基于 TCC 实现分布式事务。

相同点

都是两个阶段，一阶段并不真正的执行业务，二阶段根据一阶段的结果进行确认或者取消。

不同点

开发者感知

tcc和2pc的本质区别就是tcc面向的是业务层面，2pc面向的是资源层面

我们在学习2pc的时候，我们总说一阶段是prepare事务，也就是不真正的提交事务。也就是说对资源的更新操作实际上并没有执行，记录在事务日志中准备二阶段的commit或者rollback。但是这些对于开发者来说其实是无感知的，开发者仍旧对资源进行单一的更新操作。

而tcc，它的一阶段进行try预留操作，也就是说开发者需要从业务层面来考虑这个问题，提供try-confirm-cancel这样的一个业务逻辑来为维护事务提交，开发者对此是感知得很明显的。我们也可以理解为对业务的入侵。

强一致性和最终一致性

2pc在一定程度上我们称之为强一致性，所以2pc的执行过程会独占资源，持有资源的互斥锁，这也是2pc效率比较低的原因。

tcc虽然增加了业务代码的复杂性，但是在业务层面上避免长时间占用资源，通过一种confirm或cancel的补偿机制来完成整个业务操作，也就是保持最终一致性。最终一致性并不需要长时间持有资源的锁，每一个事务其实都是相互独立的，所以tcc的效率会更高。

BASE理论

它的核心就是基本可用(Basically Available)和最终一致性(Eventually consistent)。也有人会提到软状态(Soft state)，软状态描述的是实现服务可用性的时候系统数据的一种过渡状态，也就是说不同节点间，数据副本存在短暂的不一致。你只需要知道软状态是一种过渡状态就可以了

基本可用性

基本可用在本质上是一种妥协，也就是在出现节点故障或系统过载的时候，通过牺牲非核心功能的可用性，保障核心功能的稳定运行。通常采用流量削峰、延迟响应、体验降级、过载保护来实现

最终一致性

那么如何实现最终一致性呢?你首先要知道它以什么为准，因为这是实现最终一致性的关键。一般来说，在实际工程实践中有这样几种方式:

以最新写入的数据为准，比如 AP 模型的 KV 存储采用的就是这种方式;
以第一次写入的数据为准，如果你不希望存储的数据被更改，可以以它为准。

那实现最终一致性的具体方式是什么呢?常用的有这样几种。

读时修复:在读取数据时，检测数据的不一致，进行修复。
写时修复:在写入数据，检测数据的不一致时，进行修复。
异步修复:这个是最常用的方式，通过定时对账检测副本数据的一致性，并修复。

因为写时修复不需要做数据一致性对比，性能消耗比较低，对系统运行影响也不大，所以我推荐你在实现最终一致性时优先实现这种方式。

而读时修复和异步修复因为需要做数据的一致性对比，性能消耗比较多，在开发实际系统时，你要尽量优化一致性对比的算法，降低性能消耗，避免对系统运行造成影响。

Paxos 算法

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

一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值(提案 Value)达成共识;
另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。

Basic Paxos

角色

在 Basic Paxos 中，有提议者(Proposer)、接受者(Acceptor)、学习者(Learner) 三种角色

提议者(Proposer)：提议一个值，用于投票表决。集群中收到客户端请求的节点，才是提议者(图 1 这个架构，是为了方便演示算法原理)。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑，就可以像使用数据库一样访问后端的数据。
接受者(Acceptor):对每个提议的值进行投票，并存储接受的值，比如 A、B、C 三个节点。一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
学习者(Learner):被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。

其实，这三种角色，在本质上代表的是三种功能:

提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商;
接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存;
学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

达成共识

在 Basic Paxos 中，兰伯特使用提案代表一个提议。不过在提案中，除了提案编号，还包含了提议值。为了方便演示，我使用[n, v]表示一个提案，其中 n 为提案编号，v 为提议值。

整个共识协商是分 2 个阶段进行的

准备(Prepare)阶段

首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求，在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了，这是很多同学容易产生误解的地方。
当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。5号也是如此

当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。

接受(Accept)阶段

第二个阶段也就是接受阶段，首先客户端 1、2 在收到大多数节点的准备响应之后，会分别发送接受请求

当客户端 1 收到大多数的接受者(节点 A、B)的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空，所以就把自己的提议值 3 作为提案的值，发送接受请求[1, 3]。
当客户端 2 收到大多数的接受者的准备响应后(节点 A、B 和节点 C)，根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空，所以就把自己的提议值 7 作为提案的值，发送接受请求[5, 7]。

当节点 A、B、C 收到接受请求[1, 3]的时候，由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5，所以提案[1, 3]将被拒绝。
当节点 A、B、C 收到接受请求[5, 7]的时候，由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案[5, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。

如果集群中有学习者，当接受者通过了一个提案时，就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么它也通过该提案，接受该提案的值。

那么在这里我还想强调一下，Basic Paxos 的容错能力，源自“大多数”的约定，你可以这么理解:当少于一半的节点出现故障的时候，共识协商仍然在正常工作。

Multi-Paxos

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。

如果我们直接通过多次执行 Basic Paxos 实例，来实现一系列值的共识，就会存在这样几个问题:

如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。你想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应(比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应)而准备失败，需要重新协商。
2 轮 RPC 通讯(准备阶段和接受阶段)往返消息多、耗性能、延迟大。你要知道，分布式系统的运行是建立在 RPC 通讯的基础之上的，因此，延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。

领导者(Leader)

我们可以通过引入领导者节点，也就是说，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。
在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi- Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点(也就是领导者节点)是通过执行 Basic Paxos 算法，进行投票选举产生的。

优化 Basic Paxos 执行

我们可以采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化 Basic Paxos 执行。

也就是说，领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段:

Chubby 的 Multi-Paxos 实现

它通过引入主节点，实现了兰伯特提到的领导者(Leader)节点的特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。
主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期(Lease)。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。
“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。
实现了成员变更(Group membership)，以此保证节点变更的时候集群的平稳运行。

在 Chubby 中，为了实现了强一致性，读操作也只能在主节点上执行。

Raft算法

Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。Raft 算法是现在分布式系统开发首选的共识算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致

角色（成员身份）

成员身份，又叫做服务器节点状态，Raft 算法支持领导者(Leader)、跟随者 (Follower)和候选人(Candidate) 3 种状态。

跟随者: 就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
候选人:候选人将向其他节点发送请求投票(RequestVote)RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
领导者:蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。

需要你注意的是，Raft 算法是强领导者模型，集群中只能有一个“霸道总裁”

选举领导者过程

在初始状态下，集群中所有的节点都是跟随者的状态，每个节点等待领导者节点心跳信息的超时时间间隔是随机的，而节点 A 的等待超时时间最小(150ms)，它会最先因为没有等到领导者的心跳信息，发生超时。
这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。
如果其他节点收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。
如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。
节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权。

节点间如何通讯？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用(RPC)，在领导者选举中，需要用到这样两类的 RPC:

请求投票(RequestVote)RPC，是由候选人在选举期间发起，通知各节点进行投票;
日志复制(AppendEntries)RPC，是由领导者发起，用来复制日志和提供心跳消息。

什么是任期？

Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字(任期编号)标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的，这是在说下面几点。

跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。
如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。
在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为 3 的领导者节点 B，收到来自新领导者的，包含任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随者状态。
还约定如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。比如节点 C 的任期编号为 4，收到包含任期编号为 3 的请求投票 RPC 消息，那么它将拒绝这个消息。

选举有哪些规则？

领导者周期性地向所有跟随者发送心跳消息(即不包含日志项的日志复制 RPC 消息)，通知大家我是领导者，阻止跟随者发起新的选举。
如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
在一个任期内，领导者一直都会是领导者，直到它自身出现问题(比如宕机)，或者因为网络延迟，其他节点发起一轮新的选举。
在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号为 4 的投票请求(来自节点 A)，然后又收到了 1 个包含任期编号为 4 的投票请求(来自节点 B)。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求 RPC 消息时，对于编号为 4 的任期，已没有选票可投了。
当任期编号相同时，日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大，索引号更大)，拒绝投票给日志完整性低的候选人。比如节点 B、C 的任期编号都是 3，节点 B 的最后一条日志项对应的任期编号为 3，而节点 C 为 2，那么当节点 C 请求节点 B 投票给自己时，节点 B 将拒绝投票。

如何理解随机超时时间？

在 Raft 算法中，随机超时时间是有 2 种含义的，这里是很多同学容易理解出错的地方，需要你注意一下:

跟随者等待领导者心跳信息超时的时间间隔，是随机的;
当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的。

Raft 算法和兰伯特的 Multi-Paxos 不同之处

在 Raft 中，不是所有节点都能当选领导者，只有日志最完整的节点，才能当选领导者;
在 Raft 中，日志必须是连续的。

日志

副本数据是以日志的形式存在的，日志是由日志项组成，日志项究竟是什么样子呢?

其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令(Command)，还包含一些附加信息，比如索引值(Log index)、任期编号(Term)。

指令:一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
索引值:日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
任期编号:创建这条日志项的领导者的任期编号。

如何复制日志?

可以把 Raft 的日志复制理解成一个优化后的二阶段提交(将二阶段优化成了一阶段)，减少了一半的往返消息，也就是降低了一半消息延迟。

接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
领导者将执行的结果返回给客户端。
当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。

如何实现日志的一致？

领导者通过日志复制 RPC 消息，发送当前最新日志项到跟随者
如果跟随者它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者。
这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者
如果跟随者在它的日志中，找到了与领导者相同的日志，那么日志复制 RPC 返回成功
领导者强制跟随者更新覆盖该索引值之后的日志项也就是不一致日志项，实现日志的一致。

成员变更问题

假设我们有一个由节点 A、B、C 组成的 Raft 集群，现在我们需要增加数据副本数，增加 2 个副本(也就是增加 2 台服务器)，扩展为由节点 A、B、C、D、E， 5 个节点组成的新集群。

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。比如在进行成员变更时，节点 A、B 和 C 之间发生了分区错误，节点 A、B 组成旧配置中的“大多数”，也就是变更前的 3 节点集群中的“大多数”，那么这时的领导者(节点 A)依旧是领导者。
另一方面，节点 C 和新节点 D、E 组成了新配置的“大多数”，也就是变更后的 5 节点集群中的“大多数”，它们可能会选举出新的领导者(比如节点 C)。那么这时，就出现了同时存在 2 个领导者的情况。

单节点变更

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群。

目前的集群配置为[A, B, C]，我们先向集群中加入节点 D，这意味着新配置为[A, B, C, D]。成员变更，是通过这么两步实现的:

领导者(节点 A)向新节点(节点 D)同步数据;
领导者(节点 A)将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点(节点 A、B、C、D)上，然后将新配置的日志项提交到本地状态机，完成单节点变更。

在变更完成后，现在的集群配置就是[A, B, C, D]，我们再向集群中加入节点 E，也就是说，新配置为[A, B, C, D, E]。成员变更的步骤和上面类似。

这样一来，我们就通过一次变更一个节点的方式，完成了成员变更，保证了集群中始终只有一个领导者，而且集群也在稳定运行，持续提供服务。
我想说的是，在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。 也就是说，不会同时存在旧配置和新配置 2 个“大多数”

一致性hash算法

如果我们通过 Raft 算法实现了 KV 存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致了集群的接入性能约等于单机，那么随着业务发展，集群的性能可能就扛不住了，会造成系统过载和服务不可用，这时该怎么办呢? 答案是一致性hash

如何使用一致哈希实现哈希寻址?

一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算。

使用了一致哈希算法后，扩容或缩容的时候，都只需要重定位环空间中的一小部分数据。也就是说，一致哈希算法具有较好的容错性和可扩展性。

虚拟节点

客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，有什么办法能让数据访问分布的比较均匀呢?答案就是虚拟节点

就是对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。增加了节点后，节点在哈希环上的分布就相对均匀了。

Gossip协议-最终一致性

Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。

Gossip 的三板斧

直接邮寄

直接邮寄就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。
直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。也就是说，只采用直接邮寄是无法实现最终一致性的。

反熵

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

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

虽然反熵很实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境(比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态)，这时反熵就不适用了

谣言传播

广泛地散播谣言，它指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据

Quorum NWR算法 - 自定义一致性级别

最终一致性和强一致性有什么区别？

强一致性能保证写操作完成后，任何后续访问都能读到更新后的值;
最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。也就是说，写操作完成后，后续访问可能会读到旧数据。

Quorum NWR 的三要素

N 表示副本数，又叫做复制因子(Replication Factor)。也就是说，N 表示集群中同一份数据有多少个副本
W，又称写一致性级别(Write Consistency Level)，表示成功完成 W 个副本更新，才完成写操作
R，又称读一致性级别(Read Consistency Level)，表示读取一个数据对象时需要读 R 个副本。你可以这么理解，读取指定数据时，要读 R 副本，然后返回 R 个副本中最新的那份数据:

N、W、R 值的不同组合，会产生不同的一致性效果，具体来说，有这么两种效果:

当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。
当 W + R < N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。

Quorum NWR 是非常实用的一个算法，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度：

一般而言，不推荐副本数超过当前的节点数，因为当副本数据超过节点数时，就会出现同一个节点存在多个副本的情况。当这个节点故障时，上面的多个副本就都受到影响了。
当 W + R > N 时，可以实现强一致性。另外，如何设置 N、W、R 值，取决于我们想优化哪方面的性能。比如，N 决定了副本的冗余备份能力;如果设置 W = N，读性能比较好;如果设置 R = N，写性能比较好;如果设置 W = (N + 1) / 2、R = (N + 1) / 2，容错能力比较好，能容忍少数节点(也就是 (N - 1) / 2)的故障。