《A Critique of ANSI SQL Isolation Levels》论文中第一次提出了Snapshot Isolation隔离级别（后面简称为SI）。传统OLTP数据库，在实现SI时通过行锁来解决WW冲突防止LostUpdate的问题，通过SI能达到RC和RR隔离级别（严格意义上说SI和RR之间没有可比较性，SI有A5B的异象，而RR的定义中没有这个问题；同时RR有P3的异象）。

在lock-based的SI基础上要实现串行化隔离级别，还要解决A5B的问题，需要引入其他机制来检测RW，PostgreSQL通过SIRead结构记录每个事务操作的对象（表，页面，Tuple，索引页）并检测是否存在环。

SI+RW检测是串行化的充分不必要条件，存在误判的case。

Percolator本质上是把单机lock-based的SI进行了扩展：

1. LOCK COLUMN：对应单机的行锁，Prewrite阶段通过LOCK来检测WW冲突；
2. WRITE COLUMN：对应单机的CLog，分布式下通过随机选取一个key做为Primary，事务的原子提交发生在这个key上，然后再异步的更新其他key的WRITE COLUMN，加速后续读取；

本文提出了lock-free的Write Snapshot Isolation隔离级别，符合串行化隔离的调度要求。核心思想是检测RW冲突，并论述了在这个算法中WW冲突是不必要的。另外，Write-SI是串行化隔离的充分不必要条件，因此它也存在误判的case。

Write-SI系统需要有一个组件来检测RW冲突，记录所有最近提交的WriteSet。

FoundationDB实现了分布式的Write-SI，把对RW检测的组件也做成了分布式化，按照key rangge进行了切分。

下面是正文。

Abstract

SI没有达到串行化隔离级别，开发者仍然需要考虑非串行化的异象。

Google Percolator在BigTable上进行了事务的支持，它是lock-based snapshot isolation。而本文提出了lock-free的write-snapshot isolation，它支持串行化隔离，基础的想法是检测RW冲突。

1. Introduction

SI的好处是读写互相不阻塞，在写事务更新时读事务可以读取某个版本从而不会被写事务阻塞。存在WW冲突的问题：并发事务更新同一行。

WW冲突一个显而易见的解法是在更新一行之前对这个行上锁，就是所谓的行锁。一个长事务可能会更新大量的行，因此行锁被记录到了Tuple所属的页面中，会随着页面刷脏一起被刷到盘上。如果存在WW冲突则abort（PG中根据事务隔离级别是RC还是RR来决定是否abort）。

对于ReadOnly的事务无需维护额外的锁。

在上述基础上实现串行化还需进一步检测RW冲突，可以看到不仅要检测WW还要检测RW冲突才能达到串行化。

本文论述WW检测并不是串行化的必要条件，仅仅做RW检测就能提供串行化隔离，同时RW的并发性和WW的并发性相当。

2. Snapshot Isolation

上图中，

1. 事务TXNn能读取TXNo的更新；
2. TXNn和TXNc都更新了r，同时也是并发的事务，因此两者要abort一个;

SI中每个事务对应2个timestamp：

1. 事务开始时间（在发生read之前），Ts(txni);
2. 事务提交时间（在commit之前）Tc(txni)；

WW冲突的条件：

1. Spatial overlap：修改了一个r；
2. Temporal over：并发执行Ts(txni) < Tc(txnj) and Ts(txnj) < Tc(txni)；

2.1 Lock-based Implementation of Snapshot Isolation

未提交数据直接写入DB，此时这些数据的版本为事务开始时的时间戳。

Percolator有3个COLUMN和事务相关：

1. LOCK COLUMN: 事务提交时写本项，并记录 primary key的位置。事务成功提交后，该记录会被清理；
2. DATA COLUMN：存储实际用户数据；
3. WRITE COLUM：记录事务提交时的timestamp，关键在于WRITE COLUMN，只有该列正确写入后，事务的修改才会真正被其他事务可见。读请求会首先在该 COLUMN中寻找最新一次提交的 start timestamp,这決定了接下来从 DATA COLUMNI的哪个版本的key读取最新数据；

