No Caching

The previous lesson questioned the store’s structure and counted the share of a write that does not serve its own class. This lesson’s question is on the read side, and at first looks already answered. The Scaling the Data Layer course’s caching topic measured where caching is not needed: for a period scan with a repeat ratio of 1.00, a cache brings 2.00 extra touches per request and gains nothing. This lesson is that measurement’s mirror image — where caching is needed but was not put in place. But the quantity measured is not the same. There, a repeated read was counted; here, a repeated computation is counted.

The symptom is this: the application layer’s processor utilization is approaching saturation in the end-of-day window, even though the request rate reaching the store has not changed. In K01’s calculation, requests reaching the store is 138.89/s and cache hit rate is 0.90 under the V9 assumption; both numbers still hold. What is slowing down is not the store — it is the application itself.

Same Symptom, Two Causes

First cause: work per request genuinely grew. New fields have entered the response; serialization has gotten longer. This is the processor-side counterpart of the over-fetching the fourth lesson measured.

Second cause: the same computation repeats with the same input. Work per request has not changed at all; what changed is how many times the same work is repeated. This is called no caching, and the form measured throughout this lesson fixes it with memoization: the computation’s result is stored against a computation key derived from its inputs.

The measurement that tells the two apart is de-duplicating calls by the computation key, not the read key. If the computation repeat is close to one, the cause is the first, and memoization gains nothing; if the repeat is well above one, the cause is the second. These two repeat ratios can diverge within the same stream, and that is this lesson’s central finding.

The Computation and Three Streams

The pricing computation is a real function: the weight tier is scanned, the ordered tariff rule list is walked, and the contract multiplier is found. The measured quantity is not duration, it is the number of steps executed during the run; duration would depend on this machine, the step count does not.

KK8 — the computation’s shape. Eight zones, five weight tiers, three contract classes, and seventeen ordered tariff rules. Rationale: the zone, tariff, and contract fields in M18’s shipment library give this shape; the rule list is three layers — same zone, origin zone, and a catch-all. Its sensitivity is given through the third stream: if the weight enters the key unbucketed, the repeat collapses. This assumption is not added to K01’s table.

// computation/tariff.mjs — the pricing computation and three streams. Counters increment during
// the real run; what gets measured is not duration, it is the number of steps executed.
export const ZONE = 8;
export const TIER = [1, 5, 20, 50, Infinity];           // weight-tier upper bounds
export const CONTRACT = ["standard", "contracted", "bulk"];

export const RULE = [];
for (let k = 1; k <= ZONE; k += 1) RULE.push({ o: `Z${k}`, d: `Z${k}`, factor: 1.0 });
for (let k = 1; k <= ZONE; k += 1) RULE.push({ o: `Z${k}`, d: "*", factor: 1.0 + k / 10 });
RULE.push({ o: "*", d: "*", factor: 2.5 });             // catch-all rule

export const counter = { calc: 0, key: 0, lookup: 0 };
const reset = () => { counter.calc = 0; counter.key = 0; counter.lookup = 0; };

// The computation itself: the tier is scanned, the rule list is walked in order, the contract multiplier is found.
export function price(g) {
  let d = 0;
  while (TIER[d] < g.weight) { counter.calc += 1; d += 1; }
  let factor = 0;
  for (const rule of RULE) {
    counter.calc += 1;
    if ((rule.o === "*" || rule.o === g.origin) && (rule.d === "*" || rule.d === g.dest)) {
      factor = rule.factor; break;
    }
  }
  let s = 0;
  while (CONTRACT[s] !== g.contract) { counter.calc += 1; s += 1; }
  counter.calc += 1;
  return factor * (d + 1) * (1 + s / 4);
}

// The computation key is built only for memoization; four fields are read, the tier is scanned again.
export function key(g) {
  let d = 0;
  while (TIER[d] < g.weight) { counter.key += 1; d += 1; }
  counter.key += 3;
  return g.continuous ? `${g.origin}>${g.dest}|${g.weight}|${g.contract}`
                      : `${g.origin}>${g.dest}|${d}|${g.contract}`;
}

