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

并发控制技术确保多个事务同时执行，同时保持事务的 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_i 已经提交之后，T_j 才能开始提交。

分布式系统中的并发控制

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

分布式两阶段锁定算法

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

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

• 集中两相锁定 − 在这种方法中，一个站点被指定为中央锁管理器。 环境中的所有站点都知道中央锁管理器的位置，并在事务期间从中获取锁。

• 主副本两阶段锁定 − 在这种方法中，许多站点被指定为锁控制中心。 每个站点都有责任管理一组定义的锁。 所有站点都知道哪个锁控制中心负责管理哪个数据表/分片项的锁。

• 分布式两阶段锁定 − 在这种方法中，存在多个锁管理器，其中每个锁管理器控制存储在其本地站点的数据项的锁。 锁管理器的位置基于数据分布和复制。

分布式时间戳并发控制

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

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

冲突图

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

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

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

分布式乐观并发控制算法

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

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

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