分布式系统

1. 分布式锁

1.1 什么是分布式锁

分布式锁是用于在分布式环境中确保多个节点对共享资源的互斥访问的机制。

1.2 实现方式

1.3 Redis 分布式锁实现

// 加锁
public boolean lock(String key, String value, long expireTime) {
    return redisTemplate.opsForValue()
        .setIfAbsent(key, value, expireTime, TimeUnit.SECONDS);
}

// 解锁 (需验证值，防止误删)
public boolean unlock(String key, String value) {
    String script = "if redis.call('get', KEYS[1]) == ARGV[1] " +
                    "then return redis.call('del', KEYS[1]) else return 0 end";
    return redisTemplate.execute(
        new DefaultRedisScript<>(script, Long.class),
        Collections.singletonList(key), value) == 1;
}

1.4 Redisson 分布式锁

RLock lock = redisson.getLock("myLock");
try {
    lock.lock(30, TimeUnit.SECONDS);  // 自动续期
    // 业务逻辑
} finally {
    lock.unlock();
}

1.5 注意事项

• 锁续期：防止业务执行超时导致锁自动释放
• 主从一致性：Redis 主从切换可能导致锁丢失，建议使用 RedLock
• 可重入性：同一线程可多次获取锁

2. 分布式事务

2.1 什么是分布式事务

跨多个数据库/服务的事务操作，保证原子性和一致性。

2.2 解决方案

2PC (两阶段提交)

阶段一：准备阶段 (Prepare)
  协调者 → 所有参与者：prepare()
  参与者 → 协调者：ready/abort

阶段二：提交阶段 (Commit)
  协调者 → 所有参与者：commit()/rollback()

TCC (Try-Confirm-Cancel)

Try：预留资源
Confirm：确认执行
Cancel：取消回滚

@TwoPhaseBusiness(name = "transfer")
public boolean transfer(String from, String to, int amount) {
    // Try
    if (!accountService.tryDeduct(from, amount)) {
        return false;
    }
    // Confirm/Cancel 由框架自动处理
    return true;
}

可靠消息最终一致性

1. 本地事务 + 消息表
2. 定时任务扫描消息
3. 消息队列 + 消费者确认

2.3 Seata 分布式事务

@GlobalTransactional
public void transfer(String from, String to, int amount) {
    accountService.debit(from, amount);
    accountService.credit(to, amount);
}

3. CAP 理论

3.1 定义

3.2 核心结论

分布式系统只能同时满足其中两个，无法满足全部三个。

    C + A
   /     \
  P -------   →  不可能同时满足 CAP

3.3 典型系统

3.4 实际选择

• 强一致性场景：金融、订单 → CP
• 高可用场景：社交、推荐 → AP
• 大多数系统：通过降低一致性要求换取可用性（BASE）

4. BASE 理论

4.1 定义

BASE = Basically Available + Soft state + Eventually consistent

4.2 与 ACID 的区别

4.3 实践策略

1. 读写分离：主库写，从库读
2. 异步处理：消息队列解耦
3. 补偿机制：TCC / 失败重试
4. 版本控制：乐观锁 / 法定书

4.4 最终一致性实现

// 订单服务 → 消息队列 → 积分服务
// 异步同步，通过消息确认保证最终一致
@Transactional
public void createOrder(Order order) {
    orderRepository.save(order);
    // 发送消息，失败时重试
    mqService.sendDelayMessage("order-created", order);
}

5. Paxos 共识算法

5.1 什么是 Paxos

Paxos 是 Leslie Lamport 提出的分布式共识算法，最早被广泛认可的分布式公式算法之一，用于在分布式系统中就某个值达成一致（前提是不存在拜占庭将军问题，也就是没有恶意节点）。

5.2 角色

5.3 算法流程

阶段一：Prepare

Proposer → 所有Acceptor：.prepare(n)
Acceptor → Proposer：.promise(n, v)  // 已批准的最大提案

阶段二：Accept

Proposer → 所有Acceptor：.accept(n, v)
Acceptor → Proposer：.accepted(n)

