Local Caching Policies and Mechanisms: An Algorithmic Guide

Aug 25, 2026 · by 0xKiirecachingsystem-designalgorithms

This guide describes the algorithms behind local (in-process / single-node) caching systems in enough detail that each can be implemented from the description alone. It covers three orthogonal concerns that every cache design must answer:

Write policy — how writes propagate between cache and backing store.
Replacement (eviction) policy — which entry to discard when the cache is full.
Admission policy — whether a new entry should even enter the cache.

Expiration/invalidation and concurrency mechanisms are covered separately at the end.

1. Foundations

Terminology

Hit: requested key is present in cache.
Miss: requested key is absent; must be fetched from backing store (and possibly inserted).
Working set: the set of keys accessed within a recent window of time/requests.
Capacity: maximum number of entries (or maximum total byte size, for size-aware caches).
Recency: how long ago an item was last accessed.
Frequency: how many times an item has been accessed (often within a decayed window).

Core data structures reused throughout this guide

Hash map: key → pointer/index into a node holding value + metadata. Gives O(1) average lookup.
Doubly linked list: gives O(1) removal/insertion at arbitrary positions when you hold a node pointer, which is what makes O(1) LRU possible when paired with a hash map.
Circular buffer / ring: used for CLOCK-family algorithms.
Priority structure (heap, or frequency-bucketed linked lists): used for LFU-family algorithms where you must repeatedly find the minimum-priority item.

A cache implementation, regardless of policy, generally needs:

A capacity bound check on every insert.
A lookup path (on hit, update metadata; return value).
An insert path (on miss, fetch, evaluate admission, evict if necessary, insert, update metadata).
An eviction path (select victim according to policy, remove from both hash map and ordering structure).

2. Write Policies

These govern how updates to cached data reach the backing store (disk, remote DB, etc.). They are orthogonal to eviction policy — any write policy can be paired with any replacement policy.

2.1 Write-Through

Every write is applied to the cache and synchronously to the backing store before the write is acknowledged as complete.

Algorithm

Receive write(key, value).
Write value to backing store; wait for confirmation.
Update (or insert) the entry in the cache with the new value.
Update recency/frequency metadata as if this were an access, per the active replacement policy.
Acknowledge the write.

Properties: cache and store are never inconsistent after a completed write. Write latency equals store latency (no benefit from caching on writes). Good when reads vastly outnumber writes and consistency matters.

2.2 Write-Back (Write-Behind)

Writes go to the cache only; propagation to the backing store is deferred.

Algorithm

Receive write(key, value).
Update the entry in cache; mark it dirty (a single bit/flag per entry).
Acknowledge the write immediately.
Asynchronously, on a timer or a background thread, scan for dirty entries and flush them to the backing store, then clear the dirty flag.
On eviction of a dirty entry: flush it to the backing store before removing it from the cache (never evict dirty data without flushing first — this is the critical correctness rule).

Properties: much lower write latency; risk of data loss on crash before flush; requires careful ordering — eviction must trigger a synchronous flush-then-remove for dirty entries specifically.

2.3 Write-Around

Writes go directly to the backing store, bypassing the cache entirely. The cache is only populated on subsequent reads (cache-miss path).

Algorithm

Receive write(key, value).
Write value directly to backing store.
If key currently exists in cache, either (a) invalidate/remove it, or (b) update it in place — removal is safer and simpler, avoiding a second write path into the cache's metadata structures.
Acknowledge the write.

Properties: avoids polluting the cache with data that may not be re-read soon (e.g., bulk write workloads). First read after a write is always a miss.

2.4 Write-Allocate vs. No-Write-Allocate

A sub-decision for write misses (writing a key not currently cached):

Write-allocate: on a write miss, load the entry into the cache (possibly after reading current value from store, or just inserting the new value), then apply the write policy above.
No-write-allocate: on a write miss, write directly to the backing store and do not insert into the cache.

Write-allocate is typically paired with write-back (so subsequent writes are absorbed by the cache). No-write-allocate is typically paired with write-through.

3. Replacement (Eviction) Algorithms

This is the core of most caching systems: when the cache is full and a new item must be inserted, which existing item is evicted? Below, algorithms are ordered from simplest to most sophisticated.

3.1 FIFO (First-In, First-Out)

Evicts the entry that has been resident the longest, ignoring how often or recently it was accessed after insertion.

Data structures: a plain queue (doubly linked list is fine) ordered by insertion time, plus a hash map from key to queue node.

Algorithm

