算法分析与设计

Appearance

9.4 一致性模型：什么时候必须看到同一个世界 ​

核心问题：一致性是"所有机器数据一样"，还是"对读写顺序的承诺"？

War Story：课程报名系统的困境 ​

某大学开发分布式课程报名系统，最后一个名额，两个学生同时抢。

方案A（强一致）：

每次操作都同步到所有节点
步骤：
1. 学生A请求报名 → 锁定名额
2. 同步到所有节点 → 确认锁定
3. 学生B请求报名 → 发现名额已满 → 拒绝

优点：不会超额
缺点：每次操作耗时约100ms（同步开销）
高峰期：1000人/秒 → 系统崩溃

方案B（最终一致）：

本地操作，异步同步
步骤：
1. 学生A请求报名 → 本地记录
2. 学生B请求报名 → 本地记录
3. 后台检测超额 → 随机取消一个

优点：响应快（约10ms）
缺点：可能超额，需要补偿机制
高峰期：系统可用，但可能产生纠纷

困惑：该选哪个？

答案：看业务语义。课程报名不能超额 → 选强一致；统计展示可延迟 → 选最终一致。

一致性的本质 ​

误解 ​

常见误解：一致性 = 所有机器数据一样。

这只是表面现象，真正的定义更深层。

正确理解 ​

一致性是对读写顺序的承诺。

一致性级别定义了：系统向客户端承诺，读写操作的顺序是什么样的。

类比：多人协作整理图书馆

  • 强一致：所有人必须看到最新书目 → 每次修改要通知所有人
  • 最终一致：书目可能暂不一致 → 但最终会同步
  • 因果一致：某人看到公告后告诉他人 → 信息传播有序

一致性级别阶梯 ​

线性一致性（Linearizability） ​

定义：所有操作看起来瞬时发生，所有客户端看到相同顺序。

特点：

  • 最强的一致性级别
  • 每次读都能读到最新写
  • 操作有全局时间顺序

代价：

  • 需要全局同步
  • 延迟高
  • 不容忍网络分区

适用场景：

  • 金融交易（转账不能重复）
  • 库存扣减（不能超卖）

类比：图书馆公告板

  • 某人发布公告 → 所有人立刻看到
  • 不存在"某人发了公告但其他人没看到"的情况

顺序一致性（Sequential Consistency） ​

定义：所有进程看到相同顺序，但顺序不一定等于实际时间顺序。

特点：

  • 所有客户端看到相同顺序
  • 但顺序可能与实际时间顺序不同

代价：

  • 需要全局排序
  • 延迟较高

适用场景：

  • 配置管理（所有节点看到相同配置变化顺序）

类比：图书馆公告板（有延迟）

  • 某人发布公告 → 所有人看到，但顺序可能不是实际时间顺序

因果一致性（Causal Consistency） ​

定义：因果相关的操作顺序一致，因果无关的操作可以不同顺序。

特点：

  • 只保证因果相关操作的顺序
  • 因果无关操作可以乱序

代价：

  • 需要追踪因果关系
  • 延迟中等

适用场景：

  • 社交网络评论（A回复B → A的回复必须在B之后）

类比：图书馆公告板（因果关系）

  • 某人发布公告 → 有人评论 → 评论必须在公告之后
  • 但两个无关公告可以不同顺序

最终一致性（Eventual Consistency） ​

定义：最终收敛到相同状态，但中间可能有不一致。

特点：

  • 最弱的一致性级别（CAP定理下）
  • 最终一致，但中间可能不一致
  • 响应最快

代价：

  • 中间状态可能不一致
  • 可能读到旧数据

适用场景：

  • 缓存（可以短暂不一致）
  • 统计面板（延迟可接受）
  • 日志同步

类比：图书馆公告板（异步更新）

  • 某人发布公告 → 不是所有人立刻看到
  • 但最终所有人会看到

CAP定理 ​

定义 ​

CAP定理：分布式系统最多同时满足以下三者中的两个：

  • C（Consistency）：一致性（线性一致性）
  • A（Availability）：可用性（每次请求都有响应）
  • P（Partition tolerance）：分区容错（网络分区时系统继续运行）

选择 ​

选择说明
CP一致性 + 分区容错 → 分区时牺牲可用性
AP可用性 + 分区容错 → 分区时牺牲一致性
CA一致性 + 可用性 → 无分区容错（单机系统）

实践 ​

大多数分布式系统选择AP或CP：

  • CP系统：HBase、MongoDB（强一致配置）
  • AP系统：Cassandra、DynamoDB

教训：不可能三者兼得，根据业务选择。

幂等性设计 ​

问题 ​

网络故障导致请求重发 → 重复执行？

场景：用户扣款10元

