首页 cmu 15-445

上节课研究了2PL实现并发控制

2PL是一种悲观锁,在问题出现前就阻止了问题的发生

TimesTamp ordering (T/O) 时间戳顺序,乐观锁

基本原理:给每一个事务一个时间戳,决定如何处理,出问题怎么办

时间戳先的,对于数据库要保证先执行完毕

每一个txn给一个时间戳,让这个时间戳是单调递增的,可以是

  • 系统时钟(system clock),但是系统时钟是有问题的
  • 逻辑计数器(logical counter),只适合单节点,不适合分布式
  • 二合一(hybrid)

研究问题:

  • basic timestamp ordering(T/O) protocol 基础方法
  • optimistic concurrency control 扩展方法
  • isolation levels

BASIC T/O

读写任何对象都不加锁,每一行记录都有两个值,读时间戳与写时间戳,存着上一次进行该类型操作的事务号

每次操作时去比较自身和记录的时间戳,宗旨就是不能操作未来的事物

读操作:

如果发现被比本身大的事务写过了,

  • 自杀,用一个新的时间戳重新开始

如果没有被本身大的事务操作过

  • 更新时间戳
  • 让X拷贝到本地一份做副本,做快照,防止出问题

如果是写操作

只要有发现被本身大的事务读或写过了,都要回滚重启

否则

  • 更新时间戳
  • 拷贝一个副本

过程:流式执行,发现问题就回滚,这次是没有冲突的

image-20220305190057010.png

其实是可以优化的,因为写操作只保留最后的值,所以可以有优化

thomas write rule

如果是时间戳小于读的时间戳,只能重来

但是如果是时间戳小于写的时间戳,(未来有一个事务改了这个事务),我们可以等效成我们曾经写过,但是被改了

如果不考虑托马斯优化,

优点:

  • 没有锁,更没有死锁
  • 长事务可能会饥饿如果短事务很多

数据库的恢复是很困难的: 一个长事务执行半天要abort了,短事务都commit很多了,是无法恢复的

而且读的时候要本地拷贝,所以代价是很大的,

如果事务是短且少,这种方式是比较好的

optimistic concurrency control 乐观并发控制,这也是基于T/O的

读的所有数据都保存本地,如果要进行写操作,那就写到本地,不写入数据库,本地临时记一下

等事务commit的时候,跟其他txn比较,如果没问题就一次性提交,有问题重来

步骤:

  • read phase 进行读写操作,对于数据库只有读,写只在本地进行
  • validation phase 校验,把要写的进行校验,有问题直接重来
  • write phase 进行写操作,对数据库进行提交操作

只有在校验的过程时才获得时间戳

image-20220305192950524.png

具体过程:

read phase:

跟踪记录写过和读过那些数据,存读的数据是为了防止发生重复读操作

validation phase:

给txn 一个时间戳,数据库要保证小时间戳先发生,要防止成环

具体方法:

  • backward validation
  • forward validation

backward:

比较自身和之前事务看是否成环,成环就自杀

forward:

校验未来的事务,校验与未来事务已发生的部分是否有冲突

这里就可以选择自杀还是杀掉未来事务

  • 情况1 : 有一个事务针对完全发生另一个再发生,根本不用校验

image-20220305193703103.png

  • 情况2 : T 2在 T 1 开始其写入阶段之前完成,并且 T 2 不写入 T 1 读取的任何对象,直接让T 1 重来就可以了
  • WriteSet(T i ) ∩ ReadSet(T j ) = Ø

image-20220305194103777.png

要改成这样

image-20220305194030115.png

  • 情况3: T i 在 T j 完成其读取阶段之前完成其读取阶段,并且 T i 不会写入任何由 T j 读取或写入的对
  • WriteSet(T i ) ∩ ReadSet(T j ) = Ø
  • WriteSet(T i ) ∩ WriteSet(T j ) = Ø

当T2读操作时,是安全的,因为他是靠后的,正好读取靠后的内容

image-20220305195507438.png

write phase:

到了写这个阶段,锁全表,一次性写完,不要并发

occ的思考:

冲突低的时候好用,尤其是全读操作,或者读写操作没有任何交点

数据库非常大,查询对于整个表是比较均匀的,可以考虑occ,因为这时候加锁是浪费的

缺点还是拷贝会有本地开销,校验会很复杂,写锁表会浪费并发量

而且出问题的时候是提交的时候,之前做的算子都浪费了,无用功有点多

无论是二阶段锁还是 T/O 都是在研究update,而没有研究insert与delete

因为如果有这种操作就会产生幻读(读到了之前不存在的语句),

为了解决这种问题:

  • re-execute scans
  • predicate locking
  • index locking

re-execute scans:

涉及到范围扫描的操作,提交前再来一次,简单粗暴

这样会提高性能

predicate locking 谓词锁

给where这个谓词加锁

  • select加 shared lock
  • update insert delete 加 exclusive lock

image-20220305201143522.png

index locking 索引锁

如果谓词中有索引的话,就去锁索引的页,如果谓词没有索引,就只能加表锁了

mysql 是一种间隙锁,例如1,3,5,7,9, 1 3之间的间隙加锁,间隙是不能插入东西的,其他的不用管

其实有些事务是可以忍受非可串行化的,可串行化是一种最高级别

isolation levels 隔离级别

控制事务之间暴露的程度

事务之间暴露会产生的问题:

  • dirty reads 脏读 读未提交
  • unrepeatable reads 不可重复读 数据不一样了
  • phantom reads 幻读 数据比原来多了

levels:

  • SERIALIZABLE: No phantoms, all reads repeatable, no dirty reads.
  • REPEATABLE READS: Phantoms may happen. 可重复读
  • READ COMMITTED: Phantoms and unrepeatable reads may happen. 读已提交
  • READ UNCOMMITTED: All of them may happen.

具体实现:

  • serializable : 首先要加所有锁,加index锁,和严格的2PL
  • repeatable reads: 上面没有index lock
  • read committed: 上面S锁是立即释放的
  • read uncommitted: 同上,无S锁

SQL-92是支持isolation levels,

而且可以告诉事务是只读的就可以更快




文章评论