database_tutorial

第4章:事务处理

开篇段落

事务是数据库系统的核心抽象之一,它将一系列数据库操作封装为一个逻辑单元,确保即使在并发访问和系统故障的情况下,数据的一致性和完整性也能得到保证。本章将深入探讨事务处理的实现机制,从ACID属性的底层实现到各种并发控制策略的权衡。我们将剖析不同隔离级别的实现细节,比较MVCC与2PL两种主流并发控制方案,并探讨死锁处理和长事务优化等实际问题。通过本章学习,您将掌握设计和优化高并发事务系统所需的核心知识。

ACID深度解析

原子性(Atomicity)

原子性保证事务中的所有操作要么全部成功,要么全部失败。这个看似简单的属性,其实现涉及复杂的日志和恢复机制。在现代数据库系统中,原子性的实现不仅要考虑单机故障,还要应对分布式环境下的部分失败问题。

实现机制

撤销日志(Undo Log):记录事务修改前的数据值,用于回滚未提交的事务。

事务执行流程:
1. BEGIN TRANSACTION
2. 写入undo log: <T1, X, old_value>
3. 修改数据页: X = new_value
4. 如果COMMIT: 清理undo log
   如果ABORT: 使用undo log恢复原值

Undo Log结构:
┌────────────┬────────────┬──────────┬────────────┬──────────┐
│ Transaction│ Page ID    │ Offset   │ Old Value  │ Timestamp│
│ ID         │            │          │            │          │
├────────────┼────────────┼──────────┼────────────┼──────────┤
│ T1         │ Page_100   │ 512      │ "Alice"    │ t1       │
│ T1         │ Page_100   │ 1024     │ 1000       │ t2       │
│ T2         │ Page_200   │ 256      │ NULL       │ t3       │
└────────────┴────────────┴──────────┴────────────┴──────────┘

重做日志(Redo Log):记录事务修改后的数据值,用于崩溃恢复时重放已提交事务。

WAL协议(Write-Ahead Logging):
1. 修改前先写日志
2. 日志必须在数据页之前持久化
3. 提交时强制刷新日志(而非数据页)

日志序列号(LSN)机制:
- 每个日志记录分配递增的LSN
- 数据页记录最后修改的LSN(PageLSN)
- 恢复时:如果LogLSN > PageLSN,则需要重做

Redo Log格式:
┌─────┬──────────┬──────────┬────────────┬────────────┬─────────┐
│ LSN │ Type     │ Trans ID │ Page ID    │ New Value  │ Checksum│
├─────┼──────────┼──────────┼────────────┼────────────┼─────────┤
│ 100 │ UPDATE   │ T1       │ Page_100   │ "Bob"      │ CRC32   │
│ 101 │ INSERT   │ T2       │ Page_200   │ Row_data   │ CRC32   │
│ 102 │ COMMIT   │ T1       │ -          │ -          │ CRC32   │
└─────┴──────────┴──────────┴────────────┴────────────┴─────────┘

日志管理策略

日志缓冲区管理

内存中的日志缓冲区:
┌─────────────────────────────────┐
│        Log Buffer (8MB)         │
├─────────────────────────────────┤
│ ████████████░░░░░░░░░░░░░░░░░░ │
│   ^         ^                   │
│   |         |                   │
│   写入位置   刷盘位置           │
└─────────────────────────────────┘

刷盘策略:
1. 事务提交时(强制刷盘)
2. 日志缓冲区满
3. 定期刷盘(如每秒)
4. 检查点触发

组提交(Group Commit)优化

传统方式(每事务一次fsync):
T1: Write Log → fsync() → Return
T2: Wait → Write Log → fsync() → Return
T3: Wait → Wait → Write Log → fsync() → Return
总时间:3 × fsync_time

组提交方式:
T1, T2, T3: Write Log → 
Leader(T1): fsync() → 唤醒T2, T3
总时间:1 × fsync_time

性能提升:batch_size × (fsync_time - log_write_time)

原子性保证级别

不同故障场景下的原子性保证:

1. 应用程序崩溃:
   - 数据库继续运行
   - 未提交事务自动回滚
   - 已提交事务保持不变

2. 数据库进程崩溃:
   - 重启时执行崩溃恢复
   - REDO:重放已提交事务
   - UNDO:回滚未提交事务

3. 操作系统崩溃:
   - 依赖WAL持久化
   - 重启后完整恢复

4. 硬件故障(磁盘损坏):
   - 需要备份或复制
   - RAID保护
   - 异地备份

5. 数据中心故障:
   - 地理复制
   - 多活架构

Rule of Thumb:

一致性(Consistency)

