分布式

作者： 分类：笔记 字数：10667
CAP：

CAP理论是分布式计算系统中的一个基本理论，由Eric Brewer提出，并由Seth Gilbert和Nancy Lynch正式证明。它指出在一个分布式系统中，不可能同时满足以下三个属性：

  1. 一致性（Consistency）：每个读操作都能读到最新的写结果，即所有节点在同一时刻看到的数据是一致的。在分布式系统中，这意味着任何数据更新必须在所有相关的副本上生效后，才能被认为是成功的。
  2. 可用性（Availability）：每个请求都能得到一个响应，不管这个响应成功与否。即使部分节点故障，系统整体仍然可以处理客户端的请求。
  3. 分区容错性（Partition Tolerance）：尽管网络可能失败（如分隔成多个独立的子网），系统仍然能够运作。这意味着即使某些消息丢失或延迟，系统依然能够提供服务。

考虑一个简单的例子，假设我们有两个节点A和B，它们之间需要保持一致性和应对网络分区。

  • 如果我们要求系统具有分区容错性（P），那么在网络分区发生时，A和B之间的通信可能会中断。
  • 如果在这个时候我们也要求系统具有一致性（C），那么当A接收到了一个写请求并更新了它的状态，由于无法与B通信，B将不会知道这次更新。因此，如果一个读请求到达B，它将返回过期的数据，这违反了一致性的原则。为了保持一致性，我们必须阻止B响应读请求直到它从A那里得到了更新的信息，这就牺牲了可用性（A）。
  • 另一方面，如果我们选择可用性（A），即使在网络分区的情况下，A和B都将继续接受读写请求。然而，在这种情况下，如果A和B不能同步它们的状态，系统就不能保证一致性（C）。因此，选择了可用性就意味着放弃了强一致性。

所以，在设计分布式系统时，通常需要在这三者之间做出权衡，根据具体的应用场景来决定放弃哪一个属性。例如：

  • 选择CP（一致性+分区容错性）意味着在网络出现问题时，系统会选择等待直到确保所有节点都达到一致状态，这可能会导致某些节点暂时不可用。
  • 选择AP（可用性+分区容错性）则意味着即使在网络问题期间，系统也会继续响应请求，但可能会返回不完全一致的结果。
  • 选择CA（一致性+可用性）实际上是不可能实现的，因为在实际的分布式环境中，网络分区是一个不可避免的事实。如果要避免分区，那就意味着系统不能真正分布，也就不存在所谓的分布式系统了。

网络分区问题：

在网络分区（Network Partition）的情况下，分布式系统中的不同部分可能无法相互通信，导致原本作为一个整体运行的系统分裂成多个独立的部分。这种情况在Redis或Zookeeper这样的集群环境中被称为“脑裂”（Split Brain）。当脑裂发生时，每个独立的部分可能会继续处理读写请求，而不知道其他部分的存在或状态，这可能导致数据不一致、重复的数据更新等问题。

脑裂现象

以Zookeeper为例，它是一个为分布式应用提供协调服务的工具。如果一个由3个节点组成的Zookeeper集群中出现了网络分区，使得两个节点可以互相通信但与第三个节点失去联系，这时就可能发生脑裂。如果这两个能互相通信的节点认为它们构成了多数派，并继续进行选举和操作，那么剩下的那个孤立节点也可能尝试形成自己的多数派或者单独行动，这就形成了两个独立的工作组，各自认为自己是合法的领导者，这就是所谓的脑裂现象。

对于Redis集群来说，脑裂可能导致主从复制出现问题，比如两个不同的节点都认为自己是当前的主节点，接受写操作，而这会导致数据不一致的问题。

解决方法

  1. Quorum机制：这是最常用的解决脑裂问题的方法之一。通过设置一个大多数原则（如Paxos或Raft算法），确保只有拥有超过半数成员支持的分区才能进行写操作。例如，在一个5节点的集群中，至少需要3个节点的同意才能执行写入操作。这种方法有效地避免了脑裂问题，因为它保证了任何时候只有一个分区能够合法地处理写请求。
  2. TTL（Time To Live）或租约机制：在这种机制下，领导者会定期发送心跳信号给所有跟随者，并且每次都会附带一个新的TTL值。如果跟随者在TTL时间内没有收到心跳信号，则认为当前领导者失效，并触发新的领导者选举过程。这种方法可以帮助减少由于临时网络问题导致的脑裂风险。
  3. 版本号或时间戳：为了防止不同分区上的数据冲突，可以使用版本号或时间戳来标记数据。当网络恢复后，可以通过比较版本号或时间戳来决定哪个副本是最新的，并以此为基础进行数据同步。
  4. 手动干预：在一些情况下，可能需要管理员手动介入来解决脑裂问题。比如确定哪个分区应该被认为是权威的，并基于此来修复数据一致性问题。
