分布式一致性协议

目录

1、核心问题

2、不同级别的一致性模型

2.1 强一致性

2.2 弱一致性

2.3 最终一致性

2.4 会话一致性

3、主要分布式一致性协议

3.1 分布式事务协议

3.1.1 两阶段提交 (2PC - Two-Phase Commit)

3.1.2 三阶段提交 (3PC - Three-Phase Commit)

3.2 共识协议

3.2.1 Paxos

3.2.2 Raft

3.2.3 ZAB（重要）

3.3 副本控制协议

3.3.1 Gossip

3.4 租约机制

3.4.1 Lease（租约）机制

1、核心问题

核心问题：复制与并发

• 复制： 为了高可用和性能，数据通常会被复制到多个节点（副本）。

• 并发： 分布式系统中，多个客户端会同时（并发地）对数据的不同副本进行读写操作。

• 网络： 节点间的通信依赖于不可靠的网络，存在延迟、丢包、分区（脑裂）等问题。

• 目标： 在复制和并发操作不可避免的情况下，如何让所有客户端（无论连接到哪个副本）看到的数据状态是符合预期的（比如，读取到的值是最新写入的，或者操作是按某种顺序发生的）。

2、不同级别的一致性模型

2.1 强一致性

• 定义： 任何读操作都能看到最近一次写操作的结果。所有节点看到的数据顺序完全一致，仿佛只有一个数据副本。

• 特点： 对用户/应用最简单，但实现代价最高（性能、可用性）。

• 实现方式： 通常需要同步复制（如两阶段提交）和严格的协调协议（如共识算法）。读操作可能被阻塞或延迟，以确保读取最新值。

• 适用场景： 银行转账、库存扣减（绝对不能超卖）、关键配置信息、分布式锁等对数据准确性要求极高的场景。

2.2 弱一致性

• 定义： 不保证读操作能看到最新的写值。系统不承诺数据何时会同步到所有副本。

• 特点： 性能最高、可用性最好（写操作完成后即可返回），但可能导致用户看到过期数据。

• 实现方式： 异步复制。写操作完成后立即返回，数据在后台传播。

• 适用场景： 网站实时访客计数、非关键的用户画像更新等，对短暂不一致容忍度高的场景。

2.3 最终一致性

• 定义： 弱一致性的一个特例和承诺。如果不再有新的写操作，经过一段时间后，所有副本最终会达到一致状态。无法保证不一致的时间窗口有多长。

• 特点： 在弱一致性和强一致性之间取得平衡。在保证最终结果正确的前提下，提供较好的性能和可用性。

• 实现方式： 异步复制 + 冲突解决机制（如向量时钟、CRDTs）。

• 适用场景： DNS、社交网络状态更新、商品评论、点赞数等。非常普遍。

• 最终一致性通常不是独立使用的，而是结合一些更具体的保证：

  • 读写一致性： 保证用户总能读到自己的写操作结果。

  • 单调读一致性： 保证用户不会看到数据“时光倒流”（不会读到比之前读到的更旧的值）。

  • 单调写一致性： 保证同一个用户的写操作在所有副本上都按该用户发出写操作的顺序执行。

  • 因果一致性： 保证有因果关系的事件（如回复评论），其顺序在所有节点上保持一致；没有因果关系的并发事件，其顺序可以不同。比最终一致性更强，比强一致性弱。

2.4 会话一致性

• 定义： 将一致性保证限定在同一个客户端会话（Session）内。通常结合读写一致性、单调读等保证，确保在一个用户会话期间看到的数据状态是相对一致的。

• 特点： 比最终一致性更强，比强一致性弱。实现相对简单（如将用户绑定到一个主副本）。

• 适用场景： 大多数 Web 应用（用户在一个会话中看到自己的操作效果是一致的）。

3、主要分布式一致性协议

3.1 分布式事务协议

用于跨多个节点（数据分片/服务）的事务，保证 ACID 中的原子性（A）和一致性（C）在分布式环境下的实现，通常指 Atomic Commit。要么所有参与进程都提交事务，要么都取消事务。

