golang分布式缓存项目 Day 1

注：该项目原作者：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 project

import (
	"container/list"
)

type Cache struct {
	maxBytes  int64
	nbytes    int64
	ll        *list.List
	cache     map[string]*list.Element
	OnEvicted func(key string, value Value)
}

type entry struct {
	key   string
	value 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] = ele
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

测试

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

package project

import (
	"fmt"
	"testing"
)

type String string

func (d String) Len() int {
	return len(String(d))
}

type test = []struct {
	name       string
	id         int
	key        string
	value      String
	expectedOk 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)
	}
}

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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Axure设计之左右滚动组件教程（动态面板）

Axure设计之左右滚动组件教程（动态面板）

很多项目产品设计经常会遇到左右滚动的导航、图片展示、内容区域等&#xff0c;接下来我们用Axure来实现一下左右滚动的菜单导航。通过案例我们可以举一反三进行其他方式的滚动组件设计&#xff0c;如常见的上下滚动、翻页滚动等等。 一、效果展示&#xff1a; 1、点击“向左箭…
阅读更多...
Rust项目结构

Rust项目结构

文章目录 一、module模块1.二进制文件的cargo项目2.库的cargo项目模块中使用crate关键字模块中使用super模块中结构体的访问规则模块中枚举的访问规则模块中use关键字不同模块定义了相同类型冲突解决办法使用pub use导出本模块的函数给外面模块引入外部依赖模块与子模块 小结3.…
阅读更多...
分享：文本转换工具：PDF转图片，WORD转PDF，WORD转图片

分享：文本转换工具：PDF转图片，WORD转PDF，WORD转图片

前言 鉴于网上大多数在线转换工具要么需要收费&#xff0c;要么免费后但转换质量极差的情况&#xff0c;本人开发并提供了PDF转图片&#xff0c;WORD转PDF&#xff0c;WORD转图片等的文本转换工具。 地址 http://8.134.236.93/entry/login 账号 账号&#xff1a;STAR001&a…
阅读更多...
【Linux探索学习】第十一弹——初识操作系统：冯诺依曼体系结构与操作系统的概念与定位

【Linux探索学习】第十一弹——初识操作系统：冯诺依曼体系结构与操作系统的概念与定位

前言&#xff1a; 在学完我们前面的指令和工具之后&#xff0c;今天我们正式开启一个新的内容的学习——进程&#xff0c;在正式讲解进程之前&#xff0c;我们要先进入一些铺垫内容的学习&#xff0c;这就是我们今天要讲的冯诺依曼体系结构和操作系统的概念&#xff0c;下面我们…
阅读更多...
Java：二维数组

Java：二维数组

目录 1. 二维数组的基础格式 1.1 二维数组变量的创建 —— 3种形式 1.2 二维数组的初始化 \1 动态初始化 \2 静态初始化 2. 二维数组的大小 和 内存分配 3. 二维数组的不规则初始化 4. 遍历二维数组 4.1 for循环 ​编辑 4.2 for-each循环 5. 二维数组 与 方法 5.1…
阅读更多...
TVM计算图分割--分割方式

TVM计算图分割--分割方式

文章目录 TVM中的计算图分割方式1. Partition Pass2. dataflow_pattern3. 内置图分割接口4. Pipeline Executor5. BYOC框架6. UMA深度学习模型通常是用计算图来表示的。计算图是一种有向无环图，其中节点代表算子，表示一个操作，节点之间的边表示算子之间的数据依赖。计算图分…
阅读更多...
RNA-seq 差异分析的点点滴滴（1）

RNA-seq 差异分析的点点滴滴（1）

引言 本系列[1])将开展全新的转录组分析专栏&#xff0c;主要针对使用DESeq2时可能出现的问题和方法进行展开。 为何使用未经标准化的计数数据&#xff1f; DESeq2 工具包在接收输入时&#xff0c;期望得到的是未经处理的原始计数数据&#xff0c;比如从 RNA-seq 或其他高通量测…
阅读更多...
基于单片机的观赏类水草养殖智能控制系统的设计（论文+源码）

基于单片机的观赏类水草养殖智能控制系统的设计（论文+源码）

1总体设计 通过需求分析&#xff0c;本设计观赏类水草养殖智能控制系统的总体架构如图2.1所示&#xff0c;为系统总体设计框图。系统采用STM32单片机作为系统主控核心&#xff0c;利用DS18B20温度传感器、TDS传感器、CO2传感器、光敏传感器实现水草养殖环境中水温、CO2浓度、T…
阅读更多...
中兴光猫修改SN，MAC，修改地区，异地注册，改桥接，路由拨号

中兴光猫修改SN，MAC，修改地区，异地注册，改桥接，路由拨号

