基础理论

1. CAP 理论 ⭐⭐⭐⭐⭐

1.1 CAP 定义

• Consistency（一致性）

  • 所有节点在同一时刻看到的数据是一致的

  • 等同于所有节点访问同一份最新的数据副本

  • 强一致性 vs 弱一致性 vs 最终一致性

• Availability（可用性）

  • 每次请求都能获得非错误响应

  • 不保证获取的数据是最新的

  • 通常用可用率衡量（如 99.99%）

• Partition Tolerance（分区容错性）

  • 系统在网络分区的情况下仍能继续工作

  • 分区：网络故障导致节点间无法通信

  • 分布式系统必须容忍分区

1.2 CAP 权衡

• CA（一致性 + 可用性）

  • 单机数据库（MySQL、PostgreSQL）

  • 无法容忍网络分区

  • 不适合分布式场景

• CP（一致性 + 分区容错）

  • ZooKeeper、etcd、HBase

  • 网络分区时牺牲可用性

  • 适用于强一致性要求的场景

• AP（可用性 + 分区容错）

  • Cassandra、DynamoDB、Eureka

  • 网络分区时牺牲一致性

  • 适用于高可用要求的场景

1.3 CAP 理论深入理解

为什么只能三选二？

场景：两个节点 A 和 B 之间发生网络分区

如果选择 CP（一致性 + 分区容错）：
- 分区期间拒绝写入请求，保证数据一致
- 牺牲了可用性（无法处理请求）

如果选择 AP（可用性 + 分区容错）：
- 分区期间继续处理请求
- A 和 B 可能写入不同数据
- 牺牲了一致性

现实中的 CAP

• 网络分区是必然发生的：所以实际上是在 C 和 A 之间选择

• 不是非此即彼：可以根据不同的数据类型采用不同策略

• PACELC 扩展：在无分区时也需要在延迟（L）和一致性（C）之间权衡

1.4 常见误区

• 不是非此即彼的选择，而是程度问题

• 实际系统往往在 CP 和 AP 之间权衡

• 可以针对不同数据采用不同策略

• CAP 中的 C 是线性一致性，与 ACID 中的 C 不同

2. BASE 理论

2.1 BASE 定义

• Basically Available（基本可用）

  • 分布式系统出现故障时，允许损失部分可用性

  • 响应时间上的损失（如延迟增加）

  • 功能上的损失（如降级、限流）

• Soft State（软状态）

  • 允许系统中的数据存在中间状态

  • 该状态不影响系统整体可用性

  • 即允许不同节点间的数据同步存在延迟

• Eventually Consistent（最终一致性）

  • 系统中所有数据副本经过一定时间后最终能够达到一致状态

  • 不需要实时保证强一致性

  • 允许一定时间窗口内的数据不一致

2.2 BASE vs ACID

特性	ACID	BASE
适用场景	传统数据库	分布式系统
一致性	强一致性	最终一致性
可用性	较低	较高
并发性能	较低	较高
实现复杂度	较低	较高

2.3 BASE 实践案例

电商下单场景：

ACID 方式：
1. 开启事务
2. 扣减库存
3. 创建订单
4. 扣减余额
5. 提交事务
问题：分布式环境下难以实现，性能差

BASE 方式：
1. 创建订单（状态：待支付）
2. 异步扣减库存（软状态）
3. 异步扣减余额（软状态）
4. 全部成功后更新订单状态为已支付（最终一致）
优点：高可用，高性能

3. 分布式一致性级别

3.1 强一致性（Strong Consistency）

• 任何时刻所有节点数据完全一致

• 写入后立即可见

• 实现成本高，性能差

• 典型实现：Paxos、Raft

线性一致性（Linearizability）：

• 最强的一致性模型

• 所有操作看起来像是在某个时间点瞬间完成

• 全局时间顺序一致

3.2 弱一致性（Weak Consistency）

• 不保证后续访问能返回最新值

• 尽最大努力使数据趋于一致

• 系统不保证多久之后数据能够达到一致

3.3 最终一致性（Eventual Consistency）

• 弱一致性的特殊形式

• 保证在没有新更新的条件下，最终所有访问都能看到最新值

