分布式系统 · 协调与协定（XMU Curriculum）

本章为「2024 春季课程」分布式系统的部分重要内容，仅作归纳，便于理清框架。

✅ L6-时间同步与全局状态

  • 时钟同步
    • 物理时钟同步问题（机器本地时间）
      • NTP 网络时间协议：使用中心化的全局时间同步来保证各节点的时间统一
      • Berkeley 算法：服务器主动定期询问每台机器的时间，服务器基于客户的回答计算出平均值，告知它们拨快或者拨慢时间 —— 主动式服务（与 Cristian 算法中的被动式时间服务器相反）
      • Cristian 算法：一台机器设为时间服务器，其他的每台机器周期性地向时间服务器发送请求消息以获得当前标准时间
    • 逻辑时钟（时钟的内部一致性）
      • Lamport 算法：为了同步逻辑时钟，Lamport 定义了一个二元 关系，称作“先发生”的关系…
  • 全局状态
    • 全局一致性快照
    • Chandy-Lamport 算法：引入「分布式快照」概念
      • Initiating a snapshot
      • Propagating a snapshot
      • Terminating a snapshot

✅ L7-协调与协定

  • 分布式互斥 Ricart-Agrawala 算法

  • 选举算法

    • Bully

  • 拜占庭与共识问题

    • 拜占庭
    • 共识算法
      • Paxos
      • Raft

✅ L8-并发控制与分布式事务

  • 原子事务
    • ACID 特性
    • 事务实现
      • 私有工作空间与影子更新
      • 写前日志
    • 分为单层事务、嵌套事务、分布式事务
  • 并发控制：当多个事务在不同的进程（在不同的处理机上）中同时执行时，需要一些机制以保证它们互不干扰，这种机制称为并发控制算法
    • 两阶段封锁协议（2PL）：恰好在需要或不再需要锁时去请求或释放锁；可能会死锁
    • 乐观的并发控制：做自己想做的，有问题出现再说（避免了死锁，允许最大的并行度；有时可能会失效，这时所有的事务都必须退回重新运行一遍）
    • 时间戳：每个文件带有对它操作的最后一个提交事务的读时间戳、写时间戳
  • 分布式事务
    • CAP 理论：一致性、可用性、分区容错性
    • BASE 理论：基本可用、软状态、最终一致性
    • 分布式事务解决方案
      • CP 方式：强一致性，弱可用
      • AP 方式：高可用，但弱一致
    • 基于这两种思想，延伸出了很多分布式事务解决方案（2PC、3PC、TCC 等）
      • 两阶段提交协议（2PC）
        • 准备阶段 Prepare：取得一致决定
        • 执行阶段 Commit/Rollback：执行命令（提交或废弃）
      • 三阶段提交协议（3PC）：在协调者和参与者中都引入超时机制，并且把两阶段提交协议的第一个阶段分成了两步
        • CanCommit：与 2PC 的 Prepare 阶段类似
        • PreCommit：协调者将通知事务参与者准备提交或取消事务，写本地的 redo 和 undo 日志，但不提交
        • DoCommit：提交或回滚，如果无法及时收到来自协调者的信息之后，他会默认执行提交，不会一直锁定资源处于阻塞状态
      • TCC：解决 2PC 中的资源锁定和阻塞问题，减少资源锁定时间
        • Try：资源的检测和预留
        • Confirm：执行的业务操作提交，要求 Try 成功，Confirm 一定要成功
        • Cancel：预留资源释放

1. 分布式互斥

1.1 集中式算法（仿照单机）

选一个进程作为协调者，进程若要进入临界区，它向协调者发送请求消息，协调者负责处理

  • 优点: 易实现、通信量少 (请求-许可-释放)
  • 缺点: 单点故障、瓶颈、无法辨认服务器崩溃

1.2 分布式互斥算法（Ricart-Agrawala 算法）

