golang分布式缓存项目 Day1 LRU 缓存淘汰策略

:该项目原作者:https://geektutu.com/post/geecache-day1.html。本文旨在记录本人做该项目时的一些疑惑解答以及部分的测试样例以便于本人复习。

LRU缓存淘汰策略

三种缓存淘汰策略

  1. FIFO(First In, First Out)先进先出
    原理:FIFO是一种最简单的缓存淘汰算法,它基于“先进先出”的原则。当缓存满了之后,最早进入缓存的数据将被首先淘汰。
    适用场景:适用于数据访问模式中,数据的访问顺序与数据进入缓存的顺序一致的场景。
    优点:实现简单,公平性较好,每个数据都有相同的淘汰机会。
    缺点:可能会淘汰掉一些频繁访问的数据,导致缓存命中率降低。
  2. LFU(Least Frequently Used)最少使用
    原理:LFU算法淘汰那些在最近一段时间内访问次数最少的数据。它的核心思想是,如果数据在过去被访问得少,那么在未来被访问的可能性也低。
    适用场景:适用于那些访问模式中,某些数据被频繁访问,而其他数据则很少被访问的场景。
    优点:可以有效地保留那些频繁访问的数据,提高缓存的命中率。
    缺点:实现相对复杂,需要跟踪每个数据的访问频率,并且在数据访问模式变化时可能需要调整策略。
  3. LRU(Least Recently Used)最近最少使用
    原理:LRU算法淘汰那些最近最少被使用的数据。它基于这样一个假设:如果数据最近被访问过,那么在未来它被访问的可能性也更高。
    适用场景:适用于那些数据访问模式中,最近访问过的数据在未来很可能再次被访问的场景。
    优点:可以有效地利用缓存空间,提高缓存命中率,是实践中最常用的缓存淘汰算法之一。
    缺点:实现相对复杂,需要维护一个数据访问的时间顺序,以便快速找到最近最少使用的数据。

LRU算法实现

算法图解

在这里插入图片描述
这张图很好地表示了 LRU 算法最核心的 2 个数据结构

  • 绿色的是字典(map),存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1),在字典中插入一条记录的复杂度也是O(1)。
  • 红色的是双向链表(double linked
    list)实现的队列。将所有的值放到双向链表中,这样,当访问到某个值时,将其移动到队尾的复杂度是O(1),在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

具体代码实现

建立缓存池结构体

package projectimport ("container/list"
)type Cache struct {maxBytes  int64nbytes    int64ll        *list.Listcache     map[string]*list.ElementOnEvicted func(key string, value Value)
}type entry struct {key   stringvalue Value
}type Value interface {Len() int
}
  • 在这里我们直接使用 Go 语言标准库实现的双向链表list.List。
  • 字典的定义是 map[string]*list.Element,键是字符串,值是双向链表中对应节点的指针。
  • maxBytes 是允许使用的最大内存,nbytes 是当前已使用的内存,OnEvicted 是某条记录被移除时的回调函数,可以为nil。
  • 键值对 entry 是双向链表节点的数据类型,在链表中仍保存每个值对应的 key 的好处在于,淘汰队首节点时,需要用 key从字典中删除对应的映射。
  • 为了通用性,我们允许值是实现了 Value 接口的任意类型,该接口只包含了一个方法 Len() int,用于返回值所占用的内存大小

PS:list.Element是一个结构体其定义为

type Element struct {// Next and previous pointers in the doubly-linked list of elements.// To simplify the implementation, internally a list l is implemented// as a ring, such that &l.root is both the next element of the last// list element (l.Back()) and the previous element of the first list// element (l.Front()).next, prev *Element// The list to which this element belongs.list *List// The value stored with this element.Value any
}

所以element.Value的值可以是任何类型的,需要我们自己具体实现的时候定义下来.

方便实例化 Cache,实现 New() 函数:

func New(maxBytes int64, onEvicted func(string, Value)) *Cache {return &Cache{maxBytes:  maxBytes,ll:        list.New(),cache:     make(map[string]*list.Element),OnEvicted: onEvicted,}
}

