LADS：基于依赖图预解析的动态单线程内存OLTP并发控制架构

1. 项目概述：LADS如何重新定义内存OLTP的并发处理

在当今数据驱动的业务场景中，在线事务处理（OLTP）系统的性能直接决定了应用的响应速度和承载能力。随着多核处理器成为服务器标配，内存价格持续走低，将整个数据库置于内存中以消除I/O瓶颈已成为高性能OLTP系统的标准配置。然而，一个核心矛盾随之凸显：硬件提供了前所未有的并行计算能力，但传统的并发控制机制却成了束缚性能的枷锁。锁竞争、事务中止、缓存一致性开销，这些在磁盘时代尚可容忍的开销，在内存中却成了阻碍系统线性扩展的主要障碍。

我曾在多个高并发业务系统中，亲眼目睹过锁管理器成为全局瓶颈、乐观并发控制（OCC）在高冲突场景下因大量回滚而性能骤降的场景。这促使我们思考：能否设计一种并发控制模型，既能保留单线程执行的高效与简单（无需锁、无冲突），又能充分利用多核的并行能力？这正是LADS（动态单线程内存OLTP系统）试图回答的问题。它不是一个简单的优化，而是一种架构层面的范式转变。其核心思想是：将“依赖关系的解析”与“事务的实际执行”彻底分离。通过预先分析一批事务中所有操作（细化到记录动作）的先后顺序，构建出一个全局的、无环的依赖图，然后将这个图智能地切割成若干子图，分配给不同的工作线程独立、串行地执行。这样一来，每个线程在其“领地”内依然是纯粹的单线程模式，无需任何同步原语，而系统整体却实现了高度的、负载均衡的并行。

简单来说，LADS让系统在“思考”（构建依赖图）时是并行的、全局的，在“行动”（执行操作）时是串行的、局部的。这种“先谋后动”的策略，使其在面对工作负载偏斜、跨分区事务等传统单线程模型的噩梦时，依然能保持极高的吞吐量和稳健的性能。实验表明，相较于H-Store、DORA、SILO等先进系统，LADS能实现高达20倍的吞吐量提升。接下来，我将深入拆解LADS的设计精髓、实现细节以及在实际部署中需要关注的要点。

2. 核心设计思路：两阶段执行与依赖图抽象

LADS的架构革新源于一个深刻的观察：传统并发控制（无论是锁还是时间戳）的本质，是在事务执行过程中动态地、试探性地解决冲突。这就像在没有交通灯的路口，每辆车（事务）都在试图寻找空隙通过，必然导致大量的等待、剐蹭（锁竞争）或倒车重来（事务中止）。LADS的思路则像是在路口设置一个中央调度系统：先让所有车辆上报行程（事务解析），由调度系统规划出一个全局无冲突的通行序列（依赖图构建与分区），然后各车道（工作线程）只需按序行驶即可。

2.1 从“事务”到“记录动作”：细粒度并行单元

传统并发控制以整个事务为调度单元。LADS则进一步拆解，提出了“记录动作”的概念。一个事务可能涉及对多个记录的读写，LADS会将其分解为多个连续的、针对单一记录的操作序列，每个序列就是一个记录动作。例如，一个银行转账事务“从账户A转100元到账户B”，会被分解为两个记录动作：(事务ID: 扣减, 记录A, 100)和(事务ID: 增加, 记录B, 100)。

这种拆解带来了两个关键优势：

1. 暴露更多并行性：如果两个事务分别操作记录A和记录B，在传统模型中它们可能因为锁住整个事务而无法并行。在LADS中，只要它们的记录动作不冲突（即不操作同一记录），就可以被分配到不同线程并行执行。
2. 精确捕捉依赖：依赖关系被细化到记录级别，而非事务级别。这使得系统能更精准地识别真正的冲突点，避免不必要的串行化。

2.2 依赖图的构建：逻辑依赖与时间依赖

LADS为每一批到达的事务构建一个依赖图G=(V, E)。其中，顶点V是这批事务的所有记录动作。边E代表两种依赖关系：

• 逻辑依赖：同一事务内，记录动作必须遵循的程序逻辑顺序。例如，必须先检查余额（或扣款），才能执行转账（或存款）。这是一种由应用语义决定的固有顺序。
• 时间依赖：不同事务间，对同一记录的操作必须按照事务到达的时间戳顺序执行，以保证可串行化。这是一种由系统保证的时序顺序。

构建算法高效且易于并行化。每个工作线程维护一个“最新记录动作”的映射表。当处理一个新的记录动作时，只需将其与所操作记录的上一个“最新记录动作”相连，形成时间依赖边。同一事务内的动作则按逻辑顺序相连。这个过程是只读的、无锁的，多个线程可以同时为不同的批次构建依赖图。

