分布式系统中的事务之最强隔离级别

前两篇文章《棘手的事务概念们》🔗、《事务隔离级别》🔗 列举了很多由于隔离级别不够造成的异常，比如脏写、脏读、不可重复读、更新丢失、写偏序和幻读等等。读已提交能够避免脏写和脏读，快照隔离在此基础上，可以避免不可重复读。但更新丢失、写偏序和幻读等问题，在上述隔离级别，仍然难以解决。

而且，弱隔离级别有一些固有的问题：

1. 从数据库侧，弱隔离级别的真正含义难以理解，且不同数据库产品实现的也千差万别。

2. 从应用侧，很难判断当前代码在特定隔离级别上，是否会有竞态条件和并发问题。如果应用代码很复杂，更难看出问题。

3. 从工具侧，没有比较好用的工具来帮助检测我们的代码在特定隔离级别的竞态条件。对有竞态条件的代码测试是非常难以编写，尤其对于很小概率出现的错误来说，更是难以复现。

解决这些问题，最容易想起的就是——使用最强隔离级别，可串行化。在此种隔离级别下，所有事务的行为像顺序执行，则从根本上避免了各种竞态条件。

但可串行化有很多弱点，要了解这一点，需要逐一考察可串行化当前主要实现方法：

1. 物理上真正的对所有事务进行串行的执行。

2. 两阶段锁（2PL，two-phase locking），曾经几十年中唯一的可用选项。

3. 乐观并发控制（OCC，Optimistic concurrency control），如可串行化的快照隔离。

本文主要针对单机数据库探讨上述实现，到后面的文章，我们将会将这些理论扩展到多机。

虽然实现可串行化最直观的做法就是将所有事务串行的执行。但在过去几十年，单线程事务的性能基本是不可用的。直到 2007 年左右，一些软硬件的的发展，才促成了单线程事务的真正落地：

1. RAM 足够大且便宜，从而促使某些场景的数据可以都放内存中，即，使用内存数据库。由于不需要每次事务都执行 IO（定期 backup 可能还是需要），单线程事务只需访问内存，因此性能还可以接受。

2. AP、TP 场景的界定和区分，数据库设计人员发现，在 TP 场景下，读写事务通常持续时间较短、用到的数据规模较小；对比来说，AP 场景通常只包含读取操作。因此可以让长时间、大范围的 AP 场景运行在独立于主事务循环外的只读事务上，然后只读事务使用一个一致性的快照即可不影响主循环。

VoltDB/H-Store、Redis 和 Datomic 实现了物理上的串行执行事务。由于避免了多线程间用锁同步的开销，单线程的事务某些场景下可能性能更好，但在吞吐上可能受制于单核 CPU 的上限。此外，为了充分利用单核，相比传统形式，会对事务结构重新组织（如存储过程）。

在数据库发展早期阶段，人们试图将数据库事务设计成为包含整个用户交互流程。如果整个交互流程都从属于一个事务，那么它们就可以被原子的提交，这么抽象看起来很干净。

但人的交互所引入延迟远大于计算机 CPU 时钟周期甚至 IO 延迟，因此 OLTP 型数据库多会避免在单个事务中包含人的交互，以求单个事务能够较快的执行结束。在 Web 上，这意味着，不能让单个事务跨多个请求。但如果只允许单次请求执行一个语句，一个完整流程通常会包含多个语句，从而包含多次 RPC\HTTP 请求，会在通信上耗费太多时间。

因此，单线程串行事务系统不允许交互式的多语句事务。用户需要将多语句封装为存储过程一次性提交给数据库。如果数据都在内存中，则存储过程可以被快速的执行。

TODO：存储过程需要 if、while 都判断分支，来依赖之前结果进行决策，否则就只能实时交互。

存储过程从 1999 年就进了 SQL 标准（SQL/PSM），但由于种种原因，一直为人所诟病：

1. 每个数据库厂商都有自己的存储过程语言支持（Oracle 有 PL/SQL，SQL Server 有 T-SQL，PostgreSQL 有 PL/pgSQL 等），且语法陈旧，迭代缓慢。

