《大规模分布式图算法》综述

大规模图数据的分布式处理具有许多实际应用，并且已被广泛研究。近年来，提出了许多分布式图处理框架和算法。虽然大量工作致力于分析这些框架和算法，且大部分是基于编程模型进行分析，但较少的研究集中于理解它们在分布式环境中的挑战。在分布式环境中应用图任务并非易事，通常面临许多挑战，通过我们的分析，这些包括并行性、负载平衡、通信开销和带宽问题。在本文中，我们通过概述分布式图算法的挑战和解决方案，提供了该领域当前最先进状态的广泛综述。我们首先对分布式图处理中的固有挑战进行系统分析，然后概述现有的通用解决方案。随后，我们综述了最近的分布式图处理论文中强调的挑战及采取的应对策略。最后，我们讨论当前的研究趋势，并识别潜在的未来机会。

https://arxiv.org/abs/2404.06037

图是一种高维结构，用于模型化实体之间的点对点关系。由于其强大的表示能力，图广泛应用于社交网络分析[26]、道路网络路由[74]和生物结构预测[22]。随着近年来信息科学和大数据应用[1, 55]的发展，图数据集的规模已变得过大，单一机器因其有限的存储和计算能力而难以应对。为了支持对大规模图的查询和分析，研究人员提出了许多分布式图算法和系统，这些系统将大规模图分别存储在多台机器上并进行协作计算，例如Pregel [116]、Giraph [10]、GraphX [76]和GraphScope [61]。

近年来，关于分布式图算法的研究激增，重点是开发特定算法如PageRank、标签传播和三角形计数，或解决工作调度和机器到机器通信等挑战。然而，提供该领域全面视角的综述仍然有限。本文旨在通过整合过去十年在SIGMOD、VLDB、PPoPP、SC、TPDS和TC等知名会议和期刊上发表的关于大规模图的分布式图算法的研究，弥合这一差距。我们从这些论文中提炼出四个主要且经常被提及的挑战： • 并行性是一个主要目标，需要同时处理多个操作并减少迭代轮数。 • 负载均衡旨在均匀分配顶点工作并提高计算资源的利用率。这有助于防止某些机器过载而其他机器闲置。 • 通信是指顶点之间的消息交换，与随机内存访问相比，这是一个昂贵的操作。优化通信开销可以在实际执行中提高效率。 • 带宽限制了顶点之间传输的消息大小。某些算法需要大量带宽，这在某些框架中可能不可行。 为了应对这些挑战，提出了许多开源分布式图处理框架（例如，Pregel [116]和GPS [137]）。这些框架中抽象了通用解决方案（例如，并行循环、消息接收和发送以及广播）。用户可以利用高级功能开发图算法，有效地抽象出底层实现细节的复杂性。然而，由于图算法的不规则性，这些解决方案高度多样化，专门为特定算法量身定做，没有统一模式适合所有图算法。 此外，现有研究中的分布式图算法解决了各种图任务。为了清晰地介绍它们，我们将广泛研究的图任务分类为七个主题：中心性、社区检测、相似性、紧密子图、遍历、模式匹配和覆盖。在本文中，我们首先介绍针对四个挑战的通用解决方案，然后解析不同算法主题中解决挑战的研究论文比例。此外，我们深入探讨了特定主题中某些挑战受到不同程度关注的原因。例如，与相似性主题相关的论文中70%集中于减少通信开销（图8c）。通过这些分析，我们展示了分布式图算法研究的深入见解，并提出了未来研究的潜在有前景方向。本文的独特贡献是构建了一个综合图，如图1所示，该图概述了调研材料中的论文、主题、算法、解决方案和挑战等之间的复杂连接，为该领域的格局提供了视觉叙述。读者可以通过在线交互工具（http://gsp.blue/query-app?graph_algo）来操作这个图。贡献。现有综述主要集中于特定的分布式挑战（例如，负载均衡[92]）或特定的分布式算法（例如，模式匹配[23]）。然而，我们的综述针对不同分布式图算法在考虑不规则计算的情况下所面临的挑战。具体来说，我们的主要贡献如下： • 我们提供了分布式图算法中主要挑战及其解决方案的概述。这为分布式图处理提供了全面的理解。 • 我们调研了各种分布式图算法，并根据它们解决的挑战将它们分类为七个主题。 • 对于分布式图算法的每一个主题，我们进行了现有工作的彻底分析。我们还总结了它们解决的主要挑战，并提供了对背后原因的独特见解。本文的其余部分安排如下。第2节回顾了现有的分布式图系统和计算处理。第3节总结了一些挑战和解决方案，这些挑战和解决方案在单机算法中并不常见。第4节详细描述了流行的分布式图算法，并突出了它们与单机版本的差异。第5节讨论了流行的研究趋势和潜在的研究机会。第6节总结了这次综述。分布式图处理：挑战与解决方案概述****分布式图处理能够通过互联的计算机处理非常大规模的图。然而，从单机计算向分布式计算的转变引入了一些挑战，这些挑战源于分布式系统和图的固有特性，这些特性在设计分布式图算法时是必须考虑的关键因素。在本节中，我们将对分布式图处理中的固有挑战进行系统分析（第3.1节）并提供现有解决方案的概述（第3.2节）。