// A seeded generator using 32-bit integer arithmetic; Math.imul avoids precision loss.
export function seededRand(seed) {
  let s = seed >>> 0;
  return () => ((s = (Math.imul(s, 1664525) + 1013904223) >>> 0) / 4294967296);
}

// Period scan: each seller-day record is read once (read repeat 1.00), but the computation's
// inputs come from a small set. When `continuous` is on, the weight enters the key unbucketed.
export function periodStream(count, { continuous = false, seed = 20260730 } = {}) {
  const rand = seededRand(seed);
  return Array.from({ length: count }, (_, i) => ({
    read: `period:${i + 1}`, continuous,
    origin: `Z${Math.floor(rand() * ZONE) + 1}`,
    dest: `Z${Math.floor(rand() * ZONE) + 1}`,
    weight: continuous ? Math.round(rand() * 60000) / 1000 : [0.5, 3, 12, 35, 80][Math.floor(rand() * 5)],
    contract: CONTRACT[Math.floor(rand() * CONTRACT.length)],
  }));
}

// Tracking query: the same shipment is queried batch by batch; the computation's inputs come from the shipment itself.
export function trackingStream(requests, workingSet = 1000, batch = 10, seed = 4242) {
  const rand = seededRand(seed);
  const shipment = (no) => {
    const r = seededRand(no * 7919 + 13);
    return { read: `tracking:${no}`, continuous: false, origin: `Z${Math.floor(r() * ZONE) + 1}`,
      dest: `Z${Math.floor(r() * ZONE) + 1}`, weight: [0.5, 3, 12, 35, 80][Math.floor(r() * 5)],
      contract: CONTRACT[Math.floor(r() * CONTRACT.length)] };
  };
  let next = 1;
  const active = Array.from({ length: workingSet }, () => ({ no: next++, remaining: batch }));
  return Array.from({ length: requests }, () => {
    const j = Math.floor(rand() * active.length);
    const g = shipment(active[j].no);
    if ((active[j].remaining -= 1) === 0) active[j] = { no: next++, remaining: batch };
    return g;
  });
}

export function uncached(stream) {
  reset();
  for (const g of stream) price(g);
  return { ...counter, entries: 0 };
}

export function memoized(stream) {
  reset();
  const m = new Map();
  for (const g of stream) {
    const a = key(g);
    counter.lookup += 1;
    if (m.has(a)) continue;
    m.set(a, price(g));
  }
  return { ...counter, entries: m.size };
}

// computation/measurement.mjs — separating read repeat from computation repeat, and what memoization costs in return
import { price, key, periodStream, trackingStream, uncached, memoized } from "./tariff.mjs";

const RECORDS = 120_000;          // K01: period seller-day
const REQUESTS = 200_000;         // K01: 480 s x 416.67 requests/s peak read

// Column width comes from one place; the header and rows always stay aligned.
const W = [25, 14, 14, 15, 21, 18];
const write = (h) => console.log(h.map((x, i) => (i ? String(x).padStart(W[i]) : String(x).padEnd(W[i]))).join(" "));
const line = () => console.log(W.map((n) => "-".repeat(n)).join(" "));

const STREAM = [
  ["period scan", periodStream(RECORDS)],
  ["tracking query", trackingStream(REQUESTS)],
  ["period, continuous weight", periodStream(RECORDS, { continuous: true })],
];

write(["stream", "calls", "distinct reads", "read repeat", "distinct computations", "computation repeat"]);
line();
const measured = [];
for (const [name, stream] of STREAM) {
  const o = uncached(stream);
  const m = memoized(stream);
  const distinctReads = new Set(stream.map((g) => g.read)).size;
  measured.push([name, stream.length, o, m]);
  write([name, stream.length, distinctReads, (stream.length / distinctReads).toFixed(2), m.entries,
    (stream.length / m.entries).toFixed(2)]);
}

