详解缓存淘汰策略：LRU

缓存淘汰策略

缓存淘汰策略的存在是为了解决 缓存容量有限性 和 高缓存命中率 之间的矛盾。其核心目标是在有限的缓存空间内，尽可能提高缓存命中率

• 缓存容量有限性：缓存（例如进程的内存缓存）的空间是有限的。当缓存空间被填满，又来了新数据时，需要淘汰一些老数据，给新数据腾出空间
• 高缓存命中率：决定要淘汰哪些数据，对于提高缓存命中率至关重要。如果选择淘汰热数据，那么缓存命中率就低。反之如果淘汰冷数据，缓存命中率就高

常见的缓存淘汰策略有LRU，2q，LFU，tinyLFU等。本文介绍第一种：LRU

LRU

其核心思想是：当缓存空间不足时，优先淘汰最久未被访问的数据。它基于“时间局部性”原理，即假设最近被访问的数据更有可能在未来被再次访问

核心结构

LRU的核心结构为 一个哈希表 + 一个双向链表

• 双向链表：按访问时间顺序维护缓存项，链表头部是最近使用的项，尾部是最久未使用的项（淘汰候选）

  • 链表的每个节点entry包含以下字段：key，value，prev（链表上一个节点），next（链表下一个节点）

• 哈希表：存储键（Key）到链表节点（Node）的映射

核心操作流程

1. 访问数据（Get）：
   1. 通过哈希表在 O(1) 时间内找到对应链表节点。
   2. 将该节点从链表中删除（O(1)），并重新插入到链表头部（O(1)）。
   3. 返回节点值。
2. 插入数据（Put）：
   1. 如果键已存在：更新值，并像 Get 一样将节点移动到头部。
   2. 如果键不存在：
      1. 创建新节点，插入链表头部（O(1)）。
      2. 将键和节点存入哈希表（O(1)）。
      3. 如果缓存已满，删除链表尾部节点（O(1)），并同步删除哈希表中对应的键。

可以看出通过哈希表和双向链表的配合，Get和Put的时间复杂度都是O(1)，非常高效

一些设计上的关键问题：

• 为啥不用单链表，要用双向链表？
  • 拿到要删除的节点后，单链表无法在 O(1) 时间内删除一个节点
• 为啥节点需要存储key？
  • 当某个节点被淘汰时，可以O(1)时间根据key去哈希表中进行删除操作

局限性

上面介绍的LRU有下面的局限性：

• 突发流量污染：如果某个很少访问的项在短时间内被突然大量访问（即使之后不再访问），它会长时间占据缓存头部，挤掉可能更热（访问频率更高但近期未被访问）的项。
• 没有考虑缓存项的频率：例如一个只访问一次但刚好是最近访问的项，会排在访问了十次但稍早访问的项前面。但这在大多数场景下是不符合预期的

这两个问题在2q，LFU，tinyLFU会得到解决

源码走读

下面将针对一个经典的开源库https://github.com/hashicorp/golang-lru的LRU实现进行源码走读，版本：v2.0.7

数据结构如下：

type LRU[K comparable, V any] struct {
     // 表示缓存的最大容量
     size int
     // 双向链表，用于维护缓存中条目的访问顺序
     evictList *internal.LruList[K, V]
     // 是一个哈希表（字典），将键（K）映射到对应的缓存条目（*internal.Entry） 
     items   map[K]*internal.Entry[K, V]
     onEvict EvictCallback[K, V]
}

type Entry[K comparable, V any] struct {
	next, prev *Entry[K, V]
	
	     // 属于哪个链表
	list *LruList[K, V]
	
	Key K
	Value V
}

Add

func (c *LRU[K, V]) Add(key K, value V) (evicted bool) {
       // 检查是否已存在相同键的条目
	   if ent, ok := c.items[key]; ok {
	   // 如果存在，则将该条目移动到双向链表的最前面（表示最近使用），并更新其值
	   c.evictList.MoveToFront(ent)
       ent.Value = value
       return false
    }

     // 将新的键值对插入到双向链表的头部，表示这是最新的访问项
     ent := c.evictList.PushFront(key, value)
     // 同时将该条目加入到哈希表 items 中，以便后续快速查找
     c.items[key] = ent

     // 判断是否超出容量限制
     evict := c.evictList.Length() > c.size
     if evict {
        // 移除最老的元素
        c.removeOldest()
    }
    return evict
}

移除最老元素流程如下：

func (c *LRU[K, V]) removeOldest() {
     // 找到双向链表中最老的元素ent
    if ent := c.evictList.Back(); ent != nil {
       c.removeElement(ent)
    }
}

func (c *LRU[K, V]) removeElement(e *internal.Entry[K, V]) {
     // 从双向链表中移除
     c.evictList.Remove(e)
     // 从哈希表中删除
     delete(c.items, e.Key)
     if c.onEvict != nil {
        c.onEvict(e.Key, e.Value)
     }
}

Get

func (c *LRU[K, V]) Get(key K) (value V, ok bool) {
     // 如果存在，将其移动到链表头部，标识最近访问
     if ent, ok := c.items[key]; ok {
       c.evictList.MoveToFront(ent)
       return ent.Value, true
    }
    return
}