Consistency and Stale Data

The previous lesson separated out the patterns where a cache is needed, but one question stayed open. The value returned from the cache need not match the store’s value at that moment. This topic’s second lesson measured that drift once — 105,794 stale reads once invalidation was turned off — and its fourth lesson tied it to a parameter: the five-second upper-bound lifetime was chosen arbitrarily, and never justified.

This lesson builds that justification. How much staleness is acceptable is not a preference but a number that comes out of the data itself: however often a shipment’s state changes, a window far shorter than that change produces almost no stale response.

Two Windows, the Same Response

The Introduction to System Design course defined the replication staleness window: the time from a write’s acknowledgment until every replica has seen that value. The window here is a different one, and its name is the staleness window: the longest a cached copy can lag behind the source; a copy served within that time is stale data. Their sources differ — one from replication’s propagation, the other from an entry’s lifetime — but what they produce is the same, called by the same name: a stale response. A system can carry both at once, and they add together.

Consistency models were defined in that course and not retold here. Only one link is drawn: a cache’s eventual consistency guarantee is the lifetime given to an entry. Without a lifetime, relying on invalidation alone leaves no convergence guarantee either — this topic’s second lesson measured a lost delete leaving a stale entry with no counter showing it. Lifetime is the only mechanism that says an entry will eventually correct itself, and the staleness window is exactly the width of that guarantee.

Where the Window Comes From

A shipment produces seven state events per V4. How much time these events spread over is not in K01’s table; the only duration there is the 730-day retention period, and that is a different matter.

B1 (this lesson’s assumption): a shipment stays in transit for 48 hours from its first event to delivery. Rationale: V4’s seven states (accepted, in transit, out for delivery, delivered, and intermediate states) spread over a transit time, and a two-day transit time is enough for all of these states to occur. Since V8’s peak multiplier speeds up events too, the peak-hour event interval per shipment is $48 \cdot 3600 / 7 / 3$ seconds. Its sensitivity is given in the last measurement. Not added to K01’s table.

// cache/staleness.mjs — the in-process model of the staleness window. The clock is a counter;
// event interval, window, and capacity are parameters. Time is not measured, events and reads are counted.
export const K01 = {
  peakRead: (2_000_000 * 6 / 86_400) * 3,    // 416.67 req/s
  peakWrite: (400_000 * 7 / 86_400) * 3,     // 97.22 req/s
  eventsPerShipment: 7,                      // V4
  peakMultiplier: 3,                         // V8
};

// B1: a shipment stays in transit for 48 hours from its first event to delivery. At peak hour
// the event interval follows from V4 and V8 together.
export const TRANSIT_HOURS = 48;
export const eventInterval = (transitHours) => (transitHours * 3600) / K01.eventsPerShipment / K01.peakMultiplier;

// The read stream and the event calendar are produced together: each shipment gets its own
// event time when created. The clock is the read counter; one tick = 1/peakRead seconds.
export function run({ reads, workingSet, burst, capacity, windowS, transitHours = TRANSIT_HOURS }) {
  let seed = 20260730;
  const rand = () => ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648);
  const window = windowS * K01.peakRead;                 // ticks
  const intervalTicks = eventInterval(transitHours) * K01.peakRead;
  const box = new Map();                                 // key -> { version, expires }
  const truth = new Map();                                // key -> { version, nextEvent }
  let clock = 0, next = 1;
  const s = { hit: 0, storeRead: 0, stale: 0, lagTotal: 0, maxLag: 0, event: 0 };
  const newShipment = () => {
    const id = next++;
    truth.set(`track:${id}`, { version: 0, nextEvent: clock + rand() * intervalTicks });
    return { id, remaining: burst };
  };
  const active = Array.from({ length: workingSet }, () => newShipment());

  for (let i = 0; i < reads; i++) {
    clock += 1;
    const j = Math.floor(rand() * active.length);
    const key = `track:${active[j].id}`;
    if ((active[j].remaining -= 1) === 0) active[j] = newShipment();

    const t = truth.get(key);                             // due events are applied
    while (clock >= t.nextEvent) { t.version += 1; s.event += 1; t.nextEvent += intervalTicks; }

    const c = box.get(key);
    if (c !== undefined && c.expires > clock) {
      s.hit += 1;
      const lag = t.version - c.version;
      if (lag > 0) {
        s.stale += 1; s.lagTotal += lag;
        s.maxLag = Math.max(s.maxLag, lag);
      }
      continue;
    }
    s.storeRead += 1;
    box.delete(key);
    box.set(key, { version: t.version, expires: clock + window });
    if (box.size > capacity) box.delete(box.keys().next().value);
  }
  return s;
}

Lag is how many events a stale response falls behind by. The stale-read count says how often the window gets violated; lag says what the user sees once it is. These are two separate questions, and the design decision looks at both at once.

// cache/window.mjs — as the window grows: hit ratio, stale responses, and store load
import { K01, TRANSIT_HOURS, eventInterval, run } from "./staleness.mjs";

