分布式系统理论和实战汇总

TOC

• TOC
• CAP 定理
• 一致性协议
• 2PC
• 3PC
• Raft
  • Raft 概述
  • Raft 节点角色
  • Raft 选举过程
  • Raft 与 Paxos 的区别
• Paxos
• Quorum-Based Replication
• 分布式锁
  • 基于数据库实现分布式锁
  • 基于 Redis 实现分布式锁
  • 基于 Zookeeper 实现分布式锁
• 分布式 ID
• 分布式事务
  • 基本思想
  • Seata

CAP 定理

CAP 定理指出对于一个分布式计算系统来说，不可能同时满足以下三点：

1. 一致性（Consistency）：同一时间所有节点返回的数据都是一致的
2. 可用性（Availability）：每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据
3. 分区容错性（Partition Tolerance）：发生网络分区时（即节点之间无法通信），大部分分布式系统都不能在时限内达成数据一致性。所以在分布式系统中 P 是一定该发生的，那么 A 和 C 我们只能选择一个

一致性协议

分布式一致性具体可以分为：

1. 强一致性：是分布式系统中的一个一致性保证，它确保了系统中的所有副本始终保持一致，无论客户端请求在哪个节点处理，系统中的所有节点都能看到相同的数据。
2. 最终一致性：与强一致性不同，最终一致性允许系统在某些时刻存在短暂的不一致，直到系统最终达到一致性。它通常用于高可用性要求较高的系统（如某些 NoSQL 数据库）。

CAP 定理定义了分布式系统中的一致性、可用性和分区容忍性之间的权衡。在实际系统设计中，需要根据需求做出选择。2PC、3PC 和 Paxos 等协议提供了实现这些需求的具体方法。

• 2PC 适用于强一致性的场景，但在网络分区时可能会面临不可用的问题。
• 3PC 是对 2PC 的改进，力图在保证一致性的同时减少因网络分区导致的系统不可用。
• Raft 是一种分布式一致性算法，旨在通过简化 Paxos 算法的理解和实现，提供一种易于理解和实现的一致性协议。
• Paxos 提供了一种强一致性的分布式协议，适用于高容错性和一致性要求的系统，但在分区发生时可能会牺牲可用性。
• Quorum-Based Replication 是一种用于在分布式系统中确保数据一致性和高可用性的策略。通过设置写和读操作所需的 Quorum（法定人数），系统能够容忍部分节点的失败或延迟，确保数据在最终一致的状态下达到各个副本节点。它适用于高可用性要求较高的场景，如 NoSQL 数据库、分布式存储系统 和 缓存系统。

2PC

2PC（Two-Phase Commit）是分布式事务中的一致性协议，保证分布式系统中事务的原子性（即事务要么全部成功，要么全部失败）。2PC 由两个阶段组成：

• 第一阶段（准备阶段）：协调者向所有参与者发送“准备提交”请求，参与者要么同意提交事务，要么拒绝。
• 第二阶段（提交阶段）：如果所有参与者都同意提交，协调者发送“提交”命令；如果有任何一个参与者拒绝，协调者发送“回滚”命令。

2PC 与 CAP 的关系：

• 在 2PC 中，协调者需要等待所有参与者的回应才能决定事务是否提交。如果出现网络分区或某个节点宕机，可能无法确定事务状态，导致系统不可用。因此，2PC 在分区发生时可能会牺牲可用性来保证一致性。

3PC

3PC（Three-Phase Commit）是 2PC 的改进版本，旨在解决 2PC 在面对网络分区和节点崩溃时的阻塞问题。3PC 在 2PC 的基础上增加了一个预提交阶段，以避免事务阻塞。

• 第一阶段（准备阶段）：协调者向参与者发送“准备提交”请求。
• 第二阶段（预提交阶段）：协调者向所有参与者发送“预提交”命令，参与者确认并准备提交。
• 第三阶段（提交阶段）：协调者向所有参与者发送“提交”命令。

