我的八股笔记专栏的第7篇文章，觉得有用的建议点点订阅。

1.分布式理论

1.CAP 理论

1.什么时候CAP?

CAP 也就是 Consistency（一致性）、Availability（可用性）、Partition Tolerance（分区容错性） 这三个单词首字母组合。

在理论计算机科学中，CAP 定理（CAP theorem）指出对于一个分布式系统来说，当设计读写操作时，只能同时满足以下三点中的两个：

• 一致性(Consistency)是指更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致(强一致性)，不能存在中间状态。

• 可用性(Availability) 是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。

• 分区容错性(Partition tolerance) 是指分布式系统在遇到任何网络分区故障时，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。

2.为什么分布式系统中无法同时保证一致性和可用性？

首先一个前提，对于分布式系统而言，分区容错性是一个最基本的要求，因此基本上我们在设计分布式系统的时候只能从一致性（C）和可用性（A）之间进行取舍。

如果保证了一致性（C）：对于节点N1和N2，当往N1里写数据时，N2上的操作必须被暂停，只有当N1同步数据同步到N2时才能对N2进行读写请求，在N2被暂停操作期间客户端提交的请求会收到失败或超时。显然，这与可用性是相悖的。

如果保证了可用性（A）：那就不能暂停N2的读写操作，但同时N1在写数据的话，这就违背了一致性的要求。

3.权衡

在分布式系统中，分区容忍性必不可少，因为需要总是假设网络是不可靠的。因此，CAP 理论实际上是要在可用性和一致性之间做权衡。

可用性和一致性往往是冲突的，很难使它们同时满足。在多个节点之间进行数据同步时，

• 为了保证一致性（CP），不能访问未同步完成的节点，也就失去了部分可用性；
• 为了保证可用性（AP），允许读取所有节点的数据，但是数据可能不一致。

最终一致思想：各分支事务分别执行并提交，如果有不一致的情况，再想办法恢复数据（AP） 强一致思想：各分支事务执行完业务不要提交，等待彼此结果。而后统一提交或回滚（CP）

2.BASE理论

BASE 是基本可用（Basically Available）、软状态（Soft State）和最终一致性（Eventually Consistent）三个短语的缩写。

BASE是CAP理论中AP方案的延伸，核心思想是即使无法做到强一致性（StrongConsistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consitency）。它的思想包含三方面：

• 1、Basically Available（基本可用）：基本可用是指分布式系统在出现不可预知的故障的时候，允许损失部分可用性，但不等于系统不可用。

• 2、Soft state（软状态）：即是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

• 3、Eventually consistent（最终一致性）：强调系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。其本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

2.分布式一致性算法

1.Paxos算法

用于达成共识性问题，即对多个节点产生的值，该算法能保证只选出唯一一个值。

主要有三类节点：

• 提议者（Proposer）：提议一个值；
• 接受者（Acceptor）：对每个提议进行投票；
• 告知者（Learner）：被告知投票的结果，不参与投票过程。

算法流程

Paxos算法的流程是一个两阶段的过程，包括准备（Prepare）阶段和接受（Accept）阶段。

• 准备阶段：

1. 提案编号选择：Proposer选择一个提案编号N，这个编号必须是全局唯一且递增的，可以使用时间戳加服务器ID来生成。
2. 发送Prepare请求：Proposer向半数以上的Acceptor发送编号为N的Prepare请求。
3. 响应处理：Acceptor在收到Prepare请求后，如果它没有收到更高编号的Prepare请求，就会承诺不再接受更低编号的提案，并回应Proposer。

• 接受阶段：

1. 发送Accept请求：当Proposer收到多数Acceptor对Prepare请求的响应后，它将发送一个携带提案内容和提案编号N的Accept请求给所有Acceptor。
2. 接受提案：Acceptor在收到Accept请求后，如果该请求的提案编号大于或等于它已经响应的Prepare请求中的最大编号，那么它就会接受这个提案。
3. 学习结果：一旦提案被多数Acceptor接受，该提案就被认为是选定的，Learner可以从Acceptor那里获取并学习这个决策结果。