分布式图处理中的固有挑战

在一个由多个互联机器组成的分布式系统中，每台机器都作为一个独立的计算单元，这些机器常常分布在不同的地点。如图2所示，这种设置利用集体的计算力进行高效的数据处理。然而，这也带来了在计算和网络资源利用方面的重大挑战，这些挑战在分布式图处理的背景下尤为关键。 计算资源效率：分布式系统的特点是其庞大且可扩展的计算资源，这使得系统能够处理大量图数据并执行复杂的图计算。因此，在设计分布式图算法时，充分利用系统中的计算资源非常重要。与所有指令在单一机器上执行的集中式图算法不同，分布式图算法需要多台机器的协作与合作来完成任务，这带来了并行性和负载平衡的挑战。 * 并行性：分布式图处理中的并行性涉及在不同机器上同时执行多个计算。这种方法需要将较大的图分析任务划分为更小、更易管理的子任务。这些子任务随后在不同机器之间分配，使得它们能够同时执行。这种策略不仅有助于高效地利用资源，还显著减少了整体的计算时间，从而提高了图处理任务的性能。然而，图分析任务往往呈现出固有的顺序依赖性[3, 88, 180]，使得在分布式图算法中实现并行性变得复杂。深刻理解这些任务的基本性质对于识别可以有效并行化的独立子任务至关重要。这需要仔细分析，以在保持顺序依赖性的完整性和优化并行执行之间找到平衡。 * 负载平衡：分布式图处理中的负载平衡确保计算工作负载在所有机器上均匀分配。负载不均会导致效率低下：一些机器可能迅速完成任务并处于闲置状态，而其他机器（通常称为拖后腿者）则在进行持续的计算中，最终延迟整个过程。这种不平衡在分布式图处理中尤为问题，因为计算的不规则性来自于非均匀[50]的度分布和拓扑不对称。尽管解决负载不平衡至关重要，但它非常复杂。它不仅需要精确的初始工作负载量化，还需要在运行时进行持续的调整以解决任何不平衡。

网络资源效率：在分布式系统中，机器通过网络通信，高效使用网络资源变得至关重要，尤其是在图处理中。图数据的固有复杂性，由复杂的结构和不规则的顶点连接标记，经常需要对单个顶点的操作与多个其他顶点进行互动。这种情况导致频繁且广泛的网络数据交换，尤其是当互联顶点分布在不同机器上时。因此，在网络资源效率方面出现了两个主要挑战。 * 通信开销：分布式系统中的通信开销由消息交换的网络资源使用定义，主要取决于数据传输量。在分布式图处理中，需要跨机器通信以访问位于不同机器上的顶点或边，增加了网络通信。这些数据交换的低效管理可能导致显著的网络拥堵，使网络通信成为整体计算性能的关键瓶颈。因此，管理通信开销对于优化分布式图处理的效率和有效性至关重要。 * 带宽：分布式系统中的带宽代表每轮消息传递中机器之间的最大数据传输容量。受到硬件和网络基础设施的限制，带宽不是无限可扩展的。在分布式图处理中，由于图中顶点的度分布不均，高度顶点在与邻居进行广泛通信[33]时，或同时被许多顶点访问时（在某些基于随机游走的算法[109]中很常见），需要高带宽。此外，低带宽利用率也是一个挑战。对于许多任务，如三角形计数、BFS和连通分量，大量的小消息在低度顶点之间传输，这些消息只包含有关其邻居的信息。另一方面，每次使用消息传递接口（如MPI）的消息交换都会引入额外的开销，以报头信息和握手协议消息的形式出现，从而导致实际有效数据的比例降低，进而导致带宽资源的低效利用[150]。因此，在分布式图处理中，有效且高效地优化带宽利用率是一个挑战。

解决方案概述

继第3.1节对分布式图处理中固有挑战的分析之后，本节总结了为应对这些挑战而开发的各种解决方案，特别是在分布式图处理领域，并提供了第4节中详细算法常用技术的概览。3.2.1 计算资源效率优化。本节重点介绍优化计算资源效率的解决方案，包括并行性和负载平衡。优化网络资源效率。本节重点介绍解决通信开销和带宽挑战的解决方案，关于网络资源效率。通信开销：在分布式图处理中，不同机器的顶点频繁交换消息，导致了大量的通信开销。结论

图可以很好地表示实体之间的关系。分析和处理大规模图数据已在许多应用中得到应用，如社交网络分析、推荐系统和道路网络路由。分布式图处理提供了一种在现实世界中高效处理大规模图数据的解决方案。为了了解分布式环境中图任务的最新研究并促进其发展，本文进行了一项关于分布式图任务的广泛综述。我们首先概述了现有的分布式图处理基础设施。这些工具促进了分布式算法的设计，但仍然难以克服由分布式系统和图的固有特性所引起的挑战。随后，我们分析并总结了分布式环境中图任务面临的主要挑战及其根据分布式系统和图的特性提出的相应解决方案。然后，我们提供了主要图任务的分类，并对它们在分布式环境中的现有努力进行了详细分析，包括它们关注的挑战和解决这些挑战的独特见解。最后，我们讨论了分布式图处理领域的研究重点和现有的研究空白，并识别了潜在的未来研究机会。

成为VIP会员查看完整内容