为何需要预提交？在 2PC (Two-Phase Commit) 中，如果在第一阶段（准备阶段）和第二阶段（提交阶段）之间发生故障（如网络分区或某个参与者宕机），就会导致协议阻塞，无法完成事务。这是因为没有机制来确保在没有足够信息的情况下做出最终决策。3PC 通过引入一个“预提交阶段”来避免这一问题：

• 如果协调者在第一阶段和第二阶段之间崩溃，参与者已经在“预提交”阶段保存了事务的状态（但未完全提交），因此系统可以在恢复后继续执行，而不需要等待所有节点的反馈来决定事务的最终状态。
• 预提交确保了在第二阶段开始时，参与者已经做好提交准备，减少了事务最终不一致的风险。

Raft

Raft 概述

Raft 是一种分布式一致性算法，旨在通过简化 Paxos 算法的理解和实现，提供一种易于理解和实现的一致性协议。Raft 主要用于 分布式日志复制，它保证了在一个分布式系统中，所有的节点都能达成一致，尤其在一个节点故障或系统出现网络分区的情况下，仍能确保数据的一致性和系统的高可用性。

Raft 算法通过将一致性问题分为三个子问题来简化理解：

1. 领导选举（Leader Election）
2. 日志复制（Log Replication）
3. 安全性（Safety）

Raft 节点角色

Raft 协议中的节点有三种角色：

• Leader：负责处理所有客户端请求，并将它们记录到日志中。所有日志条目都会通过 Leader 进行复制。
• Follower：被动节点，接收来自 Leader 的日志条目，并执行日志条目中的操作。大部分节点在 Raft 集群启动时都是 Follower。
• Candidate：当 Follower 在一段时间内没有接收到 Leader 的心跳（即 Leader 没有按时发送心跳信号），它将变成 Candidate，发起选举来选举新的 Leader。

每个节点维护一份日志，记录了系统的状态变更。Raft 通过复制日志来确保系统的一致性。日志中的每个条目都包括一个索引和一个日志条目内容。

Raft 选举过程

在 Raft 中，当集群启动时，所有节点最初是 Follower。如果在 选举超时（即 Follower 一段时间内没有接收到 Leader 的心跳，这个时间各 Follower 随机），它会变成 Candidate，并发起选举。

• Candidate 会向其他节点请求投票。如果大多数节点投票给它，它就会成为新的 Leader。
• 一旦 Leader 被选举出来，它开始向 Follower 节点复制日志条目。

Raft 与 Paxos 的区别

• 简洁性：Raft 的设计目标之一就是简化实现和理解，相比于 Paxos，Raft 的概念更直观，易于理解和实现。
• Leader 优先：Raft 通过 Leader 来集中处理所有请求，这样在性能和效率上相对更优，而 Paxos 通过多轮投票机制来达成一致，可能更加复杂。
• 日志复制：Raft 强调日志复制，所有操作都通过 Leader 日志进行传递，确保数据一致性；Paxos 不直接处理日志复制问题，它关注的是如何在分布式系统中进行一致性的决策。

Paxos

Paxos 是一种用于保证分布式系统中一致性的算法。它通过提议和投票机制确保系统中的多个副本最终达成一致。Paxos 可以在网络分区和节点崩溃的情况下达成一致决策，适用于高可用性和一致性要求的系统。

Paxos 的选举过程并不像传统的领导选举那样明确，而是通过多个阶段（Prepare、Promise、Propose 和 Accept）达成一致。Paxos 保证，尽管会有多个提案同时存在，但最终会有一个值被选中，且达成一致的提案是唯一的。

• 提案者提出提案并请求投票。
• 接受者通过承诺和投票来决定是否接受提案。
• 学习者最终会了解到哪一个提案被选为一致的决策。

Paxos 是一种容错机制，能够在分布式系统中保证数据一致性，即使在部分节点失败或网络分区的情况下，最终也能达成一致的选举结果。

Quorum-Based Replication