总的来说，Paxos算法通过这两个阶段的交互，确保了即使在部分节点或网络出现问题的情况下，分布式系统也能够就某个值达成一致性。这个过程需要满足一定的条件，以确保最终能够选出一个提案。

2.Raft算法

Raft算法是一种用于管理多副本状态机的日志复制的共识算法。

Raft算法的流程包括领导者选举、日志复制和安全性保障等关键步骤。

以下是对Raft算法流程的详细阐述：

1. 领导者选举（Leader Election）：

• 在Raft中，时间被分为任期（Term），每个任期开始时都会进行领导者选举。
• 如果没有领导者或领导者出现故障，所有节点都有可能成为候选人（Candidate）并开始新的选举。
• 候选人通过向其他节点发送投票请求来争取成为领导者，如果得到多数派的投票，则该节点将成为领导者。

2. 日志复制（Log Replication）：

• 当领导者选出后，领导者负责处理客户端请求，每个请求都会被领导者以日志条目的形式记录下来。
• 领导者然后将这些日志条目同步到集群中的其他节点，也就是跟从者（Follower）。
• 跟从者接收到日志条目后将其写入自己的日志中，然后向领导者确认。一旦领导者收到多数跟从者的确认，该日志条目就被认为已经提交，领导者随后将通知客户端操作成功，并推进其日志中的commit index，即可以应用到状态机中的索引位置。

3. 安全性（Safety）：

• Raft通过一系列规则确保了系统的安全性，即使在出现网络延迟、分区或节点失效等情况下也不会导致数据不一致的问题。
• 例如，Raft使用心跳机制来判断领导者是否仍然有效，如果跟从者在一定时间内没有收到领导者的消息，它们会认为领导者可能已经崩溃，并开始新一轮的领导者选举过程。

4. 日志压缩（Log Compaction）：

• 为了优化存储空间的使用，Raft支持日志压缩功能。一旦日志条目被安全地复制到大多数节点上，并且应用到了各个节点的状态机之后，这些条目就可以被删除以释放空间。

5. 成员变更（Membership Change）：

• Raft还提供了一种机制来支持集群成员的动态变更，即在不影响系统一致性的情况下增加或移除节点。

综上所述，Raft算法通过上述流程管理多副本状态机的日志复制，实现了分布式系统中的强一致性和高容错性。它以其相对简单和易于实现的特点，在业界得到了广泛的应用与认可。

3.分布式ID

1.为什么需要分布式ID

传统的单体架构的时候，我们基本是单库然后业务单表的结构。每个业务表的ID一般我们都是从1增，通过AUTO_INCREMENT=1设置自增起始值，但是在分布式服务架构模式下分库分表的设计，使得多个库或多个表存储相同的业务数据。这种情况根据数据库的自增ID就会产生相同ID的情况，不能保证主键的唯一性。我们就需要分布式ID为不同的数据节点生成全局唯一主键

2.分布式 ID 需要满足哪些要求?

分布式 ID 作为分布式系统中必不可少的一环，很多地方都要用到分布式 ID。

一个最基本的分布式 ID 需要满足下面这些要求：

• 全局唯一：ID 的全局唯一性肯定是首先要满足的！
• 高性能：分布式 ID 的生成速度要快，对本地资源消耗要小。
• 高可用：生成分布式 ID 的服务要保证可用性无限接近于 100%。
• 方便易用：拿来即用，使用方便，快速接入！

除了这些之外，一个比较好的分布式 ID 还应保证：