一致性确保事务将数据库从一个一致状态转换到另一个一致状态,不违反任何完整性约束。这是ACID中唯一需要应用程序参与的属性,数据库提供机制,应用定义策略。

约束类型与检查时机

  1. 立即约束(Immediate Constraints):每个语句执行后立即检查
  2. 延迟约束(Deferred Constraints):事务提交时检查
  3. 级联约束(Cascading Constraints):触发器和外键级联
约束层次结构:
┌─────────────────────────────────────────┐
│          应用层约束                     │
│    (业务规则、领域逻辑)               │
├─────────────────────────────────────────┤
│          数据库约束                     │
│  ┌─────────────────────────────────┐   │
│  │ 声明式约束                      │   │
│  │ - PRIMARY KEY                   │   │
│  │ - UNIQUE                        │   │
│  │ - FOREIGN KEY                   │   │
│  │ - CHECK                         │   │
│  │ - NOT NULL                      │   │
│  ├─────────────────────────────────┤   │
│  │ 程序式约束                      │   │
│  │ - 触发器(Triggers)            │   │
│  │ - 存储过程(Stored Procedures) │   │
│  └─────────────────────────────────┘   │
└─────────────────────────────────────────┘

约束检查开销分析:
- 主键/唯一性: O(log n) - 索引查找
- 外键: O(log n) × 关联表数量
- CHECK约束: O(1) - 表达式计算
- 触发器: 取决于触发器逻辑复杂度

约束检查实现

唯一性约束的并发检查

问题场景:两个并发事务插入相同的唯一值

传统方法(存在竞态条件):
T1: CHECK不存在 → INSERT → COMMIT
T2: CHECK不存在 → INSERT → COMMIT
结果:违反唯一性约束

解决方案1:预测锁(Predicate Lock)
T1: LOCK(predicate: value=X) → INSERT
T2: 等待T1释放锁

解决方案2:唯一索引(实际采用)
插入时原子性地检查和插入索引项
使用B+树的并发控制协议保证原子性

外键约束的高效实现

外键索引策略:
┌──────────────┬──────────────┬──────────────┐
│ 父表(dept) │              │ 子表(emp)  │
├──────────────┤              ├──────────────┤
│ PK: dept_id  │<─────────────│ FK: dept_id  │
│ Index: PK    │              │ Index: FK    │
└──────────────┘              └──────────────┘

操作影响分析:
1. INSERT子表:需要S锁父表记录(验证存在)
2. DELETE父表:需要扫描子表(检查引用)
3. UPDATE父表主键:需要检查+可能级联更新

优化:
- 子表外键列建立索引(加速DELETE/UPDATE父表)
- 批量操作时临时禁用约束检查
- 使用软删除避免级联删除

多版本一致性

MVCC下的一致性读取:

场景:计算账户总余额
┌────────┬─────────┬─────────┬─────────┐
│ 账户   │ V1(T0)  │ V2(T1)  │ V3(T2)  │
├────────┼─────────┼─────────┼─────────┤
│ A      │ 1000    │ 900     │ 800     │
│ B      │ 2000    │ 2100    │ 2200    │
│ C      │ 3000    │ 3000    │ 2900    │
└────────┴─────────┴─────────┴─────────┘

一致性快照@T1:
- 读取A的V2(900)
- 读取B的V2(2100)  
- 读取C的V1(3000)
总和 = 6000(一致的)

非一致读取(无快照):
- 读取A的V3(800)
- 读取B的V1(2000)
- 读取C的V3(2900)
总和 = 5700(不一致!)

优化策略

隔离性(Isolation)

隔离性是ACID中最复杂的属性,涉及并发控制的核心机制。它定义了并发事务之间的可见性边界,直接影响系统的并发性能和正确性。

异常现象层次

异常现象的形式化定义和严重程度:

P0: 脏写(Dirty Write)
w1[x] ... w2[x] ... (c1 or a1)
T2覆盖T1未提交的修改

P1: 脏读(Dirty Read)  
w1[x] ... r2[x] ... (a1)
T2读取T1未提交的修改,T1随后回滚

P2: 不可重复读(Non-repeatable Read)
r1[x] ... w2[x] ... c2 ... r1[x]
T1两次读取同一数据得到不同结果

P3: 幻读(Phantom Read)
r1[P] ... w2[y in P] ... c2 ... r1[P]
T1的谓词查询两次返回不同记录集

P4: 写偏斜(Write Skew)
r1[x] ... r2[y] ... w1[y] ... w2[x] ... c1 ... c2
两个事务基于对方将修改的数据做决策

异常严重程度递增:
脏写(P0) < 脏读(P1) < 不可重复读(P2) < 幻读(P3) < 写偏斜(P4) < 只读异常

隔离级别的形式化定义

使用Adya的广义隔离级别定义:

隔离级别与禁止的异常:
┌──────────────────┬────┬────┬────┬────┬────┬──────────┐
│ Isolation Level  │ P0 │ P1 │ P2 │ P3 │ P4 │ 其他异常 │
├──────────────────┼────┼────┼────┼────┼────┼──────────┤
│ Read Uncommitted │ ✗  │ ✓  │ ✓  │ ✓  │ ✓  │ ✓        │
│ Read Committed   │ ✗  │ ✗  │ ✓  │ ✓  │ ✓  │ ✓        │
│ Repeatable Read  │ ✗  │ ✗  │ ✗  │ ?  │ ✓  │ ✓        │
│ Snapshot Isolation│ ✗  │ ✗  │ ✗  │ ✗  │ ✓  │ ✓        │
│ Serializable     │ ✗  │ ✗  │ ✗  │ ✗  │ ✗  │ ✗        │
└──────────────────┴────┴────┴────┴────┴────┴──────────┘
✗ = 禁止, ✓ = 允许, ? = 实现相关

隔离性的实现技术

主要实现技术对比:

1. 悲观并发控制(PCC)
   ├── 两阶段锁(2PL)
   │   ├── 基本2PL
   │   ├── 严格2PL(S2PL)
   │   └── 强严格2PL(SS2PL)
   └── 时间戳排序(TO)
       ├── 基本TO
       └── 多版本TO(MVTO)

2. 乐观并发控制(OCC)
   ├── 验证阶段协议
   ├── 基于时间戳的OCC
   └── 分区OCC

3. 多版本并发控制(MVCC)
   ├── Snapshot Isolation(SI)
   ├── Serializable SI(SSI)
   └── Write Snapshot Isolation(WSI)

性能特征:
- 读密集型:MVCC > OCC > 2PL
- 写密集型:2PL > OCC > MVCC
- 长事务:MVCC > 2PL > OCC
- 短事务:OCC > 2PL > MVCC

持久性(Durability)

持久性保证已提交的事务修改永久保存,即使系统崩溃也不会丢失。现代系统的持久性设计需要在性能和可靠性之间权衡。

持久化层次

持久化保证强度金字塔:

         ┌─────────────┐
         │ 异地备份    │ ← 数据中心故障安全
        ┌┴─────────────┴┐
        │  同步复制      │ ← 节点故障安全
       ┌┴───────────────┴┐
       │  磁盘持久化      │ ← 单机故障安全
      ┌┴─────────────────┴┐
      │  磁盘缓存         │ ← 掉电不安全
     ┌┴───────────────────┴┐
     │  操作系统缓存       │ ← 进程崩溃安全
    ┌┴─────────────────────┴┐
    │  内存缓冲区           │ ← 无持久性
    └───────────────────────┘

每层的延迟特征:
- 内存缓冲区: ~100ns
- OS缓存: ~1μs
- SSD缓存: ~100μs
- SSD持久化: ~1ms
- HDD持久化: ~10ms
- 网络复制: ~1-10ms(局域网)
- 异地复制: ~10-100ms(广域网)

持久化技术实现

Write-Through vs Write-Back:

Write-Through(写穿):
Transaction → Buffer → Disk → Commit
优点:简单、可靠
缺点:延迟高

Write-Back(写回):
Transaction → Buffer → Commit
            ↓(异步)
           Disk
优点:低延迟
缺点:需要额外的恢复机制

混合策略:
- 日志:Write-Through(保证持久性)
- 数据页:Write-Back(优化性能)

复制与持久性

复制协议对持久性的影响:

同步复制(所有副本):
Primary → Replica1 → ACK
       → Replica2 → ACK
       → Replica3 → ACK
       → 等待所有ACK → Commit
持久性:最强,延迟:最高

半同步复制(至少一个副本):
Primary → Replica1 → ACK → Commit
       → Replica2(异步)
       → Replica3(异步)
持久性:强,延迟:中等

异步复制:
Primary → Commit
       → Replica1(异步)
       → Replica2(异步)
持久性:弱,延迟:最低

Quorum复制(W+R>N):
写入W个副本才算成功
读取R个副本取最新值
N=3, W=2, R=2:平衡持久性和性能

Rule of Thumb

隔离级别实现细节

Read Uncommitted实现

最弱的隔离级别,只防止脏写,允许脏读。

实现方式:
- 写锁(排他锁):写操作持有到事务结束
- 无读锁:读操作不加锁,可能读到未提交数据

使用场景

Read Committed实现

防止脏读,但允许不可重复读。

基于锁的实现(2PL变体)

锁协议:
- 写锁:持有到事务结束
- 读锁:读取后立即释放(短读锁)