Lamport 提出了一种分布式互斥算法，Ricart 等对它作了进一步的改进。

  • 步骤 1：当一个进程想进入一个临界区时 ，它构造一个消息，其中包含它要进入的 <临界区的名字、它的进程号、当前时间>，然后它将该消息发送给所有其他的进程。

  • 步骤 2：当一个进程接收到来自另一个进程的请求消息时，它根据自己与消息中的临界区相关的状态来决定它要采取的动作。

    • 若接收者不在临界区也不想进入临界区，它就向发送者发送一个 ok 消息

    • 若接收者已经在临界区中，它不进行应答，而是将该请求放入队列中

    • 如果接收者想进入临界区但尚未进入时，它将对收到的消息的时间戳与包含在它发送给其余进程的消息中的时间戳（本身的时间戳）进行比较，时间戳最早的那个进程获胜。如果收到的消息的时间戳比较早，那么接收者向发送者发回一个 ok 消息。如 果它本身的时间戳比较早，那么接收者将收到的请求放入队列中，并且不发送任何消息

  • 步骤 3：在发送了请求进入临界区的请求消息后，进程进行等待，直到其他所有进程都发回了允许进入消息为止，一旦请求进程得到了所有进程的允许，它就可以进入临界区了。

  • 步骤 4：当它退出临界区时，它向其队列中的所有进程发送 ok 消息，并将它们从队列中删除。

缺点：

  • n 点失败
  • n 点瓶颈
  • 2(n-1) 个消息

改进方案：

  • 超时重发
  • 组通信
  • 简单多数同意

1.3 令牌环算法

进程没有固定顺序，可以用软件的方法构造出一个逻辑环，环中为每个进程都分配了一个位置（如按网络地址），不管按什么方式分配，每个进程要知道谁在它的下一个位置上。进程从它邻近的进程得到令牌后，检查自己是否要进入临界区。如果自己要进入临界区，那么它就进入临界区，做它要做的工作，然后离开临界区。在该进程退出临界区后，它沿着环继续传递令牌。

2. 选举算法

许多分布式算法需要一个进程充当协调者，发起者，排序者或其他特定的角色。

2.1 欺负算法（Bully）

当一个进程 P 发现协调者不再响应请求时，它发起选举。进程 P 选举过程如下

  • P 向所有号码比它大的进程发送选举 (Election) 消息
  • 若无人响应，P 获胜成为协调者
  • 若有号码比它大的进程响应，响应者接管，P 的工作完成
  • 由于总是号码最大的进程取胜，因而将该算法命名为欺负算法

…

3. 拜占庭问题与共识算法

3.1 拜占庭将军

Lamport 在 1982 年发表的论文《The Byzantine Generals Problem 》描述了拜占庭将军投票问题，借以映射分布式系统中计算机通信容错问题。

Wikipedia

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

投票系统的问题在于，军队中可能存在叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。这时候在已知有成员可能不可靠的情况下，其他忠诚的将军如何在不受叛徒和间谍影响的情况下意见达成一致，这就是拜占庭将军问题。

拜占庭将军问题提供了对「分布式共识」问题的一种情景化描述：

 拜占庭将军：即分布式系统的服务节点

 忠诚的将军：即分布式系统正常的服务节点

 叛变的将军：出现故障并发送误导信息的服务节点

 信使被杀：通信故障导致信息丢失

 信使被间谍替换：服务节点进行网络通信过程中信息被黑客攻击，通信存在劫持以及信息伪造

1998 年，Lamport 发表了名为《The Part-Time Parliament 》 的论文， 这是 Paxos 算法第一次公开发发布，为网络异常情况下分布式系统如何保证数据一致性提供了一个解决思路。注意 Paxos 算法是有特定前提的，即先不考虑拜占庭将军问题（消息篡改）的情况。

《The Part-Time Parliament》中使用了大量的数学证明，考虑到大多数人理解起来比较困难，Lamport 于 2001 年发表了另一篇论文《Paxos Made Simple 》，使用了逻辑推导来论述 Paxos 算法。

…

共识理论

1. 什么是共识

「共识」是指在分布式系统中，多个节点对某个数据值或决策达成一致意见。

用数学术语来描述一下分布式系统的共识问题：在一个包含 n 个实例的分布式系统中，集合 {0,1,2,…,n−1} 表示这些实例。每个实例 i 拥有一个初始值 vi。这些实例之间可以相互通信。系通过某种算法，使得即使部分实例出现故障，系统中的所有非故障实例仍能达成一致，选择出一个不可更改的最终决定值 vf。

