并发控制是数据库系统的核心挑战之一。当多个事务同时访问共享数据时，如何保证数据的一致性、避免冲突、同时最大化系统吞吐量？本章深入探讨各种并发控制机制的设计原理、实现细节和性能权衡。我们将从传统的锁机制出发，逐步扩展到乐观并发控制、时间戳排序等无锁方案，最后讨论如何根据工作负载特征选择和组合不同的策略。
锁管理器是悲观并发控制的核心组件，负责协调事务对数据资源的访问。一个高效的锁管理器需要在保证正确性的前提下，最小化锁操作的开销，减少锁冲突，并支持灵活的锁粒度。
数据库系统通常支持多级锁粒度，形成一个层次结构。这种层次化设计允许系统在并发性和开销之间找到最优平衡点。
Database
↓
Table/Relation
↓
Partition (分区表)
↓
Page/Block (通常4KB-16KB)
↓
Tuple/Row
↓
Attribute/Field
粒度选择的权衡：
动态粒度选择算法： 系统可以根据操作特征动态选择锁粒度。考虑因素包括：
锁粒度的成本模型： \(\text{Cost} = \text{LockOverhead} \times \text{NumLocks} + \text{ConflictProbability} \times \text{ConflictCost}\)
其中：
实际系统中的粒度选择：
Rule of Thumb：
锁表是锁管理器的核心数据结构，需要支持高效的查找、插入和删除操作。现代数据库系统的锁表设计必须考虑多核扩展性和缓存友好性。
基本设计：
Lock Table (Hash Table)
↓
Bucket → Lock Header → Lock Request Queue
├─ Resource ID (表ID + 页ID + 行ID)
├─ Lock Mode Bitmap
├─ Granted List (已授予锁的事务列表)
├─ Waiting Queue (等待锁的事务队列)
└─ Reference Count
详细数据结构：
struct LockHeader {
ResourceID resource_id; // 资源标识符
uint32_t granted_modes; // 已授予锁模式的位图
uint32_t waiting_modes; // 等待中锁模式的位图
List<LockRequest> granted; // 已授予队列
Queue<LockRequest> waiting; // 等待队列
atomic<int> ref_count; // 引用计数
SpinLock latch; // 保护该锁头的轻量级锁
};
struct LockRequest {
TransactionID txn_id; // 事务ID
LockMode mode; // 请求的锁模式
GrantStatus status; // GRANTED/WAITING/CONVERTING
LockRequest* next; // 链表指针
ConditionVariable cv; // 用于等待通知
};
关键优化技术：
分片数 = 2^n (通常为CPU核数的2-4倍)
分片索引 = hash(resource_id) & (num_shards - 1)
每个分片独立的锁保护，减少争用
锁兼容性矩阵：
| IS | IX | S | SIX | X | U | AI | AX
-----|----|----|----|----|----|----|----|----|
IS | ✓ | ✓ | ✓ | ✓ | ✗ | ✓ | ✓ | ✗
IX | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗
S | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ | ✓ | ✗
SIX | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✗
X | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗
U | ✓ | ✗ | ✓ | ✗ | ✗ | ✗ | ✓ | ✗
AI | ✓ | ✓ | ✓ | ✓ | ✗ | ✓ | ✗ | ✗
AX | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | ✗
其中：
快速兼容性检查： 使用位运算加速兼容性判断：
bool is_compatible(uint32_t granted_modes, LockMode requested) {
return (compatibility_matrix[requested] & granted_modes) == 0;
}
意向锁是多粒度锁协议的关键创新，它通过在粗粒度级别标记细粒度锁的存在，极大地提高了锁冲突检测的效率。没有意向锁，系统需要遍历所有子节点才能判断是否存在冲突。
工作原理：
意向锁的类型与含义：
多粒度锁协议（MGL Protocol）规则：
获取锁的完整流程：
要在行R上获取X锁：
1. 获取数据库级IX锁
2. 获取表级IX锁
3. 获取页级IX锁（如果使用页锁）
4. 获取行级X锁
伪代码：
function acquire_lock(resource, mode):
path = get_hierarchy_path(resource)
for level in path[:-1]: // 除了目标资源外的所有祖先
if mode == SHARED:
acquire(level, IS)
else: // EXCLUSIVE
acquire(level, IX)
acquire(resource, mode)
意向锁的优化实现：
死锁预防： 意向锁协议天然防止某些死锁场景：
场景：T1持有行锁，T2请求表锁
没有意向锁：T2需要检查所有行，可能形成死锁
有意向锁：T2立即发现表级IX锁，直接等待
性能影响分析：
锁升级是数据库系统平衡内存使用和并发性能的重要机制。当细粒度锁数量过多时，不仅消耗大量内存，锁管理的CPU开销也会显著增加。
锁升级（Lock Escalation）： 当事务持有大量细粒度锁时，自动转换为粗粒度锁。这是一个权衡：牺牲一定的并发性来换取更低的管理开销。
升级触发条件：
1. 数量阈值触发：
- 单事务持有锁数 > 5000
- 或 > 表总行数的 5%
2. 内存压力触发：
- 锁表内存使用 > 分配内存的 60%
- 系统总内存压力达到阈值
3. 模式识别触发：
- 检测到全表扫描模式
- 连续页访问超过阈值
- 批量DML操作
升级算法：
function try_lock_escalation(transaction, table):
if should_escalate(transaction, table):
// 尝试获取表级锁
if try_acquire_table_lock(table, transaction.lock_mode):
// 释放所有行级锁
for each row_lock in transaction.locks[table]:
release(row_lock)
// 更新锁记录
transaction.locks[table] = [table_lock]
return SUCCESS
else:
// 升级失败，保持原状或等待
return RETRY_LATER
升级策略选择：
锁降级（Lock De-escalation）： 较少见，主要用于长事务释放部分资源。某些高级系统支持部分降级。
降级场景：
1. 长事务完成批量操作后，只需保留少量锁
2. 内存压力缓解后，恢复细粒度锁以提高并发
3. 工作负载模式改变（从批量变为OLTP）
升级的代价分析：
智能升级策略：
class SmartEscalation:
def __init__(self):
self.history = {} # 记录历史升级效果
def should_escalate(self, txn, table):
# 基础检查
if txn.lock_count[table] < self.threshold:
return False
# 历史效果评估
if table in self.history:
past_benefit = self.history[table].benefit_ratio
if past_benefit < 0.5: # 历史升级效果不好
return False
# 并发影响评估
waiting_txns = get_waiting_transactions(table)
if len(waiting_txns) > 5: # 太多事务在等待
return False
# 工作负载预测
if is_oltp_workload(table):
return False # OLTP不适合表锁
return True
Rule of Thumb：
锁管理器必须能够检测和解决死锁。
检测算法：
解决策略：
乐观并发控制（OCC）假设冲突很少发生，事务执行时不加锁，只在提交时检查冲突。
OCC将事务执行分为三个阶段：
1. 读阶段（Read Phase）：
2. 验证阶段（Validation Phase）：
3. 写阶段（Write Phase）：
向后验证（Backward Validation）： 检查当前事务的读集是否与已提交事务的写集冲突。
算法伪代码：
for each committed transaction Ti where Ti < Tc:
if WriteSet(Ti) ∩ ReadSet(Tc) ≠ ∅:
abort Tc
向前验证（Forward Validation）： 检查当前事务的写集是否与活跃事务的读集冲突。
算法伪代码：
for each active transaction Ti:
if WriteSet(Tc) ∩ ReadSet(Ti) ≠ ∅:
abort Tc or Ti (based on policy)
性能优化：
写集的高效管理对OCC性能至关重要。
实现方案：
内存管理策略：
适合OCC的工作负载特征：
不适合OCC的场景：
Rule of Thumb：
时间戳排序（Timestamp Ordering, TO）是另一种无锁并发控制方法，通过为每个事务分配唯一时间戳来确定序列化顺序。
核心思想：
读操作规则：
if TS(Ti) < WTS(X):
// 读取过时数据，违反序列化顺序
abort Ti
else:
执行读操作
RTS(X) = max(RTS(X), TS(Ti))
写操作规则：
if TS(Ti) < RTS(X) or TS(Ti) < WTS(X):
// 写入会影响已发生的读或写
abort Ti
else:
执行写操作
WTS(X) = TS(Ti)
Thomas写规则是对基本TO协议的优化，减少不必要的事务中止。
优化规则：
if TS(Ti) < RTS(X):
abort Ti // 仍需中止
elif TS(Ti) < WTS(X):
忽略写操作 // 写被后续事务覆盖，可以安全忽略
else:
执行写操作
WTS(X) = TS(Ti)
优势：
MVTO结合多版本和时间戳排序，提供更好的并发性。
数据结构： 每个数据项X维护版本链：
X → [Version1: (value, WTS, RTS)]
→ [Version2: (value, WTS, RTS)]
→ ...
读操作：
找到最大的版本k，使得WTS(Xk) ≤ TS(Ti)
if 没有这样的版本:
等待或使用默认值
else:
读取Xk
RTS(Xk) = max(RTS(Xk), TS(Ti))
写操作：
找到最大的版本k，使得WTS(Xk) ≤ TS(Ti)
if TS(Ti) < RTS(Xk):
abort Ti // 会影响已发生的读
elif TS(Ti) = WTS(Xk):
覆盖版本k
else:
创建新版本
垃圾回收：
1. 系统时钟：
2. 逻辑计数器：
3. 混合时间戳：
Timestamp = (Physical_Clock << 16) | Counter
4. 向量时间戳（分布式系统）：
优势：
劣势：
Rule of Thumb：
现实系统往往结合多种并发控制机制，根据工作负载特征动态选择最优策略。
基本架构：
Monitor → Analyzer → Selector → Executor
↑ ↓
└────── Feedback Loop ←──────────┘
监控指标：
切换策略：
if abort_rate > threshold_high:
切换到悲观锁
elif abort_rate < threshold_low and conflict_rate < threshold:
切换到OCC
else:
保持当前策略
平滑切换机制：
不同数据分区使用不同的并发控制策略。
分区策略选择：
热点分区：2PL（悲观锁）
冷数据分区：OCC
只读分区：MVCC快照读
时序数据分区：追加写+TO
跨分区事务处理：
OLTP优化：
OLAP优化：
HTAP混合负载：
预测模型：
在线学习：
特征向量 = [
事务类型,
访问数据量,
读写比例,
历史冲突率,
当前系统负载
]
策略 = ML_Model.predict(特征向量)
强化学习应用：
热点数据是指被频繁访问的数据项，它们往往成为系统的性能瓶颈。有效的热点处理策略对于维持系统的可扩展性至关重要。
访问频率统计：
每个数据项维护：
- access_count：访问计数
- last_access_time：最后访问时间
- access_pattern：访问模式（读/写比例）
热点判定：
if access_count > threshold * avg_access_count:
标记为热点
滑动窗口算法：
维护最近N秒的访问历史
使用指数衰减权重：weight = e^(-λ * age)
热度分数 = Σ(access_i * weight_i)
自适应阈值：
分布式热点检测：
1. 数据分片（Sharding）：
原始热点：Counter X
分片方案：X → [X1, X2, ..., Xn]
写操作：随机选择分片Xi进行更新
读操作：Sum(X1, X2, ..., Xn)
优势：分散写压力 劣势：读操作开销增加
2. 缓存层优化：
3. 乐观锁升级：
if 检测到热点:
从悲观锁切换到OCC
使用批量验证减少开销
4. 读写分离：
动态分区：
监控分区负载
if 负载不均衡:
识别热点键范围
创建新分区
迁移部分数据
更新路由表
智能复制：
一致性哈希优化：
虚拟节点映射：
热点数据 → 更多虚拟节点
均匀分布负载
批量处理：
收集时间窗口内的请求
批量执行：
UPDATE counter SET value = value + batch_sum
请求合并：
限流与降级：
if 访问频率 > 限制:
返回缓存结果
或返回降级响应
异步处理：
计数器场景：
排行榜场景：
库存扣减：
秒杀场景：
Rule of Thumb：
并发控制是数据库系统保证事务正确执行的核心机制。本章深入探讨了多种并发控制策略：
并发度估算： \(\text{Concurrency} = \frac{N}{1 + \alpha \cdot (N-1)}\) 其中N是并发事务数，α是冲突概率
最优锁粒度选择： \(\text{Granularity} = \arg\min_{g} \left( \text{LockOverhead}(g) + \text{ConflictCost}(g) \right)\)
OCC中止率预测： \(P_{abort} = 1 - (1 - p)^{n-1}\) 其中p是单个操作冲突概率，n是事务操作数
热点分片数量： \(\text{Shards} = \lceil \sqrt{\text{ExpectedConcurrency}} \rceil\)
| 场景 | 推荐策略 | 原因 |
|---|---|---|
| 短事务、低冲突 | OCC | 无锁开销，高吞吐量 |
| 高冲突OLTP | 2PL + 细粒度锁 | 避免大量重试 |
| 只读查询为主 | MVCC | 读不阻塞写 |
| 混合负载 | 自适应/分区策略 | 针对性优化 |
| 存在热点 | 分片 + 缓存 | 分散负载 |
练习5.1 锁兼容性矩阵 给定事务序列：
使用二阶段锁协议，判断哪些操作会被阻塞？画出等待图。
提示：按时间顺序分析每个操作的锁请求
练习5.2 OCC验证 考虑三个事务的时间戳和操作：
如果T2先验证，T3后验证，使用向后验证算法，哪个事务会被中止？
提示：检查读集与已提交事务写集的交集
练习5.3 时间戳排序 给定数据项初始时间戳：WTS(X)=0, RTS(X)=0 事务序列：
哪些操作会被拒绝？
提示：比较事务时间戳与数据项时间戳
练习5.4 混合并发控制设计 设计一个自适应并发控制系统，根据以下指标动态切换策略：
要求：给出状态转换图和切换算法伪代码。
提示：考虑滞后效应避免频繁切换
练习5.5 热点优化方案 某电商系统的商品库存表成为热点，每秒10000次扣减操作。设计一个综合优化方案，包括：
提示：考虑最终一致性的可接受性
练习5.6 死锁预防算法 实现Wait-Die和Wound-Wait死锁预防算法，分析它们的优缺点。
提示：基于时间戳的优先级
练习5.7 MVCC垃圾回收 设计一个MVCC系统的垃圾回收算法，需要考虑：
提示：维护活跃事务的最小时间戳
错误：盲目使用细粒度锁
问题：管理开销超过并发收益
症状：CPU利用率高但吞吐量低
正确做法：根据访问模式选择合适粒度
错误：频繁触发锁升级
问题：突然的并发度下降
症状：性能抖动
正确做法：监控锁升级频率，调整阈值或优化查询
错误：高冲突场景使用OCC
问题：大量事务反复重试
症状：延迟激增，CPU空转
正确做法：设置重试上限，自动降级到悲观锁
错误：使用全局计数器
问题：成为系统瓶颈
症状：所有事务在时间戳分配处排队
正确做法：使用分布式时间戳或混合方案
错误：不及时回收旧版本
问题：内存爆炸，查询性能下降
症状：版本链遍历时间增长
正确做法：积极的垃圾回收，限制长事务
错误：每次锁请求都检测死锁
问题：O(n²)复杂度导致性能问题
症状：锁管理器成为瓶颈
正确做法：周期性检测或使用超时机制
错误：静态阈值判断热点
问题：无法适应负载变化
症状：真正的热点未被识别
正确做法：动态阈值 + 预测模型
错误：缓存与数据库不一致
问题：读到过期数据
症状：业务逻辑错误
正确做法：Cache-Aside模式 + 版本号验证
SHOW ENGINE INNODB STATUS查看锁信息记住：并发控制没有银弹，理解工作负载特征是选择正确策略的关键。