分布式 DBMS - 死锁处理

本章概述了数据库系统中的死锁处理机制。我们将研究集中式和分布式数据库系统中的死锁处理机制。

什么是死锁？

死锁是具有两个或多个事务的数据库系统的一种状态，此时每个事务都在等待被其他事务锁定的数据项。死锁可以通过等待图中的循环来指示。这是一个有向图，其中顶点表示事务，边表示等待数据项。

例如，在下面的等待图中，事务 T1 正在等待被 T3 锁定的数据项 X。T3正在等待被T2锁定的Y，T2正在等待被T1锁定的Z。这样就形成了一个等待周期，任何事务都无法继续执行。

集中式系统中的死锁处理

死锁处理有三种经典方法，即 -

预防死锁。
避免死锁。
死锁检测和消除。

所有这三种方法都可以合并到集中式和分布式数据库系统中。

预防死锁

死锁预防方法不允许任何事务获取会导致死锁的锁。约定是，当多个事务请求锁定同一数据项时，只有其中一个事务被授予锁定。

最流行的死锁预防方法之一是预先获取所有锁。在此方法中，事务在开始执行之前获取所有锁，并在事务的整个持续时间内保留锁。如果另一个事务需要任何已获取的锁，则它必须等待，直到它需要的所有锁都可用。使用这种方法，可以防止系统陷入死锁，因为没有等待的事务持有任何锁。

避免死锁

死锁避免方法可以在死锁发生之前对其进行处理。它分析事务和锁以确定等待是否会导致死锁。

该方法可简述如下。事务开始执行并请求需要锁定的数据项。锁管理器检查锁是否可用。如果可用，锁管理器会分配该数据项，并且事务会获取锁。但是，如果该项目被其他事务以不兼容模式锁定，则锁管理器会运行一种算法来测试将该事务保持在等待状态是否会导致死锁。因此，该算法决定该事务是否可以等待或者应该中止其中一个事务。

有两种用于此目的的算法，即wait-die和Wound-wait。假设有两个事务 T1 和 T2，其中 T1 尝试锁定已被 T2 锁定的数据项。算法如下 -

Wait-Die - 如果 T1 早于 T2，则允许 T1 等待。否则，如果 T1 比 T2 年轻，则 T1 将中止并稍后重新启动。
Wound-Wait - 如果 T1 早于 T2，则 T2 将中止并稍后重新启动。否则，如果T1比T2年轻，则允许T1等待。

死锁检测和消除

死锁检测和消除方法定期运行死锁检测算法，并在出现死锁时消除死锁。当事务发出锁请求时，它不会检查死锁。当事务请求锁时，锁管理器检查它是否可用。如果可用，则允许事务锁定该数据项；否则交易被允许等待。

由于授予锁定请求时没有预防措施，某些事务可能会死锁。为了检测死锁，锁管理器定期检查等待图是否有循环。如果系统死锁，锁管理器会从每个周期中选择一个受害者事务。受害者被中止并回滚；然后稍后重新启动。用于选择受害者的一些方法是 -

选择最年轻的交易。
选择数据项最少的交易。
选择执行更新次数最少的事务。
选择重启开销最小的事务。
选择两个或多个周期共有的事务。

这种方法主要适用于事务量低且需要快速响应锁定请求的系统。

分布式系统中的死锁处理

分布式数据库系统中的事务处理也是分布式的，即同一个事务可能在多个地点进行处理。分布式数据库系统中两个主要的死锁处理问题是事务位置和事务控制，这两个问题在集中式系统中是不存在的。一旦解决了这些问题，就可以通过死锁预防、死锁避免或死锁检测和消除来处理死锁。

交易地点

分布式数据库系统中的事务在多个站点中处理并使用多个站点中的数据项。数据处理量在这些站点之间的分布并不均匀。处理的时间也各不相同。因此，同一事务可能在某些站点上处于活动状态，而在其他站点上则处于非活动状态。当站点中存在两个冲突的事务时，可能会发生其中一个事务处于非活动状态的情况。这种情况不会出现在集中式系统中。这种担忧称为交易地点问题。

