Cache Eviction Beyond LRU: FIFO, Clock, Random and MRU in C++ with a Trace Simulator
Key takeaways
Which entry to throw out when a cache is full depends on the access pattern, not on which policy is most famous. This article implements FIFO, LRU, Clock, Random and MRU as small C++ classes, replays the same four traces through all of them, and explains the results: Bélády's anomaly, the loop that gives LRU zero hits, scan pollution, and where LFU and modern policies fit.
A fixed-size cache that is full needs a rule for which entry to throw out when a new one arrives. That rule is the replacement or eviction policy. Everyone learns LRU first, and LRU is a good default, but it has well-known blind spots. The quickest way to see them is to run several policies against the same access patterns and count hits.
This article implements five policies as small C++17 classes with the same interface, replays four traces through them, and uses the results to explain when each policy wins or loses. All numbers below come from running the code in this article (g++ 10.3, -O2). None of them are benchmarks of real systems.
The policies in one paragraph each
- FIFO evicts the entry that was inserted first. A hit doesn’t change anything. Cheap, and ignores how useful an entry is.
- LRU evicts the entry that was used least recently. Every hit moves the entry to the front of a list.
- Clock (second chance) approximates LRU with one bit per entry. A hit sets the bit. On eviction, a “hand” sweeps around a ring, clearing set bits and evicting the first entry whose bit is already clear.
- Random evicts a random entry. It needs no ordering metadata at all.
- MRU evicts the most recently used entry. It sounds backwards, and for most workloads it is, but it has one real use.
Two more come up in any discussion. LFU evicts the least frequently used entry, and OPT (Bélády’s MIN) evicts the entry whose next use is furthest in the future. OPT needs to know the future, so it’s only a yardstick for offline analysis.
Implementations
All caches share get(key) -> std::optional<V> and put(key, value), and all reject a capacity of zero. (An LRU cache with capacity 0 that calls list.back() on an empty list is undefined behavior, and it’s a common bug in interview-style implementations.)
FIFO
#include <cstddef>
#include <optional>
#include <queue>
#include <stdexcept>
#include <unordered_map>
#include <utility>
template <typename K, typename V>
class FIFOCache {
public:
explicit FIFOCache(std::size_t capacity) : capacity_(capacity) {
if (capacity_ == 0) throw std::invalid_argument("capacity must be > 0");
}
std::optional<V> get(const K& key) const {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
return it->second; // a hit does not change the order
}
void put(const K& key, V value) {
if (auto it = map_.find(key); it != map_.end()) {
it->second = std::move(value);
return;
}
if (map_.size() == capacity_) {
map_.erase(order_.front());
order_.pop();
}
order_.push(key);
map_.emplace(key, std::move(value));
}
private:
std::size_t capacity_;
std::queue<K> order_;
std::unordered_map<K, V> map_;
};This version has no erase(key), so the queue and the map always hold the same keys. If you add explicit removal, the queue will contain stale keys and eviction must skip keys that are no longer in the map.
LRU
#include <list>
template <typename K, typename V>
class LRUCache {
public:
explicit LRUCache(std::size_t capacity) : capacity_(capacity) {
if (capacity_ == 0) throw std::invalid_argument("capacity must be > 0");
}
std::optional<V> get(const K& key) {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
items_.splice(items_.begin(), items_, it->second); // move to front, O(1)
return it->second->second;
}
void put(const K& key, V value) {
if (auto it = map_.find(key); it != map_.end()) {
it->second->second = std::move(value);
items_.splice(items_.begin(), items_, it->second);
return;
}
if (map_.size() == capacity_) {
map_.erase(items_.back().first);
items_.pop_back();
}
items_.emplace_front(key, std::move(value));
map_.emplace(key, items_.begin());
}
private:
using List = std::list<std::pair<K, V>>;
std::size_t capacity_;
List items_; // front = most recent
std::unordered_map<K, typename List::iterator> map_;
};The list keeps recency order and the map points into it. splice relinks a node without copying it, and std::list iterators stay valid across splice, so the map never needs fixing up. The price: every entry carries two list pointers plus a heap allocation, and every read modifies shared structure. That second point is what makes LRU awkward under concurrency, because even get needs a write lock.
MRU is this same class with the eviction lines changed to remove items_.front() instead of items_.back().
Clock
#include <vector>
template <typename K, typename V>
class ClockCache {
public:
explicit ClockCache(std::size_t capacity) : capacity_(capacity) {
if (capacity_ == 0) throw std::invalid_argument("capacity must be > 0");
slots_.reserve(capacity_);
}
std::optional<V> get(const K& key) {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
slots_[it->second].referenced = true; // a hit only sets a bit
return slots_[it->second].value;
}
void put(const K& key, V value) {
if (auto it = map_.find(key); it != map_.end()) {
slots_[it->second].value = std::move(value);
slots_[it->second].referenced = true;
return;
}
if (slots_.size() < capacity_) {
map_.emplace(key, slots_.size());
slots_.push_back({key, std::move(value), false});
return;
}
// Sweep: clear reference bits until we find an entry without one.
while (slots_[hand_].referenced) {
slots_[hand_].referenced = false;
hand_ = (hand_ + 1) % capacity_;
}
map_.erase(slots_[hand_].key);
slots_[hand_] = {key, std::move(value), false};
map_.emplace(key, hand_);
hand_ = (hand_ + 1) % capacity_;
}
private:
struct Slot { K key; V value; bool referenced; };
std::size_t capacity_;
std::size_t hand_ = 0;
std::vector<Slot> slots_;
std::unordered_map<K, std::size_t> map_;
};A hit is a single store to a bit. That’s why Clock-style algorithms show up wherever hits must be cheap: OS page replacement, where hardware sets an “accessed” bit in the page table, and database buffer pools, such as PostgreSQL’s clock-sweep. The sweep can visit every slot in the worst case, but each visit clears a bit, so the amortized cost stays low.
One design decision here matters more than it looks: new entries start with the bit clear. An entry has to be hit at least once after insertion to earn its second chance. I first wrote this with the bit set on insert (as many textbook versions do) and got a surprise on the smallest test: put 1, 2, 3, get(1), put 4. With every bit set, the hand clears all three, comes back around and evicts 1, the only key that had actually been used. With the bit clear on insert, the same sequence evicts 2, as you’d expect:
LRU after get(1), put(4): 2 is evicted
Clock after get(1), put(4): 1 present, 2 evicted, 3 presentStarting with the bit clear is also what makes Clock resist scans, as the traces below show.
Random
#include <random>
template <typename K, typename V>
class RandomCache {
public:
explicit RandomCache(std::size_t capacity, unsigned seed = 1) : capacity_(capacity), rng_(seed) {
if (capacity_ == 0) throw std::invalid_argument("capacity must be > 0");
}
std::optional<V> get(const K& key) const {
auto it = map_.find(key);
if (it == map_.end()) return std::nullopt;
return entries_[it->second].second;
}
void put(const K& key, V value) {
if (auto it = map_.find(key); it != map_.end()) {
entries_[it->second].second = std::move(value);
return;
}
if (entries_.size() == capacity_) {
std::uniform_int_distribution<std::size_t> pick(0, entries_.size() - 1);
std::size_t victim = pick(rng_);
map_.erase(entries_[victim].first);
if (victim != entries_.size() - 1) { // swap-and-pop keeps it O(1)
entries_[victim] = std::move(entries_.back());
map_[entries_[victim].first] = victim;
}
entries_.pop_back();
}
map_.emplace(key, entries_.size());
entries_.emplace_back(key, std::move(value));
}
private:
std::size_t capacity_;
std::mt19937 rng_;
std::vector<std::pair<K, V>> entries_;
std::unordered_map<K, std::size_t> map_;
};Picking a random key needs the keys in an indexable array. An unordered_map can’t give you its k-th element in O(1). The swap-and-pop keeps the array dense. get is const and touches nothing, which is Random’s big practical advantage: reads need no write lock.
The test harness
Each trace is a list of keys. A lookup that hits counts as a hit. A miss inserts the key.
template <class Cache>
int countHits(Cache cache, const std::vector<int>& trace) {
int hits = 0;
for (int key : trace) {
if (cache.get(key)) ++hits;
else cache.put(key, key);
}
return hits;
}Trace 1: Bélády’s anomaly
The textbook sequence 1 2 3 4 1 2 5 1 2 3 4 5, run with 3 and 4 slots:
FIFO cap=3 hits= 3/12 (25.0%)
LRU cap=3 hits= 2/12 (16.7%)
FIFO cap=4 hits= 2/12 (16.7%)
LRU cap=4 hits= 4/12 (33.3%)With FIFO, the larger cache gets fewer hits: 3 hits (9 misses) with 3 slots, 2 hits (10 misses) with 4. That’s Bélády’s anomaly. It happens because FIFO’s contents at size 4 are not guaranteed to be a superset of its contents at size 3. LRU is a stack algorithm: the k most recently used keys are always a subset of the k+1 most recently used keys. So more capacity can never cost LRU a hit, as the 2 → 4 hits here show. On this particular short trace, FIFO beats LRU at size 3. That’s a reminder that small hand-picked traces prove very little in either direction.
Trace 2: a loop one entry larger than the cache
Five passes over keys 0..100 (101 keys) with a 100-entry cache:
LRU cap=100 hits= 0/505 (0.0%)
FIFO cap=100 hits= 0/505 (0.0%)
Clock cap=100 hits= 0/505 (0.0%)
Random cap=100 hits= 394/505 (78.0%)
MRU cap=100 hits= 400/505 (79.2%)This is LRU’s worst case, and it’s worth understanding because it shows up in real code. When key 100 arrives, LRU evicts key 0, which is exactly the next key requested. Every access evicts the key that is needed next, so the hit count stays at zero no matter how many passes run. FIFO and Clock (all bits get cleared by the sweep) degrade the same way.
MRU does the opposite. It keeps the older part of the pass and sacrifices the newest entry, so on each pass all but one key are still there. Random does almost as well without knowing anything about the pattern, because it doesn’t systematically evict the one key that is needed next.
This is the pattern of a nested-loop join, or a job that repeatedly re-reads a file slightly bigger than its buffer. The failure mode I watch for in practice: a cache sized just below the working set of a periodic job. Hit rates look fine in tests with smaller data, then drop off a cliff (not gradually) once the data grows past the cache. Growing the cache by a few percent fixes it completely. So does a policy that isn’t pure recency.
Trace 3: a hot set polluted by scans
Each round touches 50 hot keys twice, then scans 80 keys that are never seen again. 20 rounds, cache of 100:
LRU cap=100 hits=1000/3600 (27.8%)
FIFO cap=100 hits=1000/3600 (27.8%)
Clock cap=100 hits=1500/3600 (41.7%)
Random cap=100 hits=1191/3600 (33.1%)
MRU cap=100 hits=1608/3600 (44.7%)For LRU, the 80 scan keys are the most recent, so by the next round they have pushed 30 of the 50 hot keys out. The misses on those keys then evict the remaining 20 just before they are requested, which is the loop effect from trace 2 again. So LRU gets only the hits from the second touch in each round. Clock does better because the hot keys have their reference bit set by the second touch, while scan keys enter with a clear bit and are evicted first. That’s the payoff of the “start with the bit clear” choice above. MRU wins this synthetic trace because it evicts the scan keys as they arrive, but the next trace shows what it costs on normal traffic.
Scan pollution is the common real-world version of this: a nightly export, a cache warm-up, or a crawler walking every product page once. For an hour, it replaces the entries that daytime traffic needs, and latency spikes afterwards while the cache refills. Policies built for this, such as 2Q, LRU-K, ARC (used by ZFS) and the W-TinyLFU admission policy in the Java Caffeine library, keep new entries on probation until they are seen a second time. Linux page reclaim has long used separate active and inactive lists for the same reason, and newer kernels (6.1+) offer the multi-generational LRU.
Trace 4: skewed popularity
20,000 requests over 1,000 keys with Zipf-like popularity (key k has weight 1/k), cache of 100. This is closer to what most application caches actually see:
LRU cap=100 hits=11437/20000 (57.2%)
FIFO cap=100 hits=10362/20000 (51.8%)
Clock cap=100 hits=11718/20000 (58.6%)
Random cap=100 hits=10343/20000 (51.7%)
MRU cap=100 hits=2765/20000 (13.8%)Now recency pays off, and MRU collapses. LRU and Clock are close, and on this trace Clock is slightly ahead. FIFO and Random trail by about 5–7 points. Whether that gap matters depends on how expensive a miss is. If a miss is a 50 ms database query, 5 points of hit rate is a lot. If a miss is a cheap recomputation, the simpler policy with lock-free reads may be the better trade.
Taken together, the four traces make the point that there is no universally best policy, only a best policy for a trace. Replaying a sample of real production keys through candidate policies, with a harness like the one above, is cheap and more convincing than any rule of thumb.
Where LFU fits
LFU evicts the key with the fewest accesses. It protects a stable popular set well, including against scans, since a one-off key has a count of 1. Its weakness is history. A key that was hot yesterday keeps its large count and can squat in the cache long after demand has moved on. Practical LFU implementations therefore age counts. Redis’s LFU mode keeps a small logarithmic counter per key and decays it over time (lfu-decay-time). TinyLFU halves all counters periodically.
An exact O(1) LFU needs a map from frequency to a list of keys plus a pointer to the minimum frequency, the structure from LeetCode 460. It’s noticeably more code than LRU, which is one reason approximations dominate in practice.
What real systems do
- Redis doesn’t keep an LRU list. When it needs memory, it samples a few keys (
maxmemory-samples, default 5) and evicts the best candidate by idle time or LFU counter. Note that the defaultmaxmemory-policyisnoeviction, which means writes fail when memory is full. You have to chooseallkeys-lru,allkeys-lfuor another policy explicitly. - CPU caches work on small sets (for example 8–16 ways) and use cheap approximations such as tree pseudo-LRU, plus adaptive insertion policies on recent designs, because exact LRU bookkeeping in hardware at every access is too expensive.
- OS page caches and database buffer pools favor Clock variants, because the “hit” path must be as cheap as possible.
The shared lesson is that production systems rarely run the textbook algorithm. They pick an approximation that is cheap on the hit path and captures the part of the access pattern that matters.
Concurrency
A single mutex around an LRU cache serializes every read, since get modifies the list. The usual first fix is sharding by key hash:
#include <array>
#include <functional>
#include <memory>
#include <mutex>
#include <string>
class ShardedLRU {
public:
explicit ShardedLRU(std::size_t totalCapacity) {
for (auto& s : shards_) s = std::make_unique<Shard>(totalCapacity / kShards + 1);
}
std::optional<std::string> get(int key) {
Shard& s = shardFor(key);
std::lock_guard lock(s.mutex);
return s.cache.get(key);
}
void put(int key, std::string value) {
Shard& s = shardFor(key);
std::lock_guard lock(s.mutex);
s.cache.put(key, std::move(value));
}
private:
static constexpr std::size_t kShards = 16;
struct Shard {
explicit Shard(std::size_t cap) : cache(cap) {}
std::mutex mutex;
LRUCache<int, std::string> cache;
};
Shard& shardFor(int key) { return *shards_[std::hash<int>{}(key) % kShards]; }
std::array<std::unique_ptr<Shard>, kShards> shards_;
};(std::mutex can’t be copied or moved, so each shard is allocated separately instead of stored in a std::vector constructed by copying.) Sharding turns one global LRU into 16 independent ones. A hot key can’t use more than its shard’s capacity, and the eviction order is only approximately global. It’s usually a good trade, but it’s a behavior change, not only a performance change.
Keep in mind that std::hash<int> is the identity function in libstdc++ and libc++ (MSVC mixes the bits), so with sequential integer keys key % 16 is fine, but keys that share low bits (IDs that are all multiples of 16, for example) all land in one shard. Mixing the hash before taking the modulus avoids that.