20张图！常见分布式理论与解决方案

对于分布式系统，最简单的理解就是一堆机器对外提供服务，相比单体服务，它可以承受更高的负载，但是分布式系统也带了一系列问题，比如如何解决某个节点故障的问题？如何解决数据一致性的问题？如何解决数据倾斜的问题？今天通过这篇文章，带大家搞懂和分布式相关的常见理论和解决方案。

CAP理论

先从定义开始：

• C（Consistence）：一致性，所有的节点访问的是最新的数据副本，这是什么意思呢？我们知道在分布式系统中，为了高可用，往往一个节点会有若干个数据副本，简称Follower节点，比较常见的模式是我们的数据更新一般会写入Leader节点，然后会同步给Follower节点，当我们读取数据的时候，不论从哪个节点读取都可以读到最新的数据，这就是一致性。

A、B、C可以得到同样的数据。

• A（Availability）：可用性，非故障节点可以正常的操作，简单来说就是客户端一直可以正常访问并得到系统的正常响应，从用户角度来看就是不会出现系统操作失败或者访问超时等问题，但是系统内部可能会出现网络延迟等问题。

C节点因为自身问题不可用，正常情况会被剔除，B节点与A节点之间可能存在同步延迟，但是B节点本身没有故障，所以B节点是可用的。

• P（Partition tolerance）：分区容错性，网络的问题错综复杂，分布式系统肯定是要考虑这一点的，如果出现某个节点因为网络等问题造成数据不一致，或者数据延迟很久才同步过来，虽然会影响部分节点数据的时效性，但是服务节点依然是可用的，分布式系统要能容忍这种情况的。

B对应的节点虽然和Leader断了联系，但是依然可以对外服务，只不过提供的是老数据。

在分布式系统中，CAP是无法同时满足的，首先由于存在多节点，并且网络传输需要时间，所以可能会存在延迟，那么节点之间的数据我们无法保证某一时刻完全一致，因此P（分区容错性）是要满足的。在P满足的情况下，为什么说CA不能同时满足呢？我们来通过假设看一看，如果CA同时满足会怎么样。

1. 假设现在要求满足C（一致性），那么就是说所有的节点在某一刻提供的数据都必须一致，我们知道在P的情况，是不可能保证的，要保证的话，就只能把其他节点全部干掉，比如禁止读写，那这其实就是和A是相悖的（某些节点虽然延迟，但是节点本身可用）。
2. 假设现在要求满足A（可用性），那么就是说只要节点本身没什么问题，就可以对外提供服务，哪怕有点数据延迟，很明显这肯定是和C相悖的。

在实际的业务中，我们需要根据业务的场景来决定使用CP，还是AP。比如对一些和钱挂钩的业务，数据的一致性按道理应该是最重要的，因此一般会采用CP，而对于一些不影响主体功能的业务，比如像新闻的阅读量，不同的用户看到的阅读量不一样并不会造成什么影响，可以采用AP。

BASE理论

由于CAP理论中C和A无法兼得，eBay的架构师提出了BASE理论，BASE理论主要是在CA之间做文章，它不要求强一致性，因此可以满足一定的可用性。我们还是先从定义开始：

• BA（Basically Available）：基本可用，注意这个和不可用不是一回事，在分布式系统中出现不可预估的故障时，允许损失部分可用性，保证核心功能可用，比如正常一个接口响应200ms，在出现故障时响应超过1s，虽然响应时间变长了，但是接口还是可以对外提供服务的，再比如对于一个视频网站，在突发流量到来时，把视频的弹幕服务打挂了，但是视频的播放功能依然正常。

• S（Soft-state）：软状态，即分布式系统允许存在一个中间的状态，但是这个中间状态并不会对服务造成严重的影响，比如对于主从复制这种，允许从节点短暂的延迟。

• E（Eventually Consistent）：最终一致性，由于软状态的存在，系统对延迟是可以容忍的，但是在一段时间后，延迟的数据需要最终保持一致。

