漫畫：LRU從實現到應用層層剖析（第一講）

• 2020 年 3 月 30 日
• 筆記

今天為大家分享很出名的LRU演算法，第一講共包括4節。

• LRU概述
• LRU使用
• LRU實現
• Redis近LRU概述

01 PART

LRU 概述

LRU是Least Recently Used的縮寫，譯為最近最少使用。它的理論基礎為「最近使用的數據會在未來一段時期內仍然被使用，已經很久沒有使用的數據大概率在未來很長一段時間仍然不會被使用」由於該思想非常契合業務場景 ，並且可以解決很多實際開發中的問題，所以我們經常通過LRU的思想來作快取，一般也將其稱為LRU快取機制。因為恰好leetcode上有這道題，所以我乾脆把題目貼這裡。但是對於LRU而言，希望大家不要局限於本題（大家不用擔心學不會，我希望能做一個全網最簡單的版本，希望可以堅持看下去！）下面，我們一起學習一下。

第146題：運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 快取機制。它應該支援以下操作：獲取數據 get 和 寫入數據 put 。

獲取數據 get(key) – 如果密鑰 (key) 存在於快取中，則獲取密鑰的值（總是正數），否則返回 -1。

寫入數據 put(key, value) – 如果密鑰不存在，則寫入其數據值。當快取容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。

進階:你是否可以在 O(1) 時間複雜度內完成這兩種操作？

示例:

LRUCache cache = new LRUCache( 2 /* 快取容量 */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 該操作會使得密鑰 2 作廢

cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 該操作會使得密鑰 1 作廢

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

02 PART

LRU 使用（解釋）

由於我實在擔心部分同學完全懵逼零基礎，所以我把上面的LRUCache的示例解釋一下。

第一步：我們申明一個LRUCache，長度為2

第二步：我們分別向cache裡邊put(1,1)和put(2,2)，這裡因為最近使用的是2（put也算作使用）所以2在前，1在後。

第三步：我們get(1)，也就是我們使用了1，所以需要將1移到前面。

第四步：此時我們put(3,3)，因為2是最近最少使用的，所以我們需要將2進行作廢。此時我們再get(2)，就會返回-1。

第五步：我們繼續put(4,4)，同理我們將1作廢。此時如果get(1)，也是返回-1。

第六步：此時我們get(3)，實際為調整3的位置。

第七步：同理，get(4)，繼續調整4的位置。

03 PART

LRU 實現（層層剖析）

上面的圖搞了我半小時，基本不是弱智的話，應該都能理解LRU的使用了。現在我們聊一下實現。LRU一般來講，我們是使用雙向鏈表實現。基本上在面試的時候，能寫出來雙向鏈表的實現，已經可以打9分了。但是這裡我要強調的是，其實在項目中，並不絕對是這樣。比如Redis源碼里，LRU的淘汰策略，就沒有使用雙向鏈表，而是使用一種模擬鏈表的方式。因為Redis大多是當記憶體在用（我知道可以持久化），如果再在記憶體中去維護一個鏈表，就平添了一些複雜性，同時也會多耗掉一些記憶體，後面我會單獨拉出來Redis的源碼給大家分析，這裡不細說。

回到題目，為什麼我們要選擇雙向鏈表來實現呢？看看上面的使用步驟圖，大家會發現，在整個LRUCache的使用中，我們需要頻繁的去調整首尾元素的位置。而雙向鏈表的結構，剛好滿足這一點（再啰嗦一下，前幾天我剛好看了groupcache的源碼，裡邊就是用雙向鏈表來做的LRU，當然它裡邊做了一些改進。groupcache是memcache作者實現的go版本，如果有go的讀者，可以去看看源碼，還是有一些收穫。）

下面，我們採用hashmap+雙向鏈表的方式進行實現。

首先，我們定義一個LinkNode，用以存儲元素。因為是雙向鏈表，自然我們要定義pre和next。同時，我們需要存儲下元素的key和value。val大家應該都能理解，關鍵是為什麼需要存儲key？舉個例子，比如當整個cache的元素滿了，此時我們需要刪除map中的數據，需要通過LinkNode中的key來進行查詢，否則無法獲取到key。

type LinkNode struct {      key, val  int      pre, next *LinkNode  }  

現在有了LinkNode，自然需要一個Cache來存儲所有的Node。我們定義cap為cache的長度，m用來存儲元素。head和tail作為Cache的首尾。

type LRUCache struct {      m          map[int]*LinkNode      cap        int      head, tail *LinkNode  }  

接下來我們對整個Cache進行初始化。在初始化head和tail的時候將它們連接在一起。

func Constructor(capacity int) LRUCache {      head := &LinkNode{0, 0, nil, nil}      tail := &LinkNode{0, 0, nil, nil}      head.next = tail      tail.pre = head      return LRUCache{make(map[int]*LinkNode), capacity, head, tail}  }  

大概是這樣：

現在我們已經完成了Cache的構造，剩下的就是添加它的API了。因為Get比較簡單，我們先完成Get方法。這裡分兩種情況考慮，如果沒有找到元素，我們返回-1。如果元素存在，我們需要把這個元素移動到首位置上去。

func (this *LRUCache) Get(key int) int {      head := this.head      cache := this.m      if v, exist := cache[key]; exist {          v.pre.next = v.next          v.next.pre = v.pre          v.next = head.next          head.next.pre = v          v.pre = head          head.next = v          return v.val      } else {          return -1      }  }  

大概就是下面這個樣子（假若2是我們get的元素）

我們很容易想到這個方法後面還會用到，所以將其抽出。

func (this *LRUCache) moveToHead(node *LinkNode){          head := this.head          //從當前位置刪除          node.pre.next = node.next          node.next.pre = node.pre          //移動到首位置          node.next = head.next          head.next.pre = node          node.pre = head          head.next = node  }    func (this *LRUCache) Get(key int) int {      cache := this.m      if v, exist := cache[key]; exist {          this.moveToHead(v)          return v.val      } else {          return -1      }  }  

現在我們開始完成Put。實現Put時，有兩種情況需要考慮。假若元素存在，其實相當於做一個Get操作，也是移動到最前面（但是需要注意的是，這裡多了一個更新值的步驟）。

func (this *LRUCache) Put(key int, value int) {      head := this.head      tail := this.tail      cache := this.m      //假若元素存在      if v, exist := cache[key]; exist {          //1.更新值          v.val = value          //2.移動到最前          this.moveToHead(v)      } else {          //TODO      }  }  

假若元素不存在，我們將其插入到元素首，並把該元素值放入到map中。

func (this *LRUCache) Put(key int, value int) {      head := this.head      tail := this.tail      cache := this.m      //存在      if v, exist := cache[key]; exist {          //1.更新值          v.val = value          //2.移動到最前          this.moveToHead(v)      } else {          v := &LinkNode{key, value, nil, nil}          v.next = head.next          v.pre = head          head.next.pre = v          head.next = v          cache[key] = v      }  }  

但是我們漏掉了一種情況，如果恰好此時Cache中元素滿了，需要刪掉最後的元素。處理完畢，附上Put函數完整程式碼。

func (this *LRUCache) Put(key int, value int) {      head := this.head      tail := this.tail      cache := this.m      //存在      if v, exist := cache[key]; exist {          //1.更新值          v.val = value          //2.移動到最前          this.moveToHead(v)      } else {          v := &LinkNode{key, value, nil, nil}          if len(cache) == this.cap {              //刪除最後元素              delete(cache, tail.pre.key)              tail.pre.pre.next = tail              tail.pre = tail.pre.pre          }          v.next = head.next          v.pre = head          head.next.pre = v          head.next = v          cache[key] = v      }  }  

最後，我們完成所有程式碼：

type LinkNode struct {      key, val  int      pre, next *LinkNode  }    type LRUCache struct {      m          map[int]*LinkNode      cap        int      head, tail *LinkNode  }    func Constructor(capacity int) LRUCache {      head := &LinkNode{0, 0, nil, nil}      tail := &LinkNode{0, 0, nil, nil}      head.next = tail      tail.pre = head      return LRUCache{make(map[int]*LinkNode), capacity, head, tail}  }    func (this *LRUCache) Get(key int) int {      cache := this.m      if v, exist := cache[key]; exist {          this.moveToHead(v)          return v.val      } else {          return -1      }  }    func (this *LRUCache) moveToHead(node *LinkNode) {      head := this.head      //從當前位置刪除      node.pre.next = node.next      node.next.pre = node.pre      //移動到首位置      node.next = head.next      head.next.pre = node      node.pre = head      head.next = node  }    func (this *LRUCache) Put(key int, value int) {      head := this.head      tail := this.tail      cache := this.m      //存在      if v, exist := cache[key]; exist {          //1.更新值          v.val = value          //2.移動到最前          this.moveToHead(v)      } else {          v := &LinkNode{key, value, nil, nil}          if len(cache) == this.cap {              //刪除末尾元素              delete(cache, tail.pre.key)              tail.pre.pre.next = tail              tail.pre = tail.pre.pre          }          v.next = head.next          v.pre = head          head.next.pre = v          head.next = v          cache[key] = v      }  }  

優化後：

type LinkNode struct {      key, val  int      pre, next *LinkNode  }    type LRUCache struct {      m          map[int]*LinkNode      cap        int      head, tail *LinkNode  }    func Constructor(capacity int) LRUCache {      head := &LinkNode{0, 0, nil, nil}      tail := &LinkNode{0, 0, nil, nil}      head.next = tail      tail.pre = head      return LRUCache{make(map[int]*LinkNode), capacity, head, tail}  }    func (this *LRUCache) Get(key int) int {      cache := this.m      if v, exist := cache[key]; exist {          this.MoveToHead(v)          return v.val      } else {          return -1      }  }    func (this *LRUCache) RemoveNode(node *LinkNode) {      node.pre.next = node.next      node.next.pre = node.pre  }    func (this *LRUCache) AddNode(node *LinkNode) {      head := this.head      node.next = head.next      head.next.pre = node      node.pre = head      head.next = node  }    func (this *LRUCache) MoveToHead(node *LinkNode) {      this.RemoveNode(node)      this.AddNode(node)  }    func (this *LRUCache) Put(key int, value int) {      tail := this.tail      cache := this.m      if v, exist := cache[key]; exist {          v.val = value          this.MoveToHead(v)      } else {          v := &LinkNode{key, value, nil, nil}          if len(cache) == this.cap {              delete(cache, tail.pre.key)              this.RemoveNode(tail.pre)          }          this.AddNode(v)          cache[key] = v      }  }  

因為該演算法過於重要，給一個Java版本的：

//java版本  public class LRUCache {    class LinkedNode {      int key;      int value;      LinkedNode prev;      LinkedNode next;    }      private void addNode(LinkedNode node) {      node.prev = head;      node.next = head.next;      head.next.prev = node;      head.next = node;    }      private void removeNode(LinkedNode node){      LinkedNode prev = node.prev;      LinkedNode next = node.next;      prev.next = next;      next.prev = prev;    }      private void moveToHead(LinkedNode node){      removeNode(node);      addNode(node);    }      private LinkedNode popTail() {      LinkedNode res = tail.prev;      removeNode(res);      return res;    }      private Hashtable<Integer, LinkedNode> cache = new Hashtable<Integer, LinkedNode>();    private int size;    private int capacity;    private LinkedNode head, tail;      public LRUCache(int capacity) {      this.size = 0;      this.capacity = capacity;      head = new LinkedNode();      tail = new LinkedNode();      head.next = tail;      tail.prev = head;    }      public int get(int key) {      LinkedNode node = cache.get(key);      if (node == null) return -1;      moveToHead(node);      return node.value;    }      public void put(int key, int value) {      LinkedNode node = cache.get(key);        if(node == null) {        LinkedNode newNode = new LinkedNode();        newNode.key = key;        newNode.value = value;        cache.put(key, newNode);        addNode(newNode);        ++size;        if(size > capacity) {          LinkedNode tail = popTail();          cache.remove(tail.key);          --size;        }      } else {        node.value = value;        moveToHead(node);      }    }  }  

鄭重申明（讀我的文章必看）：

• 本系列所有教程都不會用到複雜的語言特性，不需要擔心沒有學過相關語法，使用各語言純屬本人愛好。
• 作為學術文章，雖然風格可以風趣，但嚴謹，我是認真的。本文所有程式碼均在leetcode上進行過測試運行。
• 演算法思想才是最重要的。

04 PART

Redis 近LRU 介紹

上文完成了咱們自己的LRU實現，現在現在聊一聊Redis中的近似LRU。由於真實LRU需要過多的記憶體（在數據量比較大時），所以Redis是使用一種隨機抽樣的方式，來實現一個近似LRU的效果。說白了，LRU根本只是一個預測鍵訪問順序的模型。

在Redis中有一個參數，叫做 「maxmemory-samples」，是幹嘛用的呢？

# LRU and minimal TTL algorithms are not precise algorithms but approximated  # algorithms (in order to save memory), so you can tune it for speed or  # accuracy. For default Redis will check five keys and pick the one that was  # used less recently, you can change the sample size using the following  # configuration directive.  #  # The default of 5 produces good enough results. 10 Approximates very closely  # true LRU but costs a bit more CPU. 3 is very fast but not very accurate.  #  maxmemory-samples 5  

上面我們說過了，近似LRU是用隨機抽樣的方式來實現一個近似的LRU效果。這個參數其實就是作者提供了一種方式，可以讓我們人為干預樣本數大小，將其設的越大，就越接近真實LRU的效果，當然也就意味著越耗記憶體。（初始值為5是作者默認的最佳）

這個圖解釋一下，綠色的點是新增加的元素，深灰色的點是沒有被刪除的元素，淺灰色的是被刪除的元素。最下面的這張圖，是真實LRU的效果，第二張圖是默認該參數為5的效果，可以看到淺灰色部分和真實的契合還是不錯的。第一張圖是將該參數設置為10的效果，已經基本接近真實LRU的效果了。

今天基本就說到這裡。那Redis中的近似LRU是如何實現的呢？因為時間的關係，我打算做到下一期的內容。最後，評論區留下你的想法吧