Transaction & Distributed Transaction(1)

[WIP] 事务

MySQL 并发控制

  • Shared Lock (read lock)
  • Exclusive Lock (write lock)

提供锁的粒度

  • 行锁
  • 表锁

事务

ACID

A:原子性,ddia中描述为更像可中断性,中断后还能保持事务的性质

C: 一致性,更像是客户端的保障,类似我们两个转账的时候不能有人钱白白增加了这种,感觉这玩很泛:数据库从你定义的一致状态走向另一个一致状态

I:隔离型,一个事务对别的事务正在读/写的东西读写的隔离

D:持久性,我总觉得这个很重要但是最没啥说的

串行

事务操作分为读写的话,有 R(A), W(A), 那么可以得到串行化(和独立执行一样的)调度。

MySQL 隔离级别

READ UNCOMMITED

  • 未提交的写对其它事务可见
  • 事务可以读取未提交的数据(脏读)
  • 最低的级别

READ COMMITED

  • 只能读到已经完成提交的事务,写对其它事务不可见:没有脏写
  • 解决了 Dirty Read 的问题,写入只会覆盖已经写入的数据
  • 两次同样查询,可能没有相同结果:不可重复读

REPEATEDABLE READ

挺严格的限制了,一般实现 2PL 会到这个级别

无法解决表中插入新数据的 Phantom Read (幻读)

  • MySQL 默认级别
  • 用 row-level lock 防止脏鞋
  • 对写入时,记住旧提交值和内存/现在设置的值,别的事务会读到旧值

SERIALIZABLE

  • 强制串行,应该有巨多死锁?

img

事务的麻烦

脏读

img

  • 读的东西需要对方提交才能看到,可能只看到部分更新,违反一致性
  • 允许脏读,可能会看到需要回滚的数据,cascading abort!

脏写

  • 事务写入后覆盖前
  • 但是先前没有提交,可能他应当提交的晚呢?一致性被违反了

img

买同一辆车,被写混了。

可重复读

img

这种异常被称为不可重复读(nonrepeatable read)或读取偏差(read skew)

其实这个实际上存储的东西没问题,但是你读的确实有问题

  • 严重性:可能复制的时候会“不一致”
  • 解决:SI 快照隔离可以处理

丢失更新(TODO)

常见操作序列:fetch - write - 写回

eg:

  1. inc (不考虑 inc lock 这种)
  2. 两个用户同时编辑界面

解决:

Update ... set

哦,这是个原子写入

for update

显示锁定

也可以 CAS:

UPDATE ... SET content = 'new'
WHERE id = xxx AND content = 'old';

写入偏差、幻读

可能两个都成功了,GG

img

写入两个事务,更新两个不同对象,但是之间有约束关系

  • 可重复读不能解决,序列化可以

  • 不能序列化的话,要显示锁定:

    img

事务的实现-悲观

分为两个阶段:

  • 获得锁的第一阶段:Growing
  • 释放锁的第二阶段:Shrinking

img

数据库系统实现中,提供了理论证明,事务被当成是所有锁释放的时候完成的

但是理论上的 2PL 会有 Cascading abort:

img

T1 解锁阶段 abort 了,那T2 也 应该 abort,明显就不对了吧,而且还读到了别的事务正在写的东西(俗称脏读)

所以一般实现上可能会考虑 strict 2PL

img

死锁检测

原本以为不重要,后来感觉这种玩意死锁情况很多,同事也写了死锁,所以我加上了

用 DAG 检测到 deadlock 会挂掉一个,或者等待时间挂掉

锁级别和意向锁(Intention lock)

  • IS
  • IX
  • SIX

<— TODO:

补全这边

—>

Timestamp Ordering Concurrency Control

是一种乐观的并发控制

Determine serializability order of txns before they execute.

对于每个 txn ,可以找到一个unique fixed timestamp that is monotonically increasing

可以用:

  • 系统时钟
  • 逻辑时钟
  • 混合

在 TiDB 的 PD 中,似乎有用到 Etcd 来做。Zookeeper 似乎也有这个功能,到时候我会去看看

if TS(txn1) < TS(txn2)
txn1 调度必须比 txn2 早

等同于锁,这里也有读写的区分,可以看到,对于行/对象 X:

  • W-TS 最近的 write timestamp
  • R-TS 最近的 read timestanp

基本的法则是,对于你的 txn_id ,你如果发现ts比你大/小且异常的(这个我等会儿会解释),你就要小心了

读法则

条件:读取一个对象 X,要判断自身的 txn_id 和对象的 W-TS,如果 W-TS 比自身的 txn_id 大,那abort,否则读取

读后行为:把对象的 R-TS 设制成 , 把 X 拷贝到本地的空间

写法则

条件:

  • 对象X上没有比 txn_id 更大的 W-TS 和 R-TS
  • 写入对象,并且为了防止 Repeatable Read 拷贝一份旧的对象 X

Thomas write rule

  • 碰见比自己TS大的W-TS,因为反正之后也会被它写入成这个,所以放着不管继续执行

(TODO:这个的问题是啥,我有点模糊,对于 abort 么)

T/O一点小结论: 对于不用 Thomas write rule 的 txn

  • R/W 比较多的 txn 可能会starve
  • 不过没有 deadlock

Permits schedules that are not recoverable.

我没看懂上面这句话什么意思

A schedule is recoverable if txns commit only after all txns whose changes they read, commit. Otherwise, the DBMS cannot guarantee that txns read data that will be restored after recovering from a crash.

