缓存替换算法

缓存替换算法决定了在有限的容量的缓存中,有新的项进入的时候选择哪一项被剔除的问题。
缓存算法有很多

假如我们以 K-V 形式的缓存为例。通常 KV 形式的缓存为了有 O(1) 的读取速度都会维护一个 HashMap
那么不同的算法的其中一个不同之处就是保存替换时决策所需要的信息而产生的额外的数据结构了。

LRU

LRU(Least recently used)最近最少使用,实际上就是缓存中最久未被使用的项会被优先剔除。

它的思想是如果一个项很久都没被使用了,那么它应该被剔除缓存。

但是当缓存的访问是循环的顺序遍历,而且缓存容量不足以容纳遍历的项时,缓存项就会频繁进出影响效率。

实现

Leetcode 上有 LRU Cache 的题目

为了知道最近最少访问的信息通常 LRU 的实现会采用双链表保存缓存项。因为缓存的数量会动态变化,所以会选择链表。而且会有不少的删除节点操作,为了达到 O(1) 的删除操作所以会用双链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type CacheNode struct {
key int
value int
prev *CacheNode
next *CacheNode
}

type LRUCache struct {
size int
capacity int
head *CacheNode
tail *CacheNode
cache map[int]*CacheNode
}

我们保存链表的尾指针,每当有缓存项的访问或者新项都将对应的节点移到链表的头。头插入和删除节点的操作都是 O(1)

完整实现

hashlru

还有一种近似的 LRU 算法 HashLRU 通过两个 HashMap 的交换实现 O(1) 的复杂度,在实际的 Benchmark 中的表现也很好。

LFU

LFU(Least Frequently Used)最近最不频繁使用,缓存中被使用的次数最少的项会被优先剔除。它认为被用的越少的项越应该移除。

LFU 克服了 LRU 在大规模遍历时的缺点。但是容易导致旧数据的积累。同时新数据因为使用次数少容易反复被移出缓存导致长期无法积累跟大的使用次数。

实现

Leetcode 上有 LFU Cache 的题目
为了维护相关的访问频次信息需要额外的数据结构。一种各操作 (增删查) 都为 O(1) 的形式是使用两个双链表。其中一个保存访问频次,另一个用于保存某频次对应的节点。因为频次链表会经常有增删操作所以使用双链表。而保存某频次对应节点的链表也可以使用 HashMap 或者动态表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type CacheNode struct {
key int
value int
prev *CacheNode
next *CacheNode
parent *FreqNode
}

type FreqNode struct {
freq int
head *CacheNode
tail *CacheNode
prev *FreqNode
next *FreqNode
}

type LFUCache struct {
size int
capacity int
cache map[int]*CacheNode
lfuHead *FreqNode
}

lfu

缓存保存一个使用次数为 0 的频次节点的指针。新项加入时, 头插入到次数为 1 的频次节点,时间复杂度为 O(1)

当某一个频次的节点 (除 0 以外) 所持有的缓存项个数为 0 时,该频次节点就会被移除。这样保证了 0 频次节点的下一个节点总是缓存中使用次数最少的。

此时,只要在频次节点中维护缓存项链表的尾指针,就知道了缓存中使用此是最少最老旧的缓存项。此番操作 (lfuHead.next.head) 的时间复杂度也是 O(1)

完整实现

ARC

ARC(Adaptive replacement cache) 同时使用 LRU 和 LFU。通过动态调整 LRU,LFU 的容量达到自适应的效果。
缓存中除了 LRU 和 LFU 所需的数据结构外,额外增加了两条链表 LRU 和 LFU 各一个称为 Ghost List。
开始时缓存容量被平分 LRU 和 LFU 两部分。当新项加入时,先加入到 LRU 中。当缓存项被访问而 LFU 中没有时,加入到 LFU 中。
如果缓存项被移除则将它的 Key 加入到对应的 Ghost List 中。每当缓存不命中时,都会检查 Ghost List。假如 Ghost List 中含有当前不命中的 Key 则该 Ghost List 对应的缓存的容量应该增加。

参考文章