共识算法三个性质：

  • 终止性（Termination）：所有非故障的实例最终都会确定某一个值并终止算法执行。换句话说，算法不会无限期地执行下去，实例们都会在有限的时间内达成决议。
  • 一致性（Consistency）：所有非故障的实例最终选择的值 vf 必须是相同的。
  • 完整性（Integrity）：如果所有节点提议相同的值，那么该值一定会被最终选定为共识结果。

这些性质确保了在分布式系统中，即使面临部分节点故障或网络延迟等问题，系统仍然能够达成一个一致的决策，避免数据不一致的问题。

2. 一致性和共识

一致性：指的是在分布式系统中，多个节点在执行一系列操作后，通过遵循某些协议，确保它们对外部呈现的数据和状态保持一致。简单来说，就是确保所有节点上的数据是完全同步的，并且在某个提案（Proposal）上达成共识。

共识：指的是多个节点在分布式系统中就某个状态或决定达成一致的过程。

✅ 换句话说，一致性强调的是最终的状态是否一致，而共识则是实现这种一致性的手段。

3. 为什么要达成共识

在分布式系统中，多个节点（如服务器、进程等）共同协作来完成任务，对外感觉就像是一个单机的服务。由于是分布式的环境，一定会存在网络问题，时钟问题，以及节点故障问题，这些问题都将导致系统出现各种各样的问题，其可靠性得不到保证。比如：

  • 选主（Leader Election）：在需要一个主节点进行写操作的分布式数据库中，系统必须确保在所有节点之间达成共识，选出一个主节点。如果网络出现故障，可能会导致出现多个主节点的情况，这样会引发数据冲突和一致性问题。共识算法能够保证在这种情况下，系统能够选出唯一的主节点。
  • 原子提交（Atomic Commit）：在涉及多个节点或分区的分布式事务中，所有节点必须一致地决定是提交还是回滚事务，以保证事务的原子性。如果事务在某些节点上成功，而在其他节点上失败，系统就需要使用共识机制来确保所有节点做出统一的决定，要么全部提交，要么全部回滚。

可见，共识是分布式系统正常运转的最基本保障，只有在共识的帮助下，分布式系统才能保证一致性，像单一节点一样工作，对外提供可靠的服务。

4. 共识算法

「共识算法」也叫「一致性协议算法」，是用于在分布式系统中让多个独立的节点就某个决策或状态达成一致的一类算法。分布式系统中的每个节点都可能会因为网络分区、节点故障、延迟等问题，导致它们之间无法完全同步状态。因此，共识算法的目标是在这种不确定性和潜在的故障情况下，确保所有非故障节点最终能够就某个值或操作达成一致。

共识算法通常具备以下几个关键特性：

  • 终止性（Termination）：所有非故障的实例最终都会确定某一个值并终止算法执行。换句话说，算法不会无限期地执行下去，实例们都会在有限的时间内达成决议。
  • 一致性（Consistency）：所有非故障的实例最终选择的值 vf 必须是相同的。
  • 完整性（Integrity）：如果所有节点提议相同的值，那么该值一定会被最终选定为共识结果。

4.1 常见的共识算法

  • Paxos：一种经典的共识算法，被认为是分布式一致性问题的基础解决方案
  • Raft：一种更易于理解和实现的共识算法，解决了 Paxos 的复杂性问题
  • ZAB (ZooKeeper Atomic Broadcast protocol)：ZooKeeper 使用的原子广播协议，确保分布式系统中的状态一致性

Paxos 算法

「共识算法」本质就是「一致性算法」

相关链接：

Paxos 算法是由 Leslie Lamport 在 1990 年代提出的一种基于消息传递共识算法。在讨论分布式算法时，Paxos 几乎是一个绕不开的话题。在过去的几十年中，它已经成为分布式共识的象征，许多流行的共识算法都是基于 Paxos 进行改进的，比如 Fast Paxos、Raft、ZAB 等协议。虽然 Paxos 算法可以认为是一些共识算法的基础，但是其本身也相对较复杂，理解起来有一定的难度。

Paxos 算法包括两个主要部分：

  1. Basic Paxos 算法：分布式系统中的多个节点如何就某个数据值达成共识
  2. Multi-Paxos 算法：Multi-Paxos 是在 Basic Paxos 的基础上扩展而来，用于在分布式系统中就一系列的值达成共识

1. Basic Paxos

在正式介绍 Basic Paxos 算法之前，首先来看一个问题。

