《Disigning Data-Intensive Applications》 Part II(4)

前面一篇开始讲事务了,解读了ACID的含义了,讲了实际的系统中对于隔离级别的折衷的实现,提到了Snapshot isolation,这一章我们做一些更加深入的介绍。

Weak Isolation Levels

Preventing Lost Updates

到目前为止,对于写写并发,我们只讨论了dirty write这一种。

对于上图这种情况,并不是dirty write,即使在write的时候加锁,在commit的时候释放,也会导致写丢失的问题。如果事务中有read-modify-write的动作,就有可能出现写丢失。这在很多场景下都会发生:

  • 计数的操作或者更新帐户的值
  • 对一个复杂的value做一些本地的修改,比如在一个JSON的list中加入元素
  • 两个用户同时编辑同一个wiki页面

下面介绍一下处理这个问题的方法。在这之前,有一个问题,这样的Lost Updates,处于怎样的一种隔离级别?这个问题后面会提供到,有的文章里面说如果要达到snapshot isolation,就必须要避免掉lost updates。

Atomic write operations

提供原子写操作是最常见的方式。原子操作的通常做法是在读某个对象时就申请独占锁,这样就没有其它事务可以读取这个值,直到当前的事务提交,这种方法又被称为Cursor Stability;另外一种做法是把所有的原子操作都放到一个线程里面去执行。

很多ORM框架里面会执行一些不安全的read-modify-write操作,而不是使用数据库里面的原子操作,这会带来一些隐藏的bug。

Explicit locking

如果数据库本身没有提供原子性的写,那么就需要应用程序显式地锁住需要更新的对象了。

Automatically detecting lost updates

这个技术看起来就更加高端一点了,自动识别更新丢失,这就相当于在RocksdbTransactionDB里面看到的SetSnapshot,这算是一种自动识别更新丢失的一种方法了。

这种方式的一个好处是通过和Snapshot isolation结合,可以高效地完成检查。PostgreSQL的repeatable read,Oracle的serializable,SQL Server的snapshot isolation可以自动探测出lost update,然后会让对应的事务abort。

作者看起来是个MySQL黑,这里自然要黑MySQL一把,说InnoDB的repeatable read并不能提供这个机制。有些文章里面提到snapshot isolation必须要保证不会出现lost updates,所以MySQL提供不了snapshot isolation。

Compare-and-set

对于不提供事务的数据库,可能会找到CAS的操作来保证一致性。

Conflict resolution and replication

到了replicated databases的领域,防止lost updates就会涉及到更多因素。在multi-leader和leaderless的复制模式下,锁和CAS是无法使用的,因为它们假设数据只有一个up-to-date的副本。

允许数据拥有多版本是解决问题的一个通用的办法,应用自己来合并这些版本解决冲突。原子操作在这种场景下也是可行的,特别是这些操作满足交换率的情况。作者继续声称LWW会导致数据丢失。

Write Skew and Phantoms

前面我们看了dirty write和lost update,但这并没有覆盖写写并发的所有场景。

上面这个例子讲的是一个医院的排班系统,对于某一个排班而言,必须要保证至少有一个医生。那医生那请假的时候,系统会首先检查当前排班的人数是否大于等于2,如果不满足条件,就不会让值班的医生请假。

这个例子中Alice和Bob是在同一个排班中的两个医生,他们同时感觉不舒服,并同时把自己的排班撤销掉,那么就可能发生上图这样的情况,导致最终这个排班里面没有医生。

Characterizing write skew

我们称上述这种异常是“write skew”, 这个异常并不是diry writes也不是lost updates,因为并不是针对同一对象的更新。上面这个情况事务如果是串行化地执行,就不会有这个异常。

前面看到了针对lost update,有很多方法能够处理,相对之外,处理write skew的办法就比较少:

  • 单对象的原子操作在这里用不上,因为write skew涉及到多个对象
  • lost updates的自动探测在这里也用不上
  • 有些数据库支持设置一些约束条件,但是write skew需要对多个对象进行约束条件的设置,这对于很多数据库是不支持的,但是如果对视图设置触发器,是可能可以做到的
  • 如果不支持serializable isolation,那么显式地锁住也是可以的,比如调用select … for update。

