分布式面试点

目录

1.分布式理论

为什么CAP不可兼得呢?

2.CAP对应的模型和应用

3.Base理论

4,有哪些分布式锁的案例

5.分布式事务

6.Seata

分布式一致性算法

1. 准备阶段（Prepare Phase）

2. 接受阶段（Accept Phase）

3. 学习阶段（Learn Phase）

Paxos 算法执行流程

1. 准备阶段（Prepare Phase）

2. 接受阶段（Accept Phase）

3. 学习阶段（Learn Phase）

分布式限流算法

1.分布式理论

CAP的原则

CAP就是在一个分布式系统中,一致性,可用性,分区容错性这三个最多满足其中两个.

为什么CAP不可兼得呢?

首先对于分布式系统,分区是必然存在的.那么P就一定要满足.

那么满足了P,AC可以都满足吗?

假如现在有两个分区N1和N2，N1 和 N2 分别有不同的分区存储 D1 和 D2，以及不同的服务 S1 和 S2。

• 在满足一致性 的时候，N1 和 N2 的数据要求值一样的，D1=D2。
• 在满足可用性的时候，无论访问 N1 还是 N2，都能获取及时的响应。

假如现在有这样的场景：

• 用户访问了 N1，修改了 D1 的数据。
• 用户再次访问，请求落在了 N2。此时 D1 和 D2 的数据不一致。

接下来：

• 保证一致性：此时 D1 和 D2 数据不一致，要保证一致性就不能返回不一致的数据，可用性无法保证。
• 保证可用性：立即响应，可用性得到了保证，但是此时响应的数据和 D1 不一致，一致性无法保证。

所以，可以看出，分区容错的前提下，一致性和可用性是矛盾的。

2.CAP对应的模型和应用

AC

理论上放弃 P（分区容错性），则 C（强一致性）和 A（可用性）是可以保证的。实际上分区是不可避免的，严格上 CA 指的是允许分区后各子系统依然保持 CA。

例如: 集群数据库,xFS文件系统

AP

Web缓存,DNS

CP

分布式锁,分布式数据库

3.Base理论

BA 基本可以

S 软状态

什么是硬状态呢？要求多个节点的数据副本都是一致的，这是一种“硬状态”。

软状态也称为弱状态，相比较硬状态而言，允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

E最终一致性

4,有哪些分布式锁的案例

1.MySQL分布式锁

用数据库实现分布式锁比较简单，就是创建一张锁表，数据库对字段作唯一性约束。

加锁的时候，在锁表中增加一条记录即可；释放锁的时候删除记录就行。

如果有并发请求同时提交到数据库，数据库会保证只有一个请求能够得到锁。

2.redis分布式锁

Redis 执行命令是单线程的，Redis 实现分布式锁就是利用这个特性。

实现分布式锁最简单的一个命令：setNx

3.Zookeeper分布式锁

ZooKeeper 的数据节点和文件目录类似，例如有一个 lock 节点，在此节点下建立子节点是可以保证先后顺序的，即便是两个进程同时申请新建节点，也会按照先后顺序建立两个节点。

5.分布式事务

分布式事务其实就是将单一库的事务概念扩大到了多库，目的是为了保证跨服的数据一致性。

分布式事务有哪些常见的实现方案？

• 二阶段提交（2PC）：通过准备和提交阶段保证一致性，但性能较差。
• 三阶段提交（3PC）：在 2PC 的基础上增加了一个超时机制，降低了阻塞，但依旧存在数据不一致的风险。
• TCC：根据业务逻辑拆分为 Try、Confirm 和 Cancel 三个阶段，适合锁定资源的业务场景。
• 本地消息表：在数据库中存储事务事件，通过定时任务处理消息。
• 基于 MQ 的分布式事务：通过消息队列来实现异步确保，利用重试机制保障最终一致性，适用于对实时性要求不高的场景

2PC

XA 协议

• AP（Application）：应用系统（服务）
• TM（Transaction Manager）：事务管理器（全局事务管理）
• RM（Resource Manager）：资源管理器（数据库）

准备阶段：事务管理器要求每个涉及到事务的数据库预提交(precommit)此操作，并反映是否可以提交 提交阶段：事务协调器要求每个数据库提交数据，或者回滚数据。