2. 相比本地应用代码，存储过程运行在数据库服务器中，难以进行调试、测试和监控。

3. 数据库通常对性能表现更敏感，一个写的不好的存储过程可能会拖累整个数据库的执行。

现代的存储过程放弃了 PL/SQL，转而使用通用编程语言：VoltDB 使用 Java 或 Groovy，Datomic 使用 Java 或 Clojure，而 Redis 使用 Lua。从而在某种程度上部分克服上述缺点。

对于内存数据库的单线程事务，使用存储过程可以获得不错的吞吐：

1. 内存数据库和存储过程避免了 IO

2. 单线程避免了锁开销

值得一提的是，VoltDB 还使用存储过程进行跨节点的数据同步：不是将改动复制到多个节点上，而是在每个节点执行同样的存储过程。当然，这要求存储过程具有确定性：在不同节点的不同时间执行，需要产生相同的结果。如，在存储过程中，获取当前时间戳，就要用特殊 API。

单线程事务受限于单个 CPU 吞吐，为了提高写入吞吐，处理较大数据量，可以将数据进行分区。VoltDB 支持对数据以某种方式（猜测是用户指定一个分区函数）对数据进行分区。

需要注意的是，分区方式要谨慎选择，以使绝大部分事务都局限于单个分区上。对于跨分区事务，由于需要进行额外协调（如上分布式锁），以串行执行。这会带来严重的性能损失，要尽量避免。

如，VoltDB 据称支持每秒 1000 的跨分区写入，比单机事务低几个数量级，且不能通过增加机器来平滑扩展。

能否对数据进行分区，取决于数据建模方式。如键值数据可以方便的进行分区，但具有多个次级索引的数据就很难，因为数据只能按照一种顺序来存储，而多个索引总会带来跨分区访问。

在某些特定约束场景下，对事务进行真正物理上的串行执行，已经成为一种可串行化隔离级别的实现方案。这些约束包括：

1. 所有事务都必须小（摸数据少）而快（延迟低）。因为只要有一个慢，就会拖累所有其他事务。

2. 活跃数据能够全部装入内存，沉寂数据可以放在磁盘。总之，需要最少化 IO，以保证所有事务能够快速的执行。

3. 单核 CPU 能够处理所有写入吞吐，或者，能够将事务局限在单个分区，不需要跨分区协调。

4. 只允许有限的跨分区事务。

在历史上的大约三十年时间里，只有一种广泛使用的可串行化实现：两阶段锁（2PL，two phase locking）。需要明确的是，本文所称 2PL 其实是严格两阶段锁（SS2PL, strong strict two-phase locking）。

这里，就我的理解稍微澄清下概念。两阶段锁，其实就是将使用锁的过程分为两个阶段，通常称为扩张阶段和收缩阶段。在扩张阶段（事务的整个执行过程），只会申请锁，在收缩阶段（事务提交时），只会释放锁。从另一个角度理解，每个事务都是访问数据库的一个数据对象子集，扩张阶段就是逐渐拿到该子集所有相关对象的所有权，收缩阶段就是将持有对象所有权释放。而 S2PL（Strict 2PL），是在 2PL 的基础上，将写锁保持到事务结束；SS2PL（Strong 2PL 或 Strong Strict 2PL）是将读写锁都保持到事务结束。这里仅简单做下概念上区分，具体背后理论，还是挺庞杂，感兴趣可以自行找相关书和论文读读。

TDOO：2PL 并非拿到所有的锁，才开始进行读写操作？而是按需拿锁，提交时集中放锁。

为了和书中保持一致，下面仍然称 2PL。

2PL 和 2PC 听起来很像，但它们不是一个东西，只是恰好都有两个阶段而已。

在防止脏写一节，提到了锁。但 2PL 中的锁会严格一些：

1. 如果所有事务都没有写入，允许多事务并发读取一个对象。

2. 只要任何一个事务有写入，就会将其独占到事务结束，不允许其他任何事务读或写。