Insert: append new entry to the tail of the queue; store key→node in the hash map.
Access (hit): no reordering — position in the queue is untouched.
Evict: remove the node at the head of the queue (oldest insertion); erase its key from the hash map.

Weakness: susceptible to evicting hot items purely because they were inserted early ("first-in, first-out" ignores reuse).

3.2 LRU (Least Recently Used) — exact form

Evicts the entry that has gone the longest without being accessed.

Data structures: doubly linked list ordered by recency (head = most recently used, tail = least recently used), plus a hash map from key to the corresponding list node.

Algorithm

Access (hit): unlink the node from its current position; relink it at the head. O(1) because it's a doubly linked list and you hold the node pointer directly from the hash map lookup.
Insert (miss): if at capacity, evict (see below) first. Create a new node, insert at the head, store key→node in the hash map.
Evict: remove the node at the tail (least recently used); erase its key from the hash map.

Complexity: O(1) per operation. This is the canonical "hash map + doubly linked list" LRU and is the baseline against which most other policies are compared.

Weakness: pure recency is vulnerable to scans — a one-time sequential pass over many keys (e.g., a backup job) evicts the entire working set even though those scanned keys will never be touched again, while genuinely hot items get pushed out.

3.3 Clock / Second-Chance (LRU approximation)

Approximates LRU without the cost of relinking on every access, using a single reference bit per entry.

Data structures: a circular buffer (array or circular linked list) of entries, each with a reference bit; a single "hand" pointer into the circle; a hash map from key to buffer slot.

Algorithm

Access (hit): set the entry's reference bit to 1. Do not move the hand or reorder anything.
Insert (miss) / evict: advance the hand one slot at a time.
- If the entry under the hand has reference bit 0, evict it, place the new entry in that slot, set its reference bit to 0 (or 1, depending on variant — 0 means "not yet had a second chance"), advance the hand past it, and stop.
- If the entry under the hand has reference bit 1, clear it to 0 ("give it a second chance") and advance the hand to the next slot, repeating the check.
This guarantees termination because every full sweep clears all bits it passes, so within at most two sweeps a 0-bit entry is found.

Properties: O(1) amortized; much lower per-access overhead than exact LRU (a single bit-set, no pointer relinking); reasonably close to LRU behavior in practice. Used in many OS page-replacement implementations.

GCLOCK extension: replace the single reference bit with a small saturating counter (e.g., 0–3). On access, increment the counter (saturating at max). On sweep, decrement counters instead of zeroing them, and only evict when a counter reaches 0. This approximates LFU-like weighting on top of Clock's cheap operation.

3.4 MRU (Most Recently Used)

Evicts the most recently used item instead of the least. Uses the same data structure as LRU (head/tail list), but eviction removes from the head instead of the tail.

When applicable: workloads with cyclic scans larger than cache capacity, where the item just used is the least likely to be reused soon (looping access patterns), so keeping older items is better.

3.5 LFU (Least Frequently Used) — with O(1) implementation

Evicts the entry with the smallest access count. A naive implementation (linear scan for the minimum, or a heap) works but is not O(1). The O(1) construction below avoids both:

Data structures:

A hash map from key to a node containing: the value, its current frequency count, and a pointer to the "frequency bucket" it currently belongs to.
A doubly linked list of frequency buckets, ordered by increasing frequency value. Each bucket holds: an integer frequency count, and a doubly linked list of all entries currently at that frequency.
A pointer to the bucket with the minimum frequency (the head of the bucket list).

Algorithm

Access (hit): let f be the entry's current frequency and bucket(f) its current bucket.
1. Remove the entry from bucket(f)'s entry-list.
2. If bucket(f) is now empty, unlink and free it; if it was the minimum-frequency bucket, advance the minimum pointer to the next bucket (which now holds frequency f+1 items, if any existed, or must be created — see below).
3. If a bucket for frequency f+1 does not exist immediately after bucket(f)'s former position, create one and link it in.
4. Insert the entry into bucket(f+1)'s entry-list (e.g., at the head, so ties are broken by recency — this hybrid is sometimes called LFU-LRU tie-break).
5. Increment the entry's stored frequency to f+1.
Insert (miss): if at capacity, evict first. Create the entry with frequency 1. If a bucket for frequency 1 does not exist, create it and set it as the new minimum bucket (frequency-1 buckets are always the minimum for freshly inserted items). Insert the entry there.
Evict: take any entry from the minimum-frequency bucket's entry-list (commonly the tail, i.e. the least recently used among equally infrequent items — this is the tie-break). Remove it from the bucket and from the hash map. If the bucket becomes empty, unlink it and advance the minimum pointer.

