? ??

目錄

淘汰策略方案（8種）

LRU和LFU策略的區別

使用建議

手搓LRU算法

方式一

方式二

---

????????大家好，我是jstart千語。今天和大家回來聊一下redis，這次要講的是它的淘汰策略。為什么需要淘汰策略呢，就是當redis里面的內存占滿后，存不下數據了，那么新加入的數據該如何處理呢？這種處理的方式不同，就稱為不同的數據淘汰策略。redis支持8種不同的淘汰策略。

淘汰策略方案（8種）

noeviction	默認策略，不淘汰，當內存滿時寫入會報錯（OOM）。適合讀多寫少的緩存場景
volatile-ttl	從設置了過期時間的 key 中，優先淘汰即將過期的。
allkey-random	隨機淘汰一個 key。適用于不關心數據使用頻率的場景。
volatile-random	從設置了過期時間的 key 中隨機淘汰一個。
allkeys-lru	（最近最少使用）從所有 key 中淘汰最少使用的（LRU：Least Recently Used）。
volatile-lru	（最近最少使用）從設置了過期時間的 key 中，淘汰最少使用的。
allkeys-lfu	（頻率）從所有 key 中淘汰最不常用的（LFU：Least Frequently Used）。
volatile-lfu	（頻率）從設置了過期時間的 key 中，淘汰最不常用的。

---

LRU和LFU策略的區別

LRU：最近最少使用，用當前時間減去最后一次訪問的時間，這個值越大越先被淘汰。

例如：key1是5秒前被訪問，key2是10秒前被訪問，那么就是key2優先被淘汰。

---

LFU：最少頻率使用，統計每個key的訪問頻率，值越小越先被淘汰。

例如：key1在5秒內被訪問了3次，key2在10秒內被訪問了5次。那么key2優先被淘汰。

---

---

使用建議

????????1、優先使用allkeys-lru策略。充分利用LRU算法的優勢，把最近最常訪問的數據留在緩存中。如果業務中有明顯的冷熱數據區分，建議使用該策略。

---

為什么這里不使用LFU呢？：

因為數據使用頻率可能是不固定的，在某一段時間內訪問頻率高，另外一段時間訪問頻率低，可能導致誤刪。具體還要看業務需求
?

????????2、如果業務中數據訪問頻率區別不大，沒有明顯的冷熱數據區分，建議使用allkeys-random，隨機選擇淘汰。

????????3、如果業務中有置頂需求，可以使用volatile-lru策略，同時置頂數據不設置過期時間，這些置頂的數據就一直不被刪除，會淘汰其他設置過期時間的數據。

????????4、如果業務中有短時高頻訪問的數據，可以使用allkeys-lfu或者volatile-lfu策略。

---

---

手搓LRU算法

方式一

利用Java的LinkedHashMap天然支持按訪問順序排序，通過重寫removeEldestEntry方法可實現LRU邏輯。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache(int capacity) {// 初始容量，負載因子，accessOrder=true表示按訪問順序排序super(capacity, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {// 當大小超過容量時移除最舊元素return size() > capacity;}
}

使用示例：

LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("a", "1");
cache.put("b", "2");
cache.get("a"); // 訪問"a"使其變為最近使用
cache.put("c", "3");
cache.put("d", "4"); // 插入"d"時，容量超限，淘汰最久未使用的"b"

?注意：非線程安全，需在單線程環境使用或通過Collections.synchronizedMap包裝。

---

方式二

手動實現（哈希表 + 雙向鏈表）。實現O(1)時間復雜度的get和put操作，需結合哈希表與雙向鏈表。

步驟：

1. 定義節點結構：包含前后指針及鍵值。
2. 維護雙向鏈表：頭部放最新訪問節點，尾部為待淘汰節點。
3. 哈希表映射：快速定位節點位置。

import java.util.HashMap;
import java.util.Map;public class ManualLRUCache<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 capacity;private final Map<K, Node<K, V>> cache = new HashMap<>();private Node<K, V> head; // 虛擬頭節點private Node<K, V> tail; // 虛擬尾節點public ManualLRUCache(int capacity) {this.capacity = capacity;head = new Node<>(null, null);tail = new Node<>(null, null);head.next = tail;tail.prev = head;}public V get(K key) {Node<K, V> node = cache.get(key);if (node == null) return null;moveToHead(node); // 訪問后移至頭部return node.value;}public void put(K key, V value) {Node<K, V> node = cache.get(key);if (node != null) {node.value = value;moveToHead(node);} else {node = new Node<>(key, value);cache.put(key, node);addToHead(node);if (cache.size() > capacity) {Node<K, V> removed = removeTail();cache.remove(removed.key);}}}private void moveToHead(Node<K, V> node) {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> res = tail.prev;removeNode(res);return res;}
}

線程安全優化：

• 使用ConcurrentHashMap替代HashMap。
• 對鏈表操作加鎖（如ReentrantLock或synchronized），但可能影響性能。
• 考慮讀寫鎖（ReadWriteLock），允許并發讀，寫時獨占。