const READS = 200_000, CAPACITY = 2000, WORKING = 1000, BURST = 10;
const WINDOW_S = 480;

console.log(`B1: transit time ${TRANSIT_HOURS} hours, V4 = ${K01.eventsPerShipment} events, V8 = ${K01.peakMultiplier}`);
const INTERVAL = eventInterval(TRANSIT_HOURS);
console.log(`-> peak-hour event interval per shipment = ${INTERVAL.toFixed(2)} s`);
console.log(`reads ${READS} (${WINDOW_S} s), capacity ${CAPACITY}, concurrent shipments ${WORKING}\n`);

console.log("window (s)  hit  stale reads  stale ratio  stale responses/s  avg lag  max lag  requests reaching the store/s");
console.log("---------- ------- ------------ ------------ ------------------ -------- -------- ------------------------------");
for (const windowS of [1, 5, 30, 60, 300, 1800]) {
  const r = run({ reads: READS, workingSet: WORKING, burst: BURST, capacity: CAPACITY, windowS });
  const h = r.hit / READS;
  const staleRatio = r.stale / READS;
  const behind = K01.peakRead * (1 - h);
  console.log(`${String(windowS).padStart(10)} ${h.toFixed(4).padStart(7)} ${String(r.stale).padStart(12)} ` +
    `${staleRatio.toFixed(6).padStart(12)} ${(staleRatio * K01.peakRead).toFixed(3).padStart(18)} ` +
    `${(r.stale === 0 ? 0 : r.lagTotal / r.stale).toFixed(2).padStart(8)} ${String(r.maxLag).padStart(8)} ` +
    `${(behind + K01.peakWrite).toFixed(2).padStart(30)}`);
}

const r5 = run({ reads: READS, workingSet: WORKING, burst: BURST, capacity: CAPACITY, windowS: 5 });
console.log(`\nwindow 5 s: keys that received an event while cached = ${r5.event}`);
console.log(`K01 peak write ${K01.peakWrite.toFixed(2)}/s -> total events in the window = ${Math.round(K01.peakWrite * WINDOW_S)}`);
console.log(`share of events landing on a cached key = ${(r5.event / (K01.peakWrite * WINDOW_S)).toFixed(4)}`);

console.log(`\nstaleness budget -> window (theory: window = event interval x budget)`);
console.log("budget (stale response ratio)  theoretical window (s)  measured stale ratio");
for (const budget of [0.0001, 0.001, 0.01]) {
  const windowS = INTERVAL * budget;
  const r = run({ reads: READS, workingSet: WORKING, burst: BURST, capacity: CAPACITY, windowS });
  console.log(`${budget.toFixed(4).padStart(30)} ${windowS.toFixed(2).padStart(24)} ${(r.stale / READS).toFixed(6).padStart(21)}`);
}

console.log(`\nB1's sensitivity (window 60 s):`);
console.log("transit time (h)  event interval (s)  stale ratio  stale responses/s  hit");
for (const hours of [48, 12, 2]) {
  const r = run({ reads: READS, workingSet: WORKING, burst: BURST, capacity: CAPACITY, windowS: 60, transitHours: hours });
  const o = r.stale / READS;
  console.log(`${String(hours).padStart(17)} ${eventInterval(hours).toFixed(2).padStart(20)} ${o.toFixed(6).padStart(12)} ` +
    `${(o * K01.peakRead).toFixed(3).padStart(19)} ${(r.hit / READS).toFixed(4).padStart(7)}`);
}

B1: transit time 48 hours, V4 = 7 events, V8 = 3
-> peak-hour event interval per shipment = 8228.57 s
reads 200000 (480 s), capacity 2000, concurrent shipments 1000

window (s)  hit  stale reads  stale ratio  stale responses/s  avg lag  max lag  requests reaching the store/s
---------- ------- ------------ ------------ ------------------ -------- -------- ------------------------------
         1  0.2700            3     0.000015              0.006     1.00        1                         401.40
         5  0.6313           32     0.000160              0.067     1.00        1                         250.85
        30  0.8866          221     0.001105              0.460     1.00        1                         144.46
        60  0.8968          239     0.001195              0.498     1.00        1                         140.23
       300  0.8968          239     0.001195              0.498     1.00        1                         140.23
      1800  0.8968          239     0.001195              0.498     1.00        1                         140.23

window 5 s: keys that received an event while cached = 46
K01 peak write 97.22/s -> total events in the window = 46667
share of events landing on a cached key = 0.0010

staleness budget -> window (theory: window = event interval x budget)
budget (stale response ratio)  theoretical window (s)  measured stale ratio
                        0.0001                     0.82              0.000005
                        0.0010                     8.23              0.000290
                        0.0100                    82.29              0.001195

B1's sensitivity (window 60 s):
transit time (h)  event interval (s)  stale ratio  stale responses/s  hit
               48              8228.57     0.001195               0.498  0.8968
               12              2057.14     0.004180               1.742  0.8968
                2               342.86     0.032020              13.342  0.8968