2PC与3PC并没有完全解决数据一致问题。

3.1.1 两阶段提交 (2PC - Two-Phase Commit)

• 核心思想： 引入一个协调者 (Coordinator) 来管理参与者 (Participants/Resource Managers) 的提交或中止决策。分为投票阶段和提交阶段。

• 角色： Coordinator, Participants。

• 流程：

1. 投票阶段 (Prepare Phase)：

   • Coordinator 向所有 Participant 发送 Prepare 消息（包含事务内容）。

   • Participant 执行事务操作（写 undo/redo log），但不提交。如果执行成功且准备好提交，回复 Yes (Vote-Commit)；否则回复 No (Vote-Abort)。

2. 提交阶段 (Commit Phase)：

   • 如果所有 Participant 都回复 Yes：

   • Coordinator 向所有 Participant 发送 Commit 消息。

   • Participant 收到 Commit 后，正式提交事务（释放锁，使修改永久生效），回复 Ack。

   • Coordinator 收到所有 Ack 后，完成事务。

   • 如果有任何一个 Participant 回复 No (或超时)：

   • Coordinator 向所有 Participant 发送 Abort 消息。

   • Participant 收到 Abort 后，利用 undo log 回滚事务，回复 Ack。

   • Coordinator 收到所有 Ack 后，中止事务。

• 优点： 概念简单直观。

• 缺点：

  • 同步阻塞： 参与者在 Prepare 后回复 Yes 到收到 Commit/Abort 前，会锁定资源。

  • 协调者单点故障： 如果协调者在发送 Prepare 后、Commit/Abort 前故障，参与者将一直阻塞（需要人工介入）。如果协调者在发送部分 Commit 后故障，可能导致部分参与者提交，部分未收到 Commit 而阻塞（数据不一致）。

  • 数据不一致风险： 在协调者发送 Commit 后，部分参与者提交成功，部分失败或未收到，导致不一致。

• 应用场景： 早期数据库、中间件（如 JTA），因其缺点，在现代高并发系统中较少直接使用。

3.1.2 三阶段提交 (3PC - Three-Phase Commit)

• 核心思想： 在 2PC 的投票阶段和提交阶段之间插入一个 Pre-Commit 阶段，旨在减少阻塞并解决部分协调者单点故障问题。

• 流程：

1. CanCommit Phase： Coordinator 询问参与者是否能执行事务（做初步检查）。参与者回复 Yes 或 No。

2. Pre-Commit Phase：

   • 如果所有回复 Yes： Coordinator 发送 PreCommit。参与者执行操作（写日志），但不提交，并回复 Ack。进入 DoCommit 阶段。

   • 如果有任何回复 No： Coordinator 发送 Abort。

3. DoCommit Phase：

   • 如果 Coordinator 收到所有 PreCommit 的 Ack： 发送 DoCommit。参与者提交事务，回复 Ack。

   • 如果 Coordinator 在 PreCommit 阶段超时或收到 No： 发送 Abort。

   • 参与者视角： 如果参与者在 PreCommit 后超时未收到 DoCommit/Abort，它将自行提交（基于假设：既然能到 PreCommit，说明之前都同意，协调者故障但多数派节点可能已进入 PreCommit）。

• 优点： 解决了协调者在 Commit 之前故障导致的参与者无限阻塞问题（超时后参与者可自行提交或中止）。

• 缺点：

  • 实现更复杂。

  • 网络分区下仍可能不一致： 如果协调者发送 Abort 时网络分区，部分参与者收到 Abort 中止，而另一部分在 PreCommit 后超时自行提交了。

  • 不能完全解决所有单点故障问题。

• 应用场景： 相比 2PC 有一定改进，但实际应用不如 2PC 和 Paxos/Raft 变种广泛。

3.2 共识协议

• 共识协议：分布式系统状态决策（如 Paxos、Raft）

• 崩溃容错（CFT）：容忍节点宕机（如 Raft）

