分布式

理论

【知识来源：https://javaguide.cn/distributed-system/protocol/cap-and-base-theorem.html】

【很有意思的介绍：https://ravindraelicherla.medium.com/cap-theorem-simplified-28499a67eab4】

1. CAP 理论

概述：CAP理论用来描述分布式系统在一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance）之间的权衡。

  • 一致性（C）：所有节点在同一时间看到相同的数据。

  • 可用性（A）：系统在任意时间都能响应读写请求，即使部分节点故障。

  • 分区容错性（P）：系统能在网络分区的情况下继续运行，哪怕消息可能延迟或丢失。

三者不可兼得：CAP理论并非简单的“三选二”，而是在网络分区（P）不可避免时，只能在一致性（C）和可用性（A）之间做出权衡。也就是选择CP或者AP，而不是CA。网络分区：网络分区指的是网络中部分节点之间无法通信的情况。分布式系统必须容忍这种情况，否则系统无法保持可靠性。

CAP 实际应用案例

  • CP 系统：如ZooKeeper，优先保证一致性和分区容错性。

  • AP 系统：如Cassandra，优先保证可用性和分区容错性。

2. BASE 理论

  • 背景：BASE理论是对CAP的扩展，强调系统在保障基本可用（Basically Available）的同时，接受软状态（Soft State），并最终达到一致性（Eventual Consistency）。

  • 三要素：

    • 基本可用（Basically Available）：允许在部分故障或异常情况下系统仍可提供服务，可能是功能降级或响应时间增加。

    • 软状态（Soft State）：系统状态可以是中间状态（数据不一致），不要求瞬时一致性。

    • 最终一致性（Eventual Consistency）：即使系统在短时间内存在不一致，最终将达到一致状态。

总结：CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。\

分布式共识算法

【基础知识：https://javaguide.cn/distributed-system/protocol/paxos-algorithm.html】共识是可容错系统中的一个基本问题：即使面对故障，服务器也可以在共享状态上达成一致。一般通过使用复制日志来实现复制状态机，因此共识算法的工作就是保持复制日志的一致性

3. Paxos算法

可以把Paxos算法比作一个会议中达成共识的过程：

  • 提议者：负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。

  • 接受者：会议中的参与者，负责对提议者的提案进行投票，同时需要记住自己的投票历史；

  • 学习者：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

在会议中，提议者首先提出一个方案，然后参与者们讨论并表示是否支持。如果大部分参与者承诺支持这个方案，那么这个方案就被接受了，大家都按这个方案进行操作。Paxos算法设计的目的是确保即使部分节点发生故障，系统仍然能达成一致，保证了系统的一致性和可靠性。 \

4. Raft算法

节点类型：Leader：负责发起心跳，响应客户端，创建日志，同步日志。Candidate：Leader 选举过程中的临时角色，由 Follower 转化而来，发起投票参与竞选。Follower：接受 Leader 的心跳和日志同步数据，投票给 Candidate。 流程：【时间分为任期，每个任期内只有一个Leader】

  1. Raft算法将时间分为任期，每个任期开始时进行选举。候选者（Candidate）争取成为领导者（Leader）；

  2. 若成功，则在该任期内担任Leader；若无Leader，则进入下一个任期重新选举。

  3. 每个节点存储并更新term号，确保一致性。若节点发现自己的term号过期，则退回为跟随者（Follower），并拒绝过期请求。

  4. Raft算法确保每个任期至少会有一个Leader，以维护系统的一致性。

领导人选举：【心跳机制和随机选举超时】

  1. Raft算法使用心跳机制维持领导者状态。领导者定期向跟随者发送心跳，保持其领导地位。

  2. 若跟随者在超时时间内未收到心跳，它会自增任期号并转换为候选者，发起选举。

  3. 候选者需在一个任期内获得多数（N/2+1）的选票才能成为新领导者。如果候选者收到较大term号的心跳，它将回退为跟随者；若term号较小，则拒绝请求并更新term。

  4. 为避免多个候选者同时超时，Raft随机化选举超时时间，确保选举能有效完成。

\

分布式ID

【基础知识：https://javaguide.cn/distributed-system/distributed-id.html】

【Leaf：】

1. 分布式 ID 概念

  • 什么是 ID：唯一标识数据的符号，如用户ID、商品ID。

  • 分布式 ID：分布式系统中确保唯一的ID，用于解决多数据库或服务器下的ID冲突问题。

  • 基本要求：全局唯一性、高性能、高可用、方便易用。

  • 额外要求：有序递增、安全性（敏感信息）、业务含义、独立部署。\

