Everyone thinks CI/CD is simple. “A webhook fires on push, you spin up a box, run the tests, and if they pass you ship it - it is a glorified make test && deploy wrapped in a cron.” That mental model survives exactly until you ask the two questions that actually define the system. First: a monorepo push touches three files, but the repo has 40,000 build targets wired into a dependency graph where test E cannot run until library C is built which needs A and B - how do you figure out the minimal set of jobs that this change could possibly have broken, order them so no job runs before its inputs exist, and pack that onto a finite pool of workers so the critical path finishes fast and no small team’s tiny job waits forty minutes behind a mega-build? That is a dependency-aware scheduling problem over a DAG, and it is where every naive CI system falls over. Second: you are not running one team’s builds, you are running thousands of concurrent pipelines from hundreds of teams on a shared, elastic fleet of ephemeral workers that must be created clean, used once, and destroyed - because a build that leaks a secret or a cached artifact into the next tenant’s build is a security incident and a correctness bug at the same time. How do you provision those workers in seconds, schedule across them fairly, and guarantee a poisoned job never contaminates another?

A CI/CD system - the thing under GitHub Actions, GitLab CI, Buildkite, CircleCI, Jenkins, or an internal platform at any large shop - is deceptive because the happy path (one small repo, five tests, one deploy target) is trivial, and the entire actual difficulty is in the states around it: the build graph that decides what even needs to run, the scheduler that assigns thousands of jobs to a bursty worker pool without starving anyone, the ephemeral worker lifecycle that must be fast and hermetic, the artifact flow that carries build outputs between stages and into deploys, and the deploy-with-rollback path that has to change production safely and undo itself when a canary goes bad. Get the scheduler and the worker isolation wrong and you have either a slow pipeline teams route around or an insecure one that leaks across tenants.

Let me do it properly.

Functional Requirements (FR)

In scope:

  • Trigger a pipeline on a repository event. A push, a pull-request open/update, a tag, a manual “run”, or a scheduled cron fires a pipeline. The system receives the event (a webhook from the SCM, or a poll), resolves the pipeline definition at that commit, computes what to run, and starts it. This is the entry point.
  • Compute the job graph from config and change. Read the pipeline config (a YAML file in the repo, e.g. .ci/pipeline.yml) at the triggering commit, expand it into a DAG of jobs (build, lint, unit test, integration test, package, deploy) with declared dependencies, and - for a monorepo - intersect it with the set of targets affected by the changed files so only potentially-broken work runs.
  • Run jobs on ephemeral, isolated workers. Each job runs in a fresh, sandboxed worker (a container or microVM) provisioned on demand, with the repo checked out at the commit, declared inputs (prior-stage artifacts, caches) mounted, and secrets injected per the job’s scope. The worker runs the job’s commands, captures exit code, logs, and output artifacts, then is destroyed - never reused across tenants.
  • Fan out parallel jobs and respect dependencies. Independent jobs run concurrently across many workers; a job starts only when every upstream dependency has succeeded. The scheduler assigns ready jobs to available runners, honoring resource requirements (CPU, memory, special hardware like GPU), concurrency limits, and fairness across teams.
  • Collect results, artifacts, and logs. Per-job exit status, streamed logs, test reports (pass/fail counts, timings), and produced artifacts (binaries, images, coverage) are stored and surfaced. The pipeline’s overall status (success/failure/cancelled) is reported back to the SCM as a commit status / check.
  • Deploy artifacts with automated rollback. On a passing pipeline for a deploy branch, promote the built artifact through environments (staging then production), roll it out progressively (canary, then wider), watch health signals, and automatically roll back to the last-good version if the canary or the full rollout breaches error/latency thresholds.
  • Cache and reuse to skip redundant work. Build caches (compiler outputs, dependency downloads) and prior successful job results are reused when inputs are unchanged, so an unaffected job is not re-run. This is a correctness-sensitive optimization (reuse only when inputs provably match).

Explicitly out of scope (say it so you own the scope):

  • Being the source-control system. We consume events and read config/code from an SCM (GitHub/GitLab/an internal Git host) through its API and webhooks. We do not host repositories, do merges, or manage branches - designing the Git host itself is a separate problem.
  • The build tooling itself. We run the user’s commands (bazel build, npm test, go build). We orchestrate, schedule, isolate, and cache around them, but we do not implement compilers, test runners, or the build system’s own internal incrementality - though we integrate with it (e.g. query a build tool for the affected-target graph).
  • Full infrastructure / release management. We deploy an artifact and can roll it back, but we are not a general infra-as-code / cluster-provisioning platform, a feature-flag service, or a service mesh. We call out to a deploy target (Kubernetes, a serverless platform, a fleet) and watch health; we do not reimplement those.
  • Arbitrary long-running or interactive workloads. Jobs are bounded units of work with a timeout (minutes to low tens of minutes). We are not a general compute platform for daemons or notebooks; a hung job is killed at its timeout.
  • Guaranteed exactly-once side effects inside user commands. We retry failed jobs and redeliver events, so a job can run more than once; user commands that touch the outside world must tolerate re-runs. We guarantee at-most-one successful promotion of a given artifact to an environment, not exactly-once execution of arbitrary user code.

The one decision that drives everything: the system does not run a fixed script on a fixed box, it computes a minimal dependency DAG per change and schedules it onto a shared pool of ephemeral workers, so the product’s whole quality rests on how good the scheduler is at finishing the critical path fast while fairly sharing a finite fleet and never starving anyone. Every other choice - the event ingest, the graph builder, the worker lifecycle, the artifact store, the deploy controller - exists to feed that scheduler correct work and execute its decisions safely.

