cache-policy-comparison

name	cache-policy-comparison
version	1.1.1
description	Compares bounded-cache eviction in stdlib Python: LRU, LFU, FIFO, S3FIFO classes plus a same-trace replay harness for hit rate and residency. Use when picking a policy for a buffer pool, page cache, CDN edge, or LLM KV cache, or when lining up policies on one trace. Not a Redis/Memcached operations guide and not for deploying production cache clusters.
risk	safe
source	openrouter-deepsearch
date_added	2026-06-16T00:00:00.000Z

Overview

An eviction policy decides which resident entry a cache removes when a new entry is admitted beyond capacity. This skill provides production-grade, standard-library-only implementations of four core policies — LRU, LFU, FIFO, and S3FIFO — plus a replay-and-compare harness that drives an identical trace through all of them at the same capacity and lines up the results.

Four policies cover almost every replay-and-measure task:

Policy	Data structure	On hit	On admit	Eviction choice
LRU	OrderedDict	Move to tail	Append at tail	Pop head
LFU	{key: freq} + insertion order	freq[k] += 1	freq[k] = 1	Min freq, tiebreak by insertion order
FIFO	OrderedDict	Nothing	Append at tail	Pop head
S3FIFO	Three FIFO queues + freq[k]	freq[k] = min(freq+1, cap)	Admit to small; ghost-hit admits to main	Second-chance on main; small drains to main/ghost

Each has subtleties that trip naive implementations. The implementations target CPython 3.12 (current as of 2026) and lean only on the standard library (collections, itertools, dataclasses, typing), keeping the comparison portable and avoiding behavior that shifts between releases.

When to Use

Use this skill when:

• Choosing or implementing an eviction policy for a buffer pool, page cache, CDN edge, or LLM KV cache.
• Writing a replay simulator that supports multiple policies.
• Comparing hit rates across LRU, LFU, FIFO, S3FIFO, and ARC policies.
• Understanding recency vs frequency semantics, queue topology, saturating counters, ghost buffers, and the second-chance rule that distinguishes modern FIFO-family policies from classic LRU.
• You need to clarify the distinction between a cache hit (token accounting) and a rank change (eviction order) — especially for FIFO, where a hit is still a hit but does not reorder.

Trigger keywords: eviction policy, LRU, LFU, FIFO, S3FIFO, ARC, cache hit rate, buffer pool, page cache, CDN edge, LLM KV cache, prefix cache replay, second-chance eviction, ghost queue, saturating counter.

Prerequisites

• Python: CPython 3.12 or later. The code uses from __future__ import annotations, Protocol with runtime_checkable, and PEP 695-style type aliases where applicable.

• Standard library only: No third-party packages required. Do not reach for deprecated APIs or unmaintained libraries.

• Type checker (recommended): mypy --strict or pyright for verification. See Verification.

• Windows host (primary): PowerShell is the primary shell. All commands below assume PowerShell syntax. On Windows, run Python via python (not python3). Example:

  python --version
  python -m pip install --upgrade pip
  

• Self-contained notes: S3FIFO second-chance eviction, ghost-queue admission, and ARC's adaptive recency/frequency split are documented in the S3FIFO procedure and the Extending to ARC example below. This folder does not include extra paper notes.

Procedure

Step 1 — Implement LRU

LRU bets that the recent past predicts the near future: the key you touched most recently is the one you are most likely to touch again, so the least recently used key is the safest to evict. An OrderedDict makes this cheap because it remembers insertion/move order — keep the most-recently-accessed key at the tail, and the eviction victim is always whatever sits at the head.

On a hit, move the key to the tail (move_to_end) so it is no longer a candidate for eviction. On a miss, insert at the tail and, if you are now over capacity, pop the head.

The single most common bug is forgetting to refresh recency on a hit. Skip the move_to_end and every key keeps its original insertion rank regardless of how often it is used — which is exactly FIFO.

from collections import OrderedDict
from collections.abc import Hashable


class LRU:
    """Least-Recently-Used cache tracking residency only (values are not stored)."""

    def __init__(self, capacity: int) -> None:
        if not isinstance(capacity, int) or isinstance(capacity, bool):
            raise TypeError(f"capacity must be an int, got {type(capacity).__name__}")
        if capacity <= 0:
            raise ValueError(f"capacity must be positive, got {capacity}")
        self.capacity: int = capacity
        self._order: "OrderedDict[Hashable, None]" = OrderedDict()

    def contains(self, key: Hashable) -> bool:
        return key in self._order

    def resident_count(self) -> int:
        return len(self._order)

    def access(self, key: Hashable) -> :
        
         key  :
             ValueError()
         key  ._order:
            ._order.move_to_end(key)  
             
        ._order[key] = 
         (._order) > .capacity:
            ._order.popitem(last=)  
         

