Edge Cache: Cache Keys, Stale Windows and Purges

Edge Cache: Cache Keys, Stale Windows and Purges

You've joined the delivery team that runs the HTTP cache on your company's CDN edge nodes. This repo is a deterministic simulation of one node: client requests arrive, the node answers from its cache or fetches from an origin server that ops can reconfigure at any time. Three things are queued up for you:

1. Incident review (Part 1). Support has three open tickets: users in Montreal got the English page after a French user warmed the cache; a logged-in dashboard was served to a different user; and campaign links with tracking parameters keep hammering the origin. Make the node's cache keys and freshness rules correct.
2. Origin latency (Part 2). Origins are slow. Add stale-while-revalidate, stale-if-error and request coalescing.
3. Purging (Part 3). Editors need to purge content by surrogate key, including a "soft purge" that marks content stale instead of deleting it. It must reach every variant of a page.

All times are integer seconds. Nothing here uses a wall clock: time only comes from the ts of each operation.

Codebase

The code is the source of truth for conventions this README only points at (header-name casing, how Cache-Control is parsed, how templates render, what stats counts). Read it before you change it.

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh edge node and origin and returns one result per operation. Every operation is [name, ts, ...args]. ts is an integer and never decreases. Errors are returned as strings, never raised. Operations are checked in this order: not a list, fewer than two items, a non-string name or a non-integer ts (true is not an integer) gives "error: invalid arguments"; an unknown name gives "error: unknown operation"; a wrong number of arguments or an invalid argument gives "error: invalid arguments".

