Cache Invalidation Across a Fleet — a worked solution

Questions worth asking before drawing a box:

• What is the source of truth? Here: a sharded relational DB. The cache is disposable; losing a cache host loses nothing durable.
• Look-aside or read-through? Look-aside (the app/read-tier reads cache, falls through to the DB on miss, and writes back). This is where the stale-set race lives, so it drives the lease design.
• Invalidate or update on write? Invalidate-by-delete is the safe default (a delete is reorder-safe). Write-through (update the cached value) and write-behind (buffer in cache, flush async) are the alternatives we discuss in deep-dives.
• How fresh must reads be? We target a bounded staleness window, not linearizability. Read-your-own-writes is required; other users tolerate sub-second staleness.
• Single-region or multi-region? Multi-region with a single master region for writes (single-writer-per-shard) and read replicas + a full cache fleet per region.
• Read:write ratio? ~500:1 (TAO's published figure). This is why almost all design pressure is on keeping reads correct, not on write throughput.

Assumptions:

• One service tier doing ~10M cache gets/sec, ~20k writes/sec, 98% hit ratio, 5 regions, ~60 TB hot working set.
• Staleness tolerated: ≤ ~160 ms same-region, ≤ ~500 ms cross-region. TTL backstop = 300 s caps staleness from lost invalidations.

• Read a key: serve from the nearest cache; on miss, fill from the DB and populate the cache.
• Write a key: durably persist the new value AND invalidate every cached copy of the affected keys, fleet-wide and cross-region.
• Invalidate-by-delete on write (not value-replace), so the next read re-derives the fresh value.
• Read-your-own-writes: a client that just wrote must not subsequently read its own stale value, even cross-region.
• Replay invalidations: a cache fleet that was unreachable must catch up from the durable invalidation log on recovery.
• Measure consistency: continuously report the stale-read ratio as an SLI, and auto-correct entries found stale past the window.
• Bound worst-case staleness with a TTL even when every invalidation for a key is lost.

SLOs (one service tier):

Error budget. Read availability 99.99% → ~52 min/yr. The dominant user-visible failure is not unavailability but silent staleness, so the budget that actually governs on-call is the staleness SLO burn rate: page on a fast burn (2% of the staleness budget in 1 h, confirmed by a short window), ticket on a slow burn (SRE Workbook multi-window multi-burn-rate alerting). A gray failure — invalidations silently stopping while reads look healthy — must be caught by the staleness SLI, not by a 5xx alarm.

Start from the anchored load and derive every shard/replica/fleet number rather than guessing.

1. Throughput. Anchor reads at R = 10,000,000 gets/sec for one service tier (Meta's memcache served billions/sec fleet-wide; this is one tier of that). With TAO's 500:1 read:write, writes/invalidations W = R/500 = 20,000/sec. At a 98% hit ratio, DB-bound misses = R·(1−0.98) = 200,000/sec.

2. Fleet sizing. Hot working set D = 60 TB. Hosts are 256 GB RAM, ~192 GB usable after overhead. With 25% headroom: hosts/region = 60 TB · 1.25 / 0.192 TB ≈ 390. Across 5 regions → ~1,950 cache hosts. Per-host get load = 10M / 390 ≈ 25,600 gets/sec/host — comfortably under the ~1M ops/sec single-host ceiling.

3. Why targeted, not broadcast. A write must reach the hosts holding the key. Targeted (mcrouter consistent-hash → only the owning host, in each region): fan-out ≈ regions = 5, so W·5 = 100,000 invalidations/sec. Broadcast (every host, e.g. for a wildcard/surrogate purge): fan-out = 1,950, so W·1,950 = 39,000,000 deliveries/sec — 390× more. This single multiplier is why the pipeline tails the binlog and routes through mcrouter to the owning host instead of multicasting to the fleet.

4. The TTL backstop is cheap. A 300 s TTL caps how long a lost invalidation can serve stale data; its cost is the extra refills it forces. The naive bound — every one of 60 TB / 1 KB ≈ 6×10¹⁰ entries expiring and refetching once per window — would be 6×10¹⁰ / 300 s ≈ 200,000,000 refills/sec, which is absurd (20× the entire 10M/sec read rate). It never materializes, because a TTL only triggers a refill when a still-wanted key is requested again after it expires, and those re-requests are already part of the organic miss stream (R·(1−0.98) = 200,000/sec); the cold majority of the 60 TB is never re-requested inside any 300 s window. So the backstop rides on the existing ~200,000/sec miss rate for essentially nothing while capping lost-invalidation staleness at 5 minutes. Drop TTL to 60 s and a continuously-hot key refills ~5× more often (every 60 s vs 300 s) and it starts to bite; raise it to an hour and a lost invalidation hides for an hour.

5. Where the architecture flips.

Read — two classes, by data sensitivity:

Public / non-PII object (CDN-cacheable, no auth):

GET /v1/objects/:key
200 OK
Cache-Control: public, max-age=30, stale-while-revalidate=30
Surrogate-Key: obj:123 owner:42
ETag: "v=8814"          # version/generation, used by the cache version-guard
{ "key": "obj:123", "value": { ... }, "version": 8814 }

Private / tenant / PII object (auth required, bypasses the shared CDN):

GET /v1/objects/:key
Authorization: Bearer <token>        # or session; tenant scope authorized at the gateway/read service
200 OK
Cache-Control: private, no-store     # never lands in the shared Fastly edge cache
ETag: "v=8814"
{ "key": "obj:123", "value": { ... }, "version": 8814 }

Tenant scope is enforced by the gateway/read service from the token, not by key-secrecy — knowing :key is not authorization. The obj:123 example above is a public, non-PII object: only that class may be served Cache-Control: public through the third-party edge. PII-bearing objects use the private form (Cache-Control: private / no-store) and bypass the CDN entirely, so they are never co-resident in a shared public edge cache. Internal cache-fleet entries are still version-guarded identically regardless of class.

Write (mutation, master region):

POST /v1/objects/:key
Authorization: Bearer <token>
Idempotency-Key: 7f1c...           # dedups retried mutations + invalidations
{ "value": { ... } }

200 OK
{ "key": "obj:123", "version": 8815 }
# Side effects, in order:
#   1. row committed to DB (binlog entry @v8815)   — durable
#   2. best-effort DELETE published to the bus      — fast, lossy
#   3. binlog tailer derives DELETE @v8815          — reliable, replayable

Invalidation message (on the bus):

{ "key": "obj:123", "op": "delete", "version": 8815, "region": "us-east", "source": "binlog|app|reconciler" }

A cache applies a delete only if version ≥ stored.version (older never overwrites newer); a lease-gated SET is rejected if its lease was invalidated. CDN purge is the same operation by Surrogate-Key.

Lease protocol (look-aside miss): GET key miss → cache returns (miss, lease_token); reader reads DB, then SET key value WITH lease_token; the SET is dropped if a DELETE invalidated lease_token in between. A token is re-issued at most once per ~10 s per key, which throttles the herd.

Cache entry (memcached value): value, version (monotonic per key), lease_token?, negative? flag, TTL. The version is the load-bearing field — it makes out-of-order and duplicate invalidations safe and makes staleness detectable.

DB of record (sharded by entity_id): the canonical rows. Each shard's binlog is the ordered, durable change log — the contract the whole invalidation pipeline is built on. Retained 72 h so a tailer can fall behind and replay.

Remote marker (per key, in the writing user's home-region cache pool, not the master): a short-lived flag set there when that region's write is forwarded to the master, so the read service's per-miss marker check is a local ~1 ms lookup and only reads of marked keys pay the cross-region hop to the master; it clears once replication catches up (conservative TTL tied to p99 replication lag), restoring read-your-writes.

Database choice — recommended. A sharded relational store (MySQL with binlog) for the record, memcached + mcrouter for the fleet, Kafka/Wormhole for the invalidation bus. Why MySQL: invalidation correctness rides on an ordered, durable, replayable per-shard log, and the binlog is exactly that. ScyllaDB/Cassandra (Discord) or DynamoDB are fine record stores if you tail their change streams (CDC / DynamoDB Streams) instead of a binlog. Redis/Valkey replaces memcached when you want richer data structures or built-in cross-region replication (EVCache). The one non-negotiable: the source of invalidations must be the DB's committed change log, not the application's best intentions.

Read path (the product, ~98% of traffic). Client → CDN → (edge miss) → Gateway → Read Service → Cache Fleet. On a cache hit the Read Service returns in ~1 ms. On a miss it takes a lease, reads the DB, and SETs the value back under the lease — single-flight collapses a herd of concurrent misses into one DB read. This e1 Client→CDN read is unauthenticated and only carries the public/non-PII read class; private/PII reads are authenticated (Cache-Control: private/no-store) and must skip the shared edge — that needs a direct authenticated Client → Gateway read edge (not modeled in the current graph, which only routes private reads through the CDN-fronted e1/e2).

Write path (the hard part). Client → Gateway → Write Service → DB of Record — writes take the direct, bearer-authenticated Client → Gateway edge and bypass the edge cache entirely (the CDN caches GET/HEAD only). The commit is the durable truth. The Write Service then fires a best-effort invalidation to the bus (low latency, allowed to be lost). Independently, the Invalidation Pipeline tails the DB binlog and publishes the reliable, versioned invalidation. Two paths, on purpose: the fast one for latency, the durable one for correctness. This is "write-through vs write-behind" made concrete — the best-effort publish behaves like an eager write-through of a delete; the binlog tail behaves like a guaranteed write-behind that can never forget.

Fan-out. The Invalidation Bus delivers each delete, partitioned by key-hash (per-key order), to the local Cache Fleet (targeted via mcrouter), every remote-region fleet, the Edge CDN (as a surrogate-key purge), and the Consistency Monitor. A dead-letter queue parks poison messages so one bad record cannot wedge a partition.

Cross-region. The DB binlog replicates to the EU DB Replica (async); the bus delivers invalidations to the EU Cache Fleet; the EU Read Service serves local reads but honors the remote marker to forward read-your-writes reads to the master. The EU fleet's version guard rejects a refill from a still-stale replica — defeating the invalidation-beats-replication race.

Reconciliation. The Consistency Monitor (Polaris-style) watches the invalidation stream, samples committed versions in the DB, and re-publishes a corrective invalidation for anything still stale — turning Two-Generals uncertainty into a measured, bounded SLO and draining the DLQ on recovery. Because it shares the bus's failure domain, the Synthetic Canary sits outside the pipeline entirely: it writes a probe through the real front door and reads it back directly from each fleet, paging if a probe is not reflected fleet-wide within SLO — the independent dead-man's-switch that catches the silent-staleness gray failure the monitor itself could be blind to.

Two Generals & the dual path

You can never confirm an invalidation was delivered, so don't build on confirmation. The best-effort publish from the Write Service is fast and lossy; the binlog tailer derives the same invalidation from the durable, ordered commit log and can replay it from any offset. Note this is log-tailing / CDC (the binlog is the ordered event log — an event-sourced-style projection feeds the caches), not a transactional-outbox table written inside the business transaction; we get at-least-once delivery deduped by the version guard, not exactly-once from an outbox row. Delivery is made idempotent (delete is reorder-safe) and version-guarded (older never overwrites newer). The TTL caps worst-case staleness from total loss. The Consistency Monitor measures what leaks through — but it shares the bus's failure domain (it consumes and re-publishes on the same bus), so the Synthetic Canary, living entirely outside the bus, is the actual dead-man's-switch. No single mechanism is sufficient; together they bound staleness to "<1 in 10^10 within 5 min" rather than promising zero.

Stale-set race & leases

The canonical look-aside bug: reader A misses, reads v1, stalls; writer commits v2 and invalidates; slow A now SETs v1, poisoning the cache until the next write or TTL. The fix is leases (NSDI'13): on a miss the cache hands A a token; a concurrent delete invalidates outstanding tokens, so A's late SET is rejected. The same token, re-issued at most once per ~10 s per key, throttles the thundering herd — one refiller, everyone else briefly serves stale or waits.

Write-through vs write-behind vs invalidate

Invalidate-and-refill (default): write DB, delete cache, next read refills. Cheap, reorder-safe, costs one miss. Write-through: write DB and SET the new value into the cache synchronously — gives instant read-your-writes but pays write latency and reintroduces the stale-set race (must be version-guarded), and a value-SET can lose a concurrent newer write. Write-behind (write-back): acknowledge into the cache and flush to the DB asynchronously — lowest write latency, but a crash loses acknowledged writes (unacceptable for durability-sensitive data) and the cache becomes a source of truth you must replicate. We invalidate by default and reserve write-through for keys that demand zero-miss read-your-writes.

Targeted vs broadcast fan-out

Broadcasting every invalidation to all ~1,950 hosts is 39M deliveries/sec — 390× the targeted rate. mcrouter's consistent-hash routing sends each delete to the one host that owns the key, per region. Broadcast is reserved for wildcard/surrogate purges where the key→host mapping is unknown (CDN cache-tags), and even there the CDN's purge plane fans out hub-to-spoke, not N×N.

Cross-region read-your-writes & the invalidation race

Two cross-region hazards. (1) Lag: a US write reaches EU seconds later, so an EU read sees stale data — fixed by the remote marker routing RYW reads to the master until replication catches up. (2) The race: a global-broadcast invalidation can arrive in EU before the replicated write, the EU fleet evicts, and a refill re-caches the still-stale replica value — fixed by version-guarded fills (reject a fill whose replica version is older than the invalidation's version). Meta's alternative is to derive each region's invalidations from that region's replicated binlog, so an invalidation can't outrun its data; we model the global-bus + version-guard approach (Netflix EVCache) and treat the per-region-binlog approach as the rejected alternative.

Hot keys & thundering herd

Traffic is Zipfian; one key can take 100k gets/sec. On expiry, 100k concurrent misses would crush the DB shard. Leases collapse that to one DB fetch; single-flight at the Read Service collapses concurrent in-process misses; TTL jitter (±10%) stops synchronized expiry; hot keys can be replicated across multiple cache keys or promoted to a per-region replica. The CDN absorbs the very hottest keys before they reach the origin at all.

Observability

SLIs (RED/USE per component): Read Service — request rate, error rate, p99 (RED); Cache Fleet — hit ratio, get p99, eviction rate, per-host connection saturation (USE); Bus — produce/consume rate, per-partition consumer lag, DLQ depth + age-of-oldest; Pipeline — per-shard binlog-tail lag; DB — commit rate, replication lag (in-region and cross-region). The headline SLI is the stale-read ratio from the Consistency Monitor, reported at 1/5/10-minute windows. But a measured SLI can lie by going silent — if the monitor dies, the stale-read ratio flatlines deceptively green. So two SLIs are independent of the monitor: the Synthetic Canary's probe-not-reflected-within-SLO signal (which exercises the real path from outside the bus) and a "monitor-not-reporting" alert that fires if the Consistency Monitor stops emitting its SLI for >60 s. SLO burn-rate alerts page on fast staleness burn and on invalidation-pipeline lag (binlog-tail >30 s, hard-page >6 h) before it becomes user-visible. The six dashboards on-call opens: (1) staleness SLI by region + timescale — with a freshness check that it's still updating; (2) invalidation pipeline lag (binlog tail → bus → apply); (3) cache hit-ratio & DB miss-QPS (stampede detector); (4) bus consumer lag + DLQ depth/age; (5) cross-region replication lag + remote-marker rate; (6) canary probe latency + CDN purge latency (the two fleet-wide edge signals). Tracing: the invalidation path is traced end-to-end (commit → tail → bus → apply) with head-based sampling (~1%) plus 100% sampling of the canary's write-then-read so a missed invalidation always has a trace.

Deploy & runtime

Rolling, never flush-all: a cache-tier deploy restarts hosts in small batches so the fleet never goes cold at once (a cold flush stampedes the DB). Cold-cluster warmup: a new/cold cluster reads through a warm one for hours before taking full traffic. Schema/format migrations of the invalidation message are backward-compatible (new fields optional) and rolled out consumer-first. Consumer-group rebalance on the bus is incremental (cooperative-sticky) so a deploy doesn't pause invalidation delivery. Secrets: the bus mTLS certs auto-rotate (cert-manager/SPIFFE) with an expiry-burn alarm independent of the pipeline — an expired cert silently stops all invalidations.

Multi-region / DR

Posture: active-active reads, single master region for writes (active-standby for the write path). Each region has a full cache fleet + DB replica and serves local reads. Writes route to the master region (single-writer-per-shard) so there are no conflicting cross-region invalidations. DR: losing a cache fleet is a non-event (reads miss to the local DB replica; RPO 0). Losing the master region is a deliberate promotion of a replica to master. Be honest about the two different RTOs here: the DB-promotion RTO is ~300 s (db_replica.failover.rtoSeconds) — the time to promote a replica and re-point the write service — but the user-facing region-failover RTO is realistically 5–15 min, because DNS TTLs, resolver caching, and sticky clients keep sending writes to the dead region long after promotion completes. Claiming a single 300 s number is how a postmortem ends up explaining why the flip "took 12 minutes" against a 5-minute SLO. RPO ~5 s (cross-region async replication lag — you lose up to 5 s of acknowledged master writes). Promotion is manual so a flapping link can't trigger a region flip. The invalidation bus is regional with cross-region mirroring, so a region loss doesn't lose the durable invalidation log.

Security

AuthN/Z: browser→edge is unauthenticated for cacheable GETs (so the CDN can serve them) and bearer-token on writes; every internal hop is mTLS. Tenant isolation: cache keys and surrogate keys are tenant-scoped so one tenant can't purge or read another's keys. PII: values may contain PII, so cache hosts are in-VPC, encrypted in transit, never persisted to disk (no RDB/AOF), and short-TTL'd. Threat headlines: (1) cache poisoning — an attacker-influenced key or a stale-set writes bad data; mitigated by version-guards + leases + immutable-once-written keys; (2) purge abuse — a forged surrogate-key purge as a DoS; mitigated by authenticating the purge API (e23 is auth: api-key) and rate-limiting it; (3) negative-cache poisoning — caching a 404 for a key that then exists; mitigated by short negative TTL + explicit invalidation of negatives on create. Vendor boundary: the Edge CDN is a managed third party (Fastly/Cloudflare) — its purge API has its own SLA and rate limits, so its surrogate-key purge is a best-effort fleet whose guarantee is bounded by the vendor and backstopped by the short edge TTL, exactly the Two-Generals posture applied one layer out.

Trade-offs we accepted (and the alternative we rejected)

• Look-aside + invalidate-by-delete over write-through-by-value. Rejected write-through-by-value because a value-SET races concurrent writes and reintroduces the stale-set bug; delete is reorder-safe. Cost: one refill miss per write.
• Dual-path invalidation (best-effort + binlog tail) over app-publish-only. Rejected app-publish-only because it's lossy and can't replay; the binlog can't forget a committed write. Cost: a second pipeline to run and monitor.
• Global bus + version-guard for cross-region over per-region-binlog-tail. Rejected nothing outright — both are real (EVCache vs Meta); we chose the global bus for operational simplicity and pay for it with the version-guard that defeats the invalidation-beats-replication race.
• Single master region over multi-master. Rejected multi-master because conflicting cross-region writes create conflicting invalidations needing reconciliation (CRDTs/LWW); single-writer-per-shard sidesteps it. Cost: cross-region write latency + a remote-marker for RYW.
• Eventual cache consistency with a measured SLO over strong consistency. Rejected strong (lease-everything / synchronous fan-out) because it would couple read latency to fleet-wide delivery; we accept bounded staleness and measure it. Cost: a Consistency Monitor and the admission that we're never at zero.
• TTL backstop over invalidation-only. Rejected invalidation-only because Two Generals guarantees some loss; TTL caps it. Cost: organic refills at TTL.

Failure modes & mitigations

Open questions for human review

• CDN purge plane is now wired (broker → cdn, e23) but modeled as a single managed kind: cdn fleet rather than kind: external. We keep the dedicated cdn kind (consistent with the rest of the catalog and its rich edge-TTL/surrogate-key internals) and capture the third-party/vendor-SLA nature in prose; at higher edge scale it deserves its own coreless-purge relay component (Cloudflare CacheDB). Confirm the kind choice.
• Gutter pool is modeled as a reserved sub-pool within the cache fleet node (idle hosts, ~2% capacity) rather than a separate tier, matching NSDI'13. Confirm that's the right altitude vs a dedicated gutter node.
• Per-region binlog-tail vs global bus for cross-region invalidation is presented as a chosen trade-off; a reviewer who values the "invalidation can't outrun its data" guarantee may prefer the Meta per-region model, which would add a tailer + bus per region.
• Write-through for a hot-RYW subset (e.g. a user's own profile) is discussed but not a separate path; confirm whether a small write-through lane is worth the extra complexity vs the remote marker alone.
• DLQ drain ownership is the Consistency Monitor here; some teams prefer a separate human-gated replay tool to avoid an automated replay re-introducing a fixed-then-unfixed bug.