黎笛

2022-10-02 18:00 已编辑中北大学 Java 发布于北京

关注

【八股文】分布式理论

1.什么是分布式

2.CAP定理

3.BASE理论

4.什么是分布式事务？产生的原因

5.2PC

6.3PC

7.Paxos协议

8.ZAB协议

9.分布式系统设计策略

10.分布式服务治理

1.什么是分布式

将一个业务拆分成不同的子业务，分布在不同的机器上执行。分布式是为了解决单个物理服务器容量和性能瓶颈问题而采用的优化手段。服务之间通过远程调用协同工作，对外提供服务。

2.CAP原理

一个分布式系统只能满足其中的两个，CA是单点集群

一致性：所有节点在同一时间具有相同的数据
可用性：保证每个请求不管成功或者失败都有响应
分区容错性：系统中某个节点的丢失或网络分区故障不会影响系统的继续运作

3.BASE理论

是在实践过程中基于CAP理论演化而来的，基本可用，软状态，最终一致性

基本可用：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。即保证核心可用
软状态：指系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延迟
最终一致性：所有数据副本经过一定时间后，最终能够达到一致的状态

核心思想：既然无法做到强一致性，但每个应用都可以跟据自身业务特点，采用适当的方式来使系统达到最终一致性，也就是牺牲数据的一致性来满足系统的高可用性，系统中一部分数据不可用或不一致时，仍需要保持系统整体基本可用。

4.什么是分布式事务？产生的原因

分布式事务指事务的操作位于不同的节点上，需要保证事务的ACID的特征。例如下单场景，库存和订单不在同一个节点

5.2PC

2PC和3PC解决的问题就是分布式事务数据一致性的问题，就是保证事务的原子性

在分布式系统中，每个节点都可以知晓自己操作的成功与失败，却无法知道其他节点操作的成功或失败。当一个事务跨多个节点时，为了保持事务的原子性和一致性，而引入了一个协调者来统一掌握所有参与者的操作结果，并指示他们是否把操作结果进行真正的提交或回滚

2PC：两阶段提交协议。准备阶段和提交阶段

阶段1：准备阶段

在准备阶段，协调者向所有参与者发送一个vote request确认参与者准备好开启事务

参与者在收到请求后，各参与者节点准备事务操作。如果准备好返回一个yes，否则返回一个no

阶段2：提交阶段

协调者收到所有参与者的反馈后，如果所有参与者认为可以提交，则提交事务，否则就回滚事务，并将处理结果发送给参与者

如果参与者收到提交消息则提交本地事务，否则就回滚事务

2PC存在的问题：

同步阻塞：整个事务过程中，所有参与者都处于阻塞状态
单点故障：协调者是整个事务的核心，当协调者宕机，参与者会被锁定
数据不一致：二阶段在发送提交事务的过程中，出现了宕机。只有部分参与者收到了commit，导致数据不一致

6.3PC

3PC在2PC的基础上引入了超时机制

被分为3个阶段：CanCommit，PreCommit，doCommit

阶段1：CanCommit（提交询问）

协调者向各个参与者询问是否可以进行事务提交，并收集响应结果

参与者向协调者反馈事务内容。此时收集到的反馈为同意则进入预备阶段，否则回滚事务

阶段2：PreCommit（预提交）

参与者接收到预提交请求后，执行事务操作

各个参与者向协调者反馈事务执行的响应，如果完成事务操作，则反馈给协调者，并等待最终命令

如果协调者收到预提交响应为拒绝或超时，则回滚事务，并通知各个参与者

参与者收到中断事务的响应或者等待超时，都会主动中断事务

阶段3：doCommit（最终提交）

如果各个参与者都响应，则提交事务

如果有一个参与者没有响应，就中断事务，参与者收到拒绝命令，进行事务回滚

7.Paxos协议

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟，丢失，重复，乱序，网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确的在集群内布对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

角色介绍：

Client（客户端）：客户端向分布式系统发出请求，并等待响应
Proposer（提案发起者）：提案者提倡客户端请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议
Acceptor（决策者）：可以接受提案，并进行投票。多数服从少数
Leanner（学习者）：最终结果的复制者。不参与投票，仅为了提供系统功能

8.ZAB协议

是为了zookeeper专门设计的一种支持崩溃恢复和原子广播的协议

基于该协议，Zookeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据一致性

注意：所有客户端写入数据都是写入主进程（Leader），由Leader复制到备份进程（Follower）中，从而保证了数据一致性

我们把上面这张图粗略的分为上下两部分：上半部分就代表客户端请求主进程，我们只需要注意在zk内部，写请求只能由leader接收，读请求各进程都可以接收。

下半部分是zab的核心，崩溃恢复和消息广播

消息广播

对于客户端的写请求，全部由Leader接收，Leader将请求封装成一个事务Proposal，将其转发给所有的Follower，如果有超过半数的Follower成功响应，则执行commit操作（先提交自己，再发送commit给所有Follower）

1）将数据都复制到Follower

2）等待Follower回应ack，超过半数即成功

3）当超过半数响应，主进程则执行commit，同时提交自己

Leader在收到客户端请求后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一ID，称为事务ID（ZXID），ZAB协议需要保证事务的顺序，因此必须将每个事务按照ZXID进行先后排序然后处理

崩溃恢复

首先，我们要知道什么时候可能崩溃：

当zookeeper服务器启动时
当leader服务器出现网络中断，宕机，重启等情况
当集群中已经过半的Follower不能与Leader保持通信

步骤：

1）进入崩溃恢复阶段后，首先会选举出新的leader。当新的leader选举出来后，follower会和leader进行数据同步，当有超过一半的follower与leader同步后，进入消息广播模式，对外提供服务

2）当有新的follower加入集群后，会先进入崩溃恢复模式，先进行数据同步

但除此之外，我们需要解决两个特殊情况：

1）已经被处理的事务请求（Proposal）不能丢

这种情况产生的原因就是：已经有过半的Follower返回ack，在Leader提交的过程中宕机了，导致剩下的服务器没有执行该事务。

解决方案：

选举拥有proposal最大值（zxid最大的）的节点作为新的Leader，因为拥有zxid最大的节点一定保存了所有被commit的事务
新的leader将自己事务日志中proposal但未commit的消息处理
新的 leader 与 follower 建立先进先出的队列，先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal。

2）没被处理的事务请求不能再次出现，需要丢弃那些只在leader提出/复制，但没有提交的事务

Leader已经接收了客户端的请求，已经生成proposal，但未提交时就已经宕机。这时选举别的节点当了Leader。但原来的Leader恢复后，还有这个proposal，导致这个节点与整个系统的消息不一致，需要删除

解决方案：

Zab 通过巧妙的设计 zxid 来实现这一目的。一个 zxid 是64位，高 32 是纪元（epoch）编号，每经过一次 leader 选举产生一个新的 leader，新 leader 会将 epoch 号 +1。低 32 位是消息计数器，每接收到一条消息这个值 +1，新 leader 选举后这个值重置为 0。这样设计的好处是旧的 leader 挂了后重启，它不会被选举为 leader，因为此时它的 zxid 肯定小于当前的新 leader。当旧的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的拥有旧的 epoch 号的未被COMMIT的proposal 清除。