分散トポロジカルソートアルゴリズム

Question

私の現在のプロジェクトでは、大量のデータを処理する必要があります。処理の順序は、データに子/親の依存関係があるため重要です。この時点で、あるマシンで依存関係グラフを作成し、複数のマシンに分散して配布していますが、「マスター」マシンのメモリ制限/処理制限に達しています。このプロセス全体を複数のマシンに分散したいと考えています。

この依存関係グラフは、複数のマシンでどのように作成できますか？

Answer 1

パスが非常に短いため、out-degree 0のすべての頂点を検出し、これまでの順序に追加し、それらを削除する古典的なアルゴリズムは、（MapReduceなどで）うまく並列化されます。

1. 関連するマシン間でジョブ依存グラフを分割します。各マシンには、ジョブとそのジョブに関連するすべての依存関係の分離サブセットがあります。

2. （ラウンドで繰り返されます）各マシンは、どのジョブがスケジュールされていない依存関係も持た​​ないと判断します。これらのジョブは、現在のラウンド数に等しい時間にスケジュールされます。新しくスケジュールされたジョブの1つを依存関係として持つ各ジョブについて、新しくスケジュールされたジョブを所有するマシンは、この事実を従属ジョブを所有するマシンに報告します。

総ネットワークトラフィックは、グラフの大きさのオーダーであり、ラウンド数は、最長パスの長さによって制限されるので、このアルゴリズムは、ユースケースのために合理的に効率的であるべきです。