内存事务并发（三）

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

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

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

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

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

整个过程，有点类似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的并发算法。这和各种排序算法类似，折半，适合于排好序的数据。

难点是验证阶段。