More examples of write skew

乍一看write skew是个很晦涩难懂的问题,但是,会发现在很多场景下都会发生write skew。

Meeting room booking system

在预定会议室的时候,像下面的sql一样,我们先查出在对应时段有没有预定,如果没有预定就插入记录。但是如果数据库使用了snapshot isolation,我们可能会出现并发的问题。所以这里需要显式地把(room_id,time_rang)锁住。

1
2
3
4
5
6
7
8
9
10
11
12
BEGIN TRANSACTION;
-- Check for any existing bookings that overlap with the period of noon-1pm
SELECT COUNT(*) FROM bookings
WHERE room_id = 123 AND
end_time > '2015-01-01 12:00' AND start_time < '2015-01-01 13:00';
-- If the previous query returned zero:
INSERT INTO bookings
(room_id, start_time, end_time, user_id)
VALUES (123, '2015-01-01 12:00', '2015-01-01 13:00', 666);
COMMIT;

Claiming a username

声明一个唯一的用户名,在snapshot isolation隔离级别下,依然可能有问题,需要我们使用显式的锁,在查询到用户名不存在的同时锁住这个用户名,这样才能避免并发的问题。想起来如果图支持用户提供vertex id的时候,也是需要先锁住的,要不然会出现两次addVertex同样的id成功。

Phantoms causing write skew

所有上面列举的这边现象有相同的pattern:

  1. 首先是使用一个SELECT查询,查询出一些满足某些条件的行
  2. 基于上面查询出来的值,来判断需要做哪一步
  3. 如果需要继续,就会执行一个写操作,提交到数据库

当然,也有可能是先写,然后再查询 ,然后决定要不要提交或者回滚这个操作。

在一个事务中的写,会影响另外一个事务search查询的结果,这个现象我们称之为phantom。Snapshot isolation避免了只读事务的phantom,但是在我们上面列表的读写事务中,phantom会导致write skew的问题。

Materializing conflicts

如果phantom的问题是没有对象让我们锁,那我们是不是可以人为地创建一些锁对象。比如前面预定会议室的例子,我们可以创建一个表,存放room_id和time_slot,专门用来做锁。

这种方法称之为“Materializing conflicts”,因为它把phantom转化为对数据库中具体的一组行的锁。但是,这是非常不优雅的处理方式,为了实现事务的隔离,还需要改变应用的数据模型,还是很挫的。

Serializability

隔离级别不好理解,而且在每个数据库里面的实现是不一样的;从自己的代码,很难判断出在某个特定的隔离级别上运行是否安全;没有好的工具能够检测出race condition。
这个问题在1970s弱隔离级别被引入时就存在了,研究者一直给的答案就是:使用serializable isolation!

Serializable isolation通常被认为是最强的隔离级别。它保证了即使事务并行地执行,它们运行的结果和序列化的运行是一样的,数据库会避免一切的race condition。

如果Serializable isolation这么好,为什么我们不就使用Serializable isolation呢?为了回答这个问题,我们得先看一下Serializable isolation是如何实现的,它们的表现如何?当前很多数据库实现Serializable isolation使用的以下3个方法:

  • 真的就是序列化地执行事务
  • 使用两段锁,在很长一段时间里,这是唯一的选择
  • 使用优化的并发控制技术,比如SSI

Actual Serial Execution

避免并发问题最简单的方法就是完全地移除并发:使用单线程串化地执行事务,这个就是voltdb里面的做法。虽然这是个显而易见的办法,但是直到2007年数据库设计者才认为这个方法是可行的。在过去的30年里,多线程并发都被认为是获取高性能至关重要的办法,那是什么因素的改变导致认为单线程执行是可行的呢?

  • RAM变得越来越便宜,我们可以把所有的数据都放到内存里面了
  • OLTP的事务通常来说比较小,而且只会修改少量的数据

VoltDB/H-Store、Redis、Datomic中都是使用的单线程的模型。

Encapsulating transactions in stored procedures

对于单线程执行事务的模型,如果在事务的执行中还有客户端和服务端的交互,那是无法忍受的。所以在这种模型下,需要把事务的逻辑封装成存储过程。

