不吹不黑，這個算法，你肯定不會
01、前言
我們常用緩存提升數(shù)據(jù)查詢速度，由于緩存容量有限，當緩存容量到達上限，就需要刪除部分數(shù)據(jù)挪出空間，這樣新數(shù)據(jù)才可以添加進來。緩存數(shù)據(jù)不能隨機刪除，一般情況下我們需要根據(jù)某種算法刪除緩存數(shù)據(jù)。常用淘汰算法有 LRU,LFU,FIFO,這篇文章我們聊聊 LRU 算法。
02、LRU 簡介
LRU 是 Least Recently Used 的縮寫，這種算法認為最近使用的數(shù)據(jù)是熱門數(shù)據(jù)，下一次很大概率將會再次被使用。而最近很少被使用的數(shù)據(jù)，很大概率下一次不再用到。當緩存容量滿的時候，優(yōu)先淘汰最近很少使用的數(shù)據(jù)。
假設現(xiàn)在緩存內部數(shù)據(jù)如圖所示：
這里我們將列表第一個節(jié)點稱為頭結點，最后一個節(jié)點為尾結點。
當調用緩存獲取 key=1 的數(shù)據(jù)，LRU 算法需要將 1 這個節(jié)點移動到頭結點，其余節(jié)點不變，如圖所示。
然后我們插入一個 key=8 節(jié)點，此時緩存容量到達上限，所以加入之前需要先刪除數(shù)據(jù)。由于每次查詢都會將數(shù)據(jù)移動到頭結點，未被查詢的數(shù)據(jù)就將會下沉到尾部節(jié)點，尾部的數(shù)據(jù)就可以認為是最少被訪問的數(shù)據(jù)，所以刪除尾結點的數(shù)據(jù)。
然后我們直接將數(shù)據(jù)添加到頭結點。
這里總結一下 LRU 算法具體步驟：
- 新數(shù)據(jù)直接插入到列表頭部
- 緩存數(shù)據(jù)被命中，將數(shù)據(jù)移動到列表頭部
- 緩存已滿的時候，移除列表尾部數(shù)據(jù)。
03、LRU 算法實現(xiàn)
上面例子中可以看到，LRU 算法需要添加頭節(jié)點，刪除尾結點。而鏈表添加節(jié)點/刪除節(jié)點時間復雜度 O(1)，非常適合當做存儲緩存數(shù)據(jù)容器。但是不能使用普通的單向鏈表，單向鏈表有幾點劣勢:
- 每次獲取任意節(jié)點數(shù)據(jù)，都需要從頭結點遍歷下去，這就導致獲取節(jié)點復雜度為 O(N)。
- 移動中間節(jié)點到頭結點，我們需要知道中間節(jié)點前一個節(jié)點的信息，單向鏈表就不得不再次遍歷獲取信息。
針對以上問題，可以結合其他數(shù)據(jù)結構解決。
使用散列表存儲節(jié)點，獲取節(jié)點的復雜度將會降低為 O(1)。節(jié)點移動問題可以在節(jié)點中再增加前驅指針，記錄上一個節(jié)點信息，這樣鏈表就從單向鏈表變成了雙向鏈表。
綜上使用雙向鏈表加散列表結合體，數(shù)據(jù)結構如圖所示:
在雙向鏈表中特意增加兩個『哨兵』節(jié)點，不用來存儲任何數(shù)據(jù)。使用哨兵節(jié)點，增加/刪除節(jié)點的時候就可以不用考慮邊界節(jié)點不存在情況，簡化編程難度，降低代碼復雜度。
LRU 算法實現(xiàn)代碼如下，為了簡化 key ，val 都認為 int 類型。
- public class LRUCache {
- Entry head, tail;
- int capacity;
- int size;
- Map cache;
- public LRUCache(int capacity) {
- this.capacity = capacity;
- // 初始化鏈表
- initLinkedList();
- size = 0;
- cache = new HashMap<>(capacity + 2);
- }
- /**
- * 如果節(jié)點不存在，返回 -1.如果存在，將節(jié)點移動到頭結點，并返回節(jié)點的數(shù)據(jù)。
- *
- * @param key
- * @return
- */
- public int get(int key) {
- Entry node = cache.get(key);
- if (node == null) {
- return -1;
- }
- // 存在移動節(jié)點
- moveToHead(node);
- return node.value;
- }
- /**
- * 將節(jié)點加入到頭結點，如果容量已滿，將會刪除尾結點
- *
- * @param key
- * @param value
- */
- public void put(int key, int value) {
- Entry node = cache.get(key);
- if (node != null) {
- node.value = value;
- moveToHead(node);
- return;
- }
- // 不存在。先加進去，再移除尾結點
- // 此時容量已滿 刪除尾結點
- if (size == capacity) {
- Entry lastNode = tail.pre;
- deleteNode(lastNode);
- cache.remove(lastNode.key);
- size--;
- }
- // 加入頭結點
- Entry newNode = new Entry();
- newNode.key = key;
- newNode.value = value;
- addNode(newNode);
- cache.put(key, newNode);
- size++;
- }
- private void moveToHead(Entry node) {
- // 首先刪除原來節(jié)點的關系
- deleteNode(node);
- addNode(node);
- }
- private void addNode(Entry node) {
- head.next.pre = node;
- node.next = head.next;
- node.pre = head;
- head.next = node;
- }
- private void deleteNode(Entry node) {
- node.pre.next = node.next;
- node.next.pre = node.pre;
- }
- public static class Entry {
- public Entry pre;
- public Entry next;
- public int key;
- public int value;
- public Entry(int key, int value) {
- this.key = key;
- this.value = value;
- }
- public Entry() {
- }
- }
- private void initLinkedList() {
- head = new Entry();
- tail = new Entry();
- head.next = tail;
- tail.pre = head;
- }
- public static void main(String[] args) {
- LRUCache cache = new LRUCache(2);
- cache.put(1, 1);
- cache.put(2, 2);
- System.out.println(cache.get(1));
- cache.put(3, 3);
- System.out.println(cache.get(2));
- }
- }
04、LRU 算法分析
緩存命中率是緩存系統(tǒng)的非常重要指標，如果緩存系統(tǒng)的緩存命中率過低，將會導致查詢回流到數(shù)據(jù)庫，導致數(shù)據(jù)庫的壓力升高。
結合以上分析 LRU 算法優(yōu)缺點。
LRU 算法優(yōu)勢在于算法實現(xiàn)難度不大，對于對于熱點數(shù)據(jù)， LRU 效率會很好。
LRU 算法劣勢在于對于偶發(fā)的批量操作，比如說批量查詢歷史數(shù)據(jù)，就有可能使緩存中熱門數(shù)據(jù)被這些歷史數(shù)據(jù)替換，造成緩存污染，導致緩存命中率下降，減慢了正常數(shù)據(jù)查詢。
05、LRU 算法改進方案
以下方案來源于 MySQL InnoDB LRU 改進算法
將鏈表拆分成兩部分，分為熱數(shù)據(jù)區(qū)，與冷數(shù)據(jù)區(qū)，如圖所示。
改進之后算法流程將會變成下面一樣:
- 訪問數(shù)據(jù)如果位于熱數(shù)據(jù)區(qū)，與之前 LRU 算法一樣，移動到熱數(shù)據(jù)區(qū)的頭結點。
- 插入數(shù)據(jù)時，若緩存已滿，淘汰尾結點的數(shù)據(jù)。然后將數(shù)據(jù)插入冷數(shù)據(jù)區(qū)的頭結點。
- 處于冷數(shù)據(jù)區(qū)的數(shù)據(jù)每次被訪問需要做如下判斷：
- 若該數(shù)據(jù)已在緩存中超過指定時間，比如說 1 s，則移動到熱數(shù)據(jù)區(qū)的頭結點。
- 若該數(shù)據(jù)存在在時間小于指定的時間，則位置保持不變。
對于偶發(fā)的批量查詢，數(shù)據(jù)僅僅只會落入冷數(shù)據(jù)區(qū)，然后很快就會被淘汰出去。熱門數(shù)據(jù)區(qū)的數(shù)據(jù)將不會受到影響，這樣就解決了 LRU 算法緩存命中率下降的問題。
其他改進方法還有 LRU-K，2Q,LIRS 算法，感興趣同學可以自行查閱。
