iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > GO >LRU LFU TinyLFU缓存算法实例详解
  • 770
分享到

LRU LFU TinyLFU缓存算法实例详解

2024-04-02 19:04:59 770人浏览 独家记忆
摘要

目录简介一、LRU和LFU算法LRU算法LFU算法小结:二、TinyLFU三、Window-TinyLFU简介 前置知识 知道什么是缓存 听完本节公开课,你可以收获 掌握朴素LRU、

简介

前置知识

知道什么是缓存

听完本节公开课,你可以收获

  • 掌握朴素LRU、LFU算法的思想以及源码
  • 掌握一种流式计数的算法 Count-Min Sketch
  • 手撕TinyLFU算法、分析Window-TinyLFU源码

一、LRU和LFU算法

LRU算法

LRU Least Recently Used 最近最少使用算法

LRU 算法的思想是如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。所以,当指定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

也就是淘汰数据的时候,只看数据在缓存里面待的时间长短这个维度。

这样子做有什么缺点呢?我们来看个例子

无法复制加载中的内容

按照LRU算法进行访问和数据淘汰,10次访问的结果如下图所示

无法复制加载中的内容

10次访问结束后,缓存中剩下的数据是b、c、d三个元素,这个显然不太合理。

直观上讲,为什么说他不合理,是因为明明a是被频繁访问的数据,最终却被淘汰掉了。所以如果要改进这个算法,我们希望的是能够记录每个元素的访问频率信息,访问频率最低的那个才是最应该被淘汰的那个。

恭喜你,这就是LFU的规则。

在开始LFU之前,我们先来看一下LRU的代码怎么写。

有句古话讲得好:缓存就是Map + 淘汰策略。Map的作用是提供快速访问,淘汰策略是缓存算法的灵魂,决定了命中率的高低。根据对于LRU的描述,我们需要一个东西(术语叫做数据结构)来记录数据被访问的先后顺序,这里我们可以选择链表

打开IDE,迅速写下第一行代码:

type LRU struct {
   data map[string]*list.Element
   cap int
   list *list.List
}

解释一下为什么需要这几个变量, cap 是缓存中可以存放的数据个数,也就是缓存的容量上限。data就是Map。List我们用来记录数据的先后访问顺序,每次访问,都把本次访问的节点移动到链表中的头部。这样子整个链表就会按照近期的访问记录来排序了。

func (lru *LRU) add(k, v string) {
   if Map中存有这条Key {
      替换Map中的Value值
      将链表中的对应节点移到最前面
   } else {
      if 已经达到缓存容量上限 {
         获取链表尾部节点的Key,并从Map中删除
         移除链表尾部的node
      }
      创建要插入的新节点
      将新节点插入到链表头部
      放入Map中
   }
}
func (lru *LRU) get(k string) string {
   if Map中存有这条Key {
      返回查询到的Value
      将对应节点移动到链表头部
   } else {
      返回 空
   }
}

LFU算法

我们已经成功的写出了LRU算法(伪代码),接下来尝试自己写一下LFU算法。首先我们知道LFU算法比LRU多了什么,LFU需要记录每条数据的访问次数信息,并且按照访问次数从高到低排序,访问次数用什么来记录呢?

只需要在链表节点中增加一个访问频率Frequency,就可以了,这个Frequency可以使用int来存储。同时排序的规则稍加变动,不是把最近访问的放到最前面,而是按照访问频率插入到对应位置即可。如果频率相同,再按照LRU的规则,比较谁是最新访问的。

暂时无法在文档外展示此内容

小结:

讲完了LRU和LFU,我们来看一下他们有啥优缺点。

LRU

优点:实现简单、可以很快的适应访问模式的改变

缺点:对于热点数据的命中率可能不如LFU

LFU

优点:对于热点数据命中率更高

缺点:难以应对突发的稀疏流量、可能存在旧数据长期不被淘汰,会影响某些场景下的命中率(如外卖),需要额外消耗来记录和更新访问频率

二、TinyLFU

Count-Min Sketch 算法