优点：尽量保证了数据的强一致，实现成本较低，在各大主流数据库都有自己实现，对于 MySQL 是从 5.5 开始支持。

缺点: 单点问题 事务管理器在其中很重要 比如完成了准备阶段,然后再提交阶段宕机了,那么就会堵塞

• 同步阻塞：在准备就绪之后，资源管理器中的资源一直处于阻塞，直到提交完成，释放资源。
• 两阶段提交协议虽然为分布式数据强一致性所设计，但仍然存在数据不一致性的可能，比如在第二阶段中，假设协调者发出了事务 commit 的通知，但是因为网络问题该通知仅被一部分参与者所收到并执行了 commit 操作，其余的参与者则因为没有收到通知一直处于阻塞状态，这时候就产生了数据的不一致性。

3PC

三阶段提交（3PC）是二阶段提交（2PC）的一种改进版本 ，为解决两阶段提交协议的单点故障和同步阻塞问题。

3个阶段

• CanCommit：准备阶段。协调者向参与者发送 commit 请求，参与者如果可以提交就返回 Yes 响应，否则返回 No 响应。

• PreCommit：预提交阶段。协调者根据参与者在准备阶段的响应判断是否执行事务还是中断事务，参与者执行完操作之后返回 ACK 响应，同时开始等待最终指令。

• DoCommit：提交阶段。协调者根据参与者在准备阶段的响应判断是否执行事务还是中断事务：

• 如果所有参与者都返回正确的ACK响应，则提交事务

• 如果参与者有一个或多个参与者收到错误的ACK响应或者超时，则中断事务

• 如果参与者无法及时接收到来自协调者的提交或者中断事务请求时，在等待超时之后，会继续进行事务提交

无论是 2PC 还是 3PC 都不能保证分布式系统中的数据 100%一致

TCC（Try Confirm Cancel） ，是两阶段提交的一个变种，针对每个操作，都需要有一个其对应的确认和取消操作，当操作成功时调用确认操作，当操作失败时调用取消操作

• Try：尝试待执行的业务。订单系统将当前订单状态设置为支付中，库存系统校验当前剩余库存数量是否大于 1，然后将可用库存数量设置为库存剩余数量-1，。
• Confirm：确认执行业务，如果 Try 阶段执行成功，接着执行 Confirm 阶段，将订单状态修改为支付成功，库存剩余数量修改为可用库存数量。
• Cancel：取消待执行的业务，如果 Try 阶段执行失败，执行 Cancel 阶段，将订单状态修改为支付失败，可用库存数量修改为库存剩余数量。

TCC 是业务层面的分布式事务，保证最终一致性，不会一直持有资源的锁。

• 优点： 把数据库层的二阶段提交交给应用层来实现，规避了数据库的 2PC 性能低下问题
• 缺点：TCC 的 Try、Confirm 和 Cancel 操作功能需业务提供，开发成本高。TCC 对业务的侵入较大和业务紧耦合，需要根据特定的场景和业务逻辑来设计相应的操作

本地消息表

核心思想是将分布式事务拆分成本地事务进行处理。

MQ消息事务

基于 MQ 的分布式事务是指将两个事务通过消息队列进行异步解耦，利用重试机制保障最终一致性，适用于对实时性要求不高的场景。

订单服务执行自己的本地事务，并发送消息到 MQ，库存服务接收到消息后，执行自己的本地事务，如果消费失败，可以利用重试机制确保最终一致性。

6.Seata

Seata（Simple Extensible Autonomous Transaction Architecture） 是阿里巴巴开源的分布式事务解决方案

Seata 的设计目标是对业务无侵入，因此它是从业务无侵入的两阶段提交（全局事务）着手，在传统的两阶段上进行改进，他把一个分布式事务理解成一个包含了若干分支事务的全局事务。而全局事务的职责是协调它管理的分支事务达成一致性，要么一起成功提交，要么一起失败回滚.

Seata 中存在这么几种重要角色：

• TC（Transaction Coordinator）：事务协调者。管理全局的分支事务的状态，用于全局性事务的提交和回滚。
• TM（Transaction Manager）：事务管理者。用于开启、提交或回滚事务。
• RM（Resource Manager）：资源管理器。用于分支事务上的资源管理，向 TC 注册分支事务，上报分支事务的状态，接收 TC 的命令来提交或者回滚分支事务。

分布式一致性算法

paxos

