分布式——分布式一致性算法（共识算法）

发布于：2025-06-20 ⋅ 阅读:(17) ⋅ 点赞:(0)

文章目录

Paxos算法详解

Paxos算法是分布式计算领域最重要的算法之一，由Leslie Lamport在1990年提出，用于解决分布式系统中的一致性问题。它是许多现代分布式系统的基础。

1. Paxos算法背景

1.1 分布式一致性问题

在分布式系统中，多个节点需要就某个值达成一致，即使存在节点故障或网络分区。Paxos提供了一种在不可靠环境中实现可靠共识的方法。

1.2 基本假设

Paxos基于以下假设：

  • 异步非拜占庭模型：节点可能失效但不会恶意响应
  • 消息可能丢失、重复或延迟，但不会被篡改
  • 大多数节点(>N/2)可用时能达成共识

2. Paxos核心概念

2.1 三种角色

  1. Proposer：提出提案(proposal)的节点
  2. Acceptor：对提案进行投票表决的节点
  3. Learner：学习已确定的值的节点

实际实现中，一个节点可能同时扮演多种角色。

2.2 提案(Proposal)

每个提案包含：

  • 提案编号(n)：全局唯一且递增的数字
  • 提案值(v)：需要达成一致的实际数据

2.3 两阶段协议

Paxos分为两个主要阶段：

  1. Prepare阶段：获取提案权，了解已接受的提案
  2. Accept阶段：尝试让提案被多数派接受

3. Paxos算法流程

3.1 Prepare阶段

  1. Proposer选择一个全局唯一的提案编号n，向多数派Acceptor发送Prepare请求
  2. Acceptor收到Prepare(n)后：
    • 如果n > 它已响应的任何Prepare请求编号
      • 承诺不再接受编号小于n的提案
      • 返回它已接受的最高编号提案(如果有)
    • 否则拒绝请求

3.2 Accept阶段

  1. 如果Proposer收到多数派Acceptor对Prepare(n)的响应：

    • 如果任何Acceptor返回了已接受的提案，选择其中编号最大的提案值作为v
    • 否则Proposer可以自由选择自己的值v
    • 向Acceptor发送Accept(n, v)请求

  2. Acceptor收到Accept(n, v)后：

    • 如果没有承诺过不接受n(即没有响应过更高编号的Prepare)
      • 接受该提案(n, v)
      • 返回接受确认
    • 否则拒绝

  3. 如果Proposer收到多数派Acceptor的接受确认，则值v被选定(chosen)

3.3 Learner学习已选定的值

一旦提案被多数派接受，Learner可以通过以下方式学习该值：

  • Acceptor在接受提案后通知所有Learner
  • 或Learner定期查询Acceptor

4. Paxos关键特性

4.1 安全性(Safety)

  • 唯一性：最多只有一个值被选定
  • 有效性：只有被提出的值才可能被选定
  • 一致性：一旦值被选定，后续所有选定的都是同一个值

4.2 活性(Liveness)

只要多数派节点存活且消息最终可达，最终会选定一个值。

4.3 容错能力

Paxos可以容忍：

  • 消息丢失
  • 节点失效(只要不超过半数)
  • 网络分区(只要多数派可达)

5. 完整案例：会议室预定系统

假设有5个Acceptor(A1-A5)，需要确定明天的会议室使用时间。

场景1：正常情况（无冲突）

  1. Proposer P1提出Prepare(n=1):

    • 发送Prepare(1)给A1,A2,A3（多数派）
    • Acceptor们（之前没响应过任何Prepare）：
      • 承诺不再接受编号<1的提案
      • 返回"无已接受提案"（因为它们是第一次参与）

  2. P1收到多数派(A1,A2,A3)响应：

    • 发现所有Acceptor都返回空值
    • 自由选择自己的值v=“14:00-15:00”
    • 发送Accept(1, “14:00-15:00”)

  3. Acceptor收到Accept(1, “14:00-15:00”)：

    • 检查自己的承诺（只承诺拒绝编号<1的提案）
    • 接受该提案，并返回确认

  4. P1收到多数派确认：

    • 值"14:00-15:00"被选定(chosen)
    • 系统确定明天会议室使用时间为14:00-15:00
场景2：有冲突但保证一致性

假设在P1进行过程中，Proposer P2同时发起提案：

  1. P2提出Prepare(n=2)（注意n=2 > n=1）：

    • 发送给A3,A4,A5
    • A3已经接受了(1, “14:00-15:00”)，所以返回该信息
    • A4,A5未接受过提案，返回空

  2. P2收到响应：

    • 发现A3返回了已接受的(1, “14:00-15:00”)
    • 必须选择这个值（因为这是最高编号的已接受提案）
    • 发送Accept(2, “14:00-15:00”)

  3. Acceptor收到Accept(2, “14:00-15:00”)：

    • A3,A4,A5检查自己的承诺：
      • A3之前承诺过拒绝编号<2的提案，但当前是2，所以接受
      • A4,A5未承诺过更高编号，接受
    • 即使A1,A2之前接受了n=1的提案，现在多数派(A3,A4,A5)接受了n=2的相同值

  4. 结果：

    • 值仍然是"14:00-15:00"（一致性保持）
    • 高编号提案(2)覆盖了低编号提案(1)，但值不变