总的来说，BASE理论适用性应该更广泛，很多时候我们并不要求数据的强一致性，只要在短暂的延时之后能达到一致性也是可以的。

一致性hash

hash这个词对我们来说并不陌生，以缓存服务器来说，一般会在线上配置好几台服务器，然后根据hash来决定请求哪台缓存服务，比如常见的就是取模方式 hash(key)%num 来获取目标机器。

假设现在有3台缓存服务器，并且当前有3个缓存的key，分别是k0，k1，k2，在经过hash以后，它们的分布情况如下：

hash(k0)%3=0 #No.0
hash(k1)%3=1 #No.1
hash(k2)%3=2 #No.2

很幸运，分布的非常均匀，每台机器一个。某天，由于线上要做个活动，预计访问量会加大，需要选择加一台服务器来分担压力，于是经过hash之后，k0，k1，k2的分布情况如下：

hash(k0)%4=0 #No.1
hash(k1)%4=1 #No.2
hash(k2)%4=2 #No.3

• k0的目标缓存服务器由原本的No.0变成了No.1
• k1的目标缓存服务器由原本的No.1变成了No.2
• k2的目标缓存服务器由原本的No.2变成了No.3

可以发现因为添加了一台缓存节点，导致了k0，k1，k2原来的缓存全部失效了，这似乎有点问题，类似缓存雪崩，严重的话会对DB造成很大的压力，造成这个问题的主要原因是因为我们加了一个节点，导致hash结果发生了变动，此时的hash可以说是不稳定的。

为了解决rehash不稳定的问题，于是出现了一致性hash算法。一致性hash的原理比较简单，首先存在一个hash圆环，这个圆环可以存放 0-2^32-1 个节点。

1. 第一步就是把我们的目标服务器节点通过hash映射到这个环上
2. 第二步根据我们需要查找的key，它应该也对应hash环上的某个位置

也许你会问，这k0、k1、k2也没和某个缓存节点对上呀～，这就是一致性hash不同的地方，它此时查找的方式并不是 hash(key)=某个节点，而是根据key的位置，顺时针找到第一个节点，这个节点就是当下这个key的目标节点。

我们再来看看在一致性hash的情况下，新增一个节点会发生什么。

此时唯一的变动就是k0原本应该打到cache0节点的，现在却打到了我们新加的节点cache3上，而k1，k2是不变的，也就是说有且只有k0的缓存失效了，相比之前，大大降低了缓存失效的面积。

当然这样的节点分布算是比较理想的了，如果我们的节点是这样分布的：几个cache节点分布的比较集中，由于顺时针查找法，所以最终k0，k1，k2都落在cache0节点上，也就是说cache1、cache2基本就是多余的，所以为了解决这种数据倾斜的问题，一致性hash又引入了虚拟节点的概念，每个节点可以有若干个虚拟节点，比如：

1. cache0->cache0#1
2. cache1->cache1#1
3. cache2->cache2#1

虚拟节点并不是真正的服务节点，它只是一个影子，它的目的就是站坑位，让节点更加分散，更加均匀。

这样通过映射出虚拟节点以后，k0打到cache2，k1打到cache0，k2打到cache1，虚拟节点越多，理论分布的越均匀。

Gossip协议

集群往往是由多个节点共同组成的，当一个节点加入集群或者一个节点从集群中下线的时候，都需要让集群中其他的节点知道，这样才能将数据信息分享给新节点而忽略下线节点。

A、B、C节点之间可以互相传递消息，但是D节点在下线之后会被广播告诉其他存活节点。

这样的广播协议就是今天要说Gossip协议，Gossip协议也叫Epidemic协议（流行病协议），当一个消息到来时，通过Gossip协议就可以像病毒一样感染全部集群节点，当然我们利用的是它这个极强的散播能力。

Gossip的过程是由一个种子节点发起的，当一个种子节点有信息需要同步到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，所以不能保证某个时间点所有的节点都有该条消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip协议的特点：

