Golang lru算法

groupcache lru算法

groupcache 中的 lru 算法是定义在 lru 文件夹下面的 lru.go 文件里面，lru 算法的具体实现就是使用的 Golang 中的 list，将最近被访问的移动到 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")
	}
}

执行完毕后，控制台输出如下：

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

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，用于实现缓存的查找，map 的键为 interface 类型的，也就是说键可以是任意类型。但必须是可以比较的。

缓存的值是 *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 语言中的链表来实现的，新增一个元素就放到链表的首部，访问一个元素，也是将其移到链表的首部，如果容量超出了链表的长度，那么就从链表尾删除元素即可。