时序示例:
T1: R(X) → 释放S锁(X) → ... → W(X) → 持有X锁(X)
T2: 等待X锁 → R(X) → 看到T1的修改(不可重复读)

基于MVCC的实现

版本可见性规则:
- 读取时获取当前已提交的最新版本
- 每次读取可能看到不同版本(快照不固定)

版本链示例:
X: v1(T1,committed) → v2(T2,active) → v3(T3,committed)
读取规则:忽略active版本,选择最新committed版本v3

Repeatable Read实现

防止不可重复读,但标准SQL允许幻读(实际实现各异)。

Snapshot Isolation(SI)

多数现代数据库的”Repeatable Read”实际实现SI:

快照获取时机:
- 事务开始时获取一致性快照
- 整个事务期间看到相同的数据版本

版本可见性判断:
visible(version) = 
    version.xid < snapshot.xmin OR
    (version.xid ∈ snapshot.active_xids AND version.xid = my_xid)

写-写冲突检测:
- First-committer-wins规则
- 后提交者若修改了先提交者的数据则回滚

MySQL InnoDB的Gap Lock

间隙锁机制:
- Next-Key Lock = Record Lock + Gap Lock
- 锁定索引记录及其前面的间隙
- 防止幻读的保守方案

示例:
索引值: 1, 5, 10, 20
SELECT * FROM t WHERE id > 5 AND id < 15 FOR UPDATE
锁定: (5,10] 和 (10,20) 的间隙

PostgreSQL的SSI(Serializable Snapshot Isolation)

依赖关系追踪:
- rw-dependency: T1读取的数据被T2修改
- ww-dependency: T1和T2修改相同数据
- wr-dependency: T1修改的数据被T2读取

危险结构检测:
T1 --rw--> T2 --rw--> T3 --rw--> T1(形成环)
检测到危险结构时回滚其中一个事务

Serializable实现

最强的隔离级别,保证事务的串行等价性。

严格两阶段锁(S2PL)

锁协议:
1. 扩展阶段:只能获取锁,不能释放
2. 收缩阶段:事务结束时释放所有锁

谓词锁优化:
- 索引范围锁:锁定索引范围而非所有记录
- 锁升级:细粒度锁过多时升级为粗粒度锁

串行执行

单线程执行模型(如VoltDB):
- 所有事务串行执行,无并发
- 吞吐量依赖于单核性能
- 适合内存数据库和短事务

分区串行执行:
- 数据分区,每个分区单线程
- 跨分区事务需要协调
- 热点分区成为瓶颈

Rule of Thumb

MVCC vs 2PL

MVCC(多版本并发控制)

核心机制

版本管理:
┌─────────┬──────────┬─────────┬─────────┐
│ Record  │ Version  │  XID    │ Status  │
├─────────┼──────────┼─────────┼─────────┤
│ Row-1   │ v1       │ 100     │ commit  │
│ Row-1   │ v2       │ 102     │ active  │
│ Row-2   │ v1       │ 101     │ commit  │
└─────────┴──────────┴─────────┴─────────┘

垃圾回收策略:
1. Reference Counting: 每个版本记录引用计数
2. Epoch-based: 定期扫描清理过期版本
3. Hybrid: 结合引用计数和定期清理

优势与劣势

优势

劣势

2PL(两阶段锁)

锁兼容性矩阵

        │   S   │   X   │  IS   │  IX   │  SIX  │
────────┼───────┼───────┼───────┼───────┼───────┤
   S    │   ✓   │   ✗   │   ✓   │   ✗   │   ✗   │
   X    │   ✗   │   ✗   │   ✗   │   ✗   │   ✗   │
   IS   │   ✓   │   ✗   │   ✓   │   ✓   │   ✓   │
   IX   │   ✗   │   ✗   │   ✓   │   ✓   │   ✗   │
   SIX  │   ✗   │   ✗   │   ✓   │   ✗   │   ✗   │

S: 共享锁  X: 排他锁  IS: 意向共享锁  IX: 意向排他锁  SIX: 共享意向排他锁

死锁处理

等待图(Wait-for Graph):
T1 ──等待──> T2 ──等待──> T3 ──等待──> T1
         检测到环 → 选择受害者回滚

受害者选择策略:
1. 最年轻事务(开始时间最晚)
2. 最少工作量(修改最少)
3. 最低优先级
4. 非交互式事务优先

混合方案

现代数据库often结合MVCC和2PL:

MySQL InnoDB:
- MVCC用于读操作(非锁定读)
- 2PL用于写操作和锁定读
- Gap Lock防止幻读

PostgreSQL:
- MVCC为主要机制
- 轻量级锁用于写冲突检测
- SSI用于可串行化隔离

Oracle:
- MVCC(称为多版本读一致性)
- 行级锁用于写操作
- 无读锁(通过MVCC实现)