刚才提到了LFU需要统计每个条数据的访问频率,这就需要一个int或者long类型来存储次数,但是仔细一想,一条缓存数据的访问次数真的需要int类型这么大的表示范围来统计吗?我们认为一个缓存被访问15次已经算是很高的频率了,那么我们只用4个Bit就可以保存这个数据。(2^4=16)

再来介绍一个cmSketch算法,看过硬核课堂BloomFilter视频的都知道,BloomFilter利用位图的思想来标记一条数据是否存在,存在与否可以用某个Bit位的0 | 1来代替,那么我们能不能扩展一下,利用这种思想来计数呢?

我们给要计数的值计算一个Hash,然后在位图中给这个Hash值对应的位置累加1就可以了,但是BloomFilter中的一个典型问题是假阳性,可以说只要是用Hash计算就有存在冲突的可能,那么cmSketch计数法如果出现冲突会怎么样呢?会给同一个位置多计算访问次数。这里cmSketch选择了以最小的统计数据值作为结果。这是一个不那么精确地统计方法,但是可以大致的反应访问分布的规律。

因为这个算法也就有了一个名字,叫做Count-Min Sketch。

下面我们来手撕这个算法。

//根据BloomFilter来思考一下我们需要什么
//一个bit图,n个Hash函数
//一个BitMap的实现
type cmRow []byte //byte = uint8 = 0000,0000 = COUNTER 4BIT = 2 counter
//64 counter
//1 uint8 =  2counter
//32 uint8 = 64 counter
func newCmRow(numCounters int64) cmRow {
   return make(cmRow, numCounters/2)
}
func (r cmRow) get(n uint64) byte {
   return byte(r[n/2]>>((n&1)*4)) & 0x0f
}
0000,0000|0000,0000| 0000,0000 make([]byte, 3) = 6 counter
func (r cmRow) increment(n uint64) {
   //定位到第i个Counter
   i := n / 2 //r[i]
   //右移距离,偶数为0,奇数为4
   s := (n & 1) * 4
   //取前4Bit还是后4Bit
   v := (r[i] >> s) & 0x0f //0000, 1111
   //没有超出最大计数时,计数+1
   if v < 15 {
      r[i] += 1 << s
   }
}
//cmRow 100,
//保鲜
func (r cmRow) reset() {
   // 计数减半
   for i := range r {
      r[i] = (r[i] >> 1) & 0x77 //0111,0111
   }
}
func (r cmRow) clear() {
   // 清空计数
   for i := range r {
      r[i] = 0
   }
}
//快速计算最接近x的二次幂的算法
//比如x=5,返回8
//x = 110,返回128
//2^n
//1000000 (n个0)
//01111111(n个1) + 1
// x = 1001010 = 1111111 + 1 =10000000 
func next2Power(x int64) int64 {
   x--
   x |= x >> 1 
   x |= x >> 2
   x |= x >> 4
   x |= x >> 8
   x |= x >> 16
   x |= x >> 32
   x++
   return x
}

如果我们要给n个数据计数,那么每4Bit当做一个计数器Counter,我们一共需要几个uint8来计数呢?答案是n/2

00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
//cmSketch封装
const cmDepth = 4
type cmSketch struct {
   rows [cmDepth]cmRow
   seed [cmDepth]uint64
   mask uint64
}
//numCounter - 1 = next2Power() = 0111111(n个1)
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
func newCmSketch(numCounters int64) *cmSketch {
   if numCounters == 0 {
      panic("cmSketch: bad numCounters")
   }
   numCounters = next2Power(numCounters)
   sketch := &cmSketch{mask: uint64(numCounters - 1)}
   // Initialize rows of counters and seeds.
   source := rand.New(rand.NewSource(time.Now().UnixNano()))
   for i := 0; i < cmDepth; i++ {
      sketch.seed[i] = source.Uint64()
      sketch.rows[i] = newCmRow(numCounters)
   }
   return sketch
}
func (s *cmSketch) Increment(hashed uint64) {
   for i := range s.rows {
      s.rows[i].increment((hashed ^ s.seed[i]) & s.mask)
   }
}
// 找到最小的计数值
func (s *cmSketch) Estimate(hashed uint64) int64 {
   min := byte(255)
   for i := range s.rows {
      val := s.rows[i].get((hashed ^ s.seed[i]) & s.mask)
      if val < min {
         min = val
      }
   }
   return int64(min)
}
// 让所有计数器都减半,保鲜机制
func (s *cmSketch) Reset() {
   for _, r := range s.rows {
      r.reset()
   }
}
// 清空所有计数器
func (s *cmSketch) Clear() {
   for _, r := range s.rows {
      r.clear()
   }
}