场景3：部分接受后的恢复

假设网络出现问题：

  1. **P1发送Accept(1, “14:00-15:00”)**只到达A1,A2（未形成多数派）

    • A1,A2接受了该提案
    • 但P1未收到足够确认，认为失败

  2. P2发起Prepare(n=2)：

    • 发送给A3,A4,A5
    • A3返回空，A4,A5未响应（网络问题）
    • 只收到A3的响应（未形成多数派），失败

  3. P1重试Prepare(n=3)：

    • 发送给A2,A3,A4
    • A2已接受(1, “14:00-15:00”)，返回该信息
    • A3,A4返回空
    • P1发现A2返回了值，必须选择"14:00-15:00"
    • 发送Accept(3, “14:00-15:00”)

  4. Acceptor行为：

    • A2,A3,A4接受该提案（n=3 > 它们之前的承诺）
    • 现在多数派接受了"14:00-15:00"（A1,A2,A3,A4中任意三个）

  5. 结果：

    • 即使中间有失败，最终仍选定"14:00-15:00"
    • 所有更高编号的提案都会继承这个值

关键规则总结：

  1. 编号全序性：高编号提案可以覆盖低编号提案，但必须尊重已接受的值
  2. 值传递规则：如果Acceptor返回了已接受的值，Proposer必须使用它（保证一致性）
  3. 多数派原则：
    • Prepare阶段和Accept阶段都需要多数派响应
    • 确保任何两个多数派必有交集，该交集Acceptor会传递历史信息

为什么这种设计能工作？

  • 安全性：通过强制高编号提案继承已接受的值，确保一旦值被多数派接受，就不会被改变
  • 活性：只要有一个Proposer能成功与多数派通信，最终会达成一致
  • 容错：允许部分节点失败或消息丢失（只要多数派存活）

这种设计虽然看起来复杂，但它是分布式系统在不可靠环境下实现一致性的最优方法之一。

RAFT算法

Raft 不仅仅是一个选主算法，而是一个完整的共识算法，其中领导者选举只是它的一个重要组成部分。Raft 的核心目标是管理分布式日志复制，确保多个节点在不可靠的网络环境中达成一致的数据状态。

Raft 的三大核心机制

Raft 将共识问题分解为三个相对独立的子问题：

1. Leader Election（领导者选举）

  • 作用：确保集群在任一时刻最多只有一个 Leader，避免"脑裂"（Split Brain）。
  • 触发条件：
    • Follower 在 选举超时（Election Timeout）（通常 150-300ms）内未收到 Leader 的心跳，就会变成 Candidate 并发起选举。
  • 投票规则：
    • 每个节点每个任期（Term）只能投一票。
    • Candidate 必须获得**多数派（>N/2）**的投票才能成为 Leader。
  • 防止选举冲突：
    • 随机化选举超时：不同节点的超时时间不同，减少多个 Candidate 同时竞选的概率。
    • 任期号（Term）递增：保证新 Leader 的 Term 一定比旧 Leader 高。

✅ Raft 的选主只是手段，目的是让集群快速恢复可用性。

2. Log Replication（日志复制）

  • 作用：Leader 负责接收客户端请求，并将操作日志复制到所有 Follower，确保数据一致性。
  • 流程：
    1. 客户端发送写请求到 Leader。
    2. Leader 将操作追加到自己的日志（未提交）。
    3. Leader 通过 AppendEntries RPC 发送日志给所有 Follower。
    4. 收到多数派（>N/2）确认后，Leader 提交（Commit） 该日志（应用到状态机）。
    5. Leader 通知所有 Follower 提交日志。
    6. 返回成功响应给客户端。
  • 日志匹配特性：
    • 如果两个日志条目有相同的 index 和 term，那么它们存储的命令一定相同。
    • 如果某个日志条目已提交，那么它之前的所有日志条目也一定已提交。

✅ Raft 的核心是日志复制，选主只是为了保证日志复制的正确性。

3. Safety（安全性）

  • 作用：确保系统在 Leader 切换、网络分区等情况下仍然保持一致性。
  • 关键规则：
    • 选举限制（Election Restriction）：
      • 只有拥有最新日志的节点才能成为 Leader（防止数据丢失）。
      • 投票时，Follower 会检查 Candidate 的日志是否比自己新（通过 lastLogIndex 和 lastLogTerm）。
    • 提交规则（Commit Rule）：
      • Leader 只能提交当前任期（Term）的日志，不能直接提交旧任期的日志（避免"已提交日志被覆盖"的问题）。

✅ Raft 的安全性机制保证了即使发生 Leader 切换，数据也不会丢失或冲突。

Raft vs. 纯选主算法