分布式事务：

2PC：

  • 2PC：两阶段提交，将事务的提交过程分为资源准备和资源提交两个阶段，并且由事务协调者来协调所有事务参与者，如果准备阶段所有事务参与者都预留资源成功，则进行第二阶段的资源提交，否则事务协调者回滚资源。

    1. 协调者向所有参与者发送事务内容，询问是否可以提交事务，并等待答复。
    2. 各参与者执行本地事务操作，将 undo 和 redo 信息记入事务日志中（但不提交事务）。
    3. 如参与者执行成功，给协调者反馈同意，否则反馈中止，表示事务不可以执行。

    4. 协调者收到各个参与者的准备消息后，根据反馈情况通知各个参与者commit提交或者rollback回滚。

      1. 协调者节点向所有参与者节点发出正式提交的 commit 请求。
      2. 收到协调者的 commit 请求后，参与者正式执行事务提交操作，并释放在整个事务期间内占用的资源。
      3. 参与者完成事务提交后，向协调者节点发送ACK消息。
      4. 协调者节点收到所有参与者节点反馈的ACK消息后，完成事务。
      • 协调者向所有参与者发出 rollback 回滚操作的请求。
      • 参与者利用阶段一写入的undo信息执行回滚，并释放在整个事务期间内占用的资源。
      • 参与者在完成事务回滚之后，向协调者发送回滚完成的ACK消息。
      • 协调者收到所有参与者反馈的ACK消息后，取消事务。

  • 2PC缺陷：

    • 性能问题：执行过程中，所有参与节点都是事务阻塞性的，当参与者占有公共资源时，其他第三方节点访问公共资源就不得不处于阻塞状态，为了数据的一致性而牺牲了可用性，对性能影响较大，不适合高并发高性能场景。
    • 可靠性问题：2PC非常依赖协调者，当协调者发生故障时，尤其是第二阶段，那么所有的参与者就会都处于锁定事务资源的状态中，而无法继续完成事务操作（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
    • 数据一致性问题：在阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这会导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
    • 二阶段无法解决的问题：协调者在发出 commit 消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了，那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

3PC:

  • 3PC：三阶段提交协议，是二阶段提交协议的改进版本，三阶段提交有两个改动点，1）在协调者和参与者中都引入超时机制；2）在第一阶段和第二阶段中插入一个准备阶段，保证了在最后提交阶段之前各参与节点的状态是一致的。

    1. 事务询问：协调者向所有参与者发出包含事务内容的 canCommit 请求，询问是否可以提交事务，并等待所有参与者答复。
    2. 响应反馈：参与者收到 canCommit 请求后，如果认为可以执行事务操作，则反馈 yes 并进入预备状态，否则反馈 no。

    3. 协调者根据参与者的反应情况来决定是否可以进行事务的 PreCommit 操作。根据响应情况，有以下两种可能：

      1. 发送预提交请求：协调者向参与者发送 PreCommit 请求，并进入准备阶段。
      2. 事务预提交 ：参与者接收到 PreCommit 请求后，会执行本地事务操作，并将 undo 和 redo 信息记录到事务日志中（但不提交事务）
      3. 响应反馈 ：如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。
      • 假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
      • 发送中断请求 ：协调者向所有参与者发送 abort 请求。
      • 中断事务 ：参与者收到来自协调者的 abort 请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

    4. 该阶段进行真正的事务提交，也可以分为以下两种情况：

      1. 发送提交请求：协调接收到所有参与者发送的ACK响应，那么他将从预提交状态进入到提交状态，并向所有参与者发送 doCommit 请求。
      2. 本地事务提交：参与者接收到doCommit请求之后，执行正式的事务提交，并在完成事务提交之后释放所有事务资源。
      3. 响应反馈：事务提交完之后，向协调者发送ack响应。
      4. 完成事务：协调者接收到所有参与者的ack响应之后，完成事务。
      • 中断事务：**任何一个参与者反馈 no，或者等待超时后协调者尚无法收到所有参与者的反馈，即中断事务
      • 发送中断请求：如果协调者处于工作状态，向所有参与者发出 abort 请求
      • 事务回滚：参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
      • 反馈结果：参与者完成事务回滚之后，向协调者反馈ACK消息。
      • 中断事务：协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

  • 3PC优缺点：

    • 与2PC相比，3PC降低了阻塞范围，并且在等待超时后，协调者或参与者会中断事务，避免了协调者单点问题，阶段三中协调者出现问题时，参与者会继续提交事务。
    • 数据不一致问题依然存在，当在参与者收到 preCommit 请求后等待 doCommit 指令时，此时如果协调者请求中断事务，而协调者因为网络问题无法与参与者正常通信，会导致参与者继续提交事务，造成数据不一致。
    • 【2PC和3PC都无法保证数据绝对的一致性，一般为了预防这种问题，可以添加一个报警，比如监控到事务异常的时候，通过脚本自动补偿差异的信息】