正常流程：
  请求1 → 扣款10元 → 成功

网络故障场景：
  请求1 → 扣款10元 → 成功
  网络故障 → 响应丢失
  客户端超时 → 重发请求1
  → 再次扣款10元 → 用户被扣20元！

幂等定义 ​

幂等：重复执行不会产生副作用。

幂等操作示例：
  查询：重复查询不改变数据
  设置值：set(x, 10) → 多次执行结果相同
  扣款（幂等设计）：check(request_id) → 已处理则返回结果

幂等设计方案 ​

方案1：唯一请求ID

python
def deduct(user_id, amount, request_id):
    # 检查是否已处理
    if processed_requests.contains(request_id):
        return previous_results[request_id]
    
    # 处理请求
    user_balance[user_id] -= amount
    processed_requests.add(request_id)
    result = {"success": True, "balance": user_balance[user_id]}
    previous_results[request_id] = result
    return result

方案2：乐观锁

python
def deduct(user_id, amount, version):
    # 检查版本号
    if user_version[user_id] != version:
        raise VersionConflictError()
    
    # 处理请求
    user_balance[user_id] -= amount
    user_version[user_id] += 1
    return {"success": True, "balance": user_balance[user_id]}

补偿机制 ​

问题 ​

最终一致方案可能导致超额，如何补偿？

场景：课程报名（最终一致）

正常流程：
  学生A报名 → 本地记录1个名额
  学生B报名 → 本地记录1个名额
  总名额只剩1个 → 超额！

补偿：
  检测超额 → 随机取消一个报名 → 发送取消通知

补偿设计 ​

python
def enroll(course_id, student_id):
    # 本地报名
    enrollments[course_id].append(student_id)
    
    # 异步检测超额
    async_detect_overbooking(course_id)

def detect_overbooking(course_id):
    # 同步所有节点状态
    total = sync_and_count(course_id)
    if total > capacity[course_id]:
        # 补偿：随机取消超额的报名
        overbooked = get_overbooked(course_id)
        cancel_random(course_id, overbooked)
        notify_cancelled(student_id)

补偿原则 ​

  1. 可逆操作：设计可逆操作，方便补偿
  2. 公平性：补偿时保证公平（如随机取消）
  3. 通知机制：补偿后通知用户

一致性选择决策框架 ​

决策流程 ​

业务需求分析 → 确定一致性级别

问题1：操作不能失败吗？
  是 → 强一致
  否 → 继续分析

问题2：因果关系重要吗？
  是 → 因果一致
  否 → 继续分析

问题3：最终一致可接受吗？
  是 → 最终一致
  否 → 顺序一致

业务语义决定一致性 ​

业务场景推荐一致性原因
金融转账线性一致不能重复扣款
库存扣减线性一致不能超卖
配置管理顺序一致需要一致顺序
社交评论因果一致回复顺序重要
统计面板最终一致延迟可接受
缓存同步最终一致可以短暂不一致

LLM视角：一致性选择 ​

LLM容易犯的错误 ​

LLM方案："设计课程报名系统"
方案：每次报名都同步到所有节点

审查发现：
- 功能正确：不会超额
- 性能问题：高峰期系统崩溃

改进：
- 库存扣减：强一致（不能超卖）
- 统计展示：最终一致（延迟可接受）

审查要点 ​

审查LLM给出的一致性方案时，检查：

  1. 业务语义：这个操作真的需要强一致吗？
  2. 性能影响：强一致的性能代价能接受吗？
  3. 幂等设计：是否有幂等机制防止重复执行？
  4. 补偿机制：最终一致方案是否有补偿？

小结 ​

一致性级别对比 ​

级别定义代价适用场景
线性一致操作瞬时发生最高金融交易
顺序一致相同顺序高配置管理
因果一致因果有序中社交评论
最终一致最终收敛低缓存、日志

设计原则 ​

  1. 业务语义决定一致性
  2. 不能三者兼得（CAP定理）
  3. 幂等设计防止重复
  4. 补偿机制处理超额

LLM审查要点 ​

  • 是否分析业务语义？
  • 是否选择合适的一致性级别？
  • 是否有幂等设计？
  • 是否有补偿机制？

练习 ​

1. 选择一致性级别 ​

场景：电商秒杀系统。

分析以下操作需要的一致性级别：

  • 库存扣减
  • 订单创建
  • 统计展示

2. 设计幂等扣款 ​

场景：用户扣款10元。

设计幂等扣款方案，防止网络故障导致的重复扣款。

3. 审查LLM方案 ​

让LLM设计"分布式点赞系统"，审查其一致性选择和幂等设计。

下一节 ​

理解了一致性模型后，我们来看数据分片：

9.5 数据分片与负载均衡

新时代的算法课程