缓存淘汰策略

这篇具有很好参考价值的文章主要介绍了缓存淘汰策略。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

应用层缓存

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

缓存的 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) 的链表查找。

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

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

type Node struct {
	key        string // 淘汰 tail 时需在维护的哈希表中删除,不是冗余存储
	val        interface{}
	prev, next *Node // 双向指针
}

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

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

func (l *List) Prepend(node *Node) *Node {
	if l.head == nil {
		l.head = node
		l.tail = node
	} else {
		node.prev = nil
		node.next = l.head
		l.head.prev = node
		l.head = node
	}
	l.size++
	return node
}

func (l *List) Remove(node *Node) *Node {
	if node == nil {
		return nil
	}
	prev, next := node.prev, node.next
	if prev == nil {
		l.head = next // 删除头结点
	} else {
		prev.next = next
	}

	if next == nil {
		l.tail = prev // 删除尾结点
	} else {
		next.prev = prev
	}

	l.size--
	node.prev, node.next = nil, nil
	return node
}

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

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

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

LRU 操作细节

Set(k, v)

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

Get(k)

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

代码实现:

type LRUCache struct {
	capacity int // 缓存空间大小
	items    map[string]*Node
	list     *List
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		items:    make(map[string]*Node),
		list:     new(List),
	}
}

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

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

func (c *LRUCache) Get(k string) interface{} {
	node, ok := c.items[k]
	if ok {
		c.items[k] = c.list.MoveToHead(node)
		return node.val
	}
	return -1
}

测试

func TestLRU(t *testing.T) {
	c := NewLRUCache(2)
	c.Set(K1, 1)
	c.Set(K2, 2)
	c.Set(K1, 100)
	fmt.Println(c.Get(K1)) // 100
	c.Set(K3, 3)
	fmt.Println(c.Get(K2)) // -1
	c.Set(K4, 4)
	fmt.Println(c.Get(K1)) // -1
	fmt.Println(c.Get(K3)) // 3
	fmt.Println(c.Get(K4)) // 4
}

LFU

缩写:Least Frequently Used(最近 最少 使用),频率维度。

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

对比 LRU,若缓存空间为 3 个数据量:

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

数据结构

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

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

双链表存储缓存数据:

type Node struct {
	key        string
	val        interface{}
	freq       int // 将节点从旧梯队移除时使用,非冗余存储
	prev, next *Node
}

type List struct {
	head, tail *Node
	size       int
}

LFU 操作细节

Set(k, v)

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

Get(k)

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

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

代码实现:

type LFUCache struct {
	capacity int
	minFreq  int // 最低频率

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

func NewLFUCache(capacity int) *LFUCache {
	return &LFUCache{
		capacity: capacity,
		minFreq:  0,
		items:    make(map[string]*Node),
		freqs:    make(map[int]*List),
	}
}

func (c *LFUCache) Get(k string) interface{} {
	node, ok := c.items[k]
	if !ok {
		return -1
	}

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

func (c *LFUCache) Set(k string, v interface{}) {
	if c.capacity <= 0 {
		return
	}

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

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

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

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

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

测试

func TestLFU(t *testing.T) {
	c := NewLFUCache(2)
	c.Set(K1, 1)           // 1:K1
	c.Set(K2, 2)           // 1:K2->K1	
	fmt.Println(c.Get(K1)) // 1:K2 2:K1 // 1
	c.Set(K3, 3)           // 1:K3 2:K1
	fmt.Println(c.Get(K2)) // -1
	fmt.Println(c.Get(K3)) // 2:k3->k1  // 3
	c.Set(K4, 4)           // 1:K4 2:K3
	fmt.Println(c.Get(K1)) // -1
	fmt.Println(c.Get(K3)) // 1:K4 3:K3 // 3
}

总结

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

在算法直接实现难度较大的情况下,不妨采用空间换时间,或时间换空间的策略来间接实现。要充分利用各种数据结构的优点并互补,比如链表加哈希表就实现了任意操作 O(1) 复杂度的复合数据结构。文章来源地址https://www.toymoban.com/news/detail-579301.html

到了这里,关于缓存淘汰策略的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LinkedHashMap如何实现LRU缓存淘汰策略?

    LRU,Least Recently Used, 最近最少使用 ,也就是优先淘汰最近最少使用的元素。 简而言之,就是将LinedHashMap的accessOrder设为true即可。 demo实现如下: 测试一下: 3.1 LinkedHashMap简介 LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用

    2023年04月24日
    浏览(40)
  • cache教程1.LRU 缓存淘汰策略

    这一节实现LRU算法,要理解明白其使用的数据结构。 Cache的缓存全部存储在内存中,内存是有限的,因此不可能无限制地添加数据。当占用内存超过了给定的内存大小时候,就需要从缓存中移除一条或多条数据了。我们肯定希望尽可能移除“没用”的数据,那如何判定数据“

    2024年02月04日
    浏览(45)
  • Redis 内存淘汰策略详解

    Redis 是一款高性能的非关系型数据库,它支持多种数据结构,如字符串、哈希、列表、集合、有序集合和 HyperLogLog。Redis 可以用于缓存、消息队列、应用程序中的数据结构存储等场景,它的优点是响应速度快、支持丰富的数据结构和扩展性好。 Redis 将所有数据都存储在内存中

    2024年02月10日
    浏览(55)
  • Redis的内存淘汰策略

    Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时,怎么处理需要新写入且需要申请额外空间的数据。 noeviction :当内存不足以容纳新写入数据时,新写入操作会报错。 allkeys-lru :当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的key。(这个是最常用

    2024年02月10日
    浏览(34)
  • Redis中的淘汰策略

    本文主要说明在Redis面临key过期和内存不足的情况时,可以采用什么策略进行解决问题。 正如我们知道的Redis是基于内存的、单线程的一个中间件,在面对过期数据的时候,Redis并不会去直接把它从内存中进行剔除,因为Redis是单线程的,如果出现了过期key就立马去删除,可能

    2024年02月11日
    浏览(39)
  • redis 7.x 内存过期淘汰策略

    1.查看redis默认内存大小 config  get  maxmemory config set  maxmemory    1024 注意:在64-bit系统下,maxmemory设置为0表示不限制redis的内存使用。 LRU: 最近最少使用页面置换算法 ,查看页面最后一次被使用到发生调度的时间长度,首先淘汰最长时间未被使用的页面。 LFU:最近最不经常

    2024年02月07日
    浏览(44)
  • Redis内存兜底策略——内存淘汰及回收机制

    Redis内存淘汰及回收策略都是Redis 内存优化兜底 的策略,那它们是如何进行 兜底 的呢?先来说明一下什么是内存淘汰和内存回收策略: Redis内存淘汰:当Redis的内存使用 超过配置 的限制时,根据一定的策略删除一些键,以 释放内存空间 Redis内存回收:Redis通过 定期删除 和

    2024年02月06日
    浏览(38)
  • Redis 从入门到精通【进阶篇】之过期和淘汰策略详解

    当涉及Redis中的过期和淘汰策略时,有很多值得探讨的内容。以下是一个关于Redis过期和淘汰策略的详细解释,希望对你有所帮助。 Redis中的过期策略是指在Redis中设置的键值对的生存时间过期后,系统如何处理这些过期的键值对。Redis采用了两种主要的过期策略:定期删除和

    2024年02月16日
    浏览(45)
  • Redis追本溯源(三)内核:线程模型、网络IO模型、过期策略与淘汰机制、持久化

    Redis在处理客户端请求时,通常使用单线程来进行读取、解析、执行和响应返回,因此被称为单线程应用。在4.0版本之前,这一描述是准确的。 单线程: 读取、解析、执行和响应返回。 从4.0版本开始,Redis开始使用后台线程来处理一些耗时的操作,如清理脏数据、释放超时连

    2024年02月15日
    浏览(47)
  • Redis支持的数据结构有哪些?Redis使用单线程还是多线程?Redis的持久化机制有哪些?Redis的缓存淘汰策略有哪些?

    Redis支持的数据结构包括: 字符串(string):存储一个字符串。 列表(list):按照插入顺序存储多个字符串。 集合(set):存储多个不重复的字符串。 有序集合(sorted set):存储多个不重复的字符串,并为每个字符串关联一个分数,可以根据分数进行排序。 哈希表(has

    2024年02月12日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包