有多种并发控制算法的分类方式。按照同步原语可以将并发控制算法分成两类：基于互斥存取共享数据的算法和将事务排序按规则执行的算法。图9.10并发控制算法的分类●在主本封锁中，将每个封锁单元的某个副本指定为主本，在访问该单元时主本必须封锁。这些算法可以分成基本TO、多版本TO和保守TO等。实际上，在某些基于封锁的算法中也使用时标，因为这样可以改进效率和并发性，我们称为混合算法。......
2023-10-28
分布式数据库技术：封锁型并发控制算法
【摘要】：基于封锁的并发控制的主要思想是，保证冲突操作共享的数据一次只能由一个操作存取。表9.1封锁模式的兼容矩阵在基于封锁的系统中，这是由封锁管理器来实现的。封锁管理器检查该封锁单元是否已上锁。事务结束时，解除全部封锁。图9.2表示一旦完成对一个数据项的存取，封锁管理器就释放对数据项的封锁。图9.22PL的形态图9.3严格的两阶段封锁图严格的两阶段封锁管理需要对算法9.1略作修改。算法9.2 严格的两阶段封锁LM算法。
基于封锁的并发控制的主要思想是，保证冲突操作共享的数据一次只能由一个操作存取。这是通过将锁和封锁单元（记作LU）捆绑在一起来实现的。这个锁由事务在其存取数据前设置，用完后释放。封锁单元如果已经被一个操作封锁，那么另一个操作就不能访问。这样，一个事务的封锁请求只能在没有其他事务拥有相关封锁的情况下才允许。封锁单元可以是一个数据库、一个关系、一条记录或一个字段。为了简化，我们统称为封锁单元或数据项。
因为我们讨论冲突事务的冲突操作的同步，所以可以区分两类封锁（或称两类封锁模式）：读锁（read lock（rl））和写锁（write lock（wl））。
如果有一个事务Ti希望读一个封锁单元（x）中的数据项，从而获得了x上的读锁，则记作rli（x）。如果同时发生写操作，也想封锁这个数据项，则记作wli（x）。这里就涉及一个封锁兼容性问题。如果允许两个事务对要存取的同一个数据项同时获得封锁，则这两个封锁模式是兼容的。否则，它们是不兼容的。表9.1所示的是一个封锁模式的兼容矩阵。
分布式DBMS不仅要管理封锁，也要处理事务的封锁管理响应。换言之，用户无需指定哪些数据应当封锁，分布式DBMS在每次事务发布读/写操作命令时都会自动关心这一点。
表9.1 封锁模式的兼容矩阵
在基于封锁的系统中，这是由封锁管理器（lock manager，LM）来实现的。事务管理器把数据操作（read或write）和相关信息（如存取的数据项和相关事务标识）传递给封锁管理器。封锁管理器检查该封锁单元是否已上锁。若已上锁，则检查现在申请的封锁和已加上的锁是否兼容，若不兼容，则将目前事务延迟，否则，按所需模式设置封锁。与此同时，数据操作传递给数据处理器实施实际的数据库存取。然后，事务管理器获悉其结果。事务的终止使得其强加的封锁被释放，在队列中等待存取该数据项的其他事务被启动。
下面是调度器（封锁管理器（LM））的一个基本算法。
算法9.1 基本LM。
算法9.1还不能同步执行事务。这是因为，为了产生同步调度，必须协调事务的加锁和解锁操作，而这里还没有相应的协调机制。下面用例子来说明。
【例9.5】 我们来看如下两个事务。为了方便说明，用一张表来表示。
下面是一个由封锁管理器使用算法9.1对这两个事务生成的有效调度：
S=［wl1（x），r1（x），w1（x），lr1（x），wl2（x），r2（x），w2（x），lr2（x），wl2（y），r2（y），
w2（y），lr2（y），C2，wl1（y），r1（y），w1（y），lr1（y），C1］
其中：wl表示写封锁操作，wl1（x）表示T1对数据项x的写封锁操作；lri（z）表示释放事务Ti拥有的对数据项z的封锁。注意，这里的S不是一个可串行化调度。S的等价调度可以表示为T1→T 2→T 1，不是可串行化的。对x而言，T 1→T 2；对y而言，T 2→T 1。
这样一个调度会造成数据混乱，例如，如果在执行这些事务前，x和y的值分别是50和20，如果T1在T2前执行，则其结果的值分别是102和38，反之则为101和39。而上述调度执行的结果是102和39。显然S不是可串行化的。
例9.5的问题是：这个封锁算法里，一个事务（Ti）在其执行完相关数据库命令（读或写）后就释放了封锁，因为它不再需要访问这个封锁单元（x）了。但是，事务在其释放对x的封锁后本身还拥有对其他数据项（y）的封锁。为此我们需要一个更严格的封锁协议，以保证隔离性和原子性。这样就引出了两阶段封锁（two-phase locking，2PL）。
这个协议的原则可以简述如下。
●欲存取的数据应先封锁。
●对事务已经占有的封锁，不得重复申请。
●一个事务必须注意到其他事务所做的封锁。
在2PL里，每个事务按照时间进程分为两个阶段：发育期和蜕缩期。发育期事务申请封锁，蜕缩期事务解除封锁，在蜕缩期不允许该事务申请新封锁。事务结束时，解除全部封锁。2PL的形态如图9.2所示。
图9.2表示一旦完成对一个数据项的存取，封锁管理器就释放对数据项的封锁。这样，其他正在等待数据项的事务就可以获得对数据项的封锁，从而增加了并发度。但是，困难的是封锁管理器必须知道事务已经获得它要的所有封锁，不会再申请对新的数据项封锁。封锁管理器也知道该事务不再需要使用目前计划释放封锁的数据项，所以可以释放它。最后如果在它释放封锁以后，该事务夭折，而其他事务已经使用它释放封锁的那个数据项，那些事务也必须夭折，这样就造成级联退出（cascading abort）。由于这些问题，大多数2PL调度器实现严格的两阶段封锁（strict two-phase locking），直到事务终止（commit或abort）才释放所有封锁，如图9.3所示。
图9.2 2PL的形态
图9.3 严格的两阶段封锁图
严格的两阶段封锁管理需要对算法9.1略作修改。主要修改来自数据处理器的响应。要保证在操作完成后、事务结束时再释放封锁。
下面是严格的两阶段封锁LM算法描述。
算法9.2 严格的两阶段封锁LM算法。(www.chuimin.cn)
严格的两阶段封锁相应的事务管理器（TM）的算法如下所示。
算法9.3 严格的两阶段封锁的TM算法。
这里我们通过2PL给操作强加了一个冲突可串行化序。但要指出的是，并非所有的可串行化调度都符合2PL，例如，S=［w1（x），r2（x），r3（y），w1（y）］是可串行化的（等价于T 1→T2→T3），但在2PL中是不允许的。所以，2PL比可串行化更严格。换言之，2PL是并发事务正确执行的充分条件，而非必要条件。为此，学术界提出了很多变异算法，可以解决上述2PL算法的不足，以提高并发度。
1.集中式2PL
我们可以选择一个节点来实施封锁管理，即只在一个节点设置封锁管理器，其他节点的事务管理器与它进行通信。
集中式2PL的通信结构如图9.4所示。这个算法称为集中式2PL（记作C2PL）。我们将事务启动节点的事务管理器称为协调方TM（coordinator TM），选一个节点作为集中节点，并设置一个封锁管理器，以及还有本节点和其他参与节点的数据处理器（DP），通信就在它们之间展开。
图9.4 集中式2PL的通信结构
下面就是一个集中式2PL的事务管理器（TM）（C2PL-TM）的工作算法。
算法9.4 C2PL-TM。
集中式2PL的封锁管理器（LM）算法如下。
算法9.5 C2PL-LM。
C2PL算法是存在的一个瓶颈，即集中节点处是一个瓶颈口。更进一步，问题发生在可靠性上，如果这个集中节点出现故障，系统就会出现问题。学术界对此有较多的研究。
2.主本2PL
主本2PL（primary copy 2PL，PC2PL）是一种在多副本系统中直接使用集中式2PL的方法。本质上，这种方法在多个节点上实现封锁管理器（LM），每个LM负责管理指定的封锁单元集。事务管理器则把它们的封锁/解锁请求发送给封锁管理器，后者负责响应对应于特定的封锁单元。整个算法将一个数据项版本看作为主本。
主本2PL算法与集中式2PL的区别不大。主本2PL起源于INGRES的分布版本。
3.分布式2PL
分布式2PL（简称D2PL）试图让每个节点的封锁管理器都分担一些任务。如果数据库无副本，则分布式2PL与原本2PL相似。如果数据有副本，则使用ROWA副本管理控制。
与C2PL-TM相比，分布式2PL事务管理算法有两个区别：第一个区别是，在C2PL-TM中，消息是发送给集中节点的封锁管理器；而在D2PL-TM中则是发送给所有参与节点的封锁管理器。第二个区别是，操作不是由协调事务管理器而是由参与者的封锁管理器传递给数据处理器的。这意味着协调事务管理器不必等待“lock request granted”消息。参与方数据处理器发送“操作结束”消息给协调方TM。一种替代方法是每个DP把消息发送给自己的封锁管理器，它可以释放封锁并把消息传递给协调方TM。分布式2PL算法应用在System R*和NonStop SQL中。分布式2PL的通信结构如图9.5所示。
图9.5 分布式2PL的通信结构
有关分布式数据库技术的文章
- 详细阅读
-
时标并发控制算法-分布式数据库技术详细阅读
不像基于封锁的算法，基于时标的并发控制算法不通过互相排斥来维持可串行化。这里，唯一性是时标的第一个性质。协调事务管理器为每个事务指定时标，确定每个数据项存放的节点，并向这些节点发送执行相关操作的命令。下面的算法称为基本时标序事务管理算法，记作BTO-TM。严格2PL算法要求封锁必须推迟到事务的提交或夭折才释放，同样也可以给出一个严格的TO算法。......
2023-10-28
-
乐观并发控制算法-分布式数据库技术应用案例详细阅读
前面讨论的并发控制算法都是悲观算法。反之，夭折该事务，并重新启动它。图9.7乐观事务的执行阶段可以设计一个基于封锁的乐观并发控制算法。不过原始乐观建议是基于时标序的。论文提出，事务冲突并不很频繁时，乐观算法的性能优于封锁算法的性能。乐观算法的一个主要缺点是存储开销较大。为了能够验证，乐观机制必须存储其他已终止事务的读集和写集。然而，减少了并发度，因为这仅让一个事务运行。......
2023-10-28
-
分布式数据库技术：多版本并发控制和快照隔离详细阅读
在多版本并发控制方法中经常采用异地更新技术，即不是直接在旧数据项上修改，而是先创建一个数据项的新版本，然后让新版本取代旧版本。使用MVCC的好处是，读请求不会因为存在写操作而被阻塞。数据库中的只读访问常常检索的是已被提交的数据项版本。系统的开销主要发生在相同数据项的多个版本上。有一种称为快照隔离的技术用于实现支持MVCC的数据库。SI的开销虽然小，但弱化了可串行化。SI包含以下两个重要性质。......
2023-10-28
- 详细阅读
-
控制算法的解析与运行-现场总线与应用技术详细阅读
在上位机将控制算法传输到控制卡后，控制卡会将控制算法信息暂存到控制算法缓冲区，并不会立即对控制算法进行解析。所以，控制算法的解析必须选择合适的时机。本系统中将控制算法的解析操作放在本周期的控制算法运算结束后执行，这样不会对本周期内的控制算法运行产生影响，新的控制算法将在下一周期得到执行。上位机下发给控制卡的控制算法包含控制算法的操作信息、回路信息和回路中各功能模块信息。......
2023-11-22
-
优化分布查询算法-分布式数据库技术详细阅读
表7.8分布查询优化算法比较①统计内容分别为：1=关系的基，2=每个属性的不同值个数，3=连接选择系数，4=每个连接属性上投影的大小，5=属性大小和元组大小。......
2023-10-28
-
分布式数据库的可串行化理论及并发控制详细阅读
分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。可串行化是涉及并发控制的一个重要理论。条件1表示调度涉及的域是一个由各个事务构成的集合。例9.2所示的是一个串行调度。下面我们讨论可串行化的问题。定义9.3 一个调度Sc是可串行的，当且仅当Sc冲突等价于一个串行调度，这种可串行化通常称为冲突等价可串......
2023-10-28
相关推荐