缓存淘汰策略

发表于 | 分类于
字数统计 2k | 阅读时长 8

LRU 与 LFU 缓存策略及其实现。

应用层缓存

image-20230218171235871

鉴于磁盘和内存读写的差异性，DB 中低频写、高频读的数据适合放入内存中，直接供应用层读写。在项目中读取用户资料时就使用到了 LRU，而非放到 Redis 中。

缓存的 2 个基本实现

1
2
Set(key string, value interface) // 写数据
Get(key string) interface{}      // 读数据

缓存的 2 个特征

  • 命中率：即命中数 / 请求数，比值越高即表明缓存使用率越高，缓存更有效。
  • 淘汰策略：内存空间是有限的，当缓存数据占满内存后，若要缓存新数据，则必须淘汰一部分旧数据。对于旧 的概念，不同淘汰策略有不同原则。

下边介绍两种常用的淘汰算法：LRU 与 LFU

LRU

缩写：Least Recently Used（ 最近 最久 使用），时间维度

原则：若数据在最近一段时间内都未使用（读取或更新），则以后使用几率也很低，应被淘汰。

数据结构

  • 使用链表：由于缓存读写删都是高频操作，考虑使用写删都为 O(1) 的链表，而非写删都为 O(N) 的数组。
  • 使用双链表：选用删除操作为 O(1) 的双链表而非删除为 O(N) 的单链表。
  • 维护额外哈希表：链表查找必须遍历 O(N) 读取，可在缓存中维护 map[key]*Node 的哈希表来实现 O(1) 的链表查找。

image-20220903225628251

直接使用链表节点存储缓存的 K-V 数据，链表从 head 到 tail 使用频率逐步降低。新访问数据不断追加到 head 前边，旧数据不断从 tail 剔除。LRU 使用链表顺序性保证了热数据在 head，冷数据在 tail。

双链表节点存储 K-V 数据：

1
2
3
4
5
6
7
8
9
10
type Node struct {
truekey        string // 淘汰 tail 时需在维护的哈希表中删除，不是冗余存储
trueval        interface{}
trueprev, next *Node // 双向指针
}

type List struct {
truehead, tail *Node
truesize       int // 缓存空间大小
}

从上图可知，双链表需实现缓存节点新增 Prepend，剔除 Remove 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func (l *List) Prepend(node *Node) *Node {
trueif l.head == nil {
truetruel.head = node
truetruel.tail = node
true} else {
truetruenode.prev = nil
truetruenode.next = l.head
truetruel.head.prev = node
truetruel.head = node
true}
truel.size++
truereturn node
}

func (l *List) Remove(node *Node) *Node {
trueif node == nil {
truetruereturn nil
true}
trueprev, next := node.prev, node.next
trueif prev == nil {
truetruel.head = next // 删除头结点
true} else {
truetrueprev.next = next
true}

trueif next == nil {
truetruel.tail = prev // 删除尾结点
true} else {
truetruenext.prev = prev
true}

truel.size--
truenode.prev, node.next = nil, nil
truereturn node
}

// 封装数据已存在缓存的后续操作
func (l *List) MoveToHead(node *Node) *Node {
trueif node == nil {
truetruereturn nil
true}
truen := l.Remove(node)
truereturn l.Prepend(n)
}

func (l *List) Tail() *Node {
truereturn l.tail
}

func (l *List) Size() int {
truereturn l.size
}

LRU 操作细节

Set(k, v)

  • 数据已缓存，则更新值，挪到 head 前
  • 数据未缓存
    • 缓存空间未满：直接挪到 head 前
    • 缓存空间已满：移除 tail 并将新数据挪到 head 前

Get(k)

  • 命中：节点挪到 head 前，并返回 value
  • 未命中：返回 -1

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
type LRUCache struct {
truecapacity int // 缓存空间大小
trueitems    map[string]*Node
truelist     *List
}

func NewLRUCache(capacity int) *LRUCache {
truereturn &LRUCache{
truetruecapacity: capacity,
truetrueitems:    make(map[string]*Node),
truetruelist:     new(List),
true}
}

func (c *LRUCache) Set(k string, v interface{}) {
true// 命中
trueif node, ok := c.items[k]; ok {
truetruenode.val = v                         // 命中后更新值
truetruec.items[k] = c.list.MoveToHead(node) //
truetruereturn
true}

true// 未命中
truenode := &Node{key: k, val: v} // 完整的 node
trueif c.capacity == c.list.size {
truetruetail := c.list.Tail()
truetruedelete(c.items, tail.key) // k-v 数据存储与 node 中
truetruec.list.Remove(tail)
true}
truec.items[k] = c.list.Prepend(node) // 更新地址
}