在 Paxos 中有这么几个角色：

Proposer（提议者） : 提议者提出提案，用于投票表决。

Accecptor（接受者） : 对提案进行投票，并接受达成共识的提案。

Learner（学习者） : 被告知投票的结果，接受达成共识的提案。

1. 准备阶段（Prepare Phase）

1. Proposer 选择一个唯一的提案编号 n，向 多数派（Quorum） 的 Acceptor 发送 Prepare(n) 请求。
2. Acceptor 收到 Prepare(n) 后：
   • 若 n 大于它已响应的所有提案编号，则记录 n 为 “已接受的最大编号”，并返回 上次接受的提案（若有）。
   • 否则，拒绝该请求（不回复或返回拒绝）。

2. 接受阶段（Accept Phase）

1. Proposer 收到多数派的响应后：
   • 若响应中包含 上次接受的提案，则选择编号最大的提案的值作为本次提案的值；
   • 若响应中无提案，则 Proposer 自行决定提案的值。
   • 然后向多数派的 Acceptor 发送 Accept(n, value) 请求。
2. Acceptor 收到 Accept(n, value) 后：
   • 若 n 大于等于它已响应的最大提案编号，则接受该提案，记录 (n, value)，并返回接受确认。
   • 否则，拒绝该请求。

3. 学习阶段（Learn Phase）

当多数派 Acceptor 接受了同一提案 (n, value)，则该值被认为达成一致。Acceptor 将结果通知 Learner，Learner 记录该值。

假设一个分布式系统有 5 个节点（A、B、C、D、E），需要对配置项 max_connections=100 达成一致。节点 A 作为提议者（Proposer）发起更新请求，其他节点作为接受者（Acceptor）参与投票。

Paxos 算法执行流程

1. 准备阶段（Prepare Phase）

• A 作为 Proposer 选择一个提案编号 n=5（唯一且递增），向多数派节点（至少 3 个）发送 Prepare(5) 请求。
• 接受者响应：
  • B 之前未响应过任何提案，记录 n=5 为最大编号，返回空响应（表示无历史提案）。
  • C 之前接受过提案 (3, max_connections=80)，记录 n=5 为最大编号，并返回 (3, 80)。
  • D 之前未响应过任何提案，记录 n=5 为最大编号，返回空响应。
  • E 未收到请求（网络延迟），未响应。

2. 接受阶段（Accept Phase）

• A 收到多数派（B、C、D）的响应后：
  • 发现响应中最大的历史提案是 (3, 80)，根据规则，必须选择该值作为新提案的值（即使 A 原本想提议 100）。
  • 于是 A 向多数派（B、C、D）发送 Accept(5, 80) 请求。
• 接受者处理请求：
  • B 检查 n=5 是其记录的最大编号，接受提案 (5, 80)，并返回确认。
  • C 检查 n=5 大于其之前响应的 n=3，接受提案 (5, 80)，并返回确认。
  • D 同理，接受提案 (5, 80)，并返回确认。

3. 学习阶段（Learn Phase）

• A 收到多数派（B、C、D）的接受确认后，认为值 80 已达成一致。
• A 作为 Learner 将结果通知其他节点（包括未参与投票的 E）。
• 最终，所有节点（A、B、C、D、E）的配置都更新为 max_connections=80。

分布式限流算法

计数器

计数器比较简单粗暴，比如我们要限制 1s 能够通过的请求数，实现的思路就是从第一个请求进来开始计时，在接下来的 1s 内，每个请求进来请求数就+1，超过最大请求数的请求会被拒绝，等到 1s 结束后计数清零，重新开始计数。

这种方式有个很大的弊端：比如前 10ms 已经通过了最大的请求数，那么后面的 990ms 的请求只能拒绝，这种现象叫做“突刺现象”。

桶漏算法

就是桶底出水的速度恒定，进水的速度可能快慢不一，但是当进水量大于出水量的时候，水会被装在桶里，不会直接被丢弃；但是桶也是有容量限制的，当桶装满水后溢出的部分还是会被丢弃的。

算法实现：可以准备一个队列来保存暂时处理不了的请求，然后通过一个线程池定期从队列中获取请求来执行。

令牌桶算法

令牌桶就是生产访问令牌的一个地方，生产的速度恒定，用户访问的时候当桶中有令牌时就可以访问，否则将触发限流。