大规模并行图计算：从理论到实践

图是实体组之间联系的有用理论表示，并已用于数据科学中的各种目的，从按受欢迎程度对网页进行排名和绘制社交网络，到辅助导航。在许多情况下，此类应用程序需要处理包含数千亿条边的图，这对于在单个消费级机器上处理来说太大了。缩放图算法的典型方法是在分布式系统中运行设置，即在多台计算机之间划分数据（和算法）以并行执行计算。

虽然这种方法允许人们处理具有数万亿条边的图，但它也带来了新的挑战。也就是说，由于每台计算机一次只能看到一小部分输入图，因此需要处理机器间通信和设计可以拆分到多台计算机的算法。

一个实现分布式算法的框架MapReduce于 2008 年推出。它透明地处理机器之间的通信，同时提供良好的容错能力，并激发了许多分布式计算框架的开发，包括Pregel、Apache Hadoop等。尽管如此，在非常大的图上开发分布式计算算法的挑战仍然存在，并在这种情况下设计有效的算法，即使是基本问题，如连通分量、最大匹配或最短路径，一直是一个活跃的研究领域。虽然最近的工作已经证明了许多问题的新算法，包括我们的连接组件算法（理论和实践）和层次聚类，但仍然需要可以更快地解决一系列问题的方法。

今天，我们通过首先构建分布式图算法的理论模型，然后演示如何应用该模型来解决这个问题。所提出的模型，自适应大规模并行计算(AMPC)，增强了 MapReduce 的理论能力，提供了一种以更少的计算轮次解决许多图问题的途径。我们还展示了如何在实践中有效地实施AMPC 模型。我们描述的算法套件，包括最大独立集、最大匹配、连通分量和最小生成树的算法， 工作速度比当前最先进的方法快 7 倍。

MapReduce

的局限性 为了理解 MapReduce 在开发图算法方面的局限性，请考虑连通分量问题的简化变体。输入是有根树的集合，目标是为每个节点计算其树的根。即使是这个看似简单的问题，在 MapReduce 中也不容易解决。事实上，在大规模并行计算(MPC) 模型中——MapReduce、Pregel、Apache Giraph和许多其他分布式计算框架背后的理论模型——这个问题被广泛认为至少需要多轮与log n成比例的计算，其中n是图中节点的总数。虽然log n看起来不是一个很大的数字，但处理万亿边图的算法通常每轮都会将数百 TB 的数据写入磁盘，因此即使轮数的小幅减少也可能带来显着的资源节省。

我们的算法中出现了一个类似的子问题，用于寻找连接的组件和计算层次聚类。我们观察到，可以通过使用分布式哈希表(DHT)实现这些算法来绕过 MapReduce 的限制，这是一种使用一组键值对初始化的服务，然后返回与提供的键相关联的值即时的。在我们的实现中，对于每个节点，DHT 存储其父节点。然后，处理图节点的机器可以使用 DHT 并“向上走”树直到它到达根。虽然 DHT 的使用对这个特定问题很有效（尽管它依赖于不太深的输入树），但不清楚这个想法是否可以更广泛地应用。

自适应大规模并行计算模型

为了将这种方法扩展到其他问题，我们首先开发了一个模型来从理论上分析利用 DHT 的算法。由此产生的 AMPC 模型建立在完善的 MPC 模型之上，并正式描述了使用分布式哈希表带来的功能。

在 MPC 模型中，有一组机器，它们通过同步轮次中的消息传递进行通信。一轮中发送的消息在下一轮开始时传递，并构成该轮的整个输入（即，机器不保留从一轮到下一轮的信息）。在第一轮中，可以假设输入随机分布在机器上。目标是最小化计算轮数，同时确保每轮机器之间的负载平衡。

然后我们通过引入一种新方法来形式化 AMPC 模型，其中机器每轮写入一个只写分布式哈希表，而不是通过消息进行通信。一旦新一轮开始，前一轮的哈希表变为只读，并且新的只写输出哈希表变为可用。重要的是，只有通信方法发生了变化——每台机器的通信量和可用空间都以与 MPC 模型中完全相同的方式受到限制。因此，在高层次上，AMPC 模型的附加功能是每台机器都可以选择要读取的数据，而不是提供一条数据。

算法和经验评估

机器通信方式的这种看似微小的差异使我们能够为许多基本的图形问题设计更快的算法。特别是，我们表明无论图的大小如何，都可以在恒定的轮数中找到连通分量、最小生成树、最大匹配和最大独立集。

为了研究 AMPC 算法的实际适用性，我们通过将 Flume C++（FlumeJava的 C++ 对应物）与 DHT 通信层相结合来实例化模型。我们已经针对最小生成树、最大独立集和最大匹配评估了我们的 AMPC 算法，并观察到与不使用 DHT 的实现相比，我们可以实现高达 7 倍的加速。同时，AMPC 实现平均使用少 10 倍的轮数 来完成，并且向磁盘写入的数据也更少。

我们对 AMPC 模型的实现利用了硬件加速远程直接内存访问(RDMA)，该技术允许从远程机器的内存中读取几微秒的延迟，这仅比读取慢一个数量级从本地内存。虽然一些 AMPC 算法比 MPC 算法传输的数据更多，但它们总体上更快，因为它们主要使用 RDMA 执行快速读取，而不是昂贵的磁盘写入。

结论

利用 AMPC 模型，我们建立了一个受实际高效实现启发的理论框架，然后开发了新的理论算法，这些算法提供了良好的经验性能并保持了良好的容错特性。