企业官网建设流程全解析

1.LRU

LRU（Least Recently Used）最久未被使用是一种常见的缓存淘汰算法，当缓存满时，淘汰最近最久未使用的元素。

LRU 在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU 基本思想是如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当缓存满时，最久未被访问的数据最先被淘汰。具体做法是将最近使用的元素存放到靠近缓存顶部的位置，当一个新条目被访问时，LRU 将它放置到缓存的顶部。当缓存满时，较早之前访问的条目将从缓存底部被移除。

2.groupcache LRU Cache 简介

在 Go 中，如果想使用 LRU 缓存，可以使用 Google Golang 团队官方出品的开源库 groupcache。

LRU 缓存通过groupcache/lru/lru.go实现，它主要是封装了一系列 LRU 缓存操作的相关接口。主要有：

//创建一个 LRU CachefuncNew(maxEntriesint)*Cache//向 Cache 中插入一个 KVfunc(c*Cache)Add(key Key,valueinterface{})//从 Cache 中获取一个 key 对应的 valuefunc(c*Cache)Get(key Key)(valueinterface{},okbool)//从 Cache 中删除一个 keyfunc(c*Cache)Remove(key Key)//从 Cache 中删除最久未被访问的数据func(c*Cache)RemoveOldest()//获取 Cache 中当前的元素个数func(c*Cache)Len()//清空 Cachefunc(c*Cache)Clear()

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

当然，除了使用 groupcache 的 LRU Cache，其他开源的库也可以参考一下，比如：

• Allegro 公司推出的 bigcache。
• HashiCorp 公司推出的 golang-lru。
• 零GC开销和高并发性能缓存 coocood/freecache。
• 简单的内 KV 缓存 patrickmn/go-cache。

3.源码剖析

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

packagelruimport"container/list"//Cache 是一个 LRU Cache，注意它并不是并发安全的typeCachestruct{//MaxEntries 是 Cache 中实体的最大数量，0 表示没有限制MaxEntriesint//OnEvicted 是一个可选的回调函数，当一个实体从 Cache 中被移除时执行OnEvictedfunc(key Key,valueinterface{})//ll是一个双向链表指针，执行一个 container/list 包中的双向链表ll*list.List//cache 是一个 map，存放具体的 k/v 对，value 是双向链表中的具体元素，也就是 *Elementcachemap[interface{}]*list.Element}//key 是接口，可以是任意类型typeKeyinterface{}//一个 entry 包含一个 key 和一个 value，都是任意类型typeentrystruct{key Key valueinterface{}}//创建一个 LRU Cache。maxEntries 为 0 表示缓存没有大小限制funcNew(maxEntriesint)*Cache{return&Cache{MaxEntries:maxEntries,ll:list.New(),cache:make(map[interface{}]*list.Element),}}//向 Cache 中插入一个 KVfunc(c*Cache)Add(key Key,valueinterface{}){ifc.cache==nil{c.cache=make(map[interface{}]*list.Element)c.ll=list.New()}ifee,ok:=c.cache[key];ok{c.ll.MoveToFront(ee)ee.Value.(*entry).value=valuereturn}ele:=c.ll.PushFront(&entry{key,value})c.cache[key]=eleifc.MaxEntries!=0&&c.ll.Len()>c.MaxEntries{c.RemoveOldest()}}//传入一个 key，返回一个是否有该 key 以及对应 valuefunc(c*Cache)Get(key Key)(valueinterface{},okbool){ifc.cache==nil{return}ifele,hit:=c.cache[key];hit{c.ll.MoveToFront(ele)returnele.Value.(*entry).value,true}return}//从 Cache 中删除一个 KVfunc(c*Cache)Remove(key Key){ifc.cache==nil{return}ifele,hit:=c.cache[key];hit{c.removeElement(ele)}}//从 Cache 中删除最久未被访问的数据func(c*Cache)RemoveOldest(){ifc.cache==nil{return}ele:=c.ll.Back()ifele!=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)//如果回调函数不为空则调用ifc.OnEvicted!=nil{c.OnEvicted(kv.key,kv.value)}}//获取 Cache 当前的元素个数func(c*Cache)Len()int{ifc.cache==nil{return0}returnc.ll.Len()}//清空 Cachefunc(c*Cache)Clear(){ifc.OnEvicted!=nil{for_,e:=rangec.cache{kv:=e.Value.(*entry)c.OnEvicted(kv.key,kv.value)}}c.ll=nilc.cache=nil}

4.使用示例

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

packagemainimport("fmt""github.com/groupcache/lru")funcmain(){cache:=lru.New(2)cache.Add("bill",20)cache.Add("dable",19)v,ok:=cache.Get("bill")ifok{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

参考文献

Github.groupcache
缓存淘汰算法（LFU、LRU、ARC、FIFO、MRU）分析
groupcache 源码分析（二）-- LRU