5.4 简单理解

1. 提议者提出提案，获取过半数承诺
2. 如果之前有值，使用最大值
3. 提议者基于多数派值进行提议
4. 过半数接受后达成共识

5.5 特点

• 安全性：只批准一个值
• 活性：最终能达成共识（需要额外机制）
• 复杂度高：工程实现复杂

5.6 Multi-Paxos

• 连续多个实例共用 Prepare 阶段
• 选主后直接提交命令
• Google Chubby、Spanner 使用

6. Raft 协议

6.1 什么是 Raft

Raft 是为了易于理解而设计的共识算法，目标是替代 Paxos（针对非拜占庭场景，即无恶意节点，除 Raft 外，ZAB 协议、Fast Paxos 等都是基于 Paxos 改进的共识算法）。

6.2 角色

Leader → Follower：心跳维持权威
Follower → Candidate：选举超时触发
Candidate → Leader：获多数票后成为Leader

6.3 领导者选举

1. 节点随机超时 (150-300ms)
2. 超时 → 成为 Candidate
3. 发起投票，请求其他节点投票
4. 获得多数票 → 成为 Leader
5. 开始接收客户端请求

6.4 日志复制

Leader 接收请求 → 追加本地日志 → 发送 AppendEntries
Follower 接收 → 追加日志 → 回复
Leader 收到多数响应 → 提交 → 通知Follower提交

6.5 三个子问题

1. 领导者选举：leader 崩溃后重新选主
2. 日志复制：保证所有节点日志一致
3. 安全性：已提交的日志不会被覆盖

6.6 与 Paxos 对比

6.7 实际应用

• etcd：Kubernetes 使用
• Consul：HashiCorp
• TiKV：PingCAP
• CockroachDB：分布式 SQL

7. 拜占庭问题与容错

7.1 什么是拜占庭将军问题

拜占庭将军问题描述的是：在存在恶意节点（可能发送虚假信息）的情况下，分布式系统如何达成共识（针对拜占庭场景，通常使用 工作量证明（PoW，Proof-of-Work）、权益证明（PoS，Proof-of-Stake） 等共识算法，典型应用为区块链系统）。

场景：n 个将军，其中部分是叛徒
目标：所有忠诚将军做出相同的决定

叛徒可以：
- 发送矛盾的消息
- 假装没收到消息
- 误导其他将军

7.2 拜占庭容错 (BFT)

7.3 PBFT 算法流程

1. 客户端发送请求给主节点
2. 预准备：主节点广播请求给所有副本节点
3. 准备：所有节点互相交换消息，验证请求
4. 确认：节点收到 2f+1 条确认后，执行请求
5. 回复：返回结果给客户端

前提：系统能容忍 f 个恶意节点，需要 3f+1 个总节点

7.4 Raft 与拜占庭的关系

Raft 不是拜占庭容错的。

Raft 假设：

• 节点不会故意发送错误消息
• 网络丢包/延迟是正常的，但消息内容是可信的
• 节点崩溃是唯一故障模式

7.5 实际应用中的容错

实用选择：
- 可信内网 → Raft/etcd
- 联盟链 → PBFT
- 公链 → PoW/PoS

8. Gossip 协议

8.1 什么是 Gossip

Gossip 是一种最终一致性的分布式协议，模拟人类"八卦"传播：节点随机选择邻居交换信息，最终所有节点状态一致。

8.2 核心机制

节点 A 有新数据：
1. 随机选择节点 B 交换信息
2. B 再随机选择节点 C
3. 如此往复...

最终：所有节点都会收到这条消息

8.3 三种传播方式

8.4 特点

8.5 应用场景

8.6 实现示例

public class GossipProtocol {