假设有一个分布式的 key-value 存储集群，有 A，B，C 三个节点，对外提供只读服务。也就是说，key-value 键值对一旦被创建，就不能再被修改。

假设此时，有两个客户端 client1 和 client2 同时发起创建键值对的请求，且创建的键值对 key 都为”Name”，client1 试图创建 “Name：张三”，client2 试图创建“Name：李四”，在这种情况下，这个分布式集群如何达成共识，实现在 A，B，C 各个节点上，Key 为”Name”的值是一致的呢。

image-20241018064712350

这里其实就需要一种共识机制，保证集群中的 A，B，C 三个节点能达成一致，每个节点写入一样的值，Paxos 算法就能保证这样一种共识。

1.1 Paxos 涉及的概念

Basic Paxos 的工作机制主要分为三个角色和两个主要阶段。

1.1.1 提案（Proposal）

提案指的是需要在多个节点之间达成一致的某个值或操作，提案是由提案编号（n）和提案的值（v）组成的，可以表示为 [n, v]。每个提案的提案编号是唯一的。

1.1.1.1 提案编号

提案编号一般不是由 Paxos 算法生成的，而是由外部传入的。所以不同的业务场景可以按照自身业务需求，自定义提案编号的生成逻辑，只需要保证提案编号全局唯一并且单调递增即可。

比如在只有一个 Proposer 的环境中可以简单地使用自增 ID 或时间戳作为提案编号。例如，使用时间戳 1693702932000。在有两个 Proposer 的环境中，可以为不同提议者分配不同的编号序列。

例如，一个提议者使用奇数（1, 3, 5…），另一个提议者使用偶数（2, 4, 6…）。在有多个 Proposer 的环境中，可以为每个 Proposer 分配一个固定的 ServerId，并将自增序号或时间戳与 ServerId 组合，生成唯一的提案编号。例如，1.1 或者 1693702932000.1 表示 Proposer1 生成的第一个提案编号。每个 Proposer 在发起 Prepare 请求后如果没有得到超半数响应时，会更新自己的提案号，再重新发起新一轮的 Prepare 请求。

1.1.1.2 提案值

在 Paxos 算法中，提案值的具体内容也是根据实际业务需求来定义的。提案值可以是数值、字符串、命令（cmd），甚至是一些操作。比如在分布式数据库的场景中，可以将数据的插入、更新、删除操作等作为提案值。这种灵活性允许 Paxos 算法适应各种不同的应用场景。

1.1.2 三个角色

在 Paxos 算法中，角色分为提议者（Proposer）、接受者（Acceptor）和学习者（Learner），它们的关系如下：

  • 提议者（Proposer）：处理客户端请求，主动发起提案（proposal）给所有的接受者（Acceptor），提议者的角色通常由集群中的某些节点担任
  • 接受者（Acceptor）：被动接受提案，对提案进行投票，并存储已经接受的值，返回投票结果给 Proposer 以及发送通知给 Learner
  • 学习者（Learner）：不参与提案和投票，只被动接收提案结果

一个节点，既可以是提议者，也可以是接受者！

image-20241018121610341

在实际的分布式业务场景中，一个服务器节点或进程可以同时扮演其中的一种或几种角色，而且在分布式环境中往往同时存在多个 Proposer、多个 Acceptor 和多个 Learner。

1.1.3 两个阶段
1.1.3.1 准备阶段（prepare）

提议者（Proposer）：生成一个唯一的提案编号 n，并向所有的接受者（Acceptor）发送一个准备请求（Prepare Request），请求内容是编号 n，注意在准备阶段请求只会包含请求编号，而不会包含提案值。

接受者（Acceptor）：在收到准备请求后，接受者（Acceptor）会做出如下承诺：

  • 如果接受者（Acceptor）收到过比此次提案编号n更大的准备请求，将丢弃这次准备请求，不作响应
  • 否则：
    1. 接受者（Acceptor）承诺不再通过编号小于等于 n 的提案的准备（Prepare）请求
    2. 接受者（Acceptor）承诺不再通过编号小于 n 的提案的接收（Accept）请求，也就是不再通过编号小于 n 的提案
    3. 如果接受者（Acceptor）已经通过某一提案，则承诺在准备请求的响应中返回已经通过的最大编号的提案内容，即提案值。如果没有通过任何提案，则在 prepare 请求的响应中返回空值，即尚无提案