• 具体变种：

  • 因果一致性：有因果关系的操作顺序一致

  • 读己之所写：写入后自己能立即读到

  • 会话一致性：同一会话内保证一致性

  • 单调读一致性：读到的数据不会比之前读到的旧

  • 单调写一致性：写操作顺序保证

3.4 一致性级别对比

强一致性          ──────────────────>          弱一致性
   │                    │                        │
线性一致性    顺序一致性    因果一致性    最终一致性
(Linearizable) (Sequential) (Causal)    (Eventual)

性能：       低  <──────────────────────────>  高
复杂度：     高  <──────────────────────────>  低
数据正确性： 高  <──────────────────────────>  低

4. FLP 不可能定理 ⭐⭐⭐⭐

4.1 定理内容

FLP 定理（1985年）：在一个异步分布式系统中，即使只有一个进程可能失败，也不存在一个确定性的共识算法能够在有限时间内达成一致。

4.2 定理前提

• 异步系统：消息传递没有时间上界

• 进程失败：至少一个进程可能崩溃

• 确定性算法：不使用随机数

4.3 定理意义

FLP 告诉我们：
1. 不可能设计一个在所有情况下都能达成共识的算法
2. 但这不意味着共识算法没有实用价值

实际解决方案：
1. 引入超时机制（放宽异步假设）
   - Paxos、Raft 都使用超时来检测故障
2. 使用随机化算法
   - 随机选择可以避免活锁
3. 容忍终止失败
   - 允许在某些极端情况下不终止

4.4 与其他定理的关系

• CAP 定理：分布式系统的能力边界

• FLP 定理：共识问题的可解性边界

• 两者都揭示了分布式系统的本质限制

5. 拜占庭将军问题 ⭐⭐⭐⭐

5.1 问题描述

场景：
- N 个将军围攻一座城市
- 需要通过信使传递消息来达成共识（进攻或撤退）
- 其中可能有叛徒发送错误信息
- 目标：所有忠诚的将军能够达成一致的行动

约束：
- 信使可能被截杀（消息丢失）
- 叛徒可能发送不同的消息给不同将军
- 叛徒可能伪造消息

5.2 问题结论

• 3f+1 定理：要容忍 f 个拜占庭故障节点，至少需要 3f+1 个节点

• 即：拜占庭故障节点不能超过总节点数的 1/3

5.3 拜占庭容错算法

• PBFT（Practical Byzantine Fault Tolerance）

  • 实用拜占庭容错算法

  • 需要 3f+1 个节点容忍 f 个故障

  • 区块链中广泛使用

• PoW（Proof of Work）

  • 工作量证明，比特币使用

  • 通过算力竞争达成共识

• PoS（Proof of Stake）

  • 权益证明，以太坊 2.0 使用

  • 通过持有代币数量和时间达成共识

5.4 拜占庭 vs 非拜占庭

类型	故障模型	节点要求	典型算法
非拜占庭	节点只会宕机	2f+1	Paxos、Raft
拜占庭	节点可能恶意	3f+1	PBFT、PoW

6. 分布式时钟 ⭐⭐⭐⭐

6.1 物理时钟的问题

分布式系统中物理时钟存在的问题：

1. 时钟漂移（Clock Drift）
   - 不同机器的时钟走速不同
   - 石英晶体振荡器精度有限
   - 典型漂移：10-100 ppm（每天误差约 1-10 秒）

2. 时钟同步问题
   - NTP 同步有延迟和误差
   - 网络延迟不确定
   - 无法精确同步

3. 闰秒问题
   - 闰秒调整可能导致时间倒退
   - 2012年 Linux 内核闰秒 bug

6.2 逻辑时钟（Lamport Clock）

/**
 * Lamport 逻辑时钟实现
 */
public class LamportClock {
    private long timestamp = 0;

    // 本地事件发生时
    public synchronized long tick() {
        return ++timestamp;
    }

    // 发送消息时
    public synchronized long send() {
        return ++timestamp;
    }

    // 接收消息时
    public synchronized long receive(long receivedTimestamp) {
        timestamp = Math.max(timestamp, receivedTimestamp) + 1;
        return timestamp;
    }
}

Lamport 时钟规则：