Client端执行2PC过程如下；

1. Prewrite：客户端首先从 Oracle获取全局唯一时间戳作为当前事务的start_ts，从所有key中选出一个作为primary。并将所有的 key/value数据写入请求并行地发往对应的存储节点。存储节点需要检测WW冲突：从 WRITE COLUMN列中获取当前key的最新数据，若其commit_ts大于等于start_ts，说明在该事务的更新过程中其他事务提交过对该key的修改，返回 Write Conflict错误；然后检查key是否已被锁，如果是，返回 Keylslock的错误；如果没有冲突，则向LOCK COLUMN写入锁信息；
2. Commit阶段：从Oracle获取时间戳作为事务的提交时间commit_ts；向primary key所在的存储节点发送 commit请求，并写入WRITE COLUMN；步骤2正确完成后该事务即可标记为成功，接下来异步并行地向 secondary keys所在的节点发送 commit请求；

锁清理的关键是识别出锁是否由一个失败事务残留下来的垃圾锁。

2.2 Lock-free Implementation of Snapshot Isolation

在lock-free的实现中需要一个组价来决策事务间是否存在Spatial overlap和Temporal overlap。

3. Serializability

3.1 Is Write-write Conflict Avoidance Sufficient for Serializability?

WW冲突检测不是串行化的充分条件，比如前面提到的A5B write skew：

H1. r1[x] r2[y] w1[y] w2[x] c1 c2

3.2 Is Write-write Conflict Avoidance Necessary for Serializability?

WW冲突检测不是串行化的必要条件，它需要阻止Lostupdate问题：

H3. r1[x] r2[x] w2[x] w1[x] c1 c2

WW冲突检测会误判：

H4. r1[x] w2[x] w1[x] c1 c2

H4中事务2并没有read(x)，直接write(x)，而且事务1和事务2都是并发的关系，因此WW会abort其中一个；

H4的执行顺序和H5是等价的（事务执行速率稍微慢一点）：

H5. r1[x] w1[x] c1 w2[x] c2

而H5是并没有产生Lostupdate问题。

事务1一旦提交就应该被事务2读取到，H5是合法的执行。

WW冲突检测对于直接写的事务会误判。

4. Read-Write vs. Write-Write

将事务分成读和写两个阶段：

1. read snapshot isolation：事务的读阶段不会被中断，写会被中断（检测到了WW冲突）；
2. write snapshot isolation：事务的写阶段不会被中断，读阶段会被中断（检测到了RW冲突）；

4.1 Write-Snapshot Isolation

RW冲突的条件：

1. RW-spatial overlap: 事务txnj 写r同时事务 txni读取r；
2. RW-temporal overlap: 事务txni和事务txnj是并发关系，Ts(txni) < Tc(txnj) < Tc(txni)；
   总结：事务j在事务i的生命周期内修改了事务i的读集合。

注意：RW-temporal overlap和前面的不同，下图中TXNn和TXNc''在RW-temporal overlap并不构成冲突，因为TXNc''对TXNn中读集合的修改，并没有在事务TXNn的生命周期中得到提交。而TXNn在TXNc''的生命周期提交了，但是他却没有修改TXNc''的读集合（为空）。

事务TXNc'写集合和TXNn冲突，并且是在TXN的生命周期得到了提交，因此存在RW冲突（如果串行执行事务TXNn本应该可能读取到最新的r，也可能不应该读取，但是为了防止万一，仍然需要abort，此处也是RW的误判原因）；

事务TXNc虽然和TXNn都修改了相同的写集合（满足ReadSnapshot的WW冲突），但是并没有修改读集合，因此不满足RW冲突，这两个事务可以得到串行化的效果（事务TXNc先提交了更改了r'，随后事务TXNn也修改了r'，这是允许的）；

可以看到RW允许只有写没有读的事务间的并发执行，而WW不允许。

Read-only transactions

只读事务是指写集合为空，只读事务不会被abort。

4.2 Is Read-write Conflict Avoidance Sufficient for Serializability?

为了证明Write-SI是串行化的，需要把每种场景的执行history都映射到串行化的执行history。