选择建议

死锁检测与预防

死锁的四个必要条件

死锁发生需要同时满足以下四个条件(Coffman条件):

  1. 互斥条件:资源不能被共享,只能被一个事务占用
  2. 持有并等待:事务持有至少一个资源,并等待其他资源
  3. 不可剥夺:资源只能由持有者主动释放
  4. 循环等待:存在事务的循环等待链

死锁预防策略

Wait-Die / Wound-Wait协议

基于时间戳的死锁预防,每个事务分配唯一时间戳:

Wait-Die(非抢占):
if (T_requesting.timestamp < T_holding.timestamp)
    T_requesting等待
else
    T_requesting终止(Die)并稍后重试

Wound-Wait(抢占):
if (T_requesting.timestamp < T_holding.timestamp)
    T_holding被终止(Wounded)
else
    T_requesting等待

特性比较

有序资源分配

资源编号方案:
1. 表级别:按表名字典序
2. 页级别:按页ID大小
3. 记录级别:按主键顺序

锁获取规则:
- 总是按照资源编号递增顺序获取锁
- 违反顺序时立即回滚

示例:
T1: Lock(A) → Lock(B) → Lock(C)  ✓
T2: Lock(B) → Lock(A) → 违反顺序,回滚

死锁检测算法

等待图检测

数据结构:
struct WaitForGraph {
    nodes: Set<TransactionID>
    edges: Map<TransactionID, Set<TransactionID>>
    
    addEdge(from: TID, to: TID) {
        edges[from].add(to)
        if (hasCycle()) {
            selectVictim()
        }
    }
}

环检测算法(DFS):
function hasCycle(graph):
    visited = {}
    recStack = {}
    for node in graph.nodes:
        if detectCycleDFS(node, visited, recStack):
            return true
    return false

时间复杂度:O(V + E)
空间复杂度:O(V)

超时检测

简单超时策略:
- 设置锁等待超时时间(如30秒)
- 超时后回滚事务
- 优点:实现简单,无需全局协调
- 缺点:可能误判,非真正死锁也会超时

自适应超时:
timeout = base_timeout × (1 + conflict_rate)
- conflict_rate根据历史统计动态调整
- 高冲突时增加超时时间,减少误判

死锁处理

受害者选择

优先级计算:
priority = α × age + β × work_done + γ × locks_held + δ × user_priority

参数说明:
- age: 事务运行时间(倾向保留老事务)
- work_done: 已完成的操作数(减少回滚代价)
- locks_held: 持有锁数量(释放更多资源)
- user_priority: 用户定义优先级

典型权重:α=0.3, β=0.4, γ=0.2, δ=0.1

回滚策略

完全回滚 vs 部分回滚:

完全回滚:
- 回滚整个事务到开始状态
- 实现简单,恢复彻底
- 代价可能很大

部分回滚(到安全点):
- 设置保存点(Savepoint)
- 回滚到最近的无冲突保存点
- 减少重做工作量

保存点管理:
SAVEPOINT sp1
... operations ...
SAVEPOINT sp2
... operations ...
检测到死锁 → ROLLBACK TO sp1

Rule of Thumb

长事务优化

长事务的影响

系统影响分析:
1. 锁持有时间 ∝ 事务长度 → 并发度下降
2. Undo log大小 ∝ 事务长度 × 修改量
3. 垃圾回收延迟 = min(活跃事务开始时间)
4. 内存占用 = 活跃版本数 × 版本大小

优化策略

事务拆分

拆分原则:
1. 业务边界拆分
   原始:BEGIN → 订单 → 库存 → 支付 → 通知 → COMMIT
   优化:订单事务 → 库存事务 → 支付事务(补偿机制)

2. 批量操作拆分
   原始:UPDATE million_rows SET status = 'processed'
   优化:
   for batch in chunks(1000):
       BEGIN
       UPDATE ... WHERE id BETWEEN batch.start AND batch.end
       COMMIT

3. 读写分离
   原始:长时间分析 + 最后更新统计表
   优化:只读事务分析 → 独立写事务更新

乐观锁替代

悲观锁(传统):
BEGIN
SELECT * FROM account WHERE id = 1 FOR UPDATE  -- 锁定
... 长时间处理 ...
UPDATE account SET balance = new_balance
COMMIT

乐观锁(优化):
SELECT version, balance FROM account WHERE id = 1  -- 不锁定
... 长时间处理 ...
BEGIN
UPDATE account SET balance = new_balance, version = version + 1
WHERE id = 1 AND version = old_version
IF (affected_rows == 0) RETRY
COMMIT

快照读取

