詳解工程師不可不會的LRU緩存淘汰算法

大家好，歡迎大家來到算法數據結構專題，今天我們和大家聊一個非常常用的算法，叫做LRU。

LRU的英文全稱是Least Recently Used，也即最不經常使用。我們看著好像挺迷糊的，其實這個含義要結合緩存一起使用。對於工程而言，緩存是非常非常重要的機制，尤其是在當下的網際網路應用環境當中，起到的作用非常重要。為了便於大家更好地理解，我們從緩存的機制開始說起。

緩存

緩存的英文是cache，最早其實指的是用於CPU和主存數據交互的。早年這塊存儲被稱為高速緩存，最近已經聽不到這個詞了，不知道是不是淘汰了。因為緩存的讀寫速度要高於CPU低於主存，所以是用來過渡數據用的。CPU從緩存當中讀取數據，主存的數據也會先加載到緩存當中來，之後再進入CPU。

後來緩存有了更多的應用和意為，在後端服務當中一般用來快速響應請求。其實這裡的思想和記憶化搜索有點像，我們把可能要用到的數據先存起來，後期如果要用到的話，就可以直接從內存當中讀取而不是再去計算一遍了。原理也是一樣的，有了緩存我們可以把要返回給用戶的數據儲存在內存中，當同樣的請求過來的時候，我們就可以直接從內存當中讀取結果，而不是再走一次鏈路獲取數據了。

舉一個很簡單的例子，比如說我們打開淘寶首頁會看到很多商品的推薦。其實推薦商品的流程是非常複雜的，首先要根據一定的策略去商品庫當中召回商品。比如根據用戶之前的行為召回和歷史行為相關的商品，召回了商品之後還要進行清洗，過濾掉一些明確不感興趣或者是非法、違規的商品。過濾了之後需要使用機器學習或者是深度學習的模型來進行點擊率預測，從而將發生點擊可能性最高的商品排在前面。

到這裡還沒結束，推薦商品列表其實也是分展位的，有些位置的商品是運營配好的，有些位置固定展示的是廣告。廣告往往也有自己的一條鏈路，還有些位置有一些其他的邏輯。這些商品的數據都拿到了之後，還要獲取圖片以及其他一些零零散散的信息，最後才能展示出來。因此大家可以試一下打開淘寶首頁要比打開百度首頁慢得多，這並不是淘寶技術差，而是因為這中間的鏈路實在是太長了。

我們很容易發現，對於一些經常打開淘寶的用戶來說，其實沒有必要每一次都把完整的鏈路走一遍。我們大可以把之前展示的結果存儲在內存裡，下一次再遇到同樣請求的時候，直接從內存當中讀取並且返回就可以了。這樣可以節省大量的時間以及計算資源，比如在大促的時候，就可以把計算資源節省下來用在更加需要的地方。

緩存雖然好用，但是也不是萬能的，因為內存是很貴的，我們不可能把所有數據都存在內存裡。內存裡只能放一些我們認為比較高價值的數據，在這種情況下，計算科學家們想出了種種策略來調度緩存，保持緩存當中數據的高價值。LRU就是其中一種比較常用的策略。

LRU含義

我們前面也說了，LRU的意思是最長不經常使用，也可以理解成最久沒有使用。在這種策略下我們用最近一次使用的時間來衡量一塊內存的價值，越久之前使用的價值也就越低，最近剛剛使用過的，後面接著會用到的概率也就越大，那麼自然也就價值越高。

當然只有這個限制是不夠的，我們前面也說了，由於內存是非常金貴的，導致我們可以存儲在緩存當中的數據是有限的。比如說我們固定只能存儲1w條，當內存滿了之後，緩存每插入一條新數據，都要拋棄一條最長沒有使用的舊數據。這樣我們就保證了緩存當中的數據的價值都比較高，並且內存不會超過限制。

我們把上面的內容整理一下，可以得到幾點要求：

1. 保證緩存的讀寫效率，比如讀寫的複雜度都是O(1)
2. 當一條緩存當中的數據被讀取，將它最近使用的時間更新
3. 當插入一條新數據的時候，彈出更新時間最遠的數據

LRU原理

我們仔細想一下這個問題會發現好像沒有那麼簡單，顯然我們不能通過數組來實現這個緩存。因為數組的查詢速度是很慢的，不可能做到O(1)。其次我們用HashMap好像也不行，因為雖然查詢的速度可以做到O(1)，但是我們沒辦法做到更新最近使用的時間，並且快速找出最遠更新的數據。

如果是在面試當中被問到想到這裡的時候，可能很多人都已經束手無策了。但是先別著急，我們冷靜下來想想會發現問題其實並沒有那麼模糊。首先HashMap是一定要用的，因為只有HashMap才可以做到O(1)時間內的讀寫，其他的數據結構幾乎都不可行。但是只有HashMap解決不了更新以及淘汰的問題，必須要配合其他數據結構進行。這個數據結構需要能夠做到快速地插入和刪除，其實我這麼一說已經很明顯了，只有一個數據結構可以做到，就是鍊表。

