缓存替换策略LRU和LFU的实现

在web系统中，为了提高响应效率，我们通常会把经常使用到的数据，或最近一段时间需要使用的数据放到内存中，以避免频繁地读取磁盘。但是，内存是计算机非常昂贵的部件，这就意味着内存的容量是有限的，当缓存已经占用了分配给它所有的内存后，新的数据的到来必将导致旧的数据被替换。这也是Redis数据库的所有set命令都有expire选项的原因。

内存替换最常用的两种方案是LRU（Least Recently Used）和LFU（Least Frequently Used），LRU是要替换掉上次使用时间距离当前时间最久的数据，LFU则是替换掉整个内存中使用频率最小的数据，这两种方案都有自己的优势，但LRU使用更为广泛，Redis和Memchached都选择的LRU策略。

LRU从某种意义上来说是提升版的FIFO（Frist In, First Out），相似的地方，都是替换最老的数据；区别在于，FIFO策略只受插入操作的影响，而在LRU中，插入和访问数据都会导致数据成为最近使用的数据。我们都知道，实现FIFO只需要维护一个队列的数据结构，那么实现LRU就是在维护一个先进先出的队列的基础上，支持元素被访问时把它移到队尾就可以了。

接下来我们需要解决的问题就是找到一种数据结构，能在以下几种场景中都有较小的时间复杂度

在队列首部删除元素
在队列末尾添加元素
把队列中间的某个元素移动到队列末尾

有一定算法基础的同学都会自然地联想到双向链表，因为无论在双向链表中的哪个位置，执行插入和删除的操作都是O（1）的时间复杂度。

接下来我们就要考虑怎样基于这个底层的数据结构来实现缓存的基本功能：插入数据（Put）和访问数据（Get）。例如：

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2

Put操作，可以总结为以下两点：

检查链表中是否已经包含键对应的节点，如果有则需要删除旧的节点，并在链表末尾插入新的数据
如果链表长度达到上限，则需要删除链表首部的节点，并在链表末尾插入新的数据

Get操作可以总结为：

给定键值，返回对应的结果

可以看出，不论是Get还是Put操作，都需要通过键在链表中查找节点，如果仅仅使用双向链表，时间复杂度是O（N），怎样以O（1）的时间访问数据呢？我们自然会联想到字典（也叫hashmap），字典的键存放键，字典的值存放链表中对应节点的指针，这样就可以以O（1）的时间访问节点。

另外，我们还要考虑到当发生缓存替换时，让字典中存储的键值对失效。这就意味着我们能够从链表中节点，获取到数据的键值。

综上，算法实现如下：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def push(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

    def pop(self):
        node = self.head.next
        self.remove(node)
        return node

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        self.size = 0
        self.capacity = capacity
        self.dlist = DLinkedList()

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if node:
            self.dlist.remove(node)
            self.dlist.push(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        new_node = Node(key, value)
        old_node = self.cache.get(key)
        if old_node:
            self.dlist.remove(old_node)
        elif self.size == self.capacity:   
            pop_node = self.dlist.pop()
            del self.cache[pop_node.key]
        else:
            self.size += 1

        self.dlist.push(new_node)
        self.cache[key] = new_node

zshuangyan / blog

缓存替换策略LRU和LFU的实现 #35