分布式 DBMS - 控制并发

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

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

基于锁定的并发控制协议

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

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

在此方法中，每个事务在使用前锁定一个项目，并在使用完毕后立即释放锁定。此锁定方法提供最大并发性，但并不总是强制可串行化。

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

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

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

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

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

一些基于时间戳的并发控制算法是 -

基于时间戳的排序遵循三个规则来强制可序列化 -

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

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

该算法使用三个规则来在验证阶段强制执行可序列化 -

规则 1 - 给定两个事务 Ti_和T _j，如果 Ti_{正在读取 T}_j正在写入的数据项_，则 Ti的执行阶段不能与 T _j的提交阶段重叠。T _{j只有在 T}_i执行完毕后才能提交。

规则 2 - 给定两个事务 Ti_和T _j，如果 Ti_{正在写入 T}_j正在读取的数据项，则 Ti_的提交阶段不能与 T _j的执行阶段重叠。T _{j仅在 T}_i提交后才能开始执行。

规则 3 - 给定两个事务 Ti_和T _j，如果 Ti_{正在写入 T}_j也在写入的数据项，则_Ti的提交阶段不能与 T _j的提交阶段重叠。_{只有在 T i}已经提交之后， T _j才能开始提交。

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

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

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

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

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

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

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

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

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

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

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

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