Pros and cons of stored procedures

存储过程在1999年就存在于SQL标准中,但是口碑却并不太好:

  • 每个数据库都有自己支持存储过程的语言。这些语言没有很好的维护而且缺乏完善的生态。
  • 运行在数据库中的代码难以调试,不太好进行统计,总之,就是产品化的毒瘤
  • 一个写得差的存储过程可以把数据库实例打爆(其实一个写得挫的SQL也是可以的)

虽然有这些劣势,但是都是可以被克服的。现在的数据库中都是使用通用的语言来编写存储过程,比如VoltDB使用Java或者Groovy,Datomic使用Java或者Clojure,Redis使用Lua。

VoltDB还使用存储过程来实现他们的复制:复制并不是把事务的数据拷贝到别的节点,而是在每个副本上都运行同样的存储过程。所以VoltDB要求存储过程必须是deterministic的,在不同的节点上运行的结果都是一样的。

Partitioning

为了利用多核的性能,作者建议每个核维护一个分区,这样就可以提高并发度。但是会涉及到跨分区的事务,这时候性能就会急剧地下降了。

Summary of serial execution

序列化地执行事务需要满足下面一些约束条件:

  • 所有的事务必须是短小精悍的,因为一个慢事务会拖垮其它所有的事务
  • 这种方法只能做于数据都存在于内存的场景
  • 一个CPU核就只可以处理写流量
  • 跨分区的事务是可行的,只是成本太高

Two-Phase Locking (2PL)

大概在30年的时间内,实现Serializability只有2PL这一种方法。作者的描述是:

  • 如果事务A已经读取到了一个对象,事务B想写这个对象,那个事务B必须要等到事务A提交或者abort之后才能够继续
  • 如果事务A写了一个对象,事务B想读这个对象,那么也是需要等到事务A提交或者abort之后才能够继续

2PL对于锁是很严格的,上面的描述看起来像是一个读写锁。因为2PL非常严格,所以它能避免所有的race condition,包括lost updates和wite skew,单从上面的描述是看不出来如何避免的。

Implementation of two-phase locking

作者说,2PL在MySQL和SQL Server的serializable isolation level中被使用,DB2的repeatable read isolation level也使用了。问号脸,MySQL有serializable isolation level?

刚才说了2PL看起来使用了读写锁,也就是shared mode和exclusive mode。

  • 如果事务希望读一个对象,那么必须申请一个shared mode锁,其它事务也可以同时持有这个shared mode锁,但是如果申请shared mode锁时发现exclusive mode锁已经存在了,事务就必须等待
  • 如果事务希望写一个对象,必须申请一个exclusive mode锁。这样就会把其它需要访问这个对象的事务都阻塞住
  • 如果事务先是读一个对象,然后再写,那么需要把锁升级,升级锁的过程和申请exclusive mode锁的过程是一样的
  • 事务获取到锁之后,必须持有锁直到事务结束。所以two-phase的意思,第一步指的是获取锁,第二步指的是在事务结束时释放所有的锁。这有点牵强,这看起来所有的锁都是2PL啊。

因为使用了锁,所以可能会产生死锁,数据库能够自动地检测出死锁,并让导致死锁的事务退出交给应用层来重试。

Performance of two-phase locking

2PL从1970s后并没有被每个人使用的原因就是性能:事务的吞吐和响应时间比weak
isolation要差很多。

传统的关系型数据库并不会限制事务的持续时间,因为一个等待用户输入的交互式应用程序会使用。所以,如果一个事务需要等待其它事务时,并不确定到底需要等多久。

虽然说,即使在基于lock的read committed isolation level也会有死锁的出现,但是在2PL的情况下,死锁会更加严重。

Predicate lock

为了描述这个问题,我们再回顾之前预订会议室的例子:

  • 如果事务A想要读取满足某些查询条件的对象,必须对查询条件申请shared-mode predicate lock。如果事务B这个时候已经对满足条件的对象中某一个持有exclusive lock了,那么事务A必须等到事务B退出
  • 如果事务A想要更新某个对象,事务A必须检查对象的旧值和新值是否已经被已经存在的predicate lock申请了,如果事务B已经申请了,那么A需要等到B退出 。