目标是让一组节点就单个值达成一致（例如，谁当领导？下一个要提交的日志条目是什么？）。这是构建更复杂一致性（如状态机复制）的基础。

注意：这里的单个值，并不是狭义上的某个数，它可以是一条日志，也可以是一条命令。根据应用场景不同，单个值有不同的含义

3.2.1 Paxos

• 核心问题：在分布式系统中，多个节点需要就某个值（例如：数据库的更新顺序、配置变更）达成一致。Paxos 优先保证安全性，在故障可控时保证活性。挑战包括：

  • 网络问题：消息延迟、丢失、乱序。

  • 节点故障：节点可能崩溃（Crash）或发生拜占庭错误（Byzantine Fault）。

  • 安全性（Safety）：所有正确节点最终对同一个值达成一致。

  • 活性（Liveness）：系统最终能达成共识（可能需重试）。

• 核心角色：一个节点可兼任多个角色。

  • Proposer（提案者）：提出提案（Proposal = 提案号 + 值）。

  • Acceptor（接受者）：对提案进行投票，决定是否接受。

  • Learner（学习者）：学习已达成共识的值（不参与投票）。

• Paxos的版本有: Basic Paxos , Multi Paxos, Fast-Paxos, 具体落地有Raft 和zk的ZAB协议

• 算法流程（两阶段协议）：

  • 第一阶段：Prepare 阶段

    • Proposer 发送 Prepare 请求

      • 生成全局唯一递增的提案号 n。
      • 向所有 Acceptors 广播 Prepare(n)。

    • Acceptor 响应 Promise

      • 若 n 大于其已响应的所有提案号，则返回 Promise(n)，并附带：

        • 之前接受的最高提案号对应的值（若有）。

        • 承诺不再接受任何编号小于 n 的提案。

  • 第二阶段：Accept 阶段

    • Proposer 发送 Accept 请求
      • 若收到多数派 Acceptors 的 Promise 响应：

        • 若有 Acceptor 返回已接受的值，则选择最高提案号对应的值作为新提案值。

        • 否则，使用自己的初始值。
      • 广播 Accept(n, value)。

    • Acceptor 接受提案

      • 若收到的 n 不小于其已承诺的最小提案号，则接受该提案，并回复 Accepted(n, value)。

    • 达成共识

      • 若 Proposer 收到多数派 Acceptors 的 Accepted 响应，则值 value 被选定。

      • Learners 学习该值（通过 Proposer 或 Acceptor 广播）。

• 关键机制解析： 多数派原则保证安全性；协议本身不保证所有节点同时知道结果。

  • 提案号（Proposal Number）

    • 全局唯一且递增（如 节点ID + 时间戳），用于区分提案优先级。

  • 多数派（Quorum）

    • 任意两个多数派集合必有一个公共节点（数学基础-多数派：N/2 + 1）。

    • 确保只有一个值能被选定（避免脑裂）。

  • 值的继承

    • 若 Proposer 发现已有被接受的提案，必须继承该值（保证安全性）。

  • 故障处理

    • Proposer 故障：新 Proposer 通过更高提案号重启流程。

    • Acceptor 故障：只要多数派存活，协议仍可推进。

    • 消息丢失：Proposer 超时重试。

  • 活锁问题

    • 场景：两个 Proposer 交替提出递增提案号，相互覆盖，导致共识无法推进。

    • 解决方案：

      • 引入随机超时（如指数退避）。

      • 选举唯一的 Leader（如 Multi-Paxos）。

• 优点： 理论上精炼，是共识问题的基础解决方案。

• 缺点： 难以理解、工程实现复杂、角色划分在实现中常合并。需处理日志压缩、成员变更等（衍生出 Raft、ZAB 等算法）。活锁风险，需额外机制避免竞争。

• 应用： Google Chubby (锁服务)、Apache ZooKeeper (其 ZAB 协议受 Paxos 启发)、GoogleSpanner（全球分布式数据库，Paxos 管理副本）、TiDB（通过 Multi-Paxos 实现分布式事务）。