查找功能

实现查找功能,具体步骤如下:

找到了
没找到
查找缓存池
是否找到
从字典中找到对应的双向链表的节点
将其放到双链表队列的队尾代表最近刚刚使用
返回空

代码实现

func (c *Cache) Get(Key string) (value Value, ok bool) {if ele, ok := c.cache[Key]; ok {c.ll.MoveToFront(ele)kv := ele.Value.(*entry)return kv.value, ok}return
}

删除功能

具体步骤如下:

找到双向链表中队首元素
更新内存池中所用的空间nbytes
删掉链表和map对应的元素
如果回调函数不空则调用

代码实现

func (c *Cache) RemoveOldest() {ele := c.ll.Back()if ele != nil {c.ll.Remove(ele)kv := ele.Value.(*entry)delete(c.cache, kv.key)c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())if c.OnEvicted != nil {c.OnEvicted(kv.key, kv.value)}}
}

新增/修改功能

具体步骤:

存在
不存在
超出
查找缓存池中的键是否存在
更新对应节点的值并将其移到链表队尾
对应更新所用内存nbytes
判断是否超出最大内存
将其添加到缓存池和链表队尾中
对应更新所用内存nbytes
循环调用删除函数直至小于最大内存

代码实现

func (c *Cache) Add(key string, value Value) {if ele, ok := c.cache[key]; ok {c.ll.MoveToFront(ele)kv := ele.Value.(*entry)c.nbytes += int64(value.Len()) - int64(kv.value.Len())kv.value = value} else {ele := c.ll.PushFront(&entry{key, value})c.cache[key] = elec.nbytes += int64(len(key)) + int64(value.Len())}for c.maxBytes != 0 && c.maxBytes < c.nbytes {c.RemoveOldest()}
}

测试

测试所用样例及其Len()方法实现

package projectimport ("fmt""testing"
)type String stringfunc (d String) Len() int {return len(String(d))
}type test = []struct {name       stringid         intkey        stringvalue      StringexpectedOk bool
}var tests = test{{id:         1,name:       "test existed key",key:        "key1",value:      "6666",expectedOk: true,},{id:         2,name:       "test existed key",key:        "key2",value:      "1234",expectedOk: true,},{id:         3,name:       "test existed key",key:        "key3",value:      "1111",expectedOk: true,},{id:         4,name:       "test existed key",key:        "key4",value:      "1314",expectedOk: true,},
}

测试增加/修改和删除功能

代码实现

func TestGetAndRemove(t *testing.T) {lru := New(0, nil)for _, tt := range tests {lru.Add(tt.key, tt.value)if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {fmt.Printf("find key%d successfully\n", tt.id)} else {fmt.Printf("find key%d failed\n", tt.id)}}lru.RemoveOldest()for _, tt := range tests {if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {fmt.Printf("find key%d successfully\n", tt.id)} else {fmt.Printf("find key%d failed\n", tt.id)}}
}

测试结果
在这里插入图片描述

测试超出最大容量是能否删除最久未使用的节点

代码实现

func TestOverCapacity(t *testing.T) {lru := New(int64(24), nil)for _, tt := range tests {lru.Add(tt.key, tt.value)fmt.Printf("add key%d successfully, prsent lru usedcap = %d\n", tt.id, lru.nbytes)}for _, tt := range tests {if findkey, ok := lru.Get(tt.key); ok == tt.expectedOk && findkey == tt.value {fmt.Printf("find key%d successfully\n", tt.id)} else {fmt.Printf("find key%d failed\n", tt.id)}}
}

测试结果
在这里插入图片描述

测试回调函数

代码实现

func (c *Cache) CallBack(key string, value Value) {if _, ok := c.Get(key); ok {return} else {c.Add(key, value)c.ll.MoveToFront(c.cache[key])}
}func TestOnEvicted(t *testing.T) {LoseKeys := make([]string, 0)lru := New(int64(8), func(key string, value Value) {LoseKeys = append(LoseKeys, key)})for _, tt := range tests {lru.Add(tt.key, tt.value)fmt.Printf("add key%d successfully, prsent lru usedcap = %d\n", tt.id, lru.nbytes)}for _, tt := range LoseKeys {fmt.Printf("%s被丢弃并保存在日志中\n", tt)}
}