从 prepare 流程可知：集群中的每个 Acceptor 会存储自己当前已接受（Accept）的最大提案编号和提案值。

1.1.3.2 接受阶段（accept）

提议者（Proposer）：在收到大多数接受者（Acceptor）的准备响应后，提议者将正式发起一个带有提案编号 n 和提案值 v 的接受请求 [n, v] 给所有接受者。

⚠️ 注意：这里提议者（Proposer）设置提案值 v 有一定的规则：如果在准备（prepare）请求的响应中，部分 acceptor 已经批准过的提案值，则 v 为 prepare 请求的响应中编号最大的提案值，否则可以由 proposer 任意指定。

接受者（Acceptor）：接受者（Acceptor）会根据准备阶段的响应情况作出如下承诺：

  1. 如果此时接受者没有通过编号大于 n 的准备请求，则会批准通过提案 [n, v]，并返回已通过的编号最大的提案（也就是 n）
  2. 如果此时接受者已经通过了编号大于 n 的准备请求，则会拒绝提案 [n, v]，并返回已通过的编号最大的提案（大于 n 的编号，比如 m）

提议者（Proposer）会统计收到的 accept 请求的响应，如果响应中的编号等于自己发出的编号，则认为该 acceptor 批准通过了该提案。如果存在大多数 acceptor 批准了该提案，则认为该提案已达成共识，即该提案被通过。如果没有大多数 acceptor 批准该提案，则重新回到 prepare 阶段进行协商。

需要注意的是：在准备请求中，proposer 只会发提案编号 n。而 accept 请求，proposer 会发送提案编号和提案值，也就是 [n, v]。

1.1.4 算法流程

image-20241018132934738

先明确几个变量的意思：

  • minProposal：当前 acceptor 在 prepare 请求中通过的最大提案编号
  • acceptedProposal：当前 acceptor 在 accept 请求中通过的最大提案编号
  • acceptedValue：当前 acceptor 在 accept 请求中通过的最大提案编号的提案值

Acceptor 需要持久化存储 minProposal、acceptedProposal、acceptedValue 这 3 个值

算法流程如下：

第一阶段：Prepare 阶段

  1. 为提案生成一个全局唯一且递增的提案编号 n
  2. Proposer 会向所有 Acceptor 节点发送一个包含提案编号 n 的 准备请求（Prepare(n)）
  3. 当 Acceptor 接收到准备请求（Prepare(n)）时，会将 n 与其已知的最小提案编号 minProposal 进行比较，如果 n > minProposal，则更新 minProposal 为 n，并返回其当前已经接受的提案编号 acceptedProposal 和对应的值 acceptedValue 给 Proposer，如果 n 小于或等于 minProposal，则该请求将被拒绝，不作处理
  4. Proposer 接收到大多数 （过半）Acceptor 的响应后，如果发现有 Acceptor 返回了 acceptedValue，那么 Proposer 将选择所有响应中编号最大的 acceptedProposal 对应的 acceptedValue 作为本次提案的值。
  5. 如果所有 Acceptor 都没有返回 acceptedValue，Proposer 可以自由设置本次提案的值

第二阶段：accept 阶段

  1. 在确定提案的值后，Proposer 将向所有 Acceptor 节点广播接收请求（Accept(n, value)）
  2. Acceptor 接收到 Accept(n, value) 请求后，再次比较 n 与其当前的 minProposal，如果 n >= minProposal，则 Acceptor 更新 minProposal 和 acceptedProposal 为 n，并将 value 设置为 acceptedValue，然后持久化该提案并返回确认。如果 n < minProposal，则该请求将被拒绝，并返回当前的 minProposal
  3. Proposer 接收到大多数 Acceptor 的确认后，若发现有返回值 result（minProposal） > n，表示有更新的提议，跳转到步骤 1，否则认为当前提案已经达成一致
1.1.5 最终值选定

