Caching and Parallelism

The previous lesson versioned and retained the output the pipeline produces: every run’s output sits under its own identity, and which change gave birth to it can be read. One thing was never counted — how many minutes that output took to produce. The pipeline runs every stage from scratch on every run, yet most stages’ inputs never change between two runs.

This lesson measures the pipeline’s own duration. Two levers are available: not rerunning a stage that does the same work on the same input — stage caching — and running stages that do not depend on each other at the same time — parallelism. Both have a limit, and the limits do not sit in the same place. The gate measure is two-edged here: when a stage comes from the cache, that gate does not run at all, and what the gate misses is born exactly there.

PD25. The pipeline is a model set up with node. Stage durations are the nominal values the model declares, not measured from the machine the run happens on; the environment-independent quantities are the number of stages that ran, the number of hits, and the cache entries. PD26. The stage key is computed from real files: files are written to disk, read, and hashed. PD27. The change sequence stands in for the fictional regional measurement network’s two-week patch flow; there is no randomness, the sequence is hand-written. PD28. The defect set is eight defects, and which gates can catch each one is declared; a gate that runs catches its own defect, a gate that does not run does not. PD29. Cache entries are never deleted, and no retention rule is applied. PD30. Runners are identical and queue wait is zero — that item is measured in the next lesson.

The caching of image layers was measured outside this course and is not repeated here; the unit measured here is the pipeline stage — a unit of work with its own input, its own duration, and its own output.

The Stage Key

The cache has a single rule: a stage’s key must cover everything that could change that stage’s result. When an input that is not covered changes, the key stays the same, the stage does not run, and the pipeline mistakes the old result for correct. In the model, every stage declares its own inputs.

// measurement-network/pipeline.mjs — pipeline stages and stage caching (model)
import { mkdirSync, writeFileSync, readFileSync, readdirSync, statSync, appendFileSync, rmSync } from "node:fs";
import { createHash } from "node:crypto";

const ROOT = "project";
const hash = (s) => createHash("sha256").update(s).digest("hex").slice(0, 12);
const text = (name, n) => Array.from({ length: n }, (_, i) => `// ${name} ${i}\n`).join("");
const TREE = {
  "dependency-list": "measurement-client 3.1\nqueue-connector 1.9\ncsv-parser 2.4\n",
  "src/collector.js": text("collector", 260), "src/verifier.js": text("verifier", 180),
  "src/billing.js": text("billing", 240), "test/unit/collector.js": text("unit", 300),
  "test/integration/flow.js": text("integration", 220), "test/contract/api.js": text("contract", 90),
  "config/env.json": '{"timeout":30}\n', "rules/static.json": '{"rule-count":48}\n',
  "contracts/api.json": '{"field-count":17}\n',
};

// duration: declared nominal stage duration (seconds). base: output written to the cache (bytes).
// inputs: what the stage DECLARES as its inputs — rules/ and contracts/ are declared by no stage.
export const STAGES = [
  { name: "dependency-resolution", inputs: ["dependency-list"], deps: [], duration: 42, base: 41e6 },
  { name: "build", inputs: ["src"], deps: ["dependency-resolution"], duration: 65, base: 8.6e6 },
  { name: "static-analysis", inputs: ["src"], deps: ["dependency-resolution"], duration: 27, base: 12e4 },
  { name: "unit-test", inputs: ["test/unit"], deps: ["build"], duration: 38, base: 9e4 },
  { name: "integration-test", inputs: ["test/integration", "config"], deps: ["build"], duration: 96, base: 26e4 },
  { name: "packaging", inputs: ["config"], deps: ["build"], duration: 18, base: 9.1e6 },
  { name: "contract-test", inputs: ["test/contract"], deps: ["packaging"], duration: 31, base: 6e4 },
  { name: "image-build", inputs: [], deps: ["packaging"], duration: 24, base: 12.3e6 },
];
export const RESTORE = 2; // seconds to restore an output from the cache on every hit
export const SERIAL = STAGES.reduce((t, s) => t + s.duration, 0);

export const buildTree = () => {
  rmSync(ROOT, { recursive: true, force: true });
  for (const [p, content] of Object.entries(TREE)) {
    mkdirSync(`${ROOT}/${p}`.split("/").slice(0, -1).join("/"), { recursive: true });
    writeFileSync(`${ROOT}/${p}`, content);
  }
};
export const modify = (path, no) => appendFileSync(`${ROOT}/${path}`, `// fix ${no}\n`);
const walk = (sub) => readdirSync(`${ROOT}/${sub}`, { withFileTypes: true })
  .flatMap((g) => (g.isDirectory() ? walk(`${sub}/${g.name}`) : [`${sub}/${g.name}`])).sort();
const paths = (p) => (statSync(`${ROOT}/${p}`).isDirectory() ? walk(p) : [p]);