3.2.2 Raft

• 背景：Paxos论证过程晦涩难懂，缺少必要的实现细节，而且工程实现难度较高，所以提出了易实现、易理解的分布式一致性复制协议Raft。

• 核心思想： 将共识问题分解为更易理解的子问题：Leader 选举、日志复制、安全性。强领导制简化了流程。

  • 动画展示：

    • http://thesecretlivesofdata.com/raft/
    • https://raft.github.io/

• 节点角色：

关键机制：每个节点存储当前任期号（Term），全局单调递增（类似 Paxos 的提案号），用于检测过期信息。

• 日志结构

Index: 1 | 2 | 3 | 4  → 日志索引（连续递增）
Term:  1 | 1 | 2 | 3  → 创建该日志条目的任期号
Command: x | y | z | w → 客户端请求的操作

        特性：

        1> 日志匹配性（Log Matching）：若两条日志条目索引相同且任期相同，则内容相同，且之前所有日志相同。

        2>状态机复制：已提交（Committed）的日志被应用到所有节点的状态机（如 KV 存储）。

• 三大核心流程

  • 1. 领导人选举（Leader Election）

    • 所有节点初始为 Follower。

    • Follower 在选举超时（随机）内未收到 Leader 的心跳，则成为 Candidate。

    • Candidate 增加任期号，向所有节点发送 RequestVote RPC。

    • 节点在同一任期内只能投一票（先到先得），通常投给日志至少和自己一样新的 Candidate。

    • 获得多数票的 Candidate 成为新 Leader。

    • Leader 定期向所有 Follower 发送心跳（AppendEntries RPC，无日志时为空）以维持权威。

避免分裂投票：采用随机化选举超时（如 150ms + rand(0, 150ms)），减少多 Candidate 竞争。

2. 日志复制（Log Replication）

• 客户端请求发送给 Leader。

• Leader 将命令追加到自己的日志中（未提交）。

• Leader 在下一次心跳 (AppendEntries) 中将新日志条目发送给所有 Follower。

• Follower 将日志条目追加到本地日志（如果前一条日志匹配），回复成功。

• Leader 收到多数派 Follower 的成功回复后，认为该条目已提交（Committed），可执行命令并返回结果给客户端。

• Leader 在后续的 AppendEntries 中通知 Follower 哪些条目已提交，Follower 执行已提交的条目（应用到状态机）。

• 日志冲突处理：

  • Leader 强制覆盖 Follower 的不一致日志（通过 一致性检查 + 回溯优化）。

  • Follower 拒绝接收过时或冲突的日志条目。

3. 安全性（Safety）

• 选举限制（Election Restriction）：

  • 只有拥有最新日志的 Candidate 能成为 Leader（通过投票规则保证）。

  • 防止旧 Leader 提交的日志被覆盖（见下图示例）。

• 提交规则：

  • Leader 只能提交当前任期的日志条目（避免“已提交日志被覆盖”的边界情况）。

示例：
假设 S1（Term2 的 Leader）复制日志到多数派（索引2），但未提交即崩溃。
S5（Term3）当选 Leader 后不能直接提交 Term2 的日志，必须通过复制 Term3 的新日志间接提交。

• 关键点： 强领导简化操作；日志匹配特性保证一致性；任期号解决冲突；多数派保证。

• 优点： 比 Paxos 更易理解、工程实现友好、文档丰富。

• 缺点： 强领导可能成为瓶颈（可通过优化缓解）；依赖稳定时钟（选举超时）。

• 应用： etcd, Consul, TiKV, Redis Sentinel/Cluster (部分), Kubernetes (用于存储 etcd)。

  • etcd（Kubernetes 的后备存储）：使用 Raft 管理集群状态与配置。

  • TiKV（TiDB 的存储层）：Raft 实现多副本数据一致性。

  • Consul：服务发现与配置管理，基于 Raft 保证一致性。

3.2.3 ZAB（重要）