1. 本地事件：LC = LC + 1

2. 发送消息：LC = LC + 1，消息携带 LC

3. 接收消息：LC = max(LC, msg.LC) + 1

Lamport 时钟性质：

• 如果 a → b（a 发生在 b 之前），则 LC(a) < LC(b)

• 但 LC(a) < LC(b) 不能推出 a → b

• 只能确定偏序关系，不能确定因果关系

6.3 向量时钟（Vector Clock）

/**
 * 向量时钟实现
 */
public class VectorClock {
    private Map<String, Long> clock = new HashMap<>();
    private String nodeId;

    public VectorClock(String nodeId) {
        this.nodeId = nodeId;
        clock.put(nodeId, 0L);
    }

    // 本地事件发生时
    public synchronized void tick() {
        clock.merge(nodeId, 1L, Long::sum);
    }

    // 发送消息时
    public synchronized Map<String, Long> send() {
        tick();
        return new HashMap<>(clock);
    }

    // 接收消息时
    public synchronized void receive(Map<String, Long> other) {
        // 合并时钟：取每个节点的最大值
        for (Map.Entry<String, Long> entry : other.entrySet()) {
            clock.merge(entry.getKey(), entry.getValue(), Math::max);
        }
        tick();
    }

    // 比较两个向量时钟
    public static Relation compare(Map<String, Long> v1, Map<String, Long> v2) {
        boolean v1Greater = false;
        boolean v2Greater = false;

        Set<String> allKeys = new HashSet<>();
        allKeys.addAll(v1.keySet());
        allKeys.addAll(v2.keySet());

        for (String key : allKeys) {
            long t1 = v1.getOrDefault(key, 0L);
            long t2 = v2.getOrDefault(key, 0L);
            if (t1 > t2) v1Greater = true;
            if (t2 > t1) v2Greater = true;
        }

        if (v1Greater && !v2Greater) return Relation.AFTER;
        if (v2Greater && !v1Greater) return Relation.BEFORE;
        if (!v1Greater && !v2Greater) return Relation.EQUAL;
        return Relation.CONCURRENT;  // 并发事件
    }

    enum Relation { BEFORE, AFTER, EQUAL, CONCURRENT }
}

向量时钟优势：

• 可以准确判断因果关系

• 可以检测并发事件

• 常用于冲突检测和解决

向量时钟示例：

节点 A, B, C 初始向量时钟：
A: [1,0,0]  B: [0,1,0]  C: [0,0,1]

A 发送消息给 B：
A: [2,0,0]  // A 自增后发送
B: [2,2,0]  // B 接收后合并并自增

B 发送消息给 C：
B: [2,3,0]
C: [2,3,2]

比较 [2,0,0] 和 [0,0,1]：
- A[0]=2 > C[0]=0
- A[2]=0 < C[2]=1
- 结论：并发事件，无因果关系

6.4 混合逻辑时钟（HLC）

HLC = <物理时间, 逻辑计数器>

优点：
1. 结合物理时间和逻辑时钟
2. 接近物理时间，便于调试
3. 满足因果一致性
4. CockroachDB、TiDB 使用

7. 分布式系统挑战 ⭐⭐⭐⭐⭐

7.1 网络问题

网络分区（Network Partition）：
- 节点间网络不通，形成多个独立子网
- 可能导致脑裂（Split Brain）
- 解决：Quorum 机制、Fencing

网络延迟：
- 延迟不确定，可能抖动
- 影响超时判断
- 解决：自适应超时、重试策略

消息问题：
- 消息丢失：需要确认和重试
- 消息重复：需要幂等设计
- 消息乱序：需要序号机制

7.2 节点故障

故障类型：
1. 崩溃故障（Crash）
   - 节点停止工作
   - 最简单的故障模型

2. 遗漏故障（Omission）
   - 节点未收到或未发送消息
   - 包括网络故障

3. 时序故障（Timing）
   - 响应时间超出预期
   - 异步系统中难以区分

4. 拜占庭故障（Byzantine）
   - 节点行为任意（包括恶意）
   - 最复杂的故障模型

故障检测：
- 心跳机制
- 超时判断
- Phi Accrual 故障检测器

