引言

分布式系统面临的问题：

数据一致性：数据均匀分布到多个存储节点，如何保证多个副本的数据一致性问题。
集群可用性：集群的服务是否可用。
分区容错性：当发生故障，集群如何快速恢复从而提供正常服务。

理论

拜占庭将军问题

存在恶意节点行为的场景中（数字货币的区块链技术中）：必须使用拜占庭容错算法（BFT）。常用的有PBFT算法、PoW算法。

计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法（CFT）。CFT解决的是分布式系统中存在故障，但不存在恶意节点的场景下的共识问题。这个场景可能会丢失信息、消息重复问题，但是不存在错误消息，或者伪造消息的情况。常见算法有Paxos算法、Raft算法、ZAB协议。

CAP理论

Q：如何设计分区容错一致性模型？

CAP三指标

一致性（Consistency）
- 强调的是数据在集群中的一致性。
- 客户端每次的读操作，无论访问哪个节点，要么读到同一份数据，要么读取失败。
可用性（Availability）
- 强调的是服务可用，但不保证数据的一致。
- 无论客户端访问哪个节点，都能得到响应数据，但是不保证数据是最新的。
分区容错性（Partition Tolerance）
- 强调的是集群对分区故障的容错能力。
- 节点出现任意数量的消息丢失或高延迟，系统仍然可以继续提供服务。

CAP不可能三角

对于一个分布式系统而言，一致性、可用性、分区容错性三个指标不可兼得，只能进行三选二。

CAP不可能三角

如何使用CAP理论

节点之间的分区故障是必然发生的，因此分区容错性（P）是必须要保证的。那么只剩下两种选择：

CP：选择一致性（C）的时候，如果因为消息丢失、延迟过高发生了网络分区，部分节点无法保持一致，这时集群节点拒绝客户端的写操作。
AP：选择可用性（A）的时候，系统将始终处理客户端的查询，返回特定信息，如果发生了网络分区，一些节点无法返回最新特定信息。

ACID

单机上实现ACID可以通过锁、时间序列等机制保障操作的顺序执行。分布式系统的ACID实现需要掌握分布式事务协议，比如二阶段提交协议、TCC（Try-Confirm-Cancel）。

可以将ACID特性理解为CAP中一致性的边界（最强的一致性），但是大部分场景对一致性的要求不是特别高，如果不是必须，尽量不要实现事务，可以考虑采用强一致性或最终一致性。

二阶段提交协议

用于保证多个节点操作的原子性，也就是：要么多个节点的操作全部执行成功，要么全部失败。

节点分为：

协调者
参与者

执行过程如下：

提交请求阶段（投票阶段）
- 每一个参与者投票表决事务是放弃还是提交，一旦参与者投票要求提交事务，那么不允许中途放弃事务，这个特性需要代码实现时保障的。
提交执行阶段（完成阶段）
- 事务的每个参与者执行最终统一的决定，提交事务或者放弃事务，这个约定是为了实现ACID中的原子性。

存在的问题：

提交请求阶段，需要预留资源，在资源预留时期，其他人不能操作。
数据库是独立的系统。无法动态调整锁的粒度，并发性能下降。

TCC（Try-Confirm-Cancel）

Try（预留）：预留相关资源
Confirm（确认）：确认操作，完成分布式事务。
Cancel（撤销）：如果无法操作，则进行撤销操作。

TCC本质上是补偿事务，核心思想是针对每个操作都要注册一个与之对应的确认操作和撤销操作。它是一个业务层面的协议。在业务中实现分布式事务。对业务代码的侵入性较高。实现的复杂度更高。

BASE理论

BASE理论是CAP理论中的AP的延伸，是互联网大规模分布式系统的实践总结，强调可用性。BASE理论的核心就是：

基本可用（Basically Available）
最终一致性（Eventually Consistent）

基本可用

当分布式系统出现不可预知的故障时，允许损失部分功能的可用性，保证核心功能的可用性。例如：

延迟响应：12306购票系统出现突发流量时，会将购票请求放入队列中进行排队等待处理，通过牺牲响应时间的可用性，保障核心功能的运行。
流量削峰：在不同的时间，出售不同的票，将请求错开，削弱请求峰值。
体验降级：大流量情况，通过降低图片的清晰度和大小，提升系统的处理能力。
过载保护：请求排队时，如果请求等待时间超时，这时直接拒绝超时请求。或者队列满了之后，清除队列中一定数量的排队请求，保证系统不过载，实现系统的基本可用。

最终一致性

系统中所有的数据副本在经过一段时间的同步后，最终能达到一个一致的状态。这存在一个短暂的延迟。几乎所有的互联网系统采用的都是最终一致性，只有实在无法使用最终一致性，才使用强一致性或分布式事务。对于金融系统，需要考虑分布式事务。