TinyLFU解决了LFU统计的内存消耗问题,和缓存保鲜的问题,但是TinyLFU是否还有缺点呢?

有,论文中是这么描述的,根据实测TinyLFU应对突发的稀疏流量时表现不佳。大概思考一下也可以得知,这些稀疏流量的访问频次不足以让他们在LFU缓存中占据位置,很快就又被淘汰了。

我们回顾之前讲过的,LRU对于稀疏流量效果很好,那可以不可以把LRU和LFU结合一下呢?就出现了下面这种缓存策略。

三、Window-TinyLFU

Window-TinyLFU策略里包含LRU和LFU两部分,前端的小LRU叫做Window LRU,它的容量只占据1%的总空间,它的目的就是用来存放短期的突发访问数据。存放主要元素的Segmented LRU(SLRU)是一种LRU的改进,主要把在一个时间窗口内命中至少2次的记录和命中1次的单独存放,这样就可以把短期内较频繁的缓存元素区分开来。具体做法上,SLRU包含2个固定尺寸的LRU,一个叫Probation段A1,一个叫Protection段A2。新记录总是插入到A1中,当A1的记录被再次访问,就把它移到A2,当A2满了需要驱逐记录时,会把驱逐记录插入到A1中。W-TinyLFU中,SLRU有80%空间被分配给A2段。

视频讲解

以上就是LRU LFU TinyLFU缓存算法实例详解的详细内容,更多关于LRU LFU TinyLFU缓存算法的资料请关注编程网其它相关文章!

您可能感兴趣的文档:

--结束END--

本文标题: LRU LFU TinyLFU缓存算法实例详解

