CIにおける有向非巡回グラフとは何か？ジョブ順序のモデル化

有向非巡回グラフ（DAG）は、パイプラインを、決して巡回を形成しない依存関係（有向エッジ）で接続されたjob（ノード）としてモデル化します。

内部では、CIのschedulerはjobのリストを見ません。グラフを見ます。各jobはノード、各依存関係は前提条件から依存先を指す有向エッジであり、グラフには巡回がありません（何も直接的にも間接的にも自分自身に依存できません）。このDAGこそが、パイプラインが今実行できるものと待たねばならないものを判断できるようにするものです。

なぜ「有向」で「非巡回」なのか

有向: エッジには方向がある（AはBの前に終わらねばならない）。
非巡回: 巡回がないので、依存関係が永遠にループできない。
グラフ: jobとその依存関係のエッジをまとめたもの。

schedulerがどう使うか

schedulerは、前提条件がすべて完了しているjobを実行します。jobが終わるにつれ、より多くが実行可能になります。これは自然に、あらゆる依存関係を尊重しつつ、グラフの独立した枝を並列化します。

簡単な例

buildがlintとtestの両方に供給し、testがdeployに供給します。DAGはまずbuildを実行し、次にlintとtestを並列で、その後testが終わるとdeployを実行します。lintとdeployは決して互いを待つ必要がありません。

なぜ巡回が禁じられるか

jobのAがBに依存し、BがAに依存したら、どちらも決して開始できません。CIツールは検証時にそのような巡回を拒否します。非巡回グラフだけが、実際に完了までスケジュールできる唯一の種類だからです。

DAGの形とパイプライン時間

広く浅いDAGは、多くのjobが並列に進むので速く実行されます。深く狭いDAGは、各stepが前を待つので遅く実行されます。DAGを通る最長のパスが、合計時間を制限するcritical pathです。

重要なポイント

CIのDAGは、jobをノード、依存関係を有向で非巡回のエッジとしてモデル化します。
schedulerは、すべての前提条件が完了するとすぐに各jobを実行します。
より広いグラフはより多く並列化し、最長のパスが合計時間を制限します。