Modeling Concurrency Control as a Learnable Function

本文提出了 NeurCC，一种基于贝叶斯优化和图归约搜索算法的新型可学习并发控制机制，它通过高效映射数据库状态到控制动作的查找表，在多样化及动态变化的工作负载下实现了比现有最先进算法更高的事务吞吐量和优化速度。

要点

这篇论文介绍了一个名为 NeurCC 的新技术，它旨在解决数据库管理中一个非常棘手的问题：如何同时保证数据不出错，又能让成千上万个任务跑得飞快？

为了让你更容易理解，我们可以把数据库想象成一个繁忙的超级厨房，把数据库里的“事务”（Transaction）想象成厨师，把“并发控制”（Concurrency Control）想象成厨房里的调度规则。

1. 核心痛点：老规矩不够用了

在传统的厨房里（传统数据库），有两种主要的调度规则：

• 规则 A（像 2PL 锁机制）： 只要一个厨师拿起了炒锅（锁住数据），其他厨师就必须排队等着，直到他炒完。
  • 优点： 绝对不会乱，菜不会做坏。
  • 缺点： 如果大家都抢同一个锅，厨房就堵死了，效率极低。
• 规则 B（像 OCC 乐观机制）： 厨师们先不管别人，自己随便炒。等最后要上菜（提交）时，再检查有没有人抢了锅。如果有冲突，就把刚才炒的菜全倒掉（回滚），重新炒。
  • 优点： 平时大家都能跑，速度很快。
  • 缺点： 如果厨房太忙，大家经常撞车，最后倒掉重做的成本太高，反而更慢。

问题在于： 现实中的厨房情况是千变万化的。有时候大家抢同一个锅（高冲突），有时候大家各炒各的（低冲突）。以前的系统要么死板地用规则 A，要么死板地用规则 B，或者需要人工去调整。一旦 workload（工作负载）变了（比如突然来了个大单，或者大家突然都去抢盐了），旧规则就失效了，导致厨房要么堵车，要么频繁倒菜。

2. NeurCC 是什么？一个“会学习的超级调度员”

NeurCC 的核心思想是：别死守规则，让系统自己“学”出最好的规则。

作者把并发控制看作一个可以学习的函数（就像一个超级大脑）。

• 输入（状态）： 厨房现在的状态（比如：谁在抢什么？冲突多吗？数据是热的还是冷的？）。
• 输出（动作）： 调度员给出的指令（比如：是继续炒？是停下来等？还是直接倒掉重做？给谁优先权？）。

它的创新之处在于：
以前的系统只能从几个固定的规则里选（要么选 A，要么选 B）。NeurCC 则像一个乐高大师，它把现有的规则拆成了无数个小积木（比如：检测冲突、等待时间、优先级排序、是否允许看未完成的菜等）。它可以根据当前的情况，自由组合这些积木，创造出最适合当下场景的“混合规则”。

3. 它是怎么“学”的？（两个绝招）

让系统自己学规则很难，因为试错成本太高（在数据库里试错意味着性能下降）。NeurCC 用了两个聪明的办法来加速学习：

绝招一：替身演员（贝叶斯优化 + 代理模型）

想象一下，你想找一条最快的开车路线。

• 笨办法： 每次都要真的把车开出去跑一圈，看看哪条路快。这太慢了，而且会堵车。
• NeurCC 的办法： 它先训练一个**“替身演员”**（代理模型）。这个替身演员看过很多历史数据，能根据地图（数据库状态）预测哪条路可能最快。
  • 它先在“替身”脑子里模拟跑几千次，找出最有希望的路线。
  • 只把真正最有潜力的几条路线，拿去现实中跑一次验证。
  • 这样既找到了好路线，又避免了在真实厨房里乱跑造成的拥堵。

绝招二：剪枝搜索（图简化搜索）

在复杂的厨房里，冲突关系像一张巨大的蜘蛛网（冲突图）。直接在网上乱剪很难找到最优解。

• NeurCC 发明了一种**“剪枝”**算法。它不是一开始就剪，而是先假设所有线都连着，然后像修剪盆景一样，只剪掉那些明显不需要的线（比如：两个厨师根本不可能抢同一个锅，那这条线就剪掉）。
• 通过不断“剪”和“合并”，它快速把复杂的网简化成最精简、最高效的冲突处理方案。

4. 它有多快？有多强？

论文做了大量实验，把 NeurCC 和目前最先进的五种算法（包括 2PL, Silo, Polyjuice 等）进行了对比：