2. 常见实现方案

  • 数据库主键自增：简单易用，但存在单点问题，性能和安全性较差。

  • 数据库号段模式：批量生成ID存在内存里取，减少数据库压力，但仍有单点问题。

  • NoSQL：如Redis的incr命令 + Redis Cluster，适合高并发环境。

  • 算法：

    • UUID：全局唯一ID，标准为128位（16字节）

      • 优点：生成速度快、简单易用

      • 缺点：存储空间大、无序（索引不利）、可读性差、不安全（泄露MAC地址）、涉及到时间戳所以需要解决重复ID问题

    • Snowflake：Twitter开源的高效ID生成算法，生成64位的有序ID，包含时间戳、机器ID和序列号

      • 优点：有序（时间戳）、高效、灵活（可以自由调整结构位数）

      • 缺点：也要处理重复ID问题、依赖机器 ID 对分布式环境不友好

重复ID问题：ID 生成依赖时间，在获取时间的时候，可能会出现时间回拨的问题，也就是服务器上的时间突然倒退到之前的时间，进而导致会产生重复 ID

  • 开源框架：

    • UidGenerator（百度）：基于Snowflake改进，适应不同场景。

    • Leaf（美团）：支持号段和Snowflake模式，解决时钟回拨问题。

    • Tinyid（滴滴）：优化的数据库号段模式，支持高并发。\

3. Leaf详解【项目用上】

【代码使用：https://blog.csdn.net/qq_43692950/article/details/136374892】

【用法讲解：https://blog.csdn.net/minkeyto/article/details/104943883】

【美团leaf详解：https://tech.meituan.com/2017/04/21/mt-leaf.html】

【美团leaf改进：https://tech.meituan.com/2019/03/07/open-source-project-leaf.html】

目前主流的分布式ID生成方式，大致都是基于数据库号段模式和雪花算法（snowflake），而美团（Leaf）刚好同时兼具了这两种方式，可以根据不同业务场景灵活切换。\

1. Leaf-segment数据库方案 优化数据库号段模式

原方案每次获取ID都得读写一次数据库，造成数据库压力大。现改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。 ID表结构：包括biz_tag、max_id（当前最大ID）、step、update_time等字段。biz_tag（业务标识符）：每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz_tag分库分表就行。step（号段步长）：每次获取ID数量 缺点：

  1. ID不够随机 ==》 Leaf-snowflake方案

  2. TP999数据波动大，会出现tg999偶尔会出现尖刺 ==> 双buffer优化

  3. DB宕机就gg噜 ==> DB一主二从提高可用性

双buffer优化

  1. 背景：ID号段用尽且系统在等待数据库返回新号段期间，涉及数据库I/O操作，可能造成短暂的延迟，导致ID生成暂停。

  2. 解决：为避免在获取新号段期间ID生成中断，Leaf引入了双Buffer，即两个缓存区。一个Buffer正在使用时，另一个Buffer预加载下一个号段。当当前号段即将耗尽时，自动切换到预加载的号段，确保ID生成不间断。

  3. 好处：保证可用性：偶尔的网络抖动不会影响下个号段的更新；降低DB依赖性，即使DB宕机也可以持续发号一段时间

2. Leaf-snowflake方案

Leaf-snowflake基本上就是沿用了snowflake的设计

  • 第1位置为0。

  • 第2-42位是相对时间戳，通过当前时间戳减去一个固定的历史时间戳生成。

  • 第43-52位是机器号workerID，每个Server的机器ID不同。

  • 第53-64位是自增ID。

Leaf-snowflake不同于原始snowflake算法地方，主要是在workId的生成上。Leaf中workId是基于ZooKeeper的顺序Id来生成的，每个应用在使用Leaf-snowflake时都会都在Zookeeper中生成一个顺序Id，相当于一台机器对应一个顺序节点，也就是一个workId。 改进点

  • 时间回拨问题：Leaf-Snowflake处理时间回拨的策略包括阻塞等待、丢弃旧ID、或通过配置允许一定的时间回拨范围。

  • 高可用性：美团对Snowflake算法进行了改进，以应对大规模分布式系统中的实际应用场景，比如优化了算法的时间回拨处理和分布式环境下的机器ID分配。

应用

