Caching, Part 2: how caches decide what to forget — and stay correct

1 Eviction mechanisms — deciding what to drop

Recall from Session 3 that a cache is a small, fast store that keeps copies of the data we use most. The word "small" is the whole point: fast memory (like RAM) is expensive, so a cache only has room for a tiny slice of all your data. When the cache is full and a new item needs to come in, something already inside must go. Choosing what to remove is called eviction, and the rule that makes the choice is an eviction policy (sometimes called a replacement policy).

Why a cache is (almost) always full

When you first start a cache server, it is empty. But an empty cache is wasted cache — you want it holding as much useful data as possible. So as requests flow in, the cache fills up… and from that point onwards it stays full (until it crashes and restarts). Once it's full but you still want to cache more data, you must first kick something out to make room. That is the entire job of an eviction policy: decide which already-cached item to "kick out" to make space for new data.

Two words you'll hear constantly

• Cache hit — you asked for something and it was already in the cache (fast! good!).
• Cache miss — it wasn't there, so you had to fetch it from the slow source and (usually) put it in the cache, evicting something if full.

The goal of every eviction policy is to maximise the hit rate — the percentage of requests that are hits.

The policies, one at a time

LRU — Least Recently Used

LRU evicts the item that hasn't been touched for the longest time. The bet: "if you haven't used it in a while, you probably won't need it soon." This is the most popular policy in real systems (the right choice in ~99% of cases) because it matches how people actually use data — recently used things tend to be used again.

LFU — Least Frequently Used

LFU evicts the item that has been used the fewest times overall. It keeps a counter per item. The bet: "popular things stay popular." Great for items with a stable, long-term popularity (a viral video everyone keeps watching), but it can keep stale "once-famous" items around too long and is slow to let go of yesterday's hits.

An O(1) LFU keeps a frequency bucket for each count: each bucket is itself an ordered list of keys with that exact frequency. We track the min_freq bucket so the victim is found instantly; on a tie within a bucket we evict the least-recently-used key (insertion order).

# LFU cache: O(1) get/put with frequency buckets; LRU tie-break within a bucket
from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap      = capacity
        self.val      = {}                       # key -> value
        self.freq     = {}                       # key -> use count
        self.buckets  = defaultdict(OrderedDict)  # count -> keys (oldest first)
        self.min_freq = 0

    def _bump(self, key):                        # move key to its next-higher bucket
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f] and f == self.min_freq:
            self.min_freq += 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

    def get(self, key):
        if key not in self.val:
            return -1                           # cache miss
        self._bump(key)
        return self.val[key]

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.val:                       # update + bump frequency
            self.val[key] = value
            self._bump(key)
            return
        if len(self.val) >= self.cap:            # evict least-frequent (oldest within bucket)
            evict, _ = self.buckets[self.min_freq].popitem(last=False)
            del self.val[evict]; del self.freq[evict]
        self.val[key]  = value
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq  = 1

# --- demo ---
c = LFUCache(2)
c.put(1, 10); c.put(2, 20)
print(c.get(1))   # 10  (freq of 1 -> 2, freq of 2 stays 1)
c.put(3, 30)      # full -> evicts key 2 (least frequent)
print(c.get(2))   # -1  (evicted)
print(c.get(3))   # 30

// LFU cache: O(1) get/put with frequency buckets; LRU tie-break within a bucket.
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LFUCache {
    int cap, minFreq = 0;
    unordered_map<int, pair<int, int>> val;            // key -> {value, freq}
    unordered_map<int, list<int>> buckets;             // freq -> keys (front = oldest)
    unordered_map<int, list<int>::iterator> pos;       // key -> node in its bucket

    void bump(int key) {                              // move key to next-higher bucket
        int f = val[key].second;
        buckets[f].erase(pos[key]);
        if (buckets[f].empty() && f == minFreq) minFreq++;
        val[key].second = f + 1;
        buckets[f + 1].push_back(key);
        pos[key] = prev(buckets[f + 1].end());
    }
public:
    LFUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (!val.count(key)) return -1;             // cache miss
        bump(key);
        return val[key].first;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (val.count(key)) { val[key].first = value; bump(key); return; }
        if ((int)val.size() >= cap) {                // evict least-frequent, oldest first
            int evict = buckets[minFreq].front();
            buckets[minFreq].pop_front();
            val.erase(evict); pos.erase(evict);
        }
        val[key] = {value, 1};
        buckets[1].push_back(key);
        pos[key] = prev(buckets[1].end());
        minFreq = 1;
    }
};