// Stage key: stage name + the real content of the declared inputs + the previous stages' keys.
export const runPipeline = (cache) => {
  const key = {}, result = { hits: [], ran: [], duration: 0 };
  for (const s of STAGES) {
    const files = s.inputs.flatMap(paths);
    key[s.name] = hash(s.name + files.map((p) => p + readFileSync(`${ROOT}/${p}`)).join() +
      s.deps.map((dep) => key[dep]).join());
    if (cache.has(key[s.name])) { result.hits.push(s.name); result.duration += RESTORE; continue; }
    cache.set(key[s.name], s.base + files.reduce((t, p) => t + statSync(`${ROOT}/${p}`).size, 0));
    result.ran.push(s.name); result.duration += s.duration;
  }
  return result;
};

Feeding the prior stages’ keys into a stage’s own key builds a chain: when a stage misses, every stage depending on it misses too, even if its own input has not changed. This is the cache’s correct side; its wrong side is in the declaration list — rules/ and contracts/ are real inputs to the pipeline, but no stage declares them.

Twelve Runs

The sequence runs the fictional network’s patch flow across twelve runs: source and test changes, a dependency list, a config, a run where nothing changes, and two changes touching undeclared directories. Eight defects are scattered through the sequence.

// measurement-network/run.mjs — a twelve-run change sequence, cached and uncached
import { buildTree, modify, runPipeline, STAGES, SERIAL } from "./pipeline.mjs";

// Fictional two-week sequence: file touched, change category, defect carried, gates that
// could catch the defect. No randomness; the sequence is hand-written.
const SEQUENCE = [
  ["", "first run"], ["src/collector.js", "src", "D1", ["unit-test", "integration-test"]],
  ["src/verifier.js", "src", "D2", ["static-analysis"]], ["test/unit/collector.js", "test"],
  ["", "no change"], ["dependency-list", "dependency", "D3", ["integration-test"]],
  ["rules/static.json", "rule", "D4", ["static-analysis"]],
  ["src/billing.js", "src", "D5", ["unit-test", "static-analysis"]],
  ["config/env.json", "config"], ["contracts/api.json", "contract", "D6", ["contract-test"]],
  ["test/integration/flow.js", "test", "D7", ["integration-test"]],
  ["src/collector.js", "src", "D8", ["unit-test"]],
];

buildTree();
const cache = new Map(), category = {}, missed = [];
const gates = Object.fromEntries(STAGES.map((s) => [s.name, { runs: 0, duration: 0, held: 0, alone: 0 }]));
let totalHits = 0, totalDuration = 0;

console.log(" no  change".padEnd(33) + "category".padEnd(15) + "hits ran dur(s)");
SEQUENCE.forEach(([file, cat, defect, catchableBy], i) => {
  if (file) modify(file, i);
  const r = runPipeline(cache);
  totalHits += r.hits.length; totalDuration += r.duration;
  category[cat] = category[cat] || { attempts: 0, hits: 0 };
  category[cat].attempts += STAGES.length; category[cat].hits += r.hits.length;
  for (const name of r.ran) { gates[name].runs++; gates[name].duration += STAGES.find((s) => s.name === name).duration; }
  if (defect) {
    const caught = catchableBy.filter((name) => r.ran.includes(name));
    if (!caught.length) missed.push(defect);
    else for (const name of caught) { gates[name].held++; if (caught.length === 1) gates[name].alone++; }
  }
  console.log(`  ${String(i + 1).padStart(2)}  ${file || "(" + cat + ")"}`.padEnd(33) + cat.padEnd(15) +
    String(r.hits.length).padStart(4) + String(r.ran.length).padStart(6) + String(r.duration).padStart(7));
});

const attempts = SEQUENCE.length * STAGES.length, uncached = SEQUENCE.length * SERIAL;
console.log(`\nuncached ${uncached} s, cached ${totalDuration} s (${(100 - (totalDuration * 100) / uncached).toFixed(1)}% shorter); ` +
  `hits ${totalHits}/${attempts} (${((totalHits * 100) / attempts).toFixed(1)}%); ` +
  `cache ${cache.size} entries ${([...cache.values()].reduce((a, b) => a + b, 0) / 1e6).toFixed(1)} MB`);
