CAP 定理与一致性理论

CAP 定理

CAP 定理（Brewer 定理，2000年）指出分布式系统不能同时满足以下三个属性：

C（Consistency，一致性）：
  所有节点在同一时间看到相同的数据
  更精确：线性一致性（Linearizability）——操作看起来像在单个全局顺序中串行执行

A（Availability，可用性）：
  每个请求都能收到响应（不一定是最新数据），不会超时或报错

P（Partition Tolerance，分区容错性）：
  网络分区（部分节点间无法通信）时，系统仍然继续运行

为什么 P 是必然的选择

在分布式系统中，网络分区是必然会发生的（网络故障、机房断网等）
因此 P 不是"选择"，而是"必须接受的现实"

真正的选择是：网络分区发生时，牺牲 C 还是 A？

CP 系统（牺牲可用性保一致性）：
  分区期间，不可达的节点拒绝服务（返回错误）
  等待网络恢复、数据同步后再提供服务
  例：ZooKeeper、etcd、HBase、Consul（默认）

AP 系统（牺牲一致性保可用性）：
  分区期间，各节点仍然提供服务（可能返回旧数据）
  分区恢复后通过异步同步达到最终一致
  例：Eureka、Cassandra、DynamoDB、CouchDB

BASE 理论

BASE 是对 CAP 中 AP 系统的实践总结，是 ACID 的对立面：

BA（Basically Available，基本可用）：
  系统在出现故障时，允许损失部分可用性
  例：响应时间适当延长；降级展示（返回缓存数据而非最新数据）

S（Soft State，软状态）：
  系统状态可以有一段时间的不一致（中间状态）
  不同节点的数据副本在同步期间可能不一致

E（Eventual Consistency，最终一致性）：
  经过足够长的时间，所有副本会达到一致状态
  在此期间，系统可能返回不一致的数据

最终一致性的具体模式：

单调读一致性：如果读到了版本 v，后续读不会返回比 v 更旧的版本
读自己的写：自己写入的数据，自己能立即读到
会话一致性：在同一个会话（连接）内，满足读自己的写
单调写一致性：对同一节点的写操作按顺序执行

强一致性与最终一致性的选择

选 CP（强一致性）的场景：
  • 金融账户余额、库存数量
  • 分布式锁（错误的锁状态比锁不可用更危险）
  • 配置中心（配置错误影响面大）
  • Leader 选举（不能有多个 Leader）

选 AP（最终一致性）的场景：
  • 社交媒体的帖子点赞数（稍微不准确无所谓）
  • 商品浏览量、搜索排名
  • 评论列表（短暂不一致用户无感知）
  • DNS 解析（更新延迟几分钟是可以接受的）

Raft 共识算法

Raft 是一种可理解性优先的共识算法（相比 Paxos 更易理解），etcd、TiKV、CockroachDB 等均基于 Raft 实现。

Raft 的三个子问题

1. Leader 选举

角色：
  Leader（领导者）：处理所有写请求，同步日志给 Follower
  Follower（跟随者）：接受 Leader 的日志，响应客户端读请求（Strong Read 除外）
  Candidate（候选者）：选举期间的过渡状态

选举流程：
  初始状态：所有节点都是 Follower

  Follower 超过 election timeout 没收到 Leader 心跳（150~300ms，随机）：
    1. 转为 Candidate
    2. 递增自己的 term（任期）
    3. 给自己投票
    4. 向所有节点发 RequestVote RPC

  获得多数票（> n/2）→ 成为 Leader
    → 立即发心跳给所有 Follower（防止其他 Candidate 发起新选举）

  投票规则（防止旧数据的节点成为 Leader）：
    候选人的日志必须至少和自己一样新（term 更大，或 term 相同但日志更长）才给投票

2. 日志复制

客户端写请求 → Leader
  1. Leader 将操作追加到自己的日志（uncommitted 状态）
  2. Leader 并发发送 AppendEntries RPC 给所有 Follower
  3. 等待多数（> n/2）节点确认写入日志
  4. Leader 提交日志（committed）→ 应用到状态机
  5. 通知 Follower 提交

特点：
  • 只需多数派确认，不需要全部节点（允许少数节点故障）
  • 日志是顺序的（每条日志有 index 和 term）
  • Leader 只需收到 n/2 + 1 个确认即可提交（包括自己）

3. 安全性