• 安全：ID 中不包含敏感信息。
• 有序递增：如果要把 ID 存放在数据库的话，ID 的有序性可以提升数据库写入速度。并且，很多时候 ，我们还很有可能会直接通过 ID 来进行排序。
• 有具体的业务含义：生成的 ID 如果能有具体的业务含义，可以让定位问题以及开发更透明化（通过 ID 就能确定是哪个业务）。
• 独立部署：也就是分布式系统单独有一个发号器服务，专门用来生成分布式 ID。这样就生成 ID 的服务可以和业务相关的服务解耦。不过，这样同样带来了网络调用消耗增加的问题。总的来说，如果需要用到分布式 ID 的场景比较多的话，独立部署的发号器服务还是很有必要的。

3.分布式 ID 常见解决方案

分布式 ID 常见解决方案有以下几种：

1. 数据库自增 ID：在分布式系统中，每个节点都从数据库中获取一个唯一的自增 ID。这种方式实现简单，但存在单点故障风险，且在高并发场景下性能较差。
2. UUID：使用 UUID（通用唯一识别码）作为分布式 ID，可以保证全局唯一性。但 UUID 过长(128位)，存储和传输效率较低。
3. 雪花算法：Twitter 开源的分布式 ID 生成算法，基于时间戳、机器 ID 和序列号生成唯一 ID。实现简单，性能高效，但存在时间回拨问题。
4. 美团 Leaf：美团开源的分布式 ID 生成器，基于 Snowflake 算法改进，解决了时间回拨问题，支持自定义位数。
5. 百度 UidGenerator：百度开源的分布式 ID 生成器，基于 Snowflake 算法改进，解决了时间回拨问题，支持自定义位数。
6. Flicker IdWorker：Flicker 开源的分布式 ID 生成器，基于 MySQL 数据库实现，通过预分配策略生成唯一 ID。性能较高，但依赖数据库。
7. MongoDB ObjectId：MongoDB 数据库中的 ObjectId 可以作为分布式 ID，由时间戳、机器 ID、进程 ID 和计数器组成。但依赖于 MongoDB 数据库。
8. Redis 生成 ID：利用 Redis 的原子操作命令（如 INCRBY）生成分布式 ID。性能较高，但依赖于 Redis 数据库。

比较uuid和雪花算法

UUID和雪花算法各有其优势和适用场景，它们在分布式系统中生成唯一标识符的方式存在差异。具体如下：

• UUID的特点：

1. 适用于非分布式系统或对顺序性要求不高的场合。
2. 生成的是32位随机字符串，确保了全局唯一性。
3. 由于是随机生成，所以不保证ID的有序性。
4. UUID的空间占用相对较大。

• 雪花算法的特点：

1. 适用于分布式系统，能够生成递增且趋势有序的主键ID。
2. 生成的ID是数字组成，最大64位，比UUID更有序且存储空间更小。
3. 通过时间戳+随机数+服务器标记的组合确保了全局唯一性和趋势递增性。
4. 雪花算法能够在不依赖数据库的情况下由编程语言直接生成，适合分布式场景。

在实际应用场景中，如果需要保证ID的顺序性和趋势递增，或者希望能够通过ID直观地看出数据的生成顺序，那么雪花算法更为合适。而如果对ID的顺序性没有特别要求，只需要保证全局唯一性，那么UUID可能是一个更简单的选择。

总的来说，UUID和雪花算法都是解决分布式系统中生成唯一标识符的有效方法，它们的选择取决于具体的应用需求和场景。

4.分布式锁

1.为什么需要分布式锁？

在多线程环境中，如果多个线程同时访问共享资源（例如商品库存、外卖订单），会发生数据竞争，可能会导致出现脏数据或者系统问题，威胁到程序的正常运行。

举个例子，假设现在有 100 个用户参与某个限时秒杀活动，每位用户限购 1 件商品，且商品的数量只有 3 个。如果不对共享资源进行互斥访问，就可能出现以下情况：