Step 2 — Implement LFU

LFU makes the opposite bet from LRU: popularity, not recency, predicts the future, so the key accessed the fewest times is the safest to evict. That requires two pieces of state — a frequency count per key and a tiebreaker for when counts are equal. An always-incrementing insertion counter is the simplest deterministic tiebreaker: when several keys share the minimum frequency, evict the one inserted earliest.

On a hit, increment that key's frequency. On a miss at capacity, evict the key with the minimum frequency, breaking ties toward the oldest insertion.

import itertools
from collections.abc import Hashable


class LFU:
    """Least-Frequently-Used cache with deterministic insertion-order tiebreaking."""

    def __init__(self, capacity: int) -> None:
        if not isinstance(capacity, int) or isinstance(capacity, bool):
            raise TypeError(f"capacity must be an int, got {type(capacity).__name__}")
        if capacity <= 0:
            raise ValueError(f"capacity must be positive, got {capacity}")
        self.capacity: int = capacity
        self._freq: dict[Hashable, int] = {}
        self._seq: dict[Hashable, int] = {}  # insertion order, the deterministic tiebreaker
        self._counter: "itertools.count[int]" = itertools.count()

    def contains(self, key: Hashable) -> bool:
        return key in self._freq

    def resident_count(self) -> :
         (._freq)

     () -> :
        
         key  :
             ValueError()
         key  ._freq:
            ._freq[key] += 
             
         (._freq) >= .capacity:
            ._evict_one()
        ._freq[key] = 
        ._seq[key] = (._counter)
         

     () -> :
        
        victim: Hashable = (._freq, key= k: (._freq[k], ._seq[k]))
         ._freq[victim]
         ._seq[victim]

Step 3 — Implement FIFO

FIFO makes no bet about the future at all: it evicts in the order keys arrived, ignoring both how recently and how often they were used. That makes it the natural lower-bound baseline — any policy that tracks access patterns should beat it, and if yours does not, that gap is a signal something is wrong in your richer policy.

The defining property is that a hit does not reorder anything. A hit is still counted as a hit for accounting, but the key keeps its arrival rank, so eviction always removes the oldest-inserted resident.

from collections import OrderedDict
from collections.abc import Hashable


class FIFO:
    """First-In-First-Out cache. Hits are recorded but never change eviction order."""

    def __init__(self, capacity: int) -> None:
        if not isinstance(capacity, int) or isinstance(capacity, bool):
            raise TypeError(f"capacity must be an int, got {type(capacity).__name__}")
        if capacity <= 0:
            raise ValueError(f"capacity must be positive, got {capacity}")
        self.capacity: int = capacity
        self._order: "OrderedDict[Hashable, None]" = OrderedDict()

    def contains(self, key: Hashable) -> bool:
        return key in self._order

    def resident_count(self) -> int:
        return len(self._order)

    def access(self, key: Hashable) -> :
        
         key  :
             ValueError()
         key  ._order:
               
        ._order[key] = 
         (._order) > .capacity:
            ._order.popitem(last=)  
         

Step 4 — Implement S3FIFO

S3FIFO (Yang et al., SOSP 2023) matches or beats LRU on typical web and LLM workloads while spending a fraction of the per-access bookkeeping. The insight is that most cached objects are "one-hit wonders" accessed exactly once, and you should not pay LRU's per-hit pointer surgery to discover that. Three FIFO queues separate the proven-useful keys from the noise:

• Small queue (S, ~10% of capacity) — probation area. Every brand-new key lands here. One-hit wonders age out of S quickly without ever polluting the main cache.
• Main queue (M, ~90% of capacity) — holds keys that proved their worth. Uses second-chance eviction: a key with leftover frequency credit is reinserted at the head with its counter decremented instead of being evicted, giving warm keys repeated reprieves.
• Ghost queue (G, metadata only) — remembers fingerprints of recently evicted keys. If such a key returns, that is strong evidence it belongs in the main cache, so it is admitted straight to M rather than starting over in S.

Two design points are load-bearing:

