分布式数据库管理系统 - 并发控制

并发控制技术确保多个事务可以同时执行，同时保持事务的ACID特性和调度中的可串行化。

在本章中，我们将学习并发控制的各种方法。

基于锁的并发控制协议

基于锁的并发控制协议使用数据项锁定概念。锁是与数据项关联的变量，它决定是否可以对该数据项执行读/写操作。通常，使用锁兼容性矩阵来确定两个事务是否可以同时锁定一个数据项。

基于锁的并发控制系统可以使用单相或两相锁定协议。

在这种方法中，每个事务在使用数据项之前对其进行锁定，并在使用完后立即释放锁。这种锁定方法提供了最大并发性，但并不总是强制执行可串行化。

在这种方法中，所有锁定操作都先于第一个锁释放或解锁操作。事务包括两个阶段。在第一阶段，事务仅获取它所需的所有锁，并且不释放任何锁。这称为扩展或增长阶段。在第二阶段，事务释放锁，并且不能请求任何新锁。这称为收缩阶段。

遵循两阶段锁定协议的每个事务都保证是可串行化的。但是，这种方法在两个冲突事务之间提供了较低的并行性。

基于时间戳的并发控制算法使用事务的时间戳来协调对数据项的并发访问，以确保可串行化。时间戳是由DBMS赋予事务的唯一标识符，表示事务的开始时间。

这些算法确保事务按照其时间戳指定的顺序提交。较旧的事务应该在较新的事务之前提交，因为较旧的事务比较新的事务先进入系统。

基于时间戳的并发控制技术生成可串行化的调度，使得等效的串行调度按照参与事务的年龄排序。

一些基于时间戳的并发控制算法包括：

基于时间戳的排序遵循三个规则来强制执行可串行化：

在冲突率较低的系统中，验证每个事务的可串行性的任务可能会降低性能。在这些情况下，可串行性测试被推迟到提交之前。由于冲突率较低，因此中止不可串行化事务的概率也较低。这种方法称为乐观并发控制技术。

在这种方法中，事务的生命周期分为以下三个阶段：

该算法使用三个规则在验证阶段强制执行可串行化：

规则1 - 给定两个事务T_i和T_j，如果T_i正在读取T_j正在写入的数据项，则T_i的执行阶段不能与T_j的提交阶段重叠。T_j只有在T_i完成执行后才能提交。

规则2 - 给定两个事务T_i和T_j，如果T_i正在写入T_j正在读取的数据项，则T_i的提交阶段不能与T_j的执行阶段重叠。T_j只有在T_i已提交后才能开始执行。

规则3 - 给定两个事务T_i和T_j，如果T_i正在写入T_j也正在写入的数据项，则T_i的提交阶段不能与T_j的提交阶段重叠。T_j只有在T_i已提交后才能开始提交。

在本节中，我们将了解如何在分布式数据库系统中实现上述技术。

分布式两阶段锁定的基本原理与基本两阶段锁定协议相同。但是，在分布式系统中，有一些站点被指定为锁管理器。锁管理器控制来自事务监视器的锁获取请求。为了在各个站点的锁管理器之间强制协调，至少有一个站点被授权查看所有事务并检测锁冲突。

根据可以检测锁冲突的站点数量，分布式两阶段锁定方法可以分为三种类型：

集中式两阶段锁定 - 在这种方法中，一个站点被指定为中央锁管理器。环境中的所有站点都知道中央锁管理器的地址，并在事务期间从其获取锁。
主副本两阶段锁定 - 在这种方法中，一些站点被指定为锁控制中心。每个站点负责管理一组定义的锁。所有站点都知道哪个锁控制中心负责管理哪个数据表/片段项的锁。
分布式两阶段锁定 - 在这种方法中，有多个锁管理器，其中每个锁管理器控制存储在其本地站点的数据项的锁。锁管理器的地址基于数据分布和复制。

在集中式系统中，任何事务的时间戳由物理时钟读数确定。但是，在分布式系统中，任何站点的本地物理/逻辑时钟读数都不能用作全局时间戳，因为它们不是全局唯一的。因此，时间戳由站点ID和该站点的时钟读数组合而成。

为了实现时间戳排序算法，每个站点都有一个调度程序，该调度程序为每个事务管理器维护一个单独的队列。在事务期间，事务管理器向站点的调度程序发送锁请求。调度程序将请求按时间戳递增的顺序放入相应的队列。请求按队列顺序从队列的前面处理，即最旧的请求优先。

另一种方法是创建冲突图。为此，定义了事务类。事务类包含两个数据项集，称为读取集和写入集。如果事务的读取集是类读取集的子集，并且事务的写入集是类写入集的子集，则事务属于特定类。在读取阶段，每个事务都会发出其读取集中的数据项的读取请求。在写入阶段，每个事务都会发出其写入请求。

为活动事务所属的类创建冲突图。它包含一组垂直、水平和对角线边。垂直边连接类内的两个节点，表示类内的冲突。水平边连接两个类的两个节点，表示不同类之间的写写冲突。对角线边连接两个类的两个节点，表示两个类之间的写读或读写冲突。

分析冲突图以确定同一类或两个不同类中的两个事务是否可以并行运行。

分布式乐观并发控制算法扩展了乐观并发控制算法。对于此扩展，应用了两个规则：

规则1 - 根据此规则，事务必须在执行时在所有站点本地进行验证。如果发现任何站点上的事务无效，则将其中止。本地验证保证事务在已执行的站点上保持可串行化。在事务通过本地验证测试后，将进行全局验证。

规则2 - 根据此规则，在事务通过本地验证测试后，应进行全局验证。全局验证确保如果两个冲突事务在多个站点一起运行，则它们应在所有一起运行的站点的相同相对顺序中提交。这可能需要事务在验证后等待另一个冲突事务，然后才能提交。此要求使算法不太乐观，因为事务可能无法在某个站点验证后立即提交。

打印页面