注意：依赖图在构建时就被保证是无环的。这是因为时间依赖边总是从时间戳小的事务指向时间戳大的事务，而逻辑依赖边仅存在于事务内部。这种无环特性是后续无锁执行的基础，也彻底消除了因循环等待导致的死锁问题。

2.3 动态图分区与负载均衡

构建好全局依赖图后，LADS面临的核心挑战是如何将其切割成若干子图，分配给多个工作线程执行，并满足两个目标：1) 各线程工作量均衡；2) 跨子图的依赖边（通信开销）最少。

LADS将此抽象为一个带权图的均匀划分问题。它首先将依赖图压缩为一个“记录动作队列图”：每个顶点代表一个记录的所有待处理动作队列，顶点权重是队列长度（即动作数量），边权重是连接两个队列的逻辑依赖边数量。这个压缩图规模远小于原依赖图，使得划分算法开销可控。

划分算法采用一种贪心策略：

1. 初始划分：根据记录键的范围，将压缩图粗略地、均匀地划分为N份（N为线程数）。
2. 迭代优化：计算所有跨分区的边（边割）。尝试将顶点从一个分区移动到相邻分区，评估移动后边割总权重的减少量（收益）。总是选择收益最大的移动进行操作，直到满足均衡约束（每个分区权重不超过平均值的(1+ε)倍）且无法再获得正收益为止。

这个过程充分考虑了现代多核服务器的NUMA（非统一内存访问）架构。LADS会倾向于将访问同一NUMA节点内存的记录动作队列划分到同一个分区，从而减少昂贵的跨NUMA内存访问，提升缓存局部性。

2.4 两阶段批量执行模型

完成分区后，系统进入执行阶段。这是一个批量同步并行模型：

1. 阶段一：依赖解析与图分区（并行）：多个工作线程并行地从事务队列中获取批次，各自构建依赖图并进行分区。此阶段无共享状态，完全并行。
2. 全局同步点：所有线程完成阶段一后，进行一次轻量级同步，确保所有依赖图就绪。
3. 阶段二：事务执行（并行但独立）：每个线程获取分配给自己的子图（可能来自多个依赖图），然后以单线程、无锁的方式执行。执行过程是贪心的：线程维护一个“可执行动作集合”，初始包含子图中所有入度为0的动作。执行一个动作后，将其从图中移除，并将其后继动作中入度变为0的加入可执行集合。如此循环，直至子图中所有动作执行完毕。

这种设计的美妙之处在于，执行阶段完全不需要锁或CAS操作。因为所有的冲突和依赖都在阶段一被预先解析并编码在了依赖图的结构中。每个线程只需按照图的拓扑顺序执行即可，如同处理一个已经���好序的任务列表。

3. 系统实现深度解析

理解了核心思想后，我们深入到LADS的系统实现层面，看看这些理论是如何落地的，以及其中有哪些精妙的设计和权衡。

3.1 系统架构与组件协同

LADS的架构清晰地反映了其两阶段执行的思想，主要由四个组件构成：

• 事务发起器：管理一组事务请求队列，每个队列由一个工作线程负责。它支持基于优先级调度，可以应对不同SLA要求的事务混合场景。
• 依赖图执行引擎：这是系统的核心。工作线程在这里交替扮演两种角色：图构建者和图执行者。它们并行构建多个依赖图，然后按优先级顺序串行执行这些图。这种BSP（批量同步并行）式的执行模型，简化了并发控制。
• 存储管理器：负责管理内存中的数据，支持B+树和哈希索引。其设计的关键是缓存行对齐，以最小化多核间的缓存一致性流量。每个记录除了数据本身，还包含一个指向其“记录动作队列”的指针，这是依赖图构建时的关键数据结构。
• 统计管理器：收集运行时指标（吞吐量、延迟等），并用于动态调整系统配置。最重要的一个可调参数就是批次大小，它直接决定了吞吐量与延迟的权衡。

3.2 关键实现细节与优化

1. 时间戳分配：去中心化设计与传统OCC或MVCC需要全局、原子的时间戳分配器（易成瓶颈）不同，LADS的时间戳是线程私有的。每个工作线程维护自己的时间戳计数器，只为进入其本地队列的事务分配时间戳。这些时间戳仅用于在构建单个依赖图时确定同一队列内事务间的时序依赖。不同队列间事务的冲突，是通过串行执行不同的依赖图来解决的，无需比较跨队列的时间戳。这彻底消除了全局时间戳分配的开销。