MVCC快照优化:
-- 长时间只读分析
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ READ ONLY
BEGIN
... 复杂分析查询 ...
COMMIT

优势:
- 不阻塞写事务
- 不持有锁
- 一致性视图

监控与诊断

长事务监控指标:
1. 事务持续时间分布(P50, P95, P99)
2. 锁等待队列长度
3. 活跃事务数量趋势
4. Undo log增长速率
5. 版本链长度分布

诊断查询示例(MySQL):
SELECT 
    trx_id,
    trx_started,
    TIMESTAMPDIFF(SECOND, trx_started, NOW()) as duration,
    trx_rows_locked,
    trx_rows_modified
FROM information_schema.innodb_trx
WHERE TIMESTAMPDIFF(SECOND, trx_started, NOW()) > 60
ORDER BY duration DESC;

长事务恢复

崩溃恢复优化:
1. 增量检查点
   - 定期刷新脏页,减少恢复时的redo
   - 检查点间隔 = f(脏页比例, IO负载)

2. 并行恢复
   - Redo日志按页ID分片
   - 多线程并行应用不冲突的日志

3. 快速回滚
   - 延迟undo(只标记,后台清理)
   - 优先恢复热点数据

恢复时间估算:
recovery_time = redo_size / redo_apply_rate + undo_size / undo_apply_rate
典型值:100MB/s redo应用速率,50MB/s undo应用速率

Rule of Thumb

本章小结

核心概念回顾

  1. ACID属性
    • 原子性通过undo/redo日志实现
    • 一致性依赖约束检查和触发器
    • 隔离性通过并发控制(MVCC/2PL)保证
    • 持久性需要WAL和复制机制
  2. 隔离级别谱系
    • Read Uncommitted → Read Committed → Repeatable Read → Serializable
    • 隔离级别越高,异常越少,但并发性能越低
    • 实际实现often偏离SQL标准(如SI代替RR)
  3. 并发控制对比
    • MVCC:读写不冲突,空间换时间
    • 2PL:简单直接,但锁竞争严重
    • 混合方案:结合两者优势
  4. 死锁处理
    • 预防:有序加锁、Wait-Die/Wound-Wait
    • 检测:等待图、超时机制
    • 恢复:选择受害者、部分回滚
  5. 长事务优化
    • 拆分策略:业务边界、批量处理
    • 乐观控制:减少锁持有时间
    • 监控诊断:及时发现和处理

关键公式

  1. 事务吞吐量: \(TPS = \frac{N_{concurrent}}{T_{transaction}} \times (1 - P_{conflict})\)

  2. 死锁概率(简化模型): \(P_{deadlock} \approx \frac{n^2 \times p^2}{2}\) 其中n为并发事务数,p为资源冲突概率

  3. MVCC空间开销: \(Space_{overhead} = N_{versions} \times Size_{version} \times T_{retention}\)

  4. 恢复时间估算: \(T_{recovery} = \frac{Size_{redo}}{Rate_{redo}} + \frac{Size_{undo}}{Rate_{undo}}\)

练习题

基础题

习题4.1:解释为什么在MVCC系统中,长事务会影响垃圾回收?

提示 考虑版本可见性规则和快照的概念。
答案 在MVCC系统中,每个事务开始时获取一个快照,该快照决定了事务能看到哪些数据版本。长事务持有的快照可能很旧,这意味着: 1. 系统必须保留该快照时刻之后的所有版本,即使这些版本对其他事务已经不可见 2. 垃圾回收器不能清理任何在最老活跃事务快照之后创建的版本 3. 版本链会不断增长,导致: - 存储空间浪费 - 查询性能下降(需要遍历更长的版本链) - 内存压力增加 解决方案包括:设置事务超时、使用只读事务、定期重启长事务等。

习题4.2:比较Wound-Wait和Wait-Die协议,哪种情况下各自更优?

提示 考虑事务的重启代价和等待时间。
答案 **Wait-Die更优的场景**: - 事务重启代价低(短事务、只读操作多) - 系统倾向于保护老事务的投资 - 新事务到达率高但生命周期短 **Wound-Wait更优的场景**: - 事务重启代价高(长事务、大量写操作) - 需要减少事务等待时间 - 老事务优先级确实更高(如付费用户) 关键区别: - Wait-Die中被终止的是请求者(年轻事务),可能会反复重启 - Wound-Wait中被终止的是持有者,但只会被终止一次 - Wound-Wait通常导致更少的重启次数,但可能浪费更多已完成的工作

习题4.3:在2PL协议下,为什么需要意向锁(Intention Lock)?