保证：已提交的日志不会被覆盖

关键机制：
  选举约束（Election Restriction）：
    只有日志最新的节点才能成为 Leader
    确保新 Leader 一定包含所有已提交的日志

  日志匹配（Log Matching）：
    如果两个节点的日志在某个 index 相同，则该 index 之前的所有日志都相同
    Leader 在 AppendEntries 中携带前一条日志的 index 和 term，Follower 验证后才追加

Raft 的优化：Multi-Raft 与 Raft Leader Lease

问题：所有写请求都经过 Leader，Leader 是性能瓶颈

Multi-Raft：
  将数据分片（Region/Shard），每个分片有独立的 Raft Group 和 Leader
  不同分片的 Leader 在不同节点上 → 实现写操作的水平扩展
  TiKV 使用此方案

Leader Lease（领导者租约）：
  Leader 在租约期内可以直接响应读请求（无需 heartbeat 确认）
  减少了读请求的 RTT（从 2 RTT 降到 1 RTT）
  前提：有时钟同步保障（时钟漂移在可接受范围内）

分布式时钟

分布式系统中无法依赖物理时钟（NTP 同步误差可达数毫秒到秒），需要逻辑时钟来确定事件顺序。

Lamport 时钟

规则：
  1. 每个进程维护一个计数器 LC
  2. 进程内每发生一个事件：LC++
  3. 发送消息时，携带当前 LC 值
  4. 接收消息时：LC = max(LC, 收到的LC) + 1

性质：
  如果 A happens-before B，则 LC(A) < LC(B)
  但 LC(A) < LC(B) 不代表 A happens-before B（存在并发事件）

局限：无法判断两个事件是否并发

向量时钟（Vector Clock）

每个节点维护一个向量，记录所有节点的逻辑时钟：
  Node1: [1, 0, 0]
  Node2: [1, 2, 0]
  Node3: [1, 2, 3]

规则：
  1. 事件发生：自己的分量++
  2. 发送消息：携带当前向量
  3. 接收消息：每个分量取 max，然后自己的分量++

判断关系：
  VC(A) < VC(B)（A 的所有分量都 ≤ B，且至少一个严格 <）→ A happens-before B
  VC(A) 和 VC(B) 不可比（某个分量 A 大，另一个分量 B 大）→ 并发事件

应用：DynamoDB、Riak 的冲突检测

Google TrueTime

Google Spanner 使用专用硬件（GPS + 原子钟）提供全球时间 TrueTime API：
  TrueTime.now() 返回 [earliest, latest] 时间区间（误差 < 7ms）

Spanner 在提交事务前等待不确定窗口（commit wait）：
  确保事务的提交时间戳在所有可能的时钟值之后
  → 实现了外部一致性（External Consistency，比线性一致性更强）

代价：每次写事务需要等待约 7ms（commit wait 期间）

高频面试题

Q：CAP 三者能同时满足吗？

不能。P（分区容错）是分布式系统的现实，无法舍弃。当网络分区发生时，只能在 C（一致性）和 A（可用性）之间二选一：CP 系统在分区期间拒绝服务保证数据一致，AP 系统在分区期间允许访问但可能返回旧数据。

Q：ZooKeeper 和 Eureka 分别是 CP 还是 AP？

ZooKeeper 是 CP：Leader 崩溃后需要重新选举（通常几秒），期间无法提供服务，保证了数据一致性。Eureka 是 AP：每个节点都可以独立响应，网络分区时不同节点可能注册表不一致，但服务仍可用；有”自我保护模式”，当心跳失败比例过高时不剔除服务。

Q：Raft 如何保证 Leader 一定拥有所有已提交的日志？

通过选举约束：在 RequestVote 中，投票节点只给日志”至少和自己一样新”的候选人投票（比较 lastLogTerm，相同则比较 lastLogIndex）。任何已提交的日志已经被多数派写入，而新 Leader 也必须获得多数派的票，因此新 Leader 的日志集合一定是已提交日志的超集。

Q：最终一致性和强一致性分别适合哪些场景？

强一致性（CP）适合：金融交易（账户余额）、分布式锁、配置中心、选举场景——错误数据比不可用更危险的场景。最终一致性（AP）适合：社交媒体（点赞数、评论）、购物车（短时不一致可接受）、DNS、缓存——可用性比精确一致更重要的场景。