    public void gossip(Node self, Map<String, State> localState) {
        // 1. 随机选择 1-3 个节点
        List<Node> targets = selectRandomNodes(self, 2);

        for (Node target : targets) {
            // 2. 交换版本信息
            Map<String, Version> remoteVersions = target.getVersions();

            // 3. 获取本地缺失的数据（Pull 模式）
            for (Map.Entry<String, Version> entry : remoteVersions.entrySet()) {
                if (localState.get(entry.getKey()).version < entry.getValue()) {
                    State latest = target.getState(entry.getKey());
                    localState.put(entry.getKey(), latest);
                }
            }

            // 4. 推送本地更新的数据（Push 模式）
            for (Map.Entry<String, State> entry : localState.entrySet()) {
                if (entry.getValue().version > remoteVersions.get(entry.getKey()).version) {
                    target.receive(entry.getKey(), entry.getValue());
                }
            }
        }
    }
}

9. 一致性哈希算法

9.1 解决的问题

传统哈希的问题：

假设有 3 台服务器，用 key % 3 分配：
key=0 → server0, key=1 → server1, key=2 → server2

问题：新增/删除 server 时，大量 key 需要重新映射
key=3 → server0 (原来在 server2)

9.2 一致性哈希原理

将服务器和 key 都哈希到 [0, 2^32-1] 的环上

服务器哈希：
  server0 = hash("192.168.1.1")
  server1 = hash("192.168.1.2")
  server2 = hash("192.168.1.3")

Key 分配：
  顺时针找到第一个服务器节点
  key 的哈希值落在哪个区间，就属于哪个服务器

9.3 虚拟节点

解决数据不均匀的问题：

每个物理服务器创建 N 个虚拟节点
server0 → vnode0, vnode1, vnode2... (分布在环上)

优点：
- 数据分布更均匀
- 新增/删除节点影响范围小
- 可以给性能不同的机器分配不同数量虚拟节点

9.4 实现示例

public class ConsistentHash<T> {

    private final TreeMap<Long, T> ring = new TreeMap<>();  // 哈希 → 节点
    private final HashFunction hashFunc;
    private final int virtualNodes;  // 每个物理节点的虚拟节点数

    public ConsistentHash(int virtualNodes) {
        this.hashFunc = Hashing.murmur3_128();
        this.virtualNodes = virtualNodes;
    }

    // 添加节点
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hashFunc.hashString(node.toString() + i, UTF_8).asLong();
            ring.put(hash, node);
        }
    }

    // 获取 key 所属的节点
    public T getNode(String key) {
        if (ring.isEmpty()) return null;

        long hash = hashFunc.hashString(key, UTF_8).asLong();

        // 找到第一个 >= hash 的节点，没有则取第一个（环）
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }
}

9.5 应用场景

9.6 与哈希分片对比

10. 理论之间的联系

10.1 分布式系统的三个核心问题

分布式系统的三个不确定性：
├─ 共识问题：节点之间如何达成一致？
├─ 信任问题：如何处理恶意/故障节点？
└─ 定位问题：数据如何分布到正确的节点？

10.2 举例：Redis Cluster

1. 写入数据 → 谁说了算？
   → 用 Raft 选主（共识算法）

2. 数据存在哪个节点？
   → 用一致性哈希（数据分片，即数据均匀分布在不同的节点上，每个节点只存储部分数据）

3. 节点之间怎么同步？
   → 用 Gossip 协议（最终一致，即节点的状态同步，也就是让集群中每个节点知道其他节点是否存活，数据版本：数据是否最新，节点的负载信息，集群拓扑情况：集群有哪些节点）

4. 如果节点故意使坏？
   → Redis 不处理，假设集群可信（不是拜占庭场景）

10.3 场景分类

10.4 一句话总结

10.5 它们不是替代关系

这些理论是互补的，用于解决分布式系统不同层面的问题：

一个完整的分布式系统可能同时用到：

  ┌─────────────┐
  │  一致性哈希  │  ← 数据存在哪
  └──────┬──────┘
         │
  ┌──────▼──────┐
  │  Raft/Gossip │  ← 节点之间怎么协调
  └──────┬──────┘
         │
  ┌──────▼──────┐
  │  拜占庭容错   │  ← 如果有人使坏（可选，取决于信任模型）
  └─────────────┘

参考资料

• Raft Paper
• Paxos Made Simple
• CAP 定理
• Seata 官方文档