如何实现最终一致性？

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

如何实现最终一致性？

读时修复：在读取数据时，检测数据的不一致，进行修复。
写时修复：在写入数据，检测数据的不一致，进行修复。
- 写时修复不需要做数据一致性对比，性能消耗较低，对系统运行影响不大，推荐使用。
异步修复：最常用的方式，通过定时对账检测副本数据的一致性，并修复。

异常问题

分布式系统中存在以下问题：

服务器宕机：内存错误、停电等原因，服务器重启后需要进行数据恢复，因此需要考虑对数据进行持久化。
网络异常：消息丢失、消息乱序（UDP）等原因。
- 网络分区：集群中的节点被划分成多个区域，每个区域内可以通信，区域间不乏通信。
- 设计原则：网络不可靠，任何消息都要收到回复才能认为发送成功。
磁盘故障：磁盘损坏和磁盘数据错误。
- 数据需要冗余存储，防止磁盘损坏。
- 使用校验和机制来解决数据错误问题。
超时：RPC通信时，指定时间未收到信息而判断超时。
- 设计原则：需要将操作设计为幂等的（执行一次和执行多次结果相同），这样发生超时重试不会出现错误。

一致性定义

两个角度思考一致性：

用户：客户端读写操作是否一致。
服务：系统中多个副本之间数据是否一致。

客户端角度

主要有三种一致性：

强一致性：节点A写入了一个值，后续节点读取到都将返回最新值。
弱一致性：无法保证后续读操作能读取到最新值。
最终一致性：能保证在一段时间后，读取到最新值。

服务端角度

副本一致性：多个副本之间的数据保证一致性。
更新顺序一致性：多个副本之间是否按照相同顺序执行更新操作。

数据分区

哈希分区
一致性哈希
顺序分布

算法

Paxos算法

简介

当前最常用的一批共识算法是基于该算法改进的。例如Fast Paxos算法、Cheap Paxos算法、Raft算法、ZAB协议等。

兰伯特提出的Paxos算法包含两个部分：

Basic Paxos：描述的是多节点之间如何就某个Value达成共识。
Multi-Paxos：描述的是执行多个Basic Paxos实例，就一系列值达成共识。

Basic Paxos是Multi-Paxos思想的核心，Multi-Paxos是多执行几次Basic Paxos。

问题

我们要实现一个分布式集群，集群有节点A、B、C构成，提供只读KV存储服务。一个节点创建只读变量后就无法修改它。所有节点必须对只读变量的值达成共识，然后所有节点一起创建这个只读变量。

那么当多个客户端试图创建同一个只读变量，例如client 1执行set x = 3，client 1执行set x = 7，那么分布式集群如何达成共识？

Basic Paxos中的三种角色

提议者（Proposer）：提议一个值，用于投票表决。一般是集群中接收到客户端请求的节点。
接收者（Acceptor）：对每个提议的值进行投票，并存储接受的值。一般来说，集群中所有节点都是扮演接受者的角色，参与共识协商，并接受和存储数据。
学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，容灾备份。

三种角色代表三种功能：

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

如何达成共识？

在Basic Paxos中，用提案代表一个提议，除了提案编号，还包括提议值。使用[n, v]代表一个提案，其中n为提案编号，v为提议值。

准备阶段

client 1、2作为提议者，分别向所有接受者发送包含提案编号的请求。

当节点A、B接收到提案编号为1的准备请求，C收到提案编号为5的准备请求，将这样处理：

由于之前未通过任何提案，节点A、B将返回一个尚无提案的响应，这是告诉提议者，之前没有通过任何提案，并承诺以后不再响应提案编号小于等于1的准备请求，不会通过小于5的提案。
节点C也是入磁，返回一个尚无提案的响应，并承诺不响应提案编号小于等于5的请求，不会通过编号小于5的提案。

当节点A、B接收到提案编号为5的准备请求，节点C收到提案编号为1的准备请求时，将这样处理：

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

接受阶段

client1、2收到节点的响应后，会发送接受请求。

客户端1根据响应中提案编号最大的提案的值，设置接受请求中的值，由于响应是暂无提案，就把自己的提议值设置为提案的值，发送接受请求[1,3]
客户端2收到准备响应后，根据响应中提案最大的值，设置请求中的值，由于A、B、C都是响应暂无提案，则将自己的提议值7作为提案值，发送接受请求[5,7]。

当三个节点接收到客户端的接受请求后，会这样处理：