1. Gossip协议是周期性散播消息，每隔一段时间传播一次
2. 被感染的节点，每次可以继续散播N个节点
3. 每次散播消息时，都会选择尚未发送过的节点进行散播
4. 收到消息的节点，不会向发送的节点散播
5. 同一个节点可能会收到重复的消息，因为可能同时多个节点正好向它散播
6. 集群是去中心化的，节点之间都是平等的
7. 消息的散播不用等接收节点的ack，即消息可能会丢失，但是最终应该会被感染

我们来看个例子：

1. 种子节点是A
2. A节点选择B、C节点进行散播
3. C散播到D，B散播D和E，可以发现D收到两次
4. D散播到F，最终整个网络都同步到了消息

Gossip有点类似图的广度优先遍历算法，一般用于网络拓扑结构信息的分享和维护，像redis、consul都有使用到。

Raft算法

分布式协议的难点之一就是数据的一致性，当由多个节点组成的集群中只有一个节点收到数据，我们就算成功的话，风险太大，当要求所有节点都收到数据才响应成功，性能又太差，所以一般会在数据的安全和性能之间做个折中，只要保证绝大部分节点同步数据成功，我们就算成功，Raft算法作为比较知名的一致性算法，被广泛应用于许多中间件中，比如像etcd，接下来我们就看看Raft算法是如何工作的。

首先介绍下在Raft算法中，几种情况下每个节点对应的角色：

1. Leader节点：同大多数分布式中的Leader节点一样，数据的变更都是通过它的
2. Follower节点：Leader节点的追随者，负责复制数据并且在选举时候投票的节点
3. Candidate候选节点：参与选举的节点，就是Follower节点参与选举时会切换的角色

Raft算法将一致性问题分解为两个的子问题，Leader选举和状态复制。

选举

首先我们来看看Leader的选举，系统在刚开始的时候，所有节点都为Follower节点，这时大家都有机会参与选举，也就是把自己变成Candidate，但是如果每个Follower节点都变成Candidate那么就会陷入无限的死循环，于是每个Follower都一个定时器，并且定时器的时间是随机的，当某个Follower的定时器时间走完之后，会确认当前是否存在Leader节点，如果不存在就会把自己变成Candidate，这时会投自己1票，同时告诉其它节点，让它们来投票，当拿到超过半数以上的投票时，当前的Candidate就会变成Leader节点。

1. 由于A节点的定时器时间最短（10ms），所以A会成为Candidate
2. A投自己一票，同时B、C也投出自己的同意票，因此A会变成Leader节点，同时会记录是第M任。这个M是做版本校验的，比如一个编号是10的节点，收到了一个编号是9的节点的投票请求，那么就会拒绝这个请求。

在Leader节点选举出来以后，Leader节点会不断的发送心跳给其它Follower节点证明自己是活着的，其他Follower节点在收到心跳后会清空自己的定时器，并回复给Leader，因为此时没必要触发选举了。

如果Leader节点在某一刻挂了，那么Follower节点就不会收到心跳，因此在定时器到来时就会触发新一轮的选举，流程还是一样，但是如果恰巧两个Follower都变成了Candidate，并且都得到了同样的票数，那么此时就会陷入僵局，为了打破僵局，这时每个Candidate都会随机推迟一段时间再次请求投票，当然一般情况下，就是先来先得，优先跑完定时器的Candidate理论成为Leader的概率更大。

好的选举流程大致如上，接下来我们来看看数据的复制。

复制

当Leader节点收到Client的请求变更时，会把变更记录到log中，然后Leader会将这个变更随着下一次的心跳通知给Follower节点，收到消息的Follower节点把变更同样写入日志中，然后回复Leader节点，当Leader收到大多数的回复后，就把变更写入自己的存储空间，同时回复client，并告诉Follower应用此log。至此，集群就变更达成了共识。

最后，Raft算法是能够实现分布式系统强一致性的算法，每个系统节点有三种状态Leader、Follower、Candidate，实现Raft算法两个最重要的事是：主的选举和日志的复制。

分布式事务