console.log("\nhits / change category" + " ".repeat(10) + "gate                    runs  dur  held  alone");
const rows = Object.entries(category).map(([cat, d]) => `  ${cat.padEnd(15)}${d.hits}/${d.attempts} ${((d.hits * 100) / d.attempts).toFixed(0)}%`);
STAGES.forEach((s, i) => {
  const g = gates[s.name];
  console.log((rows[i] || "").padEnd(33) + s.name.padEnd(24) + String(g.runs).padStart(3) +
    String(g.duration + "s").padStart(7) + String(g.held).padStart(7) + String(g.alone).padStart(8));
});
console.log(`\ndefect set 8, missed ${missed.length}: ${missed.join(", ")} — undeclared input, stale hit`);

 no  change                      category       hits ran dur(s)
   1  (first run)                first run         0     8    341
   2  src/collector.js           src               1     7    301
   3  src/verifier.js            src               1     7    301
   4  test/unit/collector.js     test              7     1     52
   5  (no change)                no change         8     0     16
   6  dependency-list            dependency        0     8    341
   7  rules/static.json          rule              8     0     16
   8  src/billing.js             src               1     7    301
   9  config/env.json            config            4     4    177
  10  contracts/api.json         contract          8     0     16
  11  test/integration/flow.js   test              7     1    110
  12  src/collector.js           src               1     7    301

uncached 4092 s, cached 2273 s (44.5% shorter); hits 46/96 (47.9%); cache 50 entries 287.4 MB

hits / change category          gate                    runs  dur  held  alone
  first run      0/8 0%          dependency-resolution     2    84s      0       0
  src            4/32 13%        build                     6   390s      0       0
  test           14/16 88%       static-analysis           6   162s      2       1
  no change      8/8 100%        unit-test                 7   266s      3       1
  dependency     0/8 0%          integration-test          8   768s      3       2
  rule           8/8 100%        packaging                 7   126s      0       0
  config         4/8 50%         contract-test             7   217s      0       0
  contract       8/8 100%        image-build               7   168s      0       0

defect set 8, missed 2: D4, D6 — undeclared input, stale hit

Reading the Hit Rate

Total duration drops from 4,092 seconds to 2,273 seconds: a 44.5 percent reduction, 46 hits in 96 stage attempts. This single number carries no decision on its own; the decision comes from the distribution by category.

For test changes, the hit rate is 88 percent — touching one test file only runs that one test stage. For source changes, the hit rate drops to 13 percent: source sits at the bottom of the chain, and touching it reruns seven stages. For a dependency-list change, the hit rate is zero; that file is the input of the very bottom stage and invalidates the entire pipeline. The gain depends on which layer of the pipeline is touched, and how often.

Only one of the three rows showing 100 percent is correct. In the run where nothing changes, eight of eight stages hit and the pipeline finishes in 16 seconds; that is exactly what the cache is supposed to do. Rule and contract changes also show eight hits — but something has changed there. rules/static.json is the rule set for static analysis, contracts/api.json is the contract test’s criterion; neither is an input any stage declares. The key does not change, the gate does not run, the pipeline finishes green. The two change types with the highest hit rate are the ones the cache cannot see.

The gate account writes down the cost of this. Six of eight defects are caught, two escape: D4 is a defect that becomes visible when the rule set is tightened, D6 is born from a change in the contract field; both pass through because the gate that could catch them came from the cache. The marginal-value column separates the gates: the integration test spends 768 seconds across eight runs, holds three defects, and catches two of them alone — it is the most expensive and most necessary gate in the pipeline. The unit test holds three defects in 266 seconds, but only one of them alone; of the other two, one would also have been caught by the integration test and the other by static analysis. Four stages — dependency resolution, build, packaging, image build — never hold a defect; they are production steps, not gates, and they do not enter this accounting.

If the declaration is fixed, the cost can be read off the table: on the seventh run, static analysis takes 27 seconds instead of a 2-second hit; on the tenth run, the contract test takes 31 instead of 2. The total is 54 seconds, 2.4 percent of the cached duration — in exchange, two defects do not escape.

The cache’s own cost has three items. Storage: across twelve runs, 50 entries and 287.4 MB accumulate, none of them ever deleted. Restore: each of the 46 hits costs 2 seconds, 92 seconds in total. The third item does not reduce to a number, and it is the most expensive — the two defects that escaped above are the bill for the invalidation error.

The Critical Path

Caching removed the repeated work; the remaining work still runs in a single line. The stages form a dependency graph, the ones that do not depend on each other can run at the same time, and the graph’s longest chain sets the limit.

// measurement-network/parallel.mjs — stage graph, runner count, and the critical path
import { STAGES, RESTORE } from "./pipeline.mjs";

const find = (name) => STAGES.find((s) => s.name === name);
const successors = (name) => STAGES.filter((b) => b.deps.includes(name));
// Longest remaining duration from a stage to the pipeline's end; the critical path is the chain whose head is largest.
const remaining = (s) => s.duration + Math.max(0, ...successors(s.name).map(remaining));
const chain = (s) => (successors(s.name).length
  ? `${s.name}(${s.duration}) -> ` + chain(successors(s.name).reduce((x, y) => (remaining(x) >= remaining(y) ? x : y))) : `${s.name}(${s.duration})`);