2. 条件语句与事务中止处理OLTP事务中常包含IF...ELSE等条件逻辑。LADS通过添加额外的“条件检查”记录动作来处理。这个动作作为事务的第一个动作，其他动作都逻辑依赖于它。如果条件检查失败（如余额不足），它会向同事务的其他动作发送“禁用”消息，从而避免无效的级联回滚操作。这保证了即使事务因业务逻辑失败，也不会在执行阶段引起复杂的回滚风暴。

3. 范围查询的支持范围查询（如SELECT * FROM table WHERE value > 100）会访问一个键范围，在事务执行期间，这个范围可能被其他事务修改，破坏可串行性。LADS的应对策略是粗粒度化：将整个范围查询事务视为一个巨大的、操作整个表（或分区）的“复合记录动作”。后续所有要操作该表的事务都必须依赖这个复合动作。这虽然降低了并行度，但保证了正确性。鉴于OLTP中范围查询相对罕见，这种退化是可以接受的。

4. 持久化：日志与检查点作为内存数据库，持久化至关重要。LADS采用命令日志：日志中不记录修改后的数据值，而是记录重放事务所需的最小信息（记录键、函数、参数、依赖关系）。这大大减少了日志量和I/O开销。日志写入由独立的线程批量完成，与事务执行流水线化，对性能影响较小（实验显示约15%的开销）。 定期的检查点用于限制故障恢复时间。LADS将内存划分为多个区域，由多个检查点线程并行快照。检查点不是数据库的一致性快照，需要结合之后的日志进行恢复，这是一种经典的“检查点+重放日志”的恢复策略。

3.3 与主流方案的对比分析

为了让LADS的优势更具体，我们将其与几个代表性的系统进行对比：

从对比中可以看出，LADS吸取了各家之长：它像H-Store一样在执行阶段采用高效的单线程模型；像DORA一样尝试将工作导向数据所在处；同时又避免了SILO在高冲突下的性能悬崖。其独特的价值在于，通过预计算将运行时最昂贵的冲突解决成本提前支付，换取了执行阶段极致的轻量与高效。

4. 性能表现与场景分析

论文中的实验数据充分验证了LADS设计的优越性。我们不仅要看结果，更要理解这些结果背后的原因，以及它们对实际系统设计的启示。

4.1 对写操作与数据偏斜的鲁棒性

在YCSB基准测试中，随着写操作比例和Zipfian偏斜参数u的增加（意味着热点数据访问更集中），传统系统的性能普遍下降。

• SILO：性能下降最显著。因为OCC在写冲突率高时，验证阶段失败率激增，导致大量事务回滚和重试，CPU周期被浪费。
• H-Store：在无跨分区事务时，对写比例不敏感（因为分区内串行无冲突），但受数据偏斜影响大。如果热点数据集中在一个分区，该分区线程成为瓶颈，其他线程空闲。
• DORA：性能有所下降，但比SILO平缓。私有锁机制比全局锁好，但锁管理仍有开销，且逻辑分区调整有延迟。
• LADS：表现最为稳健。因为所有的写冲突在依赖图构建阶段就已通过时间依赖边确定了执行顺序。执行阶段只是按序执行，没有回滚。动态分区又将热点记录的动作均匀分散到多个线程，避免了单个线程过载。

实操心得：这意味着对于“秒杀”、“热点商品更新”这类典型的高冲突、偏斜工作负载，LADS架构具有天然优势。在技术选型时，如果业务场景写冲突严重，应优先考虑LADS这类基于预排序的并发控制方案，而非OCC。

4.2 彻底解决跨分区事务难题

跨分区事务是静态分区数据库（如H-Store）的“阿喀琉斯之踵”。实验显示，即使只有1%的跨分区事务，H-Store的吞吐量也会暴跌，因为事务需要阻塞性地获取所有相关分区的锁。DORA同样受此困扰。 LADS和SILO因为采用共享内存架构，从概念上就不存在“跨分区”问题。但LADS更进一步：它不仅没有跨分区惩罚，还能通过依赖图优化跨“记录”的访问顺序。而SILO在处理跨记录访问时，仍然依赖事务级的冲突检测。

4.3 可扩展性与批次大小的权衡

LADS在TPC-C测试中展现了良好的扩展性，但随着线程数超过仓库数，扩展曲线放缓。这是因为TPC-C的Payment事务总会更新Warehouse表的同一字段，形成了固有的串行点（真依赖），任何并发控制协议都无法绕过。但LADS仍能并行处理其他表上的操作，因此扩展性优于其他系统。

批次大小是LADS中最重要的调优参数：

