并发控制是数据库系统实现的一个难点。本文分为三个部分对目前的分布式并发控制技术进行浅析。
一、从用户并发访问可能引起的各种问题入手，引出数据库系统提供的不同隔离级别及其技术实现。
二、分布式场景下并发控制面临的挑战及对应的技术。
三、通过分析VLDB 2018的论文Sundial，看分布式并发控制最新的研究进展。

数据库隔离性

  近几年，各种NewSQL系统进入大家的视野，可以说NewSQL最重要特性之一就是在NoSQL的基础上增加了ACID事务支持[1]。这一节我们先来回顾一下传统数据库的ACID特性，尤其是隔离性级别。对这传统数据库比较熟的同学可以跳过这一节。数据库事务的ACID，持久性是指事务一旦提交，数据就不会再丢失，一般是日志落盘。一致性是对应用定义的一些规则的保证，如数据唯一性等，是通过其他三个属性实现的。原子性是指一个事务是一个不可再分割的最小处理单元，这个单元中的所有操作要么全部成功，要么全部失败。单机数据库的原子性可以通过UNDO日志实现。隔离性是为了解决并发问题，当多个客户端同时访问相同的数据时，如何保证这些访问互不干扰，就是隔离性所做的事情。其中最高的隔离级别Serializable Isolation的意思就是让客户端的并发访问的效果跟序列化依次访问一样，不会有任何干扰。

Read Committed

  事务只有提交了才能保证数据的持久性。假设user1 读(写)到了user2未提交的事务修改过的数据，而最终user2的这个事务未成功提交，那么user1读(写)到的数据就是脏数据。
  解决了这种脏读、脏写的数据隔离级别称为 read committed。这是Oracle 11g, PostgreSQL, SQL Server 2012等数据库的默认隔离级别[2]。
  定义(解决思路)：所有访问只能读写已经提交的数据。
  实现：通过行级锁对数据进行排他性访问，当某个事务对某一行进行写操作时，加一个排他锁，禁止并发写访问。出于性能考虑，对于并发读访问，一般会保留原始数据，将原始数据返回。

Snapshot Isolation (Read Repeatable)

  一个transaction包含两次读数据，两次读数据中间可能被插入了另一个transaction，导致数据不一致问题。如下图(图片来源[2])，Alice有两个账户，她要查询资金总额需要分别查询两个账户再相加。但是在一次查询过程中，并发的有一个转账的transaction，导致这次查询得到的总金额比实际少了100块。

  解决了这种类型的数据不一致问题的隔离级别称为Snapshot Isolation 或 Read Repeatable。
  定义(解决思路)：一个transaction中的所有读操作，只会读到这个transaction开始时数据库中的数据。对于上面的例子，Alice的查询事务开始的时候第二个账户中的金额是500，那么就应该读到500。
  实现：为每个transaction分配一个递增的ID（时间戳），采用multi-version concurrency control (MVCC)机制，每行数据保留多个版本，每个版本也有一个对应的ID(写这个版本数据的transaction ID)。当某个transaction执行时，只能访问ID小于这个transaction ID的数据行。

Serializable Isolation

  并发访问的故事还没有结束，即使数据库保证了Snapshot Isolation的隔离级别，仍然可能会有数据不一致的情况发生。如下图(图片来源[2])，User1和User2分别按图中的次序，读取counter值，加1然后写回。造成的结果是counter值比期望值小1，这种情况称为lost update。

  除了lost update，考虑一个医院医生值班的场景，任何时候必须至少有一个医生值班。当某个值班医生临时有事需要走开的时候，只要确定目前不止一个医生在值班即可。如下图(图片来源[2])，医生Alice 和 Bob 同时有点事情需要离开一会儿，当他们查询目前值班医生的数量时，得到的结果都是2。因此都认为自己可以休息。最终结果就是值班医生一个都没有了。这种不一致情况称为Write skew，造成Write skew的原因是一个transaction 写数据改变了另一个transaction的查询结果，这种情况称为phantom(幻读)。

  可以防止上述所有不一致情况(包括lost update 和 write skew)的隔离级别就是Serializable Isolation。
  两阶段锁(2PL)是最广泛使用的实现Serializability的方法。2PL中的锁分为排他锁和共享锁。所谓两阶段的意思就是在事务执行过程中，对锁的操作分为两个阶段，第一阶段只能获取锁，第二阶段只能释放锁。只能在事务commit之后才能释放锁的2PL称为Strict 2PL。我们可以将2PL自行代入上面lost update 的例子，就会发现lost update不会发生。当某个事务遇到锁冲突的情况下，排队等待锁释放的策略称为WAIT_DIE，这种策略可能导致死锁。如果事务直接终止，称为NO_WAIT策略，这种情况可能导致不必要的事务终止。2PL最大的问题是当并发事务量大时，事务吞吐和响应会非常差。有各种乐观并发控制技术尝试解决这个问题，会在文章的最后一部分中介绍。

  至此，我们已经了解了数据库隔离性的几个级别以及对应的实现技术。现在我们可以来到本文的主题分布式并发控制了。