console.log();
write(["stream", "uncached steps", "memoized steps", "ratio", "steps/call", "cache entries"]);
line();
for (const [name, n, o, m] of measured) {
  const mt = m.calc + m.key + m.lookup;
  write([name, o.calc, mt, (o.calc / mt).toFixed(2), (o.calc / n).toFixed(2), m.entries]);
}

// The break-even point comes out of the measured averages: C steps computation, K steps key, L steps lookup.
console.log();
write(["stream", "C", "K", "L", "break-even repeat", "measured repeat"]);
line();
for (const [name, n, o, m] of measured) {
  const [C, K, L] = [o.calc / n, m.key / n, m.lookup / n];
  write([name, C.toFixed(2), K.toFixed(2), L.toFixed(2),
    (C / (C - K - L)).toFixed(2), (n / m.entries).toFixed(2)]);
}

// KK9: a tariff revision takes effect mid-period. If the key does not include the version,
// the value returned from the cache is wrong for records after the revision; the wrongs are counted.
const REVISION = 1.05;
const versioned = periodStream(RECORDS).map((g, i) => ({ ...g, version: i < RECORDS / 2 ? 1 : 2 }));
const correctValue = (g) => price(g) * (g.version === 2 ? REVISION : 1);
console.log();
for (const missing of [true, false]) {
  const m = new Map();
  let wrong = 0;
  for (const g of versioned) {
    const a = missing ? key(g) : `${key(g)}|v${g.version}`;
    if (!m.has(a)) m.set(a, correctValue(g));
    if (Math.abs(m.get(a) - correctValue(g)) > 1e-9) wrong += 1;
  }
  console.log(`key includes version ${missing ? "no " : "yes"}: cache entries ${String(m.size).padStart(6)},` +
    ` wrong results ${String(wrong).padStart(6)}, wrong ratio ${(wrong / RECORDS).toFixed(4)}`);
}

stream                             calls distinct reads     read repeat distinct computations computation repeat
------------------------- -------------- -------------- --------------- --------------------- ------------------
period scan                       120000         120000            1.00                   960             125.00
tracking query                    200000          20444            9.78                   960             208.33
period, continuous weight         120000         120000            1.00                119365               1.01

stream                    uncached steps memoized steps           ratio            steps/call      cache entries
------------------------- -------------- -------------- --------------- --------------------- ------------------
period scan                      1860493         734534            2.53                 15.50                960
tracking query                   3102366        1214858            2.55                 15.51                960
period, continuous weight        1948593        2745984            0.71                 16.24             119365

stream                                 C              K               L     break-even repeat    measured repeat
------------------------- -------------- -------------- --------------- --------------------- ------------------
period scan                        15.50           5.00            1.00                  1.63             125.00
tracking query                     15.51           5.00            1.00                  1.63             208.33
period, continuous weight          16.24           5.73            1.00                  1.71               1.01

key includes version no : cache entries    960, wrong results  60000, wrong ratio 0.5000
key includes version yes: cache entries   1920, wrong results      0, wrong ratio 0.0000

Step counts and distinct-key counts are in the measurement class: they were counted during the run. Call counts coming from K01 are computed; the computation’s shape is in the assumption class.

Read Repeat Does Not Say Computation Repeat

The first table’s first row is this lesson’s rationale. In the period scan, read repeat is 1.00: every seller-day record is read once and never read again. The Scaling the Data Layer course had made the correct call for this row — a read cache does not belong on this stream. The same stream’s computation repeat, though, is 125.00: 120,000 records fall onto only 960 distinct computation keys, because the price depends not on the shipment itself but on the zone pair, weight tier, and contract class. A stream can both not deserve a read cache and carry a computation that repeats on every record; the two measures diverge within the same stream.

In the tracking query, both are large: read repeat is 9.78, computation repeat is 208.33. In this stream, a read cache already prevents part of the computation; no caching stands here as a second layer.

The third row shows the boundary. When the weight enters the key unbucketed, 120,000 records produce 119,365 distinct keys, and the computation repeat drops to 1.01. The computation itself has not changed; what changed is the granularity of what the key distinguishes.

Memoization’s Ceiling