Acceptor 在每次同意新的提案值后，会将结果同步给 Learner。Learner 通过汇总各个 Acceptor 的反馈，判断是否已获得多数同意（超过半数）。如果达成共识，即获得了多数同意，Learner 会向所有 Acceptor 和 Proposer 发送广播消息，并结束提案。在实际应用中，Learner 通常由多个节点组成，每个 Learner 都需要接收到最新的投票结果。对于 Learner 的实现，Lamport 在其论文中提供了两种方案：

  1. 主从 Learner 架构：选定一个 Learner 作为主节点，专门接收投票结果（Accepted 消息），其他 Learner 节点作为备份节点。主节点接收数据后再将其同步到其他 Learner 节点。这种方案的缺点在于可能产生单点故障问题，如果主节点宕机，将无法获取投票结果。
  2. 分布式 Learner 同步：Acceptor 同意提案后，将结果同步到所有 Learner 节点，然后每个 Learner 节点再将结果广播给其他 Learner 节点。尽管这种方式避免了单点故障，但由于涉及多次消息传递，效率相对较低。
1.1.6 算法模拟

还是以开篇的例子来进行分析，在实际应用中，通常提议者（Proposer）是集群中的某些节点，接收客户端请求，将其封装成提案（proposal）。这里为了方便演示，将 Client1 和 Client2 看作提议者，并不会影响 Paxos 算法的本质。

准备阶段（prepare）：

假设 Client1 的提案编号是 1，Client2 的提案编号是 6，Client1 和 Client2 分别向所有的接受者发送准备请求

image-20241018133708424

紧接着，节点 A 和节点 B 收先到提案者 Client1 的准备请求，编号为 1，节点 C 先收到提案者 Client2 的准备请求，提案编号为 6

image-20241018133802307

分析各个节点在接收到第一个准备请求的处理过程

  • 节点A、B：由于之前没有通过任何提案，所以节点 A 和节点 B 都将返回“尚无提案”的准备提案请求响应，并承诺，后续不再响应编号小于 1 的准备请求，也不会通过编号小于 1 的提案
  • 节点 C：由于之前没有通过任何提案，所以节点 A 和节点 B 都将返回“尚无提案”的准备提案请求响应，并承诺，后续不再响应编号小于 6 的准备请求，也不会通过编号小于 6 的提案

image-20241018133850340

接下来，节点 A 和节 B 收到提议者 Client2 发出的编号为 6 的提案，而节点 C 会收到提议者 Client1 发出的编号为 1 的提案

  • 节点 A、B：此时收到的准备请求提案编号为 6，大于之前响应的准备请求的提案编号 1，并且节点 A 和节点 B 都还未通过（accept）任何提案，所以均返回“尚无提案”的准备提案请求响应，并承诺，后续不再响应编号小于 6 的准备请求，也不会通过编号小于 6 的提案
  • 节点 C：由于节点 C 此时接收到的提案编号 1 小于之前响应的准备请求的提案编号 6，所以丢弃该准备请求，不作响应

image-20241018133944150

接收阶段（accept）：

Client1 和 Client2 收到大多数节点的准备响应之后，开始发送接收请求（accept）

  • Client1：Client1 在接收到大多数的接受者（节点 A，B）的准备响应之后，会根据响应中的提案编号最大的提案值来设置接受请求的值。由于节点 A, B 均返回“尚无提案”，即提案值为空，所以 Client1 会自己设置一个提案值“张三”，把自己的提议值 “张三”作为该提案的值，发送接受请求 [1, “张三”] 给 A, B, C 三个 acceptor
  • Client2：同理 Client2 在接收到大多数接受者的准备响应后，也会根据响应中的提案编号最大的提案的来设置接受请求的值。由于节点 A, B, C 均返回“尚无提案”，即提案值为空，所以 Client2 会自己设置一个提案值 “李四”，把自己的提议值 “李四” 作为该提案的值，发送接受请求 [6, “李四”]

image-20241018134240604

节点 A，B，C 收到 Client1 和 Client2 的接受请求之后

由前面的准备阶段响应可知，节点 A，B，C 承诺可以通过的最小提案编号为 6，而此时节点 A，B，C 接收到的 Client1 发出的接受请求为 [1, “张三”]，提案编号 1 小于承诺的提案编号 6，所以 [1, “张三”] 被拒绝，并向 Client1 返回当前 accepter 在准备请求中通过的最大提案编号 6

节点 A，B，C 收到 Client2 发出的接受请求为 [6, “李四”]，提案编号 6 不小于承诺的提案编号 6，所以提案 [6, “李四”] 被通过，节点 A，B，C 达成了共识，接收 Name 的值为 “李四”