Complexity: O(1) per operation, because bucket transitions only ever move an entry to the immediately adjacent frequency bucket, and bucket creation/deletion is O(1) list-splicing.

Weakness: frequency counts persist forever by default, so an item that was extremely popular long ago but is now cold can "outrank" newly popular items indefinitely (cache pollution by stale popularity). This motivates aging/decay mechanisms (Section 3.11) or windowed variants.

3.6 Random Replacement

Evicts a uniformly random entry.

Data structures: an array (or array-backed hash map) so any entry can be selected by random index in O(1).

Algorithm

Evict: generate a random index in [0, current size), remove the entry at that index (swap with the last element and pop, to keep removal O(1) if using an array), erase from the hash map.

Properties: no metadata to maintain on access (cheapest possible per-access cost), surprisingly competitive average-case performance under certain workloads, and immune to scan-pollution in the way strict LRU is not. Used in some CPU cache designs and simple embedded caches.

3.7 Segmented LRU (SLRU)

Splits the cache into two LRU-ordered segments: a smaller probationary segment and a larger protected segment. This filters out one-time-use items before they can pollute the "truly hot" segment.

Data structures: two independent LRU lists (each as in 3.2), with a combined capacity budget split between them (commonly ~20% probationary / 80% protected, tunable).

Algorithm

Insert (miss): new entries always enter at the head of the probationary segment. If the probationary segment exceeds its budget, evict from its tail (this is a true eviction from the cache).
Access (hit) in probationary segment: remove the entry from probationary and insert it at the head of the protected segment (it has now proven reuse). If protected exceeds its budget, evict the entry at its tail — but rather than discarding it outright, demote it back to the head of probationary (this may itself force a probationary eviction if that segment now overflows).
Access (hit) in protected segment: move to the head of protected (standard LRU touch).

Properties: items must be reused at least once before entering the protected segment, so scan workloads only ever pollute the small probationary segment, not the protected one.

3.8 2Q

Similar goal to SLRU (filter scans) but uses queue membership rather than promotion between two full LRUs, and adds a ghost list to remember recently evicted keys.

Data structures: three structures, sized as fractions of total capacity:

A1in: a FIFO queue (not LRU — pure insertion order) for newly seen items, typically ~25% of capacity.
A1out: a ghost list — FIFO queue of keys only (no values) for items recently evicted from A1in, typically sized proportionally (e.g., 50% of capacity worth of keys).
Am: an LRU list for items that have proven reuse, typically the remaining ~75% of capacity for actual cached values.

Algorithm

Access, key found in Am: standard LRU touch (move to head of Am).
Access, key found in A1in: it's a hit but the item is not promoted — it stays in A1in at its current position (2Q deliberately does not reorder A1in, keeping it FIFO, to keep it cheap and scan-resistant).
Access, key found in A1out (ghost hit): this key was evicted before but is being requested again soon — evidence of real reuse. Remove it from A1out, fetch/insert its value directly into Am at the head (skipping A1in entirely). If Am is over budget, evict from its tail (standard LRU eviction, item is fully discarded, not ghosted).
Miss (key in none of the three): insert the new entry at the head of A1in. If A1in exceeds its budget, evict from its tail — but instead of discarding, move its key only into A1out (drop the value/payload). If A1out exceeds its budget, evict (fully discard) from its tail.

Properties: a single scan through many never-to-be-reused keys only ever churns through A1in (cheap FIFO operations, no Am pollution) and, if long enough, churns A1out's ghost keys. Am remains protected because entry requires a second observed access, exactly like SLRU's promotion rule, but implemented via ghost tracking instead of a second real cache.

3.9 ARC (Adaptive Replacement Cache)

Dynamically balances between recency-favoring and frequency-favoring behavior without any fixed, hand-tuned segment ratio — it adapts the ratio online based on observed workload.

Data structures: four lists, each holding keys only except where noted:

T1: LRU list of items in cache, seen exactly once recently (recency-favoring, real data).
T2: LRU list of items in cache, seen two or more times recently (frequency-favoring, real data).
B1: ghost LRU list of keys recently evicted from T1 (keys only, no data).
B2: ghost LRU list of keys recently evicted from T2 (keys only, no data).