func (c *LRUCache) Get(k string) interface{} {
truenode, ok := c.items[k]
trueif ok {
truetruec.items[k] = c.list.MoveToHead(node)
truetruereturn node.val
true}
truereturn -1
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
func TestLRU(t *testing.T) {
truec := NewLRUCache(2)
truec.Set(K1, 1)
truec.Set(K2, 2)
truec.Set(K1, 100)
truefmt.Println(c.Get(K1)) // 100
truec.Set(K3, 3)
truefmt.Println(c.Get(K2)) // -1
truec.Set(K4, 4)
truefmt.Println(c.Get(K1)) // -1
truefmt.Println(c.Get(K3)) // 3
truefmt.Println(c.Get(K4)) // 4
}

image-20220903225607839

LFU

缩写：Least Frequently Used（最近 最少 使用），频率维度。

原则：若数据在最近一段时间内使用次数少，则以后使用几率也很低，应被淘汰。

对比 LRU，若缓存空间为 3 个数据量：

1
2
3
4
5
6
7
Set("2", 2)
Set("1", 1)
Get(1)
Get(2)
Set("3", 3)
Set("4", 4) // LRU 将淘汰 1，缓存链表为 4->3->2
true    // LFU 将淘汰 3，未超出容量的时段内 1 和 2 都被使用了两次，3 仅使用一次

数据结构

依旧使用双向链表实现高效写删操作，但 LFU 淘汰原则是 使用次数，数据节点在链表中的位置与之无关。可按使用次数划分 频率梯队，数据节点使用一次就挪到高频梯队。此外维护 minFreq 表示最低梯队，维护 2 个哈希表：

  • map[freq]*List 各频率及其链表
  • map[key]*Node 实现数据节点的 O(1) 读

image-20230218171318312

双链表存储缓存数据：

1
2
3
4
5
6
7
8
9
10
11
type Node struct {
truekey        string
trueval        interface{}
truefreq       int // 将节点从旧梯队移除时使用，非冗余存储
trueprev, next *Node
}

type List struct {
truehead, tail *Node
truesize       int
}

LFU 操作细节

Set(k, v)

  • 数据已缓存，则更新值，挪到下一梯队
  • 数据未缓存
    • 缓存空间未满：直接挪到第 1 梯队
    • 缓存空间已满：移除 minFreq 梯队的 tail 节点，并将新数据挪到第 1 梯队

Get(k)

  • 命中：节点挪到下一梯队，并返回 value
  • 未命中：返回 -1

如上的 5 种 case，都要维护好对 minFreq 和 2 个哈希表的读写。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
type LFUCache struct {
truecapacity int
trueminFreq  int // 最低频率

trueitems map[string]*Node
truefreqs map[int]*List // 不同频率梯队
}

func NewLFUCache(capacity int) *LFUCache {
truereturn &LFUCache{
truetruecapacity: capacity,
truetrueminFreq:  0,
truetrueitems:    make(map[string]*Node),
truetruefreqs:    make(map[int]*List),
true}
}

func (c *LFUCache) Get(k string) interface{} {
truenode, ok := c.items[k]
trueif !ok {
truetruereturn -1
true}

true// 移到 +1 梯队中
truec.freqs[node.freq].Remove(node)
truenode.freq++
trueif _, ok := c.freqs[node.freq]; !ok {
truetruec.freqs[node.freq] = NewList()
true}
truenewNode := c.freqs[node.freq].Prepend(node)
truec.items[k] = newNode // 新地址更新到 map
trueif c.freqs[c.minFreq].Size() == 0 {
truetruec.minFreq++ // Get 的正好是当前值
true}
truereturn newNode.val
}

func (c *LFUCache) Set(k string, v interface{}) {
trueif c.capacity <= 0 {
truetruereturn
true}

true// 命中，需要更新频率
trueif val := c.Get(k); val != -1 {
truetruec.items[k].val = v // 直接更新值即可
truetruereturn
true}

truenode := &Node{key: k, val: v, freq: 1}

true// 未命中
true// 缓存已满
trueif c.capacity == len(c.items) {
truetrueold := c.freqs[c.minFreq].Tail() // 最低最旧
truetruec.freqs[c.minFreq].Remove(old)
truetruedelete(c.items, old.key)
true}

true// 缓存未满，放入第 1 梯队
truec.items[k] = node
trueif _, ok := c.freqs[1]; !ok {
truetruec.freqs[1] = NewList()
true}
truec.freqs[1].Prepend(node)
truec.minFreq = 1
}

minFreq 和 2 个哈希表的维护使 LFU 比 LRU 更难实现。

测试

1
2
3
4
5
6
7
8
9
10
11
12
func TestLFU(t *testing.T) {
truec := NewLFUCache(2)
truec.Set(K1, 1)           // 1:K1
truec.Set(K2, 2)           // 1:K2->K1
truefmt.Println(c.Get(K1)) // 1:K2 2:K1 // 1
truec.Set(K3, 3)           // 1:K3 2:K1
truefmt.Println(c.Get(K2)) // -1
truefmt.Println(c.Get(K3)) // 2:k3->k1  // 3
truec.Set(K4, 4)           // 1:K4 2:K3
truefmt.Println(c.Get(K1)) // -1
truefmt.Println(c.Get(K3)) // 1:K4 3:K3 // 3
}

image-20220903225519226

总结

常见的缓存淘汰策略有队列直接实现的 FIFO，双链表实现的 LFU 与 LRU，此外还有扩展的 2LRU 与 ARC 等算法，它们的实现不依赖于任意一种数据结构，此外对于旧数据的衡量原则不同，淘汰策略也不一样。

在算法直接实现难度较大的情况下，不妨采用空间换时间，或时间换空间的策略来间接实现。要充分利用各种数据结构的优点并互补，比如链表加哈希表就实现了任意操作 O(1) 复杂度的复合数据结构。

20200131220947.png

0%