哦,看看下面这张图就该懂了:

img

因为看来这个模型有一个假设:

  • 事务的调度按照 txn_id 来进行
  • 之前写的都能被读到

哦,那之前的 abort 就全忘了,所以才会有 recoverable 这个概念,所以有:

所有的读到的 txn 都 commit 了,这个 txn 才是 recoverable 的

严重的情况

img

这种情况下,你的 t2 结果这个 read,大概也是不可靠的,没法处理 abort/recover的概念

所以,以上的例子只有成功执行才是成功的

Performance Issues

  1. High overhead from copying data to txn’s workspace and from updating timestamps.
  2. Long running txns can get starved. → The likelihood that a txn will read something from a newer txn increases.

第二个是很好理解的,第一个实际上我个人不太理解(从自身的空间读写么?)

If you assume that conflicts between txns are rare and that most txns are short-lived, then forcing txns to wait to acquire locks adds a lot of overhead.

A better approach is to optimize for the noconflict case.

哦,是这样,在乐观的并发控制( OCC) 中

DBMS 会给每个 txn 创建一个 private workspace

  • 被 read 的数据会被 copy 到 这个 workspace
  • 修改和写入会被 applied 到这个 workspace

当一个 txn 发生 commit 的时候:

  • DBMS等待/观察它所读的事务有没有出现 abort
  • 当它依赖的事务全部被 commit 的时候,把这些变化 apply 到 global 的 workspace

OCC 的论文和原阶段

  1. Read Phase

    Track the read/write sets of txns and store their writes in a private workspace. (也不全是 read 啊,为啥要叫 read phase)

  2. Validation Phase When a txn commits, check whether it conflicts with other txns. (和我们之前讲的好像差不多)

  3. Write Phase If validation succeeds, apply private changes to database. Otherwise abort and restart the txn.

加上这个以后,加上了 private workspace,一定程度上解决了之前的 abort 问题

The DBMS needs to guarantee only serializable schedules are permitted.

T_i checks other txns for RW and WW conflicts and makes sure that all conflicts go one way (from older txns to younger txns).

同时对象的R-TS

  • R-TS 原本是检测下列的冲突:
    • W(txn_id) > R-TS : 写入之前的被更晚的 txn 读取了,无法写入

img

img

这里T1 T2 开始,T2 的 R(A) 读取了全局空间的 A。

Ti Tj 没有冲突的条件:

WriteSet()ReadSet() = Ø → WriteSet()WriteSet() = Ø

OCC Performance

High overhead for copying data locally. Validation/Write phase bottlenecks.

Aborts are more wasteful than in 2PL because they only occur after a txn has already executed.

PARTITION-BASED T/O

按 time 进行时间的分区

OCC 也要有谓词锁

MVCC

对于一个对象,RDBMS 保存多个物理版本的数据

  • txn 写,创建新对象
  • txn 读,读到(…, txn开始时间) 这一段的最新数据

对于 MVCC,

  1. Writer 和 Readers 不会互相 block
  2. txn 可以根据自己的 timstamp 从 Snapshot 中读到数据
  3. 支持历史查询

MVCC Example

img

Begin 和 End 可以当成 Created ByDeleted By 这两个 field.

  • T1 read 正常从 [Begin, End) 包含 1 的 区间读
  • W(A),写入相当于删除了旧的A,创建了新的A,Created By Txn 2.

这个例子比较简单,下面我们添加一个相对复杂的例子:

img

然后可以看到:

img

  • Commited 的时候把 end 提交

多个版本的存储

对于我本人所在的 TiKV 和 Percolator,多个版本是靠 key/value 的编码实现的。

物理的表这里可以靠 Append Only 向后添加:

img

链式相连

物理空间的回收(reclaimable)

回收条件当然要:

  • Active 的事务不再会读到这个 row/col 对应的这个版本
  • 可能由 aborted 的 txn 创建

回收可以是下面两个 level 的:

  • tuple level: 针对 tuple 回收
  • transaction level: 对 transaction 对应的 ts 回收

MVCC 的问题

事务从数据库读取一些数据,检查查询的结果,并根据它看到的结果决定采取一些操作(写 入数据库)。但是,在快照隔离的情况下,原始查询的结果在事务提交时可能不再是最新 的,因为数据可能在同一时间被修改。

换句话说,事务基于一个前提(premise)采取行动(事务开始时候的事实,例如:“目前有 两名医生正在值班”)。之后当事务要提交时,原始数据可能已经改变——前提可能不再成 立。

所以对于冲突需要:

  • 检测 MVCC 对象是不是读了未来的数据,发生了(对旧MVCC对象版本的读取)
  • 检测写入会不会搞坏掉之前的读取

我们分别介绍一下

检测旧MVCC读取

  1. Txn43 read cond, if cond is true, continue
  2. Txn42 set cond false
  3. Txn43 do…
  4. Txn42 commited
  5. Txn43 commited? 有问题咯

对,这个显然不对对吧

img

所以对于一个有更小 txn 的事务,它是确实可以做出修改,并且导致 txn 略大的事务有不正常的输出的,所以我们在读的方面确实要:

为了防止这种异常,数据库需要跟踪一个事务由于MVCC可见性规则而忽略另一个事务的写入。当事务想要提时,数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样,事务必须中止。

TODO:我还是不是很明白这个问题是怎么解决的

检测影响之前读取的写入

img

这里写入/修改会被检测,防止出现Skew write

Lost Update

需要显式锁定

img