LRU緩存及實現

2022 年 2 月 18 日
筆記
python學習筆記

一、淘汰策略

緩存：緩存作為一種平衡高速設備與低速設備讀寫速度之間差異而引入的中間層，利用的是局部性原理。比如一條數據在剛被訪問過只有就很可能再次被訪問到，因此將其暫存到內存中的緩存中，下次訪問不用讀取磁盤直接從內存中的緩存讀取。而內存是有限的，無法無限制的添加數據。當緩存超過設置的容量的時候，在添加緩存就需要選擇性的移除無效數據。需要具體的策略判定數據是否無效。

1、FIFO

FIFO：First In First Out，先進先出，淘汰緩存中最早添加的數據。認為緩存中最早添加的數據被在此使用的可能性就越小。實現可以使用一個隊列，隊列中的數據嚴格遵循先進先出，每次內存不夠用，則直接淘汰隊首元素。但是很多場景下，最早添加的元素也會被經常訪問，因此這類數據會頻繁的進出緩存，導致性能不佳。

2、LFU

LFU：Least Frequently Used，最少使用，淘汰緩存中使用頻率最低的數據。認為數據過去訪問的次數越多，將來更可能被訪問，因此應該盡量不被淘汰。實現上，需要維護一個記錄數據訪問次數的數組，每次訪問數據，訪問次數+1，數組就要重新排序，在淘汰時，只需淘汰訪問次數最少的數據。LFU的命中率很高，緩存更有效，但是每次訪問數據，都需要重排訪問次數數據，排序消耗很大。另外，數據訪問模式的經常變化，會導致緩存的性能下降。比如微博熱點事件，在某個時間點上訪問量突然加大，導致訪問次數很大，過段時間可能很少訪問，但是已經記錄了很高的訪問次數，導致該數據在緩存中很難被淘汰。

3、LRU

LRU：Least Recently Used，最近最少被使用，FIFO和LFU的這種方案。認為最近使用過的數據，在將來更可能被訪問，盡量不被淘汰。相對於LFU中需要記錄數據的訪問次數，LRU只需要維護一個隊列，隊列頭部保存剛被訪問過的數據，隊尾是最近最少未被訪問的數據，緩存容量不夠時候可以直接淘汰。

二、LRU實現

1、數據結構

緩存字典：LRU對象需要包含一個字典，用於緩存數據。這樣根據鍵查找值和插入新值的複雜度都是O(1)。
雙向鏈表：雙向鏈表維護數據的最近最少使用狀態。使用雙向鏈表可以保證隊尾刪除節點和隊頭添加節點的複雜度都是O(1)

字典的鍵是查找值，鍵對應的值是雙向鏈表對應的節點引用，這樣根據字典就可以找到雙向鏈表中的節點，進而調整雙向鏈表中節點的順序，更新數據的狀態。

2、實現

class DLinkList:
    """定義雙向鏈表""""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None


class LRUCache:
    """LRU緩存"""
    def __init__(self, capacity: int):
        # 初始化容量和佔用大小
        self.capacity = capacity
        self.size = 0
        self.cache = dict()
        # 初始化頭結點和尾節點
        self.tail = DLinkList()
        self.head = DLinkList()
        self.tail.pre = self.head
        self.head.next = self.tail

    def get(self, key: int) -> int:
        # 未命中緩存
        if key not in self.cache:
            return -1
        # 命中緩存修改將節點前移首部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        # 新增緩存
        if key not in self.cache:
            node = DLinkList(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed_node = self.removeTail()
                del self.cache[removed_node.key]
                self.size -= 1
        else:
            # 更新緩存
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def removeTail(self):
        # 移除尾部節點
        node = self.tail.pre
        self.removeNode(node)
        # 這裡仍舊需要將刪除的節點返回，為了方便cache字典刪除鍵值對
        return node

    def removeNode(self, node):
        # 移除某個節點
        node.next.pre = node.pre
        node.pre.next = node.next

    def moveToHead(self, node):
        # 節點前移首部
        self.removeNode(node)
        self.addToHead(node)

    def addToHead(self, node):
        # 添加到首部
        node.next = self.head.next
        node.pre = self.head
        self.head.next.pre = node
        self.head.next = node

註：

字典的定義的鍵是查找值，鍵對應的值是雙向鏈表對應節點的引用。
雙線鏈表的節點保存的鍵值對，好處在於，淘汰尾部節點的時候可以直接從節點取出鍵，進而刪除字典中的鍵值對。
查找數據的時候，如果緩存未命中，可以採用回調函數去查找數據庫真實數據。如果命中，則返回數據的同時，仍需要將該數據對應的節點調整到鏈表首部，更新最近最少使用狀態。
添加數據的時候，如果緩存容量滿了，則需要淘汰鏈表尾部節點，也就是最近最少訪問的節點。

相關鏈接：leetcode:lru緩存