algorithm - 分布式拓扑排序算法

Question

在我当前的项目中，我有大量数据需要处理。处理顺序很重要，因为数据中存在子/父依赖关系。此时我正在一台机器上构建依赖关系图并在多台机器上分配工作，但我在“主”机器上达到了内存限制/处理限制，我想在多台机器上分配整个过程。

我如何在多台机器上构建这个依赖关系图？

Answer 1

由于路径非常短，找到出度为 0 的所有顶点、将它们添加到目前为止的顺序并删除它们的经典算法将很好地并行化(例如，使用 MapReduce)。

1. 在相关机器之间划分作业依赖图。每台机器都获得一个不相交的作业子集以及涉及这些作业的所有依赖项。

2. (循环重复)每台机器确定其哪些作业没有计划外的依赖性。这些作业被安排在与当前轮数相等的时间。对于将新安排的作业之一作为依赖项的每个作业，拥有新安排的作业的机器将这一事实报告给拥有依赖作业的机器。

总网络流量与图的大小成数量级，轮数受最长路径长度的限制，因此该算法对于您的用例应该是相当有效的。