核心的观点是predicate lock不仅应用于已经存在的对象,而且会应用于不存在的对象。对于预订会议室的例子具体执行是这样的:

1
2
3
4
SELECT * FROM bookings
WHERE room_id = 123 AND
end_time > '2018-01-01 12:00' AND
start_time < '2018-01-01 13:00';

在预订会议室的例子中,事务A和事务B都会先执行这一句,申请到shared-mode predicate lock,然后它们的插入操作都会被阻塞住,然后死锁检测,然后某一个事务abort。

Index-range locks

遗憾的是,predicate lock的性能并不是特别好:当有很多active的事务时,检查是否的已经存在的predicate lock会变得很耗时。所以,很多使用2PL的数据库实际上使用的是index-range locking,也会被叫做是nextkey locking,这是predicate lock的一个简化实现。

index-range locking简化的方式是锁一个更大范围的对象。还是上面预订会议室的例子,如何想预定[noon, 1p.m]的room 123,那么可以扩大为锁住所有时间的room 123,或者锁住[noon, 1p.m]这个时间段内所有的房间。

在预定会议室的例子里,我们对于room_id和(start_time,end_time)可能都会有索引:

  • 如果在room_id上有索引,那么我们可以对这个索引上room_id对应的对象进行加锁,这样就表示已经有事务对room 123进行对查询了
  • 同样的,如果有基于(start_time,end_time)的索引,还可以对[noon, 1p.m]这个时间段对应的对象进行加锁

使用Index-range locks可以避免phantoms和write skew,但是并没有像predicate lock那样精确,比如说要预订[2 p.m, 3 p.m]的room 123,就可能被误伤。但是,由于开销比较小,所以会是很好的折衷。

如果没有合适的index来上锁,那么就可能对整个table进行加锁,虽然这对性能不友好,但是对于isolation而言,还是很安全的。

Serializable Snapshot Isolation (SSI)

这一章描述了令人沮丧的数据库的现状:一方面,我们可以实现serializability,但是要么就性能太差,要么就不能够扩展国;另一方面,weak isolation levels又会有各种各样并发的问题。那么,鱼和熊掌在这个场景里面能否兼得呢?

也许是可以的,serializable snapshot isolation看起来就很有前途。SSI还是比较新的,在2008年被提出的,基于澳大利亚的一个学生Michael Cahill的论文。

到今天为止,SSI既被应用于单机数据库(PostgreSQL 9.1中开始支持),也应用到了分布式数据库(FoundationDB使用了类似的算法)。和其它的并发控制机制相比,SSI还是很年轻的,但是在实际应用当中提供了很好的性能,在将来这可能是隔离级别新的默认选项。

Pessimistic versus optimistic concurrency control

2PL是悲观锁,它基于的思路是,只要有可能发生race condition,就锁住,等安全了再回来继续操作。它比较像在多线程编程中用来保护数据结构的mutual exclusion(mutex)。Serial execution是最极致的悲观锁,不管并发的事务有没有相关性,都序列化地执行。

和上面这些不同的是,serializable snapshot isolation是乐观的并发控制技术。在这个语义下,乐观的意思是在事务的执行过程中,假装一切都是ok的,在提交的时候来检测是否是冲突了(那么问题来了,所以的冲突都能够在提交的时候被检测到么?这跟之前讲自动检测lost updates有什么不同呢?)。如果检测到冲突了,就会让对应的事务abort,然后进行重试。

乐观的并发控制这个想法不是很新,它的优缺点已经争论了很久了。如果系统的争用非常多时候,性能会很差,因为很多事务都会abort。但是如果情况不是这样,乐观并发控制就会比悲观的并发控制表现得好。争用可以使用commutative的原子操作来减少。

从名称上就可以看出,SSI是基于snapshot isolation之上来做的,增加了序列化冲突的检测来决定应该让哪些事务退出。

Decisions based on an outdated premise

之前在讲snapshot isolation的里面,我们讨论了write skew这种异常,然后观察到了一种重复出现的模式:事务从数据库中读取了一些数据,检测这些查询的结果,然后基于这些结果做一些写入。但是,在snapshot isolation下,从原来的查询 中原来的结果,到了事务提交的时候,可能就out-to-date了,因为可能被别的事务已经修改过了。