• 核心思想： ZooKeeper Atomic Broadcast，为 ZooKeeper 设计，结合了类似 Paxos 的核心思想和类似 Raft 的强领导模式。核心是原子广播协议，保证所有事务（写请求）以相同的顺序被所有节点交付。核心需求：

  • 原子广播（Atomic Broadcast）：所有节点以相同顺序交付消息（如创建节点、更新配置）。

  • 崩溃恢复（Crash Recovery）：故障后快速恢复一致性。

  • 高吞吐：支持数千写操作/秒（ZooKeeper 的核心场景）。

• 节点角色​​​​​​

  角色	职责
  Leader	唯一处理写请求，广播事务提案（Proposal）。
  Follower	处理读请求，转发写请求给 Leader，参与提案投票。
  Observer	仅处理读请求，不参与投票（扩展读性能）。

• 关键数据结构

  • ZXID（ZooKeeper Transaction ID）：

    • 64 位全局唯一 ID，高 32 位为任期（epoch），低 32 位为计数器（counter）。

    • 示例：0x200000001（epoch=2, counter=1）。

    • 作用：标识提案顺序，用于崩溃恢复时同步状态。

  • 提案（Proposal）：

    • 包含 ZXID、操作（如 setData）、数据内容。

  • 已提交队列（Committed Log）：

    • 所有节点按 ZXID 顺序存储已提交的提案。

• 工作流程：

  • 崩溃恢复模式（选主 + 数据同步）：当 Leader 崩溃或网络分区触发新选举时启动：

    • 选举（Fast Leader Election）：

      • 节点发起投票，携带自身最新 ZXID（lastZxid）和逻辑时钟（electionEpoch）。

      • 投票规则：优先投给 lastZxid 最大的节点（保证新 Leader 含最新数据）；若相同则投给节点 ID 最大者。

      • 快速选举：无需多轮投票，首轮即选出（避免活锁）。

    • 数据同步（Sync Process）：

      • 新 Leader 确定后，Followers 将本地 ZXID 发送给 Leader。

      • Leader 根据 Follower 的 ZXID 决定同步方式：

        • DIFF 同步：增量补发缺失的提案（最常见）。

        • TRUNC 同步：回滚 Follower 的未提交日志（防止脏数据）。

        • SNAP 同步：直接发送完整快照（日志差距过大时）。

      • 关键点：同步完成后，所有节点拥有相同的已提交日志（Committed Log）。

  • 消息广播模式（原子广播）：正常工作时，Leader 处理写请求：

    • Leader 为每个事务生成一个全局单调递增的 zxid (事务ID)。

      • 顺序性保证：同一 Leader 任期内：ZXID 严格递增保证顺序；跨任期：新 Leader 在恢复阶段同步日志时，会丢弃旧任期的未提交提案。

    • Leader 将事务作为 Proposal 发送给所有 Follower。

    • Follower 收到 Proposal 后写入本地事务日志，并回复 ACK。

    • Leader 收到多数派 Follower 的 ACK 后，发送 Commit 消息（或在下一条 Proposal 中携带已提交的 zxid）。

    • Follower 收到 Commit 后，将事务应用到内存状态机 (ZooKeeper 的 DataTree)。

• 关键点： 严格依赖 zxid 顺序；恢复模式确保新 Leader 拥有最完整日志；多数派提交。

• 优点： 高效、为 ZooKeeper 的协调服务（如锁、配置管理）量身定制。核心价值：

  • 为协调服务定制：通过原子广播 + 严格顺序性，完美匹配分布式锁、选主等场景。

  • 高效恢复机制：Fast Leader Election + 差异化数据同步，最小化故障中断时间。

  • 工业级验证：支撑了 Hadoop、Kafka 等万亿级生态系统的稳定性。

• 缺点： 主要绑定在 ZooKeeper 中使用。

