Cache invalidation

Deep dive

How it works

Parts:

• Source of truth — database; its commit log orders every change
• Cache nodes — key to (value, expiry), a lease table, a tag-to-keys index, ordered keys for prefix ranges
• Purge messages — Key(k), Tag(t), Prefix(p); all idempotent
• Purge relay — tails the commit log, batches, sends to every node or region, retries until acknowledged
• TTL — the backstop for a lost or late purge

1. Read. Hit: return. Miss: the node issues a lease token, or answers "wait" if a live lease exists, so one reader refills (Facebook: one token per key per 10 s).
2. Fill. The reader reads the database, then sets with its token. The node accepts only a live token, then stores the value with TTL and tags.
3. Write. Commit to the database, then emit purges for the affected keys, tags or prefixes. Purging before the commit lets a reader re-cache the old row.
4. Purge. Remove the key and void its lease. A tag purge removes each key in the index; a prefix purge walks an ordered range. Both cancel all in-flight leases (the index knows only cached keys).
5. Propagate. The relay delivers each message to every node at least once; duplicates converge.
6. Expire. TTL removes what a lost purge left.

 writer ─SQL─► DB ─commit log─► relay ─batch─► node 1 ┐
                  (ordered)       │ retry      node 2 ├ delete / tag / prefix, void leases
                                  └──────────► node N ┘
 reader ─ get ─► node: Hit | Miss(token) | Wait
        └ read DB, set(token) ─► accepted only if the token survived

Code

use std::collections::{BTreeMap, HashMap, HashSet};

#[derive(Debug, PartialEq)]
pub enum Get { Hit(String), Miss(u64), Wait } // Miss carries a lease token

#[derive(Default)]
pub struct Node {
    data: BTreeMap<String, (String, u64)>,  // key -> (value, expires_at); ordered for prefix ranges
    leases: HashMap<String, (u64, u64)>,    // key -> (token, lease expires_at)
    tags: HashMap<String, HashSet<String>>, // tag -> cached keys
    next_token: u64,
}

impl Node {
    pub fn get(&mut self, k: &str, now: u64) -> Get {
        if let Some((v, exp)) = self.data.get(k) {
            if *exp > now { return Get::Hit(v.clone()); }
            self.data.remove(k);                      // lazy TTL expiry
        }
        if matches!(self.leases.get(k), Some((_, e)) if *e > now) { return Get::Wait; }
        self.next_token += 1;                         // one filler per key per lease term
        self.leases.insert(k.into(), (self.next_token, now + 10));
        Get::Miss(self.next_token)
    }
    /// Fill after a miss; fails if a delete or purge voided the lease meanwhile.
    pub fn set_leased(&mut self, k: &str, v: &str, tok: u64, tags: &[&str], ttl: u64, now: u64) -> bool {
        if !matches!(self.leases.get(k), Some((t, _)) if *t == tok) { return false; }
        self.leases.remove(k);
        self.set_blind(k, v, tags, ttl, now);
        true
    }
    /// Unconditional set: the racy path.
    pub fn set_blind(&mut self, k: &str, v: &str, tags: &[&str], ttl: u64, now: u64) {
        self.data.insert(k.into(), (v.into(), now + ttl));
        for t in tags { self.tags.entry(t.to_string()).or_default().insert(k.into()); }
    }
    pub fn delete(&mut self, k: &str) { self.data.remove(k); self.leases.remove(k); }
    pub fn purge_tag(&mut self, tag: &str) {
        for k in self.tags.remove(tag).unwrap_or_default() { self.data.remove(&k); }
        self.leases.clear(); // the index knows only cached keys: cancel all in-flight fills
    }
    pub fn purge_prefix(&mut self, p: &str) {
        let keys: Vec<String> = self.data.range(p.to_string()..)
            .take_while(|(k, _)| k.starts_with(p)).map(|(k, _)| k.clone()).collect();
        for k in keys { self.data.remove(&k); }
        self.leases.clear();
    }
}

pub enum Purge { Key(String), Tag(String), Prefix(String) }

pub struct Cluster { pub nodes: Vec<Node>, pub db: HashMap<String, String> }

impl Cluster {
    /// Idempotent on every node, so a log or pub/sub replay may deliver it twice.
    pub fn apply(&mut self, p: &Purge) {
        for n in &mut self.nodes {
            match p { Purge::Key(k) => n.delete(k), Purge::Tag(t) => n.purge_tag(t), Purge::Prefix(x) => n.purge_prefix(x) }
        }
    }
    /// Database first, then purge (in production a commit-log relay sends the purge).
    pub fn write(&mut self, k: &str, v: &str) {
        self.db.insert(k.into(), v.into());
        self.apply(&Purge::Key(k.into()));
    }
}