事务相信大家不陌生，事务的本质是要么一起向前冲，要么一起保持不动。对于MySQL的InnoDB来说，我们只需要执行begin、commit就行，有时候我们可能需要回滚rollback。但是这是在同一数据库的前提下，如果我们的数据表分库了或者说我们要操作的资源在不同的网络节点上该怎么办？这就得用到我们今天要说的分布式事务了，分布式事务有2PC、3PC、TCC等， 但是无论哪种都无法保证完美的ACID，我们来一起看看是怎么回事吧。

2PC

从名字可以看出它是分两个阶段的，所以它也叫做二阶段提交，即准备和提交，2PC要求有个事务的协调者，相比常规的事务，我们的请求是发给这个协调者的，然后由协调者帮我们协调各个节点资源的提交。

• 准备阶段：协调者会让各个参与事务的参与者，把除了提交之外所有的事情都干好，也就是就等着提交了
• 提交阶段：协调者收到各个参与者的准备消息后，根据准备情况通知各个参与者提交（commit）或者回滚（rollback）

可以发现整个过程非常依赖协调者，如果协调者挂了，那么整个分布式事务就不可用，所以一般建议协调者至少有个备份节点。

如果协调者在收到所有节点的ok之后，在准备发送commit消息的时候，由于网络问题，导致其中一个节点始终收不到消息，那么收不到消息的节点就会一直占着资源不释放，出现这种情况的时候，建议协调者有个重试功能，在commit失败之后，不停的重试，直至成功。2PC协议是一种强一致性协议，它是同步阻塞的，所以在高并发的场景它的性能可能还会有问题。

3PC

2PC存在一些问题，比如协调者从挂了到恢复后并不知道当前节点的状态，现在应该做什么（是该提交还是回滚等等），还有就是当发生网络问题的时候，无法通信的节点只会傻傻的等待，造成资源一直处于锁定状态。鉴于这些问题，出现了3PC。

首先3PC顾名思义，会分为3个阶段，分别是准备阶段、预提交阶段和提交阶段。

• 准备阶段：主要是询问参与者自身的状况，比如你的负载情况如何？能参与接下来的任务吧？
• 预提交阶段：除了commit之外的所有准备工作，就等着commit了
• 提交阶段：执行真正的commit或者rollback

如果在事务期间，有新的协调者顶替进来，它就可以根据一个参与者的状态来判断当前应该干嘛，比如如果一个参与者处于提交阶段，那么表明当前的事务正处于提交阶段。当因为网络问题某个节点一直收不到提交信息，那么此时也不会傻等了，会有超时时间，当超时时间过去了，节点可以自动提交，但是这里有个问题，对于参与者节点来说，当前应该是commit还是rollback呢？

其实2PC和3PC都无法保证绝对的一致性，因为某个参与者节点可能就是因为网络问题收不到消息，但是其他参与者节点已经提交了事务，一般为了预防这种问题，最好加一个报警，比如监控到事务异常的时候，通过脚本自动补偿差异的信息。

TCC

TCC事务的全程是Try、Commit、Cancel，TCC事务使用场景更贴近实际应用，因此它的使用也更广泛。

• Try：Try这个过程，一般表示锁定资源的过程，比如常见的下单，在try阶段，我们不是真正的减库存，而是把下单的库存给锁定住。
• Commit：真正的执行业务逻辑了，带提交的。
• Cancel：撤销，如果Commit失败可以把锁定的资源释放回来

TCC对应用的侵入性强。业务逻辑的每个分支都需要实现try、confirm、cancel三个操作，代码改造成本高。在出现网络或者其他系统故障时，TCC要根据实际业务场景实现对应的回滚逻辑。Commit或者Cancel有可能会重试，因此对应的部分最好支持幂等。

最后其实上面3种分布式事务理论上都无法保证绝对的一致性，因为无法解决网络等带来的意外因素，要解决它，要么只能无限重试，但是这个无限重试最好通过消息队列+守护进程的方式来自动补数据，前提还是得保证消息队列不丢失数据。总之不仅仅是分布式事务会带来这些问题，分布式本身也会带来许许多多的问题，没有绝对的解决方案，只有更好的解决方案。