【https://javaguide.cn/distributed-system/distributed-id-design.html#_1%E3%80%81%E4%B8%80%E7%A0%81%E4%BB%98】

  1. 一码付: 使用动态生成的二维码绑定商品信息，支持多平台支付

  2. 订单号设计:

  • 信息安全: 避免泄露公司运营数据，不能有明显规律。

  • 部分可读: 位数适中，有助于客服查询。

  • 查询效率: 使用纯数字int而不是varchar，提升查询效率。

  1. 优惠券和兑换券:

  • 预先生成: 活动前生成，体量大，需防止破解。

  • 兑换码设计: 使用特殊的编解码策略，保证唯一性和安全性。

  1. 日志跟踪 / 分布式链路跟踪:

  • 跟踪id（TraceId）: 由服务器自行生成，避免依赖外部服务。

  • 跨度id（SpanId）: 通过层级和自增序列标识请求链路位置。

短链接: 通过数字ID转高进制压缩网址长度，便于传播。 \

分布式锁

【分布式锁常见实现方案总结】

【分布式面试题，12道分布式八股文（8千字25张手绘图），面渣逆袭必看👍】

1. 为什么要分布式锁

为了保证共享资源被安全地访问，我们需要使用互斥操作对共享资源进行保护，即同一时刻只允许一个线程访问共享资源，其他线程需要等待当前线程释放后才能访问。这样可以避免数据竞争和脏数据问题，保证程序的正确性和稳定性。单机情况下我们是靠JVM锁实现的，但分布式系统下不同服务运行在独立的JVM进程上，就必须使用分布式锁 分布式锁应具备基本条件：

  1. 互斥

  2. 超时释放

  3. 可重入

  4. 高可用\

2. 怎么实现分布式锁

【场景很有意思，还有伪代码：https://blog.csdn.net/leader_song/article/details/138927511】\

1. Redis

【多种Redis实现方式，好！https://www.cnblogs.com/wangyingshuo/p/14510524.html】存在问题：

  1. 满足分布式锁特点

  2. 是否为原子操作

  3. 锁过期释放，但是业务还没执行完

  4. 锁被别的线程误删 优化过程：SETNX + EXPIRE：基本方案，但非原子操作，可能导致锁无法释放。SETNX + 时间戳：通过value存储过期时间，解决2，没解决3、4Lua脚本：确保SETNX和EXPIRE原子操作，解决2，没解决3、4SET扩展命令：EX PX NX 解决2，没解决3、4

  • NX :表示key不存在的时候，才能set成功，也即保证只有第一个客户端请求才能获得锁，而其他客户端请求只能等其释放锁，才能获取。

  • EX seconds :设定key的过期时间，时间单位是秒。

  • PX milliseconds: 设定key的过期时间，单位为毫秒

  • XX: 仅当key存在时设置值

SET EX PX NX + 校验唯一随机值，再删除：通过唯一标识防止误删锁。解决2、4，没解决3Redisson：引入看门狗机制，防止锁过期问题。全部解决Redlock：适用于Redis集群环境的高级分布式锁方案。全部解决 + 分布式 \

2. Mysql

创建一张锁表，数据库对字段作唯一性约束。加锁的时候，在锁表中增加一条记录；释放锁的时候删除记录。如果有并发请求同时提交到数据库，数据库会保证只有一个请求能够得到锁。这种属于数据库 IO 操作，效率不高，而且频繁操作会增大数据库的开销，因此这种方式在高并发、高性能的场景中用的不多。\

3. ZooKeeper

是一个比较重的分布式组件，通过创建节点实现分布式锁具备高可用、可重入、阻塞锁特性，可解决失效死锁问题，但性能不如redis\

分布式锁需求上线后重点观察指标（被问了两次了，简历上有分布式锁的同学可以关注下）

你的项目提到了分布式锁，为什么要用分布式锁你是怎么实现分布式锁的，有没有什么注意事项最后释放的时候怎么保证释放的锁是自己的呢除了用Redis实现分布式锁，你还能想到什么实现方式

  • 这里没答上来，提示可以用数据库：用SELECT FOR UPDATE，就是数据库的行锁来实现

  • 面试官说还可以用唯一索引来实现

  • 黑马点评问题_牛客网

分布式事务

【分布式面试题，12道分布式八股文（8千字25张手绘图），面渣逆袭必看👍】

分布式事务其实就是将对同一库事务的概念扩大到了对多个库的事务。目的是为了保证分布式系统中的数据一致性。分布式事务处理的关键是：

  1. 需要记录事务在任何节点所做的所有动作；

  2. 事务进行的所有操作要么全部提交，要么全部回滚。

分布式常见的实现方案有 2PC、3PC、TCC、本地消息表、MQ消息事务、最大努力通知、SAGA事务 等等。

