OCC和MVCC的区别是什么?

关注者
157
被浏览
4,521

4 个回答

*最简单的并发控制算法是2PL(2 Phase Locking),分为两阶段:

1)获得锁阶段;

2)释放锁阶段。

一般2PL被称为是悲观并发控制。


与之相对的是乐观并发控制OCC( Optimistic Concurrency Control)。OCC假设事务会成功,开始事务时该读读,该写写,不加锁。只有到提交时做一下验证,验证这个事务是不是能够成功提交。 OCC分为三阶段:

1)Read Phase, 对于读,放到Read Set,对于写,把写记到临时副本,放到Write Set。因为写是写到临时区的,属于未提交结果,其它事务读不到(这点是和MVCC的重要区别);

2)Validation Phase,重扫Read Set,Write Set,检验数据是否满足Isolation Level,如果满足则Commit,否则Abort;

3)WritePhase,或者叫做Commit Phase,把临时副本区的数据更新到数据库中,完成事务提交。


MVCC(Multiversion Concurrency Control)是另一种并发控制算法。MVCC为每条记录维护多个快照(Snapshot),通过起止两个时间戳(Begin Timestamp / End Timestamp)维护副本的可见性。读写进行的不同操作如下:

Update,创建一个新的版本(Version);

Delete,更新End Timestamp。

Read,通过起止时间戳判定记录是否对当前事务可见(OCC读不到未提交的记录,所以不需要做这个判断)。

这样,通过Snapshot,实现了读写互不阻塞。但为了实现Serializable,对读写规则还是要进行一定的限制。MVCC通过不同的方法实现。有基于锁定的,MV-2PL,如MySQL。有基于时间排序(Time Ordering)的,叫MV-TO,如PostgreSQL。其实准确来说,PG的实现叫SSI(Serializable Snapshot Isolation),不算MV-TO。也有像OCC那样基于乐观算法的,MV-OCC,即读写时不做验证,延迟到提交时验证。


效率上,2PL在锁争用比较大的情形下较好(维护锁开销小于回滚开销),OCC在冲突比较少的情形下比较高效(维护锁开销大于回滚开销),MVCC对不同类型Workload更有很好的适应性,许多RDBMS也都用MVCC,如Oracle,PostgreSQL,MySQL。还有一个效率问题,随着现在CPU核心数越来越多,考虑并发控制算法往往需要考虑它的多核扩展性好不好。由于多数MVCC,OCC算法都需要时间戳分配,时间戳通常对全局变量进行CAS(Compare And Swap)操作来计算,当核心数变大时,CAS的争用也变大了。在许多时候,2PL反倒是多核扩展性最好的算法。


另外,现在的许多并发控制方法经常混合了多种算法。先有人提出了A,后有人提出了B,再后来就有人提出了A+B,那么A+B应该是叫A呢还是叫B呢?就像上面提到的MV-2PL,MV-TO,MV-OCC。

-------------------------------------

关于并发控制算法怎么分类,有不同的意见。


《Transactional Information Systems》对并发控制算法的分类。把多版本相对于单版本,作为另一个维度看。多版本可以应用在任一算法上,形成MV-SGT,MV-TO,MV-2PL,MV-OCC等。


CMU 15-722课程里,把并发控制分为两类,2PL和TO,OCC和MVCC都归为TO。

-------------------------------------

感谢 @Ed Huang 纠正关于2PL应用场景的错误

如果我们假设CMU15-721可以代表学术界, 又假设学术界定义了名词概念的话,

那么最常有的混乱是由于OCC不仅指乐观并发控制思想, 还指特定的算法引起的.


悲观并发控制思想 v.s. 乐观并发控制思想(OCC)

悲观控制唯一的实现是2PL

乐观控制唯一的实现是Timestamps

2PL和Timestamps是唯二解决事务并发的模型.


Timestamps的实现又分为

Basic T/O, 遵循Thomas Write Rule, 每个transaction不用到commit阶段就立马写进数据结构, 依靠read timestamps和write timestamps检查保证操作序列化.

OCC算法(对, 没错这也叫OCC, 但这叫OCC算法), 所有的操作都在本地完成. 比如, 我Get A, 这不阻塞, A就复制到了本地, 之后所有对于A的操作都是在"private memory space"内, 直到commit的时候, 开始检查冲突, 有正向验证(validation), 也有反向验证, 在一定的时间区间(epoch)内.

题外话: epoch思想还用于epoch GC, 例子BW-Tree. 在一个区间内标记为垃圾的资源, 在这个区间以及之前区间的所有线程都退出后, 就可以释放掉, 不需要引用计数.

MVCC, 百家争鸣. 在不同的isolation level也有不同的表现形式, 共享的思想是通过保存多个版本来解决冲突. 很多人认为这能解决读写冲突和写读冲突, 但这是在Snapshopt Isolation(SI)下的情况. SI会导致Write Skew Anomaly. 现有50个男生, 50个女生. 事务1: 如果男生数量跟女生相同, 赶走所有女生, 换成男生. 事务2: 如果男生数量和女生相同, 赶走所有男生, 换成女生. SI等级下, 结果是毛线都没发生. 但如果我们严格遵守序列化操作, 最后要么只有100个男生, 要么只有100个女生.

所以MVCC是乐观并发控制思想的一种体现, 但不是具体严格的算法. MVCC在数据库系统中必须根据不同的isolation level搭配一些别的CC算法, 比如MySQL InnoDB的MVCC+2PL. 据我不严格判断, MyRocks的默认实现也是这样的.


还有lock和latch也是经常被误会的. lock保护的是transaction, latch保护的是数据结构. Timestamps是lock-free的, 但实现这个目标的数据结构不一定是latch-free的. 2PL不是lock-free的, 但RocksDB的memtable是latch-free的(吗?).