1. The frequency counter saturates at a small cap (FREQ_MAX = 3) so the main-queue second-chance loop does a bounded amount of work per eviction. An unbounded counter would let one very hot key spin that loop indefinitely.
2. Ghosts are not residents: they hold no value, count against neither queue's capacity, and a ghost hit on insertion is not a cache hit for token accounting.

from collections import OrderedDict
from collections.abc import Hashable


class S3FIFO:
    """S3-FIFO eviction (Yang et al., SOSP 2023): a small admission queue, a main
    queue with second-chance eviction, and a metadata-only ghost queue.

    The frequency counter saturates at FREQ_MAX so the main-queue second-chance
    loop performs a bounded amount of work per eviction.
    """

    FREQ_MAX: int = 3

    def __init__(self, capacity: int) -> None:
        if not isinstance(capacity, int) or isinstance(capacity, bool):
            raise TypeError(f"capacity must be an int, got {type(capacity).__name__}")
        if capacity <= 0:
            raise ValueError(f"capacity must be positive, got {capacity}")
        self.capacity: int = capacity
        self._small_capacity: int = max(1, capacity // 10)
        self._main_capacity: int = max(1, capacity - self._small_capacity)
        self._ghost_capacity: int = self._main_capacity

        ._small:  = OrderedDict()
        ._main:  = OrderedDict()
        ._ghost:  = OrderedDict()
        ._freq: [Hashable, ] = {}

     () -> :
        
         key  ._small  key  ._main

     () -> :
         (._small) + (._main)

     () -> :
        
         key  :
             ValueError()
         key  ._small  key  ._main:  
            ._freq[key] = (._freq.get(key, ) + , .FREQ_MAX)
             
        ._insert(key)  
         

     () -> :
         .resident_count() >= .capacity:
            ._evict()
         key  ._ghost:
             ._ghost[key]
            ._main[key] =   
            ._freq[key] = 
        :
            ._small[key] =   
            ._freq[key] = 

     () -> :
        
         (._small) >= ._small_capacity:
            ._evict_small()
        :
            ._evict_main()

     () -> :
        
        
         ._small:
            key, _ = ._small.popitem(last=)  
             ._freq.get(key, ) > :
                ._main[key] =   
            :
                 ._freq[key]
                ._to_ghost(key)
                

     () -> :
        
        
         ._main:
            key, _ = ._main.popitem(last=)  
            freq = ._freq.get(key, )
             freq > :
                ._freq[key] = freq - 
                ._main[key] =   
            :
                 ._freq[key]
                ._to_ghost(key)
                

     () -> :
        ._ghost[key] = 
         (._ghost) > ._ghost_capacity:
            ._ghost.popitem(last=)  

Step 5 — Build the replay-and-compare harness

The harness treats each policy class as a factory (LRU, LFU, FIFO, S3FIFO are all Callable[[int], EvictionPolicy]), rebuilds a clean cache per run so the comparison is fair, and validates the trace at the boundary so a malformed input fails loudly instead of producing a quietly wrong hit rate.

Two correctness details are baked in deliberately:

• Residency is read with contains() before access() mutates the cache — reversing that order makes every block hit against itself.
• The resident count comes from the uniform resident_count() method each policy exposes, never from a guess that capacity was fully used (S3FIFO routinely ends below capacity because ghosts absorb admission pressure).

from __future__ import annotations

from collections.abc import Callable, Hashable, Sequence
from dataclasses import dataclass, field
from typing import Protocol, runtime_checkable


@runtime_checkable
class EvictionPolicy(Protocol):
    """Structural type implemented by LRU, LFU, FIFO, and S3FIFO above."""

    def contains(self, key: Hashable) -> bool:
        """Return True if `key` is currently resident (ghost entries excluded)."""

    def access(self, key: Hashable) -> bool:
        """Record an access to `key`; return True on a hit, False on a miss."""

    def resident_count(self) -> int:
        """Return the number of resident keys (ghost entries excluded)."""


@dataclass(frozen=True)
class Block:
    """One cache unit referenced by a request, carrying its token weight."""

    key: Hashable
    tokens: int

    def __post_init__(self) -> None:
        if self.key is None:
            raise ValueError()
          (.tokens, )  (.tokens, ):
             TypeError(
                
            )
         .tokens < :
             ValueError()


Request = [Block]
Trace = [Request]



 :
    hit_tokens:  = 
    prompt_tokens:  = 
    per_request_hit_tokens: [] = field(default_factory=)
    resident_count:  = 


     () -> :
         .prompt_tokens == :
             
         .hit_tokens / .prompt_tokens


 () -> ReplayResult:
    
      (policy_factory):
         TypeError()
      (capacity, )  (capacity, ):
         TypeError()
     capacity <= :
         ValueError()

    policy: EvictionPolicy = policy_factory(capacity)
    result = ReplayResult()

     request  trace:
        request_hit_tokens = 
         block  request:
              (block, Block):
                 TypeError(
                    
                )
            
            is_hit = policy.contains(block.key)
            policy.access(block.key)
            result.prompt_tokens += block.tokens
             is_hit:
                request_hit_tokens += block.tokens
        result.hit_tokens += request_hit_tokens
        result.per_request_hit_tokens.append(request_hit_tokens)

    result.resident_count = policy.resident_count()
     result


 () -> [, ReplayResult]:
    
    factories: [, [[], EvictionPolicy]] = {
        : LRU,
        : LFU,
        : FIFO,
        : S3FIFO,
    }
     {name: replay(factory, capacity, trace)  name, factory  factories.items()}

Step 6 — Run the demo

Save all classes and the harness in a single module (e.g. cache_policies.py), then add the demo entry point and run it:

if __name__ == "__main__":
    shared_prefix: list[Block] = [Block("sys", 8), Block("ctx", 16)]
    demo_trace: Trace = [
        [*shared_prefix, Block("q1", 4)],
        [*shared_prefix, Block("q2", 4)],
        [Block("sys", 8), Block("other", 32), Block("q3", 4)],
    ]
    for name, outcome in compare_policies(capacity=4, trace=demo_trace).items():
        print(
            f"{name:7s} hit_rate={outcome.hit_rate:6.2%} "
            f"hit_tokens={outcome.hit_tokens:4d} resident={outcome.resident_count}"
        )

python cache_policies.py

Expected output (approximate — exact numbers depend on eviction order):

LRU     hit_rate= 28.57% hit_tokens=  16 resident=4
LFU     hit_rate= 28.57% hit_tokens=  16 resident=4
FIFO    hit_rate= 28.57% hit_tokens=  16 resident=4
S3FIFO  hit_rate= 28.57% hit_tokens=  16 resident=3

Step 7 — Interpret workload implications

• Strong recency → LRU wins slightly.
• Stable hot set with long tail (Zipf) → LFU or S3FIFO.
• Nearly uniform random → all converge toward capacity / working_set hit rate.
• Prefix-shared LLM workloads are mixed — shared prefixes are both recent and frequent, so LRU/LFU/S3FIFO typically sit within a few percent of each other at the same capacity, but they differ in which blocks remain resident at end-of-trace, and their miss-handling costs diverge. Measure, don't assume.

Step 8 — Compare beyond hit rate

Replay the same trace through each policy at identical capacity, record total_hit_tokens / total_prompt_tokens and the final resident set. Do not compare hit rate alone — also compare:

• Final residency — how many unique blocks are resident at the end. Under S3FIFO this is often strictly less than capacity because ghost entries absorb the admission pressure.
• Per-request hit-token distribution — two policies can have similar overall hit rate but very different per-request variance.
• Admission effort — under policies with ghost structures, the bookkeeping cost per access is non-trivial.

Examples

Extending to ARC (Adaptive Replacement Cache)

ARC maintains two ghost lists (one for recently evicted from the recency-sensitive side, one for the frequency-sensitive side) and dynamically adjusts the split point between the two resident queues based on which ghost list is producing hits. To add ARC to the harness:

1. Implement an ARC class that satisfies the EvictionPolicy protocol (contains, access, resident_count).
2. Add "ARC": ARC to the factories dict in compare_policies.
3. Confirm that resident_count() returns only the sum of the two resident queues, excluding both ghost lists.
4. Drive ARC's adaptive p from which ghost list is hitting (recency-evicted vs frequency-evicted), keeping resident_count() as the two resident queues only.

Pitfalls

These are the mistakes that quietly corrupt a comparison. Each is listed with the underlying reason so you can recognize the same failure mode in a variation the list does not name.

• Treating FIFO as "LRU without the hit update" in your accounting. The implementations overlap, but the concepts diverge where it matters: a hit on a FIFO cache is still a hit for token accounting — the block simply keeps its existing rank instead of being promoted. If you let "no rank change" leak into "not a hit," your hit-rate numbers silently drop and the comparison becomes meaningless.
• Reusing an LRU implementation when the task specifies S3FIFO, or vice versa. These policies make different eviction decisions, so both the final hit rate and the resident set will differ. A comparison exists precisely to surface those differences, so "close enough" defeats the purpose — you would be measuring two copies of the same policy.
• Counting ghost entries as resident, or scoring a ghost hit as a real hit. Ghosts are metadata-only: they remember that a key was recently evicted so the policy can react if it returns, but they hold no value and consume no capacity. Conflating them with resident entries inflates both your residency count and your hit rate, which double-distorts the comparison.
• Letting the frequency counter grow without bound. S3FIFO's main-queue eviction repeatedly decrements freq and re-inserts entries that still have credit. If freq is unbounded, a single very hot key can accumulate a huge count and turn that second-chance loop into a near-infinite spin. Saturating the counter (a small cap such as 3) bounds the work per eviction to a constant.
• Picking the LFU victim with min(d.items(), key=d.get) and no explicit tiebreaker. When several keys share the minimum frequency, min returns whichever the iteration order happens to surface first, and that order is not guaranteed stable across interpreters or versions. An explicit insertion-order tiebreaker makes the eviction deterministic and your results reproducible.
• Checking residency after applying the current request's admission side effects. The hit/miss decision must be read against the cache state as it was before this request mutated it. If you insert the key first and then test membership, every request reports a hit against itself, and the trace looks like a 100% hit rate that is pure artifact.
• Computing final cache size without excluding ghosts or accounting for the small/main capacity split. S3FIFO's capacity is partitioned between the small and main queues, and ghosts sit outside both. A size calculation that ignores either fact will not match the policy's actual residency, so report the resident set as (small ∪ main), never including ghost.
• Reaching for deprecated APIs or unmaintained libraries. The implementations here target CPython 3.12 (current as of 2026) and lean only on the standard library, which keeps the comparison portable and avoids behavior that shifts under you between releases.

Verification

Each check below targets a specific failure mode from the pitfalls list — the point is not to tick boxes but to catch the mistakes that make a comparison silently wrong before you trust its numbers.

1. Cross-policy divergence: Replay one identical trace through all four policies at several capacities; confirm the hit rates differ where the policies should differ. A flat tie across very different policies usually means a shared bug in the harness.

   python -c "from cache_policies import compare_policies, Block; t=[[Block('a',1),Block('b',1)],[Block('a',1),Block('c',1)],[Block('b',1),Block('a',1)]]; [print(k, v.hit_rate, v.resident_count) for k,v in compare_policies(2, t).items()]"
   

2. LRU recency refresh: On a recency-heavy workload, confirm LRU clearly beats FIFO — equal hit rates mean the move_to_end recency refresh was dropped and LRU has degenerated to FIFO.

3. LFU tiebreaker determinism: Confirm the LFU victim is chosen by the (freq, insertion_seq) pair so repeated runs of the same trace evict the same key; a result that wobbles between runs means the tiebreaker is missing.

4. FIFO hit-without-reorder: Confirm FIFO returns True on a repeat access but does not reorder its queue (hit accounting still counts, eviction order does not change).

5. S3FIFO counter saturation: Confirm S3FIFO caps freq at FREQ_MAX and that the main-queue second-chance loop terminates in bounded time even under a hot-key-only trace.

6. Ghost exclusion: Confirm contains() and resident_count() exclude the ghost queue, and that a ghost match on insertion is not counted as a hit.

7. Resident set correctness: Confirm the reported resident set is small ∪ main (never including ghost) and that it can legitimately end below capacity under S3FIFO.

8. Per-request variance: Inspect per_request_hit_tokens variance across policies — two policies with the same overall hit rate can have very different per-request behavior.

9. Type safety: Run mypy --strict (or pyright) over the module and confirm it passes with no Any leaking through and no missing annotations.

   python -m mypy --strict cache_policies.py
   

10. Boundary validation: Confirm the boundary validations fire: a non-positive capacity, a key, a non- trace entry, and a negative token count each raise immediately rather than producing a wrong number.

Related Skills

• prefix-cache-replay — Applies these policies to LLM prefix-cache traces, where keys are prompt-prefix blocks and the payoff is reused KV-cache tokens. This skill is self-contained (the full S3FIFO implementation lives in the S3FIFO section above); reach for prefix-cache-replay when you need trace ingestion, block hashing, and token accounting wired specifically for prefix sharing.