image-20241018134338212

假设集群中还有学习者，在接受者通过了某个提案后，会通知所有学习者。一旦学习者确认多数接受者都同意了这个提案，它们也会同意并采纳提案的值。

1.1.6.1 接受者存在已通过提案的情况

在上述例子中，在准备阶段和接受阶段均不存在已通过提案的情况，准备阶段接受者的请求响应都是“尚无提案”，假设有节点已经通过了提案点又是什么场景呢？想象出这样一个场景：

假设节点 A，B 已经通过了 [6, “李四”] 提案，而节点 C 尚未通过任何提案，此时，新增一个提议者 Client3，Client3 的提案为 [8，“王五”]

Client3 向节点 A，B，C 发送提案编号为 8 的准备请求。

image-20241018135343311

节点 A 和 B 将接收 Client3 的准备请求，由于节点 A 和 B 已经通过了编号为 [6, “李四”] 的提案，所以它们在准备响应中会包含这个提案的详细信息。而节点 C 因为之前没有通过任何提案，因此它返回的是‘尚无提案’的准备响应。

image-20241018135504824

在接收到来自节点 A、B、C 的准备响应后，Client3 随即向这些节点发送接受请求。特别要注意的是，Client3 会根据响应中提案编号最大的提案值来确定接受请求的值（1.1.3.2 小节的注意事项）。由于准备响应中包含了提案 [6, “李四”]，因此 Client3 将接受请求的提案编号设为 8，提案值设置为“李四”，即客户端 3 发送的接受请求为 [8, “李四”]。

image-20241018135546912

节点 A, B, C 接收到提议者 Client3 的接受请求，由于提案编号 8 不小于三个节点承诺可以通过的最小提案编号 6，因此均通过提案 [8, “李四”]。

image-20241018135614277

1.1.7 活锁问题

先看一个例子，这里 Server1 和 Server4 既作为 Proposer，又作为 Acceptor，Server1 即 Proposer1，Server4 即 Proposer4。所有的 server 都是 acceptor。P1.1 表示 Proposer1 发起的编号为 1 的 prepare 请求，P2.4 表示 Proposer4 发起的编号为 2 的 prepare 请求，以此类推。A1.1 X 表示 Proposer1 发起的 accept 请求，提案编号为 1，提案值为 X，A2.4 Y 表示 processe4 发起的 accept 请求，提案编号为 2，提案值为 Y，以此类推。

image-20241018135658553

client1 向 server1 即 Proposer1 发起写入 X 的请求，client2 向 server4 即 Proposer4 发起写入 Y 的请求。

随着时间线从左往右看，server3 即 acceptor3 先收到 proposer1 发起的 prepare 请求 P1.1，由于没有通过任何提案，所以尚无提案，承诺不通过提案编号小于 1 的提案，随后 acceptor3 收到了 proposer4 发起的 prepare 请求 P2.4，由于此次天的编号 2 大于之前承诺的提案编号 1，所以向 proposer4 返回，承诺不再通过提案编号小于 2 的提案。

紧接着 acceptor3 收到 proposer1 发起的 accept 请求 A1.1 X，由于之前承诺了不再通过提案编号小于 2 的提案，而此次收到的 accept 提案编号为 1，所以拒绝。proposer1 发起的 accept 提案被拒绝了，所以它加大编号，又发起了 P3.1 的 prepare 请求，此次提案编号为 3，大于 acceptor3 承诺的最大提案编号 2，所以做出响应，回应承诺不再通过提案编号小于 3 的提案，随后 proposer4 发来 accept 请求 A2.4 Y，此时由于提案编号为 2，小于 acceptor3 刚刚承诺的最大提案编号 3，所以这个 accept 请求也会被决绝。proposer4 又加大 prepare 的提案编号，如此循环往复…..

一直通过多个 Proposer 的 prepare 请求，但是不能通过 accept 请求，导致一直没有提案通过，这样就形成了活锁。

1.1.7.1 活锁的定义

在多个提议者同时提出提案时，由于出现竞争，这几个提议者不断的更新提案编号，发起新的提案，导致一直没有 accept 请求被通过，导致提案一直不能通过，而陷入这样的死循环，就是活锁问题。

