分布式拓扑排序算法

Question

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

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

Answer 1

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

1. 分区所涉及的计算机之间的作业依赖关系图。每台机器获得作业的不相交的子集以及涉及这些jobs.
2. (repeated的所有依赖项。这些作业的调度时间与当前轮次数相等。对于将其中一个新计划的作业作为依赖项的每个作业，拥有新计划的作业的计算机会将此事实报告给拥有依赖作业的计算机。

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