分布式并发控制

分布式数据系统的以下三个特点，使并发控制变得更具挑战性。
1.Unreliable Clocks
  前面提到MVCC的第一步就是为每个Transaction分配一个递增的ID(时间戳)，然而分布式环境下并没有全局统一的时钟，要做到这一点就非常困难。Spanner[3]通过原子钟加GPS提供平均误差为4ms的TrueTime接口解决这个问题。而OceanBase[4] 使用集中式的服务来提供全局统一的版本号。
2.Replication
  为了保证容灾性，分布式数据库的数据通常都是多副本的。保证多副本的数据一致性，屏蔽多副本带来的并发问题，称为Linearizability。目前一般采用共识(Consensus)协议来实现，如spanner[3] 和 OceanBase[4] 都采用了Paxos协议，TiDB[5] 采用了Raft协议。关于Linearizability以及Consensus，我会在后面文章中分析，本文不再展开。
3.Partitioning
  在分布式数据系统中，数据会按一定规则(如Hash of Key)划分为partitions存储到不同节点。如果一个事务中访问到的数据都在同一个partition，那么使用上一节中提到的数据隔离性技术足矣。而当一个事务会访问多个partitions的数据，问题就变得更加复杂了。

2PC

  一个跨节点的事务，其实可以分解成多个节点上的独立事务，所以问题的关键就在于保证多个节点上的事务，要么全部提交，要么全部终止。
  两阶段提交(2PC)就是这么一个目前被广泛使用的保证多个节点原子提交的方法。2PC将多节点的事务提交分为Prepare和Commit 两个阶段。2PC的过程如下图(图片来源[2])，其中有一个Coordinator 的角色(通常就是发起事务的那个节点)，其他参与数据读写的节点为participants。当transaction读写完数据，准备提交，Coordinator会向所有participants发送prepare请求，询问是否准备就绪。如果得到的所有回复都是yes，Coordinator就会发送commit请求，通知各个节点提交事务。否则，Coordinator就会发送abort请求，通知所有节点事务终止。

  经过2PC，可以做到所有的节点要么全部提交，要么全部终止。乍看之下很美好，然而现实总是充满意外。最大的问题是现实的分布式环境中，网络不可靠(消息会丢)，单个节点不可靠(节点会挂)。所以在2PC的过程中，为了错误恢复，Coordinator发送prepare请求和commit 请求之前都需要持久化日志。而participant回复Coordinator之前也需要持久化日志。考虑一种情况，当participant回复prepare请求yes之后，Coordinator挂了。这个时候participant的事务将处于不确定的状态，它无法决断是该commit还是abort，唯一能做的就是等待Coordinator恢复。这就是2PC的单点问题。为了解决2PC的单点问题，有研究人员提出了三阶段提交(3PC)，但是3PC有个问题是以超时判定某个节点crash。这在现实情况下不一定为真，这可能导致数据不一致。因此，目前大多数系统仍然使用2PC。如OceanBase在使用Paxos保证Coordinator高可用的前提下，省去了传统2PC过程中Coordinator持久化日志的步骤[6]，提高事务性能。
  2PC是在分布式环境下对MVCC和2PL等并发技术的补充。MVCC本身只能提供Snapshot Isolation隔离级别，与2PL结合提供Serializability仍然比较常见[7]。前文也提到了2PL最大的问题就是高并发情况下的性能问题，而在分布式环境下采用2PC的情况下这个问题更甚。因为participant在2PC的过程中是需要一直持有锁直到最终提交成功的，这样其它的并发事务就只有等待或者终止。针对这个问题，越来越多系统开始研究乐观并发控制。