测试结果
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470245.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

工业相机选取

1.相机分类&#xff1a; 1.1 在相机曝光方式中&#xff0c;全局曝光和卷帘曝光是两种主流技术。CCD相机通常采用全局曝光方式&#xff0c;而CMOS相机则可能采用卷帘曝光。 面阵相机与全局曝光关联与区别 关联&#xff1a;面阵相机可以使用全局曝光作为曝光方式&#xff0c;但…

如何查看电脑关机时间

要查看电脑的关机时间&#xff0c;可以按照以下步骤进行操作&#xff1a; 1. 打开事件查看器&#xff1a;按下键盘上的Windows键R键&#xff0c;然后在弹出的运行对话框中输入"eventvwr.msc"&#xff0c;并按下Enter键。 2. 在事件查看器窗口中&#xff0c;单击左侧窗…

jwt用户登录,网关给微服务传递用户信息,以及微服务间feign调用传递用户信息

1、引入jwt依赖 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version></dependency> 2、Jwt工具类&#xff0c;生成token以及解析token package com.niuniu.gateway.uti…

SQL练习(2)

题源&#xff1a;牛客官网 选择题 假设创建新用户nkw&#xff0c;现在想对于任何IP的连接&#xff0c;仅拥有user数据库里面的select和insert权限&#xff0c;则列表语句中能够实现这一要求的语句是&#xff08;&#xff09; A grant select ,insert on *.* to nkw% B grant…

【MySQL从入门到放弃】InnoDB磁盘结构(一)

前言 从MySQL 5.5版本开始默认 使用InnoDB作为引擎&#xff0c;它擅长处理事务&#xff0c;具有自动崩溃恢复的特性&#xff0c;在日常开发中使用非常广泛。 下面是官方的InnoDB引擎架构图&#xff0c;主要分为内存结构和磁盘结构两大部分。 上一篇文章&#xff0c;我们解析了…

RT-DETR融合CVPR[2020]轻量化卷积模块Ghost Module模块

RT-DETR使用教程&#xff1a; RT-DETR使用教程 RT-DETR改进汇总贴&#xff1a;RT-DETR更新汇总贴 《GhostNet: More Features from Cheap Operations》 一、 模块介绍 论文链接&#xff1a;https://arxiv.org/abs/1911.11907 代码链接&#xff1a;GitHub - huawei-noah/Effici…

《TCP/IP网络编程》学习笔记 | Chapter 11:进程间通信

《TCP/IP网络编程》学习笔记 | Chapter 11&#xff1a;进程间通信 《TCP/IP网络编程》学习笔记 | Chapter 11&#xff1a;进程间通信进程间通信的基本概念通过管道实现进程间通信通过管道进行进程间双向通信 运用进程间通信习题&#xff08;1&#xff09;什么是进程间通信&…

2024 kali操作系统安装Docker步骤

1、更新系统 在开始之前&#xff0c;确保你的Kali系统是最新的。打开终端并运行以下命令&#xff1a; apt update 2、安装 apt install docker.io 3、查看启动状态 systemctl status docker 4、安装完 Docker 后&#xff0c;启动 systemctl start docker 5、启动并使…

LLMs之Code:Github Spark的简介、安装和使用方法、案例应用之详细攻略

LLMs之Code&#xff1a;Github Spark的简介、安装和使用方法、案例应用之详细攻略 目录 Github Spark的简介 Github Spark的安装和使用方法 1、安装 2、使用方法 Github Spark的案例应用 Github Spark的简介 2024年10月30日&#xff0c;GitHub 重磅发布GitHub Spark 是一…

MySQL数据库:SQL语言入门 【上】(学习笔记)