提示 考虑多粒度锁和锁兼容性检查的效率。
答案 意向锁解决多粒度锁系统中的效率问题: 1. **问题场景**: - T1要锁定整个表(表级X锁) - T2已经锁定了表中某一行(行级X锁) - 如何快速检测冲突? 2. **无意向锁的问题**: - 需要遍历检查表中所有行的锁状态 - O(n)的时间复杂度,n为表中行数 3. **意向锁的解决**: - T2在获取行级X锁前,先在表级获取IX锁 - T1检查表级锁时,立即发现IX锁冲突 - O(1)的冲突检测 4. **层次规则**: - 获取S锁:IS锁自顶向下,最后获取S锁 - 获取X锁:IX锁自顶向下,最后获取X锁 - 释放:自底向上释放所有锁

挑战题

习题4.4:设计一个乐观并发控制(OCC)协议,要求支持只读事务的快速路径。描述验证阶段的算法。

提示 考虑如何区分只读和读写事务,以及如何减少验证开销。
答案 **OCC协议设计**: 1. **事务阶段**: ``` Read Phase: 读取数据到私有空间,记录读集合 Validation Phase: 检查冲突 Write Phase: 如果验证通过,写入数据 ``` 2. **时间戳分配**: - 只读事务:开始时分配时间戳 - 读写事务:验证开始时分配时间戳 3. **验证算法**: ```python def validate(T_new): if T_new.is_readonly(): # 快速路径:只读事务总是成功 return True T_new.timestamp = get_next_timestamp() for T_old in committed_transactions: if T_old.timestamp < T_new.start_time: continue # T_old在T_new开始前提交,无冲突 if T_old.timestamp < T_new.timestamp: # 检查写-读冲突 if T_old.write_set ∩ T_new.read_set ≠ ∅: return False # 冲突,验证失败 # 检查写-写冲突 if T_old.write_set ∩ T_new.write_set ≠ ∅: return False # 冲突,验证失败 return True # 验证成功 ``` 4. **优化**: - 只读事务无需验证,直接提交 - 使用Bloom Filter加速集合交集检查 - 分区验证减少全局协调

习题4.5:在分布式数据库中,如何实现全局的Snapshot Isolation?考虑时钟偏差问题。

提示 参考Google Spanner的TrueTime或HLC(Hybrid Logical Clock)。
答案 **分布式Snapshot Isolation实现**: 1. **全局时间戳方案**: a) **中心化时间戳服务器**: ``` - 单点分配全局唯一时间戳 - 优点:简单、一致 - 缺点:单点故障、性能瓶颈 ``` b) **TrueTime方案(Spanner)**: ``` - GPS + 原子钟提供有界误差的时间 - 等待不确定性窗口确保因果一致性 - commit_timestamp = TT.now().latest - 等待直到 TT.now().earliest > commit_timestamp ``` c) **HLC(Hybrid Logical Clock)**: ``` HLC = (physical_time, logical_counter, node_id) 更新规则: - 本地事件:hlc.physical = max(hlc.physical, wall_clock) - 接收消息:hlc.physical = max(hlc.physical, msg.hlc.physical, wall_clock) - 如果physical相同,递增logical_counter ``` 2. **快照获取协议**: ```python class DistributedSnapshot: def begin_transaction(): snapshot_ts = get_global_timestamp() # 广播给所有节点 for node in all_nodes: node.register_snapshot(snapshot_ts) return snapshot_ts def read(key, snapshot_ts): versions = get_versions(key) # 找到快照可见的最新版本 for v in versions.reverse(): if v.commit_ts <= snapshot_ts and v.status == COMMITTED: return v.value return None ``` 3. **处理时钟偏差**: ``` - 最大时钟偏差:ε(如10ms) - 提交等待:等待ε时间确保全局可见 - 读取等待:如果版本时间戳在[now-ε, now+ε]内,等待确定 ``` 4. **优化策略**: - 本地快照:同一节点的事务共享快照 - 快照推进:定期推进最小活跃快照 - 因果一致性令牌:客户端携带已见最大时间戳

习题4.6:证明在Snapshot Isolation下,写偏斜(Write Skew)异常是可能发生的,并设计一个检测机制。