菊花链模型可以解决这个问题。在此模型中，当一笔交易从一个站点移动到另一个站点时，它会携带某些详细信息。一些详细信息是所需的表列表、所需的站点列表、已访问的表和站点列表、尚未访问的表和站点列表以及已获取的锁类型列表。事务通过提交或中止而终止后，应将信息发送到所有相关站点。

交易控制

事务控制涉及指定和控制分布式数据库系统中处理事务所需的站点。关于选择在哪里处理交易以及如何指定控制中心有很多选择，例如 -

可以选择一台服务器作为控制中心。
控制中心可以从一台服务器转移到另一台服务器。
控制责任可以由多个服务器分担。

分布式死锁预防

就像集中式死锁预防一样，在分布式死锁预防方法中，事务应该在开始执行之前获取所有锁。这可以防止死锁。

交易进入的站点被指定为控制站点。控制站点向数据项所在站点发送消息以锁定数据项。然后等待确认。当所有站点都确认已锁定数据项时，事务开始。如果任何站点或通信链路出现故障，则交易必须等到它们修复后再进行。

虽然实现很简单，但这种方法有一些缺点 -

预获取锁需要较长时间的通信延迟。这增加了交易所需的时间。
如果站点或链接出现故障，事务必须等待很长时间才能使站点恢复。同时，在运行站点中，项目被锁定。这可能会阻止其他事务的执行。
如果控制站点出现故障，则无法与其他站点通信。这些站点继续将锁定的数据项保持在锁定状态，从而导致阻塞。

分布式死锁避免

与集中式系统一样，分布式死锁避免会在死锁发生之前对其进行处理。此外，在分布式系统中，需要解决事务位置和事务控制问题。由于交易的分布式性质，可能会发生以下冲突 -

同一站点中的两个事务之间存在冲突。
不同站点中的两个事务之间存在冲突。

如果发生冲突，其中一个事务可能会根据分布式等待芯片或分布式伤口等待算法而被中止或允许等待。

让我们假设有两个事务：T1 和 T2。T1 到达站点 P 并尝试锁定已被 T2 在该站点锁定的数据项。因此，站点 P 存在冲突。算法如下 -

分布式绕线模具
- 如果 T1 早于 T2，则允许 T1 等待。在站点 P 收到 T2 已在所有站点成功提交或中止的消息后，T1 可以恢复执行。
- 如果 T1 比 T2 年轻，则 T1 中止。站点 P 的并发控制向 T1 访问过的所有站点发送消息以中止 T1。当 T1 在所有站点中成功中止时，控制站点会通知用户。
分布式等待
- 如果 T1 早于 T2，则需要中止 T2。如果 T2 在站点 P 处于活动状态，则站点 P 会中止并回滚 T2，然后将此消息广播到其他相关站点。如果 T2 已离开站点 P 但在站点 Q 处于活动状态，则站点 P 广播 T2 已中止；然后站点 L 中止并回滚 T2，并将此消息发送到所有站点。
- 如果T1比T1年轻，则允许T1等待。在站点 P 收到 T2 已完成处理的消息后，T1 可以恢复执行。

分布式死锁检测

就像集中式死锁检测方法一样，死锁是允许发生的，如果检测到则将其删除。当事务发出锁定请求时，系统不执行任何检查。为了实现，创建了全局等待图。全局等待图中存在循环表明存在死锁。然而，由于事务需要通过网络等待资源，因此很难发现死锁。

或者，死锁检测算法可以使用计时器。每个事务都与一个计时器相关联，该计时器被设置为预计事务完成的时间段。如果事务在此时间段内未完成，计时器就会关闭，表明可能存在死锁。

用于死锁处理的另一个工具是死锁检测器。在集中式系统中，有一个死锁检测器。在分布式系统中，可以有多个死锁检测器。死锁检测器可以发现其控制下的站点的死锁。分布式系统中的死锁检测有三种替代方案：

集中式死锁检测器- 一个站点被指定为中央死锁检测器。
分层死锁检测器- 许多死锁检测器按层次结构排列。
分布式死锁检测器- 所有站点都参与检测死锁并消除它们。