SQL&#xff08;Structured Query Language&#xff09;是结构化查询语言的简称&#xff0c;它是一种数据库查询和程序设计语言&#xff0c;同时也是目前使用最广泛的关系型数据库操作语言。&#xff08;95%适用于所有关系型数据库&#xff09; 【 SQL是关系型数据库通用的操作…

腾讯云nginx SSL证书配置

本章教程,记录在使用腾讯云域名nginx证书配置SSL配置过程。 一、nginx配置 域名和证书,替换成自己的即可。证书文件可以自定义路径位置。服务器安全组或者防火墙需要开放80和443端口。 server {#SSL 默认访问端口号为 443listen 443 ssl; #请填写绑定证书的域名server_name c…

使用electron-egg把vue项目在linux Ubuntu环境下打包并安装运行

electron-egg一个入门简单、跨平台、企业级桌面软件开发框架https://www.kaka996.com/electron-egg 跳转地址 1,使用 git下载代码到本地,如果没有git需要进行安装 # gitee git clone https://gitee.com/dromara/electron-egg.git # github git clone https://github.com/dro…

Nginx配置自带的stub状态实现活动监控指标

场景 为了确保应用以最佳性能和精度运行&#xff0c;需要清晰地了解有关其活动的监控指标。 NGINX 提供了多种监控选项&#xff0c;例如 stub 状态。 注&#xff1a; 博客&#xff1a;霸道流氓气质-CSDN博客 实现 启用 NGINX stub 状态 启用 NGINX HTTP 服务器内 locati…

vscode下nuget包的本地引入方法

优势&#xff1a; nuget包的本地引入可以方便打包后的本地测试&#xff0c;确保打包正确、功能完善后再上传至nuget服务端本地引入方式也极为简单&#xff0c;三步操作即可搞定&#xff0c;熟悉之后这个操作2分钟内就可以搞定 具体步骤&#xff08;以引入Epic.RobotService包…

【知识科普】SPA单页应用程序介绍

SPA单页应用程序 概述和传统的多页应用有什么区别&#xff1f;用户体验架构和开发性能和优化SEO&#xff08;搜索引擎优化&#xff09;维护和扩展 如何优化SEO服务端渲染和预渲染有什么区别&#xff1f; 概述 SPA&#xff0c;全称为Single Page Application&#xff08;单页应用…

免费HTML模板和CSS样式网站汇总

HTML模板&#xff1a;&#xff08;注意版权&#xff0c;部分不可商用&#xff09; 1、Tooplate&#xff0c;免费HTML模板下载 Download 60 Free HTML Templates for your websitesDownload 60 free HTML website templates or responsive Bootstrap templates instantly from T…

深入理解接口测试:实用指南与最佳实践5.0(二)

✨博客主页&#xff1a; https://blog.csdn.net/m0_63815035?typeblog &#x1f497;《博客内容》&#xff1a;.NET、Java.测试开发、Python、Android、Go、Node、Android前端小程序等相关领域知识 &#x1f4e2;博客专栏&#xff1a; https://blog.csdn.net/m0_63815035/cat…

【go从零单排】Random Numbers、Number Parsing

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 这里是引用 &#x1f4bb;代码 Random Numbers package mainimport ("fmt…

网页web无插件播放器EasyPlayer.js点播播放器遇到视频地址播放不了的现象及措施

在数字媒体时代&#xff0c;视频点播已成为用户获取信息和娱乐的重要方式。EasyPlayer.js作为一款流行的点播播放器&#xff0c;以其强大的功能和易用性受到广泛欢迎。然而&#xff0c;在使用过程中&#xff0c;用户可能会遇到视频地址无法播放的问题&#xff0c;这不仅影响用户…

mysql5.7安装SSL报错解决(2),总结

Caused by: java.io.EOFException: SSL peer shut down incorrectly 在java里面连接mysql5.7.17数据库&#xff0c;报以上错误&#xff0c; 将数据库升级到mysql5.7.44就可以了。 这两天处理java连接mysql的问题&#xff0c;报了各种错误&#xff0c;总结一下就是openssl和mysq…