对比项 Raft 纯选主算法（如 Bully 算法）
目标 管理分布式日志，保证强一致性 仅选举 Leader，不涉及数据同步
数据一致性 严格保证（日志复制 + 安全性机制） 不保证
适用场景 分布式数据库（etcd、TiDB） 简单的主从切换（如 MySQL 主从）
复杂度 较高（需处理日志、任期、提交等） 较低（仅选举）

总结：Raft 不仅仅是选主

  1. 选主（Leader Election）：只是 Raft 的一个阶段，目的是快速恢复集群可用性。
  2. 日志复制（Log Replication）：Raft 的核心，确保数据在多个节点间一致。
  3. 安全性（Safety）：保证即使发生故障切换，数据也不会丢失或错误。

Raft 是一个完整的共识算法，选主只是它的一部分。类似 Paxos，它的最终目标是让分布式系统在部分节点故障时仍能安全、一致地运行。

常见的 使用Paxos或类似共识算法 的中间件和系统

1. 分布式键值存储 & 配置管理

(1) Google Chubby

  • 用途：分布式锁服务，类似 ZooKeeper
  • 算法：Paxos
  • 特点：Google 内部使用，为 BigTable、GFS 提供协调服务

(2) ZooKeeper

  • 用途：分布式协调服务（配置管理、Leader选举、分布式锁）
  • 算法：ZAB（ZooKeeper Atomic Broadcast，类似 Multi-Paxos）
  • 特点：Hadoop、Kafka 等依赖它做集群管理

(3) etcd

  • 用途：分布式键值存储，Kubernetes 的默认存储后端
  • 算法：Raft（Paxos 的简化版）
  • 特点：强一致性，用于服务发现、配置存储

(4) Consul

  • 用途：服务发现、健康检查、KV存储
  • 算法：Raft（一致性部分）
  • 特点：支持多数据中心

2. 分布式数据库

(5) Google Spanner

  • 用途：全球分布式数据库
  • 算法：Paxos（跨数据中心同步） + TrueTime（全局时钟）
  • 特点：强一致性，支持全球部署

(6) CockroachDB

  • 用途：分布式 SQL 数据库（兼容 PostgreSQL）
  • 算法：Raft（每个数据分片使用 Raft 共识）
  • 特点：高可用，自动分片

(7) TiDB

  • 用途：分布式 NewSQL 数据库（兼容 MySQL）
  • 算法：Raft（存储层 TiKV 使用 Raft）
  • 特点：HTAP（混合事务分析处理）

(8) Amazon DynamoDB

  • 用途：NoSQL 数据库
  • 算法：Paxos（用于跨区域复制）
  • 特点：低延迟，可扩展

3. 消息队列 & 流处理

(9) Apache Kafka

  • 用途：分布式消息队列
  • 算法：ZooKeeper（旧版 Leader 选举）→ KRaft（Kafka 自研 Raft 实现，取代 ZooKeeper）
  • 特点：高吞吐，持久化日志

(10) Apache Pulsar

  • 用途：分布式 Pub-Sub 消息系统
  • 算法：ZooKeeper（元数据管理） + BookKeeper（日志存储，使用 Raft）
  • 特点：支持多租户，低延迟

4. 分布式计算 & 存储

(11) Google File System (GFS)

  • 用途：分布式文件存储
  • 算法：Paxos（用于 Master 节点选举）
  • 特点：BigTable 的底层存储

(12) Apache Hadoop HDFS

  • 用途：分布式文件系统
  • 算法：ZooKeeper（用于 NameNode HA）
  • 特点：大数据存储基础

5. 其他分布式系统

(13) Kubernetes (k8s)

  • 用途：容器编排
  • 依赖：etcd（Raft 算法存储集群状态）
  • 特点：自动化部署、扩缩容

(14) Docker Swarm

  • 用途：容器集群管理
  • 算法：Raft（用于 Manager 节点选举）
  • 特点：轻量级容器编排

总结：哪些中间件用了 Paxos/Raft？

中间件 用途 共识算法
ZooKeeper 分布式协调服务 ZAB（类Paxos）
etcd 键值存储（K8s 后端） Raft
Consul 服务发现 & KV 存储 Raft
TiDB 分布式 SQL 数据库 Raft
CockroachDB 分布式 SQL 数据库 Raft
Kafka (KRaft) 消息队列（新版本） Raft
Spanner 全球分布式数据库 Paxos
Chubby 分布式锁（Google内部） Paxos

为什么 Raft 比 Paxos 更流行？

  1. 更易理解：Paxos 论文晦涩难懂，Raft 设计更直观。
  2. 工程友好：Raft 有清晰的 Leader 选举和日志复制流程，易于实现。
  3. 广泛应用：etcd、Consul、TiDB 等主流中间件都选择 Raft。

结论

  • Paxos：Google 内部系统（Chubby、Spanner）使用较多。
  • Raft：开源生态主流选择（etcd、TiDB、Kafka KRaft）。
  • 你的电商系统：通常直接使用 etcd/ZooKeeper/MySQL Cluster，而不会自己实现 Paxos。

如果你的系统需要强一致性，建议直接使用现成的 Raft-based 中间件（如 etcd），而不是从头实现 Paxos。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布