パイプラインのcritical pathとは何か？最長のチェーン

パイプラインのcritical pathとは、依存するjobの最長のチェーンで、パイプライン全体がどれだけ速く終われるかの下限を定めます。

どれだけ多くのマシンをパイプラインに投入しても、最長の依存関係チェーンより速くは終われません。そのチェーンがcritical pathです。その上のすべてのjobは前のjobを待たねばならないので、所要時間が加算されます。critical pathを見つければ、パイプラインの速度を制限している唯一のものを見つけたことになります。

なぜ最長のチェーンが支配するか

critical path外のjobは並列に実行されて早く終わり、合計時間を延ばしません。critical path上のjobは順次実行されるので、所要時間が加算されます。パイプラインは、このチェーンの最後のjobが完了したときにのみ終わります。

critical pathを見つける

依存関係グラフを始点から終点までたどり、jobの合計所要時間が最大となるパスを見つけます。そのパスが、単独の遅いjobではなく、最小実行時間を決定します。

簡単な例

build（5m）-> test（10m）-> deploy（3m）が最長のチェーンなら、他の10個のjobが並んで並列に実行されても、パイプラインは少なくとも18分かかります。並列jobを高速化しても何も変わりませんが、testを高速化するとすべてが変わります。

critical pathの短縮

遅いクリティカルなjobを並列shardに分割する（fan-out）。
作業をキャッシュし、クリティカルなstepが変更なしのときスキップされるようにする。
直列化を強制する不要な依存関係を取り除く。
必須でない作業をcritical pathの外へ移す。

critical pathとランナー

クリティカルなjobのキュー時間はcritical path全体を延ばすので、runnerを待つjobは遅いjobと同じくらいコストが高いです。マネージドランナー（Latchkey）はウォームなキャパシティを準備しておくことでクリティカルなjobのキュー時間を減らし、critical pathを待機ではなく実行時間にします。

重要なポイント

critical pathは、パイプライン内で依存するjobの最長のチェーンです。
最小実行時間を定めます。パス外のjobはそれを延ばしません。
critical pathを高速化、shard化、またはキャッシュしてパイプラインを速くします。