# 基础理论 ## 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） ```java /** * 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） ```java /** * 向量时钟实现 */ public class VectorClock { private Map 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 send() { tick(); return new HashMap<>(clock); } // 接收消息时 public synchronized void receive(Map other) { // 合并时钟：取每个节点的最大值 for (Map.Entry entry : other.entrySet()) { clock.merge(entry.getKey(), entry.getValue(), Math::max); } tick(); } // 比较两个向量时钟 public static Relation compare(Map v1, Map v2) { boolean v1Greater = false; boolean v2Greater = false; Set 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