分布式系统中的分层死锁检测

引言

死锁检测是使分布式系统可靠并正常运行的重要方面。当一组进程阻碍了进展时，因为每个进程都在等待另一个进程持有的资源，形成了一个依赖循环，就会出现死锁，导致没有进程可以继续执行。

分层死锁检测方法旨在通过使系统分层来有效检测和解决死锁。利用系统层次结构将这些检测工作集中在局部化死锁上，从而减少全局检测机制的开销。

了解分布式系统中的死锁

在分布式系统中，如果每个进程都在等待其他进程持有的某些资源，并且它们都无法继续执行，因为它们之间存在循环依赖，则进程处于死锁状态。这种情况导致这些相关进程需要继续执行的资源被占用，从而陷入僵局。如果所有四个条件都同时成立，就会发生死锁情况。

1. 互斥： 至少一个资源必须以不可共享的方式占用，并且一次只能有一个进程使用该资源。
2. 占有并等待： 一个进程至少持有一个资源并等待获取其他进程持有的资源。
3. 不可抢占： 资源只能由持有它们的进程自愿释放；不能强行从持有它们的进程中移除资源。
4. 循环等待： 一组进程以循环链的形式等待其他进程持有的资源。

由于系统状态缺乏全局视图、通信延迟以及这些系统中进程动态出现的性质等因素，分布式系统中的死锁检测和解决比集中式系统更困难。

传统死锁检测方法

分布式系统中的死锁检测基于传统方法，这些方法通常可分为两类：集中式方法、分散式方法和分层式方法。

1. 集中式死锁检测： 在这种方法中，系统的所有节点只向一个协调器报告资源分配和进程状态。协调器构建 WFG（等待图）以检测循环，指示死锁。这种方法简化了检测过程，但会存在单点故障和可伸缩性问题。
2. 分散式死锁检测： 这种方法通过将检测责任分配给多个节点来消除单一协调器。但是，它通过监视每个节点的本地资源并与其他节点协作来检测死锁。通常，通过沿 WFG 边缘发送特殊探测消息来使用边缘追踪等技术来检测循环。这里介绍的方法具有可伸缩性和容错性，但通信开销高，并且可能因消息延迟而导致错误的死锁检测。
3. 分层死锁检测： 分层方法试图通过将系统划分为控制单元的层次结构来在集中式和分散式方法之间找到最佳解决方案。存在一个单元的控制单元，用于检测其域内的死锁，并在必要时向其上级单元报告死锁。这种结构可以局部化检测工作，减少通信开销，并使系统更具可伸缩性。

分布式系统中的分层死锁检测

分布式系统中的分层死锁检测是一种通过将系统结构化为多个级别或集群来处理分布式系统中的死锁检测的方法。系统被划分为一个层次结构，其中每个节点（称为控制单元或协调器）负责系统资源和进程的每个子集。根据地理分布、管理域、资源类型等不同组织，可以有不同级别的层次结构。下面是检测过程的逐步解释：

1. 系统组织： 分布式系统由多级或集群组成，这些集群由一组节点或进程形成。用于死锁检测的分层结构允许管理和控制复杂性。
2. 局部检测： 这是最低级别的检测，每个集群或节点都必须能够检测其范围内的死锁。这意味着所讨论的死锁发生在集群内的所有进程或资源之间，因此不需要持续的全局监控。
3. 局部解决： 如果发现死锁，该集群中的进程将尝试解决它。可用于此的技术包括资源抢占、进程终止和回滚。
4. 集群间通信： 如果死锁无法在集群内解决，有关死锁的信息会传播到层次结构中的更高级别。这些更高级别负责监督许多集群，并协助它们之间的解决过程协调。
5. 全局协调： 在某些情况下，全局协调器或管理器可能会参与更复杂的死锁，这些死锁可能会跨越多个集群。此级别保证在整个分布式系统中一致地使用解决方案策略。
6. 易于开发： 这种方法通过将系统分解为层次结构级别，使系统开发更容易。该系统具有可伸缩性和效率，并通过局部检测和解决减少了对大量通信的需求。

分层死锁检测通过分散检测过程并将精力导向需要的地方，为处理分布式系统的复杂性提供了一个整体解决方案。

分层死锁检测算法

分层死锁检测算法是处理大型系统中死锁的高度复杂方法，其中大型系统以层次结构排列。它有助于处理复杂性并提高效率。

分层死锁检测通过使用多种算法进行，例如 Ho-Ramakrishnan 算法、Chandy-Misra-Haas 算法、边缘追踪算法、路径推送算法、基于探测的算法和扩散计算算法。所有这些方法都采取独特的行动，通过分层方法批准死锁。

1. Ho-Ramakrishnan 算法

2. Chandy-Misra-Haas 算法

在这种方法中，死锁分为或类型和与类型。

• 或死锁：进程要继续进行所需的众多资源之一。
• 与死锁：进程同时需要所有请求的资源。

系统通过系统传播探测并检测死锁。当进程请求资源时，进程向持有资源的进程发送探测消息。探测中存在的信息是发起者和依赖链。如果探测最终返回到发起进程，它会进行循环等待，从而确认发现死锁。这种层次结构允许将探测传播减少到相关级别，从而提高系统可伸缩性并减少大型分布式系统的开销。

3. 边缘追踪算法