鍊表有一個問題是我們想要查詢鍊表當中的某一個節點需要O(n)的時間，這也是我們無法接受的。但這個問題並非無法解決，實際上解決也很簡單，我們只需要把鍊表當中的節點作為HashMap中的value進行儲存即可，最後得到的系統架構如下：

對於緩存來說其實只有兩種功能，第一種功能就是查找，第二種是更新。

查找

查找會分為兩種情況，第一種是沒查到，這種沒什麼好說的，直接返回空即可。如果能查到節點，在我們返回結果的同時，我們需要將查到的節點在鍊表當中移動位置。我們假設越靠近鍊表頭部表示數據越舊，越靠近鍊表尾部數據越新，那麼當我們查找結束之後，我們需要把節點移動到鍊表的尾部。

移動可以通過兩個步驟來完成，第一個步驟是在鍊表上刪除該節點，第二個步驟是插入到尾部：

更新

更新也同樣分為兩種情況，第一種情況就是更新的key已經在HashMap當中了，那麼我們只需要更新它對應的Value，並且將它移動到鍊表尾部。對應的操作和上面的查找是一樣的，只不過多了一個更新HashMap的步驟，這沒什麼好說的，大家應該都能想明白。

第二種情況就是要更新的值在鍊表當中不存在，這也會有兩種情況，第一個情況是緩存當中的數量還沒有達到限制，那麼我們直接添加在鍊表結尾即可。第二種情況是鍊表現在已經滿了，我們需要移除掉一個元素才可以放入新的數據。這個時候我們需要刪除鍊表的第一個元素，不僅僅是鍊表當中刪除就可以了，還需要在HashMap當中也刪除對應的值，否則還是會佔據一份內存。

因為我們要進行鍊表到HashMap的反向刪除操作，所以鍊表當中的節點上也需要記錄下Key值，否則的話刪除就沒辦法了。刪除之後再加入新的節點，這個都很簡單：

我們理順了整個過程之後來看代碼：

class Node:    def __init__(self, key, val, prev=None, succ=None):        self.key = key        self.val = val        # 前驅        self.prev = prev        # 後繼        self.succ = succ    def __repr__(self):        return str(self.val)class LinkedList:    def __init__(self):        self.head = Node(None, 'header')        self.tail = Node(None, 'tail')        self.head.succ = self.tail        self.tail.prev = self.head    def append(self, node):        # 將node節點添加在鍊表尾部        prev = self.tail.prev        node.prev = prev        node.succ = prev.succ        prev.succ = node        node.succ.prev = node    def delete(self, node):        # 刪除節點        prev = node.prev        succ = node.succ        succ.prev, prev.succ = prev, succ    def get_head(self):        # 返回第一個節點        return self.head.succclass LRU:    def __init__(self, cap=100):        # cap即capacity，容量        self.cap = cap        self.cache = {}        self.linked_list = LinkedList()    def get(self, key):        if key not in self.cache:            return None        self.put_recently(key)        return self.cache[key]    def put_recently(self, key):        # 把節點更新到鍊表尾部        node = self.cache[key]        self.linked_list.delete(node)        self.linked_list.append(node)    def put(self, key, value):        # 能查到的話先刪除原數據再更新        if key in self.cache:            self.linked_list.delete(self.cache[key])            self.cache[key] = Node(key, value)            self.linked_list.append(self.cache[key])            return         if len(self.cache) >= self.cap:            # 如果容量已經滿了，刪除最舊的節點            node = self.linked_list.get_head()            self.linked_list.delete(node)            del self.cache[node.key]        u = Node(key, value)        self.linked_list.append(u)        self.cache[key] = u

在這種實現當中我們沒有用除了dict之外的其他任何工具，連LinkedList都是自己實現的。實際上在Python語言當中有一個數據結構叫做OrderedDict，它是一個字典，但是它當中的元素都是有序的。我們利用OrderedDict來實現LRU就非常非常簡單，代碼量也要少得多。

我們來看代碼：

class LRU(OrderedDict):    def __init__(self, cap=128, /, *args, **kwds):        self.cap = cap        super().__init__(*args, **kwds)    def __getitem__(self, key):        # 查詢函數        value = super().__getitem__(key)        # 把節點移動到末尾        self.move_to_end(key)        return value    def __setitem__(self, key, value):        # 更新函數        super().__setitem__(key, value)        if len(self) > self.cap:            oldest = next(iter(self))            del self[oldest]

在上面一種實現當中由於只用了一個數據結構，所以整個代碼要簡潔許多。使用起來也更加方便，直接像是dict一樣使用方括號進行查詢以及更新就可以了。不過在其他語言當中可能沒有OrderedDict這種數據結構，這就需要我們自己來編碼實現了。

好了，今天的文章就到這裡。衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話，請來一個三連支持吧~（點讚、關注、轉發）

- END -

本文始發於公眾號：TechFlow，求個關注