7.3 数据一致性

一致性挑战：
1. 并发更新冲突
2. 副本同步延迟
3. 部分失败

解决策略：
1. 强一致性协议（Paxos、Raft）
2. 冲突解决策略（LWW、CRDT）
3. 版本向量追踪

7.4 分布式协调

常见协调问题：
1. 领导者选举
2. 分布式锁
3. 分布式屏障
4. 配置管理

协调服务：
- ZooKeeper
- etcd
- Consul

8. 面试要点总结

8.1 理论核心

知识点	重要程度	考察频率
CAP 理论	⭐⭐⭐⭐⭐	非常高
BASE 理论	⭐⭐⭐⭐	高
一致性级别	⭐⭐⭐⭐	高
FLP 定理	⭐⭐⭐	中
拜占庭问题	⭐⭐⭐	中
逻辑时钟	⭐⭐⭐⭐	高
向量时钟	⭐⭐⭐	中

8.2 关键记忆点

CAP：
- 三选二是错误理解，实际是 P 必选，CA 二选一
- 可以针对不同数据采用不同策略
- PACELC 是更完整的模型

BASE：
- BASE 是 CAP 中 AP 方案的延伸
- 核心是用最终一致性换取高可用
- 实际系统大多采用 BASE

时钟：
- 物理时钟不可靠，需要逻辑时钟
- Lamport 时钟只能确定偏序
- 向量时钟可以检测并发和因果

9. 常见面试题

9.1 CAP 相关

Q1：CAP 理论是什么？为什么只能三选二？

答：CAP 指一致性、可用性、分区容错性。
分布式系统必须容忍网络分区（P），
所以实际是在 C 和 A 之间选择。
当网络分区发生时：
- 选 C：拒绝请求，保证一致
- 选 A：继续服务，牺牲一致

Q2：ZooKeeper 是 CP 还是 AP？

答：ZooKeeper 是 CP 系统。
- 使用 ZAB 协议保证强一致性
- 网络分区时，少数派节点不可用
- 写操作需要多数派确认

Q3：如何在一个系统中同时满足 CA？

答：使用不同的数据分区策略。
- 强一致数据：使用 CP 存储（如订单状态）
- 高可用数据：使用 AP 存储（如商品浏览量）
- 本地数据：单机 CA（如缓存）

9.2 一致性相关

Q4：最终一致性的变种有哪些？

答：
1. 因果一致性：有因果关系的操作顺序一致
2. 读己之所写：自己写的数据立即可读
3. 会话一致性：同一会话内一致
4. 单调读一致性：不会读到更旧的数据
5. 单调写一致性：写操作顺序保证

Q5：如何实现分布式系统的强一致性？

答：
1. 共识算法：Paxos、Raft、ZAB
2. 两阶段提交：2PC（有阻塞问题）
3. 三阶段提交：3PC（解决部分阻塞）
4. 全局时钟：Google Spanner TrueTime

9.3 时钟相关

Q6：为什么分布式系统需要逻辑时钟？

答：
1. 物理时钟有漂移，无法精确同步
2. NTP 同步有误差（毫秒级）
3. 需要确定事件的因果顺序
4. 逻辑时钟可以提供事件偏序关系

Q7：Lamport 时钟和向量时钟的区别？

答：
Lamport 时钟：
- 单个整数
- 只能确定偏序（a<b 不能推出 a→b）
- 空间复杂度 O(1)

向量时钟：
- 每个节点一个分量
- 可以判断因果和并发
- 空间复杂度 O(n)

9.4 故障容错相关

Q8：拜占庭故障和普通故障有什么区别？

答：
普通故障（崩溃故障）：
- 节点只会停止工作
- 不会发送错误信息
- 2f+1 节点容忍 f 个故障

拜占庭故障：
- 节点可能发送错误/恶意信息
- 可能欺骗其他节点
- 3f+1 节点容忍 f 个故障

Q9：FLP 定理对工程实践有什么影响？

答：
FLP 证明了异步系统无法保证共识终止。
工程解决方案：
1. 引入超时机制（Paxos、Raft）
2. 使用随机化（随机选举）
3. 接受概率性保证
4. 实际系统中问题很少出现