2PL 不允许读写并发、写写并发，而快照隔离却正好相反，即读写互相不阻塞。另一方面，2PL 通过阻止读写并发，可以避免更新丢失和写偏序等并发问题。

2PL 用于 MySQL（InnoDB）和 SQL Server 中实现可串行化隔离级别，以及 DB2 中实现可重复读隔离级别。

通过对每个对象进行加锁，可以实现单个对象的读写互斥。锁可以处于共享模式（shared mode）或者互斥模式（exclusive mode），具体来说：

1. 如果某个事务想读取一个对象，需要首先获取该对象的共享锁。多个事务可以同时获取同一个对象的共享锁。但若某个事务持有该对象的互斥锁，则所有需要读写该对象的事务都得等待。

2. 如果某个事务想写入一个对象，需要首先获取该对象的互斥锁。任何其他事务都不能同时持有该对象的任何种类的锁。因此，如果该对象上已经有锁，该事务必须先等待其释放。

3. 如果某个事务要先读取，再写入某个对象，可以先获取其共享锁，然后将其升级为互斥锁。升级互斥锁和获取互斥锁的条件相同。

4. 当某个事务获取锁之后，必须持有到事务结束（中止或者提交）。这也是上面两阶段定义的由来。

由于每个对象都要上锁，而一个事务通常会访问多个对象，因此很可能造成死锁：多个事务持有锁，并且互相等待对方的锁。

两阶段锁的最大问题在于其性能，这也是其没有被所有人都接受原因。两阶段锁的实现下，事务的吞吐要比其他弱隔离级别低的多。维护大量锁的开销是一个原因，更重要的原因是并发性的降低。

延迟不稳定。按照 2PL 的实现定义，任何有竞态条件的事务都要通过锁进行物理上串行化的执行，类似于 DAG 的拓扑排序。因此，基于 2PL 的实现，其响应延迟会相当不稳定。由于没有对等待时长进行限制，虽然你的事务很短，但系统中任何长事务都可能对你的执行造成影响。

死锁更加频繁。尽管基于锁实现的读已提交隔离级别会发生死锁，但其发生频次远不如基于 2PL 实现的可串行化隔离级别。这也会造成额外的性能问题：死锁被检测到，会引发重试；如果死锁频繁，则会浪费巨大的性能。

前面所提到的锁，其实遗漏了一个很关键的细节——锁的粒度。

在之前小节，我们讲到，幻读是一个事务改变另一个更事务的查询结果，而一个具有可串行化隔离级别的数据库，需要避免幻读。在会议室预定例子中，这意味着，在一个事务查询某个时间段可用会议室时，另外的事务不能更新该时间段的同会议室的使用情况。

如何实现这一点？从概念上讲，我们需要一个谓词锁（predicate lock）。它通常是共享模式，但粒度更大——不再限于单个对象，而需要囊括所有符合条件的查询结果。

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

如何使用谓词锁？和共享锁类似，只不过粒度更大一些。

1. 当某个事务需要读取匹配条件的所有对象时，需要获得该查询条件的共享谓词锁。如果有任何其他事务持有该范围内对象的互斥锁，则该事务需要等待其结束。

2. 当某个事务想要写入（插入、更新或者删除）某个对象时，上互斥锁前，需要检查是否有其他事务持有包含该对象的谓词锁。如果有，则该事务需要等待其结束。

谓词锁的一个关键点是，可以锁住一个对象集合，该对象集中的对象甚至不必已存在，但将来可能会被添加。通过谓词锁，2PL 可以解决幻读问题。

如果活跃事务比较多，谓词锁的性能会非常差，因为锁冲突的检查会（TODO：谓词锁代表的集合可能是离散的、非连续的几个集合的并集，只能线性检查？）非常耗时。因此，大多数 2PL 的数据库使用了谓词锁的一个近似——索引范围锁（index-range locking，也称为 next-key locking）。

