本文是阅读论文Efficient Optimistic Concurrency Control Using Loosely Synchronized Clocks的读书笔记.

概述

论文是在1995年发表的，当时分布式数据系统中怎么实现分布式事务这个方向就是一个热门的领域，这么多年过去了，一直到现在，当时提出的OCC（Optimistic Concurrency Control）仍然是当今的一个热门个研究方向。

人们一直都希望能够实现一个高效、可扩展、稳定的持久化存储系统，而本文提出的OCC正是用来解决这个问题的，其特点是：

1. 数据在client端本地缓存，在server端持久化
2. 对提交的事务提供了serializability and external consistency的保证
3. 通过松散同步的时钟获取global serialization

OCC支持并发事务，但是没有像传统方法那样对每个数据都保存着并发控制的信息，而是只保存了一个版本号，保证了内存消耗尽量的少，并且低存储消耗的情况下，也保证了性能。

介绍

本文介绍的OCC适用的场景是什么？

分布式面向对象数据库系统，数据持久化由server负责，client为了提高性能会对数据进行cache。

为什么叫乐观并发控制？

乐观是相对比悲观算法来说的，为了保证事务的external consistency，一个简单的方法就是通过锁，将所有事务串行化，但是这样子肯定会使得性能很差，那解决方法就是去掉锁，只有当冲突发生的时候才采取措施，因此乐观是相对于悲观的加锁算法来说的。

什么是external consistency？

external consistency(有些文章叫Linearizability或者strict serializability) 是指：后开始的事务一定可以看到先提交的事务的修改

乐观的代价

由于我们不采用锁，因此OCC有其使用的限制：适合冲突少的场景，如果大量事务都发生冲突，那OCC会有非常糟糕的性能，因为：

悲观算法只会延迟事务的执行，乐观算法一旦冲突，会直接终止事务执行。

乐观的实现

乐观算法本质上只是将冲突的检测延后了，当发生冲突后进行恢复，因此核心解决的问题有两个：

1. 冲突检测
2. 冲突恢复

环境

本文提出的OCC已经在面向对象数据库Thor中实现，下面给出Thor的模型图

Thor模型图

此处每个应用直接运行在client上，数据持久化在server上，为了提高性能，每个client本地对数据都进行了cache，应用可以直接在client上执行，然后操作本地cache中的数据，最后提交时才与后端servers进行通信。

在数据提交的时候，会带上两部分信息：

1. validation information：表示本次事务T中涉及到的数据的读写类型
2. installation information：修改后的数据

client发送commit请求给后端server，如果这些数据是server自己拥有的，则进行提交操作，否则，server转换为Coordinate角色，和拥有数据的participants一起完整事务的提交操作。

此时coordinate和participants之间会涉及到2-phase protocol，下面简要的描述下。

第一阶段如下：

1.1 coordinate发送prepare msg给各个参与者，消息包含了validation information和installation information

1.2 参与者验证通过后，将 installation information记录到磁盘，回复ok

1.3 coordinate收到所有参与者回复ok后，记录一条commit消息到本地磁盘，然后回复给客户端说ok

第二阶段是异步执行的

2.1 coordinate发送commit消息给各个参与者

2.2 参与者将installation消息中的新值覆盖掉老值，并在本地记录一条commit日志，回复给coordinate说ok

当server提交了事务后，需要发送invalidation messages给除了客户端之外的其他持有缓存数据的客户端，那怎么找到这些客户端呢？

server这边对每个客户端都存着一个cached set，这些invalidation messages不要求正确，但是需要满足下面两点：

1. 如果client收到invalidation messages，当前执行中的transaction还没读到旧数据了，那将本地cache中的数据失效
2. 如果当前transaction已经读到旧数据了，则立即终止当前transaction

当客户端处理完invalidation messages消息后，回复给server，server将其从失效集合（invalid set）中移除。

高效的验证规则