Write-SI阻止了RW冲突，而通过快照读取到的内容是不变的，因此可对事务进行如下变换：

1. 对于写事务，commit order不变；
2. 事务内部读写操作顺序不变；
3. 所有只读的操作可以等价的向左移动到事务开始的时间点（只要拿到了一个快照，无论何时读取，内容都是一样的）；
4. 所有写操作向右移动到commit时间点；

总结：所有事务在时间轴上可以变换成只有2个点：

1. 事务start时间点：对应所有读操作；
2. 事务commit时间点：对应所有写操作；

Read-Only事务

下图中：TXNr的read操作可等价的移动到事务开始时间点，那么TXNc本来是在TXNr的事务执行期间得到了提交修改了它的读集合，通过等价变化后，TXNr的执行时间变成了无穷小，因此也就不会被其他事务修改其读集合。因此，所有read-only事务都不会被abort掉。

Write-Only事务

下图中：

Lemma 1. History serial(h) is serial.

在时间轴上：

只读和只写事务变换成了一个点；

读写事务变换成了一个线段；

RW阻止了线段之间的交集；

因此，RW调度等价于串行执行；

RW能阻止LostUpdate问题，比如：

H3. r1[x] r2[x] w2[x] w1[x] c1 c2

事务1写入x，并先commit，修改了事务2执行期间的x，因此会被RW阻止。

4.3 Is Read-write Conflict Avoidance Necessary for Serializability?

Write-SI的一个优势是，允许在标准SI下被误判的调度顺序被执行，比如：

H4. r1[x] w2[x] w1[x] c1 c2 -- SI阻止此History

SI误判的原因是：事务1和事务2都修改了x，但是事务2并没有读取操作不存在RR的问题。

同理，Write-SI也会出现误判，比如：

H6. r1[x] r2[z] w2[x] w1[y] c2 c1 -- Write-SI阻止次History

H6的执行顺序存在RW冲突会被阻止，事务2修改了事务1的读集合；

而如果使用下面H7的调度顺序，先放行事务1，再放行事务2，事务1并没有修改事务2的读集合，因此不存在冲突；

出现误判的原因是：

事务2修改了事务1的读集合，而事务1没有修改事务2的读集合，此时依赖调度顺序。

H7. r1[x] w1[y] c1 r2[z] w2[x] c2

也就是：SI和Write-SI都会出出现误判，误判的概率依赖实际的workload。

5. Lock-free Implementation of Write-snapshot Isolation

lock-free的实现需要一个中心化的组件status oracle server来做RW检测，RW中的读集合是指真正被事务读取到的keys，而不用关心事务的搜索条件。

相比于SI，Write-SI的commit消息会比较大因为多出了Rr读集合。

5.1 Read-only Transactions

不管是SI还是Write-SI对只读事务的处理是一样的。

5.2 Analytical Traffic

对于分析型的查询，通常会读取大量的数据，那么读集合会很大，可以使用描述性表达式来描述读集合。另外，对于AP场景大查询通常是只读事务。

6. Evaluation

在压力不高时WW和RW性能相当；压力大时RW比WW慢一点，原因是在RW冲突检测时先load读集合，然后load写集合；而WW检测直接load写集合；

下图在测试zipfian测试时，RW性能稍弱，原因是该测试的读集合是从刚刚写入集合中选取，增大了RW冲突概率。

status oracle server中需要在内存中存最近提交事务，为了防止内存耗尽：只处理最近一段时间的事务Tmax。清理Tmax之前事务所占用的内存，所有在Tmax之前的长事务直接abort掉。

此外，status oracle server为了能做failover，需要把commit的信息写入自己的WAL日志中。同理，为了高可用可对WAL进行复制。

7. FoundationDB的实现

FoundationDB实现了一个分布式的Write-SI：

1. 使用KeyRange将RW检测分散到多个Resolver进程上；
2. Resolver进程是无状态的，状态从LS上获取；
3. 为了解决lastCommit内存问题，只允许5s的事务，因此Resolver可以清理超过5秒的数据了；