聊聊快取淘汰演算法-LRU 實現原理

  • 2019 年 10 月 29 日
  • 筆記

前言

我們常用快取提升數據查詢速度，由於快取容量有限，當快取容量到達上限，就需要刪除部分數據挪出空間，這樣新數據才可以添加進來。快取數據不能隨機刪除，一般情況下我們需要根據某種演算法刪除快取數據。常用淘汰演算法有 LRU,LFU,FIFO,這篇文章我們聊聊 LRU 演算法。

LRU 簡介

LRU 是 Least Recently Used 的縮寫，這種演算法認為最近使用的數據是熱門數據，下一次很大概率將會再次被使用。而最近很少被使用的數據，很大概率下一次不再用到。當快取容量的滿時候，優先淘汰最近很少使用的數據。

假設現在快取內部數據如圖所示：

image.png

這裡我們將列表第一個節點稱為頭結點，最後一個節點為尾結點。

當調用快取獲取 key=1 的數據，LRU 演算法需要將 1 這個節點移動到頭結點，其餘節點不變，如圖所示。

image.png

然後我們插入一個 key=8 節點，此時快取容量到達上限，所以加入之前需要先刪除數據。由於每次查詢都會將數據移動到頭結點，未被查詢的數據就將會下沉到尾部節點，尾部的數據就可以認為是最少被訪問的數據，所以刪除尾結點的數據。

image.png

然後我們直接將數據添加到頭結點。

image.png

這裡總結一下 LRU 演算法具體步驟：

  • 新數據直接插入到列表頭部
  • 快取數據被命中，將數據移動到列表頭部
  • 快取已滿的時候，移除列表尾部數據。

LRU 演算法實現

上面例子中可以看到，LRU 演算法需要添加頭節點，刪除尾結點。而鏈表添加節點/刪除節點時間複雜度 O(1)，非常適合當做存儲快取數據容器。但是不能使用普通的單向鏈表，單向鏈表有幾點劣勢:

  1. 每次獲取任意節點數據，都需要從頭結點遍歷下去，這就導致獲取節點複雜度為 O(N)。
  2. 移動中間節點到頭結點，我們需要知道中間節點前一個節點的資訊，單向鏈表就不得不再次遍歷獲取資訊。

針對以上問題，可以結合其他數據結構解決。

使用散列表存儲節點，獲取節點的複雜度將會降低為 O(1)。節點移動問題可以在節點中再增加前驅指針，記錄上一個節點資訊，這樣鏈表就從單向鏈表變成了雙向鏈表。

綜上使用雙向鏈表加散列表結合體，數據結構如圖所示:

LRU.png

在雙向鏈表中特意增加兩個『哨兵』節點，不用來存儲任何數據。使用哨兵節點，增加/刪除節點的時候就可以不用考慮邊界節點不存在情況，簡化編程難度，降低程式碼複雜度。

LRU 演算法實現程式碼如下，為了簡化 key ，val 都認為 int 類型。

public class LRUCache {        Entry head, tail;      int capacity;      int size;      Map<Integer, Entry> cache;          public LRUCache(int capacity) {          this.capacity = capacity;          // 初始化鏈表          initLinkedList();          size = 0;          cache = new HashMap<>(capacity + 2);      }        /**       * 如果節點不存在，返回 -1.如果存在，將節點移動到頭結點，並返回節點的數據。       *       * @param key       * @return       */      public int get(int key) {          Entry node = cache.get(key);          if (node == null) {              return -1;          }          // 存在移動節點          moveToHead(node);          return node.value;      }        /**       * 將節點加入到頭結點，如果容量已滿，將會刪除尾結點       *       * @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) {          // 首先刪除原來節點的關係          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));        }  }

LRU 演算法分析

快取命中率是快取系統的非常重要指標，如果快取系統的快取命中率過低，將會導致查詢迴流到資料庫，導致資料庫的壓力升高。

結合以上分析 LRU 演算法優缺點。

LRU 演算法優勢在於演算法實現難度不大，對於對於熱點數據， LRU 效率會很好。

LRU 演算法劣勢在於對於偶發的批量操作，比如說批量查詢歷史數據，就有可能使快取中熱門數據被這些歷史數據替換，造成快取污染，導致快取命中率下降，減慢了正常數據查詢。

LRU 演算法改進方案

以下方案來源與 MySQL InnoDB LRU 改進演算法

將鏈表拆分成兩部分，分為熱數據區，與冷數據區，如圖所示。

LRUimmprove.png

改進之後演算法流程將會變成下面一樣:

  1. 訪問數據如果位於熱數據區，與之前 LRU 演算法一樣，移動到熱數據區的頭結點。
  2. 插入數據時，若快取已滿，淘汰尾結點的數據。然後將數據插入冷數據區的頭結點。
  3. 處於冷數據區的數據每次被訪問需要做如下判斷：
    • 若該數據已在快取中超過指定時間，比如說 1 s，則移動到熱數據區的頭結點。
    • 若該數據存在在時間小於指定的時間，則位置保持不變。

對於偶發的批量查詢，數據僅僅只會落入冷數據區，然後很快就會被淘汰出去。熱門數據區的數據將不會受到影響，這樣就解決了 LRU 演算法快取命中率下降的問題。

其他改進方法還有 LRU-K，2Q,LIRS 演算法，感興趣同學可以自行查閱。

歡迎關注我的公眾號：程式通事，獲得日常乾貨推送。如果您對我的專題內容感興趣，也可以關注我的部落格：studyidea.cn

其他平台.png

VirMach 便宜 VPS

QNews

QNews