通过适当放大锁住的对象集来简化谓词锁。如当有多个条件进行与的时候，只锁一个条件。仍以会议室预定为例，假设你想预定一个中午十二点到下午一点的 123 会议室。相对于该条件上的谓词锁，锁定 123 会议室或者锁定十二点到一点的所有会议室，也是安全的，因为后者的对象集包括前者。

只锁定单个条件的好处在于，你可能在该条件上有索引。则可以将谓词锁，转化为一个在该索引上的范围锁、甚至单个索引对象锁。相比谓词锁，可以更快的判断冲突：

1. 假设索引在会议室编号 room_id 上，并且使用此索引查询 123 会议室的所有预定，则可将共享锁加在该索引项上。

2. 假设索引在时间段上，则可以将十二点到一点的所有索引条目上加共享锁。

无论那种方式，都使用单个条件将共享锁加在了相应的索引上；如果另一个事务想要修改相关房间或者相应时间段的会议室预定，则其必定需要同步更新索引。此时，索引上锁的存在会保证这些事务串行的执行。

这种方式也可以避免幻读和写偏序。相比谓词锁，索引范围锁虽然锁住的范围大，但实现开销较低。但谓词相关的索引并不总是能找到，此时可以简单的退化成整张表上的共享锁。这样做虽然有损性能，但是实现简单且安全。

前面小节详细聊了下数据库中隔离级别的图景：

1. 在光谱一侧，我们有很好的隔离级别——可串行化，但其实现要么性能差（两阶段锁），要么不可扩展（物理上串行执行）。

2. 在光谱另一个侧，我们有一些相对较弱的隔离级别，它们性能较好，但会有各种竞态条件（更新丢失、写偏序、幻读等等）。

难道说强隔离级别和高性能两者不可得兼吗？

2008 年，Michael Cahill 在其博士论文中提出了一种新型的可串行化实现方案：可串行的快照隔离（SSI，serializable snapshot isolation）。今天，无论单机数据库（PostgreSQL 9.1+ 的可串行化隔离级别）和分布式数据库（FoundationDB 使用了类似算法）都有 SSI 的身影。相比其他实现方式，SSI 还相对不太成熟，但其表现出的性能优势，使其隐隐然有成为可串行化默认实现的趋势。

2PL 是一种悲观（pessimistic）的并发控制机制，就像多线程编程中的互斥锁（mutual exclusion）。其背后哲学是，当可能有不好的事情（如并发）发生时，先悲观的等待到条件好转（其他事务释放锁），再进行执行。而物理上的串行执行，是将这种悲观哲学提升到了极致，等价于每个事务在执行时都持有了整个数据库级别的互斥锁。为了弥补这种悲观带来的性能损失，需要保证每个事务执行足够快。

SSI 是一种乐观（optimistic）的并发控制机制，类比多线程编程中的乐观锁。其相应哲学是，当存在潜在危险时，仍然不做任何检查去大胆的执行。当事务提交时，再进行冲突检测，如果存在冲突，则回退重试。将乐观发展到极致，则是不上任何锁，但为了给这种乐观进行兜底，需要在执行完后进行检查。

乐观并发控制并不是一种新思想，其优缺点被充分的讨论过：

1. 如果系统负载接近上限，且争用很多，乐观并发控制会导致事务大量中止和重试，从而进一步加重系统负载。

2. 如果系统很空闲，且争用较少，乐观并发控制性能较好，因为其避免了锁的开销。此外，可以调换满足交换律的原子操作顺序，来减少争用。如并发增加的计数器场景。

SSI，顾名思义，基于快照隔离。即在 SSI 隔离级别中，所有的读取都针对一份一致性的快照，这是其区别于早期乐观并发控制之处。在快照隔离之上，增加写写冲突检测算法，以决定哪些事务需要中止重试，是为 SSI。

在之前讨论写偏差时，我们观察到一种一再发生的模式：读取 - 决策 - 写入。

1. 读取：事务首先从数据库中读取到一些数据。

2. 决策：考察读到的数据，做出某种决策。

3. 写入：将对应决策造成结果写回数据库。