fn main() {
    let mut c = Cluster { nodes: vec![Node::default(), Node::default()], db: HashMap::new() };
    c.db.insert("user:1".into(), "v1".into());
    // Blind set: the reader holds v1 while the writer commits v2 and deletes.
    let Get::Miss(_) = c.nodes[0].get("user:1", 0) else { panic!() };
    let seen = c.db["user:1"].clone();
    c.write("user:1", "v2");
    c.nodes[0].set_blind("user:1", &seen, &[], 60, 1);
    assert_eq!(c.nodes[0].get("user:1", 2), Get::Hit("v1".into()));  // stale until the TTL
    assert!(matches!(c.nodes[0].get("user:1", 61), Get::Miss(_)));   // TTL is the safety net
    // Same interleaving with a lease: the delete voids the token, the late set fails.
    let Get::Miss(tok) = c.nodes[1].get("user:1", 0) else { panic!() };
    assert_eq!(c.nodes[1].get("user:1", 0), Get::Wait);              // second reader waits
    c.write("user:1", "v3");
    assert!(!c.nodes[1].set_leased("user:1", &seen, tok, &[], 60, 1));
    // Tag and prefix purge, delivered twice: same end state.
    for n in &mut c.nodes {
        n.set_blind("post:1", "a", &["feed:7"], 60, 0);
        n.set_blind("img:9/s", "c", &[], 60, 0);
    }
    for _ in 0..2 { c.apply(&Purge::Tag("feed:7".into())); c.apply(&Purge::Prefix("img:9/".into())); }
    for n in &mut c.nodes {
        assert!(matches!(n.get("post:1", 1), Get::Miss(_)) && matches!(n.get("img:9/s", 1), Get::Miss(_)));
    }
}

The asserts show a blind late set keeping v1 until the TTL, and a lease rejecting it.

Complexity and constants

• Tag purge: one index lookup, then one removal per key. Prefix purge: one range seek, then one removal per match. Fan-out: O(nodes) messages per purge.
• mcsqueal: only 4% of deletes hit a cached key; most purge traffic removes nothing.
• Measured on this Mac (Apple M4 Pro), in process, one thread, 16 nodes x 100,000 keys, 100 keys per tag (3 runs): tag purge 97-113 ns per key removed (89-103K node-applications/s); prefix purge of 100 contiguous keys 71-73 ns per key (137-142K node-applications/s). No network: a CPU floor only.
• Staleness window = relay delay + retries. Facebook: four nines of deletes applied within 1 s in the master region, three nines elsewhere.

Efficiency

• Cost: O(keys removed) CPU per node plus one message per node; about 100 ns per removed key in process (measured above). At scale the bound is the network and relay delay.
• Levers:
  • batch deletes per destination — 18x more deletes per packet (Nishtala et al.) — many databases feeding many cache servers
  • one lease holder per key — peak database queries 17K/s to 1.3K/s (same paper) — hot, frequently written keys
  • soft purge: mark stale, serve while revalidating — avoids origin spikes (Fastly docs) — content that tolerates seconds of staleness
  • skip nodes that cannot hold the key — a per-node Bloom filter digest might save messages (inference, not measured) — large fleets
• Naive → standard → state of the art:
  • TTL only · stale up to the TTL
  • delete after the database write, from the app · fresh normally, stale after a lost delete or late set
  • commit-log deletes, batched, with leases and TTL · seconds of staleness, bounded by relay delay

Implementation notes

• Drive deletes from the commit log, not the web tier: lost deletes can be replayed (Nishtala et al.). See change data capture and transactional outbox.
• HTTP caches must drop the target URI after a non-error response to an unsafe method, and may drop same-origin Location and Content-Location URIs (RFC 9111 4.4).
• Header limits: Cloudflare Cache-Tag 16 KB (about 1,000 tags); Fastly Surrogate-Key 1 KB per token, 16 KB per header.
• Redis CLIENT TRACKING pushes an invalidation to each connection that read a key (RESP3); BCAST with PREFIX pushes by prefix. A disconnect flushes the client's local cache.

Pitfalls

• Purge before the commit. A reader refills the old row in between. Database first.
• Set instead of delete on write. Two writers' sets can reorder.
• Late refill after a delete. Lease tokens, or a hold-off that rejects add after a delete (Facebook: 2 s on cold-cluster deletes), close it.
• Shield or tier races. A purged edge refills from an unpurged upper tier. Fastly advises purging twice, about 2 s apart for URL and key purges; see origin shielding.
• Pub/sub as the only channel. Events are lost while a subscriber is disconnected; keep a TTL or a log.
• Tag index leaks. Entries for expired keys dangle until their tag is purged.
• Purge storms. A wide tag empties the cache; the origin sees a stampede.

Variants and alternatives

In production

Facebook memcache and TAO; Fastly surrogate keys; Cloudflare purge by tag and prefix; Varnish xkey; Redis and Valkey client-side caching.

Implementations

Sources

• Rajesh Nishtala et al., Scaling Memcache at Facebook, NSDI 2013. paper
• Nathan Bronson et al., TAO: Facebook's Distributed Data Store for the Social Graph, ATC 2013. paper
• Fielding, Nottingham, Reschke, HTTP Caching, RFC 9111, 2022. RFC
• Fastly, Working with surrogate keys, Soft purges. docs
• Cloudflare, Purge cache (tags, prefix, limits). docs
• Redis, Client-side caching, CLIENT TRACKING, Keyspace notifications. docs