标题：面向数据的事务处理
一篇研究事务领域并行处理的论文。

ABSTRACT

并行环境下的事务处理，竞争的临界区成为扩展性的问题，这其中，中心化的锁管理器（下简称全局锁）成为性能瓶颈。
我们定位到传统的thread-to-transaction分配策略是竞争的主要原因。
本文设计的DORA系统，将事务拆解成Actions，把Action根据其访问的数据分配到各个线程去，这让每个线程访问的数据绝大多数都是thread-local的数据，减少和全局锁的交互。
DORA维护了所有的ACID特性，提高了4.8x的吞吐量。

1. INTRODUCTION

事务处理系统里的临界区太多了，严重地拖慢了多核环境下的系统性能。

1.1 Thread-to-transaction vs. thread-to-data

传统事务处理系统出现问题的主要原因就是数据访问的不协调。事务被任意分配给一些线程，然而事务处理临界区又多，每个事务执行时间又很短，因此同步问题会随着并行度增加而放大。下面两张实验图，可以说明临界区在并行处理时的瓶颈问题。

image.png

• thread-to-data：即本文提出的DORA分配策略，将每个线程和具体一部分数据相绑定。事务被分割成一个个sections，当事务需要访问的数据变化了，事务所属的线程也会变化。DORA就是负责将事务拆分成sections，然后将它们路由至所属的线程。本质上是将“拉数据到线程模式”改为“把计算推到数据上的模式”。

image.png

3. THE LOCK MANAGER AS SOURCE OF CONTENTION

一句话概括：锁上的线程请求很多，加上执行事务和竞争锁的线程数量的增长，共同造成了性能的退化。
如下图，系统负载增加的时候，大部分时间都花在了竞争锁上。

image.png

4. A DATA-ORIENTED ARCHITECTURE FOR OLTP

4.1 Design overview

DORA的功能主要分成三个部分：

1. 把工作线程绑定到不相交的数据子集上；
2. 把每个事务都分布到多个工作线程上（根据需要的数据）；
3. 尽可能避免了和中心化的锁管理器交互。

4.1.1 Binding threads to data

这一部分主要介绍几个概念：

• dataset：一个表的逻辑子集，由一个线程来负责绑定；
• executor：一个执行线程，绑定一个或多个Dataset；
• routing rule：一个Dataset如何对应一个Executor的规则；
• routing fields：用于切分dataset的若干列；（通常是主键/候选键）

routing rules由DORA资源管理器动态维护，这些规则会在运行时阶段性更新以负载均衡。分配给每个表的executor数量也根据负载和size各不相同。

4.1.2 Transaction flow graphs

• action: DORA会把事务切割成多个action，每个action是一个事务代码的片段，只包含对同一个表的一部分数据的访问。

• identifier: 每个action都有一个identifier，代表其对数据的访问需求，要么是routing field中的一些值，或者是个空集。
  action的identifier越具体，越容易给action找到对应的executor。具体来说，

  • identifier包括全部routing fields时（一组值），可以通过表的routing rules，直接定位到executor；
  • identifier只包括部分routing fields时，一般会对应多个executors，则需要把它们拆分成更小的actions；
  • 如果根本不包含routing fields，是通过其它field进行数据访问的，就称之为second actions，它们的identifier就是空集，如何为它们分配executor，在4.2.2节说明。

• RVP(rendezvous point)：事务的Actions之间通常会有一些数据依赖，没有依赖，只是对不同部分的数据执行计算的Actions可以并行，称之为一个phase；不同phase之间可能会产生一些数据依赖，需要等同一个phase所有actions完成之后全体进入下一个phase，那么这个同步点就称之为RVP。
  每个phase的RVP初始化为action的个数，每个executor执行完毕一个action就在RVP上-1。使RVP归0的executor同时负责把下一阶段的action分发到各个executor上去。

4.1.3 Executing requests

每个Executor要负责处理很多Actions，关键之处在于要保持隔离性，对有冲突的actions进行排序。
DORA Executor包含三个内部数据结构：

• 到来的actions队列；
• 完成的Actions队列；
• 线程本地的锁表；

Actions按到达顺序执行，Executor利用本地锁表对冲突进行检测，在action identifier的级别进行冲突解决（进入锁表的是action identifiers）。
本地锁只有两种模式：共享和互斥。而由于identifier通常是primary key的子集，本地锁的模式更类似于前缀锁。
总体来说，本地的事务处理就是串行化处理的。每个Action一旦拿到了本地锁，直到action所属的整个事务结束才会释放。事务结束后，所有的action才会被放进完成action队列里，action占有的lock也会被清除。后续被阻塞的action可以进行占用。

4.2 Challenges

4.2.1 Record inserts and deletes

