Serializable隔离级别

事务的一致性和隔离性是事务的两个重要的特性，从隔离级别的角度看，两者是息息相关的，更高的隔离级别代表更严格的一致性。

在ANSI SQL标准中，事务有4个隔离级别，Read Uncommitted，Read Committed，Repeatable Read，Serializable，其中Serializable是最高的隔离级别。可以说，在传统数据库中，只有Serializable的事务才能完全满足ACID的特性，因为低隔离级别的事务之间还是有可感知的互相影响，比如幻读，严格来说，这既破坏原子性又破坏隔离性。

现实中，即使是面向OLTP的数据库，大部分也没有实现Serializable隔离级别，或没有采用Serializable作为默认隔离级别，见下表

Database	Default Isolation	Maximum Isolation
IBM DB2 10 for z/OS	CS	S
IBM Informix 11.50	Depends	RR
MySQL 5.6	RR	S
MemSQL 1b	RC	RC
MS SQL Server 2012	RC	S
Oracle 11g	RC	SI
Postgres 9.2.2	RC	S
SAP HANA	RC	SI
Cockroach	S	S
tidb	SI	SI
cloud spanner	S	S
Legend	RC: read committed, RR: repeatable read, S: serializability,SI: snapshot isolation, CS: cursor stability, CR: consistent read

​ (摘自 When is "ACID" ACID? Rarely.，有增删)

在表中，比较重要的没有实现Serializable的数据库有Oracle 11g，身为商业数据库的霸主，没有提供Serializable隔离级别，不能不说是一种遗憾。

隔离级别是在一致性和并发性之间的一次权衡，对于互联网应用，Serializable往往是不必要的，相较之下，吞吐量更为重要，这是nosql，newsql，sharding中间件能够流行的一个重要原因。但对于金融领域的某些场景，Serializable的重要性就凸显出来了。

如何实现Serializable

悲观方案-加锁

最简单的方法，当然是加数据库锁，读加共享锁，写加排它锁。

但是在tp类型的数据库，这种方法显然不可行，这会导致数据库所有事务的读写和写写行为全部串行化。为了提高并发性，可以采用加表锁的方式，但是，这种方法也不能满足并发性的要求。对于数据库事务，行是修改的最小单位。因此采用行加锁的方式实现串行化，是并发性最高的方案。

乐观方案-SSI

在SIGMOD 2008，论文《Serializable Isolation for Snapshot Databases》提出了一个使用乐观机制实现Serializable的方法。
事务的有害依赖可以分为：

1. rw-dependency，代表事务T1读取了元素X，事务T2随后修改了元素X；
2. wr-dependency，代表事务T1修改了元素X，事务T2随后读了元素X；
3. ww-dependency，代表事务T1修改了元素X，事务T2随后再次修改了元素X；

由于MVCC机制的特殊性，对于snapshot隔离级别，当事务T1，T2并行执行时，是互相读不到对方修改后的结果的，因此任何事务读取了对方修改的数据，一定是前一个版本（或者前几个版本），即使读操作是发生在写之后，这会形成一个rw-dependency，而不是wr-dependency。

显然，对于任何一个非串行化的调度，那么一定有多个事务组成的读写关系形成了环。

这篇论文证明了，对于snapshot隔离级别，任何一个成环的调度必然包含连续的两个rw-dependency，这是一个充分不必要条件。以write skew为例：

write-skew.png

事务T1和T2分为读取了对方修改前的数据，形成了两个rw-dependency，如下图：

RW conflict.png

也就是说，只要破坏这两个rw-dependency，既可以实现串行化。同时，这个方案会带来一定误判，并不是所有包含两个rw-dependency的事务都构成了环。

常见数据库Serializable隔离级别的实现

MySQL(innodb)如何实现Serializable

MySQL是通过gap lock的方式实现了Serializable，简单来说，在snapshot读的基础上，对读操作加锁。

1. 如果查询包括索引，在索引上使用gap lock，锁下一个key；
2. 如果查询不包含索引，使用表锁；

考虑一下，对于上图中的write skew会发生什么？

事务T1读X的时候加锁，事务T2读Y的时候加锁，事务T1修改Y的时候被阻塞，事务T2修改X的时候被阻塞，形成死锁。死锁检测导致其中一个事务回滚，环被打破，实现Serializable。

见下面这个例子，id是主键。

mysql serilizable-write skew.png

为什么这种加锁的方式可以实现SSI？

读写操作都加锁之后，无论两个事务之间如何发生冲突，都不可能形成环，至于为什么锁下一个key，这是一种谓词锁的实现方式，代表对满足条件但是尚未插入的数据加锁（幻读）。

PostgreSQL如何实现Serializable

PostgreSQL在版本9.2之后根据论文《Serializable Isolation for Snapshot Databases》提出的算法实现了Serializable隔离级别，可以说是这篇论文的开源实现。

回想一下《Serializable Isolation for Snapshot Databases》论文中的内容，为了实现Serializable，我们需要追踪rw-dependency，这不仅需要记录每行的修改事务，同时也要记录每行的读取事务。

PostgreSQL是行级MVCC机制的，这点和MySQL相同。行级MVCC机制表示该行的每个版本都记录了是由哪个事务的修改的，由此可见，我们缺少的就是该行的读取事务的信息。