提示 构造一个具体的写偏斜场景,然后考虑如何追踪读写依赖。
答案 **写偏斜示例**: 场景:医院值班系统,要求至少一名医生值班 ```sql -- 初始状态:Alice和Bob都在值班 -- T1: Alice请假 BEGIN SELECT COUNT(*) FROM doctors WHERE on_duty = true -- 返回2 -- 检查通过(2-1 >= 1) UPDATE doctors SET on_duty = false WHERE name = 'Alice' COMMIT -- T2: Bob同时请假 BEGIN SELECT COUNT(*) FROM doctors WHERE on_duty = true -- 返回2 -- 检查通过(2-1 >= 1) UPDATE doctors SET on_duty = false WHERE name = 'Bob' COMMIT -- 结果:无人值班,违反约束! ``` **证明**: 1. 两个事务读取相同的快照(都看到2个医生值班) 2. 各自基于快照做出决策(可以请假) 3. 写入不同的记录(无写-写冲突) 4. SI下两个事务都成功提交 5. 最终状态违反业务约束 **检测机制设计**: ```python class WriteSkewDetector: def __init__(self): self.read_deps = {} # txn -> {read items} self.write_deps = {} # txn -> {written items} def track_read(self, txn_id, item, predicate=None): if txn_id not in self.read_deps: self.read_deps[txn_id] = set() self.read_deps[txn_id].add((item, predicate)) def validate_write_skew(self, txn_id): """ 检测危险结构: T1 --read--> Data <--read-- T2 | | v v Write X Write Y """ my_reads = self.read_deps.get(txn_id, set()) my_writes = self.write_deps.get(txn_id, set()) for other_txn in concurrent_transactions: if other_txn == txn_id: continue other_reads = self.read_deps.get(other_txn, set()) other_writes = self.write_deps.get(other_txn, set()) # 检查是否读取了相同的数据 common_reads = my_reads & other_reads if common_reads: # 检查是否各自写入了不同的数据 if my_writes and other_writes: if my_writes & other_writes == set(): # 检测到写偏斜模式 return False return True def prevent_write_skew(self, txn_id): """预防策略:提升读锁为写锁""" # 方案1:SELECT FOR UPDATE # 方案2:物化冲突(创建锁表) # 方案3:使用SSI而非SI pass ``` **预防方案**: 1. **显式锁定**:SELECT ... FOR UPDATE 2. **物化冲突**:创建额外表记录约束 3. **SSI**:自动检测并阻止写偏斜 4. **应用层重试**:乐观锁 + 版本号检查

常见陷阱与错误

1. 隔离级别误解

陷阱:认为Repeatable Read完全防止幻读

-- MySQL InnoDB的RR实际使用Gap Lock防止幻读
-- 但PostgreSQL的RR(实际是SI)允许幻读

正确理解

2. 死锁处理不当

陷阱:忽略死锁重试

# 错误:死锁后直接失败
try:
    execute_transaction()
except DeadlockError:
    raise  # 用户看到错误

# 正确:自动重试
for attempt in range(MAX_RETRIES):
    try:
        execute_transaction()
        break
    except DeadlockError:
        if attempt == MAX_RETRIES - 1:
            raise
        time.sleep(exponential_backoff(attempt))

3. 长事务陷阱

陷阱:在事务中执行耗时操作

# 错误:事务中调用外部API
BEGIN
SELECT * FROM users WHERE id = 1
result = call_external_api()  # 可能需要几秒
UPDATE users SET status = result
COMMIT

# 正确:事务外准备数据
result = call_external_api()
BEGIN
SELECT * FROM users WHERE id = 1
UPDATE users SET status = result
COMMIT

4. MVCC垃圾回收

陷阱:忽视版本累积的影响

-- 监控版本链长度
SELECT MAX(version_count) 
FROM pg_stat_user_tables;

-- 定期检查膨胀
SELECT schemaname, tablename, 
       pg_size_pretty(pg_total_relation_size(schemaname||'.'||tablename)) AS size,
       n_dead_tup, n_live_tup,
       round(n_dead_tup::numeric / NULLIF(n_live_tup, 0), 2) AS dead_ratio
FROM pg_stat_user_tables
WHERE n_dead_tup > 1000
ORDER BY dead_ratio DESC;

5. 乐观锁失败处理

陷阱:无限重试导致活锁

# 错误:无退避的重试
while True:
    if try_optimistic_update():
        break

# 正确:指数退避 + 最大重试
for attempt in range(MAX_RETRIES):
    if try_optimistic_update():
        break
    if attempt < MAX_RETRIES - 1:
        time.sleep(min(2 ** attempt * 0.1, 2.0))
    else:
        # 降级到悲观锁
        do_pessimistic_update()

调试技巧

  1. 事务追踪
    -- 启用事务日志
    SET log_transaction = ON;
    SET log_lock_waits = ON;
    
  2. 锁等待分析
    -- 查看锁等待
    SELECT * FROM pg_locks WHERE NOT granted;
    
  3. 死锁日志分析: ``` 解析死锁日志关键信息:
    • 涉及的事务ID
    • 等待的资源
    • 持有的锁
    • 事务执行的语句 ```
  4. 性能诊断
    -- 事务延迟分析
    SELECT 
        query,
        mean_exec_time,
        stddev_exec_time,
        calls
    FROM pg_stat_statements
    WHERE mean_exec_time > 1000
    ORDER BY mean_exec_time DESC;