• 吞吐量（炒菜速度）： NeurCC 的表现是其他算法的 3 到 4 倍。在繁忙的厨房里，它能多炒出好几倍的菜。
• 适应速度（学习速度）： 当厨房 workload 突然变了（比如从做中餐突然变成做西餐），NeurCC 能在 10 分钟 内学会新规则。而以前的“学习型”算法（如 Polyjuice）可能需要 1 小时以上，甚至更久。
• 稳定性： 无论厨房是冷清还是爆满，NeurCC 都能保持高速运转，不会像旧系统那样大起大落。

5. 总结：为什么这很重要？

想象一下，如果你的手机 APP、银行转账、电商购物背后的数据库都能用上 NeurCC：

• 平时： 大家各忙各的，互不干扰，速度飞快。
• 大促时（如双 11）： 突然几百万人同时下单，系统能瞬间“学会”如何排队、如何协调，自动调整策略，避免系统崩溃或卡顿。

一句话总结：
NeurCC 就像给数据库装上了一个**“自动驾驶”系统**。它不再依赖人类工程师死记硬背的规则，而是通过观察和快速学习，实时调整策略，确保在任何情况下，数据库都能以最高效、最安全的方式运行。

技术摘要

1. 研究背景与问题 (Problem)

背景：
现代数据库系统已不再受限于磁盘 I/O，并发控制（Concurrency Control, CC）算法对于利用硬件并发能力、确保事务隔离性（正确性）并实现高吞吐量至关重要。

现有挑战：

1. 工作负载适应性差： 现有的最先进（SOTA）CC 算法（如 2PL、OCC 及其变体）通常针对特定类型的工作负载优化。例如，2PL 在高冲突负载下表现好，而 OCC 在低冲突负载下表现好，但没有单一算法能在所有工作负载下都表现优异。
2. 无法应对动态漂移： 大多数现有算法无法适应随时间变化的工作负载漂移（Workload Drift）。现有的自适应方法（如 CormCC, Polyjuice）通常需要手动调整分类规则或算法选择，或者优化时间过长，导致在动态环境中反应迟钝。
3. 学习难度高： 现有的基于学习的方法（如 Polyjuice）面临参数非连续、缺乏局部性（Locality）的问题，导致传统的机器学习方法（如策略梯度）失效，不得不依赖代价高昂的进化算法或随机搜索，优化收敛慢。

目标：
设计一种可学习的并发控制算法，能够在多样化的工作负载下实现高性能，同时具备快速优化的能力，以应对动态工作负载的变化。

---

2. 方法论 (Methodology)

NeurCC 的核心思想是将并发控制建模为一个可学习的函数 $F: \{s\} \to \{a\}$，该函数将数据库状态 $s$ 映射到并发控制动作 $a$。

2.1 统一模型设计

NeurCC 将并发控制分解为一系列冲突检测和解决动作的组合，而不是从现有算法中选择一个。

• 状态 ($s$)： 包含轻量级、无锁可计算的数据库特征，如事务类型、数据热度（Hotness）、依赖事务数量、已执行操作数等。
• 动作 ($a$)： 包含三个维度的决策：
  1. 冲突检测策略： 无检测（No detection）、检测关键冲突（Detect critical）、检测所有冲突（Detect all）。
  2. 超时设置（Timeout）： 阻塞等待的时长。
  3. 优先级与流水线等待（Priority & Pipeline-wait）： 决定事务的优先级以及是否允许脏读（Dirty Read）或流水线等待。
• 实现： 函数 $F$ 被实现为数据库内的查找表（Lookup Table）。状态 $s$ 经过特征选择器 $E$ 处理后，直接查表获得动作 $a$。这保证了极低的执行开销（仅需数百个 CPU 周期）。

2.2 高效的学习与优化流程

为了快速找到最优函数 $F$，NeurCC 采用了混合优化策略：

1. 贝叶斯优化 (Bayesian Optimization)：

   • 用于优化连续参数（如超时时间）和部分离散参数。
   • 使用**高斯过程（Gaussian Process）**作为代理模型（Surrogate Model），在线训练以预测系统吞吐量。
   • 利用上置信界（UCB）采集函数来平衡探索（Exploration）与利用（Exploitation），减少昂贵的真实系统评估次数。