OCC

  乐观并发控制(OCC)早在1981年[8]就提出来了。其思想简单来说就是在一个事务执行过程中，在本地缓存中任意更新数据，但是在提交之前，需要检查本次更新是否与本事务开始之后的新事务提交的数据有冲突(两个事务读写集合是否相交)。如果有冲突，则终止，如果没有冲突，即可提交。OCC虽然可以提高事务并行度，但是在高竞争条件下，不仅无法减少冲突，还使得事务无法尽早终止，浪费资源。因此，在那个年代，OCC只停留在理论研究阶段，并没有什么数据库真正使用这项技术。
  近来，在分布式NewSQL数据库的场景下，一方面网络延迟等因素容易导致2PL过程中节点长时间持有锁，另一方面节约资源不在那么重要，提高并发，提高吞吐率变得更加重要。OCC终于开始在各种系统中落地了，如内存数据库Hekaton[9]，Google的F1[10]。
  OCC的重点在于冲突检查阶段，如何判断在本事务的执行时间内新提交事务的数据与本事务的数据是否有读写冲突。最基本的思想就是判断事务的读写数据之间是否有交集，MaaT[11] (如下图)通过给每行数据增加指向正在读写本数据的事务的时间信息的指针，做到在检查阶段分布式细粒度的判断冲突情况。

  MaaT优化了冲突检查方案，完全消除了锁的存在，且可以每个节点独立的进行冲突检查。但是其冲突判定策略依然没变，那就是若T1事务在提交时发现其读或写到的数据，已被T2事务(T2与T1并发，在T1提交之前提交)修改过，那么T1就只能终止了。然而是不是这种情况就一定是冲突呢？
  Sundial[12]指出这种情况下有时候T1也是可以提交的，并没有发生真正的冲突。这几句话有点绕了，直接看下图。T1和T2分别在2PL(WAIT_DIE)、OCC、Sundial三种并发控制场景下的执行情况。在2PL的情况下，当T2 W(A) 时，T1已经加了读锁，所以要等待T1 commit 释放锁之后，T2才会继续执行，并最终执行成功。在OCC的情况下，T1会终止，因为在冲突检查阶段会发现A已被修改，判定为冲突。而在Sundial的情况下，两个事务都能成功提交，且T2没有被阻塞，提高了响应速度和吞吐。

  Sundial 这个优化乍一看匪夷所思，其实关键在于T1和T2是并发的，而他们唯一共同访问到的数据为A，T1先读了A，之后T2写A。虽然实际上T1在T2之后commit，但是在逻辑上只要T1在T2之前commit 就完全没有问题。图中可以看到，T1的Commit 时间为TS=0，而T2的commit时间为TS=11。Sundial 就是通过这种逻辑commit时间的移动，来使原本的冲突合理化的。Sundial 通过逻辑租约来实现这个冲突检查过程以及逻辑commit时间的移动。简单来说就是，Sundial以tuple 为数据访问粒度，为每个tuple增加一组逻辑时间wts和rts，称为逻辑租约。wts表示tuple的最后修改逻辑时间，rts表示租约的最后期限，事务commit的逻辑时间ts需要满足 tuple.wts ≤ T .commit_ts ≤ tuple.rts。租约的更新算法在论文[12]中有详细描述，这里就不展开了。

总结

本文介绍了数据库的Read Committed、Snapshot Isolation、Serializability三种隔离级别，MVCC、2PL、2PC、OCC等主流的并发控制技术，以及OCC最近的一些研究进展。想要更深入的同学可以看下这篇VLDB2017的论文[13]，其对目前主要的并发控制技术进行了各方面的性能测试和对比。

引用

[1] Pavlo, Andrew, and Matthew Aslett. "What's really new with NewSQL?." ACM Sigmod Record 45.2 (2016): 45-55.
[2] Kleppmann, Martin. Designing data-intensive applications: The big ideas behind reliable, scalable, and maintainable systems. " O'Reilly Media, Inc.", 2017.
[3] Corbett, James C., et al. "Spanner: Google’s globally distributed database." ACM Transactions on Computer Systems (TOCS) 31.3 (2013): 8
[4] https://zhuanlan.zhihu.com/p/47667540
[5] https://github.com/pingcap/tidb
[6] https://zhuanlan.zhihu.com/p/42142376
[7] Wu, Yingjun, et al. "An empirical evaluation of in-memory multi-version concurrency control." Proceedings of the VLDB Endowment 10.7 (2017): 781-792
[8] Kung, Hsiang-Tsung, and John T. Robinson. "On optimistic methods for concurrency control." ACM Transactions on Database Systems (TODS) 6.2 (1981): 213-226.
[9] Larson, Per-Åke, et al. "High-performance concurrency control mechanisms for main-memory databases." Proceedings of the VLDB Endowment 5.4 (2011): 298-309.
[10] Shute, Jeff, et al. "F1: A distributed SQL database that scales." Proceedings of the VLDB Endowment 6.11 (2013): 1068-1079.
[11] Mahmoud, Hatem A., et al. "Maat: Effective and scalable coordination of distributed transactions in the cloud." Proceedings of the VLDB Endowment 7.5 (2014): 329-340
[12] Yu X, Xia Y, Pavlo A, et al. Sundial: harmonizing concurrency control and caching in a distributed OLTP database management system[J]. Proceedings of the VLDB Endowment, 2018, 11(10): 1289-1302.
[13] Harding, Rachael, et al. "An evaluation of distributed concurrency control." Proceedings of the VLDB Endowment10.5 (2017): 553-564.