跳转至

本篇文档介绍 MiniOB 中的事务模块是如何工作的。

背景

事务是数据库中非常基础的一个模块,也是非常核心的功能。事务有一些基本的概念,叫做ACID,分别是原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持久性(Durability)。如果你对事务的基本概念不太清楚,建议先学习了解事务的基本概念,比如学习事务处理章节,或者在网上搜索更多资料。

MiniOB 中的事务

实现简介

MiniOB 作为一个帮助学习数据库的代码,为了使其学习起来更简单,实现了两种类型的事务。一个叫做Vacuous,另一个叫做MVCC,可以在启动observer时,选择特定的事务模块。

Vacuous(真空)

顾名思义,这个事务模块,将不会做任何事务相关的处理,这保留了原始的简单性,有利于学习其它模块时,简化调试。

MVCC

多版本并发控制,是一种常见的事务实现。著名的MySQL数据库也支持MVCC,OceanBase也实现了此机制。

简单来说,MVCC 会在修改数据——MiniOB当前支持插入和删除——时,不会直接在现有的数据上修改,而是创建一个新的行记录,将旧数据复制出来,在新数据上做修改。并将新旧数据使用链表的方式串联起来。每个数据都会有自己的版本号(或者称为时间戳),而版本号通常使用单调递增的数字表示,每个事务根据自己的版本号与数据的版本号,来判断当前能够访问哪个版本的数据。由此可见,MVCC 一个优点就是可以提高只读事务的并发度,它不与其它的写事务产生冲突,因为它访问旧版本的数据就可以了。

NOTE: 不同的数据库,会有不同的实现方式。对MVCC感兴趣的同学,可以阅读一些相关的论文。

如何运行与测试

当前MiniOB支持两种类型的事务模型,并且默认情况下是Vacuous,即不开启事务特性。

测试MVCC

编译时增加选项 -DCONCURRENCY=ON:

cmake -DCONCURRENCY=ON ..

然后在build目录执行 make。编译完成后启动 observer 服务端进程。

也可以使用 bash build.sh -DCONCURRENCY=ON 来编译

可以在启动observer时,增加 -t mvcc 选项来开启MVCC,假设当前目录是build(或build_debug之类):

./bin/observer -f ../etc/observer.ini -s miniob.sock -t mvcc

-f 是配置文件,-s 指使用unix socket,-t 指定使用的事务模型

启动observer后,可以使用obclient连接observer:

./bin/obclient -s miniob.sock

可以开启多个客户端。在命令行界面执行 begin 可以开启事务,执行 commit 提交事务,rollback 回滚事务。

更多的实现原理

事务代码位于 src/observer/storage/trx 目录下,代码很少。

事务模型选择

trx.h 文件中有一个抽象类 TrxKit,它可以根据运行时参数传入的名字来创建对应的 VacuousTrxKitMvccTrxKit。这两个类可以创建相应的事务对象,并且按照需要,初始化行数据中事务需要的额外表字段。当前 Vacuous 什么字段都不需要,而MVCC会额外使用一些表字段。

事务接口

不同的事务模型,使用了一些统一的接口,这些接口定义在 Trx 中。

事务本身相关的操作

  • start_if_need。开启一个事务。在SQL请求处理过程中,通常需要开启一个事务;
  • commit。提交一个事务;
  • rollback。回滚一个事务。

行数据相关的操作

  • insert_record。插入一行数据。事务可能需要对记录做一些修改,然后调用table的插入记录接口。提交之前插入的记录通常对其它事务不可见;
  • delete_record。删除一行数据。与插入记录类似,也会对记录做一些修改,对MVCC来说,并不是真正的将其删除,而是让他对其它事务不可见(提交后);
  • visit_record。访问一行数据。当遍历记录,访问某条数据时,需要由事务来判断一下,这条数据是否对当前事务可见,或者事务有访问冲突。

MVCC 相关实现

版本号与可见性

与常见的MVCC实现方案相似,这里也使用单调递增的数字来作为版本号。并且在表上增加两个额外的字段来表示这条记录有效的版本范围。两个版本字段是begin_xidend_xid。每个事务在开始时,就会生成一个自己的版本号,当访问某条记录时,判断自己的版本号是否在该条记录的版本号的范围内,如果在,就是可见的,否则就不可见。

