1.OCC算法简介

在基于锁的并发控制中，通常研究如何保证高并发的情况下避免死锁，以避免事务回滚的开销。OCC （Optimistic Concurrent Control）不使用锁，这种方法在事务间没有冲突或者冲突比较少的情况下效果比较好，而且不会发生死锁（因为没有锁），但可能发生饥饿问题。

OCC 要求事务 T 在其生命周期中按照三个阶段执行：

1. 读阶段

在该阶段，系统执行事务 T。T 读取各个数据项的值，T 中所有更新都是在私有工作区中进行的，并不对数据库进行真正的更新。

1. 验证阶段

对事务 T 进行有效性检查测试（具体参考后几节的有效性检查协议）。若测试失败，直接终止这个事务，然后重启；否则进入写阶段。该阶段的作用是为了保证数据库的一致性（ACID 中的 C），让事务的并发执行等价于某个序列化调度。

1. 写阶段(只读事务不需要)

若验证无冲突，将事务私有内存中的更新数据写入数据库使其全局可见。

每个事务有三个关联的时间戳，这三个时间戳的值是不同的而且递增：

1. StartTS(T)：事务开始执行的时间。
2. ValidationTS(T)：read 执行结束开始有效性检查的时间。
3. FinishTS(T)：事务完成局部缓存到数据库的刷写，事务结束的时间。

验证规则

对事务𝑇_𝑖 , 𝑇_𝑗 ,且 𝑇_𝑖<𝑇_𝑗，则检查事务𝑇_𝑗是否符合可串行化（即𝑇_𝑖在𝑇_𝑗之前完成），需满足如下三种条件之一：

1. 𝑇_𝑖在𝑇_𝑗开始读取阶段前完成写入阶段，即𝑇_𝑖在𝑇_𝑗开始之前提交；
2. 𝑇_𝑖在𝑇_𝑗开始验证阶段前完成写入阶段，且𝑇_𝑖的写集与𝑇_𝑗的读集不相交；
3. 𝑇_𝑖在𝑇_𝑗完成读取阶段前完成读取阶段，且𝑇_𝑖的写集与𝑇_𝑗的读集和写集都不相交。