groupcache源码(二)-核心数据结构Cache的lru实现

1.简介

groupcache使用Cache(结构体名称)进行数据存储，Cache内部利用lru缓存淘汰策略进行数据淘汰

2. 结构体字段

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{})
// 实现lru的双向链表
	ll    *list.List
// 使用map进行key 双向链表节点指针的存储， 方便数据的快速访问。 ll 双向链表也存储key value 主要用来lru
	cache map[interface{}]*list.Element
}

// A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators
type Key interface{}

type entry struct {
	key   Key
	value interface{}
}

// 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),
	}
}

3. 数据添加/更新

// 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
	}

// 如果键不存在
// 键值对存在entry下，该节点加到对头, 返回Element
	ele := c.ll.PushFront(&entry{key, value})
// map存储该节点
	c.cache[key] = ele
// 如果使用内存大于限制时，删除最少对尾元素
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}

1. 数据存在时，更新值，并将该节点移到对头

2. 数据不存在时，生成新节点，并增加到队头，如果超出内存限制时，删除队尾元素

4. 查找数据

// Get looks up a key's value from the cache.
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
	if c.cache == nil {
// 如果cache 没有初始化 直接返回 false
		return
	}
// 判断map是否有该键
	if ele, hit := c.cache[key]; hit {
// 如果有该键
// 节点移到队头
		c.ll.MoveToFront(ele)
// 返回该值
		return ele.Value.(*entry).value, true
	}
// 不存在该键时 返回false
	return
}

直接通过cache(map结构)查找，如果存在，将该节点移到队头，返回该值，其他情况返回nil, false

5. 删除数据

// 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)
	}
}

如果key在cache中，直接删除该节点

6. 节点删除

func (c *Cache) removeElement(e *list.Element) {
// 双向链表删除该元素
	c.ll.Remove(e)
	kv := e.Value.(*entry)
// map 删除该key
	delete(c.cache, kv.key)
// 执行删除元素的回调函数
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

在删除数据和删除队尾元素时，都调用该方法。该方法将数据删除的同时，会执行对应的回调函数