Two-Phase Locking.docx

Two-Phase Locking简介：Two-Phase Locking，简称是2PL，中文通常被翻译为二项锁，是管理事务调度（Transaction Scheduling）的一项重要技术概念，主要应用场景为支持事务的存储或计算系统中，如Mysql数据库中innodb引擎对事务调度即使用2PL技术。2PL本身的技术概念比较简单，解释起来不难，但是要吃透它，就涉及到很多外围的技术概念，为了能够更好地理解这个技术，先做一些技术知识的铺垫说明。知识预备：几个系统能力特征描述概念。(1) Recoverability（可恢复性）：即系统恢复到之前正常运行状态的能力。其中更多地是强调数据的可恢复性，即数据与宕机或重启前是否完全一致。对于一些简单系统而言，可以通过把数据定期全部dump出来，恢复时全部reload这样的方法，Recoverability就能够满足要求（由于dump的时间间隔，并不能完全达到恢复成最后运行时刻的状态）。要保证Recoverability常用方法是基于redo-log（恢复日志/重写日志），重启时依次读取redo-log中的操作记录，从而恢复整体系统数据。要做到这点，需要有一个前提，就是事务执行的过程可以完全被依次操作redo-log的记录进行代替，这就引出另外一个概念Serializability（可串行化）。(2) Serializability（可串行化）：也有称为：冲突可串、可串性等，简单来讲，即一堆事务的调度执行（可能是并行的调度），可以等价为一个串行的调度（下一个事务在上一个事务的最后一个操作完成之后开始）。这么讲非常抽象，由于Serializabilty是一个非常理论性质的定义，在很多数据库相关的教科书中出现较多，而且对其定义也有非常数学化的解释，这里我很难避免数学方式的描述，但尽量描述的通俗一些。Serializability的概念建立在Conflct（冲突）的概念之上，下面基于一个简单例子进行说明。时间顺序Transaction(1)Transaction(2)Time0 (假设A=10;B=20)Time1Read Variable ATime2Write Variable A=30Time3Write Variable B=30Time4Write Variable B=A*100ResultA=30;B=1000上面描述了两个事务的一种调度过程，其中事务1和事务2各自都包含两个操作。其中对同一个变量的操作，称为冲突。因此事务1中Read A与事务2中Write A是冲突，事务1中Write B与事务2中Write B也是冲突。当同一时间遇到冲突操作时，一个执行，一个等待其执行完成，从而使冲突在不同的时间段执行（实际情况是通过Lock方式），如果一个系统允许以上例子的调度方式，从冲突执行顺序上看，是事务1事务2事务1，那么可能的两种串行化方式，都无法得到最后的数据。时间顺序串行方案1串行方案2Time0 (假设A=10;B=20)Time1(开始执行事务1)Read Variable AWrite Variable A=30Time2Write Variable B=A*100Write Variable B=30Time3(开始执行事务2)Write Variable A=30Read Variable ATime4Write Variable B=30Write Variable B=A*100ResultA=30;B=30A=30;B=3000串行化在数学上的定义，即为事务在冲突执行顺序上无环。实例中事务1事务2事务1则出现环。(3) Strictness（严格性）：简单而言，即数据读取的变化保证严格与事务执行的顺序一致。为什么要提出Strictness的问题，在数据系统中通常会由于事务调度问题，引起几类数据问题：A. 更新丢失问题时间顺序Transaction(1)Transaction(2)Time0 (假设A=10)Time1Read Variable ATime2Read Variable ATime3Write Variable A=A*100Time4Write Variable A=A*10ResultA=100事务1的操作完全丢失，因为事务2不是基于事务1的结果进行操作。B. 不可重复读问题时间顺序Transaction(1)Transaction(2)Time0 (假设A=10)Time1Read Variable ATime2Read Variable A（10）Time3Write Variable A=A*100Time4Read Variable A（100）C. 读脏数据问题时间顺序Transaction(1)Transaction(2)Time0 (假设A=10)Time1Write Variable A=100Time2Read Variable A（100）Time3Aborts and RollBack(4) Cascadinglessness（避免级联回滚）：也称为Avoid Cascading Aborts，ACA。当有(3)中描述的事务1出现Abort，但数据已经被其它事务读取，那么不仅要事务1回滚，相关联的事务（事务2）也要进行回滚，那么这就引起了Cascading Aborts问题。Cascadinglessness是描述系统即使出现回滚，也不会级联回滚。(5) Commitment Ordering（事务提交有序）：也称为Commit Ordering，CO。这是一个技术方法概念，其实实现方式有很多种，比如后面基于2PL的一种变种也能达到这种效果。但CO的主要目的，其实是为了Serializability，所以把CO定位成一种方法，而不是系统的一种特征，更为合适一些。2PL：经过对预备知识的了解，我们可以梳理出一个简单的逻辑线 Serializability Recoverability，而Recoverability可以做很多的事情，比如系统备份、系统重启恢复、系统灾难恢复等。所以如何能够实现Serializability便成为了技术焦点，这也就引出了对于2PL研究的意义。Two-Phase Locking，解释起来其实很简单，就是一个事务，对于所有的加锁和解锁分成两个前后的步骤。(1) Expanding Phase（也有的称为Growing Phase）：在这个阶段，只能加锁，不能解锁；(2) Shrinking Phase：在这个阶段，只能解锁，不能加锁。（关于Shrinking Phase有个概念容易迷糊，那就是2PL中并没有强调Shrinking Phase究竟什么时候开始，很多人容易误解为Expanding Phase完成，事务就算完成commit，其实不是这样，两者不是一个概念，但expanding phase肯定要早于事务的commit）如果所有要调度的事务，都按照Two-Phase Locking的方式来进行，即满足Two-Phase Locking Protocol，那么可以保证所有事务的Serializability。这个是可以证明的，利用反证法简单说明一下：如果一组调度的事务不能串行化，就表示执行顺序有环（Serializability的定义），假设有3个事务，T1/T2/T3，都满足2PL，但执行顺序为T1-T2-T3-T1。那么就表示T1分成两个时间阶段来执行，并且在T1-T2是要解锁，在T3-T1是要加锁，这个与T1满足2PL矛盾。证毕。S2PL：2PL非常简单，但有2个比较致命的问题，从而导致在实体项目和系统中，使用较少，最多只是学术上的研究。问题1就是并没有保证Strictness；问题2就是需要系统能够检测到Phase-1结束的时间，而这个在实际系统中是比较难做到的。针对Strictness的解决，就引出了Strict Two-Phase Locking（S2PL），其在2PL的概念之上，新增一个要求，那就是写锁（write lock，具体是什么，由于概念比较简单，就不说了，跟read lock呼应）需要在事务commit或者abort后才能释放，而读锁则不用。通过这个方式，可以保证Strictness。SS2PL：S2PL由于比较难于检测到Phase-1结束的时间，这个是一个应用级别的问题，所以阻碍了S2PL在实际系统中的应用。针对这个问题，就引出了Strong Strict Two-Phase Locking（SS2PL），其在2PL的概念之上，将读锁和写锁都要求在事务commit或者abort后才释放，这样就不用去检测Phase-1的结束时间，整个Phase-2由于锁基本统一时间释放，因此可以认为没有Phase-2。对于SS2PL很多会有疑问，相对与S2PL而言，SS2PL把读锁延迟释放，并发调度能力上（concurrency）不是会有影响么？从实际应用上看，这个影