Non-Functional Requirements (NFR)

  • Scale: on the order of thousands of repositories and hundreds of teams, tens of thousands of pipeline runs/day, each exploding into anywhere from a handful to tens of thousands of jobs (a monorepo change can touch thousands of affected targets). Peak concurrency of tens of thousands of running jobs across the fleet, with sharp diurnal and “everyone pushes before lunch” bursts. The defining shape is spiky fan-out of short jobs over a shared worker pool, with a long tail of a few enormous monorepo graphs.
  • Latency: developer-perceived time-to-first-feedback matters most - a ready job should start on a worker within single-digit seconds of becoming ready (queue + provision), not minutes. Short jobs (a lint, a unit-test shard) should complete end-to-end in tens of seconds. The critical path of a pipeline (longest dependency chain) is the floor on total time; the scheduler must not add avoidable queueing on top of it.
  • Availability: 99.9%+ for accepting events and scheduling. A webhook must never be silently dropped (lost event = a change ships untested); event ingest is durable and redelivered. The control plane degrades gracefully - if the scheduler is briefly unavailable, jobs queue rather than fail.
  • Consistency: a pipeline’s status must be correct and monotonic - a run that is “failed” never flips to “passed”, a deploy gate must see the true aggregate result before promoting. Job scheduling needs exactly-once assignment semantics (a job runs on one worker at a time; a lease/fencing scheme prevents double-execution after a worker is presumed dead). Artifact and cache lookups must be content-addressed so reuse is never a stale-input correctness bug.
  • Isolation / hermeticity (a core NFR): every job runs in a fresh environment with no state from any prior job or tenant - no leaked secrets, no leftover files, no shared mutable cache that one tenant can poison for another. Workers are single-use and destroyed after a job. Secrets are scoped to the job and never written to logs or artifacts. A malicious or buggy build must not read another team’s source, cache, or credentials.
  • Durability: build artifacts, logs, and test results are durably stored (logs streamed and persisted so a crashed worker does not lose them); the last-known-good deployable artifact per environment is retained so rollback always has a target. Pipeline run history is retained for audit.
  • Fairness (the scheduler’s defining NFR): no team, repo, or single giant pipeline can monopolize the fleet. A 20,000-job monorepo build must not starve a two-job hotfix from another team. Per-tenant concurrency shares, priority for interactive/PR jobs over background jobs, and anti-starvation guarantees are mandatory, not optional.

Back-of-the-Envelope Estimation (BoE)

Let me ground the design in numbers.

Runs, jobs, and the fan-out shape:

Pipeline runs:        50,000 /day across all repos
Jobs per run:         avg ~50, but a long tail: a monorepo change can be
                      10,000-30,000 affected test targets
Total jobs:           50,000 runs * ~50 avg = ~2,500,000 jobs/day
                      (the tail monorepo runs dominate: a few runs of 20,000
                       jobs each add millions more on their days)
Average rate:         2.5M / 86,400s = ~29 jobs/sec steady
But bursty:           pushes cluster in work hours; peak is many multiples
                      of steady - call it ~300-500 jobs/sec at peak, and a
                      single big monorepo run dumps 20,000 ready jobs at once.

The first non-obvious number: the distribution is brutally skewed. Most runs are small (a handful of jobs) and most jobs come from a few giant monorepo runs. A scheduler tuned only for the average will let one 20,000-job graph swamp the fleet and starve everyone. The system must handle a single run that is larger than a normal hour of total traffic, which is exactly why fairness and affected-target pruning are load-bearing.

Job duration and worker concurrency:

Average job duration: ~90 seconds (lint/unit short; integration tests long)
Concurrency (Little's law): 29 jobs/s * 90s = ~2,600 jobs running steady,
                      peaking to tens of thousands during bursts.
Worker packing:       say a worker is 4 vCPU / 8 GB, runs 1 job at a time
                      (hermetic, single-use). Peak 30,000 concurrent jobs
                      -> up to ~30,000 ephemeral workers at peak, scaled
                      down to a small warm pool off-peak. Elastic fleet.
Provision time:       a cold worker (VM boot + image pull + checkout) is the
                      enemy of time-to-first-feedback; target < a few seconds
                      via a warm pool and cached base images.

Affected-target pruning (the biggest lever in a monorepo):

Monorepo targets:     40,000 build/test targets in the dependency graph
Naive "test everything": every push runs all 40,000 -> hours, huge cost
Typical change:       touches ~3 files -> affects ~50-500 downstream targets
Pruned set:           run ~200 affected jobs instead of 40,000
                      = ~200x less work on the common change. This single
                      optimization is the difference between a usable and an
                      unusable monorepo CI.

Storage, logs, bandwidth:

Artifacts:    2.5M jobs/day, say 20% produce an artifact, avg ~50 MB
              (binaries, images, coverage) -> 500k * 50 MB = ~25 TB/day
              written, most short-lived (keep per-run for a retention window,
              promote release artifacts to long-term). Content-addressed and
              deduped - a cache hit writes nothing.
Logs:         2.5M jobs * avg ~200 KB of log -> ~500 GB/day, streamed to
              object storage, indexed for search, retained per policy.
Build cache:  dependency downloads + compiler outputs, content-addressed,
              shared read-mostly; terabytes, hot entries on fast storage near
              workers. Cache hit rate is the other big cost lever.
Metadata:     run + job state (status, graph edges, leases) - small per job
              but read/written constantly during a run; needs a fast,
              consistent store, not a blob store.

The headline shape: tens of thousands of small, short jobs a day with a long tail of a few enormous monorepo DAGs, over an elastic pool of single-use workers, where the scarce resources are worker slots, scheduler fairness, and provision latency. Prune the graph to affected targets (200x on the common change), cache aggressively and content-address everything (so reuse is safe), keep a warm worker pool to kill provision latency, schedule for critical-path-first with hard fairness so no giant run starves anyone, and stream logs/artifacts off the worker so a crash loses nothing.

High-Level Design (HLD)

The system splits into an event ingest layer (webhook receivers + pollers that durably capture SCM events), a pipeline/graph service that reads the config at the commit, computes the affected-target set, and materializes the job DAG plus run state, a scheduler (the brain) that tracks which jobs are ready (all deps satisfied) and assigns them to workers under resource, priority, and fairness constraints, a worker fleet of ephemeral runners managed by an autoscaler/provisioner plus a per-worker agent that executes a job in a sandbox and streams results, an artifact + cache store (content-addressed object storage) that carries outputs between stages, a metadata store for run/job state and leases, a log pipeline, and a deploy controller that promotes artifacts through environments with canary analysis and automated rollback.

   SCM EVENTS
  ┌───────────────┬──────────────────┬─────────────────────┐
  │ push / PR     │ tag / release    │ manual / schedule   │
  │ (webhook)     │ (webhook)        │ (API / cron)        │
  └──────┬────────┴────────┬─────────┴──────────┬──────────┘
         │ 1. event         │                     │
         ▼                  ▼                     ▼
 ┌──────────────────────────────────────────────────────────┐
 │        EVENT INGEST  (durable queue, idempotent)          │
 │  verify signature, dedup by delivery-id, enqueue          │
 └───────────────────────────┬──────────────────────────────┘
          2. build the graph  ▼
 ┌──────────────────────────────────────────────────────────┐
 │           PIPELINE / GRAPH SERVICE                        │
 │  read config@commit, expand to job DAG, intersect with    │
 │  AFFECTED TARGETS (changed files -> reverse deps),        │
 │  resolve cache keys, write run+jobs to metadata store     │
 └──────────────┬───────────────────────────────┬───────────┘
    ready jobs  │                                 │ run/job state
                ▼                                 ▼
 ┌──────────────────────────────┐        ┌──────────────────┐
 │         SCHEDULER            │◀──lease─│  METADATA STORE  │
 │  ready-queue per priority;   │        │ (runs, jobs, DAG │
 │  per-tenant fair shares;     │        │  edges, leases,  │
 │  resource-match; assign to   │        │  statuses)       │
 │  a worker; anti-starvation   │        └──────────────────┘
 └───────┬──────────────────────┘
 3.assign │   ▲ heartbeat/result            ┌──────────────────┐
         ▼   │                              │ AUTOSCALER /     │
 ┌─────────────────── WORKER FLEET ───────┐ │ PROVISIONER      │
 │ ephemeral runner (container/microVM)   │◀┤ warm pool, scale │
 │  agent: checkout@commit, mount inputs, │ │ on queue depth   │
 │  inject scoped secrets, run commands,  │ └──────────────────┘
 │  stream logs, upload artifacts, EXIT   │
 │  -> worker DESTROYED (single use)      │────┐ 4. outputs
 └────────────────────────────────────────┘    ▼
                          ┌─────────────────┬──────────────────┐
                          │ ARTIFACT+CACHE  │  LOG PIPELINE     │
                          │ (content-addr   │  (stream->store,  │
                          │  object store)  │   index/search)   │
                          └────────┬────────┴──────────────────┘
          5. on deploy job, promote│ artifact
                                   ▼
 ┌──────────────────────────────────────────────────────────┐
 │        DEPLOY CONTROLLER                                  │
 │  staging -> canary -> full; watch health (err/latency);  │
 │  AUTO-ROLLBACK to last-good on breach; gate promotions   │
 └──────────────────────────────────────────────────────────┘

Request flow - a push triggers a pipeline (the common path):

  1. A push webhook hits an ingest receiver. It verifies the signature, dedups by delivery id (webhooks are at-least-once), and writes the event to a durable queue. The HTTP handler returns 200 immediately - ingest never blocks on building the graph.
  2. The pipeline/graph service picks up the event. It reads the pipeline config at the pushed commit, expands it into a job DAG, computes the changed files (diff against the base), queries the dependency graph for reverse dependencies of those files to get the affected target set, and intersects: the run is only the affected jobs plus their required upstream build steps. It resolves a cache key per job (hash of inputs) and writes the run and all jobs - with their dependency edges and initial status (blocked or ready) - to the metadata store. Jobs whose cache key already has a successful result are marked cached and skipped.
  3. The scheduler sees newly ready jobs (no unsatisfied deps). It places each in a per-priority, per-tenant ready queue, and assigns ready jobs to workers: it picks the next job by fairness + priority + critical-path weight, matches it to a worker meeting its resource needs, writes a lease (worker id, expiry) to the metadata store, and dispatches. If no worker is free, it signals the autoscaler to grow the fleet.
  4. A worker (pulled from the warm pool or freshly provisioned) runs the job via its agent: check out the commit, mount declared input artifacts and caches, inject job-scoped secrets, run the commands in a sandbox, stream logs to the log pipeline, upload output artifacts to the content-addressed store, report exit status, and self-destruct. The agent heartbeats; if it dies, the lease expires and the scheduler reassigns (fencing prevents a zombie from double-committing).
  5. On success, the graph service marks the job done, re-evaluates downstream jobs (some become ready), and the scheduler assigns them - the DAG drains. When all jobs finish, the run’s aggregate status is computed and posted back to the SCM as a commit check. If the run includes a deploy job on a release branch, it hands the built artifact to the deploy controller, which promotes through staging and a canary, watches health, and auto-rolls-back on breach.

Request flow - a pull-request update: same path, but the config may select a different job set (PR-only checks), jobs run at higher interactive priority (a human is waiting), and the final status gates the merge button. Scheduled and manual triggers fan in identically; manual re-runs reuse cached results where inputs match.

The key architectural insight: a pipeline run is a scheduling problem over a pruned DAG, not a script execution. The graph service decides what must run (affected targets only) and in what order (dependency edges); the scheduler decides when and where each ready job runs under fairness and resource constraints; the workers are stateless, single-use executors that stream their outputs away and vanish. The scheduler is the heart - everything upstream feeds it a correct, minimal set of ready jobs, and everything downstream executes its assignments and reports back so the next wave of jobs unblocks.

Component Deep Dive

Four hard parts: (1) the dependency-aware scheduler - assigning a huge DAG to a finite fleet fast and fairly without starvation (the hardest problem); (2) affected-target computation - pruning a 40,000-target monorepo graph to the few hundred jobs a change could break, correctly; (3) ephemeral worker lifecycle - fast and hermetic provisioning with content-addressed caching; and (4) deploy with automated rollback - promoting an artifact safely and undoing it on a bad signal. I will walk each from naive to the real design.

1. The Dependency-Aware Scheduler: Assigning a DAG Fairly Without Starvation

This is the signature problem. You have a DAG of jobs (edges = “must finish before”), a finite elastic pool of workers, many concurrent pipelines from many tenants, and two goals in tension: finish each pipeline’s critical path fast and share the fleet fairly so no run starves. Naive approaches break on exactly this tension.

Approach A: FIFO queue of all ready jobs (the naive instinct)

Maintain one global queue. When a job becomes ready (all deps done), push it. Workers pull from the front. First-come-first-served.

on job_ready(j):   queue.push(j)
on worker_free(w): j = queue.pop_front(); assign(j, w)

Where it breaks: a single monorepo push dumps 20,000 ready jobs onto the front of the queue. Every other team’s two-job hotfix now sits behind 20,000 jobs and waits 40 minutes - head-of-line starvation, the cardinal CI sin. FIFO also ignores the critical path: it will happily run 500 leaf tests while the one long build on the critical path that unblocks the next stage waits its turn, so the pipeline’s total wall-clock balloons even when workers are free. And it ignores resource shape - it hands a GPU job to a CPU-only worker and stalls. A single global FIFO optimizes nothing that matters.

Approach B: Priority + critical-path weighting (closer, still unfair)

Replace FIFO with a priority queue. Score each ready job by its priority class (interactive PR job > scheduled nightly) and its critical-path length - the longest chain of remaining work downstream of it - so jobs that unblock the most future work run first.

score(j) = w_priority * priority_class(j)
         + w_cpath    * critical_path_remaining(j)   # longest downstream chain
assign highest-score ready job to a matching free worker
  • Progress: critical-path weighting (classic list scheduling) shortens each pipeline’s wall-clock - you run the job that unblocks the longest tail first, keeping the DAG’s frontier wide and workers busy on work that matters. Priority classes let a human-waited PR check jump ahead of a background nightly.
  • Where it still breaks: it is globally greedy, so it is still unfair across tenants. A monorepo run whose jobs all have long critical paths will out-score a small team’s short jobs forever - the big run monopolizes the fleet by virtue of being big. Priority alone does not bound any one tenant’s share, and critical-path weighting actively favors the giant graph. You have optimized each pipeline’s internal order but not the sharing between pipelines. Starvation is back, just more sophisticated.

Approach C: Hierarchical fair-share scheduling with critical-path ordering inside a tenant’s share

Schedule in two levels. First decide which tenant/run gets the next worker slot by fair share; then, within that tenant, pick which of its ready jobs by priority and critical path.

Level 1 - fair share across tenants (who runs next):
  each tenant has a WEIGHT (its guaranteed share of the fleet).
  track each tenant's RECENT USAGE (dominant-resource, decayed over time).
  pick the tenant whose (usage / weight) is lowest  -> fair queuing / DRF.
  reserve a slice of the fleet for INTERACTIVE jobs so PR checks never
  wait behind batch, regardless of share.

Level 2 - within the chosen tenant (what runs next):
  among that tenant's ready jobs, pick highest score by
  priority then critical-path-remaining then age.
  age/aging term guarantees anti-starvation: a job's effective
  priority rises the longer it waits, so nothing waits forever.

Then resource-match: assign to a free worker meeting the job's
  (cpu, mem, arch, gpu, special-label) requirements; if none, ask the
  autoscaler to provision that shape.
  • This is the real design and it resolves the tension. Level-1 fair share (weighted fair queuing on the dominant resource, a la DRF) guarantees every tenant their slice no matter how huge another tenant’s DAG is - the 20,000-job monorepo gets its fair portion of the fleet and no more, so the two-job hotfix runs now out of its own tenant’s share. Level-2 critical-path ordering keeps each run’s internal wall-clock short. The aging term is the hard anti-starvation guarantee: any job’s effective priority increases monotonically with wait time, so even the lowest-priority background job eventually runs - no job waits unboundedly. A reserved interactive slice means human-waited jobs get instant pickup even under a batch flood.
  • Make the ready-set cheap to maintain. The scheduler must not rescan the whole graph on every event. Track per-job an unsatisfied-dependency counter; when an upstream job completes, decrement the counters of its direct dependents, and any that hit zero move to ready. This is O(out-degree) per completion, not O(graph). The ready queues are indexed by tenant and priority so Level-1/Level-2 selection is a heap pop, not a scan.
  • Assignment must be exactly-once under worker death. Assigning a job writes a lease (worker id + expiry) in the metadata store via a conditional/compare-and-set write, so two scheduler replicas cannot assign the same job. The worker heartbeats to renew the lease; if it stops (crash, network partition), the lease expires and the job returns to ready for reassignment. A fencing token on the lease means a resurrected zombie worker’s late result-commit is rejected (its token is stale) - so a presumed-dead job that was actually still running cannot double-commit an artifact or a deploy. Exactly-once assignment; at-least-once execution that is safe because commits are fenced and idempotent.
  • Shard the scheduler, keep fairness global per tenant. At tens of thousands of jobs/sec of scheduling decisions, one scheduler process is a bottleneck. Shard by tenant (or repo) so each shard owns a disjoint set of runs and makes assignments independently; a tenant lives on one shard so its fair-share accounting is consistent. A thin global capacity broker hands fleet slots to shards in proportion to demand so cross-tenant fairness holds without a global lock on every decision.

The scheduler answer: two-level hierarchical scheduling - weighted fair share across tenants (dominant-resource fair queuing with a reserved interactive slice) to guarantee no run starves, and critical-path-weighted priority within a tenant to keep each pipeline’s wall-clock short - with an aging term for hard anti-starvation, dependency-counter bookkeeping so the ready set is maintained in O(out-degree), leased-and-fenced assignment for exactly-once scheduling under worker death, and per-tenant sharding with a capacity broker so it scales horizontally while fairness stays global.

2. Affected-Target Computation: Pruning the Monorepo Graph Correctly

In a monorepo, “run everything on every push” is minutes-to-hours and enormous cost. The win is running only jobs a change could have broken - but getting the pruning wrong (missing an affected target) ships a bug, so it must be sound.

Approach A: Run every job every time (naive baseline)

Ignore the change; expand the full pipeline and run all 40,000 targets.

Where it breaks: a 3-file change triggers hours of builds and tests and burns the fleet, so developers wait forever and the cost is absurd. Worse, it trains people to ignore CI (flaky, slow, always red somewhere), which defeats the point. Running everything is correct but economically and ergonomically broken at monorepo scale.

Approach B: Path-based rules (closer, but unsound)

Let teams write rules: “if files under services/foo/** change, run foo’s jobs.” Map changed paths to job sets with globs.

  • Progress: cheap and simple; a change to one service runs only that service’s tests. Works for loosely-coupled repos.
  • Where it breaks: it is unsound for a real dependency graph. If services/foo depends on libs/common and someone changes libs/common, the path rule for foo does not fire unless a human remembered to list libs/common as a trigger for foo - so you skip a job that the change actually broke and ship a bug. Hand-maintained path rules drift out of sync with the real dependency edges the instant anyone refactors. Pruning that can miss affected targets is worse than running everything, because it is silently wrong.

Approach C: Reverse-dependency closure over the real build graph

Derive affected targets from the actual dependency graph the build system already knows, not from hand-written rules:

1. Changed files  = diff(pushed_commit, merge_base)
2. Directly-hit targets = targets whose SOURCE INPUTS include a changed file
   (the build tool maps files -> targets that consume them)
3. Affected set = reverse-dependency CLOSURE of the hit targets:
   everything that transitively DEPENDS ON a hit target, because a change
   to a dependency can break its dependents.
   affected = {} ; stack = directly_hit
   while stack: t = pop; for d in reverse_deps(t): if d not in affected:
       add d; push d
4. Jobs to run = test/build jobs whose target is in `affected`,
   plus the build steps those jobs depend on (forward deps, to produce inputs).
5. Also invalidate on NON-source inputs: a change to the pipeline config,
   a toolchain version, or a base image busts the relevant cache keys and
   forces re-run, so you never skip because "no source changed" when the
   environment changed.
  • This is sound because it follows the true edges. The build graph (from Bazel/Buck/an internal build system, or a computed import/dependency graph) is the ground truth for “X depends on Y”. Taking the reverse-dependency closure of changed targets yields exactly the set that could be affected - no more (you do not run unrelated services) and no less (you do not miss a dependent of a changed library). Refactors update the graph automatically, so there is nothing to drift.
  • Make the closure fast. The graph has tens of thousands of nodes; computing the reverse-dep closure per push must be milliseconds. Precompute and cache the reverse-dependency index (target -> its dependents), updated incrementally as the graph changes, so a push is a BFS over the affected frontier (hundreds of nodes), not a full-graph traversal. Query the build tool’s own query interface where available rather than reimplementing it.
  • Content-addressed cache keys turn “affected” into “actually changed”. Even within the affected set, a target whose transitive inputs hash to a value already built successfully does not need to re-run - mark it cached and reuse its result. The cache key is hash(target source + all transitive dependency outputs + toolchain + build flags); a hit is provably the same build, so reuse is sound, not a guess. This is what collapses “500 affected” down to “40 actually need to run” when most of the closure was unchanged in substance.
  • Fail safe, not silent. If the affected-target computation cannot be done confidently (graph unavailable, an unparseable change, a BUILD file edited that could change edges broadly), fall back to running the broader set (or everything in the touched package subtree) rather than skipping. The invariant is “never skip a job the change could have broken”; when in doubt, run more, because a missed test is a shipped bug.

The affected-target answer: compute the reverse-dependency closure of changed targets over the real build graph (sound by construction, auto-updating with refactors), accelerate it with a cached incremental reverse-dep index, then shrink the surviving set further with content-addressed cache keys so only genuinely-changed targets re-run - and fail safe to a broader set whenever the graph or the change cannot be analyzed confidently.

3. Ephemeral Worker Lifecycle: Fast and Hermetic at Once

Every job needs a clean environment, provisioned in seconds (for feedback latency) yet fully isolated and single-use (for security and correctness). These two goals pull against each other.

Approach A: A fixed pool of reused, long-lived workers (naive)

Keep N persistent VMs. Route a job to a free one, run it, leave the box as-is, hand it to the next job.

Where it breaks: no hermeticity. Job 2 inherits job 1’s leftover files, environment variables, installed packages, and - catastrophically - any secret or artifact job 1 left on disk, so a build can read another team’s credentials or be poisoned by a malicious prior job. State accumulates: caches grow stale, disk fills, “works on worker 7 but not worker 12” flakiness appears. Reusing workers is fast but fails the isolation NFR outright - it is a security incident waiting to happen.

Approach B: A fresh worker per job, provisioned cold (correct, too slow)

For every job, provision a brand-new VM/container, run the job, destroy it.

  • Progress: perfect hermeticity - every job starts clean and nothing survives it. This is the right correctness model.
  • Where it breaks: cold provisioning is slow. Booting a VM, pulling a multi-GB toolchain image, and checking out a large monorepo can take minutes - which destroys time-to-first-feedback and, multiplied across millions of jobs, wastes enormous compute on setup. Correct but, done naively, far too slow and expensive. The challenge is keeping the clean-per-job guarantee while cutting the setup cost.

Approach C: Warm pool of pre-baked, single-use workers with content-addressed caches

Keep hermeticity (single-use, destroyed after one job) but attack every slow step:

  • Warm pool, not cold boot. Maintain a pool of pre-provisioned, idle workers already booted on pre-baked base images (toolchains, runtimes, common dependencies baked in). Assigning a job grabs a warm worker - seconds, not minutes - and the autoscaler refills the pool ahead of demand based on queue depth and time-of-day patterns. The worker is still single-use: after the job it is destroyed, and a fresh warm one takes its place. You get cold-start hermeticity at warm-start speed.
  • Hermetic isolation per job. Each job runs in its own sandbox - a container with a fresh overlay filesystem on the pre-baked base (so the base is shared read-only, the job’s writes are a throwaway layer), or a microVM for untrusted/multi-tenant isolation (own kernel, no shared mutable state). Secrets are injected into the job’s environment at dispatch, scoped to that job, held in memory, never written to the shared image or logs, and gone when the sandbox dies. One worker runs exactly one job and never touches another tenant’s data.
  • Content-addressed caches make setup cheap without sharing mutable state. The expensive inputs - dependency downloads, compiler outputs, the checkout - are served from a content-addressed cache (keyed by input hash) mounted read-only into the job. A cache entry is immutable (its key is its content hash), so a job cannot poison another tenant’s cache - it can only produce new immutable entries. A large monorepo checkout uses a shared, read-only base snapshot plus a sparse/partial checkout of only the affected paths, not a full clone every time. The job reads shared immutable caches but writes only to its throwaway layer.
  • Stream outputs off the worker immediately. Logs are streamed to the log pipeline line-by-line (not held on the worker and uploaded at the end), and artifacts are uploaded to the content-addressed store as produced, so a worker that crashes mid-job loses nothing already streamed and the scheduler can reassign cleanly. The worker holds no durable state; it is a pure, disposable executor.
  • Right-size and label workers. Jobs declare resource needs (cpu/mem/arch/gpu/special labels); the pool is heterogeneous and the scheduler resource-matches (part 1). The autoscaler keeps a small warm pool of each common shape and provisions rare shapes (GPU) on demand, trading a little extra latency on rare jobs for not paying for idle GPUs.

The worker answer: single-use, destroyed-after-one-job workers for hermeticity, drawn from a predictively-refilled warm pool of pre-baked base images so provisioning is seconds not minutes, isolated per job via fresh overlay FS or microVM with job-scoped in-memory secrets, fed by read-only content-addressed caches and sparse checkouts so setup is cheap and no tenant can poison another, with logs and artifacts streamed off the worker so a crash loses nothing and the job reassigns cleanly.

4. Deploy With Automated Rollback: Changing Production Safely

A passing pipeline on a release branch must get the artifact into production without taking the service down, and undo itself automatically when a bad build slips through tests.

Approach A: Replace all instances at once on green (naive)

Pipeline passes, push the new artifact to every production instance simultaneously, done.

Where it breaks: tests never catch everything - a config difference, a load-only bug, a bad migration surfaces only in production. An all-at-once replace means a bad build is 100% of traffic instantly, a full outage, and rollback is a panicked manual redeploy of the old version while customers are down. No blast-radius control and no automatic undo. Big-bang deploys turn every escaped bug into a full incident.

Approach B: Progressive canary rollout with health-gated promotion and auto-rollback

Roll out in stages, watch health at each, and promote or roll back automatically:

promote(artifact):
  1. deploy to STAGING, run smoke/integration gate -> must pass to proceed
  2. CANARY: route a small % (e.g. 1-5%) of prod traffic to the new version,
     keep the rest on last-good.
  3. Watch health signals for a bake window: error rate, p99 latency,
     saturation, key business metrics - compared against the stable version
     (A/B), not an absolute threshold, so you catch relative regressions.
  4. if any signal breaches -> AUTO-ROLLBACK: shift 100% back to last-good,
     mark the deploy failed, alert, stop. No human needed to stop the bleed.
  5. if healthy -> widen in steps (5% -> 25% -> 50% -> 100%), re-checking
     health at each step; a breach at any step rolls back.
  6. on 100% healthy, the new version becomes LAST-GOOD and is retained
     as the next rollback target.
  • This bounds blast radius and removes the human from the emergency path. A bad build hits only the canary slice before the health gate catches it and rolls back, so an escaped bug is a 1-5% blip for a few minutes, not a full outage. Comparative canary analysis (new vs stable on the same live traffic) catches regressions an absolute threshold would miss - the canary getting 2x the stable version’s error rate fails even if it is “under 1%”. Automated rollback means mean-time-to-recovery is the bake window, not however long it takes to page a human.
  • Keep the last-good artifact and make rollback a routing flip, not a rebuild. The previous version stays deployed (or instantly re-deployable from a retained, content-addressed artifact) so rollback is shifting traffic back, which is seconds, not rebuilding and redeploying, which is minutes. The deploy controller records the last-good version per environment as a first-class pointer.
  • Handle the stateful hazards deploys actually hit. Database migrations are the sharp edge: a rollback of code must not strand a forward-only schema change. Enforce backward-compatible, expand/contract migrations (add columns/tables first, deploy code that tolerates both shapes, contract only after the new code is fully stable) so code can roll back without a schema rollback. Make deploy steps idempotent (re-applying the same artifact is a no-op) because the pipeline may retry. Hold a per-environment deploy lock/lease so two pipelines cannot promote to production concurrently and clobber each other - exactly-once successful promotion per environment even though jobs can re-run.
  • Gate promotion on the true aggregate result. The deploy job runs only after the pipeline’s status is conclusively green (all required checks done, status monotonic - part of the consistency NFR), so you never promote on a partial or flapping result. Manual-approval gates (a human clicks “ship to prod”) slot in as a job dependency for teams that want them, without changing the mechanism.

The deploy answer: progressive canary rollout with comparative health analysis (new vs stable on live traffic) and automated rollback on breach so an escaped bug is a brief small-slice blip not an outage; a retained last-good artifact so rollback is a seconds-scale routing flip; backward-compatible expand/contract migrations and idempotent steps so code can roll back without stranding data; and a per-environment deploy lease plus a conclusively-green gate so promotion is exactly-once and never on a partial result.

API Design & Data Schema

Pipeline / control API

POST /v1/webhooks/{scm}                         # SCM event sink (push, PR, tag)
  Headers: X-Signature, X-Delivery-Id           # verify + dedup
  Body: <SCM event payload>
  -> 200 { "accepted": true, "run_id": "run_7Qd2" }   # or 200 dedup no-op

POST /v1/repos/{repo}/runs                       # manual / API trigger
  { "ref": "refs/heads/main", "commit": "abc123",
    "reason": "manual", "inputs": { "deploy": true } }
  -> 201 { "run_id": "run_7Qd2", "state": "building_graph" }

GET  /v1/runs/{run_id}                           # run status + job summary
  -> 200 { "state": "running", "jobs_total": 212, "jobs_done": 180,
           "jobs_failed": 0, "critical_path_eta_s": 95 }

GET  /v1/runs/{run_id}/jobs                       # all jobs + statuses + edges
GET  /v1/jobs/{job_id}                            # one job: status, worker, timing
GET  /v1/jobs/{job_id}/logs?follow=true           # stream logs (SSE/chunked)
POST /v1/runs/{run_id}/cancel                     # cancel run -> cancel ready/running jobs
POST /v1/jobs/{job_id}/retry                      # re-run one job (reuses cache if valid)

Deploy API

POST /v1/deploys                                  # promote an artifact
  { "artifact_ref": "cas://sha256:abc...", "env": "production",
    "strategy": "canary", "steps": [1,5,25,50,100], "bake_s": 300 }
  -> 202 { "deploy_id": "dep_9x", "state": "staging" }

GET  /v1/deploys/{deploy_id}                      # state, current %, health verdict
POST /v1/deploys/{deploy_id}/rollback             # manual rollback (auto also exists)
  -> 200 { "state": "rolling_back", "target": "last_good:v41" }

Internal scheduler / agent contract (not public)

CLAIM(worker_id, capabilities)  -> job assignment (job_id, lease, inputs) | NONE
  # scheduler leases a ready job to a worker matching capabilities
HEARTBEAT(worker_id, job_id, fencing_token) -> renew lease | REVOKED
REPORT(job_id, fencing_token, {exit_code, artifacts[], test_summary})
  # fenced: stale token (zombie worker) -> rejected
READY_FANOUT(job_id)  # on completion, decrement dependents' dep-counters
PROVISION(shape, count)  # autoscaler grows warm pool of a worker shape

Data model

runs (relational - one row per pipeline run):

run_id           STRING   PRIMARY KEY
repo_id          STRING   INDEX
tenant_id        STRING   INDEX          # team/org - the fair-share unit
commit_sha       STRING
ref              STRING                  # branch/tag
trigger          ENUM     # push | pr | tag | manual | schedule
state            ENUM     # building_graph | running | success | failed | cancelled
jobs_total       INT
created_at, finished_at  TIMESTAMP

INDEX idx_tenant_time (tenant_id, created_at)   # a team's recent runs
INDEX idx_repo_commit (repo_id, commit_sha)

jobs (relational / fast KV - hot during a run, read+written per state change):

job_id           STRING   PRIMARY KEY
run_id           STRING   INDEX
name             STRING                  # e.g. "test //services/foo:unit"
target           STRING                  # build target for cache keying
state            ENUM     # blocked | ready | assigned | running | done
                          #        | failed | cached | cancelled
dep_unsatisfied  INT                     # counter: 0 => ready (part 1)
depends_on       LIST<job_id>            # DAG edges (also a dependents index)
cache_key        STRING   INDEX          # hash(inputs); hit => skip
priority_class   ENUM     # interactive | normal | batch
cpath_remaining  INT                     # critical-path weight for scheduling
requirements     JSON                    # {cpu, mem, arch, gpu, labels}
lease_worker     STRING                  # current worker id (if assigned)
lease_expiry     TIMESTAMP               # lease fence
fencing_token    BIGINT                  # monotonically increasing per assignment
artifact_refs    LIST<STRING>            # content-addressed outputs
started_at, finished_at  TIMESTAMP

INDEX idx_run_state (run_id, state)             # drive the ready-set per run
INDEX idx_ready (tenant_id, priority_class, state)  # scheduler ready queues

artifacts / cache (content-addressed - object store + index):

content_hash     STRING   PRIMARY KEY     # sha256 of the content = the key
size_bytes       BIGINT
kind             ENUM     # build_output | test_report | image | cache_blob
blob_ref         STRING                   # pointer into object storage
refcount         INT                      # for GC when no run references it
created_at       TIMESTAMP
# immutable: same content -> same key -> dedup. Reuse is provably safe.

deploys (relational - deploy state machine + rollback target):

deploy_id        STRING   PRIMARY KEY
env              STRING   INDEX            # staging | production (lease unit)
artifact_ref     STRING
state            ENUM     # staging | canary | rolling_out | success
                          #        | rolling_back | failed
current_pct      INT
last_good_ref    STRING                    # retained rollback target
health_verdict   JSON                      # per-step error/latency comparison
lock_lease       STRING                    # per-env deploy lease (one at a time)
created_at, finished_at  TIMESTAMP

SQL vs NoSQL - the choice and why. Run/job/deploy state is relational and transactional: a job’s state transitions, lease writes, and dependency-counter decrements need conditional/atomic updates (compare-and-set for exactly-once assignment) and consistent reads (the deploy gate must see the true aggregate), so a sharded relational store (Postgres/an internal transactional KV), sharded by tenant_id, fits - SQL for the control plane and scheduler state. The hot job/lease rows are also fronted by an in-memory layer in the scheduler shard that owns them, because scheduling decisions happen thousands/sec and cannot pay a DB round-trip per decision - the DB is the durable source of truth, the shard holds the live ready-queues. Artifacts, caches, and logs are large, immutable, and content-addressed - object storage with a small index table, deduped by content hash, GC’d by refcount; never a transactional DB. Logs stream to object storage plus a search index. The deciding factor is the access pattern: transactional-state-with-conditional-writes -> SQL (plus in-memory for the hot scheduler path); large-immutable-content -> content-addressed object store; append-and-search -> log store.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. One giant pipeline starves everyone (head-of-line blocking). A 20,000-job monorepo run swamps a FIFO fleet and a two-job hotfix waits 40 minutes. Fix: hierarchical fair-share scheduling - weighted fair queuing across tenants (dominant-resource) so each team gets its slice regardless of another’s graph size, critical-path ordering within a tenant for short wall-clock, an aging term for hard anti-starvation, and a reserved interactive slice so PR checks never wait behind batch. This is the single most important design decision.

2. Running everything on every push. Full monorepo builds are hours and burn the fleet. Fix: reverse-dependency-closure affected-target pruning over the real build graph (sound, auto-updating) to run only jobs a change could break (~200x less on the common change), then content-addressed cache keys to skip targets whose inputs are unchanged - “affected” shrinks to “actually changed”. Fail safe to a broader set when the graph can’t be analyzed.

3. Cold worker provisioning kills feedback latency. Booting a VM + pulling images + full checkout is minutes. Fix: warm pool of pre-baked base images refilled predictively on queue depth, content-addressed read-only caches and sparse checkouts so setup is cheap, workers still single-use and destroyed for hermeticity. Seconds-to-first-job without giving up isolation.

4. Scheduler throughput. One scheduler can’t make tens of thousands of assignment decisions/sec. Fix: shard the scheduler by tenant/repo (disjoint run ownership, consistent per-tenant fair-share), a thin global capacity broker apportions fleet slots to shards so cross-tenant fairness holds without a global lock; maintain ready-sets in O(out-degree) via dependency counters, not graph rescans.

5. Double execution on worker death. A presumed-dead worker that’s actually alive could double-commit an artifact or a deploy. Fix: leased assignment with compare-and-set (one assignment wins), heartbeat-renewed leases (expire -> reassign), and a fencing token so a zombie’s late commit is rejected. Exactly-once assignment; at-least-once execution made safe by fencing + idempotent, content-addressed commits.

6. Cache correctness and poisoning. A shared mutable cache lets one tenant corrupt another’s build or lets stale inputs produce a wrong “pass”. Fix: content-addressed, immutable caches mounted read-only (key = content hash, so reuse is provably the same build and no job can mutate another’s entry); cache key includes toolchain, flags, and config, so an environment change busts it. New entries only ever add, never overwrite.

7. Artifact / log storage and hot keys. 25 TB/day of artifacts and a popular base image or cache blob is read by thousands of jobs. Fix: content-addressed object storage with dedup (a cache hit writes nothing), tiered retention (per-run short, release artifacts long), refcount GC; replicate/CDN-cache hot read-only blobs (base images, common deps) near workers so a popular blob isn’t a single hot shard; stream logs off workers so a crash loses nothing.

8. Bad build reaches 100% of production. Tests miss a load/config/migration bug. Fix: progressive canary with comparative health analysis (new vs stable on live traffic) and automated rollback on breach so an escaped bug is a small-slice blip; retained last-good artifact so rollback is a routing flip (seconds); expand/contract backward-compatible migrations so code rolls back without stranding schema.

9. Concurrent deploys clobber each other. Two pipelines promote to prod at once. Fix: per-environment deploy lease (one promotion at a time), idempotent deploy steps, and promotion gated on a conclusively-green, monotonic run status so you never ship on a partial or flapping result - exactly-once successful promotion per environment.

10. Event ingest drops a webhook. A lost push event means a change ships untested. Fix: durable, idempotent ingest - verify signature, dedup by delivery id (webhooks are at-least-once), enqueue durably, return 200 fast; a reconciliation poller backfills from the SCM API so a missed webhook is caught. Never build the graph synchronously in the webhook handler.

11. Secret leakage across jobs. A build reads another tenant’s credentials or leaks a secret to logs/artifacts. Fix: single-use workers destroyed after one job, job-scoped secrets injected in-memory at dispatch (never on the base image, never persisted), log/artifact redaction of known secret patterns, and microVM isolation for untrusted multi-tenant builds so there is no shared mutable surface to leak through.

12. Flaky tests and poison jobs. A job that reliably fails (or flakes) burns worker time and blocks the DAG. Fix: retry with backoff and an attempt cap (then mark failed, don’t cycle the fleet), quarantine detected-flaky tests out of the gating set with an alert to the owner, and circuit-break a target that fails to even build so it stops consuming workers; a failed job fails its dependents fast rather than leaving them blocked forever.

Wrap-Up

The trade-offs that define this design:

  • A pipeline run is a scheduling problem over a pruned DAG, not a script. The product’s quality is the scheduler’s quality - how fast it finishes each critical path while fairly sharing a finite elastic fleet and never starving anyone. Hierarchical fair-share (across tenants) plus critical-path ordering (within a tenant) plus an aging term is the whole ballgame; a FIFO or a globally-greedy priority queue both let the giant monorepo run starve the small hotfix.
  • Prune soundly or not at all. Reverse-dependency closure over the real build graph is the only pruning that is safe (it follows the true edges and auto-updates with refactors); path-rule pruning silently misses affected targets and ships bugs. Content-addressed cache keys then shrink “affected” to “actually changed”, and when in doubt you run more, because a skipped job is a shipped bug.
  • Hermeticity and speed are reconciled by a warm pool of single-use workers. Reusing workers is fast but leaks state and secrets across tenants; cold-provisioning per job is clean but minutes slow. A predictively-refilled warm pool of pre-baked images, destroyed after one job, with read-only content-addressed caches and sparse checkouts, gives cold-start isolation at warm-start speed.
  • Exactly-once lives in assignment and promotion, not in user code. Leased, fenced job assignment gives exactly-once scheduling under worker death; per-environment deploy leases plus idempotent steps give exactly-once successful promotion; everything in between is at-least-once execution made safe by content-addressing and idempotency, because jobs and events both retry.
  • Deploy is reversible by construction. Progressive canaries with comparative health gating bound the blast radius of an escaped bug to a small slice, automated rollback makes recovery the bake window not a human page, a retained last-good artifact makes rollback a routing flip, and expand/contract migrations keep data from stranding a code rollback.

One-line summary: a durable event-ingest front end feeds a graph service that prunes each change to its reverse-dependency-affected jobs, a sharded two-level scheduler (fair share across tenants, critical-path order within) leases those jobs - exactly-once, fenced - onto a warm pool of single-use hermetic workers fed by content-addressed caches, and a deploy controller promotes the resulting artifact through health-gated canaries with automated rollback, so thousands of pipelines share one elastic fleet fast, fairly, and safely.