内存事务并发(三)

本文讨论基于乐观并发的事务控制机制。区别于乐观并发的对立方式,是悲观并发机制。悲观并发通常指的是锁并发模型。悲观体现的是,事务执行之前,就假设事务是冲突的;乐观并发机制假设事务没有冲突,先执行,如果有冲突,则回滚。

乐观事务的基本做法是分为一下三个阶段:

读阶段:事务维护读写集合,读取事务要访问的数据集,然后在事务局部集合内修改数据;

验证阶段:验证事务是否与相关活动事务冲突,冲突则回滚,重启事务。

写阶段:在验证合法后的事务,合并局部修改的数据到全局数据库中。

整个过程,有点类似git的过程,

读阶段:clone代码后,在局部修改;

验证阶段:提交代码时,会判定是否有confict

写阶段:如果代码没有conflict,就合并到公司代码库

乐观并发的原始paper出自CMU的文章:《on optimistic methods for concurrency control》

下面大致讲一个baseline的实现:

串行化

满足下面三种情况,说明两个事务之间有先后序的关系:

注意:每个事务在读阶段结束的时刻,获取时间戳,则可以保证第三条规则满足。

读阶段,写阶段

读写阶段相对简单,之间参照以下伪代码:

读阶段,在局部空间内,完成增删改查

写阶段,合并数据,并全局删除已经被删除了的数据

验证阶段:

难点是验证阶段,下面讨论三种验证方式,逐步优化

单核CPU算法

多核CPU算法优化

并行验证:

划重点:

悲观并发,悲观的地方在于,及时不冲突的事务,也要加锁。比如在理想的情况,所有事务都是read-only的,此时,事务的锁开销都是浪费了的。乐观并发,在开始执行之前便假设不存在冲突,先执行了再说,有冲突再解决。这就好比商人投资,有的人保守,投资前想着会亏本,有的人乐观,心里想到的都是怎么赚钱。

悲观并发,适合于“wrost case”, 冲突很多。

乐观并发,适合“best case”,冲突较少。

没有one algorithm fits all的并发算法。这和各种排序算法类似,折半,适合于排好序的数据。

难点是验证阶段。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180121G0D1NF00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券