Redis LRU vs Classic LRU: Differences, LFU Comparison, and How to Choose

LRU (Least Recently Used)

LRU evicts the entry that has not been accessed for the longest time. The algorithm assumes that items not used recently are unlikely to be needed soon.

Cache capacity 3. Insert A, B, C → [A,B,C]. Access A → order becomes [B,C,A]. Insert D (cache full) → evict B (least recently used) → [C,A,D].

Advantages

Simple logic, low implementation cost.

O(1) insert, delete, and lookup when implemented with a hash map plus a linked list.

Matches short‑term locality patterns where recently accessed data is likely to be accessed again.

Disadvantages

Bursty accesses can evict frequently used items (e.g., cache capacity 3, hot key A, burst D,E,F replaces A,B,C).

Ignores access frequency; a key accessed many times long ago may be evicted if it was not accessed recently.

Implementation options

Option 1: LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    public LRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true);
        this.maxCapacity = maxCapacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println(cache); // {1=A, 2=B, 3=C}
        cache.get(1); // access 1
        System.out.println(cache); // {2=B, 3=C, 1=A}
        cache.put(4, "D"); // evict 2
        System.out.println(cache); // {3=C, 1=A, 4=D}
    }
}

Option 2: Doubly linked list + hash map

public class LRUCache2<K, V> {
    static class Node<K, V> {
        K key; V value; Node<K, V> prev; Node<K, V> next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
    private final int maxCapacity;
    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head;
    private final Node<K, V> tail;
    public LRUCache2(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.map = new HashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail; tail.prev = head;
    }
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        removeNode(node);
        addToHead(node);
        return node.value;
    }
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            Node<K, V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            if (map.size() > maxCapacity) {
                Node<K, V> tailNode = removeTail();
                map.remove(tailNode.key);
            }
        } else {
            node.value = value;
            removeNode(node);
            addToHead(node);
        }
    }
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private Node<K, V> removeTail() {
        Node<K, V> tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
    public static void main(String[] args) {
        LRUCache2<Integer, String> cache = new LRUCache2<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println(cache.get(1)); // A, moves to head
        cache.put(4, "D"); // evicts 2
        System.out.println(cache.get(2)); // null (evicted)
    }
}

LFU (Least Frequently Used)

LFU evicts the entry with the lowest access frequency, which better reflects long‑term popularity.

Cache capacity 3, insert A(1), B(1), C(1). Access A twice → frequencies A=3, B=1, C=1. Insert D → evict B or C (lowest frequency). Final cache: A(3), C(1), D(1).

Advantages

Retains high‑frequency items even if they were not accessed recently.

More stable hit rate under bursty accesses because low‑frequency burst keys do not evict hot keys.

Disadvantages

Implementation is more complex (typically O(log n) operations).

Cold‑start problem: new keys start with low frequency and may be evicted early.

Frequency aging: old hot keys may linger if not decayed.

Implementation (hash map + priority queue)

public class LFUCache<K, V> {
    static class Node<K, V> {
        K key; V value; int freq; long lastUseTime;
        Node(K k, V v) { key=k; value=v; freq=1; lastUseTime=System.currentTimeMillis(); }
    }
    private final int maxCapacity;
    private final Map<K, Node<K, V>> cache;
    private final Map<Integer, LinkedHashSet<K>> freqMap;
    private int minFreq;
    public LFUCache(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.cache = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.minFreq = 1;
    }
    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) return null;
        updateNodeFreq(node);
        return node.value;
    }
    public void put(K key, V value) {
        if (maxCapacity <= 0) return;
        Node<K, V> node = cache.get(key);
        if (node != null) {
            node.value = value;
            node.lastUseTime = System.currentTimeMillis();
            updateNodeFreq(node);
        } else {
            if (cache.size() >= maxCapacity) evictMinFreqKey();
            Node<K, V> newNode = new Node<>(key, value);
            cache.put(key, newNode);
            freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }
    }
    private void updateNodeFreq(Node<K, V> node) {
        int oldFreq = node.freq;
        int newFreq = oldFreq + 1;
        LinkedHashSet<K> oldSet = freqMap.get(oldFreq);
        oldSet.remove(node.key);
        if (oldFreq == minFreq && oldSet.isEmpty()) minFreq = newFreq;
        freqMap.computeIfAbsent(newFreq, k -> new LinkedHashSet<>()).add(node.key);
        node.freq = newFreq;
        node.lastUseTime = System.currentTimeMillis();
    }
    private void evictMinFreqKey() {
        LinkedHashSet<K> minSet = freqMap.get(minFreq);
        K evictKey = minSet.iterator().next();
        minSet.remove(evictKey);
        if (minSet.isEmpty()) freqMap.remove(minFreq);
        cache.remove(evictKey);
        System.out.println("Evicted key: " + evictKey);
    }
    public static void main(String[] args) {
        LFUCache<Integer, String> cache = new LFUCache<>(3);
        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        System.out.println(cache.get(1)); // A, freq becomes 2
        cache.put(4, "D"); // evicts key 2 (freq 1)
        System.out.println(cache.get(2)); // null
    }
}

Redis LRU implementation

Redis uses an approximate LRU for performance. Each key stores an lru timestamp. When eviction is required, Redis randomly samples N keys (default 5, configurable via maxmemory-samples) and removes the sampled key with the smallest timestamp.

maxmemory-policy allkeys-lru
maxmemory-policy volatile-lru
maxmemory-samples 5

Redis LFU implementation

Introduced in Redis 4.0, LFU adds a frequency counter ( lfu_count) with logarithmic growth and a decay mechanism ( lfu_decay_time) measured in minutes.

Frequency increments slowly as access count grows, preventing the counter from exploding.

When a key is idle longer than lfu_decay_time, its lfu_count decays, allowing stale hot keys to be evicted.

Eviction also uses random sampling; the key with the smallest lfu_count is removed, ties broken by LRU.

maxmemory-policy allkeys-lfu
maxmemory-policy volatile-lfu
lfu-decay-time 1
lfu-log-factor 10

Key differences between Redis LRU and LFU

Decision metric: last access time vs. access frequency (with decay).

Typical scenarios: short‑term locality for LRU; long‑term hot data for LFU.

Burst traffic handling: LRU can evict hot keys during spikes; LFU resists such bursts.

Cold‑start friendliness: LRU works out‑of‑the‑box; LFU may need lfu-log-factor tuning to protect new keys.

Memory overhead: LRU stores only a timestamp; LFU stores frequency and decay info, slightly higher overhead.

Choosing a policy

Choose LRU when cache access exhibits short‑term concentration, such as session data or temporary activity pages. Choose LFU for data that stays hot over long periods, like product catalogs, region codes, or homepage banners. After switching, monitor INFO stats (keyspace_hits / keyspace_misses) to verify improvement.