专栏首页C/C++基础Golang groupcache LRU 缓存简介与用法

Golang groupcache LRU 缓存简介与用法

1.LRU

LRU(Least Recently Used,最近最久未使用算法)是一种常见的缓存淘汰算法,当缓存满时,淘汰最近最久未使用的元素,在很多分布式缓存系统(如Redis, Memcached)中都有广泛使用。其基本思想是如果一个数据在最近一段时间没有被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当缓存满时,最久未被访问的数据最先被淘汰。具体做法是将最近使用的元素存放到靠近缓存顶部的位置,当一个新条目被访问时,LRU 将它放置到缓存的顶部。当缓存满时,较早之前访问的条目将从缓存底部被移除。

2.groupcache LRU Cache 简介

在 Go 中,如果想使用 LRU 缓存,可以使用 Google Golang 团队官方出品的开源库 groupcache ,开源地址见 Github.groupcache。LRU 缓存通过 groupcache/lru/lru.go实现,它主要是封装了一系列 LRU 缓存操作的相关的接口。主要有:

//创建一个 LRU Cache
func New(maxEntries int) *Cache
 
//向 Cache 中插入一个 KV
func (c *Cache) Add(key Key, value interface{})

//从 Cache 中获取一个 key 对应的 value
func (c *Cache) Get(key Key) (value interface{}, ok bool)

//从 Cache 中删除一个 key
func (c *Cache) Remove(key Key)

//从 Cache 中删除最久未被访问的数据
func (c *Cache) RemoveOldest()

//获取 Cache 中当前的元素个数
func (c *Cache) Len()

//清空 Cache
func (c *Cache) Clear()

注意,groupcache 中实现的 LRU Cache 并不是并发安全的,如果用于多个 Go 程并发的场景,需要加锁。

当然,除了使用 groupcache 的 LRU Cache,其他开源的库也可以参考一下,比如 HashiCorp 公司推出的 golang-lru

3.源码剖析

LRU Cache 基于 map 与 list,map 用于快速检索,list 用于实现 LRU。具体实现如下:

package lru

import "container/list"

//Cache 是一个 LRU Cache,注意它并不是并发安全的
type Cache struct {
	//MaxEntries 是 Cache 中实体的最大数量,0 表示没有限制
	MaxEntries int
	
	//OnEvicted 是一个可选的回调函数,当一个实体从 Cache 中被移除时执行
	OnEvicted func(key Key, value interface{})
	
	//ll是一个双向链表指针,执行一个 container/list 包中的双向链表
	ll *list.List
	
	//cache 是一个 map,存放具体的 k/v 对,value 是双向链表中的具体元素,也就是 *Element
	cache map[interface{}]*list.Element
}

//key 是接口,可以是任意类型
type Key interface{}

//一个 entry 包含一个 key 和一个 value,都是任意类型
type entry struct {
	key   Key
	value interface{}
}

//创建一个 LRU Cache。maxEntries 为 0 表示缓存没有大小限制
func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,
		ll:         list.New(),
		cache:      make(map[interface{}]*list.Element),
	}
}

//向 Cache 中插入一个 KV
func (c *Cache) Add(key Key, value interface{}) {
	if c.cache == nil {
		c.cache = make(map[interface{}]*list.Element)
		c.ll = list.New()
	}
	if ee, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ee)
		ee.Value.(*entry).value = value
		return
	}
	ele := c.ll.PushFront(&entry{key, value})
	c.cache[key] = ele
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}

//传入一个 key,返回一个是否有该 key 以及对应 value
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value, true
	}
	return
}

//从 Cache 中删除一个 KV
func (c *Cache) Remove(key Key) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.removeElement(ele)
	}
}

//从 Cache 中删除最久未被访问的数据
func (c *Cache) RemoveOldest() {
	if c.cache == nil {
		return
	}
	ele := c.ll.Back()
	if ele != nil {
		c.removeElement(ele)
	}
}