即，这里面存在一个因果关系，读为因，写为果。如果在提交时，发现决策的前提（premise，如：“今天有两名医生排到了值班”）不再满足，则后面写入失去意义。因此为了提供可串行化的隔离级别，需要识别这种因果关系，并且能够在提交时检测前提是否失效，以决定是否中止事务。

那如何检测前提是否失效呢？

1. 在读取时，要检测读到的数据版本是否为最新版本。（读之前，可能有未提交的写入）

2. 在写入时，要检测写入的数据是否覆盖了其他事务的读取。（读之后，可能发生了写入）

代入之前的例子，其实是从上述模式的不同阶段来考虑这个冲突的。

快照隔离通常通过多版本并发控制（MVCC）来实现。当事务基于 MVCC 数据库中的某个一致性的快照进行读取时，会忽略其他事务潜在的任何修写入。

在下图中，事务 43 在查询时，认为 Alice on_call = true，但在事务 43 提交时，事务 42 已经先一步提交，并且导致 Alice on_call = false。

为了避免这种异常，数据库需要跟踪由于 MVCC 读所忽略的写入集合（读时发现有更新的未提交版本），如果在提交时检测到这些写入集存在已经提交的对象，则本事务必须终止。

延迟到提交时检测，而不是发现过时读取立即终止，是因为事务并不知道之后是否会发生基于这些读取的写入操作。

总结：读取时，检测写读冲突，延到提交时，看有冲突的写入是否已提交。

即，在一个事务写入某对象时，需要检测是否该数据被另一个事务读取过（TODO：提交时检测？检测读取是否提交？）。

在 2PL 中，我们讨论了索引范围锁，可以基于索引对某个条件范围整体上锁。此处为了检测冲突，使用了类似的技术，但不会真的锁定，只是进行了记录。

如上图，假设在班次编号 shift_id 上存在索引，事务 42、43 在读取了对应数据后，会在 shift_id = 1234 的索引条目上记下事务编号，并在事务和所有并发事务完成时，删除标记。当事务发生写入时，需要通知读过该索引的所有事务（通过标记可以知道）：你读到的数据过期了。该过程类似于上锁，但并不真正的等待，而是简单通知。

如上图，事务 43 会在写入数据时，会通知事务 42 其所读取的数据过期；事务 42 在写入时，也会通知事务 43。但事务 42 首先发起提交，尽管事务 43 的写入影响了 42，但 43 未提交，此时 42 会提交成功。但 43 在提交时，发现收到通知的事务已经提交，则 43 只能中止，然后重试。

总结：在写入时，利用之前在对应索引范围记下的读取事务编号记录冲突，在提交时，看有冲突的读取是否已经提交。

一如既往，实现的细节会影响其性能表现，如事务读写跟踪粒度：

1. 如果细粒度跟踪，虽然能精确的检测到真正的冲突，减少重试，但会有显著的记录开销。

2. 如果粗粒度的跟踪，虽然性能会好，但会导致更多的冲突和重试。

在某些情况下，即使一个事务读到的信息被另外一个事务的写入覆盖，仍然能保证可串行化的隔离级别。这取决于事务读到这些信息后，用来做了什么，PostgreSQL 便根据这个原则来减少不必要的重试。

和 2PL 相比，SSI 的最大优点是，不会通过锁来阻塞有依赖关系的事务并发执行。SSI 就想运行在快照隔离级别一样，读不阻塞写，写不阻塞读。只是追踪记录，在提交时决定是否提交或重试。这种设计是的查询延迟更可预测。尤其是，只读事务可以工作在一致性快照上，而不受影响，这对读负载很重的场景很有吸引力。

相比物理上的串行化，SSI 能够进行平滑扩展。如 FoundationDB 就可以利用多机并行进行冲突检测，从而通过加机器获取很高的吞吐。

事务的中止率会显著影响 SSI 性能。长时间的读写事务大概率会引起冲突，并重试。因此 SSI 要求读写事务尽可能的短。尽管如此，SSI 仍然比物理串行化以及两阶段锁对慢事务更友好。