Quorum-Based Replication 是一种用于分布式系统中实现数据一致性的策略，尤其是在高可用性和容错性要求较高的系统中，如 NoSQL 数据库（如 Cassandra 和 Riak）和分布式存储系统。它通过设置读和写的 Quorum（法定人数）来保证数据在多个副本间的最终一致性。

在分布式系统中，数据通常会被复制到多个节点上。Quorum-based replication 通过定义 读（read） 和 写（write） 操作所需的最小确认节点数来确保一致性。在每个操作中，系统会在特定数量的节点上执行并确认操作，只有当足够的节点同意时，操作才会被认为是成功的。

主要概念：

• Quorum：一个操作需要的最小节点数。通常，写操作和读操作会使用不同的 Quorum 大小来确保一致性。
• 写 Quorum (W)：执行写操作时，需要在至少 W 个节点上完成写操作才能算作成功。
• 读 Quorum (R)：执行读操作时，需要从至少 R 个节点获取数据才能返回结果。
• 副本数 (N)：数据在系统中被复制的副本数，通常是指每个数据的副本存储在多少个节点上。

工作原理：

1. 写操作：当进行写操作时，数据会被写入到至少 W 个节点。如果系统的副本数为 N，那么 W 必须大于 N/2，即写操作必须在超过半数的节点上成功写入才能认为是成功。
2. 读操作：当进行读操作时，系统会从至少 R 个节点中读取数据。如果在这些节点中存在不同版本的数据，系统会通过版本号、时间戳或其他方式来解决冲突并保证数据一致。
3. 一致性保证：为了保证一致性，通常有一个要求：W + R > N。这个条件保证了在读写操作之间，至少有一个节点是重叠的（即包含了最新的数据）。例如，如果在写操作时写入了 W 个节点，那么当执行读操作时，至少会从 R 个节点中读取到数据，这样可以避免读取到过时的数据。

分布式锁

分布式锁是一种用于保证在分布式系统中，同一时间只有一个服务或线程可以访问共享资源的机制，防止不同节点上的并发操作产生数据不一致或其他冲突。由于分布式系统中，多个服务实例通常会并发访问同一资源，因此需要一种机制来确保在某些时刻，只有一个实例能对资源进行操作。

基于数据库实现分布式锁

1. 悲观锁：select ... for update
2. 乐观锁：版本号递增（CAS）

基于 Redis 实现分布式锁

1. 初始化锁的时候，使用 setnx k v，并使用 expire 命令为锁添加一个超时时间，超过该时间则自动释放锁，锁的 value 值为一个随机生成的 UUID，通过此在释放锁的时候进行判断;
2. 获取锁的时候设置一个获取的超时时间，若超过这个时间则放弃获取锁;
3. 释放锁的时候，通过 UUID 判断是不是该锁，若是该锁，则执行 delete 进行锁释放。

基于 Zookeeper 实现分布式锁

1. 创建一个目录 mylock；
2. 线程 A 想获取锁就在 mylock 目录下创建临时顺序节点；
3. 获取 mylock 目录下所有的子节点，然后获取比自己小的兄弟节点，如果不存在，则说明当前线程顺序号最小，获得锁；
4. 线程 B 获取所有节点，判断自己不是最小节点，设置监听比自己次小的节点；
5. 线程 A 处理完，删除自己的节点，线程 B 监听到变更事件，判断自己是不是最小的节点，如果是则获得锁。

分布式 ID

分布式 ID 是指在分布式系统中，生成的标识符（ID）具有全局唯一性，能够在多个节点或服务之间保证不重复，并且通常是高效、顺序的。分布式 ID 的生成通常需要满足以下几个要求：

• 全局唯一性：每个 ID 必须在整个分布式系统中唯一，不会发生重复。
• 高效性：生成 ID 的速度必须足够快，不会成为系统的瓶颈。
• 顺序性（可选）：有些场景可能需要 ID 按时间递增（有序），以便在数据库中按顺序存储。
• 分布式系统兼容性：在多个节点、服务实例之间，ID 的生成方式应具有良好的兼容性，避免产生冲突。