数据库是如何探测出查询的结果有变化了呢?这里有两个case需要考虑:

  • 探测出读到了一个stale的MVCC对象的版本
  • 探测出写操作影响了之前的读

Detecting stale MVCC reads

为了避免这种问题,数据需要跟踪一个事务A是否因为MVCC的可见性问题忽略了另外的事务B的写入。当事务A想要提交的时候,数据库需要检查之前被忽略的写入有没有被事务B提交,如果提交了,就需要将事务A回滚。

那么,为什么要等到提交的时候呢?为什么不在检测到transaction 43有脏读的时候马上就让它abort呢?hmm,因为transaction 43可能是一个只读事务。因为transaction 43在读取数据的时候,数据库并不知道这个事务会不会更进写入,另外,如果在transaction 43提交的时候,transaction 42还没有提交,那这就不是一个脏读了。

Detecting writes that affect prior reads

前面在讲2PL的时候,我们讨论了index-range locks,索引范围锁可以让数据库锁住满足某些搜索查询匹配的所有行。我们在SSI里面可以使用一个类似的技术。

在上图当中,transaction 42和transaction 43都做了相同的查询。如果对于shift_id有索引 ,那么数据库就可以使用索引中1234这个条目来记录transaction 42和43读取过这条数据。这个信息只需要保留到事务结束。

当事务写入数据库时,需要在索引中查询有哪些其它的事务最近读取过被影响的数据。这个过程有点像申请写锁的过程,但是它不会阻塞住直到读取了这个数据的事务结束,而是会通知这个事务它读到的数据不再是最新的了。

就像在上图中transaction 43会通知transaction 42它之前读到的数据是脏的,同样的中transaction 42也会通知transaction 43之前写的数据是脏的。这里,transaction 42会先提交,需要它之前读到的数据是脏的,但是造成这个影响的transaction 43还没有提交,所以,transaction 42可以提交成功。transaction 43就没有这么成功了,它会abort掉。

Performance of serializable snapshot isolation

如果数据库能够非常详细地记录每个事务的行为,那么数据库就可以详细地知道哪些事务需要abort,但是这个记帐的开销也是很大的。粗略一点的tracking会快一点,但是会导致一些事务不必要地abort。

在某些case下,事务读取到被别的事务修改之后的数据也是ok的,有时候并不一定需要serializable。PostgrelSQL就借助于这个理论降低了unnecessary aborts。

相对于2PL而言,SSI的一个好处是事务并不需要阻塞地去等其它事务持有的锁,这个设计准则就会让查询延时可预测。

相对于serial execution,SSI不会受限于单个CPU的吞吐。FoundationDB把serialization的检测分布到多台机器上去执行了,这样就可以达到非常可观的吞吐了。虽然数据会分片到不同的机器,事务可以从多个分片上读取数据,并且还能够保证serializable isolation。

事务abort的频率严重影响了SSI的整体性能。比如,一个运行时间非常长的读写事务很有可能会和别事务产生冲突并abort。所以SSI要求读写事务比较短。

Summary

在这一章节中,我们讨论了事务,并浓墨重彩地描述了并发控制中的异常:

  • Dirty reads
  • Dirty writes
  • Read skew (nonrepeatable reads)
  • Lost updates
  • Write skew
  • Phantom reads

在Weak isolation levels中,我们能避免某些异常,但是需要开发者显式地调用lock来避免其它异常。何以解忧,唯有serializable isolation。我们介绍了3种实现serializable isolation的手段:

  • Literally executing transactions in a serial order
  • Two-phase locking
  • Serializable snapshot isolation (SSI)

在这一章中我们的例子都是基于关系型数据库的,但是事务这个抽象对于任何数据模型都是有用的。我们讨论的所有东西还是基于单机数据库的,分布式领域的事务会有新的挑战,在后面的章节中会讨论到。

最后

这一章节对理解事务隔离级别需要面临的问题还是非常有帮助的,但是对于隔离级别实现的细节,比如说SSI具体是怎么做冲突检测的,还需结合具体产品的实现才能够得到更深入的理解。