1. 2PC（Two-Phase Commit）

  • 描述：2PC是经典的分布式事务协议，分为两个阶段：

    • 准备阶段：协调者向所有参与者请求准备提交事务。

    • 提交阶段：所有参与者同意后，协调者发出提交命令；若有参与者拒绝，协调者发出回滚命令。

  • 优点：简单直观，尽量保证一致性。

  • 缺点：协调者/参与者出现故障，会导致系统无法完成事务的提交或回滚，存在阻塞问题

\

2. 3PC（Three-Phase Commit）

  • 描述：3PC是2PC的改进版，增加了一个中间阶段以减少阻塞：

    • 准备阶段：协调者向所有参与者请求准备提交事务。

    • 预提交阶段：协调者请求参与者预提交事务，参与者响应准备就绪。【减少因协调者故障导致的阻塞，因为参与者已经准备好提交】

    • 提交阶段：协调者最终发送提交或回滚指令。【减少协调者阻塞，参与者可以从预提交状态恢复】

  • 优点：减少了2PC的阻塞问题。

  • 缺点：增加了协议复杂度和通信开销。

3. TCC（Try-Confirm-Cancel）

  • 描述：TCC将事务分为三个阶段：

    • Try：尝试执行操作，预留资源。

    • Confirm：确认操作，正式提交事务。

    • Cancel：取消操作，回滚事务。

  • 优点：适用于长时间运行的事务，具有较高的灵活性。

  • 缺点：需要业务支持并实现补偿逻辑，复杂度高。

4. 本地消息表

  • 描述：将消息发送和事务操作结合，通过本地消息表记录未处理的消息：

5. MQ消息事务

\

6. Seata 开源的分布式事务解决方案

【中文文档：https://seata.io/zh-cn/docs/overview/what-is-seata.html】【使用 + 项目集成：https://blog.csdn.net/weixin_43759352/article/details/134618081】Seata 中存在这么几种重要角色：

  • TC（Transaction Coordinator）：事务协调者。管理全局的分支事务的状态，用于全局性事务的提交和回滚。

  • TM（Transaction Manager）：事务管理者。用于开启、提交或回滚事务。

  • RM（Resource Manager）：资源管理器。用于分支事务上的资源管理，向 TC 注册分支事务，上报分支事务的状态，接收 TC 的命令来提交或者回滚分支事务

\

分布式设计 == 幂等

详见：幂等

分布式限流

详见：

服务治理：限流、熔断、降级

\

\

其他

分布式面试题，12道分布式八股文（8千字25张手绘图），面渣逆袭必看👍

分布式id生成方法？

讲了下uuid，redis，leaf美团leaf替换雪花id：原因及实现原理令牌桶和漏斗算法介绍一下，业务上这两个怎么做选择分布式一致性算法，只浅浅讲了raft的半数以 【这一套题都好好：https://www.nowcoder.com/feed/main/detail/c5ef447b0bbe427a9e25a8bba2b252f4?sourceSSR=search】

什么适合做唯一标识？

18、uuid是什么时机生成的？讲讲项目中订单的项目业务

25、如何保证乘车人表和订单表数据的一致性？（分布式事务 没了解过）

26、讲讲项目中订单相关的流程？

27、讲讲雪花算法及组成，缺点及解决方案？组成中数据中心号和机器标识码的含义，各占多少bit（我引申到了美团分布式框架Leaf）\

消息丢失场景，从发送的confirm到broker持久化到消费者ack，再到broker没收到ack重发如何保证幂等，再到唯一id生成(uuid，雪花，数据库自增，美团也有一个leaf啥的)\

  • 设计一个分配有序的分布式ID的模型

    • 面试官举的是论坛的例子，论坛底下是一层一层的，每一条留言对应一个ID，有序且唯一

    • 回答采用雪花算法（1bit + 41bit-时间戳 + 10bit-工作机器Id + 12bit序列号）

    • 然后问雪花算法的原理，问是否还有其他的吗，然后我回答还有美团的Leaf，但是原理还是不懂。我真是给自己挖坑的好手。\

  1. 单一业务ID有了解哪些算法吗 答：UUID、snowflake和美团leaf算法，自己试过snowflake

  2. snowflake具体介绍

  3. snowflake有什么缺点 复盘感觉应该是想问snowflake如果单机时间出错导致业务ID重复，当时没想到说的是每毫秒最多生成4096个ID。面试官说每毫秒最多生成4096个ID是单机下的，snowflake还有机器号,多机是没有这个限制的，连忙解释说自己只试过单机的。

  4. 那单机下怎么突破4096这个限制？ 压缩时间戳或者机器号的位数给序列号

上一页高可用下一页幂等设计

最后更新于