1。数据库并发控制的作用1.1事务的概念在介绍并发控制之前，首先需要了解一下事务。数据库提供了增、删、改、查询等几种基本操作，用户可以灵活组合这些操作，实现复杂的语义。在很多场景下，用户希望一组操作能够作为一个整体一起生效，这就是一个事务。事务是数据库状态变化的基本单位，包括一个或多个操作（如多条SQL语句）。一个经典的转账交易包括三个操作：（1）检查A账户余额是否充足。(2)够了，A扣100。(3)B账户增加100元。事务有一个基本特征：这组操作要么一起生效，要么不一起生效。如果事务执行过程中出现错误，则必须撤回所有已执行的操作。这就是事务的原子性。如果发生故障后，部分有效的交易无法撤销，数据库进入不一致状态，这与现实世界的事实相反。比如从A账户扣款100元后转账交易失败，B账户还没有充值。如果不撤回A账户的扣款操作，世界将莫名其妙地损失100元。原子性可以通过日志记录（变化前的值）来实现，有的数据库会在本地缓存事务操作，失败时直接丢弃缓存中的操作。只要事务被提交，它的结果就不能改变。即使系统宕机，重启后数据库的状态也和宕机前一样。这就是事务的持久化。只要数据存储在非易失性存储介质中，停机就不会造成数据丢失。因此，数据库可以采用以下方法来保证持久化：(1)在事务完成之前，保证所有的变化都存储在磁盘上。或者（2）在提交完成之前，将事务的变化信息以日志的形式保存在磁盘上，重启进程根据日志恢复数据库系统的内存状态。一般来说，数据库会选择方法（2），原因留给读者自己思考。为了提高资源利用率和事务执行效率，减少响应时间，数据库允许事务并发执行。但是，当多个事务同时操作同一个对象时，必然会发生冲突，事务的中间状态可能会暴露给其他事务，导致某些事务根据中间状态将错误的值写入数据库其他交易的状态。需要提供一种机制保证事务的执行不受并发事务的影响，让用户感觉当前只有自己发起的事务在执行，这就是隔离。隔离让用户专注于单个事务的逻辑，而不考虑并发执行的影响。数据库通过并发控制机制保证隔离。由于隔离对事务执行顺序的要求很高，很多数据库都提供了不同的选择，用户可以牺牲部分隔离来提高系统性能。这些不同的选项是事务隔离级别。数据库反映了现实世界，而现实世界中有很多限制，比如：无论你如何在账户之间转账，总金额不会改变等现实限制；年龄不能为负数，性别只能为男性、女性或变性人。完整性约束，例如选项。交易执行无法打破这些约束并确保交易从一种正确状态转移到另一种正确状态。这是一致性。与前三个属性完全由数据库实现来保证不同，一致性不仅取决于数据库实现（原子性、持久化、隔离性也是为了保证一致性），还取决于应用程序端编写的事务逻辑。1.2事务并发控制如何保证隔离性为了保证隔离性，一种方式是串行执行所有事务，使事务之间互不干扰。但是，串行执行的效率很低。为了提高吞吐量和减少响应时间，数据库通常允许同时执行多个事务。因此，并发控制模块需要保证事务并发执行的效果与事务串行执行的效果完全一致（可串行化），以满足隔离性的要求。为了便于描述并发控制如何保证隔离，我们简化了事务模型。一个事务由一个或多个操作组成，所有的操作最终都可以拆分成一系列的读和写。一批同时发生的事务，所有读写的一个执行顺序，定义为一个schedule，例如：T1，T2同时执行，一个可能的schedule：T1.read(A),T2.read(B),T1.write(A),T1.read(B),T2.write(A)如果并发事务执行的调度效果等同于串行执行调度（serialschedule），则可以满足串行化。一个不断改变读写操作顺序的schedule，总会变成serializableschedule，只是有些变化可能会导致事务执行的结果不同。在一个调度中，如果两个相邻的操作调换位置，导致事务结果发生变化，那么这两个操作就是冲突的。冲突需要同时满足以下条件：1.这两个操作来自不同的事务2.其中至少有一个是写操作3.操作对象相同。因此，常见的冲突包括：读写冲突。有两种调度：事务A先读取一行数据，事务B后修改该行数据，事务B先修改一行事务，事务A读取该行记录。事务A读取的结果不同。这样的冲突可能会导致不可重复读异常和脏读异常。写读冲突。原因同读写冲突。这样的冲突可能会导致脏读异常。写-写冲突。两个操作先后写入一个对象，后一个操作的结果决定了写入的最终结果。此类冲突可能会导致更新丢失异常。只要数据库保证并发事务的调度保持冲突操作的执行顺序不变，只替换不冲突的操作，就可以成为串行调度，它们可以认为是等价的。这种等价判断方法称为冲突等价：两个调度的冲突操作顺序相同。例如下图的例子，T1write(A)和T3read(A)冲突，T1先于T3发生。T1read(B)和T2write(B)冲突，T2先于T1，所以左图事务执行的调度相当于T2、T1、T3串行执行的串行调度（右图）.左图的执行顺序满足冲突可串行化。然后分析一个反例：T1read(A)和T2write(A)冲突，T1先于T2，T2write(A)和T2write(A)冲突，T2先于T1。下图中的调度不能等同于任何串行调度。是不满足冲突串行化的执行顺序，会导致更新丢失的异常。一般来说，可串行化是一个比较严格的要求。为了提高数据库系统的并发性能，许多用户愿意降低隔离要求以寻求更好的性能。数据库系统往往会实现多个隔离级别，供用户灵活选择。事务隔离级别可以参考这篇文章。既然并发控制的要求明确了，那么如何实现呢？下面的文章将介绍基于乐观冲突检测的并发控制的常用实现方法。2.基于两级锁的并发控制2.12PL既然要保证操作按正确的顺序执行，那么最容易想到的就是加锁保护访问对象。数据库系统的锁管理器模块专门负责锁定和释放访问对象，确保只有持有锁的事务才能操作相应的对象。锁可分为两类：S-Lock和X-Lock。S-Lock是读请求的共享锁，X-Lock是写请求的独占锁。它们的兼容性是这样的：操作同一个对象，只有两个读请求是相互兼容的，可以同时执行，而且读写操作都会因为锁冲突而串行执行。2PL（两阶段锁定）是最常见的基于锁的数据库并发控制协议。顾名思义，它由两个阶段组成：Phase1：Growing，事务向锁管理器请求它需要的所有锁（有可能加锁失败）。Phase2：Shrinking，事务释放Growing阶段获得的锁，不再申请新的锁。为什么要把加锁和解锁分成两个截然不同的阶段呢？2PL并发控制的目的是实现可序列化。如果并发控制没有提前申请所有需要的锁，而是在释放锁后，允许再次申请锁。可能会出现一个事务中对同一个对象的两次操作之间，其他事务修改了这个对象（如下图），导致无法实现冲突serializable，出现不一致（下图例子是丢失更新）。2PL可以保证冲突可串行化，因为事务必须获得所有需要的锁才能执行。比如正在执行的事务A和事务B发生冲突，事务B要么已经执行完，要么还在等待。因此，那些冲突操作的执行顺序与串行执行BA或AB时冲突操作的执行顺序是一致的。那么，只要数据库采用2PL，一致性和隔离性就可以保证了吗？我们来看这个例子：上面的执行顺序符合2PL，但是T2读到了未提交的数据。如果此时回滚T1，会触发级联回滚（任何事务都看不到T1的变化）。因此，数据库经常使用增强版的S(trong)S(trict)2PL，它与2PL有点不同：在收缩阶段，只有在事务结束后才能释放锁，彻底消除了未提交的数据交易被阅读。2.2死锁处理并发的事务加锁和解锁不可避免地避免不了一个问题——死锁：事务1持有A锁和其他B锁，事务2持有B锁和其他A锁。目前，死锁问题的解决方案有两种：死锁检测：数据库系统根据waits-forgraph记录事务的等待关系，其中一个点代表一个事务，一条有向边代表一个事务等待另一个事务来释放一个锁。当等待图中出现循环时，表示发生了死锁。系统后台会定时查看等待图。如果发现循环，则需要选择合适的事务中止。死锁预防：当一个事务请求一个已经持有的锁时，数据库系统会杀死其中一个事务以防止死锁（一般情况下，事务持续时间越长，保留的优先级越高）。这种预防性方法不需要等待图，但会增加事务被终止的速度。2.3意向锁如果只有行锁，那么一个事务需要获取1亿个行锁来更新1亿条记录，会占用大量的内存资源。我们知道锁是用来保护数据库内部访问对象的。这些对象可能是：属性、元组、页面和表（根据它们的大小）。对应的锁又可以分为行锁、页锁等。锁、表锁（没有人实现属性锁，对于OLTP数据库来说，最小的操作单位是行）。对于事务来说，当然最好是获取最少的锁。比如更新1亿条记录，或许加个表锁就够了。更高级别的锁（如表锁）可以有效减少资源占用，显着减少锁检查次数，但会严重限制并发。较低级别的锁（如行锁）有利于并发执行，但在事务请求对象较多的情况下，需要进行大量的锁检查。为了解决高层锁限制并发的问题，数据库系统引入了意向（Intention）锁的概念：Intention-Shared(IS)：表示一个或多个内部对象被S-Lock保护，比如一张表加IS，表中至少有一行被S-Lock保护。Intention-Exclusive(IX)：表示其中的一个或多个对象受X-Lock保护。比如一张表加了IX，表中至少有一行被X-Lock保护。Shared+Intention-Exclusive(SIX)：表示内部至少有一个对象受X-Lock保护，自身受S-Lock保护。例如，如果一个操作需要扫描整个表并更改表中的几行，则可以向表中添加SIX。读者可以这样思考为什么XIX或者XIS意向锁和普通锁没有兼容关系：.(1)此时要对表发起DDL操作，需要申请表的X锁，那么看到表持有IX就可以直接等待，而不用去检查表中的行是否holdrowlocksonebyonebyholdrowlocks，有效减少检查开销。(2)这时候其他的读写事务过来了，因为表加了IX而不是X，不会阻止对该行的读写请求（表先加IX，再加S/Xtotherecord)，如果事务不涉及用X锁定的行，则可以正常执行，增加了系统的并发度。3.基于TimingOrder（T/O）的并发控制，为每一个事务分配一个时间戳，决定事务执行的顺序。当事务1的时间戳小于事务2时，数据库系统必须保证事务1先于事务2执行。时间戳的分配方式包括：（1）物理时钟；(2)逻辑时钟；(2)混合时钟。3.1基本T/O基于T/O并发控制，读写不需要锁，每行记录都标有最后一次修改并读取它的事务的时间戳。当事务的时间戳小于记录的时间戳时（无法读取“未来”数据），需要中止后重新执行。假设记录X标记了读写的两个时间戳：WTS(X)和RTS(X)，交易的时间戳为TTS，可见性判断如下：Read:TTS
