Concurrency Control Methods
Transaction Locks
DBMS有一个锁管理者用来决定一个事务是否能够拥有一个锁，有整个系统的全局信息。
1.Shared Lock(S-LOCK)：允许多个事务读同一个对象在同一时间内。
2.Exclusive Lock(X-LOCK)：允许一个事务去修改一个对象。和其他的锁不能同时存在。
锁的运行方式：
1.事务向lock manager请求锁。
2.lock manager要么满足要么拒绝请求，取决于其他事务拥有的锁的类型。
3.事务在不需要锁的时候释放它们。
4.lock manager更新内部的lock-table，并且把锁给等待中的事务。
Two-Phase Locking
两阶段锁是一种悲观并发协议，将事务的进行分为两个阶段：Growing和Shrinking。
Phase1：Growing
处于这个阶段的事务会向DBMS的lock manager请求需要的锁。
Phase2：Shrinking
一旦一个事务释放了一个锁，这个事务就会进行这个阶段。在这个阶段里事务只能够释放锁而不能够请求锁。
优缺点
2PL能够保证依赖图是无环的，所以可以确保是conflict serializable，但是可能造成cascading aborts，具体来说就是当一个事务aborts时，会引起其他有关联的事务一起aborts，这样可能会引起特别多的回滚操作。
而且2PL的限制更加严格，可能会有一些原本是serializable的调度方案不满足2PL的限制。
Strong Strict Two-Phase Locking
在2PL的基础上取消了shrinking阶段，只有在事务commit的时候才会释放锁。
2PL Deadlock Handling
不同的主流数据库用不同的方法处理死锁问题。有的采用detection的方法，即会不定期检测是否出现了死锁问题，有的采用preevention，即每一步都先看是否会出现死锁问题，在死锁问题出现前就解决掉。
Approach1：Deadlock Detection
DBMS创建一个waits-for图，图中的点都是事务，如果事务Ti等待Tj释放锁，就从Ti连一条边向Tj。这个系统会定期检查图中是否存在环然后决定如何去破坏这个环。
1.如果DBMS检测到了死锁，它会选择一个牺牲者去restart或者abort。
2.DBMS根据事务的很多特性去决定选哪一个牺牲者。比如事务创建时间、有多少个条目被锁住了等等。
而且回滚也不是全部回滚，可能只是回滚事务的一部分。
Approach2：Deadlock Prevention
当一个事务尝试去获取一个锁时，如果这个锁已经被其他事务占据了，DBMS就会做出一些防止死锁的事情。
给事务分配时间戳属性，可以设定要么是老的事务优先级高，要么是新的事务优先级高。如果T1要去获取T2上的锁，如果T1的优先级高，T1等待，否则T1aborts。
Lock Granularities
如果一个事务想要修改特别多的tuples，如果锁太细了，就会在锁上面花很多时间。解决这个问题的方法是分层，思想就是我们一次锁更高层次，比如把一页或者一个table给锁住，而不是一次一个tuple。
我们设计了一种叫做Intention locks的东西，允许在更高层次的点上加锁而不需要去检查所有的后代节点。如果一个点处于intention模式，那么说明它下面层次的点被显式上锁了，如果它下面层次的所有点都上了某一种锁，那么这个点的intention锁可以进行提升，比如Intention-shared锁可以提升为shared锁。
有这么几种锁：
1.Intention-Shared（IS）：表明低层次的点被共享锁锁住了。
2.Intention-Exclusive（IX）：表明低层次的点被exclusive或共享锁锁住了。
3.Shared+Intention-Exclusive（SIX）：这个点已经处于shared mode，并且低层次的点正要被exclusive锁锁住。
我们在S、X的基础上添加了额外三种类型的锁，那么当我们要从上往下去遍历到一个叶子节点时，我们对路径上的逐个点尝试加锁，如果当前要加的锁和这个点上已经存在的锁冲突了，这次操作就失败了，就要restart。这里会有一张5*5大小的表格来表示每两种类型的锁之间会不会冲突。
举个例子：如果我们要进行一次读取操作，我们会尝试给路径上的所有点加上Intention-Shared锁，给叶子节点加上Shared锁；如果我们要对所有的叶子节点进行一次读取操作，并且修改其中某个叶子节点的值，我们会给路径上的所有点加上SIX锁。
Timestamp Ordering Concurrency Control
1.Timestamp ordering是一种乐观并发协议，不需要在操作前去请求锁，而是通过时间戳去确保serializability order。
2.每个事务Ti都会被赋值一个独特的严格单调的时间戳：TS(Ti)。
3.如果TS(Ti) < TS(Tj)，那么DBMS必须确保最后的执行方案等同于Ti在Tj之前发生的一个serial schedule。
Basic TimeStamp Ordering
每个数据库对象X都被赋予了一个时间戳，这个时间戳是最后一次对这个对象进行读/写操作的事务的时间戳，如W-TS(X)：X的写时间戳；R-TS(X)：X的读时间戳。
假设接下来要进行的步骤属于事务Ti，对X进行操作：
Read Operations：
1.如果TS(Ti) < W-TS(X)，说明如果Ti对X操作，会影响到后面对X的写操作，因此将Ti给abort并且用原来的TS值restart。
2.否则先让Ti去读X，然后将R-TS(X)更新为max(R-TS(X),TS(Ti))。
3.这里Ti对X的操作之前必须先拷贝X，在副本上进行操作。
Write Operations：
操作基本上和读一样，只是一开始的判断条件为TS(Ti) < R-TS(X)或者TS(Ti) < W-TS(X)时要abort并且restart Ti。
托马斯优化：如果只是TS(Ti) < W-TS(X)，那么只需要忽略掉这个写操作让事务继续进行下去即可。因为这个写操作在其他的写操作之前发生，因此一定会被其他的写操作给覆盖，那么这次写操作也就是不必要的了。但是需要注意的是托马斯优化会破坏conflict serializable。
优缺点
不会造成死锁问题，如果不用托马斯优化可以确保方案是conflict serializable的。但是如果短事务持续冲突，会让长事务一直处于starvation状态；并且调度方案可能是不可恢复的；复制数据到事务的工作空间花销较大；
Recoverable
如果所有的事务在他读/写涉及到的其他事务提交之后提交，那么这个事务就是可恢复的。
Optimistic Concurrency Control
1.如果事务之间的冲突很罕见，并且大多数事务流程很短，那么就可以假设事务之间不会出现冲突。OCC这种方法在冲突数量少的时候表现比较好。
2.整个OCC分为三个阶段：Read、Validation、Write。
Read Phase：得到事务的read/write set，并把write存到自己的工作空间。
Validation Phase：当一个事务commit的时候，检查它是否跟其他的事务冲突了。
Write Phase：如果通过了Validation Phase，将自己的变化应用到数据库中，否则abort并且restart事务。
3.DBMS为每个事务创建一个私自的工作空间，所有的事务的修改都被应用在工作空间中、所有对对象的读取操作都将对象复制到工作空间中、不同事务的工作空间是相互隔离的。
4.如果一个事务commit了，那么DBMS会将这个事务空间的write set和其他事务进行比较。如果合法就把这个write set放到全局数据库中。
Validation Phase
每个事务只有在进入Validation阶段才会被赋予一个时间戳，Ti会检查其他的所有事务，看是否存在RW和WW冲突，并且只会从一个方向上检查，例如只会检查Tj > Ti的事务j或者检查Tj < Ti的事务j。
如果TS(Ti) < TS(Tj)，那么下面三个条件必须满足至少一个：
1.Ti 在 Tj开始前完成了所有阶段。
2.Ti在Tj开始写阶段前完成了，并且Ti不会去写任何被Tj读的对象。
3.Ti在Tj完成读阶段前完成了读阶段，并且Ti不会去写任何被Tj写或读的对象。
优缺点
1.将数据复制到事务各自的空间中花费过高。
2.Validation和Write阶段是瓶颈。
3.这里Abort只有可能发生在事务执行完的时候，比其他方法的Abort所花时间可能更长。
4.分配时间栈也是一个时间瓶颈。
Partition-Based T/O
如果用OCC，在事务非常多的情况下，Validation就会花很多时间。如果我们把数据库给分区，并且只检查那些涉及到相同分区的事务之间是否冲突就能减少复杂度。这里我们只会给区上锁，区里面的操作都是单线程的。
对每个分区，我们都维护一个队列，取队列中第一个事务进行操作：
1.获取分区的锁。
2.如果这个事务涉及到的所有分区的锁都被获取了，那么他就可以开始执行。
3.事务可以在获得锁的分区中读/写任何东西，因为可以把在分区中的操作看成是单线程的，如果一个事务尝试到一个他没有获取锁的分区中，他就会abort并且restart。
优缺点
1.很快，因为DBMS一般提前可以知道每个事务会访问哪些分区，并且大部分事务只会访问一个分区。
2.如果事务访问涉及到多个分区，就会比较麻烦。