miniob-transaction.md

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

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

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

**Vacuous（真空）**

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

**MVCC**

多版本并发控制，是一种常见的事务实现。著名的MySQL数据库也支持MVCC，[OceanBase](https://github.com/oceanbase/oceanbase)也实现了此机制。

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

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

## 如何运行与测试
当前MiniOB支持两种类型的事务模型，并且默认情况下是Vacuous，即不开启事务特性。

**测试MVCC**

编译时增加选项 `-DCONCURRENCY=ON`:
```bash
cmake -DCONCURRENCY=ON ..
```
然后在build目录执行 make。编译完成后启动 observer 服务端进程。

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

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

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

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

启动observer后，可以使用obclient连接observer：

```bash
./bin/obclient -s miniob.sock
```

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

## 更多的实现原理

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

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

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

**事务本身相关的操作**

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

**行数据相关的操作**

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

### MVCC 相关实现
**版本号与可见性**

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

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

**记录版本号与事务版本号**

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

```cpp
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_xid`或`end_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-Steal` 和 `Force/No-Force` 的概念。

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

- 基于锁的并发控制

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

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

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


# 进一步学习

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

想直接上手看工业届的事务实现原理，欢迎阅读：
- [分布式事务并发控制的思考与实现](https://open.oceanbase.com/blog/1100128)
- [OceanBase事务引擎的技术创新](https://open.oceanbase.com/blog/1100194)
- [深入浅出事务的本质，附OceanBase事务解析14问！](https://open.oceanbase.com/blog/1100248)

内功深厚想要直接阅读源码：[OceanBase 事务源码](https://github.com/oceanbase/oceanbase/tree/master/src/storage/tx)

还有一些著名开放课程，理论结合实践，比如 
- [CMU 15445](https://15445.courses.cs.cmu.edu/spring2023/)。理论结合实践，不仅有课程讲解，还有实验项目，对理解数据库实现原理帮助非常大
- [CMU 15721](https://15721.courses.cs.cmu.edu/spring2023/)。卡内基梅陇大学的数据库进阶课程

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

- [A Critique of ANSI SQL Isolation Levels](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf) 该论文针对ANSI SQL标准中隔离级别的定义进行了深入的分析，提出了一些改进的建议。天天看到RC/RR名词的，可以看看这篇论文，了解更详细一点。

- [Granularity of Locks and Degrees of Consistency in a Shared Data Base](https://web.stanford.edu/class/cs245/readings/granularity-of-locks.pdf) 这也是一个又老又香的论文，提出了基于锁的并发控制。

- [An Empirical Evaluation of InMemory Multi-Version Concurrency Control](https://www.vldb.org/pvldb/vol10/p781-Wu.pdf) 介绍MVCC可扩展性的。通过这篇论文可以对MVCC有非常清晰的认识。

- [Scalable Garbage Collection for In-Memory MVCC Systems](http://www.vldb.org/pvldb/vol13/p128-bottcher.pdf) 这里对各种垃圾回收算法做了说明，并且有些创新算法。

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

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