• 吞吐量：随着批次增大，吞吐量上升并逐渐趋于平缓。因为更大的批次让依赖图构建和分区算法有更多优化空间，分摊了固定开销。
• 延迟：随着批次增大，平均延迟线性增长。因为事务需要等待其所属批次被处理完毕才能提交。

注意事项：批次大小直接决定了吞吐量与延迟的权衡点。在实际部署中，需要根据业务SLA（服务等级协议）动态调整。例如，在流量低谷期可以增大批次以提升吞吐、节约资源；在流量高峰或对延迟敏感时段，则应减小批次以保障响应时间。LADS的统计管理器正是为此设计。

4.4 对动态工作负载的适应性

现实中的工作负载是动态变化的。实验模拟了一小时内，跨分区事务比例和冲突强度随机波动的情况。LADS的吞吐量和延迟曲线波动幅度远小于其他系统。这证明了其动态分区机制的有效性——它不依赖于历史访问模式进行缓慢的重新分区，而是针对每一批到达的事务，实时地、基于当前依赖图进行最优划分。这种“即时响应”的能力，使其非常适合云原生环境中负载不可预测的应用。

5. 实战考量与部署建议

将LADS的思想应用于实践或理解其适用边界，需要关注以下几个关键点。

5.1 适用场景与不适用场景

LADS非常适合以下场景：

1. 短事务、高并发OLTP：如金融交易、实时竞价、游戏状态更新。
2. 工作负载偏斜严重：存在明显热点数据，传统分区方案效果差。
3. 事务模式复杂：包含一定比例的跨分区/跨记录访问。
4. 对吞吐量要求极致，且能接受一定批处理延迟（毫秒级）。

LADS可能不适用或需要改进的场景：

1. 对延迟极其敏感（微秒级）：批处理引入的等待时间可能不可接受。
2. 只读查询或分析型负载为主：依赖图构建的 overhead 可能得不偿失，传统的MVCC或快照隔离更合适。
3. 超长事务：长事务会阻塞整个批次的提交，影响系统整体吞吐。需要拆分为小事务或采用其他机制。
4. 范围查询频繁：如前所述，LADS会将其退化为粗粒度操作，严重影响并行度。

5.2 关键配置参数与调优

1. 最大批次大小：这是核心参数。设置太小，无法充分发挥依赖图优化和批量提交的优势；设置太大，会增加延迟并占用更多内存构建大图。建议：初始值设置为单线程每秒处理能力（如5000 TPS）的10-50倍，然后根据监控的吞吐和延迟曲线进行调整。
2. 工作线程数：通常设置为物理核心数。需要关注超线程的影响，在某些情况下，使用物理核心数而非逻辑核心数可能性能更好，因为依赖图构建是计算密集型任务。
3. 图分区均衡因子：控制分区时负载均衡的严格程度。ε值越小，分区越均衡，但算法可能更难找到解；ε值越大，允许的不均衡度越高，算法更易收敛。建议：从0.1开始调整，观察各线程的CPU利用率是否均衡。
4. NUMA感知设置：在NUMA架构服务器上，务必启用NUMA感知的分区优化，将访问同一NUMA节点内存的记录动作尽量分在一起，这是提升性能的关键。

5.3 潜在挑战与解决思路

1. 依赖图构建开销：对于极其简单、冲突极少的事务（如纯主键点查），依赖图构建的开销可能成为瓶颈。优化思路：可以实现一个快速路径，对于检测到的“单记录、单事务”批次，绕过依赖图构建，直接分发执行。
2. 内存开销：依赖图需要额外内存存储。对于海量事务批次，图可能很大。优化思路：采用更紧凑的数据结构存储依赖图；或设置批次大小上限，防止内存耗尽。
3. 故障恢复复杂度：由于采用命令日志，恢复时需要重新构建依赖图并执行，恢复时间可能比数据日志长。优化思路：更频繁的检查点可以缩短恢复时间，但会增加运行时开销。需要根据RTO（恢复时间目标）要求进行权衡。

LADS代表了一种并发控制的新思路：将复杂的运行时协调问题，转化为一个可以预先计算、静态优化的调度问题。它用“空间换时间”（额外的内存存储依赖图）和“计算换协调”（预先的图分区计算），换取了执行阶段极致的简洁与高效。对于深陷于锁竞争和事务回滚泥潭的高并发内存数据库应用来说，这种架构无疑提供了一条充满希望的路径。当然，没有银弹，其引入的批处理延迟和计算开销也需要在具体场景中仔细评估。但无论如何，LADS的设计深刻地启示我们，在面对多核硬件的并行潜力时，或许我们应该更勇敢地重新思考并发控制这一数据库核心问题的根本解法。