因此，边缘追踪算法使用在资源请求路径上发送的特殊消息（令牌）来发现循环。每个令牌都包含有关请求进程的信息。如果进程可以接收其令牌，则表明存在循环等待；如果发生这种情况，则确认存在死锁。

4. 路径推送算法

维护每个进程的依赖列表。当发出新请求时，依赖列表会更新并传播。如果发现循环依赖，则检测到。

5. 基于探测的算法

它沿资源依赖链发送探测，以检测循环。每个探测都携带进程信息，如果探测返回到发送者本身，则意味着存在死锁。

6. 扩散计算算法

该算法使用基于树的方法，其中节点沿层次结构向上传播资源依赖信息，并根据其所依赖的依赖关系扩散所使用的资源量。如果收集到的数据中检测到循环，则收集到的数据是无意义的。所有这些方法都采用了一些独特的死锁检测和解决技术，以分层方式进行。

7. 分层资源分配图 (HRAG)

与资源分配图类似，通过创建层次结构来改进传统算法。层次结构中每个级别的资源分配图独立维护，并使用层次结构协调不同级别的图以检测和解决全局死锁。

8. 等待图

这是通过在每个集群级别构建等待图来实现的。在本地检测到死锁，如果需要，有关等待循环的信息会向上报告，并在全局范围内解决。

9. 使用令牌的分层方案

在某些情况下，为了检测死锁，会在集群之间传递一个令牌。令牌有助于跟踪资源及其分配，并且它们的缺失或存在可能表明可能存在死锁。它还有助于在不同级别同步死锁检测。

分布式系统中死锁检测的实现

1. 局部死锁检测

• 资源分配图： 对于每个节点/集群，资源分配图按节点或集群维护，节点是进程，边缘是资源请求和分配。在这些图中找到循环表示死锁。
• 等待图： 每个集群都会构建一个等待图，以记录哪些进程正在等待哪些资源。此图是局部的，这些死锁是根据循环检测到的；为此使用了局部算法。
• 基于令牌的方法： 其中一些系统通过在节点之间传递令牌来检测死锁。令牌可用于表示资源或防止循环等待条件的控制机制。令牌缺失，或者令牌存在于循环中：死锁。

2. 集群间协调

• 分层协调： 在分层系统中，局部死锁检测和解决由较低级别执行。如果死锁无法在本地解决，信息将传输到较高级别。较高级别协调集群并使用解决方案策略。
• 消息传递： 这被称为消息传递，系统通过消息传递在层次结构中向上通信死锁信息。它们包含死锁的详细信息并解决问题中的资源和进程。

分布式系统中死锁检测的案例研究

1. Google 的 Spanner 数据库

Google Spanner 是一个分布式数据库，有助于扩展并具有高可用性。其分布式事务管理需要死锁检测。

• 实现： Spanner 中的死锁使用分布式事务日志和分层等待图以及解决。第三，它结合了一个全局协调机制，用于管理不同节点之间的事务，以及对单个节点上事务的局部死锁检测。
• 结果： Spanner 采用分层方法，确保在分布式环境中保持高可用性和一致性。系统性能和可靠性的主要要求之一是其快速管理和解决死锁的能力。

2. Amazon DynamoDB

DynamoDB 是一种NoSQL高可用性和可伸缩的完全托管数据库服务。层次结构用于检测分布式事务中的死锁。

• 实现： DynamoDB 结合使用局部和全局死锁检测机制和实现。执行每个节点或分区的死锁的局部检测，并且全局协调保证死锁解决（如果任何死锁包括跨多个分区的死锁）。
• 结果： 通过分层检测机制，DynamoDB 能够以低延迟和高吞吐量处理大量具有高数据分布的微事务。

3. 分布式文件系统

分布式文件系统，如Hadoop 分布式文件系统 (HDFS)，需要快速死锁检测来处理文件访问和资源分配。

• 实现： HDFS 和使用分层死锁检测的相关系统来管理文件块的访问。局部集群处理与特定文件块相关的死锁，更高级别协调整个文件系统上的死锁。
• 结果： 这种方法消除了与文件操作和块分配相关的死锁，以确保即使多个进程想要一个文件，除了其他进程之外，也可以有效访问文件，从而在死锁情况下不会停机。

分层死锁检测的优点

1. 可伸缩性： 层次结构确保检测随着系统增长而扩展。
2. 减少通信开销： 全局广播可以被不同级别的局部检测取代，从而减少网络拥塞。
3. 容错性： 如果一个级别发生故障，它仍然会导致故障发生在其他级别。
4. 提高效率： 由于死锁是首先在本地检测到的，因此浪费的计算量更少。

挑战和局限性

尽管分层死锁检测有很多优点，但它也带来了一些挑战。

1. 复杂实现： 必须仔细设置设计层次结构级别。
2. 检测延迟： 由于分布式检测，这使得死锁检测延迟。
3. 协调开销： 同步多个检测器增加了开销的复杂性。
4. 消息延迟： 由于消息延迟，可能会出现误报死锁。

结论

分层死锁检测高效且可伸缩地解决了分布式系统中的死锁管理问题。通过多级检测结构，通信开销得以降低，系统可靠性得以提高。存在挑战，但它们在AI、区块链和混合系统中的成功持续提高了该系统的有效性。在不断增长的分布式系统中，分层死锁检测仍然是实现不间断资源管理和系统稳定性的重要方法。