实现方案：

1. 雪花算法
2. UUID
3. 数据库自增 ID + 分布式锁

雪花算法（Snowflake Algorithm）是由 Twitter 提出的分布式唯一 ID 生成算法，旨在解决在分布式系统中生成 全局唯一且递增 的 ID 问题。它通过结合时间戳、机器标识、序列号等信息，生成一个 64 位的 ID，确保高并发环境下的唯一性和顺序性。

雪花算法生成的 ID 是一个 64 位的整数，通常分成以下几个部分：

1. 符号位（1 bit）：始终为 0，保证生成的 ID 是正数。
2. 时间戳（41 bits）：41 位时间戳，表示自某个纪元以来的毫秒数，支持约 69 年 的时间范围。
3. 机器 ID（10 bits）：10 位机器标识，支持最多 1024 台机器。可以根据需要分为数据中心 ID 和机器 ID。
4. 序列号（12 bits）：在同一毫秒内，支持生成 最多 4096 个唯一 ID，保证 ID 的唯一性和高并发。

雪花算法的时钟回拨问题：由于雪花算法依赖时间戳生成 ID，如果机器的系统时钟发生回拨（如 NTP 同步或系统时间调整），可能会导致 ID 冲突或顺序错误。优化：

1. 通过记录上次生成的时间戳，在时钟回拨时暂停 ID 生成，直到时钟恢复到正确的时间。
2. 增加时间戳回拨检测机制，例如通过记录时间戳的最大值，避免出现回拨导致的冲突。

分布式事务

基本思想

​分布式系统会把一个应用系统拆分为可独立部署的多个服务，各个服务的事务会操作各自的数据库，因此需要服务与服务之间远程协作才能完成事务操作。这种分布式系统环境下由不同的服务之间通过网络远程协作完成事务称之为分布式事务。

例如用户下一个订单，需要首先创建订单，然后删减库存，接着扣除用户的金钱，最后完成订单。这个过程中，每个操作都可以作为一个微服务，每个微服务操作对应的数据库，而各个数据库可能分布在不同机器上，那么分布式事务就产生了，我们要确保一个事务被正确地处理，必须解决好分布式事务的数据提交与回滚。

Seata

Seata 是一款开源的分布式事务解决方案，致力于提供高性能和简单易用的分布式事务服务。在 Seata 中，分布式事务的执行过程通常涉及三个主要角色：

• TC (Transaction Coordinator)：事务协调者，维护全局和分支事务的状态，驱动全局事务提交或回滚。
• TM (Transaction Manager)：事务管理器，定义全局事务的范围：开始全局事务、提交或回滚全局事务。
• RM (Resource Manager)：资源管理器，管理分支事务处理的资源，与 TC 交谈以注册分支事务和报告分支事务的状态，并驱动分支事务提交或回滚。

Seata 使用 2PC 协议来保证分布式事务的 原子性 和 一致性，确保在多个服务间的操作要么全部成功（提交），要么全部失败（回滚）。

在 Seata 中，分布式事务的执行流程：

1. TM 开启分布式事务（TM 向 TC 注册全局事务记录）；
2. 按业务场景，编排数据库、服务等事务内资源（RM 向 TC 汇报资源准备状态 ）；
3. TM 结束分布式事务，事务一阶段结束（TM 通知 TC 提交/回滚分布式事务）；
4. TC 汇总事务信息，决定分布式事务是提交还是回滚；
5. TC 通知所有 RM 提交/回滚 资源，事务二阶段结束；

为什么不使用 Raft？在分布式事务中，Seata 更注重事务的一致性和原子性，并且其主要目标是让事务能够在分布式环境中进行有效的协调和管理。Raft 更多地关注在分布式系统中如何处理节点故障、保证一致性和日志同步，而 Seata 更侧重于事务的 隔离性 和 原子性。Seata 的事务协调 更适合使用类似 2PC 或 TCC 这种高效的协议，而 Raft 的复杂性和实现方式对于事务管理来说可能不够合适。