// List scheduling: among FINISHED stages, the one whose remaining path is longest gets its
// dependents assigned to a free runner first. Runner count is n.
const schedule = (duration, n) => {
  const done = new Set(), running = [], pending = STAGES.map((s) => s.name);
  let clock = 0;
  while (done.size < STAGES.length) {
    const ready = pending.filter((name) => find(name).deps.every((d) => done.has(d)))
      .sort((x, y) => remaining(find(y)) - remaining(find(x)));
    while (running.length < n && ready.length) {
      const name = ready.shift();
      pending.splice(pending.indexOf(name), 1);
      running.push({ name, ends: clock + duration(name) });
    }
    clock = Math.min(...running.map((r) => r.ends));
    for (let i = running.length - 1; i >= 0; i--) if (running[i].ends <= clock) { done.add(running[i].name); running.splice(i, 1); }
  }
  return clock;
};

const start = STAGES.filter((s) => !s.deps.length).reduce((x, y) => (remaining(x) >= remaining(y) ? x : y));
const limit = remaining(start), serial = STAGES.reduce((t, s) => t + s.duration, 0);
const cold = (name) => find(name).duration;
// On a source change, the cache only hits at dependency-resolution (table above, run 2).
const cached = (name) => (name === "dependency-resolution" ? RESTORE : find(name).duration);

console.log(`serial ${serial} s, critical path ${limit} s: ${chain(start)}`);
console.log("\nrunners   cold  distance from critical path  gain from one more runner  cached (src change)");
let prev = null;
for (let n = 1; n <= 6; n++) {
  const s = schedule(cold, n);
  console.log(String(n).padStart(9) + String(s + " s").padStart(9) + String(s - limit + " s").padStart(18) +
    (prev === null ? "-" : prev - s + " s").padStart(24) + String(schedule(cached, n) + " s").padStart(28));
  prev = s;
}

serial 341 s, critical path 203 s: dependency-resolution(42) -> build(65) -> integration-test(96)

runners   cold  distance from critical path  gain from one more runner  cached (src change)
        1    341 s             138 s                       -                       301 s
        2    218 s              15 s                   123 s                       178 s
        3    203 s               0 s                    15 s                       163 s
        4    203 s               0 s                     0 s                       163 s
        5    203 s               0 s                     0 s                       163 s
        6    203 s               0 s                     0 s                       163 s

The second runner gains 123 seconds, the third 15 seconds, the fourth zero. Duration flattens at three runners and stops at 203 seconds; this number comes from the graph, not from the runner count. The chain that sets the limit is dependency resolution, build, and the integration test: 42 + 65 + 96. All three must wait on each other, so no runner count can bring the pipeline below 203 seconds. The highest speedup is 1.68 times, and everything past the fourth runner is paid-for idle capacity.

The only way past the limit is to shorten the chain: if the integration test is split into two independent parts, the critical path drops to 42 + 65 + 48. This is a pipeline design decision, not a decision about buying more runners.

The two levers multiply each other, but they do not grip the same place. The last column shows the source-change run: the cache brings the 42 seconds at the head of the chain down to 2, and with three runners duration settles at 163 seconds. Caching shortens the chain’s head; parallelism removes the work outside the chain; neither can touch the 65 and 96 seconds in the middle. That is the pipeline’s real floor.

Summary

• The stage key derives from the content of a stage’s declared inputs and the keys of the prior stages. When an undeclared input changes, the key does not change, the gate does not run, and the pipeline finishes green.
• Across twelve runs, caching brought duration down from 4,092 seconds to 2,273 seconds (44.5 percent), and hits reached 46 in 96 attempts. The distribution carries the decision: 88 percent for tests, 13 percent for source, zero for the dependency list.
• The 100 percent hit rate shown for rule and contract changes is the cache’s blindness. Two defects (D4, D6) escaped because the gate that could catch them came from the cache; fixing the declaration adds 54 seconds to twelve runs, that is, 2.4 percent.
• Gates’ marginal value is not equal: the integration test held three defects in 768 seconds, two of them alone; the unit test held three defects in 266 seconds but only one of them alone. The cache’s own cost is 50 entries, 287.4 MB of storage, and 92 seconds of restoring.
• Parallelism cannot bring the pipeline below 203 seconds. The limit is set by the dependency resolution → build → integration test chain; past the third runner, the gain from one more runner is zero.

Next Step

This measurement counted two things as free. Every one of the forty-six hits assumes a machine that can still find the previous run’s output; PD30 also took queue wait as zero and assumed three runners were always ready. Both assumptions come down to the same decision: where the pipeline runs. If the pipeline runs on a machine set up clean on every run, the cache is empty every time and the 1,819-second gain measured here evaporates; if it runs on self-hosted machines, the cache stays, but the machines wait, age, and demand maintenance. The next lesson runs the same pipeline on two runner types and counts four items — queue wait, cost per run, the cache’s persistence, and maintenance load — then calculates the threshold: past how many runs a day, which type gets cheaper.