groupcache lru算法

groupcache 中的 lru 算法是定义在 lru 文件夹下面的 lru.go 文件里面,lru 算法的具体实现就是使用的 中的 ,将最近被访问的移动到 list 的开头,每次添加元素时,判断是否达到了链表的最大长度,如果达到了,则直接失败链表的最后一个元素即可。

我们先写个代码,看具体如何使用,具体代码如下:

package main import ( "fmt" "github.com/golang/groupcache/lru" ) func main(){ fmt.Println("嗨客网(www.haicoder.net)") // 使用New创建一个Cache对象,设置最大存储5个元素 cache := lru.New(5) //设置删除元素时的回调 cache.OnEvicted = func(key lru.Key, value interface{}) { fmt.Println("Remove key ", key) } //向Cache添加三个元素,这里的键和值可以是任意类型,但键必须是可比较的 cache.Add("name", "haicoder") cache.Add("url", "haicoder.net") cache.Add("age", 109) //获取键为url的值 if val, isOk := cache.Get("url"); isOk{ fmt.Println("Get key url =", val) }else{ fmt.Println("Get key url err") } //再次添加两个元素 cache.Add("isok", true) cache.Add("cname", "嗨客网") //再次获取元素 if val, isOk := cache.Get("url"); isOk{ fmt.Println("Get key url =", val) }else{ fmt.Println("Get key url err") } //此时,再次添加一个元素,容量已经超过了我们设置的最大容量5 // 此时会删除键,并调用删除的回调 cache.Add("isonline", true) //此时,我们再次获取name,键已经不存在,被删除了 // 因为超出了最大容量,将最久的键删除了 if val, isOk := cache.Get("name"); isOk{ fmt.Println("Get key name =", val) }else{ fmt.Println("Get key name err") } }

执行完毕后,控制台输出如下:

01_groupcache源码扩展.png

我们看到,当容量超出最大容量之后,最旧的键被删除了。

groupcache lru源码解析

我们查看 lru.go 文件,首先看到的是 Cache 结构体,具体代码如下:

// Cache is an LRU cache. It is not safe for concurrent access. type Cache struct { // MaxEntries is the maximum number of cache entries before // an item is evicted. Zero means no limit. MaxEntries int // OnEvicted optionally specifies a callback function to be // executed when an entry is purged from the cache. OnEvicted func(key Key, value interface{}) ll *list.List cache map[interface{}]*list.Element }

Cache 是缓存的主结构体,其中,MaxEntries 是缓存的最大容量,缓存的数量超出该值,将会被删除。OnEvicted 是当删除某个键时的回调函数。 ll 就是一个 List,存放所有的元素,当新增元素时,就放到链表的开头。 cache 是一个 ,用于实现缓存的查找,map 的键为 类型的,也就是说键可以是任意类型。但必须是可以比较的。

缓存的值是 *list.Element 类型的,这里为什么是 *list.Element 类型是因为 list 的所有操作几乎都是基于 *list.Element 类型的,因此,这里使用 *list.Element 类型方便从 cache 里面删除元素和添加元素。

lru 一共就暴露了七个接口,具体接口的解释如下:

接口 作用
New 创建一个 Cache
Add 向 Cache 里面添加元素
Get 从 Cache 里面获取元素
Remove 从 Cache 里面删除一个键
RemoveOldest 从 Cache 里面删除最久的元素
Len 缓存的长度
Clear 清空缓存的所有元素

在看具体接口实现之前,我们首先看一个结构体,具体定义如下:

type Key interface{} type entry struct { key Key value interface{} }

很简单,就是首先定义了一个 Key 是一个接口类型的,接着,定义了一个缓存的实体 entry,就是一个 key 和 value。现在,我们看 New 接口,具体代码如下:

// New creates a new Cache. // If maxEntries is zero, the cache has no limit and it's assumed // that eviction is done by the caller. func New(maxEntries int) *Cache { return &Cache{ MaxEntries: maxEntries, ll: list.New(), cache: make(map[interface{}]*list.Element), } }

New 接口就是返回一个 Cache 对象,并且将一些字段设置默认值而已。接着,我们看 Add 接口,具体代码如下:

// Add adds a value to the cache. 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() } }

首先,判断 Cache 对象的 cache 属性是否为空,如果为空,则直接 make 下,并且同时,将 Cache 对象的 ll 属性也创建下。接着,判断键是否在 cache 里,如果已经存在了,则直接将其移到链表首,并且更新该键的元素值,此时就实现了最近被访问的元素放到链表的头部,如果元素不存在,那直接使用 PushFront 将缓存实体存入到链表头部,并放入到 map 中,最后,如果缓存的最大容量不为 0,并且当前的长度已经大于了最大长度,那么就删除最旧的那个元素。

现在,我们来看 Get 接口,具体代码如下:

// Get looks up a key's value from the cache. 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 }

直接从 map 里面获取元素,如果获取到了,则使用 MoveToFront 将元素放到链表的最开始,同样,这样做是为了实现 lru,最后返回链表的值即可。接着,我们查看 Remove 函数,具体实现如下:

// Remove removes the provided key from the cache. func (c *Cache) Remove(key Key) { if c.cache == nil { return } if ele, hit := c.cache[key]; hit { c.removeElement(ele) } }

Remove 函数直接调用的是 removeElement 函数,我们看 removeElement 函数的具体实现,代码如下:

func (c *Cache) removeElement(e *list.Element) { c.ll.Remove(e) kv := e.Value.(*entry) delete(c.cache, kv.key) if c.OnEvicted != nil { c.OnEvicted(kv.key, kv.value) } }

首先,调用链表本身的 Remove 方法,用于删除一个元素,接着,再使用 delete 从 map 中删除该元素,最后,如果有回调,那么就调用回调函数即可。接着,我们看 RemoveOldest 函数,具体代码如下:

// RemoveOldest removes the oldest item from the cache. func (c *Cache) RemoveOldest() { if c.cache == nil { return } ele := c.ll.Back() if ele != nil { c.removeElement(ele) } }

该函数的思想就是使用链表的 Back 获取链表尾元素,然后调用 removeElement 将其删除即可。接着,就是链表的长度函数,具体代码如下:

// Len returns the number of items in the cache. func (c *Cache) Len() int { if c.cache == nil { return 0 } return c.ll.Len() }

该函数非常简单,直接获取链表的长度即可,最后,我们看 Clear 函数,具体代码如下:

// Clear purges all stored items from the 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 }

该函数的思想就是如果以后回调函数,也就是 OnEvicted 不为空,那么就遍历 map,对 map 中的每一个元素调用回调函数。最后,直接将链表和 map 设置为 nil 即可。

groupcache lru算法总结

其实整体的算法非常的简单与清晰,就是借助了 Go 语言中的链表来实现的,新增一个元素就放到链表的首部,访问一个元素,也是将其移到链表的首部,如果容量超出了链表的长度,那么就从链表尾删除元素即可。