Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Resident LRU-K: Evict by the Kth Recent Reference

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A resident LRU-K cache keeps the last K reference times for each currently cached key. At capacity it evicts the resident whose Kth most recent reference is oldest. A resident with fewer than K references has an undefined Kth time and loses against a fully observed resident; among such cold residents, this explicit policy evicts the one with the oldest latest reference. The code uses a logical counter instead of wall-clock time, so equal timestamps cannot occur. An update is counted as a reference. A missing read raises KeyError and records nothing. On eviction, the resident's history is discarded. This is a bounded, resident-only variant of the idea, rather than a full buffer manager with ghost histories or correlated-reference control.

Operational case

A three-slot incident cache stores 47, 19, and 61. The service then reads 47 and 61, giving each two observations while 19 has only its insertion. When 83 arrives, 19 is the eviction victim even though 83 also starts with one observation. The new resident remains until a later capacity decision. If the service updates 47, that update refreshes its history under this policy; a system that wants reads-only reference counts must choose a different rule. Returning the evicted ID makes the decision observable. Comparing with exact LRU is instructive: the last access alone cannot distinguish a briefly touched page from a page with repeated demand, whereas the second reference can. It still cannot forecast future demand.

Working Python program

python
from collections import deque


class ResidentHistoryCache:
    def __init__(self, capacity, reference_count):
        if capacity < 1 or reference_count < 2:
            raise ValueError("capacity must be positive and reference count at least two")
        self.capacity = capacity
        self.reference_count = reference_count
        self.clock = 0
        self.residents = {}
        self.histories = {}

    def _record(self, case_id):
        self.clock += 1
        self.histories[case_id].append(self.clock)

    def read(self, case_id):
        if case_id not in self.residents:
            raise KeyError(case_id)
        self._record(case_id)
        return self.residents[case_id]

    def put(self, case_id, payload):
        if case_id in self.residents:
            self.residents[case_id] = payload
            self._record(case_id)
            return None
        victim = None
        if len(self.residents) == self.capacity:
            def rank(resident_id):
                history = self.histories[resident_id]
                kth = history[0] if len(history) == self.reference_count else -1
                return (kth, history[-1], resident_id)
            victim = min(self.residents, key=rank)
            del self.residents[victim]
            del self.histories[victim]
        self.residents[case_id] = payload
        self.histories[case_id] = deque(maxlen=self.reference_count)
        self._record(case_id)
        return victim


cache = ResidentHistoryCache(capacity=3, reference_count=2)
for case_id in (47, 19, 61):
    cache.put(case_id, f"case-{case_id}")
cache.read(47)
cache.read(61)
print(cache.put(83, "case-83"))
print(sorted(cache.residents))
print(cache.read(47))

Output

Output
19
[47, 61, 83]
case-47

Time, space, and tradeoff

A resident hit or update performs expected O(1) map work and appends to a deque of at most K timestamps. A full insertion scans all C residents to choose a victim, so that operation takes O(C) time. Storage is O(CK) timestamps plus O(C) keys and payload references. The histories here never survive eviction; this can make a recurring item look cold after it returns. An ordered candidate index could reduce victim scans at the cost of more update work and additional state, but that is outside this example. A tie falls through to the integer case ID after Kth and most-recent times, making repeated traces deterministic. Long-running services should also decide how to handle logical counter rollover and synchronized writes.

Common Mistakes

  • Do not rank a one-reference resident as though it has a Kth reference.
  • Do not call this resident-only implementation a complete database buffer policy.
  • Do not claim full-cache insertion is constant time while it scans every resident.
  • Do not silently change whether writes count as references.

Connected lessons

Compare the operation contract with Splay Trees: Access Rotations and Join Invariants, then work through the audit project and contract quiz.

data structures
range-query-structures
Storage details