有些文章或者某些数据库实现中,使用"时间戳"来表示版本号。如果可以保证时间戳也是单调递增的,那这个时间戳确实更好可以作为版本号,并且在分布式系统中,比单纯的单调递增数字更好用。

记录版本号与事务版本号

行数据上的版本号,是事务设置的,这个版本号也是事务的版本号。一个写事务,通常会有两个版本号,在启动时,会生成一个版本号,用来在运行时做数据的可见性判断。在提交时,会再生成一个版本号,这个版本号是最终设置在记录上的。

trx start:
  trx_id = next_id()
  read record: is_visible(trx_id, record_begin_xid, record_end_xid)

trx commit:
  commit_id = next_id()
  foreach updated record: update record begin/end xid with commit_id

Q:为什么一定要在提交时生成一个新的版本号?只用该事务之前的版本号不行吗?会有什么问题?

版本号与插入删除

新插入的记录,在提交后,它的版本号是 begin_xid = 事务提交版本号,end_xid = 无穷大。表示此数据从当前事务开始生效,对此后所有的新事务都可见。 而删除相反,begin_xid 保持不变,而 end_xid 变成了当前事务提交的版本号。表示这条数据对当前事务之后的新事务,就不可见了。 记录还有一个中间状态,就是事务刚插入或者删除,但是还没有提交时,这里的修改对其它事务应该都是不可见的。比如新插入一条数据,只有当前事务可见,而新删除的数据,只有当前事务不可见。需要使用一种特殊的方法来标记,当然也是在版本号上做动作。对插入的数据,begin_xid 改为 (-当前事务版本号)(负数),删除记录将end_xid改为 (-当前事务版本号)。在做可见性判断时,对负版本号做特殊处理即可。

假设某个事务运行时trx id是 Ta,提交时是 Tc

operation trx state begin xid end xid
inserted committed Tc +∞
deleted committed some trx_id Tc
insert uncommit -Ta +∞
delete uncommit some trx_id -Ta

并发冲突处理

MVCC很好的处理了只读事务与写事务的并发,只读事务可以在其它事务修改了某个记录后,访问它的旧版本。但是写事务与写事务之间,依然是有冲突的。这里解决的方法简单粗暴,就是当一个写事务想要修改某个记录时,如果看到有另一个事务也在修改,就直接回滚。如何判断其它事务在修改?判断begin_xidend_xid是否为负数就可以。

隔离级别

我们通常在聊事务隔离级别时,都会说脏读(Read Uncommitted)、读提交(Read Committed)、可重复读(Repeatable Read)和可串行化(Serializable),说这些时也通常都会提到大名鼎鼎的MySQL。但实际上隔离级别不止是这4种。 不过这里也没有对隔离级别做特殊的处理,让它顺其自然。

Q: 通过上面的描述,你知道这里的MVCC是什么隔离级别吗?

遗留问题和扩展

当前的MVCC是一个简化版本,还有一些功能没有实现,并且还有一些已知BUG。同时还可以扩展更多的事务模型。

  • 事务提交时,对外原子可见

当前事务在提交时,会逐个修改之前修改过的行数据,调整版本号。这造成的问题是,在某个时刻,有些行数据的版本号已经修改了,有些还没有。那可能会存在一个事务,能够看到已经修改完成版本号的行,但是看不到未修改的行。 比如事务A,插入了3条数据,在提交的时候,逐个修改版本号,某个情况下可能会存在下面的场景(假设A的事务ID是90,commit id是100):

record begin xid end xid data
R1 100 +∞ ...
R2 100 +∞ ...
R3 -90 +∞ ...

此时有一个新的事务,假设事务号是 110,那么它可以看到记录R1和R2,但是看不到R3,因为R3从记录状态来看,还没有提交。

  • 垃圾回收

随着数据库进程的运行,不断有事务更新数据,不断产生新版本的数据,会占用越来越多的资源。此时需要一种机制,来回收对任何事务都不再可见的数据,这称为垃圾回收。垃圾回收也是一个很有趣的话题,实现方式有很多种。最常见的是,开启一个或多个后台线程,定期的扫描所有的行数据,检查它们的版本。如果某个数据对当前所有活跃事务都不可见,那就认为此条数据是垃圾,可以回收掉。当然,这种回收方法最简单,也是最低效的,同学们如何优化或者实现新的回收方法。

  • 多版本存储

