论文导读 | 可串行化事务机制
在现代数据库系统中，事务处理是核心功能之一。事务是指一系列数据库操作，这些操作作为一个整体执行，要么全部成功，要么全部失败。为了确保事务的正确性和一致性，数据库系统采用了多种隔离级别，其中最高级别就是可串行化隔离。本文将详细探讨可串行化隔离机制的定义、实现方法及其重要性；并在后面介绍两篇可串行化事务的论文。
可串行化事务的基础介绍
如图A是一个对数据A/B的操作序列。尽管一个事务内的操作顺序是固定的，但当有两个事务同时执行的时候，两个事务各自的线程（亦或是其他模型）的抢占调度不定，因此不同操作交叉的执行顺序是无法确定的。这种操作的执行顺序被我们称之为Schedule。例如图B和图C就分别是两个相同的图A事务的Schadule。
由此，我们有了下面这些定义。
可串行化隔离的定义
可串行化隔离是指多个事务并发执行的结果等价于这些事务以某种顺序串行执行的结果。换句话说，即使事务并发执行，其最终效果也应与某个特定的串行调度相同。这确保了事务之间的相互独立性和数据的一致性。
冲突、冲突等价与冲突可串行化
实现可串行化隔离面临的主要挑战是复杂的并发控制机制。为了确保事务的正确性，数据库系统需要精确地管理事务之间的冲突。这些冲突主要包括读写冲突（RW）、写读冲突（WR）和写写冲突（WW）。我们具体考虑两个操作I/J，并用R(X)和W(X)分别表示对数据项X的读写操作。那么我们有以下四种情况：
I 和 J 的目标数据项不同： 两个操作针对不同的数据项，顺序不影响结果。
I = R(Q), J = R(Q)： 两个读操作针对同一数据项，顺序不影响结果。
I = R(Q), J = W(Q)：读操作和写操作针对同一数据项，顺序影响结果。
I = W(Q), J = W(Q)： 两个写操作针对同一数据项，顺序影响结果。
我们可以看出，冲突即是RW/WR/WW三种。
因此，如果某个调度的两个相邻操作可以交换顺序而不影响最终结果，我们就称该调度和交换后的调度为冲突等价。显然一个调度可以一直执行冲突等价的交换。如果它最终能够与一个串行化调度冲突等价，那我们就称这个调度是冲突可串行化的。下图是一个将一个调度经过多次冲突等价调换后成为一个可串行化调度的例子。
事务优先图
事务优先图是一个有向图，它包含表示事务的节点和表示冲突关系的边。在图中，每个节点代表一个事务，每条有向边则代表两个事务之间的冲突关系。具体来说，如果事务T1中的某个操作A1与事务T2中的某个操作A2存在冲突，并且A1在A2之前执行，则从T1节点指向T2节点画一条有向边。下图是一个简单的带环的事务优先图。
当事务优先图中无环时，意味着所有事务之间的冲突关系都可以按照某种顺序进行排列。当事务优先图中存在环时，意味着存在至少两个事务之间的冲突关系构成了循环依赖。因此，可以利用事务优先图来判断一个调度是否是冲突可串行化的。
请注意冲突可串行化调度是可串行化调度的子集，想要切实判断所有的可串行化调度是不现实的，因此实际使用中大都使用冲突可串行化或是更严格的方式来实现可串行化调度。
实现可串行化事务的协议
接下来我们介绍两个基础的可以实现可串行化事务的协议。
两阶段锁（2PL）
两阶段封锁协议（2PL）是实现可串行化的一种常见方法。2PL要求事务分两个阶段进行：
增长阶段：事务可以获取锁，但不能释放任何锁。缩减阶段：事务可以释放锁，但不能获取任何新锁。
通过这种方式，2PL确保了事务之间的冲突不会导致数据不一致。然而，2PL可能导致性能下降，特别是在高并发环境下。
此外，如下左图，由于T2事务在T1事务释放锁后读取了T1事务的数据，因此如果T1事务最终回滚后T2事务也需要回滚。而T2事务的回滚可能导致更多事务的回滚，因此2PL可能会导致级联回滚。
对此，我们可以使用严格两阶段锁（S2PL）协议，该协议要求事务只有在结束的时候才能释放锁，可以避免级联回滚的问题。
由于2PL使用了锁机制，因此2PL针对死锁问题有三个解决办法：
NO_WAIT： 获取锁时从不等待。如果锁请求被拒绝，事务会立即被中止。
WAIT_DIE： 为每个事务分配一个时间戳，并通过比较时间戳与锁持有者的时间戳来避免死锁 当一个事务（例如Ti）请求被锁时，只有当Ti的时间戳小于所有持有者的时间戳时，Ti才被允许进入等待队列（即WAIT）；否则，Ti会被中止（即DIE）。
WOUND_WAIT： 当一个事务（例如Ti）请求被锁时，那些时间戳大于Ti的持有者会被中止（即WOUND） Ti要么成为新的锁持有者，要么根据是否所有持有者都已被中止来决定是否等待锁（即WAIT）。
乐观并发控制（OCC）
乐观并发控制（OCC）假设事务间的冲突较少，因此在事务执行过程中不使用锁。事务分为三个阶段，并分别获取三个时间戳用于之后判断事务冲突。
Read阶段
事务可以读取所有已提交事务的数据，而写操作执行在本地缓存中。并且记录下该事务的读操作集和写操作集。
Validation阶段
事务检查是否存在冲突。如果检测到冲突，事务将被中止。具体来说，对于想要提交的事务Ti，需要对所有已提交事务或执行到验证阶段事务Tj检查是否满足下方条件中的一个：
-
Ti Read在Tj Write之后
-
Ti Write在Tj Write之后，Ti Rset与Tj Wset无交
-
Ti Read在Tj Read之后， Ti R/Wset都与Tj Wset无交
Write阶段
通过验证的事务将自己的更新应用到数据库中。
OCC的优点是在低冲突环境中性能较高，但高争用下表现不佳，且存在饥饿问题。
接下来介绍两篇关于可串行化的事务论文。
Silo(Speedy Transactions in Multicore In-Memory Databases)
Silo注意到OLTP工作中的吞吐量大，全局时间戳的分配将成为瓶颈。因此它基于OCC的乐观机制，但取消了OCC的串行节点，并且优化了只读事务。缺点是运行在一次性(One Shot)事务上，无法支持交互式事务。
由于产自于OCC，因此Silo也有类似的三个流程：Pre-Commit/Commit/Write
Silo的Pre-Commit过程
Silo使用epoch防止每个事务都去获取一次全局时间戳，执行一个原子写
-
全局epoch有一个编号E，对所有事务可见
-
事务定期更新自己的本地epochs编号e_w，保证𝐸−e_w≤1
每个事务分配一个64位的TID，包括事务提交时的全局epoch（E），3bit状态位，其余的则为每个worker线程自己用于区分的编号。该分配方案是去中心化的。方案如下：
-
大于当前事务（当前worker来记录）读取或写入的任何记录的 TID
-
大于worker最近选择的TID
-
在全局的epoch下
每条数据会记录下修改自己的最新TID，并且事务在执行期间会记录自己的读写集。
Silo的Commit过程
Phase 1
-
遍历写集并加锁
-
同步全局epoch
Phase 2
-
遍历读集并检查是否有被更新（OCC）
-
同步全局epoch
Phase 3
-
计算TID并更新所有写
-
记录TID与锁状态位，由于它们合并起来存储在一个64bit，可以原子完成
Silo的write流程与OCC一致，不再介绍。
Plor (General Transactions with Predictable, Low Tail Latency)
Plor观察到OCC的高吞吐量以及2PL的低高尾延迟，希望将两者的优势结合起来。
注意到2PL相比Silo有用极少的尾部延迟，这是因为延迟与中断次数高度正相关，而Silo（OCC）中没有额外的机制保证中断的事务比其他事务更早提交，因此导致了高尾延迟。而2PL中，WOUND_WAIT具有更小的尾部延迟，因为其工作机制是将锁的所有权给到时间戳最大的等待者，而WAIT_DIE则是给最小的，因为它要保证等待队列中的时间戳要小于持有者。相对的，NO_WAIT会导致多次中止，因此在尾部延迟上并没有优势。
Plor为每个工作线程设置一个上下文ctx，包括：
-
wid：目前的线程id
-
ts：目前的事务时间戳
-
status：1bit，记录事务是否中止
-
R/Wset 读写集
由于借用了OCC的思想，因此Plor也类似的有三个阶段。但其中Validation阶段由于采用了锁思想，因此不需要执行验证，更换为Commit阶段。
Plor的Read阶段
Plor的Commit阶段
Plor的其他细节
-
写阶段与OCC一致，不再赘述
-
DMA：延迟写写冲突，在COMMIT阶段再加写锁。在部分workload上表现不佳
-
只读事务：初始只读事务不加读锁，Commit阶段多次中止后，下次retry时加读锁
-
无死锁：启用DMA时，可以使用全局顺序加锁避免死锁；不启用DMA时加锁时依照WOUND_WAIT，不会死锁。
Plor的实验部分
可以看到，在吞吐量略低于Silo与TicToc（另一边关于可串行化的事务论文）的同时，高尾延迟有着极高的降低，达成了论文的预期。
参考文献
[1]Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden.2013. Speedy Transactions in Multicore In-Memory Databases. In Proceedings ofthe Twenty-Fourth ACM Symposium on Operating Systems Principles (Farminton,Pennsylvania) (SOSP ’13).
[2]Youmin Chen, Xiangyao Yu, Paraschos Koutris, AndreaC. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, and Jiwu Shu.2022.Plor:General Transactions with Predictable, Low Tail Latency. In Proceedings of the 2022 International Conference on Management ofData (Philadelphia, PA, USA) (SIGMOD ’22)