TTL LRU LFU and Cache Memory Limits

01 The idea

The problem this lesson solves

A cache has finite memory. When new data no longer fits, the system must reject writes, remove entries or use another configured behavior. Separately, values may expire because they are too old under the cache policy. Eviction and expiration solve different problems. We will trace concrete reads through a tiny cache so the policies become visible rather than remaining acronyms.

You should recognize the application, the database and the request path. Treat the database as the authority unless explicitly stated otherwise.

02 Worked example

Trace six reads through a two-entry cache

03 The method

Understand the mechanism

Separate expiration from eviction

Expiration removes or makes an entry unavailable after its lifetime ends. Eviction removes an entry to satisfy a capacity policy, even if its TTL has not elapsed. A value can disappear because of either event, manual deletion, restart or another operational action.

A TTL therefore does not promise that an entry will remain present for that duration. It sets an expiry boundary under the implementation’s behavior. Applications using a cache must tolerate earlier misses and recover from the authority.

Likewise, a long TTL does not guarantee fresh data. It may keep an old value eligible for reuse longer unless updates are coordinated. Memory management and freshness are related operationally but are not the same guarantee.

When diagnosing misses, distinguish expired entries, capacity evictions and absent keys that were never loaded. They suggest different remedies: changing expiry policy, increasing useful capacity or improving access patterns.

Trace exact LRU by hand

Least recently used, or LRU, removes the entry whose last access is oldest in the model. Use capacity two and requests A,B,A,C,A,B. Write cache order from least recent to most recent after every request.

A misses and gives [A]. B misses and gives [A,B]. A hits and moves to the most-recent end, giving [B,A]. C misses, evicts B and gives [A,C]. A hits and gives [C,A]. B misses, evicts C and gives [A,B].

There are two hits and four misses, for a hit ratio of 2/6 ≈ 33.3%. The final set alone does not reveal that history; you must trace accesses and updates to recency.

LRU exploits temporal locality: recently used data may be used again soon. A one-time scan over many distinct keys can evict a useful hot set, so recency is not always a good predictor. Actual cache products may approximate LRU to reduce bookkeeping cost; the exact toy model teaches the policy, not every implementation detail.

Compare FIFO and LFU on workload behavior

First in, first out removes the oldest inserted entry without moving it merely because it was read. In the same A,B,A,C sequence, reading A does not renew its position, so C can evict A. FIFO has different metadata and behavior from LRU.

Least frequently used, or LFU, favors entries accessed often. It can protect a repeatedly popular key from a stream of one-time reads. But frequency needs a time model: an entry popular last month should not necessarily dominate forever after the workload changes.

Implementations may use approximate counters, decay or sampling. Tie-breaking also matters in small examples. State the exact toy policy before calculating a hit count, and consult the selected product’s behavior before relying on a particular ordering.

Choose with representative traces rather than a universal ranking. A cache serving a stable hot set, a sequential scan and a rapidly changing trend can favor different policies. Memory cost and bookkeeping overhead also contribute.

Size entries and choose the eviction domain

Memory use includes key bytes, value bytes and structural overhead. Two caches with the same entry count can consume very different memory if one stores large JSON documents and the other stores small identifiers.

An eviction policy can apply to all keys or a configured subset, depending on the system. Mixing disposable cache entries with authoritative counters or session state in one eviction domain can remove data the application was not prepared to lose.

Decide what happens when memory is full and no eligible entry can be removed. Some configurations reject memory-growing writes rather than evicting. The application must handle that result instead of assuming every SET succeeds.

Monitor memory, evictions, rejected writes, hit ratio and origin load together. Increasing the memory limit can help if the working set barely exceeds capacity, but not if keys grow without bound because the application includes a random value in every key.

Use TTL commands as observations, not assumptions

In the Redis tutorial, SET with EX 60 stores a value with a sixty-second expiry. GET retrieves it while present. TTL reports remaining lifetime in seconds, with special values indicating missing keys or keys without expiry.

The remaining TTL changes as time passes, so a test should check a valid range rather than require exactly 60 at every observation. After DEL, GET returns a miss and TTL reports the missing-key sentinel. This gives you a concrete way to distinguish a value from its lifetime metadata.

Be careful when rewriting values or copying data between layers: the operation’s expiry behavior must be understood. A new write may require explicitly preserving or setting the intended TTL under that command’s semantics.

Expiration work and physical reclamation are implementation details; application correctness should depend on documented lookup semantics rather than guessing when a background cleanup loop frees memory. A cache miss remains a normal branch.

Tune using traces and recovery limits

Capture an appropriate access trace or generate a representative workload in a practice environment. Compare policies at several capacities while keeping the trace constant. Report hit ratio, origin work and memory rather than choosing a winner from one tiny example.

Include a working-set change. A policy that performs well during steady popularity may recover slowly when a new campaign starts. Include large values and cold scans if they exist in the real workload.

Eviction can create an origin surge. If many useful entries disappear together, misses increase even though external QPS is unchanged. The cache recovery lesson supplies coalescing and admission controls; eviction tuning alone cannot guarantee safe origin load.

Your design should explain which data is disposable, which policy selects victims, how expiration differs, and what the application does on a miss or rejected fill. Those statements are more durable than memorizing a product’s default setting.

redis-cli SET sd:lab:link:a7 https://example.com EX 60
redis-cli GET sd:lab:link:a7
redis-cli TTL sd:lab:link:a7
redis-cli DEL sd:lab:link:a7
redis-cli GET sd:lab:link:a7
# Expected final result: nil (cache miss)
# TTL: -2 means missing; -1 means an existing key has no expiry.

from collections import OrderedDict
cache = OrderedDict()
hits = 0
for key in ["A", "B", "A", "C", "A", "B"]:
    hit = key in cache
    if hit:
        hits += 1
        cache.move_to_end(key)
    else:
        if len(cache) == 2:
            cache.popitem(last=False)
        cache[key] = True
    print(key, "hit" if hit else "miss", "".join(cache))
print(f"hits={hits}, misses={6-hits}")

A miss A
B miss AB
A hit BA
C miss AC
A hit CA
B miss AB
hits=2, misses=4

05 Cheat sheet

Review the decisions

Use this table to explain the mechanism and its limit without memorizing a product name.

06 Where & why

Check the primary references

Use official references for protocol and implementation details. The questions here are teaching prompts.

07 Interview questions

Explain the reasoning out loud

Answer before opening the explanation. The questions progress from vocabulary to decisions and failure behavior.

08 Practice problems

Practice a new case

Solve the new cases before revealing hints. Complete worked solutions follow the set.

Worked solutions