All the numbers belong to the computed class: they were counted over a deterministic stream.

The Window Saturates

The first table lands somewhere unexpected. Past 60 seconds, the window changes nothing: hit ratio 0.8968, stale ratio 0.001195, requests reaching the store/s 140.23 — three identical rows. The reason: the entry gets evicted before it can exhaust its lifetime. A shipment’s ten queries spread over roughly twenty-four seconds; once that ends, the shipment leaves the working set and its entry drops under capacity pressure. A window longer than sixty seconds is being given to an entry that will never be read again.

This makes the fourth lesson’s five-second assumption a poor choice. At five seconds, the hit ratio is 0.6313 and requests reaching the store/s is 250.85; at sixty seconds, 0.8968 and 140.23. The five-second window loads 110.62 extra requests per second onto the store, and in exchange lowers the stale ratio from 0.001195 to only 0.000160: 110.62 requests are paid to gain 0.43 stale responses per second.

The second table gives the rule for choosing the window. A staleness budget — an accepted stale response ratio — is set, and the window becomes the event interval times the budget. A one-percent budget corresponds to an 82.29-second window; the measured ratio, though, is 0.001195, one-eighth of the budget. Theory gives the upper bound, and eviction pulls it lower still.

The Magnitude of Staleness

The stale-read count alone is not enough. The average-lag and max-lag columns read 1.00 and 1 in all six rows: a stale response never falls more than one event behind. To the user, this means seeing the shipment one state step behind — “at the transit hub” instead of “out for delivery.” The state never falls two steps behind, and refreshing the page shows the correct one.

This number is the real reason the window is acceptable. 0.498 stale responses per second comes to 239 responses over an eight-minute window, each of them exactly one step behind. The same budget would call for a different decision if the lag were two or three.

The acceptance decision also has a layer dimension. This topic’s first lesson measured 0.7002 of the hit ratio served at the client layer, and a copy placed there cannot be revoked until it expires. Most stale responses therefore come from the layer that cannot be revoked: there, the window is not an estimate but a commitment.

A Computation in Place of an Assumption

The last two output blocks carry this topic’s most important correction.

This topic’s second lesson used an upper bound: it assumed all state events land on shipments being queried at that moment and noted that this is the direction where invalidation is strongest. B1 puts a computation in its place. The window carries 46,667 state events, and only 46 of them land on a key sitting in the cache: a share of 0.0010. The rest go either to shipments not being queried or to keys not currently in the cache, and drop no entry at all.

This turns the second and third lessons’ numbers into upper bounds. The 0.7287 hit ratio cache-aside measured would hold if every event landed on a hot key; at the real share, the hit ratio stays at 0.8968, and the gap between cache-aside and write-through disappears on the read side. The third lesson’s write-path analysis is unaffected: its length, coalescing ratio, and loss window are independent of where events land.

The last table gives B1’s sensitivity and draws the boundary of the decision. As transit time drops from 48 hours to 2 hours, the event interval falls from 8228.57 seconds to 342.86 seconds, and the same sixty-second window raises the stale ratio from 0.001195 to 0.032020, and the stale response rate to 13.342 per second. The hit ratio does not change. The same cache design, with the same measures, produces twenty-seven times more stale responses for a shipment flow delivered the same day. The window depends on the data, not the system.

Summary

• The staleness window is how far a cached copy can lag behind the source; it differs from the replication staleness window in its source but produces the same stale response, and it is exactly the width of the cache’s eventual consistency guarantee.
• The window follows from how fast the data changes: with B1 and V4, the peak-hour event interval is 8228.57 seconds, and the window is that interval times the staleness budget — a one-percent budget gives 82.29 seconds.
• The window saturates at 60 seconds: hit ratio 0.8968, requests reaching the store/s 140.23, stale ratio 0.001195. The fourth lesson’s five-second window loaded 110.62 extra requests per second onto the store to gain 0.43 stale responses per second.
• A stale response never fell more than one event behind in any run; average and max lag are both 1. The acceptance decision looks at these two numbers together, not at the stale response count.
• Only 46 of the window’s 46,667 events land on a key in the cache (a share of 0.0010); this turns the second lesson’s invalidation assumption into an upper bound. At a 2-hour transit time, the same window raises the stale ratio to 0.032020.

Next Step

This topic met reads in front of the store and bounded their staleness with a window. requests reaching the store/s dropped from 513.89 to 140.23, and V9’s 0.90 stopped being an assumption and became the outcome of a placement, a strategy, and a window decision. But this design never once questioned one thing: the shape of the value placed in the cache. The cache lightened the read path; what it reads is still a model designed for writing. The shipment record is organized so the carrier can write its state event, and because the tracking query has to read that same model, it first joins, then formats, then stores. The cache does not remove this borrowing — it only hides it from requests that do not miss; every missed request still goes to it. The next topic removes the borrowing and scales the read and write paths with their own models. Its first question is this: does keeping the same data in two separate structures let the read and write paths scale separately, and if so, past which ratio. </content>