groupcache源码分析

1.源文件作用

consistanthash.go: 实现一致性哈希,使得每一个同样的key得到的结果都是一样的.用途是找一个合适的node,使得负载均衡
lru.go: 顾名思义,这是实现了一个最近最少使用的算法,用于淘汰最不活跃的item
singleflight.go: 用于处理多个带相同key的请求,使得只有其中一个被处理,另外的直接使用被处理的那个请求的结果,然后直接返回.
byteview.go: 用于封装[]byte和string,对外无差别使用
http.go: http的封装
peers.go: 单个node的一些实现,例如:注册节点…
sinks.go: 结合byteview,实现对[]byte,string,proto的数据封装
groupcache.go: 库入口,对外提供主api.

2.consistanthash解析

consistanthash.go原文件中,有一个Map来保存一个key到该key的哈希,结构是这样:

type Map struct {
	hash     Hash
	replicas int
	keys     []int // Sorted
	hashMap  map[int]string
}

hash为哈希函数,如果传进的是nil那么就用默认的crc32.ChecksumIEEE,replicas就是虚拟桶的概念,即将一个key存到多个桶里面,使得分配更加均匀,负载更加均衡.[]keys里面就是排好序的哈希值,hashMap存哈希值到key的映射.该Map的Get方法:

	hash := int(m.hash([]byte(key)))

	// Binary search for appropriate replica.
	idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })
    ...
    return m.hashMap[m.keys[idx]]

会将任意一个key的哈希值计算出来,取第一个大于 []keys中保存的那个哈希值,然后取出存在对应hashMap的key.举个例子:

    c := consistenthash.New(70, nil)
	c.Add("A", "B", "C", "D", "E")
	for _, key := range []string{"what", "nice", "what", "nice", "good", "yes!"} {
		fmt.Printf("%s -> %s\n", key, c.Get(key))
	}

输出结果:

// Expect output
// -------------
// what -> C
// nice -> A
// what -> C
// nice -> A
// good -> D
// yes! -> E

这样结果就会比较均匀,当我们的key值代表node的时候,如:127.0.0.1,127.0.0.2…使数据均匀的缓存到node中去.

3.singleflight解析

如果一个node短时间内收到了多个对同一key值的查询,那么我们应该只处理第一个,然后其他请求都返回该值.

func (g *Group) Do(key string, fn func() (interface{}, error)) (interface{}, error) {
	g.mu.Lock()
	if g.m == nil {
		g.m = make(map[string]*call)
	}
	if c, ok := g.m[key]; ok {
		g.mu.Unlock()
		c.wg.Wait()
		return c.val, c.err
	}
	c := new(call)
	c.wg.Add(1)
	g.m[key] = c
	g.mu.Unlock()

	c.val, c.err = fn()
	c.wg.Done()

	g.mu.Lock()
	delete(g.m, key)
	g.mu.Unlock()

	return c.val, c.err
}

以上代码表示:g有一个map来保存该caller与key的映射,当m==nil表示没有对该key的请求进入,此时应初始化该map,此时注意:c.val, c.err = fn()这一行是主要做计算的步骤,在这行以前应该设置好key到一个caller的映射,并设置wg.Add(1),计算完成后,再将map删除掉:delete,在删除以前,有可能其他的对该key的请求进来,则会进入到第二个if逻辑中,根据key值拿到前面设置的那个caller,并且通过wg.Wait(),等待caller被处理完,即:wg.Done(),拿到结果后直接返回.

4.groupcache 解析

type Group struct {
	name       string
	getter     Getter
	peersOnce  sync.Once
	peers      PeerPicker
	cacheBytes int64 // limit for sum of mainCache and hotCache size
	mainCache cache	
	hotCache cache
	loadGroup flightGroup
	_ int32 // force Stats to be 8-byte aligned on 32-bit platforms

	// Stats are statistics on the group.
	Stats Stats
}

type cache struct {
	mu         sync.RWMutex
	nbytes     int64 // of all keys and values
	lru        *lru.Cache
	nhit, nget int64
	nevict     int64 // number of evictions
}

//lru.Cache
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,cache中又是lru的Cache结构来存储数据,主要是一个链表ll,用来做数据item的活跃情况,删除时选取链表最后一个:从链表删除并从cache的map中删除.请求了一个item后会将它移到链表的最前面,表示活跃.cache是一个map用来存数据.

回到Group,当初始化一个Group时,会在变量groups = make(map[string]*Group)这样一个map里面加入该key和Group,

Contents

1.源文件作用

2.consistanthash解析

3.singleflight解析

4.groupcache 解析