TCC:

  • TCC（Try Confirm Cancel）:是应用层的两阶段提交，所以对代码的侵入性强，其核心思想是：针对每个操作，都要实现对应的确认和补偿操作，也就是业务逻辑的每个分支都需要实现 try、confirm、cancel 三个操作，第一阶段由业务代码编排来调用Try接口进行资源预留，当所有参与者的 Try 接口都成功了，事务协调者提交事务，并调用参与者的 confirm 接口真正提交业务操作，否则调用每个参与者的 cancel 接口回滚事务，并且由于 confirm 或者 cancel 有可能会重试，因此对应的部分需要支持幂等。

    • 第一阶段：Tay，业务系统进行检测并且预留资源（加锁等），比如下单阶段会锁库存。
    • 第二阶段，根据一阶段结果决定confirm 还是cancel ，conform的话执行业务并释放锁，cancel释放try预留的资源（锁）。

  • TCC如何保证最终一致：

    • 在Try阶段，因为在业务逻辑实现，保障最好，即使失败也可以进行cancel操作。
    • 定义为重要开始进行confirm操作，confirm一定成功。
    • 如果执行失败，TCC进行重试补偿。
    • 存在极低概率在CC环节失败，可能需要定时任务或人工介入。

  • TCC注意事项：

    • 允许空回滚：可能由于try超时或丢包，导致二阶段回滚，触发cancel操作，此时事务参与者未收到try但是收到cancel，即使没有发现对应事务主键xid，也要返回回滚成功。
    • 防悬挂：网络原因导致cancel比一阶段try先执行（try超时导致事务管理器触发回滚，执行cancel）但是此时收到try操作，此时空回滚成功，但是会记录该事务的xid或业务主键，try检测到会放弃执行。
    • 幂等：由于网络或重试导致TCC重复执行，所以需要进行幂等控制。

  • TCC优缺点：

    • 性能提升：性能提升了，锁粒度变小，不会锁整体资源。
    • 数据最终一致性：基于CC的幂等，保证数据最终完成确认或取消。
    • 可靠性：解决XA协议单点故障问题，由业务发起方控制业务，业务活动器也变成多点。
    • 缺点：TCC与业务耦合高，提升开发成本。

Saga：

  • Saga：Saga 事务核心思想是将长事务拆分为多个本地短事务并依次正常提交，如果所有短事务均执行成功，那么分布式事务提交；如果出现某个参与者执行本地事务失败，则由 Saga 事务协调器协调根据相反顺序调用补偿操作，回滚已提交的参与者，使分布式事务回到最初始的状态。

    • 每个 Saga 事务由一系列幂等的有序子事务(sub-transaction) Ti 组成。
    • 每个 Ti 都有对应的幂等补偿动作 Ci，补偿动作用于撤销 Ti 造成的结果。

本地消息表：

  • 本地消息表：本地消息表的核心思路就是将分布式事务拆分成本地事务进行处理，在该方案中主要有两种角色：事务主动方和事务被动方。事务主动发起方需要额外新建事务消息表，并在本地事务中完成业务处理和记录事务消息，并轮询事务消息表的数据发送事务消息，事务被动方基于消息中间件消费事务消息表中的事务。

    • 避免消息不一致：1）业务处理成功，事务消息发送失败；2）业务处理失败，事务消息发送成功
幂等性：

同一个接口，多次发出同一个请求，请求的结果是一致的。（幂等和防重有些不同，防重强调的防止数据重复，幂等强调的是多次调用如一次，防重包含幂等）