2. 图归约搜索算法 (Graph Reduction Search)：

   • 专门用于优化流水线等待动作（Pipeline-wait actions），因为这部分参数非连续且缺乏局部性。
   • 将学习任务重构为**最优冲突图（Optimal Conflict Graph）**的学习任务。
   • 算法从一个全连接的冲突图开始，通过**边移除（Edge Removal）和节点合并（Node Merging）**的变异操作，逐步简化冲突图，消除不必要的冲突检测，从而找到最优的流水线等待策略。

3. 分阶段优化管道 (Optimization Pipeline)：

   • 阶段 1 & 3： 优先优化 $F_P$（流水线等待）和 $F_D$（冲突检测与优先级），因为这两者对性能提升贡献最大（可达 80%）。
   • 阶段 2 & 4： 优化 $F_T$（超时）及微调所有参数。
   • 这种分阶段策略利用知识迁移，确保在有限的优化预算内快速收敛。

4. 特征选择器优化：

   • 使用贝叶斯优化自动选择最有效的特征子集，以平衡状态空间的大小和优化速度。

2.3 部署与漂移检测

• 漂移检测： 系统后台监控吞吐量变化。当吞吐量相对变化超过阈值（如 10%）时，触发优化流程。
• 无缝切换： 优化过程在后台进行，新函数加载后通过原子指针更新切换，不阻塞当前事务。

---

3. 主要贡献 (Key Contributions)

1. NeurCC 算法： 提出了一种新型的可学习并发控制算法，能够跨多样化工作负载实现高性能，且优化速度快，能迅速适应工作负载漂移。
2. 统一模型： 提出了一种将并发控制建模为“状态到动作”映射函数的新范式。该模型涵盖了现有的多种 CC 算法（如 2PL, OCC, Polyjuice, bLDSF 等）的设计选择，并允许任意组合这些设计。
3. 高效学习算法： 设计了结合贝叶斯优化和图归约搜索的混合优化算法，解决了非连续参数优化难、评估成本高的问题，显著加快了收敛速度。
4. 广泛的实验评估： 在 TPC-C 和 YCSB 等多种工作负载下，与 5 种 SOTA 算法（2PL, Silo, CormCC, Polyjuice, IC3）进行了对比。

---

4. 实验结果 (Results)

实验在 24 核 Intel Xeon 服务器上进行，对比了存储过程模式（Stored Procedure）和交互式事务模式（Interactive Transaction）。

• 吞吐量提升：
  • 在存储过程模式下，NeurCC 的吞吐量比 Polyjuice 高 3.32 倍，比 2PL 高 4.38 倍，比 Silo 高 4.27 倍。
  • 在交互式事务模式下，NeurCC 比次优基线高出 1.96 倍。
• 优化速度：
  • NeurCC 达到峰值性能的平均优化时间为 9.67 分钟（存储过程模式），而 Polyjuice 需要 1.78 小时。
  • NeurCC 的优化速度比 Polyjuice 快 11 倍。
• 鲁棒性：
  • 在面对工作负载漂移（如线程数从 1 变 16）时，NeurCC 能快速响应并重新优化，而基于随机搜索的基线算法表现波动大或收敛慢。
  • 在快速变化的工作负载压力测试中，NeurCC 的表现始终优于静态基线。
• 消融实验：
  • 证明了优化 $F_D$（冲突检测）和 $F_P$（流水线等待）对性能提升贡献最大（占总提升的 80% 以上）。
  • 证明了特征选择器（如事务类型、已执行 SQL 数）对性能至关重要。

---

5. 意义与影响 (Significance)

1. 打破传统界限： NeurCC 不再局限于选择现有的单一 CC 算法，而是通过“学习”自动组合冲突检测和解决机制，实现了比任何单一现有算法更优的自适应能力。
2. 解决动态适应难题： 通过极快的优化收敛速度，NeurCC 使得数据库系统能够实时应对工作负载的漂移，解决了传统自适应算法调整滞后或手动配置繁琐的问题。
3. 低开销实现： 通过将学习模型实现为高效的内存查找表，NeurCC 确保了在纳秒级的事务执行路径上，并发控制的决策开销微乎其微，这是许多基于复杂 ML 模型的方法无法做到的。
4. 通用性： 该框架不仅适用于特定的工作负载，还能通过特征选择和图归约搜索适应从低冲突到高冲突、从只读到复杂读写混合的各种场景。

总结： NeurCC 通过创新的“可学习函数”建模和高效的混合优化策略，成功解决了并发控制在动态复杂环境下的性能瓶颈，为下一代自适应数据库系统提供了重要的技术基础。