Groupcache 介绍

Groupcache 是一个内存级别的分布式缓存，在许多情况下可以替代 memcached 节点池。

和 memcached 比较

相同点

Groupcache 与 memcached 相比，相同点在于：

按照 key 进行切分，用于选择哪个节点对该 key 负责。

不同点

不同点在于：

不需要运行一组单独的服务器。groupcache 是一个客户端，也是一个服务器。它连接到自己的 peer，形成分布式缓存。
带有缓存填充机制。memcached 只是说“缓存丢失”，这通常会导致来自无限数量的客户端连接数据库（或其他）加载缓存。而 groupcache 协调缓存填充，使得整个复制的一组进程中只有一个加载填充缓存（singleflight），然后将加载的值多路传输给所有调用方。
不支持变更 values。既没有缓存过期时间，也不能显式的从缓存中删除。
支持将热点条目自动镜像到多个进程。对于热点条目，自动镜像到多个节点，这样可以防止单点存储热点数据的服务器过载。

LRU

LRU，Least Recently Used，最近最少使用。如果数据最近被访问过，那么将来被访问的概率也会更高。

LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。

数据结构

下图就是 LRU 的数据结构：

蓝色的是字典，用于保存 key 和 value 的映射关系。
红色的是双向链表（作为队列），将所有的值存储在双向链表中。头部代表最近被访问的数据，尾部代表最久未被访问过的数据。
- 当访问到值时将这个元素移动到双向链表的头部。
- 如果需要删除最近最久未被访问的数据，只需要删除尾部元素即可。

LRU Cache

entry 条目

lru.entry 定义了存储在双向链表中的条目，包括键（key）和值（value）。

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

Cache 结构体

lru.Cache 是一个 LRU 缓存，其中：

MaxEntries 定义了缓存中最大的数据量。
ll 为双向链表。
cache 为键和值的映射。
OnEvicted 定义了当这个键从缓存中移除时，需要进行的操作。

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

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

同时 lru.Cache 还定义了一些对于缓存的操作：

添加键值对：

这里用了懒惰初始化的方法，当真正需要添加数据时才对双向链表和字典映射做初始化。
当看key 对应的数据存在时，将元素移动到链表头部，然后改变 value。
不存在时新建一个元素，将元素移动到链表头部。
当超过缓存数据量限制时，删除最老的缓存数据。

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

查询键所对应的数值：

1	func (c *Cache) Get(key Key) (value interface{}, ok bool)

键值删除：在删除时会调用 OnEvicted 所定义的函数。
1
func (c *Cache) Remove(key Key)
获取缓存当前大小：
1
func (c *Cache) Len() int
清空缓存：
1
func (c *Cache) Clear()

ByteView

ByteView 保证的内部字节的不可变（这是 groupcache 的特性，不可更改 value）。

ByteView 结构体

ByteView 在内部封装着一个字节切片和其对应的字符串，但是调用者看不见这个内部细节。

// A ByteView holds an immutable view of bytes.
// Internally it wraps either a []byte or a string,
// but that detail is invisible to callers.
//
// A ByteView is meant to be used as a value type, not
// a pointer (like a time.Time).
type ByteView struct {
   // If b is non-nil, b is used, else s is used.
   b []byte
   s string
}

ByteView 方法

ByteView 定义了很多方法，并且还实现了 io.ReaderAt 和 io.WriterTo 接口：

查询 ByteView 的长度：
1
func (v ByteView) Len() int
获取一个字节切片的复制：
1
func (v ByteView) ByteSlice() []byte
获取字节切片对应的字符串：
1
func (v ByteView) String() string
获取字节切片中下标为 i 的字节：
1
func (v ByteView) At(i int) byte

获取 [from, to) 范围内的字节：

1	func (v ByteView) Slice(from, to int) ByteView

获取 [from, end) 范围内的字节：

1	func (v ByteView) SliceFrom(from int) ByteView

将字节切片复制到指定的切片中，返回被复制的字节数：
1
func (v ByteView) Copy(dest []byte) int

用于比较的方法：

func (v ByteView) Equal(b2 ByteView) bool

func (v ByteView) EqualString(s string) bool

func (v ByteView) EqualBytes(b2 []byte) bool

返回一个 io.ReadSeeker：

// Reader returns an io.ReadSeeker for the bytes in v.
func (v ByteView) Reader() io.ReadSeeker {
   if v.b != nil {
      return bytes.NewReader(v.b)
   }
   return strings.NewReader(v.s)
}

实现 io.ReaderAt 和 io.WriterTo 接口：

// ReadAt implements io.ReaderAt on the bytes in v.
func (v ByteView) ReadAt(p []byte, off int64) (n int, err error) {
   if off < 0 {
      return 0, errors.New("view: invalid offset")
   }
   if off >= int64(v.Len()) {
      return 0, io.EOF
   }
   n = v.SliceFrom(int(off)).Copy(p)
   if n < len(p) {
      err = io.EOF
   }
   return
}

// WriteTo implements io.WriterTo on the bytes in v.
func (v ByteView) WriteTo(w io.Writer) (n int64, err error) {
   var m int
   if v.b != nil {
      m, err = w.Write(v.b)
   } else {
      m, err = io.WriteString(w, v.s)
   }
   if err == nil && m < v.Len() {
      err = io.ErrShortWrite
   }
   n = int64(m)
   return
}

Dawn's Blogs

Groupcache源码阅读 (1) LRU和ByteView