怎么解决：

  • RequestId或版本号：insert前先select在保存数据的接口中，在insert前，先根据requestId等字段先select一下数据。如果该数据已存在，则直接返回，如果不存在，才执行 insert操作。【使用了乐观锁，更新操作必须都更新】
  • 唯一索引：加唯一索引是个非常简单但很有效的办法，如果重复插入数据的话，就会抛出异常，为了保证幂等性，一般需要捕获这个异常。如果是java程序需要捕获：DuplicateKeyException异常，如果使用了spring框架还需要捕获：MySQLIntegrityConstraintViolationException异常。
  • 悲观锁：可以加悲观锁，把对应用户的哪一行数据锁住。同一时刻只允许一个请求获得锁，其他请求则等待。（对于数据库for update）【这种方式有一个缺点，获取不到锁的请求一般只能报失败，比较难保证接口返回相同值。】
  • 分布式锁：数据库加锁可能有性能问题，可以使用分布式锁。
限流算法：
  1. 计数器（Counter）算法
  • 原理：计数器是最简单的限流算法之一。它通过设定一个时间窗口内的最大请求数来限制流量。每当有请求到来时，检查当前计数是否已达到设定的最大值，若未达到则允许请求并增加计数；反之则拒绝请求。

  • 实现思路：

    • 设置一个固定大小的时间窗口和该窗口内允许的最大请求数。
    • 每当收到请求时，增加计数器。
    • 如果计数超过设定的阈值，则拒绝请求。
    • 时间窗口结束后重置计数器。
  • 优点：简单易实现。
  • 缺点：存在临界问题，即在两个相邻的时间窗口交界处可能会出现短时间内接受过多请求的情况。
  1. 漏桶（Leaky Bucket）算法
  • 原理：漏桶算法将请求看作水滴进入一个固定容量的桶中，桶底部有一个小孔以恒定速度漏水。如果流入的速度超过了流出的速度，桶会满溢，多余的请求将被丢弃。

  • 实现思路：

    • 设定一个队列作为“桶”，用来存储请求。
    • 新来的请求首先加入到队列中。
    • 按照固定的速率从队列中取出请求进行处理。
    • 如果队列满了，则新的请求会被直接拒绝或排队等待。
  • 优点：能够平滑突发流量，确保输出的请求速率稳定。
  • 缺点：不能完全利用系统的处理能力，因为在高峰期可能会有很多请求被延迟或丢弃。
  1. 令牌桶（Token Bucket）算法
  • 原理：令牌桶算法是基于令牌生成与消耗的概念。系统按照一定的速率向桶中添加令牌，每个请求需要消耗一个令牌才能被处理。如果桶为空，则新的请求必须等待直到有足够的令牌可用。

  • 实现思路：

    • 定义一个固定大小的桶和令牌生成速率。
    • 每隔一定时间向桶中添加一定数量的令牌（不超过桶的容量）。
    • 当请求到达时，先尝试获取一个令牌，成功后才执行请求；如果没有令牌，则拒绝请求或让请求等待。
  • 优点：既能应对突发流量，又能保证长期平均速率不超过设定值。
  • 缺点：实现相对复杂一些。
  1. 固定窗口（Fixed Window）与滑动窗口（Sliding Window）算法
  • 固定窗口：类似于计数器算法，但在每个固定大小的时间窗口内重新计算请求数量。
  • 滑动窗口：改进了固定窗口的问题，通过使用两个时间窗口的组合来更精确地控制速率，从而解决了临界点的问题。

  • 实现思路（滑动窗口为例）：

    • 将时间划分为多个小窗口，并记录每个小窗口内的请求数。
    • 当新请求到来时，更新最近一个小窗口的计数。
    • 根据所有相关小窗口的总请求数判断是否允许新请求。
  • 优点：滑动窗口能更好地处理临界情况下的流量波动。
  • 缺点：实现较为复杂，尤其是随着窗口细分程度增加时。
Raft算法：

Raft 是一个 一致性算法，和 Paxos 目标相同。但它还有另一个名字 - 易于理解的一致性算法。Paxos 和 Raft 都是为了实现 一致性 产生的。这个过程如同选举一样，参选者 需要说服 大多数选民 (Server) 投票给他，一旦选定后就跟随其操作。Paxos 和 Raft 的区别在于选举的 具体过程 不同。

  • 角色划分：Raft将系统中的每个节点分配为三种角色之一：

    • Leader（领导者）：处理所有客户端请求，并负责将日志复制到其他节点。
    • Follower（跟随者）：被动地接受来自Leader的日志条目或投票请求。
    • Candidate（候选人）：在选举期间尝试成为新的Leader。