Total real cache capacity c is split adaptively between T1 and T2 via a target size parameter p for T1 (so T2's target is c − p). p starts at 0 and self-tunes. B1 and B2 are typically bounded so that |T1|+|B1| ≤ c and |T2|+|B2| ≤ c (ghost lists shrink as their paired real list grows, so total tracked keys stays bounded around 2c).

Algorithm — on each request for key x:

Case: x is in T1 or T2 (real cache hit). Move x to the head of T2 (a second access promotes/keeps it in the frequency-favoring list; even a T2 hit re-promotes to head of T2).
Case: x is in B1 (ghost hit — was evicted from the recency list, now seen again). This is evidence recency-favored eviction was too aggressive: increase p by max(1, |B2| / |B1|) (adapt toward favoring recency more), then run the replacement procedure (below) using the updated p, then move x from B1 into the cache at the head of T2 (it has now been seen twice — once before eviction, once now).
Case: x is in B2 (ghost hit on the frequency list side). Evidence frequency-favored eviction was too aggressive: decrease p by max(1, |B1| / |B2|) (adapt toward favoring frequency more, i.e. shrink T1's target), run replacement using the updated p, then move x from B2 into the cache at the head of T2.
Case: x is in none of the four lists (true miss). If |T1| + |B1| = c (recency side is full including ghosts): if |T1| < c, evict the LRU key of B1 and run replacement; else evict the LRU entry of T1 itself (real eviction) and drop it (no ghost, since B1 already full to its own bound). Else if total tracked keys |T1|+|B1|+|T2|+|B2| ≥ c (combined structure full), trim the oldest ghost entry from whichever ghost list is largest if the four-list total reaches 2c, then run replacement. Finally, insert x at the head of T1 (new items always start in the recency-favoring list, on first sight).

Replacement procedure (selects and evicts one real entry from T1 or T2, moving its key to the matching ghost list):

If T1 is non-empty and (|T1| > p, or (x was found in B2 and |T1| = p)): evict the LRU entry from T1, move its key to the head of B1.
Otherwise: evict the LRU entry from T2, move its key to the head of B2.

Properties: because p shifts based on which ghost list registers hits, ARC self-tunes between LRU-like and LFU-like behavior per-workload with no manual parameters, and is provably at least as good as the better of a fixed-ratio LRU/LFU split in the worst case. This is the algorithm used in ZFS's ARC and ported into several database buffer managers.

3.10 CAR (Clock with Adaptive Replacement)

Same adaptive p-based logic as ARC, but replaces each of T1/T2's doubly linked LRU lists with Clock-style circular buffers plus reference bits, avoiding the pointer-relinking cost of ARC's LRU lists on every hit (an access just sets a reference bit, as in Section 3.3).

Algorithm (differences from ARC only):

T1 and T2 become circular buffers, each with a hand and per-entry reference bits, instead of linked lists ordered strictly by recency.
Access (hit): instead of moving x to the head of T2, simply set x's reference bit to 1 in whichever of T1/T2 it resides (no relinking).
Replacement: instead of evicting the LRU tail of T1/T2, sweep the relevant hand: if the entry under the hand has reference bit 0, evict it (proceed as in ARC's replacement — move key to B1 or B2); if reference bit 1, clear it to 0 and advance the hand (Clock's second-chance rule), continue sweeping until a 0-bit entry is found.
B1/B2 remain simple FIFO ghost lists of keys (no reference bits needed, since they hold no data).
The p adaptation rules on B1/B2 hits are identical to ARC.

Properties: same adaptive quality as ARC with lower constant-factor overhead per access, at the cost of slightly coarser recency ordering (Clock only approximates true recency order).

3.11 LFU with Aging / Window-LFU

Addresses LFU's "stale popularity never decays" weakness (Section 3.5) by periodically decaying all frequency counts.

Algorithm (added on top of the O(1) LFU structure in 3.5)

Maintain a global counter of total accesses since the last decay, or a wall-clock timer.
On a fixed schedule (every N accesses, or every T seconds): iterate all frequency buckets and either (a) halve every entry's stored frequency (integer divide by 2, floor at 1), or (b) shift every entry down by a fixed decrement, floored at 1. Re-bucket entries whose frequency changed (multiple buckets may need merging if they now collide on the same decayed value).
Simpler alternative avoiding a full sweep: store frequency as a real-valued exponentially decayed counter. On each access at time t to an entry last touched at time t_prev with stored frequency f, update f ← f · decay^(t − t_prev) + 1 before re-bucketing (decay is a constant slightly below 1, e.g. 0.98 per second). This spreads the decay cost across accesses instead of a periodic sweep, at the cost of needing floating-point (or fixed-point) bucket keys rather than integers.

3.12 LRU-K

Generalizes LRU by keying eviction on the time of the K-th most recent access rather than just the single most recent one, so an item accessed only once recently (even if that access was very recent) is distinguished from one accessed K times.

Data structures: hash map from key to a small fixed-size ring buffer (or bounded queue) of the last K access timestamps for that entry, plus a priority structure (min-heap, keyed by the K-th most recent timestamp) over all cached entries. Entries with fewer than K recorded accesses are given a "backward K-distance" of infinity (or a separate lower-priority bucket), so they are preferentially evicted before any entry that has reached K accesses.

Algorithm

Access (hit or after insert): push the current timestamp into that entry's ring buffer of last-K timestamps (evicting the oldest recorded timestamp if the buffer was already full). Recompute the entry's key in the priority structure as its K-th most recent timestamp (i.e. the oldest timestamp currently in its ring buffer, once it has K entries).
Evict: pop the entry with the smallest K-th-most-recent timestamp from the priority structure (i.e., the entry whose K-th access, counting backward, is furthest in the past — or which has never reached K accesses at all, per the infinity rule above).

Complexity: O(log n) per operation due to the priority structure (heap), higher than plain LRU's O(1), in exchange for much better resistance to one-off accesses masquerading as "recent" under plain LRU. K=2 (LRU-2) is the most common practical choice, balancing overhead against benefit.

3.13 LIRS (Low Inter-Reference Recency Set)

Classifies items by inter-reference recency (IRR) — the number of distinct other items accessed between two consecutive accesses to the same item — rather than raw recency or frequency, giving strong resistance to both scans and to LFU's stale-popularity problem, without needing an adaptive parameter like ARC.

Data structures:

Every observed item (even ones no longer holding cached data) is classified as either LIR (Low IRR — considered "hot"/likely to be reused soon) or HIR (High IRR — considered "cold"). The count of LIR items is capped at a fixed fraction of capacity (e.g., 99%), with the remainder of capacity reserved for a small pool of resident HIR items.
An LRU stack S: contains, in recency order, every LIR item and every HIR item that has been accessed at least twice (this stack is allowed to contain entries beyond the actual cache capacity, since it also tracks history for classification, not just resident data — this is its key difference from a normal LRU list).
An LRU queue Q: contains only the currently resident HIR items (bounded to the small HIR capacity fraction), in recency order — this is the actual eviction candidate pool.
Each item stores its current classification (LIR/HIR) and whether it's currently resident in cache.

Algorithm — on access to item x:

If x is not in stack S and not resident (a true miss on a never/long-ago-seen item): classify it as HIR. If the resident-HIR pool (governed by Q) is at its capacity, evict the HIR item at the front of Q (its data is discarded; it may remain a non-resident record in S if it was already there, or simply be forgotten). Insert x's data into the cache, push x onto the top of S, and push x onto the back of Q (it is resident HIR).
If x is resident and classified HIR, and x is found in S (meaning it has now been accessed at least twice while still being tracked — a short inter-reference distance, i.e. low IRR): promote x to LIR. Remove x from Q (it's no longer part of the HIR resident pool). Push x onto the top of S. Because LIR count is now one over its cap, demote the bottom-most LIR item in S to HIR: remove it from consideration as LIR, mark it HIR, and push it onto the back of Q (it remains resident, now as an HIR item) — this may itself trigger an eviction from Q per step 1's capacity rule if Q overflows.
If x is resident and classified HIR, but not found in S at all (its previous stack entry had already been pruned — long inter-reference distance, i.e. still "cold"): it stays HIR. Push x onto the top of S and move it to the back of Q (standard recency refresh within the HIR pool).
If x is resident and classified LIR (found, by definition, in S): move x to the top of S (standard recency refresh). No reclassification needed.
Stack pruning: after any push to the top of S, if the item at the bottom of S is HIR (not LIR), pop it off repeatedly until the bottom of S is an LIR item. (LIR items at the bottom define the recency boundary; trailing HIR history below the lowest LIR item is no longer useful for classification and is discarded to bound S's size.)

Properties: because promotion to LIR requires a second access while the stack still remembers the first (i.e., a short inter-reference distance), a long one-time scan never promotes anything — scanned items get pruned from S before they could ever be seen twice — while genuinely hot items that alternate closely with other hot items get promoted and protected. Considered to outperform LRU, 2Q, and even ARC on several scan-heavy and loop-heavy benchmark traces.

3.14 GreedyDual-Size / GDSF (cost- and size-aware)

For caches where entries have heterogeneous fetch cost (e.g., network latency to repopulate) and heterogeneous size (e.g., variable-length HTTP response bodies), not just uniform-cost/uniform-size entries. Chooses the eviction victim by minimizing cost-effectiveness rather than pure recency.

Data structures: a min-priority-heap (or an ordered structure) over all entries, keyed by a per-entry value H. A single running inflation clock value L, initialized to 0.

Algorithm

Each entry stores its cost c (cost to refetch/recompute) and size s (its storage cost in the cache).
Insert (miss): compute the entry's priority H = L + (c / s) (cost-per-unit-size, offset by the current inflation clock). Insert into the priority heap with key H.
Access (hit): recompute H = L + (c / s) for that entry (using the current L) and update its position in the heap accordingly (this re-rewards it as if freshly inserted, capturing recency).
Evict: pop the entry with the minimum H from the heap. Before discarding it, set the inflation clock L ← H_evicted (the priority value of the entry just evicted). This is the mechanism that gives the algorithm its aging/recency property: every future insertion's priority is offset by the accumulated L, so an old low-cost entry inserted long ago cannot remain artificially cheap to evict forever relative to items inserted after many evictions have occurred — conversely, it also means every remaining entry's effective competitiveness rises over time relative to fresh insertions, capturing a recency signal alongside the cost/size signal.
For the uniform-cost, uniform-size special case (c = s = 1 for every entry), this algorithm's ordering reduces exactly to plain LRU eviction order, because H then just becomes L + 1, and the entry with smallest recency (least recently touched) ends up with smallest H. Increasing c or decreasing s for an entry makes it comparatively more expensive to re-fetch relative to its footprint, so GDSF keeps it longer than plain LRU would.

Properties: this is the algorithm behind Squid's web cache replacement policy; effective when cache entries genuinely differ in fetch cost/size (e.g., a small, cheap-to-refetch item vs. a large, expensive-to-recompute item), which pure LRU/LFU ignore entirely.

3.15 TinyLFU (admission filter, typically paired with an eviction policy)

Unlike the previous sections (which are all eviction policies), TinyLFU is primarily an admission policy: it decides, at insert time, whether a new candidate is even worth admitting into the cache, by comparing its estimated historical frequency against the frequency of the item that would need to be evicted to make room. It is almost always paired with a small LRU-based eviction mechanism for the actual resident set (see W-TinyLFU below), rather than used standalone.

Data structures:

A Count-Min Sketch: a fixed-size 2D array of counters with dimensions d (number of hash functions/rows) × w (width per row). To increment a key's estimated count: hash the key with each of the d hash functions to get d column indices (one per row), and increment the counter at each of those d positions. To query a key's estimated count: hash the key the same d ways and return the minimum value among the d counters read (minimum, not sum or average, because it bounds the overestimation caused by hash collisions — this is the defining trick of a Count-Min Sketch).
A periodic halving mechanism: maintain a running total of increments performed. Once the total reaches a threshold (commonly set to 10× the intended cache capacity), halve every counter in the sketch (integer divide by 2) and reset the running total to (roughly) half its value. This bounds memory to fixed-size counters and provides the same "stale popularity decays" benefit as Section 3.11, applied to the frequency estimator rather than to per-entry state.

Algorithm

On every access (hit or miss) to key x: increment x's estimated count in the Count-Min Sketch, and increment the running total, triggering the periodic halving described above when the threshold is reached.
On a miss where the cache is at capacity and a candidate victim v has been chosen by the paired eviction policy (e.g., LRU's tail): before actually evicting v and admitting the new key x, compare their estimated frequencies from the sketch. Admit x (evict v) only if estimate(x) > estimate(v). If estimate(x) ≤ estimate(v), reject x — do not insert it, leave v in place, and simply serve/fetch this one request without caching it (it will need to be fetched again from the backing store on the next request too, unless it accumulates enough sketch hits to eventually win admission).

Properties: this prevents a burst of one-off, never-to-be-repeated keys (e.g. a crawler hitting many distinct URLs once each) from evicting genuinely hot resident items one-by-one, since each one-off candidate has an estimated frequency of essentially 1 and will almost always lose the comparison against an established resident item.

W-TinyLFU (Windowed TinyLFU): combines TinyLFU admission with a small separate "window" cache to avoid TinyLFU's own weakness — sudden bursts of new legitimately-hot keys that haven't yet accumulated enough sketch count to win admission against long-resident items.

Split total capacity into a small window segment (commonly ~1%) and a large main segment (commonly ~99%), the main segment itself organized as SLRU (Section 3.7).
Insert (any miss): always admit the new key into the window segment first (plain LRU eviction within the tiny window — cheap, since it's a small fixed budget).
When an item is evicted from the window segment (window is full and a new item is inserted), it becomes a candidate for promotion into the main segment: run the TinyLFU admission comparison (above) between this window-evictee and the main segment's current probationary-tail victim (Section 3.7's SLRU eviction candidate). Whichever of the two has the higher sketch estimate is admitted into the main segment's probationary head; the other is discarded entirely.
This gives new arrivals a brief, cheap grace period (the window) to accumulate access evidence before having to compete on frequency against established residents, fixing plain TinyLFU's cold-start/burst weakness while keeping its scan resistance. This is the design used by the Caffeine caching library.

3.16 Belady's Algorithm / OPT (theoretical optimum, offline only)

Not implementable online (it requires knowledge of the future), but included because it is the correctness baseline every other algorithm above is measured against, and is directly implementable for offline analysis (e.g., replaying a captured access trace to compute the best-possible hit rate).

Algorithm

Given a full trace of future accesses in advance: on eviction, evict the resident entry whose next future access is furthest away in the trace (or which is never accessed again at all, which counts as infinitely far away and is evicted first, before any entry that will be reused eventually).
Implementation: for each resident entry, scan forward through the remaining trace to find its next occurrence (or record it as "never again" if not found), and evict the entry with the maximum such distance. A naive implementation is O(n) per eviction from re-scanning; a practical offline implementation precomputes, for every position in the trace, the index of that key's next occurrence in a single backward pass over the trace before replay begins, turning each eviction decision into an O(log n) max-priority-heap operation instead.

Use: run this offline against a captured production access trace to compute the maximum possible hit rate for that trace, then compare each candidate online policy's hit rate against it to judge how much headroom remains.

4. Expiration and Invalidation

Independent of eviction-under-capacity-pressure, most caches also need time-based expiration and explicit invalidation.

4.1 TTL (Time-to-Live) — Lazy Expiration

Each entry stores an absolute expiry timestamp (insertion time + TTL duration) or is checked against a separately stored insertion time.

Algorithm

On lookup: before returning a hit, compare current time against the entry's expiry timestamp. If expired, treat this as a miss — remove the entry from all cache data structures as if it were being evicted (update whichever eviction policy's bookkeeping accordingly), then proceed with the normal miss path (fetch from backing store, re-insert if it passes admission).
No proactive scanning is performed; expired entries simply sit in the cache, silently occupying space, until either (a) they happen to be looked up again and get lazily purged as above, or (b) they are evicted anyway by the capacity-based replacement policy before ever being looked up again.

Properties: zero background CPU cost, but can waste memory on expired-but-never-requested-again entries indefinitely if not combined with active expiration.

4.2 Active (Eager) Expiration

A background process periodically scans for and removes expired entries regardless of whether they're looked up.

Algorithm

Maintain a min-heap keyed by expiry timestamp (separate from whatever structure the eviction policy uses for its own ordering), or bucket entries into a timing wheel (an array of buckets where bucket i holds entries expiring in time-slot i, with a rotating "current slot" pointer advanced by a periodic timer tick).
On a timer interval (min-heap approach): peek the minimum expiry timestamp; while it is ≤ current time, pop it and remove that entry from the cache entirely (from both the expiry heap and the eviction policy's structures); repeat until the minimum exceeds current time.
On each timer tick (timing-wheel approach): advance the current-slot pointer by one slot, and purge every entry found in the slot just passed. This trades exact-timestamp precision for O(1) tick cost instead of a heap's O(log n) per removal, at the cost of expiry granularity equal to the wheel's slot width.

4.3 Explicit Invalidation

Removal triggered by an external event (e.g., the backing store's data changed), independent of both capacity and TTL.

Algorithm

Point invalidation: given a specific key, if present, remove it from the hash map and from whatever eviction-policy structure it currently sits in (same removal logic as a normal eviction, just triggered externally rather than by the replacement algorithm).
Pattern/prefix invalidation: when keys share a queryable structure (e.g., a trie or sorted index keyed by prefix), locate all matching keys via that index and point-invalidate each. Without such an index, this degrades to a full O(n) scan of all resident keys.
Versioned/generation invalidation (fast bulk invalidation without touching every entry): maintain a single global generation counter, and store the generation number active at the time each entry was inserted alongside the entry. To invalidate everything at once ("flush"), simply increment the global generation counter — an O(1) operation. On lookup, compare the entry's stored generation against the current global generation; if they differ, treat it as a miss (and lazily remove it, as in TTL lazy expiration) even though the entry structurally still exists in memory until then.

5. Concurrency Mechanisms for Local (In-Process) Caches

Local caches are usually accessed by multiple threads within the same process, so the pure data structures above need a concurrency strategy layered on top.

5.1 Single Global Lock

Simplest approach: one mutex guards the entire cache (hash map + eviction-policy structures). Every operation (get/put/evict) acquires the lock for its full duration.

Tradeoff: correctness is trivial to reason about; throughput is bottlenecked to one operation at a time across all threads, which becomes the limiting factor under high concurrency.

5.2 Sharding (Striped Locking)

Split the cache into N independent shards, each a fully self-contained cache (its own hash map, its own eviction-policy structures, its own lock), where N is typically a power of two related to expected concurrency (e.g., 16, 32, or proportional to core count).

Algorithm

To route a key to a shard: compute shard_index = hash(key) mod N (or, if N is a power of two, hash(key) & (N − 1) to avoid a division).
All operations for a given key acquire only that key's shard's lock, not a global lock. Different keys in different shards can proceed fully in parallel.

Consequence for eviction policy: capacity must be split per-shard (e.g., total capacity / N per shard), and each shard runs its own independent instance of whichever eviction algorithm (Section 3) was chosen — there is no cross-shard coordination of "which item is globally least-recently-used." This is an accepted approximation in exchange for concurrency; skewed key distributions across shards can cause some shards to evict much more aggressively than others.

5.3 Read-Copy-Update / Lock-Free Reads (for read-heavy workloads)

For workloads dominated by lookups with comparatively rare writes/evictions, reads can avoid locking entirely using atomic pointer swaps, at the cost of more complex write-path logic.

Algorithm sketch

The hash map's bucket entries (or the whole map, for small caches) are referenced through an atomic pointer.
Reads: load the atomic pointer once (a single atomic read, no lock), then traverse the data structure it points to. Because the structure pointed to is treated as immutable once published, concurrent readers never observe a torn/partial update.
Writes: construct a new version of the affected structure (e.g., a new bucket chain, or a new copy-on-write node) reflecting the change, then atomically compare-and-swap the shared pointer from the old version to the new version. If the CAS fails (another writer raced ahead), retry by re-reading the current pointer and reconstructing the update against it.
Reclamation: the old version cannot be freed immediately after a successful CAS, because readers that loaded the old pointer before the swap may still be traversing it. Reclaim it only once it is certain no in-flight reader still holds a reference — typically via a grace-period mechanism (e.g., deferring frees until all reader threads have passed through a quiescent point, or using reference counting on the structure itself).
Note that recency/frequency metadata updates on read (e.g., LRU's move-to-head, or LFU's counter increment) are themselves writes from a concurrency standpoint. A common practical compromise is to make the hot lookup path fully lock-free/read-only, and batch the resulting "this key was accessed" events into a lock-protected or lock-free queue that a separate maintenance step drains periodically to update the eviction-policy's ordering structures — trading perfectly precise recency/frequency ordering for much lower per-lookup contention. (This is the general strategy used by Caffeine's BoundedLocalCache.)

6. Choosing Among Policies — Summary Comparison

Policy	Per-access cost	Scan-resistant	Adapts recency↔frequency	Extra memory beyond entries
FIFO	O(1)	No	No	none
LRU (exact)	O(1)	No	Recency only	2 pointers/entry
Clock	O(1) amortized	No	Recency only	1 bit/entry
LFU (bucketed)	O(1)	Partially (frequency floor)	Frequency only	bucket pointers
Random	O(1), no access-time cost	Yes	No	none
SLRU	O(1)	Yes (probationary filter)	No	2 pointers/entry ×2 lists
2Q	O(1)	Yes	No	ghost-key list
ARC	O(1)	Yes	Yes (self-tuning `p`)	2 ghost lists
CAR	O(1) amortized	Yes	Yes (self-tuning `p`)	2 ghost lists + ref bits
LRU-K	O(log n)	Yes (K≥2)	Partial (K-depth history)	K timestamps/entry + heap
LIRS	O(1) amortized	Yes (strong)	Yes (via IRR)	stack beyond capacity
GDSF	O(log n)	N/A (cost/size aware)	Recency + cost/size	heap
TinyLFU / W-TinyLFU	O(1)	Yes (admission-based)	Yes (frequency sketch + window)	fixed-size sketch

Rules of thumb:

Uniform, small entries, simple needs → LRU (Clock variant if per-access cost must be minimal).
Known scan/backup-style workloads mixed with genuine hot keys → SLRU, 2Q, or LIRS.
Workload character unknown or shifts over time → ARC/CAR (self-tuning) or W-TinyLFU (strong general-purpose default used by several production libraries).
Entries vary significantly in fetch cost or size (e.g., HTTP/object caches) → GDSF.
Need to evaluate "how good could any policy possibly do" on a captured trace → Belady's OPT, offline only.