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

Frequency admission: compare an arrival with an eviction victim

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

Admission decides whether an arriving item deserves cache space; eviction chooses the resident it would replace. This model keeps an LRU-ordered resident map and a separate four-row frequency sketch. Every lookup attempt and put records the key in the sketch, including a lookup that misses the resident map. A full-cache put compares the candidate's minimum row count with the LRU victim's estimate and admits only when the candidate estimate is strictly greater. Sketch counters saturate at fifteen and are halved after a fixed number of samples, limiting how long old traffic dominates. The digest is deterministic for the teaching trace. This is a simplified frequency-admission cache, not a complete windowed cache policy with adaptive regions or a measured hit-rate claim.

Operational case

Residents 47 and 19 fill a two-entry cache. Four repeated reads of 47 make it a hot resident. Incident 83 arrives once and is rejected because its estimate does not exceed that of the least-recently-used victim. Five observations of incident 61 precede its put; the sketch now rates 61 above victim 19, so 61 is admitted and 19 is removed. The remaining residents are 47 and 61. Recording a request is distinct from admitting its payload, and a rejected candidate can still gain frequency evidence through later requests. Digest collisions may inflate an estimate, so this comparison is a heuristic rather than proof of future demand.

Working Python program

python
from collections import OrderedDict
import hashlib


class AgingFrequencySketch:
    def __init__(self, width=16, rows=4, sample_size=64):
        if min(width, rows, sample_size) < 1:
            raise ValueError("sketch dimensions and sample size must be positive")
        self.width = width
        self.counters = [[0] * width for _ in range(rows)]
        self.sample_size = sample_size
        self.samples = 0

    def _columns(self, incident_id):
        digest = hashlib.blake2b(str(incident_id).encode(), digest_size=16).digest()
        for row in range(len(self.counters)):
            yield int.from_bytes(digest[row * 4:row * 4 + 4], "little") % self.width

    def record(self, incident_id):
        for counters, column in zip(self.counters, self._columns(incident_id)):
            counters[column] = min(15, counters[column] + 1)
        self.samples += 1
        if self.samples == self.sample_size:
            for counters in self.counters:
                for column in range(self.width):
                    counters[column] //= 2
            self.samples = 0

    def estimate(self, incident_id):
        return min(counters[column] for counters, column in zip(self.counters, self._columns(incident_id)))


class FrequencyAdmissionCache:
    def __init__(self, capacity=2):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.order = OrderedDict()
        self.sketch = AgingFrequencySketch()

    def get(self, incident_id):
        self.sketch.record(incident_id)
        self.order.move_to_end(incident_id)
        return self.order[incident_id]

    def put(self, incident_id, payload):
        self.sketch.record(incident_id)
        if incident_id in self.order:
            self.order[incident_id] = payload
            self.order.move_to_end(incident_id)
            return True
        if len(self.order) == self.capacity:
            victim_id = next(iter(self.order))
            if self.sketch.estimate(incident_id) <= self.sketch.estimate(victim_id):
                return False
            self.order.popitem(last=False)
        self.order[incident_id] = payload
        return True


cache = FrequencyAdmissionCache(2)
cache.put(47, "incident-47")
cache.put(19, "incident-19")
for _ in range(4):
    cache.get(47)
accepted_cold = cache.put(83, "incident-83")
for _ in range(5):
    cache.sketch.record(61)
accepted_warm = cache.put(61, "incident-61")
print("cold=", accepted_cold, " warm=", accepted_warm,
      " resident=", list(cache.order), sep="")

Output

Output
cold=False warm=True resident=[47, 61]

Time, space, and tradeoff

With R rows, W counters per row, and key encoding length K, recording or estimating a key costs O(R + K) for bounded digest work; in this fixed model R is four. Every sample_size records the sketch halves all RW counters in O(RW) time, so an individual operation can have that spike. The cache map and recency update are expected O(1). Storage is O(RW + C) for C residents, excluding Python object overhead. Counter saturation and aging discard precise historical frequencies. A different hash policy, sample interval, or tie rule can change decisions, and a workload trace is needed to evaluate actual hit rates.

Common Mistakes

  • Do not call the sketch estimate an exact request count.
  • Do not admit every miss automatically when the cache is full.
  • Do not compare a candidate with an arbitrary resident when the policy names the LRU victim.
  • Do not omit the O(RW) counter-halving spike from worst-case cost.

Connected lessons

Compare retention and timing contracts with CLOCK caches: revisit pages through reference bits, Segmented LRU: separate probation from protected reuse, Hashed timing wheels: bucket incident expiries by tick, then run the policy audit and contract quiz.

data structures
range-query-structures
Storage details