int main() {
    LFUCache c(2);
    c.put(1, 10); c.put(2, 20);
    cout << c.get(1) << "\n";   // 10
    c.put(3, 30);                  // evicts key 2 (least frequent)
    cout << c.get(2) << "\n";   // -1
    cout << c.get(3) << "\n";   // 30
}

// LFU cache: O(1) get/put with frequency buckets; LRU tie-break within a bucket.
import java.util.*;

class LFUCache {
    private final int cap;
    private int minFreq = 0;
    private final Map<Integer, Integer> val  = new HashMap<>();   // key -> value
    private final Map<Integer, Integer> freq = new HashMap<>();   // key -> count
    // freq -> keys, insertion-ordered so the eldest is the LRU tie-break
    private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();

    public LFUCache(int capacity) { this.cap = capacity; }

    private void bump(int key) {                        // move key to next-higher bucket
        int f = freq.get(key);
        buckets.get(f).remove(key);
        if (buckets.get(f).isEmpty() && f == minFreq) minFreq++;
        freq.put(key, f + 1);
        buckets.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        if (!val.containsKey(key)) return -1;        // cache miss
        bump(key);
        return val.get(key);
    }

    public void put(int key, int value) {
        if (cap == 0) return;
        if (val.containsKey(key)) { val.put(key, value); bump(key); return; }
        if (val.size() >= cap) {                       // evict least-frequent, eldest first
            LinkedHashSet<Integer> b = buckets.get(minFreq);
            int evict = b.iterator().next();
            b.remove(evict);
            val.remove(evict); freq.remove(evict);
        }
        val.put(key, value);
        freq.put(key, 1);
        buckets.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    public static void main(String[] args) {
        LFUCache c = new LFUCache(2);
        c.put(1, 10); c.put(2, 20);
        System.out.println(c.get(1)); // 10
        c.put(3, 30);                 // evicts key 2 (least frequent)
        System.out.println(c.get(2)); // -1
        System.out.println(c.get(3)); // 30
    }
}

FIFO — First In, First Out

FIFO evicts whatever was added first, regardless of how often or how recently it's been used — like a queue at a ticket counter. Simple and cheap, but dumb: it might evict a super-popular item just because it happens to be old.

MRU — Most Recently Used

MRU is the complete opposite of LRU: it evicts the item used most recently. Sounds backwards, and it is bad for 99% of cases — but it shines in specific patterns, e.g. scanning a big file once top-to-bottom, where the page you just read is the one you're least likely to read again soon. Homework: find a valid use-case of the MRU eviction policy.

FIFO vs LIFO

Alongside FIFO there's LIFO (Last In, First Out) — evict whatever was added most recently, like a stack. Both ignore usage entirely; they are simple but rarely the best choice. In practice the field narrows to FIFO, LIFO, LRU, LFU, and MRU, and for ~99% of cases the answer is LRU.

Random

Random replacement just picks a victim at random. No bookkeeping at all. It sounds careless, but it's extremely cheap and, surprisingly, performs almost as well as LRU in some hardware caches — which is why CPUs sometimes use it.

TTL-based — Time To Live

A TTL (Time To Live) isn't a victim-selection rule like the others; it's an expiry stamp. Each item is tagged "good until 3:05pm." After that, it's treated as gone no matter how popular it is. TTL is usually combined with another policy: TTL handles "too old to trust," while LRU/LFU handle "no room left." We'll lean on TTL heavily in the consistency and case-study sections.

Implementing LRU: hashmap + doubly linked list

LRU needs two things to be fast: instant lookup ("is X in the cache?") and instant reordering ("mark X as just-used" and "find the oldest item"). The classic trick combines two data structures so that every operation is O(1):

• A hashmap from key → node for O(1) lookup.
• A doubly linked list ordered by recency: the head is the most-recently-used end, the tail is the least-recently-used end. A doubly linked node (with prev and next pointers) lets us unlink and move a node in O(1) without scanning.

On a get, we look the key up in the map and move its node to the head (just used). On a put, we add at the head; if we're over capacity, we drop the tail node (the oldest) and remove it from the map.

# LRU cache: O(1) get and put using hashmap + doubly linked list
class Node:
    def __init__(self, key, value):
        self.key   = key
        self.value = value
        self.prev  = None      # toward head (most recent)
        self.next  = None      # toward tail (least recent)

class LRUCache:
    def __init__(self, capacity):
        self.cap  = capacity
        self.map  = {}                  # key -> Node, gives O(1) lookup
        # two dummy "sentinel" nodes so we never check for None edges
        self.head = Node(None, None)   # most-recently-used side
        self.tail = Node(None, None)   # least-recently-used side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):            # unlink a node, O(1)
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):         # insert right after head, O(1)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.map:
            return -1               # cache miss
        node = self.map[key]
        self._remove(node)              # pull it out...
        self._add_front(node)           # ...and mark as most-recently-used
        return node.value

    def put(self, key, value):
        if key in self.map:           # update existing
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:   # over capacity -> evict LRU
            lru = self.tail.prev        # node just before tail = oldest
            self._remove(lru)
            del self.map[lru.key]

