主内存数据库系统设计/并发
目录 —
第 8 章：并发管理
并发是指多个进程和线程能够同时访问和更改数据记录的能力。随着更多用户的参与，对访问和修改数据的争用降低，并发性越好，反之亦然。访问数据的进程会阻止其他进程更改数据。这会降低并发性。修改数据的进程会阻止其他进程访问或更改数据。这会降低并发性。
一般来说，数据库系统使用两种方法来管理并发数据访问：悲观和乐观。这两种模型都无法避免冲突，区别仅在于处理冲突的时间。
悲观并发系统假设会发生冲突，并通过获取正在读取或修改的数据的锁来避免冲突，这样其他进程就无法修改该数据。在这个模型中，读取器会阻塞写入器，写入器也会阻塞读取器。
乐观并发系统假设事务不太可能修改另一个事务正在修改的数据。这是通过使用版本控制技术实现的。这允许读取器在修改发生之前看到数据的状态，因为系统在实际尝试更改数据记录之前会维护数据记录的先前版本。在这个模型中，读取器不会阻塞写入器，写入器也不会阻塞读取器。但是，写入器会阻塞写入，这会导致冲突。
任何并发控制机制都必须解决一些问题。有三种方式会导致错误。分别是丢失更新问题、未提交依赖和不一致分析。在这三种情况下，单个事务都是正确的，但当它们交错时可能会产生错误的结果。
TODO- 定义这个
TODO- 绘制图表
事务-1 在时间 t1 读取元组 1 事务-2 在时间 t2 读取元组 1 事务-1 在时间 t3 更新元组 1 事务-2 在时间 t4 更新元组 1
事务-1 在时间 t3 对元组 1 的更新丢失了，因为事务-2 在没有检查元组 1 是否已更改的情况下，覆盖了事务-1 对元组 1 的更新。
当一个事务被允许访问或更新另一个事务已更新但尚未提交的元组时，就会发生这种情况。
TODO- 绘制图表
事务-1 在时间 t1 更新元组 1 事务-2 在时间 t2 读取元组 1 事务-1 在时间 t3 回滚事务 在上面的序列中，事务-2 在时间 t2 看到一个未提交的更改，该更改在时间 t3 被撤销。事务-2 使用在时间 t2 看到的值进行操作。结果，事务-2 可能会产生不正确的结果。
如果事务-2 在 t2 更新元组 t1 而不是读取它，情况会更糟，它将失去对元组 t1 的更新，一旦事务-1 回滚。
如果一个事务正在计算对记录的聚合汇总函数，而其他事务正在更新汇总中涉及的某些记录，那么聚合函数可能会使用更新之前的某些值和更新之后的某些值进行计算。
TODO- 绘制图表
例如，假设事务-1 正在计算特定日期所有影院的预订总数；与此同时，事务-2 正在预订当天 5 个座位，那么事务-1 的结果将减少 5 个，因为事务-1 在从 X 中减去 5 个座位之后读取 X 的值。
以上所有三个问题都可以通过使用称为锁定的并发控制技术来解决。基本思想是在事务正在处理数据记录时，拒绝所有事务访问该数据记录。
锁是一个与数据项关联的变量，它描述了数据项的状态。通常，在 DBMS 中每个数据项（记录）都有一个锁。锁用于通过并发事务同步访问数据项。Unix 类操作系统支持两种类型的锁
- pthread 互斥体
- 信号量
pthread 互斥锁在多线程环境中运行良好，信号量在多线程和多进程环境中也运行良好。pthread 互斥锁被称为二元锁，因为它们只有两种状态（lockState）：锁定和解锁。信号量可以用于二元锁以及计数锁。在我们的案例中，二元锁将用于提供对数据项的同步并发访问。使用二元锁定有两个操作：lockItem() 和 unlockItem()。一个事务通过首先发出 lockItem(X) 操作来请求访问数据项 X。如果 lockState(X) 为 1，则事务将被迫等待，直到 lockState(X) 变为 0。如果它为零，则 lockState(X) 设置为 1，并且允许事务访问数据项 X。当事务完成使用数据项时，它将发出 unlockItem(X) 操作，该操作将 lockState(X) 设置为零，以便其他事务可以访问 X。
锁定方法的数据访问协议是
- 读取事务将在读取数据之前获取对数据的锁定。
- 写入事务将在写入数据之前获取对数据的锁定。
- 如果锁定请求被拒绝，则事务进入等待状态，并定期尝试获取锁定，直到获取锁定的事务释放锁定。
在上述锁定模型中，
- 读取器阻塞读取器和写入器
- 写入器阻塞读取器和写入器
通过使读取器不阻塞其他读取器来稍微提高上述模型的并发性，因为这不会导致任何不一致。这可以通过引入另一种类型的锁来实现，这种锁将由所有读取器共享。这些锁被称为共享锁。另一种类型的锁，排他锁，由写入器获取，以阻止所有读取器和写入器访问数据。此锁定方法的数据访问协议是
- 读取事务将在读取数据之前获取对数据的共享锁。
- 写入事务将在写入数据之前获取对数据的排他锁。
- 如果另一个事务对数据项拥有排他锁，则读取操作的锁定请求将被拒绝。
- 如果另一个事务对数据项拥有读取锁或排他锁，则写入操作的锁定请求将被拒绝。
- 如果锁定请求被拒绝，则事务进入等待状态，并定期尝试获取锁定，直到获取锁定的事务释放锁定。
在上述锁定模型中，
- 读取器阻塞写入器并允许其他读取器
- 写入器阻塞读取器和写入器
上述规则应概括为锁定兼容性矩阵
共享 排他 无锁 共享 是 否 是 排他 否 否 是 否 锁 是 是 是 TODO::上述锁定兼容性矩阵以图像形式显示
是 -> 兼容，无冲突，锁定请求将被授予。
否 -> 不兼容，存在冲突，因此应拒绝锁定请求。
锁定协议的并发问题
- 丢失更新问题– 事务 1 从时间 t3 开始无限期地等待排他锁，因为共享锁由事务 1 和事务 2 获取。事务 2 从时间 t4 开始无限期地等待排他锁，因为共享锁由事务 1 和事务 2 获取。我们的丢失更新问题已解决，但出现了一个新问题。它被称为“死锁”。我们将在后面详细介绍它。
- 未提交依赖- 事务 2 在时间 t2 尝试读取元组 1 时等待锁定，因为它被事务 1 独占锁定。它将等待，直到事务 1 提交或回滚。锁定避免了未提交依赖问题。
- 不一致分析– 事务 1 等待，直到事务 2 释放对数据记录 X 的排他锁，然后计算聚合，从而给出正确的结果。
8.3.1 可序列化事务
[edit | edit source]如果一组给定的事务产生与这些事务按顺序逐个执行时相同的结果，则该组事务被认为是可序列化的。
- 单个事务是正确的，因为它们将数据库的正确状态转换为另一个正确状态
- 按任何顺序一次执行一个事务也是正确的，因为单个事务彼此独立。
- 如果交织执行等效于串行执行或可序列化，则它是正确的。
可序列化概念首先由 Eswaran 提出，Gray 证明了二阶段锁定协议，该协议简要描述如下
If all transactions obey the “two-phase locking protocol”, then all possible interleaved schedules are serializable.
8.3.2 二阶段锁定协议
[edit | edit source]在释放锁定后，事务永远不能继续获取更多锁定。遵守此协议的事务因此有两个阶段，一个锁定获取或“增长”阶段和一个锁定释放或“收缩”阶段。
二阶段锁定可能会限制调度中可能发生的并发量。这是因为事务可能无法在完成数据项后释放对该数据项的锁定。这是为了保证所有调度的可序列化而不必检查调度本身而付出的代价。
二阶段锁定 (2PL) 有许多变体。我们上面描述的技术被称为 2 阶段锁定。
8.3.2.1 保守型 2PL
[edit | edit source]这要求事务在事务开始之前锁定它访问的所有项目，方法是声明读取集和写入集。事务的读取集是事务读取的所有项目的集合，写入集是它写入的所有项目的集合。
如果读取集或写入集中的任何项目无法锁定，它将等待其他事务释放它，并在一次获取所有锁定后，它将启动事务。保守型 2 阶段锁定是一种无死锁协议。但是，由于需要声明读取集和写入集，因此在实践中很难使用，这在大多数情况下实际上是不可能的。
在保守型 2 阶段锁定的情况下，增长阶段在事务开始之前，收缩阶段在事务结束时开始。
8.3.2.2 严格型 2PL
[edit | edit source]2 阶段锁定的最流行变体是严格型 2 阶段锁定。事务在事务提交或回滚之前不会释放任何排他锁。这保证了严格的调度，因为在事务提交之前，没有其他事务可以读取或写入该事务写入的项目。增长阶段在事务开始时开始，写入锁的收缩阶段在事务提交或回滚时发生。
8.3.2.3 严格型 2PL
[edit | edit source]这是严格型 2 阶段锁定协议的更严格版本。事务在事务提交或回滚之前不会释放任何共享锁和排他锁。这是最容易实现的 2 阶段锁定，但会降低读取的并发性。
增长阶段在事务开始时开始，收缩阶段在事务提交或回滚时发生。
8.3.3 锁定饥饿
[edit | edit source]当事务在无限期的时间内无法继续进行，而系统中的其他事务继续正常运行时，就会发生锁定饥饿。这可能是由于不公平的锁定调度算法导致的，该算法实现了基于优先级的锁定。解决饥饿问题的一个方法是采用公平的锁定等待方案，例如先进先出 (FIFO) 队列。
当死锁算法反复选择相同的事务进行中止时，也会发生饥饿，从而永远不会允许它完成。应修改算法以对已中止多次的事务使用更高优先级，以避免此问题。
8.3.4 死锁
[edit | edit source]当一组两个或多个事务中的每个事务都等待由该组中的另一个事务锁定的某个资源时，就会发生死锁。
例如，事务 T1 获取资源 R1，事务 T2 获取资源 R2。在此之后，如果 T1 等待 R2，而 T2 等待 R1。两者都永远不会获得锁定，这种情况被称为死锁。
TODO 关于时间的图表
8.3.4.1 死锁预防
[edit | edit source]有许多预防协议，但大多数协议在 DBMS 的情况下实际上不可行。它们是保守型 2 阶段锁定、数据记录锁定排序、无等待、谨慎等待、等待-死亡和伤亡-等待。
保守型二阶段锁定协议是一种死锁预防协议，其中所有锁定都在事务对数据记录进行操作之前获取。
数据记录锁定排序也将防止死锁。在多个数据记录上进行操作的事务应始终按预定的顺序获取锁定。这需要程序员或 DBMS 了解所选数据记录锁定的顺序。这在数据库系统中也不切实际。
无等待算法如果事务无法获得锁，它将立即中止，并在经过一定时间延迟后重新启动，而不会检查是否实际发生了死锁。这会导致事务不必要地中止和重启。谨慎等待算法
为了避免在没有等待算法的情况下不必要的重启，如果事务 T1 试图锁定数据记录 R1，但由于 R1 被另一个事务 T2 以冲突锁锁定而无法做到。如果 T2 没有被其他锁定数据记录阻塞，那么 T1 将被阻塞并允许等待；否则中止 T1。
等待-死亡和伤亡-等待算法其他两种技术，等待-死亡和伤亡-等待，使用事务时间戳作为基础来确定在发生死锁的情况下该做什么。事务时间戳是分配给每个事务的唯一标识符。这些时间戳通常是运行计数器，在每个开始的事务都会递增。如果事务 T1 在事务 T2 之前开始，那么 TS(T1) < TS(T2)
假设事务 T1 试图锁定数据记录 R1，但由于 R1 被另一个事务 T2 以冲突锁锁定而无法锁定。这些方案遵循的规则如下
等待-死亡 - 如果 TS (T1) < TS (T2)，则允许 T1 等待，否则中止 T1 并稍后以相同的时间戳重新启动它。伤亡-等待 - 如果 TS (T1) < TS (T2)，则中止 T1 并稍后以相同的时间戳重新启动它；否则允许 T1 等待
在等待-死亡中，允许较旧的事务等待较年轻的事务，而较年轻的事务请求锁定被较旧的事务持有的记录 R1 将被中止并重新启动。伤亡-等待方法则相反；允许较年轻的事务等待较旧的事务，而较旧的事务请求锁定被较年轻的事务持有的记录 R1 会通过中止较年轻的事务来抢占它。两种方案最终都会中止可能参与死锁的两个事务中较年轻的那个。在等待-死亡中，事务只等待较年轻的事务。在伤亡-等待中，事务只等待较旧的事务。因此在这两种方案中都不会产生循环，避免死锁。
死锁检测比死锁预防技术更实用。这首先检查系统中是否实际存在死锁状态，然后再采取任何措施。
检测死锁状态的一种简单方法是让系统构建和维护一个“等待-for”图TODO-图和说明
如果系统处于死锁状态，则必须中止导致死锁的一些事务。应用程序或 DBMS 应该选择参与死锁的事务之一进行回滚以使系统摆脱死锁情况。此选择算法应考虑避免运行时间过长的事务和执行过多次更新的事务。最适合中止的事务是 SELECT 或只读事务。
处理死锁的最简单解决方案是超时。在这种方法中，等待时间超过系统定义的超时时间的事务被认为处于死锁状态，并被中止。
TODO
数据项的大小通常称为数据项粒度。细粒度是指数据项大小小，而粗粒度是指数据项大小大。
数据项大小越大，并发度越低。例如，如果数据项大小是表示为 Table1 的“表”，则需要锁定记录 X 的事务 T1 必须锁定包含记录 X 的整个表 Table1，因为锁与整个数据项 Table1 相关联。如果另一个事务 T2 想要锁定 Table1 的另一个记录 Y，它将被迫等待 T1 释放对 Table1 的锁定。如果数据项大小是单个记录，那么事务 T2 就可以继续执行，因为它会锁定不同的数据项。
数据项大小越小，数据库中项目数量越多。因为每个项目都与一个锁相关联，所以系统将拥有更多活动锁。将执行更多锁和解锁操作，导致更高的开销。此外，存储这些锁需要更多存储空间。
对于访问许多记录的大型事务，应该使用粗粒度；对于访问少量记录的小型事务，应该使用细粒度。
粒度级别按从粗到细的顺序列出如下
- 数据库
- 表
- 磁盘块或内存页
- 记录
- 记录字段
由于最佳粒度大小取决于给定的事务，因此 DBMS 应该支持多个级别，以便事务能够选择任何它想要的级别。
让我们以一个包含一个表 Table1 的示例数据库 DB1 为例，Table1 包含 2 个页面 P1 和 P2。P1 有 10 个记录 R1 到 R10，P2 有 10 个记录 R11 到 R20。
TODO::绘制树结构表示上述内容。
场景 1
事务 T1 想要更新 Table1 中的所有记录。它将请求对 Table1 进行排他锁定。这对 T1 来说比为每个数据记录获取 20 个锁更有益。现在假设，另一个事务 T2 想要从页面 P1 读取记录 R5，那么 T2 将请求对 R5 进行共享记录级锁定。现在 DBMS 将检查所请求的锁与已持有的锁的兼容性。验证此问题的一种方法是遍历从叶子节点 R5 到根节点 DB1 的树，并检查冲突锁。
场景 2
事务 T1 想要从页面 P1 读取记录 R5，然后 T2 将请求对 R5 进行共享记录级锁定。现在假设，另一个事务 T2 想要更新 Table1 中的所有记录，因此它将请求对 Table1 进行排他锁定。现在 DBMS 将检查所请求的锁与已持有的锁的兼容性。为此，它需要检查页面级和记录级的所有锁，以确保没有冲突锁。
对于上述两种场景，基于遍历的锁冲突检测效率非常低，会破坏拥有多个粒度锁定的目的。
引入了新型锁以提高多个粒度锁定的效率。意图锁背后的理念是让事务沿从根节点到所需节点的路径指示它将在其中一个节点的后代节点上需要哪种类型的锁。
有三种类型的意图锁。
- 意图共享 (IS)
- 意图排他 (IX)
- 共享意图排他 (SIX)
意图-共享锁
指示将对某个后代节点请求共享锁
意图-排他锁
指示将对某个后代节点请求排他锁
意图-共享锁
指示该节点处于共享模式锁定，并且将对某个后代节点请求排他锁
兼容性表
模式 IS IX S SIX X IS 是 是 是 是 否 IX 是 是 否 否 否 S 是 否 是 否 否 SIX 是 否 否 否 否 X 否 否 否 否 否
TODO::上述锁兼容性表的图表
锁定协议
- 必须首先锁定树的根节点
- 只有当父节点已经被事务以 IS 或 IX 模式锁定时，事务才能以 S 或 IS 模式锁定节点
- 只有当节点的父节点已经被事务以 IX 或 SIX 模式锁定时，事务才能以 X、IX 或 SIX 模式锁定节点
- 只有当节点的任何子节点都没有被事务当前锁定时，事务才能解锁节点。
- 应遵守锁兼容性和两阶段锁定。
TODO::说明上述协议和兼容性表的示例：参考 Elmasri 的 445
解决幻像记录问题的一种解决方案是使用索引锁定。
一种更通用的技术，称为谓词锁定，将锁定对满足谓词或条件的所有记录的访问。事实证明，谓词锁很难有效地实现。
还有另一种基于时间戳排序的并发控制技术，它避免了锁的使用。由于它避免了锁，因此在这种并发控制机制中不会发生死锁。
时间戳是由DBMS创建的唯一标识符，用于识别事务。通常，时间戳值是按照事务提交到系统的顺序分配的。通常它是事务开始时间，称为TS（T）。这些唯一的标识符应该使用简单的计数器来实现，当事务开始时计数器会递增。由于它有有限的最大值，算法应该注意在达到最大值时将其重置。
每个数据项X都有两个时间戳
- ReadTS(X) – 数据项X的读取时间戳；这是所有成功读取数据项X的事务的时间戳中的最大值。
- WriteTS(X) – 数据项X的写入时间戳；这是所有成功修改数据项X的事务的时间戳中的最大值。
当某个事务T尝试发出readItem(X)或writeItem(X)时，算法应该将T的时间戳与ReadTS(X)和WriteTS(X)进行比较，以确保事务执行的时间戳顺序没有被违反。如果该顺序被违反，则事务T将被中止，并作为新事务重新提交到系统，并分配一个新的时间戳。如果T被中止，则任何可能使用T写入的值的事务T1也必须中止。同样，任何可能使用T1写入的值的事务T2也必须中止，依此类推。这种效应被称为级联回滚，是与这种方案相关联的最大问题之一。
基本时间戳排序算法总结如下
事务T发出writeItem(X)操作如果readTS(X) > TS(T)或writeTS(T) > TS(T)，则中止T，否则执行T的writeItem(X)并将writeTS(X)设置为TS(T)
事务T发出readItem(X)操作如果writeTS(T) > TS(T)，则中止T，否则执行T的readItem(X)并将readTS(X)设置为TS(T)和当前readTS(X)中的最大值
每当基本时间戳排序算法检测到两个冲突操作以不正确的顺序发生时，它会通过中止发出该操作的事务来拒绝后面的操作。该算法产生的调度保证是冲突可串行化的，就像两阶段锁定协议一样。
严格时间戳排序是基本时间戳排序的一种变体，它确保调度是可恢复的和冲突可串行化的。在这个变体中，一个发出readItem(X)或writeItem(X)的操作且TS(T) > writeTS(X)的事务T，它的读或写操作会被延迟，直到写入X的值的事务T1提交或中止。为了实现这个算法，需要锁定。这个算法不会导致死锁，因为只有当TS(T) > TS(T1)时，T才会等待T1。
TODO::参考白皮书并添加更多内容
TODO
在锁定和时间戳排序这两种并发控制技术中，在事务对数据项进行操作之前都会进行一些检查。在锁定中，检查是用来确定要访问的项是否被锁定的。在时间戳排序中，事务时间戳会与数据项的读写时间戳进行比较。这给事务执行带来了开销。在乐观并发控制技术中，在事务执行过程中不会进行任何检查。在这种方案中，事务中的更新不会直接应用于数据项，直到事务结束。在事务执行过程中，所有更新都会应用于数据项的本地副本，这些副本以每个事务为基础保存。在事务执行结束时，验证阶段会检查事务的任何更新是否违反了可串行化。如果没有违反，则事务提交，数据库从本地副本更新，否则事务中止，然后稍后重新启动。该协议有三个阶段
- 读取阶段– 事务可以从数据库中读取已提交数据项的值。但是，更新只应用于保存在事务工作区中的数据项的本地副本。
- 验证阶段- 执行检查以确保如果事务更新被应用于数据库，则不会违反可串行化。
- 写入阶段– 如果验证阶段表明它是可串行化的，则事务更新被应用于数据库。否则，更新被丢弃，事务被重新启动。
这种协议非常适合事务之间对数据项的干扰很少的情况。如果干扰更多，则事务将经常被重新启动。这种技术被称为“乐观”，因为它们假设干扰很少发生，因此在事务执行期间不需要进行检查。
TODO::参考白皮书并添加更多内容
传统数据库系统中的并发控制旨在维护数据库的一致性。MMDB中的并发控制由于满足时间约束和维护数据一致性的冲突需求而变得困难。