groupcache 中的 LRU

lru 是一种缓存算法, 没什么可讲的, 维基百科介绍:

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes. LRU is actually a family of caching algorithms with members including 2Q by Theodore Johnson and Dennis Shasha,[3]
and LRU/K by Pat O’Neil, Betty O’Neil and Gerhard Weikum.[4]

一般来讲, 需要一个双向链表来实现, 在 go 语言内, 已经提供了相应包container/list:

func (e *Element) Next() *Element  //返回该元素的下一个元素,如果没有下一个元素则返回nil
func (e *Element) Prev() *Element//返回该元素的前一个元素,如果没有前一个元素则返回nil。
func New() *List //返回一个初始化的list
func (l *List) Back() *Element //获取list l的最后一个元素
func (l *List) Front() *Element //获取list l的第一个元素
func (l *List) Init() *List  //list l初始化或者清除list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  //在list l中元素mark之后插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element//在list l中元素mark之前插入一个值为v的元素,并返回该元素,如果mark不是list中元素,则list不改变。
func (l *List) Len() int //获取list l的长度
func (l *List) MoveAfter(e, mark *Element)  //将元素e移动到元素mark之后,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveBefore(e, mark *Element)//将元素e移动到元素mark之前,如果元素e或者mark不属于list l,或者e==mark,则list l不改变。
func (l *List) MoveToBack(e *Element)//将元素e移动到list l的末尾,如果e不属于list l,则list不改变。
func (l *List) MoveToFront(e *Element)//将元素e移动到list l的首部,如果e不属于list l,则list不改变。
func (l *List) PushBack(v interface{}) *Element//在list l的末尾插入值为v的元素,并返回该元素。
func (l *List) PushBackList(other *List)//在list l的尾部插入另外一个list,其中l和other可以相等。
func (l *List) PushFront(v interface{}) *Element//在list l的首部插入值为v的元素,并返回该元素。
func (l *List) PushFrontList(other *List)//在list l的首部插入另外一个list,其中l和other可以相等。
func (l *List) Remove(e *Element) interface{}//如果元素e属于list l,将其从list中删除,并返回元素e的值。

lru.go

// Add adds a value to the cache.
// 如果已经包含该key, 就移动到首部, 并更新 value
// 否则移动到首部, 增加缓存
// 如果超出数量限制, 移除最近最少使用 即 lru
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()
  }
}

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

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

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

// 从链表中删除
// 从缓存中删除
// 回调
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)
  }
}

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

短短100来行代码, 精简至极, 实乃 go语言典范, 简洁高可读,无炫技,无花头, 比js不知道高到哪里去了, 如大家所知, 并发编程需要保证线程安全的,
如果有空的话, 接下来看看groupcache 如何实现的