origin spec. A JSON object; every field is optional: status (int, default 200), cache_control (string, default ""), vary (string, default ""), surrogate_key (string, default "", used from Part 3), body (string, default "") and latency (int seconds >= 0, default 0, used from Part 2). Any other type is invalid. The origin answers a request for path (the URL without its query string) from the exact route if there is one, otherwise from the longest registered route ending in /* whose prefix the path starts with (/img/* matches /img/a.png), otherwise with 404, body "not found", no headers, latency 0. Re-registering a route changes future origin answers only; it never touches responses the edge already stored. body and surrogate_key are templates: {last} becomes the final segment of the request path and {h.name} becomes that request header's value ("-" if the request did not send it).

request. method is a string (case-sensitive), url starts with / and may carry a query string and a #fragment, headers is an object of string values. The reply is {"cache": <label>, "status": <int>, "age": <int>, "body": <string>}. warm issues count GET requests at that one instant, for url_template with {i} replaced by 0 .. count-1 in order, and returns how many replies carried each cache label (keys sorted). It behaves exactly like count separate request operations at the same ts. stats reports every origin fetch made so far (of any kind, including PASS) and the number of entries in the store (expired ones included; nothing is evicted for age).

---

Part 1: Fix the cache key and the freshness rules

Goal. The three tickets come from wrong behaviour in the key and the policy code. Make the node follow the rules below. Labels used in this Part: HIT (served from cache), MISS (fetched from the origin), PASS (not cacheable method). In this Part every origin fetch completes instantly (ignore latency).

1. Only GET is cacheable. Any other method (POST, HEAD, even lower-case get) is fetched from the origin, answered with label PASS and age 0, and never reads or changes the store.
2. Normalised URL. Drop the #fragment. Split the query on &, ignore empty segments, split each segment at its first = into (name, value); a bare flag and flag= are the same parameter. Drop parameters whose name is listed in config.EDGE_IGNORED_PARAMS (exact, case-sensitive). Sort the rest by (name, value) using plain string comparison, rebuild them as name=value joined by &, and omit the ? when none remain. The path is compared as written; percent-escapes are never decoded.
3. Variants (Vary). The edge remembers, per normalised URL, the Vary header names of the response it stored most recently for that URL. A request's cache key is its normalised URL plus the request's value for each remembered name. Names are case-insensitive and treated as a set (order and repeats do not matter); values are compared exactly after trimming surrounding whitespace; a header the request did not send counts as an empty value. Headers the response does not list never affect the key. A response without Vary is a single entry per URL. If a newly stored response has a different Vary than the previous one, requests from then on use the new names; entries stored under the old names are no longer found (they stay in the store until replaced).
4. What may be stored. Only statuses in config.EDGE_CACHEABLE_STATUSES (200 and 404). This is a *shared* cache: a response with a private or no-store directive (names are case-insensitive; private="set-cookie" counts) is never stored, and neither is one whose Vary includes *. Other directives (public, no-cache, must-revalidate, anything unknown) are ignored by this edge. A response that is not stored is returned as MISS and leaves the store untouched.
5. Lifetime. s-maxage if present (including 0), otherwise max-age, otherwise EDGE_DEFAULT_TTL for a 200 and EDGE_NEGATIVE_TTL for a 404. A directive that is not a whole number counts as absent; if a directive repeats, the first one wins. headers.parse_cache_control already does this parsing.
6. Freshness. A stored response's age at ts is ts - stored_at. It is fresh while age < lifetime, and from age == lifetime it is expired. A fresh response is a HIT carrying the stored status and body and its age. A missing or expired one is fetched from the origin and, if storable, replaces the entry; the reply is MISS, age 0, with the origin's status and body.

Worked example. Tracking parameters are ignored and age counts from when the response was stored:

[["origin", 0, "/logo.png", {"cache_control": "max-age=60", "body": "png"}],
 ["request", 5, "GET", "/logo.png?utm_source=mail", {}],
 ["request", 25, "GET", "/logo.png", {}],
 ["request", 65, "GET", "/logo.png", {}]]

returns true, {"cache":"MISS","status":200,"age":0,"body":"png"}, {"cache":"HIT","status":200,"age":20,"body":"png"}, {"cache":"MISS","status":200,"age":0,"body":"png"} (the entry was stored at 5 and expired at 65). With vary: "Accept-Encoding" and body: "page:{h.accept-encoding}" a gzip request, a br request and a second gzip request (header sent as Accept-Encoding) give MISS page:gzip, MISS page:br, HIT page:gzip.

---

Part 2: Origin latency, stale windows and request coalescing

Goal. Origin fetches now take time, and the node must stop stampeding the origin when a popular object expires. A fetch no longer completes instantly: it completes latency seconds after it starts, the cache learns the response only then, and a request that arrives meanwhile can wait for it instead of starting another fetch. Add two more response directives, stale-while-revalidate and stale-if-error. New labels: STALE and HIT-WAIT.

1. Fetch timing. A fetch that starts at ts uses the origin's answer as registered at ts and completes at ts + latency (of that answer). A storable response is stored at completion, with stored_at = the completion time, so its age and its expiry count from then, not from when the fetch started. Until completion the fetch is *in flight* and the cache does not know the response. Before any operation runs at ts (a request, stats, origin or anything else), every fetch that completes at or before ts is stored, oldest completion first (ties in start order). A request at exactly the completion time therefore sees a normal HIT of age 0.
2. Windows. stale-while-revalidate=N and stale-if-error=M come from the stored response's Cache-Control (absent or not a whole number means 0). Let expires = stored_at + lifetime (lifetime from Part 1 rule 5).
3. Serving a request for a key (Part 1 rules 2 and 3 still define it), in this order, at time ts:
4. ts < expires: HIT, as in Part 1.
5. expires <= ts < expires + N: reply STALE with the stored status and body and age ts - stored_at, and start a background fetch unless a fetch for that cache key is already in flight. A background fetch that completes with a storable response replaces the entry; any other outcome (5xx, private, ...) is dropped and the old entry stays, so the next stale request starts another one.
6. Otherwise, if an in-flight fetch can be shared (rule 4): HIT-WAIT, with that fetch's status and body and age 0. No origin fetch is made.
7. Otherwise start a fetch now. If the response is storable the reply is MISS (origin status and body, age 0; the reply does not model the wait). If it is not storable, its status is >= 500 and a stale entry exists with ts < expires + M, the reply is STALE with that entry (age ts - stored_at). Otherwise the reply is MISS with the origin's response, and the stale entry stays as it was. stale-if-error only ever answers 5xx; a 403, a 404 or a successful response replaces or bypasses the stale copy as usual.
8. Coalescing. A request can share an in-flight fetch when the fetch's response is storable, it is for the same normalised URL, and the request's variant matches: build the request's key with the in-flight response's own Vary names (the store may not know them yet) and compare it with the key that response will be stored under. A fetch is in flight from its start up to, but not including, its completion time. Responses that are not storable are never shared: each such request makes its own origin fetch. A request after the revalidation window can join an in-flight background fetch the same way.

Worked example.

[["origin", 0, "/news", {"cache_control": "max-age=10, stale-while-revalidate=20", "latency": 3, "body": "v1"}],
 ["request", 0, "GET", "/news", {}],
 ["request", 1, "GET", "/news", {}],
 ["request", 5, "GET", "/news", {}],
 ["origin", 6, "/news", {"cache_control": "max-age=10, stale-while-revalidate=20", "latency": 3, "body": "v2"}],
 ["request", 14, "GET", "/news", {}],
 ["request", 15, "GET", "/news", {}],
 ["request", 17, "GET", "/news", {}],
 ["stats", 17]]

returns true; MISS v1 (fetch runs 0 to 3); HIT-WAIT v1 age 0 (fetch in flight at 1); HIT v1 age 2 (stored at 3, expires at 13); true; STALE v1 age 11 (14 is inside [13, 33), a background fetch starts and will complete at 17); STALE v1 age 12 (that fetch is still in flight, so no second one); HIT v2 age 0 (stored at 17); and {"origin_fetches": 2, "entries": 1}.

---

Part 3: Purge and soft purge by surrogate key

Goal. Editors tag content with surrogate keys and need to invalidate it by tag. The origin's surrogate_key field is a space-separated list of tokens (rendered as a template like body, tokens are case-sensitive, a repeated token counts once). Every stored entry remembers the tokens of the response it was stored from. A tag typically covers many URLs and, for each URL, every Vary variant (and every query variant) of it.

1. ["purge", ts, token] deletes every stored entry that carries token: all variants, all query forms, expired entries and entries orphaned by a changed Vary included. Returns how many entries were deleted (0 if none).
2. ["soft_purge", ts, token] marks every entry carrying token stale as of ts without deleting it: its expiry becomes min(its expiry, ts). stored_at and the age counter are untouched. From then on it follows the Part 2 rules as an entry that has expired at that moment: its own stale-while-revalidate window runs from the new expiry, its stale-if-error window likewise, and without a window the next request refetches synchronously. A soft purge can only make an entry expire sooner, never later. Returns how many entries matched (even entries that were already expired).
3. ["sweep", ts, action, template, count] runs purge or soft_purge (action must be one of those two strings) for each token template with {i} replaced by 0 .. count-1, in order, all at ts, and returns the total of the results. token/template must be non-empty strings and count an integer in 0 .. config.EDGE_MAX_WARM, otherwise "error: invalid arguments".
4. Purges see exactly the entries stored by ts (completions at or before ts happen first, Part 2 rule 1). They do not cancel fetches that are still in flight: such a fetch stores its response when it completes.
5. When a response replaces an entry under the same key, only the new response's tokens count from then on.
6. Sweeps over thousands of tokens and entries must stay fast. Earlier Parts are unchanged: all rules above still hold for requests made before and after purges.

Worked example.

[["origin", 0, "/a", {"cache_control": "max-age=60, stale-while-revalidate=30", "vary": "accept-encoding",
                      "surrogate_key": "news home", "body": "a:{h.accept-encoding}"}],
 ["request", 0, "GET", "/a", {"accept-encoding": "gzip"}],
 ["request", 1, "GET", "/a", {"accept-encoding": "br"}],
 ["soft_purge", 10, "news"],
 ["request", 10, "GET", "/a", {"accept-encoding": "gzip"}],
 ["request", 11, "GET", "/a", {"accept-encoding": "gzip"}],
 ["request", 11, "GET", "/a", {"accept-encoding": "br"}],
 ["purge", 12, "home"],
 ["stats", 12],
 ["request", 13, "GET", "/a", {"accept-encoding": "gzip"}]]

returns true, MISS a:gzip, MISS a:br, 2 (both variants), STALE a:gzip age 10 (expiry pulled back to 10; a background fetch replaces the entry at 10), HIT a:gzip age 1, STALE a:br age 10 (its revalidation also replaces it), 2 (both replaced entries still carry home), {"origin_fetches": 4, "entries": 0}, and a MISS a:gzip at 13.