当节点A、B、C收到接受请求[1,3]的时候，由于提案编号1小于三个节点中能通过的提案的最小提案编号5，所以[1,3]将被拒绝。
当A、B、C收到接受请求[5,7]时，由于提案编号不小于三个节点承诺的能通过的提案的最小编号5，则通过提案[5, 7]。

当提案被通过后，会通知给所有的学习者，当学习者发现大多数接受者都通过某个提案，那么它将接受该提案的值。

Basic Paxos的容错能力，源自于大多数的约定。
Basic Paxos是通过二阶段提交的方式来达成共识的。
Basic Paxos还实现了容错，在少于一半节点出现故障时，集群也能工作。
本质上：提案编号的大小代表着优先级。
Basic Paxos只能就单个值达成共识。

Multi Paxos

由于Multi Paxos并没有提供实现细节，导致每个人实现的不一样，例如Chubby的Multi-Paxos实现、Raft算法、ZAB协议等。

Multi Paxos是一种思想，它指的是基于Multi Paxos思想，通过多个Basic Paxos实例实现一系列值的共识算法。

多次执行Basic Paxos实例，实现共识的问题：

如果多个提议者同时提交提案，可能出现提案冲突，在准备阶段没有提议者接收到大多数准备响应，需要重新协商。
两轮RPC通信往返消息多、延迟大，需要考虑优化。

领导者

可以引入领导者节点，它作为唯一提议者，这样就不存在提案冲突的现象。

在论文中，作者并没有说如何选举领导者，需要我们实现Multi Paxos算法时自己实现。

优化Basic Paxos执行

当leader处于稳定状态，省略掉准备阶段，直接进入接受阶段。leader节点中，序列中的命令都是最新的。

Chubby的Multi Paxos实现

在Chubby中，主节点通过执行Basic Paxos算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期。如果主节点出现故障，其他节点又会投票选举出新的主节点。

Chubby也实现了上述的优化机制。实现了成员变更（Group membership），以此保证节点变更的时候集群的平稳运行。

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

所有的读写请求都在主节点处理，当主节点接收到写请求时，作为提议者，执行Basic Paxos实例，将数据发送给所有的节点，并且大多数节点接受了这个写请求之后，再响应给客户端成功。
当主节点接收到读请求，只需要主节点查询本地数据。

Raft算法

Raft算法属于Multi-Paxos算法，做了简化和限制。Raft算法是现在分布式系统开发首选的共识算法。本质上说：Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

Q：如何保证同一个时间，集群中只有一个领导者？

节点身份

Leader：一切以领导者为准，主要工作为三部分：
1. 处理写请求
2. 管理日志复制
3. 发送心跳信息，告知其他节点自己还活着。
Follower：默默接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，会主动站出来，推荐自己当候选人。
Candidate：候选人向其他节点发送请求投票RPC消息，通知其他节点来投票，如果赢得了投票，就晋升为领导者。

领导者选举

初始状态如下：

Raft算法实现了随机超时时间（每个节点等待leader节点心跳信息的超时时间间隔是随机的）。

当节点超过自己的随机超时时间，节点会增加自己的任期编号，并推举自己为候选人，先给自己投一张选票，然后向其它节点发送请求投票的RPC消息。请他们选举自己为leader。

节点之间如何通信？

通信采用RPC，在领导者选举过程中。通常用到两类RPC：

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

任期

Raft算法中的领导者有任期，每个任期由单调递增的数字标识（任期编号）.

Follower在等待leader心跳信息超时后，推举自己为candidate时，会增加自己的任期号，比如节点A的当前任期编号为0，那么推举自己为candidate时，会将自己的任期编号增加为1.
如果一个节点发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值，比如B的任期编号为0，当收到A的请求投票RPC消息时，因为消息中包含了A的任期编号，并且编号为1，那么B将自己的任期编号更改为1.

Raft算法中的任期不只是时间段，会影响领导者选举和请求的处理。

如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随着状态，比如分区错误恢复后，任期编号为3的领导者节点B，收到来自新领导者的任期编号为4的心跳信息，节点B会立即恢复成跟随者。
如果一个节点接收到包含任期较小的请求，那么它会直接拒绝这个请求。

选举规则

主要有以下几点规则：

领导者周期性发送心跳信息，阻止跟随者发送新的选举。
指定时间内，跟随着没有接收到领导者信息，它会认为当前没有领导者，并推举自己为候选人，发起领导者选举。
在选举中，赢得大多数投票的候选人，晋升为领导者。
在一个任期内，除非领导者心跳消息未接收到，其他节点才能发出新一轮的选举。
一次选举中，一个节点最多会对一个任期编号投出一张选票，按照先来先服务的规则进行投票。
任期编号相同时，日志完整性高的跟随者（最后一条日志项对应的任期编号更大）拒绝投票给日志完整性低的候选者。（换而言之：日志最完整的节点才能当选领导者）