• 线程 1、2、3 等多个线程同时进入抢购方法，每一个线程对应一个用户。
• 线程 1 查询用户已经抢购的数量，发现当前用户尚未抢购且商品库存还有 1 个，因此认为可以继续执行抢购流程。
• 线程 2 也执行查询用户已经抢购的数量，发现当前用户尚未抢购且商品库存还有 1 个，因此认为可以继续执行抢购流程。
• 线程 1 继续执行，将库存数量减少 1 个，然后返回成功。
• 线程 2 继续执行，将库存数量减少 1 个，然后返回成功。
• 此时就发生了超卖问题，导致商品被多卖了一份。

2.分布式锁应该具备哪些条件？

一个最基本的分布式锁需要满足：

• 互斥：任意一个时刻，锁只能被一个线程持有。
• 高可用：锁服务是高可用的，当一个锁服务出现问题，能够自动切换到另外一个锁服务。并且，即使客户端的释放锁的代码逻辑出现问题，锁最终一定还是会被释放，不会影响其他线程对共享资源的访问。这一般是通过超时机制实现的。
• 可重入：一个节点获取了锁之后，还可以再次获取锁。

除了上面这三个基本条件之外，一个好的分布式锁还需要满足下面这些条件：

• 高性能：获取和释放锁的操作应该快速完成，并且不应该对整个系统的性能造成过大影响。
• 非阻塞：如果获取不到锁，不能无限期等待，避免对系统正常运行造成影响。

3.分布式锁的常见实现方式

分布式锁的常见实现方式包括基于缓存、数据库和Zookeeper等。具体如下：

1. 基于缓存实现分布式锁：

   • 利用Redis的SETNX（SET If Not eXists）和SETEX（SET with EXpiration）命令来实现。SETNX用于在键不存在时设置值，SETEX用于设置带过期时间的键值对。这种方式简单高效，但在Redis集群模式下需要考虑一致性问题。

2. 基于数据库实现分布式锁：

   • 可以通过在数据库中创建一个专门的锁表，使用insert和delete操作来加锁和解锁。这种方式操作简单，易于理解，但性能开销较大，可能不适合高并发场景。此外，还需要考虑锁超时和主从备份等问题。

3. 基于Zookeeper实现分布式锁：

   • Zookeeper是一个分布式协调服务，它通过创建临时节点（EPHEMERAL nodes）的方式来实现分布式锁。客户端可以在Zookeeper中创建一个临时节点，当节点创建成功时，客户端就获得了锁。其他客户端如果尝试创建相同路径的节点则会失败，从而等待锁释放。Zookeeper能够保证高可用性和一致性，适合对锁的安全性要求较高的场景。

在选择分布式锁的实现方式时，需要根据具体的业务需求和技术架构来决定。例如，如果业务对锁的性能要求极高，可能会优先考虑基于缓存的实现；如果业务对锁的安全性和一致性要求较高，则可能会选择基于Zookeeper的实现。此外，还需要考虑系统的可扩展性、容错性以及维护成本等因素。

5.分布式事务

1.什么是分布式事务？

指事务的操作位于不同的节点上，需要保证事务的 ACID 特性。

例如在下单场景下，库存和订单如果不在同一个节点上，就涉及分布式事务。

分布式锁和分布式事务区别：

• 锁问题的关键在于进程操作的互斥关系，例如多个进程同时修改账户的余额，如果没有互斥关系则会导致该账户的余额不正确。
• 而事务问题的关键则在于事务涉及的一系列操作需要满足 ACID 特性，例如要满足原子性操作则需要这些操作要么都执行，要么都不执行

2.分布式事务解决方案

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

1.两阶段提交（2PC）

两阶段提交（2PC）：这是最常见的分布式事务解决方案，分为准备阶段和提交阶段。在准备阶段，协调者询问所有参与者是否准备好提交事务，如果所有参与者都回答“是”，则进入提交阶段，协调者通知所有参与者提交事务；如果有任何一个参与者回答“否”，则协调者通知所有参与者回滚事务。这种方法的缺点是协调者可能会出现单点故障。

需要注意的是，2PC的主要目的是确保分