Segmented LRU: separate probation from protected reuse

Last updated: 4 Oct 20269 min read

tutorial

Segmented LRU maintains two access-ordered groups. New incident records enter probation. A read hit in probation moves its record to the protected group, where repeated hits refresh its recency. When protected exceeds its own capacity, its oldest record returns to probation. If that demotion overfills probation, probation's oldest record is evicted. This gives a record that has been read twice a chance to survive a stream of one-time insertions. The implementation uses Python OrderedDict instances, whose map lookups and end moves are expected constant time. It fixes both segment capacities; their sum is the maximum number of residents, but a quiet protected segment does not lend its unused slots to probation in this model.

Operational case

With two probation slots and two protected slots, incidents 47 and 19 enter probation. Reading 47 promotes it. Incident 61 enters probation, and a read promotes it. Reading 19 then fills the protected segment beyond capacity, so its oldest member, 47, falls back into probation. The final protected order is 61 then 19, and probation contains 47. A write to an existing protected record refreshes its protected position. A write to an existing probation record refreshes that group's order but does not count as a promotion; only the read path promotes in this policy. That rule is deliberate and must be stated when comparing traces.

Working Python program

from collections import OrderedDict


class SegmentedIncidentCache:
    def __init__(self, probation_capacity=2, protected_capacity=2):
        if probation_capacity < 1 or protected_capacity < 1:
            raise ValueError("both segment capacities must be positive")
        self.probation_capacity = probation_capacity
        self.protected_capacity = protected_capacity
        self.probation = OrderedDict()
        self.protected = OrderedDict()

    def _trim_probation(self):
        if len(self.probation) > self.probation_capacity:
            return self.probation.popitem(last=False)[0]
        return None

    def get(self, incident_id):
        if incident_id in self.protected:
            self.protected.move_to_end(incident_id)
            return self.protected[incident_id]
        payload = self.probation.pop(incident_id)
        self.protected[incident_id] = payload
        if len(self.protected) > self.protected_capacity:
            demoted_id, demoted_payload = self.protected.popitem(last=False)
            self.probation[demoted_id] = demoted_payload
            self._trim_probation()
        return payload

    def put(self, incident_id, payload):
        if incident_id in self.protected:
            self.protected[incident_id] = payload
            self.protected.move_to_end(incident_id)
            return None
        if incident_id in self.probation:
            self.probation[incident_id] = payload
            self.probation.move_to_end(incident_id)
            return None
        self.probation[incident_id] = payload
        return self._trim_probation()


cache = SegmentedIncidentCache(2, 2)
for incident_id in (47, 19):
    cache.put(incident_id, f"incident-{incident_id}")
cache.get(47)
cache.put(61, "incident-61")
cache.get(61)
cache.get(19)
print("protected=", list(cache.protected), " probation=", list(cache.probation), sep="")

Output

protected=[61, 19] probation=[47]

Time, space, and tradeoff

A successful lookup, insertion, promotion, demotion, and eviction each perform expected O(1) ordered-map operations. Each operation can trigger at most one protected demotion and one probation eviction, so the total expected time is O(1) per call under ordinary hash behavior. Resident storage is O(P + R) for probation capacity P and protected capacity R, plus map metadata. The two fixed partitions can waste available capacity when protected is empty and probation is full. This is not an adaptive policy, does not age access counts, and does not handle weighted objects or expiry.

Common Mistakes

Do not put one incident ID in both segments.
Do not evict the protected oldest member without first demoting it to probation.
Do not promise unused protected slots are borrowed by probation in this model.
Do not count a probation write as a promotion when the implementation promotes only reads.

Connected lessons

Compare retention and timing contracts with CLOCK caches: revisit pages through reference bits, Frequency admission: compare an arrival with an eviction victim, Hashed timing wheels: bucket incident expiries by tick, then run the policy audit and contract quiz.

Resident LRU-K: Evict by the Kth Recent Reference extends this operation comparison.

data structures

range-query-structures