← 返回首页 📚 实战课程
📑 本篇章节导航 (共5章,点击直达)
本节目标(学完能回答的面试题)核心知识(1小时精讲内容)面试速记卡(考前30秒速看)练习题(自测)学习资料

L31 - 分布式理论

本节目标(学完能回答的面试题)

核心知识(1小时精讲内容)

1. CAP理论

CAP三要素:


CAP不可能三角:

         C (一致性)
          /\
         /  \
        /    \
       /______\
    A          P
  (可用性)  (分区容错)

  网络分区必然存在 → P必须选
  实际选择:CP 或 AP

CP方向 — ZooKeeper:

AP方向 — Nacos:

2. BASE理论

BASE是对CAP中AP方向的工程实践总结:

概念全称含义
BABasically Available基本可用,允许响应时间增加或功能降级
SSoft State软状态,允许中间状态存在
EEventually Consistent最终一致性,一段时间后达到一致

ACID vs BASE:


ACID (传统数据库)          BASE (分布式系统)
├─ 原子性                  ├─ 基本可用
├─ 一致性                  ├─ 软状态
├─ 隔离性                  └─ 最终一致性
└─ 持久性
  强一致,性能低             弱一致,性能高

3. 一致性算法

2PC(两阶段提交)


协调者(TM)          参与者1(RM)    参与者2(RM)
    │                    │               │
    │──Phase 1: Prepare──▶               │
    │                    │───Yes/No──────│
    │◀───────────────────│               │
    │                    │               │
    │──Phase 2: Commit/Abort────────────▶│
    │                    │───ACK─────────│
    │◀───────────────────│               │

2PC的致命缺陷:

1. 同步阻塞:所有参与者在等待期间锁住资源,性能极差

2. 单点故障:协调者挂了,所有参与者永远阻塞

3. 数据不一致:Phase 2 部分参与者网络超时,导致部分提交部分回滚

4. 太过保守:任一参与者超时未响应,整个事务回滚

Paxos(思想理解)

Paxos是共识算法的理论基础,但工程实现极其复杂:

Raft(重点掌握)

Raft将共识问题拆成三个相对独立的子问题:

1. Leader选举:


节点状态:Follower → Candidate → Leader

选举流程:
  1. Follower超时未收到心跳 → 转为Candidate
  2. 自增term,投自己一票,向其他节点发RequestVote
  3. 收到多数派投票 → 成为Leader
  4. 开始周期性发送心跳(AppendEntries)

选举约束:
  - 每个term最多一个Leader
  - 候选人日志至少不比投票者旧(日志完整性检查)
  - 随机超时时间避免分票

2. 日志复制:


Client → Leader → AppendEntries → Followers
              │
              ▼
         本地写入日志
              │
              ▼
      多数派确认 → Apply到状态机 → 响应Client

日志一致性保证:
  - 如果两条日志的index和term相同,内容一定相同
  - 如果某条日志已提交,所有之前条目都已提交

3. 安全性:

4. 分布式ID生成

雪花算法(Snowflake)


0 | 0000...0000 | 00000 00000 | 0000...0000 | 000...000
  │      │            │      │         │           │
  │      │            │      │         │           └─ 12位序列号(0~4095)
  │      │            │      │         └───────────── 10位机器ID
  │      │            │      └─────────────────────── 5位数据中心ID  
  │      │            └────────────────────────────── 41位时间戳(ms)
  │      └─────────────────────────────────────────── 1位符号位(0)
  
64位 Long型ID = 1 + 41 + 5 + 5 + 12

理论QPS:409.6万/ms(单机)
可用年限:约69年(从epoch起算)

时钟回拨问题及解决方案:

1. 回拨 < 5ms:自旋等待

2. 回拨 > 5ms:抛异常,告警

3. 百度UidGenerator:借用未来时间

4. 美团Leaf:使用ZK的事务ID替代时钟

美团Leaf

两种模式:


  DB表: biz_tag | max_id | step | version
  每次取一个号段(如1000个ID),用完再取
  双Buffer:A号段用到10%时异步加载B号段

// Leaf-segment 号段模式示意
public class SegmentBuffer {
    private Segment[] segments; // 双buffer
    private volatile int currentPos; // 当前使用0或1
    private volatile boolean nextReady; // 下一个buffer是否就绪
    private volatile boolean idle; // 是否在加载中
}

class Segment {
    private AtomicLong value;  // 当前值
    private long max;          // 号段最大值
    private long step;         // 步长
}

面试速记卡(考前30秒速看)

练习题(自测)

1. Nacos为什么能同时支持AP和CP?底层协议分别是什么?

2. Raft选举中,如果两个Candidate同时获得相同票数会怎样?

3. 雪花算法的41位时间戳能用多少年?为什么不是从1970开始?

4. 2PC和3PC的区别是什么?3PC解决了2PC的哪些问题?

5. Leaf-segment的"双Buffer"机制解决了什么问题?

学习资料