# --- demo ---
c = LRUCache(2)
c.put(1, 10); c.put(2, 20)
print(c.get(1))   # 10  (1 is now most-recently-used)
c.put(3, 30)      # full -> evicts key 2 (least recent)
print(c.get(2))   # -1  (miss, was evicted)
print(c.get(3))   # 30

// LRU cache: O(1) get and put using unordered_map + doubly linked list.
// std::list is a doubly linked list; we store iterators for O(1) splice.
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int, int>> dll;                          // front = most recent, back = least recent
    unordered_map<int, list<pair<int, int>>::iterator> map;  // key -> node
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;             // cache miss
        dll.splice(dll.begin(), dll, it->second);      // move node to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) dll.erase(it->second);     // drop old node
        dll.push_front({key, value});                  // insert at most-recent end
        map[key] = dll.begin();
        if ((int)map.size() > cap) {                 // over capacity -> evict LRU
            map.erase(dll.back().first);
            dll.pop_back();                            // back = least recent
        }
    }
};

int main() {
    LRUCache c(2);
    c.put(1, 10); c.put(2, 20);
    cout << c.get(1) << "\n";   // 10
    c.put(3, 30);                  // evicts key 2
    cout << c.get(2) << "\n";   // -1
    cout << c.get(3) << "\n";   // 30
}

// LRU cache: O(1) get and put by extending LinkedHashMap (map + DLL built in)
import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int cap;

    public LRUCache(int capacity) {
        // accessOrder=true: get/put move an entry to the most-recent end
        super(capacity, 0.75f, true);
        this.cap = capacity;
    }

    // LinkedHashMap calls this after each insert; true -> drop eldest (LRU)
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > cap;
    }

    public int get(int key) {
        return getOrDefault(key, -1);   // -1 on a cache miss
    }

    public static void main(String[] args) {
        LRUCache c = new LRUCache(2);
        c.put(1, 10); c.put(2, 20);
        System.out.println(c.get(1)); // 10
        c.put(3, 30);                 // evicts key 2
        System.out.println(c.get(2)); // -1
        System.out.println(c.get(3)); // 30
    }
}

Comparison table

2 Consistency models for caches

A cache holds a copy of data that really "lives" somewhere else (the database, the source of truth). The moment we keep a copy, we face a question: when the original changes, how quickly must the copy agree with it? The answer is the cache's consistency model.

First, two plain words: consistent vs inconsistent

• Consistent — it is not possible to read a stale value. Every read is guaranteed to return the latest data.
• Inconsistent — it is possible for reads to be stale (you might read an old value).

With that, there are three consistency models you'll hear about (we cover two in depth here; the third is the scary one):

Strong (immediate) consistency

