Invalidation

Versioned keys, TTLs, and why bounded staleness is a number you choose rather than a bug you fix.

Syntaxuser:{id}:g{generation}:profile // INCR gen:user:{id} invalidates every derived key

Populating a cache is easy. Deciding when an entry stops being true is the hard half, and most cache bugs in production are invalidation bugs.

Three tools

TTL is the blunt instrument: every entry is wrong for up to its TTL, and that is the whole guarantee. It needs no coordination and it never leaks, which is why it is the right default for anything whose staleness budget is measured in minutes.

Explicit deletion on write is precise but only as good as your list of keys. The moment one row feeds five derived cache entries, the write path has to know all five, and the one it forgets is the bug.

Versioned keys sidestep that. Put a generation number in the key and bump it on write: every derived entry becomes unreachable at once, with one atomic INCR and no key enumeration. The old entries expire on their own TTL.

The race nobody avoids on the first try

Write the database, then delete the key — never the other way round, or a concurrent reader repopulates the pre-commit value. Even in the right order a narrow window remains: a reader that loaded the old row just before the commit can write it back just after the delete. A short TTL bounds the damage. Closing it properly needs the cache to reject such writes, which is what the leases in Facebook's memcache paper (NSDI 2013) do.

Bounded staleness is a decision

Write the budget down per field: a product title may be an hour stale, a price thirty seconds, stock never cached. Then "the cache is wrong" becomes something somebody signed off on rather than an incident.

Example

Example · javascript
// Versioned keys: do not hunt for keys to delete, change the name instead.
// One INCR invalidates every derived entry for that user atomically.
const genCache = new Map(); // process-local, 1s TTL: keeps the extra GET cheap

async function generation(userId) {
  const cached = genCache.get(userId);
  if (cached && cached.until > Date.now()) return cached.value;
  const value = (await redis.get(`gen:user:${userId}`)) ?? '0';
  genCache.set(userId, { value, until: Date.now() + 1000 });
  return value;
}

async function keyFor(userId, part) {
  return `user:${userId}:g${await generation(userId)}:${part}`;
}

export async function readFeed(userId) {
  const key = await keyFor(userId, 'feed');
  const hit = await redis.get(key);
  if (hit !== null) return JSON.parse(hit);
  const feed = await buildFeed(userId); // expensive fan-out read
  await redis.set(key, JSON.stringify(feed), { EX: 600 });
  return feed;
}

// Any write that affects the user: feed, profile, counters, everything.
// Old keys are now unreachable and die on their own TTL. Nothing is scanned.
export async function invalidateUser(userId) {
  await redis.incr(`gen:user:${userId}`);
}

When to use it

  • A price edit must be visible within seconds on a page assembled from six cached fragments.
  • Removing a SCAN-based purge job that spikes Redis latency every time an admin saves a record.
  • Writing down, for review, exactly how stale each field on a page may be.
  • Fixing a report that a deleted comment keeps reappearing for some users.

More examples

Commit first, delete second, TTL as the backstop

This is the ordering every cache-aside write path needs, and the comment is the part interviewers listen for: you cannot delete the race away, you can only bound it or use a cache primitive such as a lease that rejects the late write. Use it for any field where a short TTL is acceptable but a stale value for an hour is not.

Example · javascript
export async function setPrice(productId, priceCents) {
  const tx = await pg.connect();
  try {
    await tx.query('BEGIN');
    await tx.query('UPDATE products SET price_cents = $1 WHERE id = $2', [
      priceCents,
      productId,
    ]);
    await tx.query('COMMIT'); // the delete MUST come after this
  } finally {
    tx.release();
  }

  // UNLINK reclaims memory on a background thread (Redis 4.0+); DEL does it
  // inline, which matters for large values.
  await redis.unlink(`product:${productId}`);
  // Residual risk: a reader that SELECTed the old row before COMMIT can SET it
  // after this UNLINK. The entry's own short TTL is what bounds that window.
}

Tag sets, when a key cannot carry a version

Tagging is the answer when one write must reach entries whose keys you could not have predicted, such as rendered fragments or search result pages. The cost is a second write per tag and an index that can drift, which is why the tag set gets a TTL of its own rather than living forever.

Example · javascript
// For entries derived from several entities, record the reverse index as you
// write, so invalidation never has to guess or scan.
async function cacheWithTags(key, value, tags, ttl) {
  const m = redis.multi();
  m.set(key, JSON.stringify(value), { EX: ttl });
  for (const tag of tags) {
    m.sAdd(`tag:${tag}`, key);
    m.expire(`tag:${tag}`, ttl * 2); // the index must not long outlive its members
  }
  await m.exec();
}

async function invalidateTag(tag) {
  const keys = await redis.sMembers(`tag:${tag}`);
  if (keys.length) await redis.unlink(keys);
  await redis.unlink(`tag:${tag}`);
}

// A rendered order summary depends on the order, the customer and two products.
await cacheWithTags(
  `summary:order:${order.id}`,
  summary,
  [`order:${order.id}`, `customer:${order.customerId}`, ...order.productIds.map((p) => `product:${p}`)],
  900,
);
await invalidateTag(`product:912`); // every summary mentioning product 912

The staleness budget, written down in code

Turns an implicit guess into an explicit product decision, and gives security review something concrete to object to. Build this table the first time two engineers disagree about whether a cached value is a bug.

Example · javascript
// Reviewable, testable, and the thing to point at when someone files a bug
// about a number being a few seconds behind.
export const FRESHNESS = {
  'product.title':       { ttl: 3600, invalidateOnWrite: false }, // an hour is fine
  'product.description': { ttl: 3600, invalidateOnWrite: false },
  'product.price':       { ttl: 30,   invalidateOnWrite: true  }, // shown at checkout
  'product.stock':       { ttl: 0,    invalidateOnWrite: true  }, // never cached
  'user.permissions':    { ttl: 60,   invalidateOnWrite: true  }, // revocation lag
};

// ttl: 0 means read through every time. A reviewer can now see, in one place,
// that a revoked permission can survive for up to 60 seconds, and say whether
// that is acceptable rather than discovering it during an incident.

Related

sd cache strategiessd cache layerssd consistency modelssd reverse proxy cdnsd hot keys

Discussion

  • Be the first to comment on this lesson.