• 应用： Apache ZooKeeper 的核心协议、分布式锁（如 Apache Kafka 的 Controller 选举）、配置管理、服务发现（如 Dubbo、Hadoop YARN）

  • Apache ZooKeeper 自身：服务发现（如 Kafka Broker 注册）、分布式锁（InterProcessMutex）、配置管理。

  • Apache Kafka：使用 ZooKeeper 存储元数据（Topic/Partition 信息），Controller 选举依赖 ZAB。

  • Hadoop YARN：ResourceManager 的高可用（HA）基于 ZooKeeper 的 Leader 选举。

3.3 副本控制协议

副本控制协议（Replication Control Protocol） 是确保数据在多节点间一致、可靠的核心机制。其核心目标是在故障频发（节点宕机、网络分区）的环境中，平衡数据一致性、可用性、性能三者的冲突。

主流副本控制协议分为四类：

• 强一致性协议：所有副本实现同步，读写满足线性一致性。
  • Primary-Backup（主备协议）：主节点确认所有备份写入成功后才响应客户端
  • 基于共识的复制：使用 Paxos/Raft/ZAB 等共识算法确保多数派达成一致后才提交数据。如etcd（Raft）、ZooKeeper（ZAB）、TiDB（Multi-Raft）
• 弱一致性协议：优先保障可用性和性能，允许副本间短暂不一致。
  • Gossip（流行病协议）：节点随机选择其他节点交换数据，通过多轮传播最终达到一致。如Redis Cluster（元数据同步）、Cassandra（故障检测）
• 最终一致性协议：不保证实时一致，但确保无新写入时所有副本终将一致。
  • 异步主从复制：主节点异步推送数据到从节点。比如MySQL异步复制、Redis主从复制。
• 混合型协议：按场景动态切换一致性级别。
  • Quorum复制（NRW策略）：
    • 通过定义三个变量确定策略：W（写操作需成功的副本数）+ R（读操作需查询的副本数）> N（副本总数）
    • 强一致：W = N, R = 1（同步写所有节点）

    • 弱一致：W = 1, R = 1（风险最高）

3.3.1 Gossip

• 原理：节点随机选择邻居同步数据，通过多轮传播实现最终一致。
• 流程：

  • 节点 A 携带状态信息（如版本号）。

  • A 随机选择节点 B 发送状态信息。

  • B 合并信息后继续传播。

• 关键机制：

  • 通信拓扑策略：

    • 随机选择：每轮随机选择 k 个节点（简单但可能重复选择）

    • 部分视图：每个节点维护一个固定大小的邻居列表（如 SWIM 协议）

    • 拓扑感知：优先选择同机架/可用区的节点（减少跨区域带宽）

  • 数据比对优化：

    • Merkle Tree：为数据集生成哈希树，仅同步差异子树

    • 版本向量：记录数据项的版本号，快速识别新旧数据

    • Bloom Filter：压缩表示数据集合，减少传输量

  • 收敛性保障

    • 传播轮数计算：指数扩散，期望轮数 O(log N)

    • 失效检测：若节点在T时间内未收到某邻居的消息，将其标记为疑似下线

• 优点：去中心化、高扩展性、容错性强。

• 缺点：收敛延迟（通常为 O(log N) 轮），消息冗余。

• 应用：Redis Cluster 节点状态同步、Consul 服务发现。

3.4 租约机制

3.4.1 Lease（租约）机制

• 目标：通过时效性授权解决节点状态一致性问题（非数据一致性）。
• 原理：

1. 主节点向从节点颁发租约（如 10 秒）。

2. 从节点在租约期内可执行特定操作（如提供读服务）。

3. 租约到期 ExpiryTime 前需重新申请授权。如果主节点未能在到期之前成功续约（原因可能包括：持有者宕机、网络分区、颁发者不可达、持有者进程卡死等），租约自动到期失效。颁发者可以自由地将该特权重新授予其他申请者。

• 关键点：

  • 时钟同步要求：依赖节点间时钟误差小于租约时长（通常使用 NTP 同步）。

• 应用场景：

  • 分布式锁（如 ZooKeeper 临时节点）。

  • 缓存一致性（如节点持有租约期间可直接读本地缓存）。