随机超时时间

Raft算法如何处理选举无效的问题？（未达到半数票，需要重新选举）

Raft算法巧妙使用随机选举超时时间的方法，把超时时间分散开来，在大多数情况下只有一个服务器节点先发起选举，这样能减少因为同时选举而导致选票被瓜分导致选举失败的情况。

日志复制

Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程。

日志

日志由日志项构成，日志项是一种数据格式，主要包含用户指令，还包括一些附加信息，例如日志索引、任期编号。

如何复制日志

接收到客户端请求，领导者创建一个日志项，并附加到本地日志中。
领导者通过日志复制RPC消息，将日志项复制到集群其他节点上。
在复制到其他节点上时，领导者会将这条日志项提交到它的状态机中。
领导者将执行的结果返回给客户端。
当跟随者接收到心跳消息，或者新的日志复制RPC消息后，如果跟随着发现领导者已经提交某条日志项，而它还没提交，那么跟随着就将这条日志项提交到本地的状态机中。

如何实现日志的一致

Raft算法中，以领导者的日志为准，来实现各节点日志的一致性。主要有以下两个步骤：

首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值，这个索引值之后的日志是不一致的。
然后领导者强制跟随者更新覆盖不一致的日志项。

上图中PrevLogEntry表示当前要复制的日志项，前一条日志项的索引值，PrevLogTerm表示当前要复制的日志项，前一条日志项的任期编号。

领导者通过日志复制RPC消息，发送当前最新日志项到跟随者，消息的PrevLogEntry为7，PrevLogTerm为4
如果跟随者在它的日志中，找不到PrevLogEntry为7，PrevLogTerm为4的日志项，那么跟随者就会拒收新的日志项，并返回失败消息给领导者。
这时，领导者会递减要复制的日志项的索引值，发送新日志项给跟随者，这个消息的PrevLogEntry为6，PrevLogTerm为3。
如果跟随者在日志中，发现了[6,3]这个日志项，那么返回成功消息，这样领导者知道跟随者在这个位置与自己日志相同。
领导者通过日志复制RPC，复制并更新覆盖索引值之后的日志，最终实现各节点的日志一致。

成员变更

当集群成员变更时，可能会出现多个领导者，Raft算法通过单节点变更来解决。

单节点变更

通过一次变更一个节点实现成员变更，如果需要变更多个节点，那么则需要执行多次单节点变更。

但是如果并发执行单节点变更，坑里出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现两个领导者的情况。

一致性哈希算法

Q：Raft算法实现了分布式存储，但是集群性能约等于单机性能，，如果通过分集群来提升性能，那么会存在数据迁移的过程，一致性哈希主要解决数据迁移成本高的问题。

一致性哈希算法具有较好的容错性和可扩展性。

哈希寻址

当需要对指定key的值进行读写的时候，通过下面两步进行寻址：

首先：将key作为参数执行c - hash()计算哈希值，并确定此key在环上的位置。
然后，从这个位置沿着哈希环顺时针走，遇到第一个节点就是key对应的节点。

如果现在一个节点存在故障，如上图，假设C出现故障，那么key-03的寻址将被重定位到A。

如果在B、C之前扩容一个D节点，那么受影响的仅仅是key-03会被重定位到D。

在哈希寻址中，如果节点过少，可能会导致节点分布不均匀，造成数据访问的冷热不均，如下图：

该问题主要通过虚拟节点来解决。

对每个节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。如下图：

一致性哈希是一种特殊的哈希算法，节点增减变化时只影响到部分数据的路由寻址，因此只需要迁移部分数据。
节点数量较少时，可能出现节点在哈希环上分布不均匀的情况，导致节点的访问冷热不均。
一致性哈希算法本质是一种路由寻址算法，适合简单的路由寻址场景。

Gossip协议

用于实现最终一致性。利用一种随机、带有传染性的方式，将消息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。

三个主要功能：

直接邮寄（Direct Mail）：直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。
- 可能因为缓存队列满了而丢失数据。无法实现最终一致性。
反熵（Anti-entropy）：本质上是通过异步修复实现最终一致性。
- 本意是指集群中的节点，每隔一段时间就随机选择某个其它节点，然后通过交换自己所有数据来消除两者之间的差异，实现数据的最终一致性。
- 推、拉、推拉三种方式。
- 反熵需要节点两两交换数据，成本较高。可以通过引入校验和等机制，降低需要对比的数据量和通讯消息。
- 但是如果在节点数量动态变化的分布式环境下，反熵不适用。
谣言传播（Rumor mongering）：一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其它节点向其发送新数据，直到所有的节点都存储了该数据。