Write a policy

1. What a policy is

A decision policy is a small piece of code that answers one question, repeatedly, with incomplete information. Which cached item should I drop? Should this request go through? How long before I retry? Which parts of this context can I forget?

What the four have in common is the shape of the problem, not the subject. Each sees a stream of events, keeps some state, and must commit to an answer now, with no knowledge of what is coming next. That last constraint is the whole difficulty. A policy that could see the future would be easy to write and impossible to deploy, which is exactly what Bélády's OPT is: a bound, not a candidate.

Every policy in this registry is described by a policy.json that the catalog validates. Nothing on this site is hand-maintained alongside the code. It is all read from files like this one.

{
  "id": "cache/lru",
  "name": "LRU",
  "domain": "cache",
  "summary": "Evict the key used longest ago. The default baseline, and what most people mean when they say \"cache\".",
  "source": { "type": "folklore" },
  "complexity": { "time": "O(1)", "space": "O(n)" },
  "params": [
    {
      "name": "capacity",
      "type": "number",
      "default": 1000,
      "description": "Maximum number of entries held."
    }
  ],
  "tags": ["baseline", "recency", "default"],
  "recommended": false,
  "ports": ["ts", "python", "c"],
  "notes": null,
  "status": "stable"
}

2. Read the interface

Each domain has one interface, and every policy in it implements exactly that. Here is the whole of the cache one: two required methods and an optional third.

export interface CachePolicy<K> {
  /**
   * Called on every lookup, before insertion on a miss.
   *
   * `hit` says whether the key was resident. A policy learns everything it
   * knows from this call.
   */
  onAccess(key: K, hit: boolean, meta?: CacheMeta): void;

  /**
   * Called when capacity is exceeded. Returns the key to remove.
   *
   * The returned key must currently be resident; the harness treats anything
   * else as a bug in the policy.
   */
  evict(): K;

  /**
   * Optional admission control. Return false to skip inserting the key.
   *
   * Policies like W-TinyLFU use this to keep a one-hit wonder from displacing
   * something valuable.
   */
  admit?(key: K, meta?: CacheMeta): boolean;

Note what is not here. There is no get, no put, and no storage of values. The harness owns the cache contents while the policy owns only the decision. That separation is why a policy is a few dozen lines rather than a data structure library, and why the same policy can be implemented in TypeScript, Python and C against one set of test vectors.

Here is LRU implementing it. Two methods, an intrusive doubly-linked list, and no allocation once it is warm.

onAccess(key: K, hit: boolean): void {
  if (hit) {
    const slot = this.index.get(key);
    if (slot === undefined) {
      throw new Error(`Lru: onAccess reported a hit for a key it does not hold: ${String(key)}`);
    }
    this.moveToFront(slot);
    return;
  }

  if (this.freeCount === 0) {
    throw new Error(
      `Lru: ${this.capacity + 1} entries inserted without an evict, capacity is ${this.capacity}. ` +
        "Call evict() once the cache is over capacity.",
    );
  }

  this.freeCount -= 1;
  const slot = this.freeSlots[this.freeCount]!;
  this.keys[slot] = key;
  this.index.set(key, slot);
  this.linkFront(slot);
}

evict(): K {
  if (this.tail === NIL) {
    throw new Error("Lru: evict() called with nothing resident");

3. Run one

This is that same file, running in your browser on a generated trace. Not a reimplementation for display: the runner imports policies/cache/lru/index.ts, the one you just read, and the benchmark numbers on LRU's page come from it too.

Press play. The grid is the cache, in the order LRU holds it, and the line beneath is the running hit rate against the best any policy could have done knowing the whole future.

Try scan-heavy. LRU loses its whole working set to a scan it will never see again, which is the failure that most of the other cache policies exist to avoid.

4. Write your own

Start with the scaffold, which writes all four files for you:

$ pnpm policybook new cache/my-policy

  policies/cache/my-policy/policy.json     metadata the catalog validates
  policies/cache/my-policy/index.ts        the implementation
  policies/cache/my-policy/vectors.gen.ts  hand-written expectations
  policies/cache/my-policy/README.md       the explainer page

Then write the simplest thing that satisfies the interface. Here is one that does, badly and on purpose. When the cache is full it throws out whatever arrived most recently, which means it spends every eviction undoing the insert that caused it.

export default class EvictNewest {
  private readonly capacity: number;
  /** Insertion order, oldest first. */
  private readonly order: number[] = [];

  constructor(params: { capacity: number }) {
    this.capacity = params.capacity;
  }

  /**
   * Called for every request, hit or miss.
   *
   * On a hit there is nothing to do: the key is already resident and this
   * policy does not care how often or how recently anything is used. On a miss
   * the harness is about to insert the key, so it goes on the end.
   */
  onAccess(key: number, hit: boolean): void {
    if (!hit) this.order.push(key);
  }

  /**
   * Called when the cache is over capacity. Return the key to drop.
   *
   * The newest is the one we just inserted, which means this policy spends
   * every eviction undoing the insert that caused it. The cache therefore
   * settles at `capacity` items and then almost never changes, which is exactly
   * what the runner shows.
   */
  evict(): number {
    const victim = this.order.pop();
    if (victim === undefined) throw new Error("evict() with nothing resident");
    return victim;
  }

  /** Optional introspection, the same method SIEVE exposes. Unused here. */
  sizeOf(): number {

Predict what happens before you press play. The cache fills with the first thousand distinct keys and then never changes again, so the hit rate is simply how often the trace asks for one of those.

Now the part worth slowing down for. On the everyday Zipf trace, EvictNewest scores 0.6711 against LRU's 0.6714, a gap of 0.0003. A policy designed to be as bad as possible is, on the workload most people would reach for first, indistinguishable from the one every textbook teaches.

It is not that EvictNewest is fine. It is that a stationary trace cannot tell the two apart: when the popular keys never change, holding the first thousand of them is very nearly the right answer. Switch to shifting-popularity and the same policy scores 0.2953 against 0.6670, a gap of 0.3717 , about 1,239× wider.

That is the most useful thing on this page. A benchmark can only find a difference its workload contains, so the first question about any result is not "which policy won" but "would this trace have noticed if the answer were wrong". Try both:

EvictNewest's frozen cache keeps answering yesterday's question. A policy that cannot forget is as broken as one that forgets everything, but you only find out on a workload that changes its mind.

5. Verify it, then port it

One command checks a policy against everything the registry expects of it: the metadata schema, the vectors in every language that implements it, and the invariants the harness enforces.

$ pnpm policybook verify cache/my-policy

  policy.json      valid
  vectors          31 cases, 118 expectations
  typescript       31/31 pass
  python           31/31 pass
  c                31/31 pass
  invariants       evict() returned a resident key in every case

Porting is then a matter of making the same vectors pass. The Python and C implementations read the same vectors.json, so there is no second definition of correct to keep in sync. If all three pass, all three agree, and CI runs them on every commit.

That is the whole loop: an interface, an implementation, vectors that pin it, and a benchmark that says what it costs. Everything on this site is generated from those four things.

Compare the real ones → or browse the cache policies

★Star on GitHub If this was useful, a star helps other people find it.