本文链接: https://www.lsjlt.com/news/121142.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • LRU LFU TinyLFU缓存算法实例详解
    目录简介一、LRU和LFU算法LRU算法LFU算法小结:二、TinyLFU三、Window-TinyLFU简介 前置知识 知道什么是缓存 听完本节公开课,你可以收获 掌握朴素LRU、...
    99+
    2022-11-11
  • C++ 实现LRU 与 LFU 的缓存算法
    目录一、LRU (Least Recently Used) 缓存 二、LFU (Least Frequently Used) 缓存一、LRU (Least Recently Used...
    99+
    2022-11-12
  • Java实现常用缓存淘汰算法:FIFO、LRU、LFU
    目录缓存淘汰算法FIFOLRULFU总结缓存淘汰算法 在高并发、高性能的质量要求不断提高时,我们首先会想到的就是利用缓存予以应对。 第一次请求时把计算好的结果存放在缓存中,下次遇到同...
    99+
    2022-11-12
  • Java实现LRU缓存的实例详解
    Java实现LRU缓存的实例详解1.CacheCache对于代码系统的加速与优化具有极大的作用,对于码农来说是一个很熟悉的概念。可以说,你在内存中new 了一个一段空间(比方说数组,list)存放一些冗余的结果数据,并利用这些数据完成了以空...
    99+
    2023-05-31
    java lru缓存 ava
  • Java实现LRU缓存算法的参考示例
    目录一、什么是 LRU二、Java 实现 LRU 缓存算法一、什么是 LRU LRU(Least Recently Used,最近最少使用)是...
    99+
    2023-05-20
    Java 算法 Java LRU缓存算法 Java LUR
  • JavaScript实现LRU算法的示例详解
    目录LRU简介如何实现实现思路缺陷双向链表+哈希表双向链表实现思路不知道屏幕前的朋友们,有没有和我一样,觉得LRU算法原理很容易理解,实现起来却很复杂。 明明一个map就能解决,标准...
    99+
    2023-05-17
    JavaScript实现LRU算法 JavaScript LRU算法 JavaScript LRU
  • JavaScript双向链表实现LFU缓存算法
    目录什么是LFU描述解题思路1、构造节点结构体2、构造双向链表3、编写链表头添加节点方法4、编写删除节点方法5、构造LRU缓存结构体6、编写get方法7、编写put方法什么是LFU ...
    99+
    2022-11-12
  • 手动实现Redis的LRU缓存机制示例详解
    前言 最近在逛博客的时候看到了有关Redis方面的面试题,其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制,然后找了这方面的一些资料与大家分享一下。 LRU总体大概...
    99+
    2022-11-11
  • java实现LRU缓存淘汰算法的方法
    LRU算法:最近最少使用淘汰算法(Least Recently Used)。LRU是淘汰最长时间没有被使用的缓存(即使该缓存被访问的次数最多)。 如何实现LRU缓存淘汰算法 场景: ...
    99+
    2022-11-12
  • LRU缓存算法的实现方法是什么
    这篇文章主要讲解了“LRU缓存算法的实现方法是什么”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“LRU缓存算法的实现方法是什么”吧!LRU就是Least R...
    99+
    2022-10-19
  • Redis如何实现LRU缓存淘汰算法
    小编给大家分享一下Redis如何实现LRU缓存淘汰算法,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!1 标准LRU的实现原理LR...
    99+
    2022-10-19
  • JavaScript如何实现LRU缓存淘汰算法
    目录如何实现LRU缓存淘汰算法使用哈希表和双向链表哈希表实现LRU缓存淘汰算法如何实现LRU缓存淘汰算法 LRU(Least Recently Used)缓存淘汰算法是一种常见的缓存...
    99+
    2023-05-17
    JavaScript LRU缓存淘汰算法 LRU缓存淘汰算法 JavaScript LRU
  • Java如何实现LRU缓存淘汰算法
    这篇文章主要介绍了Java如何实现LRU缓存淘汰算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。概述LRU 算法全称为 Least Recently Used 是一种常见的...
    99+
    2023-06-15
  • JavaScript双向链表实现LRU缓存算法的示例代码
    目录目标什么是LRU简介硬件支持寄存器栈代码实现思路链表节点数据结构链表数据结构LRUCache数据结构完整代码测试目标 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束...
    99+
    2022-11-13
  • Nodejs基于LRU算法实现的缓存处理操作示例
    本文实例讲述了Nodejs基于LRU算法实现的缓存处理操作。分享给大家供大家参考,具体如下: LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是...
    99+
    2022-06-04
    示例 缓存 算法
  • Redis的LRU缓存淘汰算法怎么实现
    本文小编为大家详细介绍“Redis的LRU缓存淘汰算法怎么实现”,内容详细,步骤清晰,细节处理妥当,希望这篇“Redis的LRU缓存淘汰算法怎么实现”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起...
    99+
    2022-10-19
  • JavaScript实现LRU缓存的三种方式详解
    目录分析使用Map实现LRU缓存使用Object + Array实现LRU缓存使用双向链表实现LRU总结LRU全称为Least Recently Used,即最近使用的。针对的是在有...
    99+
    2022-11-13
  • PHP实现LRU算法的原理详解
    1.概念 LRU : 最近最少使用算法 2.代码 <php class Node { public $preKey = null; //链表前一个节点 publ...
    99+
    2022-11-13
  • LRU算法及Apache LRUMap源码实例解析
    目录1. 什么是LRU1.1 自定义实现LRU的要求1.2 Apache LRUMap示例1.2.1 pom依赖1.2.2 demo2. 源码解析2.1 设计2.2 数据结构2.3 ...
    99+
    2022-11-12
  • Spring+EHcache缓存实例详解
    一、ehcahe的介绍EhCache 是一个纯Java的进程内缓存框架,具有高速、精干等特点,是Hibernate中默认的CacheProvider。Ehcache是一种广泛使用的开源Java分布式缓存。主要面向通用缓存,Java EE和轻...
    99+
    2023-05-31
    spring ehcache 缓存
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作