PostgreSQL通过predicate lock维护事务的读取信息，以记录物理时间上读后写产生的rw-dependency。和MySQL的gap lock不同，predicate lock并不会阻塞任何其他事务，仅仅用于生成rw-dependency，并在生成rw-dependency时和事务提交时判断是否以事务为中心构成了两个连续的rw-dependency，以此判断事务是否需要回滚。

PostgreSQL通过对整个index page加锁的方式实现了类似MySQL next key lock的效果，这同样是为了解决读操作发生后有满足条件的数据插入。

见下面这个例子，同样，id是主键（不过，pg是heap表，不是IOT表）

pg serializable-write skew.jpg

虽然是同样的语句，一样是write skew的例子，但是pg的事务行为和MySQL不同，只有在提交时，后提交的事务（右边）显式的回滚了，这是乐观机制和悲观机制的不同。

Cockroach如何实现Serializable

Cockroach是跨数据中心部署的分布式数据库，全局数据结构的维护代价要远远高于单机数据库，因此无法像MySQL和PostgreSQL一样维护全局锁表，也就无法使用MySQL和PostgreSQL的方式实现Serializable，同时，Cockroach是纯乐观机制，实现上并没有锁，也不可能为了实现Serializable推翻自己的根本设计基础。

那Cockroach是如何实现的Serializable隔离级别？Cockroach lab有一篇文章，介绍了他们是如何实现的Serializable隔离级别，见Serializable, Lockless, Distributed: Isolation in CockroachDB

想想PostgreSQL实现Serializable隔离级别时需要解决的几个问题：

1. 实现类似next key lock的机制（索引页面加锁），解决读后插入数据的问题；
2. 读加锁，解决读后修改的问题；

Cockroach为了实现Serializable，提供了两个关键的机制：

1. Cockroach允许snapshot隔离级别的事务在提交时使用一个更新的timestamp，这是符合snapshot隔离级别的语义的，但是不允许Serializable隔离级别的事务使用更新的timestamp，Serializable隔离级别的事务会用一个timestamp读取数据，同时也用这个timestamp提交数据，因此Serializable隔离级别的事务逻辑上等价在这个时间瞬时完成，虽然物理上并非如此。
2. Cockroach内所有的key都是按照range组织的，而非hash，这为serializab的实现提供了极大的便利，类似PostgreSQL的predicate lock，Cockroach维护了一个单独的timestamp cache，记录了读写指定范围内的key的timestamp。在写操作发生时，会检查这个范围的最大read timestamp。如果read timestamp > 事务的timestamp，那么这两个事务之中就有一个需要回滚。

结合这两点，我们可以发现，在Cockroach中，Serializable隔离级别的实现有两个关键点：

1. 通过固定timestamp，将所有Serializable隔离级别的事务按照Serializable隔离级别进行串行化排序；
2. 通过timestamp cache，进行读写冲突的判断，同时，cache以range的形式维护，也避免了幻读的问题；

同样的，我们分析一下为什么Cockroach的这种方法可以实现Serializable？

Cockroach中，每个Serializable隔离级别的事务他们的读写行为都在另一个发生冲突的Serializable隔离级别的事务之前或之后，按照timestamp的顺序严格排序，没有任何交叉的可能，因此一定是Serializable的；

同样，举一个Cockroach处理write skew的例子。

cockraoch-write skew.png

总结

Mysql使用gap lock的实现和PostgreSQL使用SSI的实现更像是悲观机制和乐观机制之间的比较。Cockroach则使用了最严格的方式，但他的并发性也是这三个数据库中最差的。看下面这个例子

-- run in serialzable isolation level
start transaction; --Tx1               |             start transaction; --Tx2
select * from t1 where id=0;           |
                                       |             select * from t1 where id=0;
update t1 set id2=id2+1 where id=1;    |
commit;                                |             
                                       |             commit;

明显，这两个事务可等价于Tx2->Tx1的串行调度。但是在不同的数据库中，他们的行为就各不相同。

1. 在MySQL中，事务Tx1需要等待事务Tx2提交后才能提交；
2. 在PostgreSQL中，两个事务可以无阻塞的并发执行下去；
3. 在Cockroach中，左边的事务会回滚；

当然，这并不能说明PostgreSQL的实现方式就优于MySQL，在上面write skew的例子中，PostgreSQL会继续执行注定失败的update，如果其后有一些其他的语句，那么无用操作的开销更多，而MySQL在update发生时就会立刻回滚，避免后续空耗资源。很明显，这还是乐观机制和悲观机制的差别。当冲突较多时，悲观机制更优，当冲突较少时，乐观机制更优。

而cockroach，采用了串行化事务的所有操作的方式，有最差的并发性，但也避免了实现全局锁的巨大工程开销。

参考文档

1. A Critique of ANSI SQL Isolation Levels
2. 《Highly Available Transactions: Virtues and Limitations》
3. When is "ACID" ACID? Rarely.
4. 《Serializable Isolation for Snapshot Databases》
5. PostgreSQL SSI README
6. PostgreSQL-wiki Serializable
7. 《Serializable Snapshot Isolation in PostgreSQL》
8. MySQL Phantom Rows
9. Cockroach design doc
10. How CockroachDB Does Distributed, Atomic Transactions
11. Serializable, Lockless, Distributed: Isolation in CockroachDB