二阶段提交
1.简介¶
为了为事务提供隔离性，系统需要提供一些手段如为每一个事务提供一个视图（即为每一个事务提供一个数据副本）等手段。
一种最简单的方式是利用锁来保护事务操作的数据，在对每一个数据进行操作时，都需要去获取锁的权限。
这是一种悲观锁，本质是利用锁的所有权对对象的所有权进行分配。另一种悲观锁是利用时间戳对对象的所有权进行分配，在后文中讨论。
悲观锁是一种相对较重、代价较高的并发控制手段，在并发事务的数据交集较多的时候拥有好的表现效果。另外一种类型的锁被称之为乐观锁，它假设并发事务的冲突较少，只在结束时才进行冲突检测，在并发事务数据交集较少的时候拥有好的表现效果，在后文中讨论。
本文将要讨论的主要问题有二阶段提交，死锁检测与避免以及层级锁（Hierarchical Locking)。
2.Lock type¶
- s-lock:shared locks for read.
- x-lock:exclusive locks for writes.
读锁与读锁兼容，而写锁和任何锁都不兼容。
3.Two-phase locking¶
Two-phase locking是一个并发协议，在不需要提前知道事务的具体细节就可以保证conflict serializability。二阶段提交包含两个阶段：
- Growing：去向lock manager获取事务所需要的锁。
- Shrinking：该事务只允许使用在growing阶段得到的锁，不能获取新的锁。
本质是因为，如果对于两个有事务交集的事务，那么这种只在Growing阶段获取锁且只在Shrinking阶段丢弃锁的手段会使得交集数据强制形成顺序，从而在依赖图中不成环。若形成了冲突，那么就会因为死锁检测而有一方事务被中止。
这又可能会导致多米诺效应的cascading aborts，即一个事务获取了另一个事务Shrinking放弃的锁，但由于某些原因，另一个事务最终出错回滚了，那么就可能会导致一系列的事务一起回滚。
解决方法是使用更严格的Strong Two-phase Locking，即事务在结束的时候才会一次性放弃所有锁。
4.DeadLock¶
因为事务只在获得所有锁之后才会放弃锁，因此可能会造成死锁。
实现方式是在系统中执行一个后台进程\线程，定期进行检测。但这种行为可能会占用很多资源，因此这个周期取决于你不想死锁存在的最长时间为多少。
MySQL的设置周期语句为SET GLOBAL innodb_lock_wait_timeout = x;
4.1.死锁检测¶
构建Waits-for graph，其中点由事务构成，边为等待该锁的事务指向持有该锁的事务，若成环则产生了死锁。
造成死锁后直接终止其中的一些事务即可。简单的策略有：
- Timestamp：运行时间最短的
- Progress：执行命令最少的
- Locks num：获取最多锁的
- Rollback num：需要回滚数量最多的
4.2.死锁避免¶
在获取锁的时候就检测有没有可能造成死锁。有两种根据时间戳的避免策略：
- Wait-Die(Old Wait for Young)：若另一个事务比本事务的时间戳大，那么本事务就会等待；否则直接放弃本事务。
- Wount-Wait(Young Wait for Old)：若另一个事务比本事务的时间戳大，那么本事务就会中止另一个事务并获取锁；否则本事务进行等待。
本质是根据时间戳安排在冲突时的锁获取顺序。
5.Hierarchical Locking¶
可以想象假如一个事务需要对十亿个tuple进行更新，那么如果都用同一粒度的锁，对lock manager的影响是很大的，即lock manager需要在内存中构建一个很大的数据结构对这些tuple的锁进行状态标识。
因此，Lock应该是具有层级的。如若事务获取了table的锁，则暗示了该事务获取了该table的所有page的锁，也拥有所有tuple的锁。