The second table gives the gain in steps. In the period scan, the uncached run executes 1,860,493 steps, the memoized run 734,534: a ratio of 2.53. The gain is not proportional to the 125x repeat, and the reason is in the third table: computation averages 15.50 steps per call, but building the computation key costs 5.00 steps on every call, and the lookup itself costs 1.00 step. Even if memoization eliminated repeats entirely, 6 steps per call would keep being paid. The gain’s ceiling is therefore 15.50 / 6.00, that is, 2.58; the measured 2.53 sits just under that ceiling.

This flips memoization’s measure around. What determines the gain is not the repeat ratio, but the computation’s ratio to its key. The repeat ratio only says how close the run gets to the ceiling.

The third table gives the break-even point. The threshold derived from the three measured costs takes the form $C / (C - K - L)$, and for the period scan it is 1.63: if the computation repeat is above this value, memoization pays off. Since the measured repeat is 125.00, it pays off many times over. In the continuous-weight stream, the threshold is 1.71 and the measured repeat is 1.01; memoization is at a loss there — the ratio is 0.71, meaning the memoized run executes 1.41 times more steps than the uncached one.

What Grows in Return

Memoization grows two things, and both are countable.

Memory. 960 entries are held in the period scan; 119,365 in the continuous-weight stream. The second number shows how the cost explodes where there is no gain: nearly one entry per record. This is the counterpart, here, of the 2.00 extra touches the Scaling the Data Layer course measured.

Wrongness surface. The last two rows measure this. The tariff is revised mid-period (KK9; rationale: billing is settled on a monthly period, and a revision can take effect within the period). When the computation key does not include the version, memoization holds 960 entries and 0.5000 of the results come out wrong — every record after the revision gets the value computed before the revision. When the version is added to the key, entries rise to 1920 and the wrong ratio becomes 0.0000. The cost is memory doubling; what is gained is correctness.

An uncached computation cannot be wrong. Memoization ties correctness to the key’s completeness, and that tie breaks silently if it is never measured.

The Condition Where No Caching Is Correct

No caching is correct design, not an anti-pattern, under two conditions, and both are given with a number.

When the computation repeat is below the break-even threshold. In the continuous-weight stream, the repeat is 1.01 and the threshold is 1.71; memoization increases the step count by 1.41x and holds 119,365 entries. In this stream, doing the computation every time is correct.

When the computation is cheaper than the key. The threshold $C / (C - K - L)$ is undefined when $C \le K + L$: if building the key costs more than doing the computation, no repeat ratio saves memoization. In this measurement, $C$ is 15.50 and $K + L$ is 6.00, so the condition holds, but it would not hold for a cheap computation.

Summary

• The symptom is the application layer approaching saturation; it has two causes — work per request has grown, or the same computation is being repeated. The distinguishing measurement is de-duplicating calls by the computation key.
• In the period scan, read repeat is 1.00 while computation repeat is 125.00: a stream can go without deserving a read cache while still carrying a computation that repeats on every record. This is the mirror image of the pattern the Scaling the Data Layer course measured.
• Memoization’s gain is 2.53x and its ceiling is 15.50 / 6.00 = 2.58; what determines the ceiling is not the repeat ratio, but the computation’s ratio to its key-building cost.
• The break-even repeat is derived from the measured costs and is 1.63; in the continuous-weight stream, the repeat is 1.01, the threshold is 1.71, and memoization drops to a 0.71x ratio — there, no caching is correct design.
• What memoization costs is memory and a wrongness surface: 960 entries against 119,365 entries, and when the computation key does not include the tariff version, 0.5000 of the results come out wrong.

Next Step

All seven patterns so far measured a single owner’s work: the system’s excess work was shared out among its own streams. One assumption was never questioned — that everyone using a shared resource is on the same side. The shipment tracking and pricing service does not serve a single customer; sellers pass through the same edge, the same store, and the same worker pool. The next lesson picks up the symptom from there: latency for one group of sellers grows even though the total request rate never changes. This too has two causes, and the measure that tells them apart is not the request count — how many units of work one request generates varies sixty-fold from stream to stream, and a measurement that counts share by request can never see the noise.