Loading...
System Design and AI Engineering, by Roni Das. 972 interactive lessons.
Start LearningFoundation · Caching Strategies
A cache that, when full, throws away the item nobody has used for the longest time. It keeps recently used data on the bet that it will be used again soon.
In short
An LRU cache is a cache with a size limit that, when it is full, removes the item nobody has used for the longest time. LRU stands for least recently used. It bets that something used recently will be used again soon.
In short
An LRU cache is a cache with a size limit that, when it is full, removes the item nobody has used for the longest time. LRU stands for least recently used. It bets that something used recently will be used again soon.
This page is the free part.
₹499 in India$49 everywhere elseonce, for the whole course
The System Design course covers LRU Cache across a run of lessons, not one page. These 4 alone are about 86 minutes of step-by-step reading, every one with a quiz.
LFU beat LRU by 6 to 15 points, FIFO measured identical to random, and the scan that supposedly destroys LRU cost it 11 points for four hundred requests.
Write-through took the read hit rate from 71.5 percent to 68.3 on uniform writes, and from 59.5 to 71.9 on correlated ones. It is a bet on whether your writes predict your reads.
A batch job taking 30 percent of requests cost LRU 6.3 points of hit rate on the real requests, admission by approximate frequency 4.2, and exact counting 0.8, in 2,048 bytes.
Granting the minimum permissions necessary to perform a task, nothing more, nothing less.
all part of
System Design Masterclass
769 lessons · about 282 hours · 18 free to read
₹499in India, by UPI
$49everywhere else, by PayPal
The material has been designed with a lot of effort and dedication. It has covered vast range of topic with sufficient content and diagrams wherever required. It complements well with other system design materials.
You own this course
Continue with Cache Eviction Policiespay once,
yours for life
A cache is a small, fast store that keeps copies of data, so you do not have to fetch it from a slower place every time. Memory is limited, so a cache has a maximum size. Sooner or later it is full, and a new item arrives.
At that moment the cache must remove something. This is called eviction. The rule that picks which item to remove is called the eviction policy.
LRU is one such rule. LRU means least recently used. The cache remembers the order in which items were last touched. When it needs space, it removes the item that was touched longest ago.
Every eviction policy is really a guess about the future. The cache wants to remove the item that nobody will ask for again. It cannot know that, so it guesses. LRU guesses that the item idle for the longest time is the one least likely to come back.
An LRU cache supports two operations. get(key) returns a value, or a miss if the key is not there. put(key, value) stores a value. Both must be fast, because they run on every request.
To make both fast, an LRU cache uses two structures together. The first is a hash map, a table that finds any key in constant time. The second is a doubly linked list, a chain of entries where each entry points to the one before it and the one after it. The list holds the use order: newest at one end, oldest at the other.
Moving an entry in a doubly linked list only changes a few pointers. Finding the entry is one hash map lookup. So get and put both run in O(1) time, which means the cost does not grow with the size of the cache.
LRU cache is a common coding interview question. In the LeetCode version, problem 146, you build a class with get and put, and both must run in O(1) average time. The answer is the hash map plus linked list idea above.
In Python you do not need to write the list yourself. An OrderedDict is a dictionary that also remembers order. It has move_to_end, to mark a key as newest, and popitem(last=False), to remove the oldest key. That is an LRU cache in a few lines. The code below was run before it was added here.
lru_cache.py
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.items = OrderedDict() # oldest first, newest last
def get(self, key):
if key not in self.items:
return -1 # miss
self.items.move_to_end(key) # a hit makes it the newest
return self.items[key]
def put(self, key, value):
if key in self.items:
self.items.move_to_end(key)
self.items[key] = value
if len(self.items) > self.capacity:
self.items.popitem(last=False) # evict the least recently used
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the newest
cache.put("c", 3) # full: evicts "b", the least recently used
print(list(cache.items)) # ['a', 'c']
print(cache.get("b")) # -1Read the last lines carefully. The cache holds two items. Reading "a" makes it the newest, so when "c" arrives, "b" is the oldest and is evicted. In an interview, you may be asked to build the linked list by hand. The logic is the same: a hit moves the entry to the front, and eviction takes from the back.
If you only want to cache the results of a Python function, the standard library already has functools.lru_cache. In Java, LinkedHashMap can keep entries in access order, and its removeEldestEntry method lets you drop the oldest one.
LRU is not the only policy. The common ones are these:
The lesson replayed 200,000 requests over 5,000 keys through all four, at four cache sizes. The traffic followed a Zipf distribution. That means a few keys get most of the requests and a long tail of keys gets very few, which is how real traffic often looks.
LFU beat LRU at every size, by 6 to 15 points of hit rate. The hit rate is the share of requests the cache could answer. At 50 entries, LFU scored 49.3 percent and LRU 34.4. At 1,000 entries, LFU scored 81.1 and LRU 74.9. FIFO and random gave identical results at every size, both below LRU.
Why did LFU win? The popular keys in Zipf traffic are popular because they are asked for often, and frequency is exactly what LFU counts. LRU evicts a hot key as soon as enough other keys are touched after it. In a small cache, that happens quickly.
LFU has a weakness, and it is the reason LRU is still the common default. A plain LFU count remembers the past too well. A news story read 50,000 times yesterday has a huge count. A new story read twice this morning has a count of 2, so LFU evicts the new story. The popular thing is no longer popular, but the count does not know. Real LFU caches, such as Redis's allkeys-lfu, use a counter that decays over time to fix this.
LRU has no such memory. When the set of hot keys moves, LRU follows it at once. So use LRU when popularity changes quickly, for example with fresh news, trending items or session data. Consider LFU, or a policy with an LFU filter, when popularity stays stable for days.
A full scan is the other case people worry about. A nightly export or a crawler touches every key once. To LRU, every one of those keys now looks recently used, so the hot keys get pushed out. The common belief is that this destroys an LRU cache. The lesson measured it. Right after a scan, LRU's hit rate fell from its usual 53 percent to 42, and was back to normal within about four hundred requests. LFU showed no dip. The effect is real, but small. The simple fix is to keep batch jobs out of the shared cache.
The lesson's choosing rule starts with one number. Divide your cache size by your number of distinct keys. If the cache is large compared with the key space, the policy barely matters, so take the default.
Exact LRU has a hidden cost. Every hit moves an entry in the list. That is a write on the read path. With one thread this is cheap. With many threads, every read must take a lock on the shared list, and the lock becomes a bottleneck.
So almost nothing in production runs textbook LRU. Redis's allkeys-lru is approximate. It does not keep a list. When it must evict, it samples a few keys and removes the oldest of those. Memcached uses a segmented LRU. PostgreSQL's buffer cache uses a clock sweep, a cheap way to get close to LRU. The Linux page cache keeps two LRU lists, active and inactive. Caffeine, a Java cache library, uses W-TinyLFU: an LFU admission filter in front of LRU.
Admission is a different question from eviction. Eviction asks which old key to remove. Admission asks whether the new key deserves a place at all. A key that arrives once during a scan loses that test, so it cannot push out anything useful.
The lesson's strongest finding was not about LRU at all. Growing the cache from 50 to 1,000 entries raised the hit rate by 40.5 points. Switching from LRU to LFU raised it by 6 to 15. Memory is usually cheaper than a debate about eviction, and it helps more.
So check these first. Set a memory limit, because Redis by default rejects writes instead of evicting. Pick an allkeys policy, because the volatile policies only evict keys that have a TTL. Graph hit rate against cache size. Keep batch jobs out. Only then compare LRU and LFU.
Also remember that a TTL and an eviction policy do different jobs. A TTL limits how old a value can be. Eviction limits how much memory the cache uses. If your evictions far exceed your expirations, eviction is deciding how long items live, and tuning the TTL will change very little. The TTL lesson covers that side.
To find the right policy for your own traffic, log one hour of cache keys and replay them offline through each policy at several sizes. The Cache Eviction Policies lesson shows the full lab, the scan measured at three resolutions, and a decision chart. It is the best next step if you are choosing a policy for a real cache. For the wider family of rules, see cache eviction.
Redis
allkeys-lru and allkeys-lfu are both approximate: Redis samples a few keys at eviction time instead of keeping a list. The default policy, noeviction, rejects writes when memory is full.
Memcached
Uses a segmented LRU, with no option to choose another policy.
Caffeine (Java)
Uses W-TinyLFU: an LFU admission filter over LRU, so a key seen once cannot push out a popular one.
PostgreSQL
The shared buffer cache uses a clock sweep, which approximates LRU without moving entries on every hit.
Python functools.lru_cache
A decorator that caches a function's results and discards the least recently used ones once it reaches maxsize.
An LRU cache is a cache with a fixed size that, when full, removes the item that was used longest ago. LRU stands for least recently used. It keeps recently used data because it expects that data to be needed again soon.
Combine a hash map with a doubly linked list. The hash map finds a key in O(1). The list keeps use order. On every get or put, move the entry to the newest end. When the cache is over capacity, remove the entry at the oldest end and delete its key from the map. In Python, an OrderedDict with move_to_end and popitem(last=False) does both jobs.
The idea is simple. The hard part is doing get and put in constant time, which needs two structures working together and careful pointer updates in the linked list. Once you see why the list must be doubly linked, so an entry can be removed from the middle, the rest follows.
It depends on your traffic. On stable Zipf traffic, the lesson measured LFU 6 to 15 points ahead of LRU. When popularity shifts quickly, LRU adapts faster, and plain LFU can hold on to keys that are no longer popular. If the cache is large compared with the number of keys, the choice barely matters.
Checked against these on .
Cache Eviction
The process of removing entries from a cache when it's full. Common policies: LRU (least recently used), LFU (least frequently used), FIFO (first in, first out).
TTL
Time To Live: how long a cached entry, DNS record, or packet is valid before it expires and must be refreshed or discarded.
Read-Through Cache
A cache that loads missing data from the database by itself, through one loader function, so your code only ever asks the cache. What the loader does when the database fails decides whether an outage shows up as errors or as wrong answers.
Caching
Storing frequently accessed data in a faster storage layer so you don't have to fetch it from the original (slower) source every time.
CDN
A network of servers distributed globally that caches content close to users. Netflix uses CDNs to stream video from servers near you, not from one central location.
Cache-Aside
A caching pattern where the application checks the cache first; on a miss, it fetches from the database and populates the cache. Also called lazy loading.
This page explains the idea. The "Cache Eviction Policies" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 769 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Cache Eviction Policies lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.