2PL(两阶段锁定)算法如何工作 -Vlad Mihalcea

19-12-03 banq
                   

2PL(两阶段锁定)算法是关系数据库系统用来保证数据完整性的最古老的并发控制机制之一。

在本文中,我将解释2PL算法如何工作以及如何以任何编程语言实现它。

锁类型

在我们开始讨论2PL算法实现之前,解释读和写锁的工作方式非常重要。

1.读锁:读取或共享锁定可防止在并发读取的同时写入。

2.写锁:写锁或排他锁不允许对给定资源进行读和写操作。

某些数据库系统(例如PostgreSQL,MySQL或SQL Server)提供了获取指定元组或元组范围上的读取和写入锁的可能性。其他数据库系统(例如Oracle)仅允许通过FOR UPDATE子句获取写/独占锁。

数据库      Read lock clause        Write lock clause
Oracle      FOR UPDATE            FOR UPDATE
SQL Server   WITH (HOLDLOCK,ROWLOCK)   WITH (HOLDLOCK,UPDLOCK, ROWLOCK)
PostgreSQL   FOR SHARE             FOR UPDATE
MySQL       LOCK IN SHARE MODE      FOR UPDATE

但是,读和写锁不仅限于数据库系统。传统上,进入Java synchronized块允许获取排他锁,从1.5版开始,Java允许通过ReentrantReadWriteLock对象进行读写锁。

两相锁定/两段锁

仅锁是不足以防止冲突。并发控制策略必须定义如何获取和释放锁,因为这也会影响事务交织。

为此,2PL协议定义了一种锁定管理策略,以确保严格的可序列化性。

2PL协议将事务分为两部分:

  • 扩展阶段(获取锁,并且不允许释放锁)
  • 收缩阶段(释放所有锁,并且无法进一步获取其他锁)。

对于数据库事务,扩展阶段意味着允许从事务开始到结束为止获取锁,而收缩阶段由提交或回滚阶段表示,就像在事务结束时一样,所有已获取的锁锁被释放。

下图显示了2PL如何协调事务交织:

  • 爱丽丝(Alice)和鲍勃(Bob)都post通过SELECT FOR SHARE的PostgreSQL语句获得了对指定记录的读取锁定。
  • 当Bob尝试对post条目执行UPDATE语句时,其语句被锁管理器阻止,因为UPDATE语句需要在该post行上获取写锁,而Alice仍对该数据库记录保持读锁。
  • 只有在Alice的事务结束并且释放了所有锁之后,Bob才能恢复其UPDATE操作。
  • Bob的UPDATE语句将生成锁升级,因此他先前获取的读取锁将被排他锁替换,这将防止其他事务获取同一post记录上的读取或写入锁。
  • 爱丽丝启动了一个新事务,并发出了SELECT FOR SHARE针对同一post条目的读取锁获取请求的查询,但是由于鲍勃对该记录拥有排他锁,因此该语句被锁管理器阻止。
  • 提交Bob的事务后,将释放他的所有锁,并且可以恢复Alice的SELECT查询。

严格的可序列化(可串行化、可线性化)

2PL算法提供严格的可序列化性,这是涉及数据完整性的黄金标准。严格的可序列化性意味着结果既可序列化又可线性化。

如果两个或多个事务的关联读取和写入操作以某种结果等效于某种串行执行的方式交错,则它们是可序列化的。例如,如果我们有两个事务A和B,只要结果是A,B或B,A,则这两个事务都是可序列化的。对于N个事务,结果必须等于N!事务排列之一。

但是,可串行性未考虑时间流。另一方面,线性化意味着基于时间的排序。例如,如果任何后续读取将反映先前写入操作所做的更改,则系统是可线性化的。有关Lienearizbaility的更多详细信息,请查看本文