前言 请先阅读上一篇博客获取到光猫超级密码电信光猫获取超级密码 电信光猫天翼网关4.0获取超级密码教程 四川电信光猫 中兴 F1855V2 ZXHN F1855V2 telent权限 实战 实测_天翼4.0光猫超级密码-CSDN博客 修改SN-修改地区&#xff0c;光猫异地注册&#xff0c;设置桥接模式&#…
阅读更多...
基于卷积神经网络的农作物病虫害识别系统（pytorch框架，python源码）

基于卷积神经网络的农作物病虫害识别系统（pytorch框架，python源码）

更多图像分类、图像识别、目标检测等项目可从主页查看 功能演示&#xff1a; 基于卷积神经网络的农作物病虫害检测&#xff08;pytorch框架&#xff09;_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积神经网络的农作物病虫害识别系统是在pytorch框架下实现的…
阅读更多...
aardio 5分钟多线程开发简单入门

aardio 5分钟多线程开发简单入门

废话不多说 直接开干&#xff01; 借用作者话说 虽然 aardio 的多线程开发非常简单&#xff0c;但是&#xff1a; 1、请先了解:「多线程」开发比「单线程」开发更复杂这个残酷的现实。 2、请先了解: aardio 这样的动态语言可以实现真多线程非常罕见。 建议先找任意的编程语言试…
阅读更多...
PMP–知识卡片--人才九宫格

PMP–知识卡片--人才九宫格

在人才盘点时&#xff0c;根据人才的绩效和潜能&#xff0c;分别作为横坐标和纵坐标&#xff0c;将人才盘点的结果划分为9个象限&#xff0c;人才分为九个类别&#xff0c;以便于分类管理&#xff0c;因材施教。
阅读更多...
1.每日SQL----2024/11/7

1.每日SQL----2024/11/7

题目&#xff1a; 计算用户次日留存率,即用户第二天继续登录的概率 表&#xff1a; iddevice_iddate121382024-05-03232142024-05-09332142024-06-15465432024-08-13523152024-08-13623152024-08-14723152024-08-15832142024-05-09932142024-08-151065432024-08-131123152024-…
阅读更多...
解决yum命令报错“Could not resolve host: mirrorlist.centos.org

解决yum命令报错“Could not resolve host: mirrorlist.centos.org

这个主要是yum源出了问题或者服务器网络有问题&#xff0c;检查网络排除网络问题后&#xff0c;可更换源 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.k wget -O /etc/yum.repos.d/CentOS-Base.repo https://mirrors.huaweicloud.com/repository…
阅读更多...
qt QColorDialog详解

qt QColorDialog详解

1、概述 QColorDialog是Qt框架中的一个对话框类&#xff0c;专门用于让用户选择颜色。它提供了一个标准的颜色选择界面&#xff0c;其中包括基本的颜色选择器&#xff08;如调色板和颜色轮&#xff09;、自定义颜色输入区域以及预定义颜色列表。QColorDialog支持RGB、HSV和十六…
阅读更多...
得物多模态大模型在重复商品识别上的应用和架构演进

得物多模态大模型在重复商品识别上的应用和架构演进

重复商品治理介绍 根据得物的平台特性&#xff0c;同一个商品在平台上不能出现多个链接&#xff0c;原因是平台需要保证一品一链的特点&#xff0c;以保障商品的集中竞价&#xff0c;所以说一个商品在整个得物平台上只能有一个商详链接&#xff0c;因此我们需要对一品多链的情…
阅读更多...
第二十九篇——线性代数：“矩阵”到底怎么用？

第二十九篇——线性代数：“矩阵”到底怎么用？

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华 一、背景介绍 数学中的线性代数&#xff0c;再生活中的落地和应用&#xff0c;是我这个…
阅读更多...
【dvwa靶场：XSS系列】XSS (Reflected)低-中-高级别，通关啦

【dvwa靶场：XSS系列】XSS (Reflected)低-中-高级别，通关啦

一、低级low 简单拿捏 <script>alert(123)</script>二、中级middle 源码过滤了script但是没有过滤大小写&#xff0c;改成大写S <Script>alert(123)</script>三、高级high 比中级高&#xff0c;过滤了script并且以及大小写&#xff0c;使用其他标…
阅读更多...
如何使用Varjo直接观看Blender内容

如何使用Varjo直接观看Blender内容

最近&#xff0c;开源的3D建模程序Blender为Varjo提供了出色的OpenXR支持&#xff0c;包括四视图和凹进渲染扩展。但是在Blender中&#xff0c;默认不启用VR场景检查。要开始使用VR场景检查&#xff0c;只需遵循以下步骤&#xff1a; 1. 下载并安装Blender 2.启用Blender VR场景…
阅读更多...
Any 的原理以及实现

Any 的原理以及实现

序言 在 C17 的更新中引入了一个特别有意思的类型&#xff0c;它提供了一种通用的方式来存储任何类型的数据而不需要提前指定类型&#xff0c; 该类型就是 any。  any 允许你将任意类型的数据存储在一个容器中&#xff0c;并且能够在运行时动态地访问该数据。话不多说&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023