初始状态下，所有节点都是Follower。如果一段时间内没有收到Leader的心跳信号（即超时），其中一个Follower会转变为Candidate并发起一次选举。

  • 领导选举

    • 当一个Follower在选举超时时间内未接收到Leader的心跳信号时，它会转换为Candidate状态，增加自己的任期号，并为自己投票，然后向集群中的其他节点发送请求投票的RPC。
    • 如果一个Candidate获得了大多数节点的投票（包括自己），它就会成为新的Leader。
    • 如果多个Candidates同时竞选导致票数分散，没有任何一个获得多数票，则等待下一个选举超时周期重新开始选举过程。

  • 日志复制：一旦选出Leader后，它就开始接收来自客户端的请求。每个请求都包含一条需要执行的命令。Leader首先将这条命令追加到自己的日志中，然后通过AppendEntries RPC将该日志条目复制给其他Follower节点。

    • Follower成功复制了日志条目后，会回复确认信息给Leader。
    • Leader收到大多数节点的成功响应后，应用这条日志条目到它的状态机，并指示Follower也这样做。

  • 安全性

    • Leader完整性：如果某个日志条目已经在特定任期中被提交，则后续的所有Leader必须包含该日志条目。
    • 只允许Leader写入：只有Leader可以处理客户端请求并将新条目添加到日志中。
    • 任期检查：每个RPC消息都包含了发送者的当前任期号。如果接收者发现对方的任期号更大，则会立即转换角色（例如从Leader变为Follower）。
paxos算法：

Paxos算法是莱斯利·兰伯特（Leslie Lamport）提出的一种基于消息传递的一致性算法，用于解决分布式系统中如何就某个值达成一致的问题。它是许多现代分布式系统的基石，Paxos 有点类似前面说的 2PC，3PC，但比这两种算法更加完善。在很多大厂都得到了工程实践，比如阿里的 OceanBase 的 分布式数据库， Google 的 chubby 分布式锁 。

Paxos算法的核心概念

Paxos算法主要由以下几个部分组成：Proposer（提议者）、Acceptor（接受者）、和Learner（学习者）。它们共同工作以确保在分布式环境中即使面对节点故障或网络分区的情况下也能达成一致。

  1. 基本流程

  • 阶段一：Prepare请求

    • Proposer选择一个提案编号N，然后向大多数Acceptor发送Prepare请求。
    • 如果Acceptor收到的Prepare请求中的提案编号N大于之前接收的所有提案编号，则Acceptor作出承诺不再接受任何小于N的提案，并回复自己已经接受过的最大编号的提案（如果有的话）。否则忽略该请求。

  • 阶段二：Accept请求

    • 如果Proposer从大多数Acceptor那里收到了对Prepare请求的响应，它就可以发送Accept请求给这些Acceptor。这个请求包含了最初提出的值以及在Prepare阶段确定的提案编号N。如果在这个过程中没有发现已经有被接受的提案，那么Proposer可以自由选择自己的值；如果有，则必须选择Acceptor已经接受的最大编号提案中的值。
    • Acceptor收到Accept请求后，如果确认提案编号N没有变化（即没有接收到更大编号的Prepare请求），则接受该提案。

  • 阶段三：Learn

    • 当一个提案被大多数Acceptor接受后，Learner可以被告知该提案已被接受，并将其作为最终决定值。
  1. 确保一致性的关键点
  • 唯一性：在一个Paxos实例中，只能有一个值被选定。这通过要求Acceptor只接受具有最高提案编号的提案来保证。
  • 安全性：一旦一个值被选定，后续所有的提案都必须接受这个值。这意味着一旦一个值被大多数Acceptor接受，之后任何成功的提案都必须包含这个值。
  • 活跃性：在没有故障的情况下，系统能够继续进行决策过程并最终选定一个值。
  1. 多Paxos与优化

原始的Paxos算法适用于单次决策，而在实际应用中往往需要持续地做出一系列决策，这就引出了Multi-Paxos的概念。Multi-Paxos允许在一个Paxos实例上连续执行多个Paxos算法实例，从而支持一系列决策。为了提高效率，通常会引入Leader角色，让一个固定的Proposer负责提交所有提案，减少Prepare阶段的开销。

此外，还有多种针对特定问题场景下的Paxos变种和优化方案，例如Fast Paxos、Cheap Paxos等，旨在进一步提高性能或降低复杂度。

总之，虽然Paxos算法在理论上提供了一种强大的工具来处理分布式环境下的共识问题，但由于其实现细节较为复杂，实践中常采用更易理解和实现的Raft等算法作为替代。

添加新评论

Copyright © 2025 io2020
Powered by Typecho | Theme by Waxy