Strong consistency (also called immediate consistency) means: the instant the real data changes, every read — from cache or database — sees the new value. There is never a moment where someone reads an outdated copy. To guarantee this, the cache and database must be kept in lockstep on every write (e.g. update both together, or wipe the cached copy the moment the data changes — we'll see exactly how in Section 3).

Eventual consistency

Eventual consistency means: after a change, copies will all agree eventually — but for a short window, some readers may still get the old value. As long as no new writes come in, given enough time everything converges to the latest value. The gap between "data changed" and "all copies updated" is when staleness lives.

How TTL gives you "tunable" eventual consistency

Recall TTL from Section 1. A TTL is the dial that controls how stale data can get. If you cache a value with TTL = 60s, the cache promises the copy is at most 60 seconds old. So the worst-case staleness equals the TTL. Shorter TTL → fresher data but more cache misses (more trips to the slow database); longer TTL → faster but staler. The TTL knob lets you trade freshness for speed.

3 Write strategies & invalidation

Sections 1 and 2 set up the problem: cached copies drift from the truth, and we must decide how fresh to keep them. A write strategy is the concrete rule for what happens to the cache when data is written or changed. Closely related is cache invalidation — marking a cached copy as no longer valid so it won't be served. (There's a famous joke: "There are only two hard things in computer science: cache invalidation and naming things." It's hard because getting it wrong means serving wrong data.)

How cache reads & writes actually happen

Before naming strategies, here's the typical read/write cycle that most caches use:

• Writes go directly to the database (typically) — not to the cache.
• Reads: the app server first checks the cache.
  • Cache hit (value present) → return the cached value.
  • Cache miss (value absent) → app server fetches the value from the DB, returns it to the user, and (asynchronously) updates the value in the cache.

Two reading patterns first

How data gets into the cache also matters. Two read patterns:

• Cache-aside (lazy loading) — the application talks to the cache itself. On a miss, the app loads from the DB and then fills the cache. The cache only ever holds things that were actually requested.
• Read-through — the app only ever talks to the cache; the cache itself knows how to fetch from the DB on a miss. (Mentioned for completeness; cache-aside is by far the most common.)

Cache-aside (lazy loading) — the default workhorse

This is the most common pattern in real systems. Reads are "lazy": data is loaded into the cache only when first requested.

# Cache-aside read (lazy loading)
def get_user(user_id):
    user = cache.get(user_id)
    if user is not None:
        return user                 # cache hit
    user = db.query(user_id)         # cache miss -> go to source of truth
    cache.set(user_id, user, ttl=300) # fill cache for next time (5-min TTL)
    return user

On a write with cache-aside, you update the DB and then invalidate (delete) the cached copy, so the next read re-loads the fresh value:

# Cache-aside write: update DB, then invalidate the stale copy
def update_user(user_id, new_data):
    db.update(user_id, new_data)     # source of truth changes first
    cache.delete(user_id)            # invalidate -> next read reloads fresh

TTL (Time To Live) — the simplest invalidation policy

TTL is both an invalidation policy and (with a small modification) an eviction consideration — you may even see it listed as an eviction strategy because it's so simple. (Strictly, pure TTL is not an eviction policy on its own.)

The idea: whenever you store data in the cache, alongside the value you also store an expiry time. Every entry is valid for a fixed amount of time (its TTL). TTL can be set globally (one value for all keys) or per key. After the TTL expires, we assume the value is stale and invalidate it — even though in reality we have no idea whether the DB value actually changed.

For example, if we write a = 10 at 8 am with a TTL of 1 hour, the entry's expiry is set to 9 am:

When do we actually delete an expired entry? Eager vs Lazy

• Eager invalidation — delete the entry immediately when its expiry passes. This forces the cache to run a timer/event loop per expiry (think Timer + Priority Queue), adding overhead. Worse, if many entries share an expiry time (say 9 am), then at 9 am incoming requests must wait while the cache busily clears all the expired entries. Performance becomes "jittery" — not smooth — with temporary latency spikes during cleanup.
• Lazy invalidation — delete the entry only when the next read for that key arrives and finds it expired. You may temporarily store stale data (wasted space), but that's fine because the eviction algorithm reclaims it anyway. Lazy is almost always better: it gives smooth latency across all requests.

What's the ideal TTL value?

Completely application-dependent — anywhere from 5 seconds to a week.

• Lower TTL → more cache misses (data invalidated quickly), but data is fresher.
• Higher TTL → better hit rate, but data is staler.

Write-around — a background job recomputes the cache

Write-around is very similar to TTL in that it also provides eventual consistency, but it's used for a different reason. The key difference is how expensive it is to produce the cached value:

• TTL works best when fetching an entry from the DB is easy and needs little post-processing. Example — caching user preferences:

  -- table: user_preferences(user_id bigint, name text, preferences json)
  SELECT * FROM user_preferences WHERE user_id = 1234;

  A very simple, fast query. If we're OK with eventual consistency, TTL is ideal here.
• Write-around works best when producing the data is extremely expensive or needs heavy computation. Example — "find all users using dark theme on a mobile device":

  -- expensive join + group-by
  SELECT * FROM user_preferences up
  JOIN user_devices ud ON ud.user_id = up.user_id
  WHERE ud.device_type = 'mobile' AND up.theme = 'dark'
  GROUP BY up.user_id;

  A complex, slow query — here a write-around policy is better.

With write-around there's a separate background process (running in its own app server) that periodically fetches all recently updated data from the DB, does the heavy computation, and updates the cache in one go:

# background "cron job": recompute and refresh the cache in bulk
SELECT * FROM ...
WHERE updated_at > (now() - '1 hour');

Write-through — update cache and DB together, synchronously

Write-through means every write goes through the cache to the DB in the same operation: write the cache and the DB before reporting success. The cache is never out of date, so it naturally supports strong consistency — at the cost of slower writes (you pay for two writes every time).

# Write-through: both updated before we return success
def write_through(key, value):
    cache.set(key, value)            # 1) update cache
    db.write(key, value)             # 2) update DB, synchronously
    return "ok"                    # only now is the write "done"

Write-back (write-behind) — update cache now, DB later

Write-back (a.k.a. write-behind) writes only to the cache immediately and returns success right away; the DB is updated later, asynchronously (in a batch or after a short delay). It provides no consistency guarantees — in fact it can lead to data loss.

# Write-back: ack immediately, flush to DB asynchronously
def write_back(key, value):
    cache.set(key, value)            # update cache now
    dirty_queue.push(key)            # mark "needs flushing to DB"
    return "ok"                    # return BEFORE the DB is updated

# a background worker drains the queue periodically
def flush_worker():
    while True:
        key = dirty_queue.pop()      # risk: a crash here loses un-flushed writes
        db.write(key, cache.get(key))

Write-around — write straight to the DB, skip the cache

Write-around writes new data only to the DB and does not put it in the cache. The cache is populated only later, on a read miss (often paired with cache-aside reads). Good when freshly written data is rarely read again soon — it avoids flooding the cache with write-only data. The downside: a read right after a write is a guaranteed miss (the new data isn't cached yet).

Putting the write strategies side by side

4 Case study — Scaler Code Judge

Let's design caching for a code judge — an online-judge system (think Scaler, LeetCode, Codeforces) where a user reads a problem, submits code, and the system runs that code against hidden test cases to produce a verdict like "Accepted" or "Wrong Answer." It's read-heavy and latency-sensitive — a perfect caching playground that lets us apply everything from Sections 1–3.

Step 1 — What should we cache?

The first design question is always what data is read far more often than it changes? Those are the caching candidates. Let's classify the judge's data:

Step 2 — What consistency does each need?

Now apply Section 2. Each data type tolerates a different amount of staleness:

• Problem statements: mostly eventual consistency is fine (a long TTL, say minutes to hours). But when an author fixes a wrong example or a typo that changes the answer, we must invalidate immediately — a stale statement could make a correct solution look wrong.
• Test cases: this is the strict one. If a buggy test case is fixed, every later submission must be judged against the new set. A stale test case = wrong verdicts. So we want strong consistency: invalidate the moment they change.
• Verdicts: trivially consistent because they're immutable — a verdict for submission #12345 is computed once and never changes. Immutable data is the easiest thing in the world to cache: cache it forever, never invalidate.
• Leaderboard: eventual consistency with a short TTL (e.g. 5–10s) is perfect — nobody is harmed if the ranking is a few seconds behind.

Step 3 — Which write strategy and eviction policy?

• Reads: use cache-aside (Section 3) everywhere — on a miss, load from the DB and fill the cache. Simple and robust.
• Problem statements & test cases: on an author edit, do a cache-aside write: update the DB, then invalidate (delete) the cached key so the next read reloads the fresh version. For test cases we make this invalidation reliable (strong consistency) so no submission is judged on stale tests.
• Verdicts: write-through is natural and safe — when a verdict is computed, store it in both DB and cache. Since it's immutable, there's never an invalidation to worry about.
• Eviction: LRU for problem statements and test cases (popular problems stay hot, old contest problems fade out naturally). Add a TTL as a safety net so nothing lingers wrong forever. LFU would also work well for problems, since a handful of famous problems are read constantly.

Step 4 — Walk through the design end to end

# --- Read path (cache-aside) used by the judge for every submission ---
def get_test_cases(problem_id):
    tests = cache.get(f"tests:{problem_id}")
    if tests is not None:
        return tests                       # hit: thousands of submissions reuse this
    tests = db.get_test_cases(problem_id)    # miss: load from source of truth
    cache.set(f"tests:{problem_id}", tests, ttl=3600)  # LRU + 1h TTL safety net
    return tests

# --- Author edits the test cases: strong consistency required ---
def update_test_cases(problem_id, new_tests):
    db.set_test_cases(problem_id, new_tests)     # 1) source of truth first
    cache.delete(f"tests:{problem_id}")        # 2) invalidate immediately
    cache.delete(f"problem:{problem_id}")      # 3) statement may reference them too
    # next submission misses, reloads fresh tests -> no more wrong verdicts

★ Putting it all together

You've now gone from "what is a cache" (Session 3) to "how do real caches stay small and correct." Here's the one-paragraph story tying the four topics together:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] - Caching 2".

Papers, docs & deep dives

• AWS: Caching best practices — cache-aside, write-through and other write strategies explained.
• Redis: Key eviction policies — LRU, LFU, TTL and how a real cache evicts under memory pressure.
• MDN: HTTP caching — freshness, expiry and cache invalidation in practice.