Step 1 of 5 · Reading · ~1 min

Read

Why LRU

Why Caches?

A cache trades memory for speed. Common pattern: keep the most-frequently-used data in fast storage so you don't redo expensive work.

def get_user(user_id):
    if user_id in cache:
        return cache[user_id]   # 0.1ms
    user = db.query(user_id)    # 10ms
    cache[user_id] = user
    return user

The challenge: cache is BOUNDED. When full, you must EVICT something. The eviction policy determines what's good vs bad cache:

Policy	Strategy	Hit rate
Random	Evict random entry	OK
FIFO	Evict oldest INSERT	OK
LRU	Evict least-recently-USED	Best for typical workloads
LFU	Evict least-frequently-USED	Best when popularity is stable
ARC	Adaptive: blend recency + frequency	Excellent (used in ZFS)
TinyLFU	Frequency-aware with bloom filter	Excellent (used in Caffeine)

LRU is the workhorse: when used recently means likely-to-be-used-again, LRU is near-optimal. The implementation is also simple — O(1) get/put with the right data structures.

Next: Practice

Up nextNaive LRU: List ScanWhy LRU

Discussion

Ask a question, share an insight, or help someone who’s stuck.

Loading…