当前miniob仅实现了插入和删除,并不支持更新操作。而插入和删除最多会存在两个版本的数据,从实现上来看,最多需要一条数据就可以。这大大简化了MVCC的实现。但是也因此没有涉及到MVCC非常核心的多版本数据存储问题。如何合理的存储多个版本的数据,对数据库的性能影响也是巨大的。比如多个版本数据串联时,使用从新到旧,还是从旧到新。两种方式都有合理性,适用于不同的场景。另外还有,多版本的数据存储在哪里?内存还是磁盘,是与原有的数据放在同一个存储空间,还是规划单独的空间,各有什么优缺点,都适用于什么场景。还有,更新数据时,复制整行数据,还是仅记录更新的字段。各有什么优缺点,各适用于什么场景。

  • 持久化事务

持久性是事务的基本要素之一,是指事务修改后的数据,在数据库重启或者出现异常时,能够从磁盘中将数据恢复出来。除了将修改的数据直接写入到磁盘,还有一个常用的技术手段是WAL,比如Redo日志和Undo日志。那么什么情况下使用Redo,什么时候使用Undo,以及如果只使用Redo或者只使用Undo会有什么问题。另外还有如何存储这些日志,B+树的持久化怎么处理等。有兴趣的同学可以再了解一下 Steal/No-StealForce/No-Force 的概念。

  • MVCC的并发控制

如前文描述,这里的写事务并发冲突处理过于简单粗暴,以至于可以避免的冲突却没有避免。

  • 基于锁的并发控制

MVCC的并发控制通常认为是乐观事务,就是我们认为此系统中事务之间大部分情况下不会存在冲突。但是在OLTP系统中,访问冲突可能是非常频繁发生的,这时候使用悲观事务,效率会更高一点。常见的悲观事务实现方法就是基于锁来实现。假设使用记录锁(行锁)来实现并发,在读数据时加读锁,写时加写锁,也可以实现多种级别的隔离机制。另外,还可以将使用基于锁的机制与MVCC结合起来,实现更好的并发控制。

顺便提一下一个常见的问题,就是在使用行锁时,如何与页面锁(latch)协调? 大家都知道,latch 都是短锁,在latch保护范围内,都不应该出现长期等待的事情。另外,latch没有死锁检测,不处理锁冲突。而行锁是一种长锁,需要做锁冲突处理,可能需要等待。那在拿着某个latch时,需要等待行锁时,如何处理?

这是很多做了CMU 15445课程的同学没有考虑的问题,15445 课程中将 Lock Manager 模块单独拎出来让同学们做练习。但是当行锁与latch同时工作时,它的复杂度将提升好几个量级。

进一步学习

事务是非常复杂非常有趣的,相关的话题也已经有非常多的研究。如果对事务感兴趣,可以在了解数据库整体实现基础之上,深入研究事务的实现原理。 这里推荐一些介绍数据库入门的书籍: - 《数据库系统概念》该书是数据库领域的经典教材之一,涵盖了数据库基本概念、关系型数据库设计、事务处理、并发控制等方面的内容,也可以着重阅读事务相关的内容 - 《数据库系统实现》:该书是一本数据库系统实现方面的教材,讲解了数据库系统的核心组成部分,包括事务处理、索引、查询优化等方面的内容,对事务处理机制进行了较为细致的讲解 - 《MySQL技术内幕:InnoDB存储引擎》:该书是一本MySQL数据库方面的重要教材,对InnoDB存储引擎的事务处理机制进行了详细的阐述,包括事务的隔离级别、MVCC实现、锁机制等方面。

想直接上手看工业届的事务实现原理,欢迎阅读: - 分布式事务并发控制的思考与实现 - OceanBase事务引擎的技术创新 - 深入浅出事务的本质,附OceanBase事务解析14问!

内功深厚想要直接阅读源码:OceanBase 事务源码

还有一些著名开放课程,理论结合实践,比如 - CMU 15445。理论结合实践,不仅有课程讲解,还有实验项目,对理解数据库实现原理帮助非常大 - CMU 15721。卡内基梅陇大学的数据库进阶课程

如果上面的还感觉太浅,可以持续找一些事务的论文研读:

大家看了这些论文会发现,都是一些陈年老论文。数据库领域发展这么多年了,技术依然不过时。

如果这些还不够,可以问问ChatGPT还有啥资料。如果觉得单机上的玩腻了,可以再看看分布式事务,总之希望你能玩得愉快。