数据更新只需要本地锁即可，但是数据的插入和删除仍然需要全局锁。原因就是物理冲突（不访问同一个数据，但访问了同一个位置），举个例子：

1. 事务A找到记录R1，删除之；
2. 事务B发现R1的位置空出来了，在原位置上插入了一条新Record R2;
3. 此时A abort，想要回滚会失败，因为R1的位置没法再写回了。

行级锁可以处理这个问题，insert和delete时会对RID（和对应的物理slot）进行加锁。这里就用到了全局锁。实际上，行级锁一般不会造成过度的竞争。

4.2.2 Secondary Actions

刚才提到了一个问题，对于一些访问二级索引的Action，不会涉及到routing fields，那么就不知道这些Action具体要访问哪个我们逻辑上划分好的dataset，从而不知道把这个Action分给哪个executor。
为了解决这个问题，我们在被访问的二级索引上加上覆盖索引(cover index)。即在叶子节点上的每个entry中，补上routing fields的值，这样在访问二级索引时，就可以知道routing field是多少，从而分配给对应的executor。
那么谁来访问这些二级索引，以决定Executor分配呢？前一个phase的RVP执行线程。如果是第一个phase，那么就是接受请求的dispatcher线程。注意到访问二级索引的线程对于绑定数据来说是任意的，也可能不绑定任意数据。

至目前为止，对于insert和update的workload由于Executor的序列化执行可以做到隔离性。但是delete操作仍然容易出现问题，考虑以下场景：

1. 事务A在主索引上删除了Record R1，在二级索引上也删除了对应的entry；
2. 事务B访问二级索引该entry，返回为null；
3. 事务A abort, rollback，此时事务B没有做到隔离性，Read uncommited。

为了解决该问题，我们将二级索引的删除滞后，删除事务只先删主索引，然后提交，之后再去给二级索引打一个Delete flag。
也就是说无论在删除事务执行的任意时刻，访问二级索引的事务都可以访问到对应的entry，然后其被要求访问主索引，发现record已经被删除了，或者正在被删除（行级锁，释放后可以看到最终结果）。事务执行后的一段时间内，二级索引对应的entry被打上Delete flag，在叶子节点合并时机进行垃圾清理。

4.2.3 Deadlock Detection

local lock table可能会block，因此底层存储引擎会开放一个死锁检测器接口提供给DORA使用。
然而DORA在设计上尽量避免了死锁。对于某个transaction，一个phase最后一个action的提交，会按顺序latch住所有的下一个phase的所有并行执行的executor的incoming queues。然后将下一phase的所有actions逐个进队，进队后释放latch，把这个过程做成一个原子性的。
注意到所说的顺序实际上是事务提交时，各个语句的顺序。各个语句被组合成Action，那么Action也是有顺序的，对应的executor也是有顺序的，即使会并行执行。
基于这样的设计，两个拥有同样事务流图的事物，不会造成死锁。因为executor的申请是原子性的，会先满足一个事务的所有需求，然后另一个事务会在第一个phase就阻塞掉，直到前一个事务彻底完成。

5. PERFORMANCE EVALUATION

5.1 Experimental setup & workloads

• Hardware：8核16线程，32GB内存
• I/O：日志和数据库都存于内存中，以使得CPU饱和
• Workload：OLTP benchmark：TM-1(7.5GB) TPC-C(20GB) TPC-B(2GB)。

5.2 Eliminating the lock manager contention

可以看到，由于弱化了对中心化锁管理器的需求，DORA即使在高负载的情况下，也可以将主要CPU用于执行事务本身，而非竞争锁。

image.png

下图量化了在三种workload下，DORA和baseline对锁的请求量。DORA对锁的请求主要是thread-local锁表，对行级锁和全局锁的需求量很小。

image.png
下图研究了DORA和BaseLine的扩展性，虽然CPU利用率的升高，吞吐量（TPS）的变化。对于像TM1这样的小查询，baseline中对锁的竞争量非常高，严重影响了吞吐量；对于后两种，baseline的情况就好一些。一旦负载量超过CPU100%，baseline的吞吐都受到了影响，因为抢占的出现，很多临界区的代码被迫暂停，产生了这样的问题。对于DORA，则没出现严重的退化，主要由于对于锁的竞争没有那么严重。
image.png
image.png

5.3 Intra-transaction parallelism

DORA除了减少了对全局锁的过度依赖，实际上，也充分发挥了事务执行过程中的并行性，这样在CPU负载不满的情况下，加快了事务的响应速度。

image.png

5.4 Maximum throughput

经过合适的调优，测试DORA和baseline在不同Workload下的极限吞吐量（每CPU利用率）。总的来说，测试集对全局锁竞争越多，DORA提升越大。

image.png