上节课研究了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拷贝到本地一份做副本,做快照,防止出问题
如果是写操作
只要有发现被本身大的事务读或写过了,都要回滚重启
否则
- 写
- 更新时间戳
- 拷贝一个副本
过程:流式执行,发现问题就回滚,这次是没有冲突的
其实是可以优化的,因为写操作只保留最后的值,所以可以有优化
thomas write rule
如果是时间戳小于读的时间戳,只能重来
但是如果是时间戳小于写的时间戳,(未来有一个事务改了这个事务),我们可以等效成我们曾经写过,但是被改了
如果不考虑托马斯优化,
优点:
- 没有锁,更没有死锁
- 长事务可能会饥饿如果短事务很多
数据库的恢复是很困难的: 一个长事务执行半天要abort了,短事务都commit很多了,是无法恢复的
而且读的时候要本地拷贝,所以代价是很大的,
如果事务是短且少,这种方式是比较好的
optimistic concurrency control 乐观并发控制,这也是基于T/O的
读的所有数据都保存本地,如果要进行写操作,那就写到本地,不写入数据库,本地临时记一下
等事务commit的时候,跟其他txn比较,如果没问题就一次性提交,有问题重来
步骤:
- read phase 进行读写操作,对于数据库只有读,写只在本地进行
- validation phase 校验,把要写的进行校验,有问题直接重来
- write phase 进行写操作,对数据库进行提交操作
只有在校验的过程时才获得时间戳
具体过程:
read phase:
跟踪记录写过和读过那些数据,存读的数据是为了防止发生重复读操作
validation phase:
给txn 一个时间戳，数据库要保证小时间戳先发生，要防止成环
具体方法:
- backward validation
- forward validation
backward:
比较自身和之前事务看是否成环,成环就自杀
forward:
校验未来的事务,校验与未来事务已发生的部分是否有冲突
这里就可以选择自杀还是杀掉未来事务
- 情况1 : 有一个事务针对完全发生另一个再发生，根本不用校验
- 情况2 : T 2在 T 1 开始其写入阶段之前完成，并且 T 2 不写入 T 1 读取的任何对象,直接让T 1 重来就可以了
- WriteSet(T i ) ∩ ReadSet(T j ) = Ø
要改成这样
- 情况3: T i 在 T j 完成其读取阶段之前完成其读取阶段,并且 T i 不会写入任何由 T j 读取或写入的对
- WriteSet(T i ) ∩ ReadSet(T j ) = Ø
- WriteSet(T i ) ∩ WriteSet(T j ) = Ø
当T2读操作时,是安全的,因为他是靠后的,正好读取靠后的内容
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
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,
而且可以告诉事务是只读的就可以更快