1.1.7.2 活锁的解决方案
  1. 随机延迟重试：当一个 Proposer（提议者）发现支持它的 Acceptor（接受者）数量小于半数时，Proposer 并不会立即更新编号并再次发起提案，而是会随机延迟一小段时间。这样做的目的是为了错开多个 Proposer 之间的冲突。
  2. 设置 Proposer 的 Leader：可以在系统中选举一个 Proposer 作为 Leader，让这个 Leader 负责发起所有的提案。其他 Proposer 不再主动提案，只在需要时响应 Leader 的请求。

2. Multi-Paxos

Basic Paxos 算法虽然能一定程度解决分布式系统的共识问题，但是存在很多的局限性：

  • 它只能对一个值形成决议
  • 提案的最终确定至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，因此性能低下
  • 当存在多个 Proposer 的时候，极端情况下甚至会形成活锁

因此 Basic Paxos 算法几乎只是用来做理论研究，并不直接应用在工程实践中。

有没有更好的算法策略能够有效解决 Basic Paxos 算法带来的这些问题呢？基于这种目的随即出现了 Multi-Paxos 算法

2.1 Multi-Paxos 算法概念

Multi-Paxos 算法其实是 Lamport 提出的一种思想，而并非具体的算法。可以认为，Multi-Paxos 算法是一类算法的总称，这类算法都基于 Multi-Paxos 思想，实现了一系列值共识。

2.2 Multi-Paxos 思想

总的来说，multi-paxos 思想基于 basic-paxos 算法做了两点改进：

2.2.1 领导者选举

在所有 Proposers 中选举出一个 Leader，让这个 Leader 唯一地提交提案（Proposal）给 Acceptors 进行表决。这样一来，就没有多个 Proposer 之间的竞争，从而解决了活锁问题。在只有一个 Leader 提交提案的情况下，Prepare 阶段可以被跳过，从而将原本的两阶段过程简化为一阶段，从而显著提高了系统的效率。

image-20241018063551863

2.2.2 优化 Basic Paxos 执行过程

准备阶段的意义在于让 Proposer 通过发送 Prepare 请求来了解各个 Acceptor 节点上已通过的提案，但有了领导者（Leader）后，只有领导者才可发送提议，领导者独自负责提出提案，所以领导者能够保证提案的最新性和唯一性。因此，领导者的提案就已经是最新的了。所以不再需要通过准备阶段来发现之前被大多数节点通过的提案。领导者可以直接跳过准备阶段，进入接受阶段（Accept Phase），从而减少不必要的通信开销和 RPC 调用次数。

3. Paxos 面试题

3.1 Prepare 与 Accept 阶段工作过程差不多，为什么需要 Prepare 过程呢，Paxos 算法在设计之初为什么不直接进行 Accept 阶段呢

因为在 basic proxos 算法中，有多个 proposer 可以发起提案，一个 acceptor 可能通过不同的 proposer 发起的提案，prepare 请求的主要作用就是获取各个 acceptor 节点上已通过的最新提案，保证最新性和唯一性。

3.2 提案编号可以怎么生成

在只有一个 Processer 的环境中可以简单地使用自增 ID 或时间戳作为提案编号。例如，使用时间戳 1693702932000。在有两个 Processer 的环境中，可以为不同提议者分配不同的编号序列。例如，一个提议者使用奇数（1, 3, 5…），另一个提议者使用偶数（2, 4, 6…）。在有多个 Processer 的环境中，可以为每个 Processer 分配一个固定的 ServerId，并将自增序号或时间戳与 ServerId 组合，生成唯一的提案编号。例如，1.1 或者 1693702932000.1 表示 Processer1 生成的第一个提案编号

3.3 Paxos 协议的活锁问题怎么解决

  1. 随机延迟重试：当 Proposer 接收到响应，发现支持它的 Acceptor 小于半数时，不立即更新编号发起重试，而是随机延迟一小段时间，来错开彼此的冲突
  2. 设置 Proposer 的 Leader：可以在系统中选举一个 Proposer 作为 Leader，让这个 Leader 负责发起所有的提案，其他 Proposer 不再主动提案，只在需要时响应 Leader 的请求，等同于 Multi-Paxos 算法
许可协议

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

分享文章
✍️ Yikun Wu 已发表了 69 篇文章 · 总计 293k 字，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

🌀 本站总访问量 次