//从 Cache 中删除一个元素,供内部调用
func (c *Cache) removeElement(e *list.Element) {
	//先从 list 中删除
	c.ll.Remove(e)
	
	kv := e.Value.(*entry)

	//再从 map 中删除
	delete(c.cache, kv.key)
	
	//如果回调函数不为空则调用
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

//获取 Cache 当前的元素个数
func (c *Cache) Len() int {
	if c.cache == nil {
		return 0
	}
	return c.ll.Len()
}

//清空 Cache
func (c *Cache) Clear() {
	if c.OnEvicted != nil {
		for _, e := range c.cache {
			kv := e.Value.(*entry)
			c.OnEvicted(kv.key, kv.value)
		}
	}
	c.ll = nil
	c.cache = nil
}

4.使用示例

从上面的源码分析来看,groupcache 实现的 LRU Cache 还是比较简单的,Google 一直秉持着简单易用的设计理念,可见一斑。下面看一个使用示例。

package main

import (
	"fmt"
	"github.com/groupcache/lru"
)

func main() {
	cache := lru.New(2)
	cache.Add("bill", 20)
	cache.Add("dable", 19)
	v, ok := cache.Get("bill")
	if ok {
		fmt.Printf("bill's age is %v\n", v)
	}
	cache.Add("cat", "18")
	
	fmt.Printf("cache length is %d\n", cache.Len())
	_, ok = cache.Get("dable")
	if !ok {
		fmt.Printf("dable was evicted out\n")
	}
}

编译运行输出:

bill's age is 20
cache length is 2
dable was evicted out

参考文献

[1] Github.groupcache [2] 缓存淘汰算法(LFU、LRU、ARC、FIFO、MRU)分析 [3] groupcache 源码分析(二)-- LRU

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C的全缓冲、行缓冲和无缓冲

    基于流的操作最终会调用read或者write函数进行I/O操作。为了使程序的运行效率最高,流对象通常会提供缓冲区,以减少调用系统I/O库函数的次数。

    Dabelv
  • Linux命令(3)——sed命令

    sed(Stream EDitor)是一种流文件编辑器,它一次处理一行内容。处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(pattern spac...

    Dabelv
  • Linux命令(3)——sed命令

    sed(Stream EDitor)是一种流文件编辑器,它一次处理一行内容。处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(Pattern Spac...

    Dabelv
  • Hadoop学习笔记—18.Sqoop框架学习

      Hadoop正成为企业用于大数据分析的最热门选择,但想将你的数据移植过去并不容易。Apache Sqoop正在加紧帮助客户将重要数据从数据库移到Hadoop...

    Edison Zhou
  • 你还在命令行下管理 Redis 吗?是时候使用这款全平台客户端工具了!

    今天发现一个不错的 Redis 客户端工具:AnotherRedisDesktopManager。

    iMike
  • Git基本命令 -- 历史

    历史. 收先需要了解一下git log命令, 使用git的帮助看看: git help log: 执行该命令后, 我的win10弹出来一个html页面, 里面是...

    solenovex
  • 撮合引擎开发:缓存和MQ

    虽然现在只用到了 Redis 一个中间件,但设计个 middleware 包,会方便以后扩展添加其他中间件,如 Kafka 或 RocketMQ 等。

    Keegan小钢
  • Nmap扫描结果的保存和输出 原

    该选项可将扫描结果以标准格式、XML格式和Grep格式一次性保存,分别放在.nmap,.xml和.gnmap文件中。

    青木
  • 171 Excel Sheet Column Number

    /** * 题意:A表示1 B表示2 AA表示27 AB表示28 ------>给你一串字符串输出相应的数字 * 分析:这个就类似于二进制转十进制,从...

    用户1624346
  • 20180818_ARTS_week08

    这道题是要把字符串中的数字变成 int,通常的做法是遍历字符串,然后判断是不是在 0~9 中,如果把 0~9 放数组里每次循环检查感觉不是太好,时间复杂度是个 ...

    Bob.Chen

扫码关注云+社区

领取腾讯云代金券