LRU, LFU, Random, TTL-Aware Eviction, and Memory Pressure

1. Eviction starts when useful data exceeds available cache memory

A cache has finite capacity. When a new entry arrives and no free space remains, an eviction policy chooses a victim before that victim's normal expiration. Eviction therefore differs from TTL expiration: expiration follows lifecycle metadata; eviction follows memory pressure.

LRU favors recently accessed entries. LFU favors frequently accessed entries, usually with aging/decay in practical systems. Random avoids per-key recency/frequency bookkeeping. A TTL-aware heuristic can prefer entries whose remaining lifetime is shortest. None is universally optimal because the future request distribution is unknown.

2. Same workload, different victims

AtlasMart repeatedly reads keys A and B, then performs a one-time scan through C–G, then returns to A and B. A strict recency policy can let the scan push formerly hot entries out of a three-slot cache. A frequency-aware policy may retain them because earlier repeated hits increased their score. If popularity changes, LFU can instead become sticky unless old frequency decays.

3. Real systems often approximate textbook policies

Maintaining exact global LRU order at very high throughput costs CPU, memory, and synchronization. Redis, for example, documents sampled/approximated LRU and probabilistic LFU counters. Therefore benchmark the implementation you actually deploy, not an abstract algorithm name. Policy metadata itself consumes memory; expiry metadata also has a cost.

4. Admission matters, and capacity remains the hard limit

Eviction decides what leaves. An admission policy can decide whether a newly observed item deserves cache space at all. This helps prevent one-time scans from displacing the useful working set. But if AtlasMart's steady hot working set is ten large objects and the cache holds only three, no policy can keep all ten simultaneously. The system must accept misses, increase effective capacity, reduce object size, shard/partition differently, or change what is cached.

5. AtlasMart lab: compare victim heuristics

from collections import OrderedDict, Counter
import random

trace = list("ABABAB") + list("CDEFG") + list("ABAB")
capacity = 3

def run_lru(trace):
    c=OrderedDict(); hits=0; ev=[]
    for k in trace:
        if k in c:
            hits += 1; c.move_to_end(k)
        else:
            if len(c) >= capacity:
                ev.append(c.popitem(last=False)[0])
            c[k]=True
    return hits, ev, list(c)

def run_lfu(trace):
    c=set(); freq=Counter(); age={}; hits=0; ev=[]
    for t,k in enumerate(trace):
        if k in c: hits += 1
        else:
            if len(c) >= capacity:
                victim=min(c, key=lambda x:(freq[x], age[x]))
                c.remove(victim); ev.append(victim)
            c.add(k); age[k]=t
        freq[k]+=1
    return hits, ev, sorted(c)

def run_random(trace):
    rng=random.Random(7); c=[]; hits=0; ev=[]
    for k in trace:
        if k in c: hits += 1
        else:
            if len(c) >= capacity:
                victim=rng.choice(c); c.remove(victim); ev.append(victim)
            c.append(k)
    return hits, ev, c

for name,fn in [("LRU",run_lru),("LFU",run_lfu),("RANDOM",run_random)]:
    hits,ev,final=fn(trace)
    print(name, "hits=", hits, "evicted=", ev, "final=", final)

print("\nTTL-AWARE VICTIM CHOICE")
remaining_ttl={"hot":3, "warm":40, "cold":8}
print("shortest remaining TTL victim:", min(remaining_ttl, key=remaining_ttl.get))
print("but 'hot' may still be the highest-value cache entry")

print("\nCAPACITY REALITY")
working_set=10
print("working set", working_set, "capacity", capacity, "minimum simultaneous misses remain inevitable")
print("lesson: eviction changes which misses you pay for; it does not create memory")

6. Deliberately wrong approach: “LRU is the best default, so capacity no longer matters”

That conclusion turns a heuristic into a guarantee. A cache can have excellent steady-state hit ratio and still collapse under a scan, synchronized cold start, or object-size growth. A safer process measures the key/value size distribution, working-set curve, hit ratio by policy, evictions/sec, memory fragmentation/overhead, and origin load during eviction bursts.

7. Production judgment and bridge

Choose eviction with real traffic traces, not folklore. Test policy under Zipf-like hotness, scans, bursts, deploy cold starts, TTL mixes, and changing popularity. Watch hit/miss ratio, evictions, rejected writes, resident bytes, metadata overhead, per-shard skew, and origin saturation. A tenant that can flood unique keys can also evict other tenants' useful data, so quotas/admission may be part of isolation.

The next lesson moves from individual victims to correlated misses: synchronized expiration can make hundreds of clients hit the same source at once.